Monte Carlo Learning
我们已经讨论的是强化学习中最简单的场景。在该场景中，状态转移可以用概率\(p_\delta(s'\mid s,a)\)来描述，即时奖励也可以用概率\(p_r(r\mid s,a)\)来描述。但是在更复杂的场景中，我们并不能做这样的假设。这样的场景称为model-free的，原先的场景称为model-based的。例如，在机器人走网格的例子中，现实中机器人想要在\(s\)处触发动作\(a\)可能会因为环境干扰导致动作触发失败或产生偏差，此时人类难以提前为\(p_\delta\)建模，也不可能在每个新环境都重新为\(p_\delta\)建模。再例如，在“围棋”的任务中，我们无法预测对手的动作，所以如果把动作定义为“己方下一步棋”，那我们根本不可能提前用概率来建模\(p_\delta\)，或者说\(p_\delta\)本身就是我们希望机器自己学会的东西。在围棋中，即时奖励也是无法提前设定的，关于奖励只有一个确切的信号，那就是最终的输赢。所以，在这些更复杂的情况下我们需要对应的强化学习算法。上面介绍的基于贝尔曼方程的算法，本质上只是在模型给定时做了一个动态规划。
考虑一个马尔可夫决策过程，其中即时奖励的概率\(p_r(r\mid s,a)\)已知，但是状态转移的概率\(p_\delta(s'\mid s,a)\)未知。这样，值迭代或者策略迭代的方法就失效了，因为它们都需要在给定\(s,a\)时用\(p_\delta\)计算动作值\(\sum\limits_{r}r\cdot p_r(r\mid s,a)+\gamma \cdot\sum\limits_{s'}p_\delta(s'\mid s,a)\cdot v(s')\)。
解决这个问题的方法就是用实际的“采样”来代替提前设定的“概率”，这样的方法通常称为蒙特卡洛学习法(Monte Carlo learning)。蒙特卡洛方法的数学基础就是大数定律。动作值\(q(s,a)\)的含义是从状态\(s\)做动作\(a\)以后返回值的期望，此时我们可以在真实环境中做\(N\)次采样\(g^{(i)}(s,a)\)，因为动作的即时奖励的概率分布是已知的，所以我们可以记录下每次采样对应的奖励值。将\(N\)次采样的结果取平均，得到的\(\dfrac{1}{N}\sum\limits_{i=1}^{N}g^{(i)}(s,a)\)就可以看作\(q(s,a)\)的近似值。这样我们就又可以用值迭代或者策略迭代的方法来求最优策略了，其中策略的计算公式需要替换为\(\pi(a\mid s):=\mathbb{1}\left[a=\arg\max\limits_{a_0}\left(\dfrac{1}{N}\sum\limits_{i=1}^{N}g^{(i)}(s,a_0)\right)\right]\)。
像上面这样做蒙特卡洛学习的运算成本是非常高的。假设每一次模拟平均会做出\(m\)次决策才到达终点，采样进行\(N\)次，动作值需要对每个状态和每个动作计算，并且计算次数和整个算法的迭代次数\(K\)一致。所以整个过程的复杂度至少为\(O(mNK\cdot |S|\cdot|A|)\)。
上面的算法可以做优化。假如在一次采样中，从\(s_1,a_1\)开始，先后经历了\(s_2,a_2,\cdots,a_{m-1},s_m\)到达终点，求得总奖励为\(R\)，那么这一结果\(R\)同样适用于\(g(s_2,a_2)\)，\(g(s_3,a_3),\cdots\)，而不仅仅适用于\(g(s_1,a_1)\)。这样，我们就把采样效率提高了\(m\)倍。
上面的优化加快了采样的效率，但是我们至少还是需要从每一对\((s,a)\)出发做采样，这样才能保证覆盖到了所有的\((s,a)\)。实践中还有一个常用的做法，是在迭代中对策略\(\pi\)做一点平滑处理。原先的策略是“greedy(贪心)”的，它总会把全部的概率分配给动作值最大的方向，而对其他所有方向分配概率\(0\)。我们这样做平滑处理：选定一个常数\(\varepsilon\in (0,1)\)，对于动作值非最大的方向，分配概率\(\dfrac{\varepsilon}{|A|}\)；剩余的概率分配给动作值最大的方向，概率为\(1-\dfrac{\varepsilon}{|A|}(|A|-1)\)。在这样的设定下，我们任意选定一个起始点\((s,a)\)做采样，只要时间足够长，我们就可以采集到所有点上的动作值。我们把这样的策略称为\(\varepsilon\)-greedy的策略。实践证明，这样做很大程度提高了采样的效率。但是注意，最优策略应当是greedy策略而不是\(\varepsilon\)-greedy策略。一个办法是，在求最优策略时，我们再反过来把\(\varepsilon\)-greedy策略转化为greedy策略：只需把分配概率最大的方向改为概率\(1\)，其余的改为概率\(0\)。这样的转化在\(\varepsilon\)很小的时候往往能被证明是有效的。
如果\(\varepsilon\)太大，那么greedy策略与\(\varepsilon\)-greedy策略的转化会影响决策最优性；如果\(\varepsilon\)太小，那么采样的效率就会降低。所以实践中，我们需要调整参数\(\varepsilon\)来达到最好的效果。一个常见的办法是，在刚开始采样的时候设定较高\(\varepsilon\)的值，以提高效率；随后慢慢降低\(\varepsilon\)，以保证最优性。
Stochastic Approximation
上面这种用“采样”来代替“建模”的方法，其实反映出统计学方法中的一个核心观念：要能做出好的决策，要么需要建立好的数学模型，要么需要充分的统计数据。关于如何高效地用采样代替建模，发展出了一个称为随机近似(stochastic approximation)的学科。让我们初步讨论一下这门学科。
\(\newcommand{\E}{\mathbb{E}}\)随机近似中最基本的问题是，给定一个随机变量\(X\)，当我并不事先清楚\(X\)的概率分布时，如何求出\(X\)的期望？蒙特卡洛方法的做法是，对\(X\)做\(N\)次采样\(\{x_i\}\)，根据大数定律可知当\(N\)足够大时\(\dfrac{1}{N}\sum\limits_{i=1}^{n}x_i\)就“逼近”\(\E [X]\)（这里的“逼近”的严格表述就是概率论中的随机过程的收敛性，根据“依概率收敛”和“almost surely收敛”分为弱大数定理和强大数定理）。我们可以对这个方法做一些小的调整：令\(w_{k+1}=\dfrac{1}{k}\sum\limits_{i=1}^{k}x_i\)，那么序列\(\{w_{k}\}\)就可以可视化地展示出平均值是如何逼近期望的。而显然，\(w_k\)可以这样递推地计算：\(w_{k+1}=\dfrac{(k-1)w_k+x_{k}}{k}\)。整理一下，写作：
可见，\(w_{k+1}\)与\(w_{k}\)之间只相差一个修正项\(-\dfrac{1}{k}(w_k-x_k)\)，这个修正项正比于新的一次采样结果\(x_k\)与上一次的平均值\(w_k\)的差，再乘上一个反比于步数\(k\)的系数。
Robins-Monro Algorithm
我们来推广一下上面这个问题。上面的问题其实等价于求解关于\(w\)的方程\(w-\E[X]=0\)。也即\(\E[w-X]=0\)。令\(g(w)=\E[w-X]\)，我们就是要近似求解方程\(g(w)=0\)的根。然而，我们并不提前清楚\(g\)这个函数的解析式，甚至也不能把\(g\)看作一个能够返回准确值的黑盒：对于任意\(w_0\)，我们并不知道\(g(w_0)\)的准确值。但是对于任意\(w_0\)，我们可以用“采样”的方法来获取\(g(w_0)\)的一个近似值。 例如，对于给定的\(w_0\)，我们可以对\(X\)进行一次采样得到\(x_0\)，然后把\(\tilde g(w_0)=w_0-x_0\)看作\(g(w_0)\)的近似值，这个近似值与准确值之间实际上有偏差\(g(w_0)-\tilde g(w_0)=x_0-\E[X]\)。
所以我们可以这样描述推广后的问题：要尽量准确地求解方程\(g(w)=0\)的根，其中\(g\)的表达式是未知的，并且对于第\(k\)次采样，输入\(w_k\)我们能获得\(\tilde g(w_k)\)，它满足\(\tilde g(w_k)-g(w_k)=\eta_k\)，\(\eta_k\)是第\(k\)次采样的噪声(noise)。
上一节的例子告诉我们，当\(g\)的真实表达式为\(g(w)=\E[w-X]\)时，我们可以用下面这个迭代算法逼近\(g\)的根：\(w_{k+1}=w_k-\dfrac{1}{k}\tilde g(w_k)\)。大数定律保证了这个算法的正确性。
随机近似中有一个奠基性的算法，称为Robbins-Monro(RM)算法。它说我们可以用下面的迭代算法来求\(g\)的根：
只要满足下面三个条件，上面这个递推式中\(w_k\)就会（almost surely）收敛到\(g\)的根：
- 存在常数\(c_1,c_2\)，使得\(\forall w,0<c_1\leq \nabla_w g(w)\leq c_2\)；
- \(\sum\limits_{i=1}^{\infty}a_i=\infty\)且\(\sum\limits_{i=1}^{\infty}a_i^2<\infty\)；
- \(\E[\eta_k\mid \mathcal{H}_k]=0\)且\(\E[\eta_k^2\mid \mathcal{H}_k]<\infty\)；其中，\(\eta_k=\tilde g(w_k)-g(w_k)\)，\(\mathcal{H}_k:=\{w_k,w_{k-1},\cdots\}\)
Stochastic Gradient Descent
我们来看RM算法的一个应用，称为随机梯度下降，这个算法在机器学习和强化学习中都有广泛应用。
我们的问题是：要求函数\(J(w)\)的最小值，其中这个函数\(J(w)\)可以写成\(J(w)=\E[f(w,X)]\)的形式。
普通的梯度下降的做法是：做迭代\(w_{k+1}=w_k-\alpha_k\nabla _w J(w)\)。这要求我们能够求出\(\nabla_w J(w)\)，也就是求出\(\nabla _w\E[f(w,X)]=\E[\nabla_w f(w,X)]\)。
我们可以用蒙特卡洛的“采样”代替“求期望”的方法，把上面这个算法改为\(w_{k+1}=w_k-\alpha_k\cdot \dfrac{1}{N} \sum\limits_{i=1}^{n}\nabla_w f(w_k,x_i)\)。这就称为Batch Gradient descent算法，其中\(N\)就称为batch的大小。
现在，我们可以用RM算法来改进Batch Gradient Descent。要求\(J(w)\)的最小值，通常的做法就是解方程\(\nabla _w J(w)=0\)。所以RM算法中的\(g(w)\)我们就用\(\nabla_wJ(w)\)，也就是\(\E[\nabla_w f(w,X)]\)来代替。根据RM算法，只要满足三个条件，递推式\(w_{k+1}=w_k-\alpha_k \nabla_w f(w_k,x_k)\)就会正确地收敛到\(\nabla_w J(w)=0\)的点上。因此，只要我们选取合适的步长\(\alpha_k\)使之满足RM算法的条件，同时函数\(J\)满足恰当的性质使得RM算法的条件成立，这样一个batch大小为\(1\)的迭代算法就已经能正确求出\(J(w)\)的最小值了。这就是随机梯度下降(stochastic gradient descent)算法。
参考资料
[1] 赵世钰 《强化学习的数学原理》