02 Monte-Carlo Learning

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)的学科。让我们初步讨论一下这门学科。

随机近似中最基本的问题是，给定一个随机变量$X$，当我并不事先清楚$X$的概率分布时，如何求出$X$的期望？蒙特卡洛方法的做法是，对$X$做$N$次采样$\{x_i\}$，根据大数定律可知当$N$足够大时$\dfrac{1}{N}\sum\limits_{i=1}^{n}x_i$就“逼近”$\mathbb{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)$$

可见，$w_{k+1}$与$w_{k}$之间只相差一个修正项$-\dfrac{1}{k}(w_k-x_k)$，这个修正项正比于新的一次采样结果$x_k$与上一次的平均值$w_k$的差，再乘上一个反比于步数$k$的系数。

Robins-Monro Algorithm

我们来推广一下上面这个问题。上面的问题其实等价于求解关于$w$的方程$w-\mathbb{E}[X]=0$。也即$\mathbb{E}[w-X]=0$。令$g(w)=\mathbb{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-\mathbb{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)=\mathbb{E}[w-X]$时，我们可以用下面这个迭代算法逼近$g$的根：$w_{k+1}=w_k-\dfrac{1}{k}\tilde g(w_k)$。大数定律保证了这个算法的正确性。

随机近似中有一个奠基性的算法，称为Robbins-Monro(RM)算法。它说我们可以用下面的迭代算法来求$g$的根：

$$w_{k+1}=w_k-a_k\tilde g(w_k)$$

只要满足下面三个条件，上面这个递推式中$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$；
• $\mathbb{E}[\eta_k\mid \mathcal{H}_k]=0$且$\mathbb{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)=\mathbb{E}[f(w,X)]$的形式。

普通的梯度下降的做法是：做迭代$w_{k+1}=w_k-\alpha_k\nabla _w J(w)$。这要求我们能够求出$\nabla_w J(w)$，也就是求出$\nabla _w\mathbb{E}[f(w,X)]=\mathbb{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)$，也就是$\mathbb{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] 赵世钰 《强化学习的数学原理》