Bdq的IT技术博客

在一篇文章强化学习与马尔可夫决策中，介绍了使用马尔可夫决策过程对强化学习的过程进行建模。通过建模可以得出，只要求解最优价值函数，即可得到对应的最优策略。那么如何求解最优价值函数呢？本篇文章将介绍一些最优价值函数的求解算法。

predict和control

首先介绍一下强化学习的两个基本问题，预测和控制。

predict

在已知状态集$S$，动作集$A$，模型状态转化概率矩阵$P$，即时奖励$R$，衰减因子$\gamma$的条件下，给定策略$\pi$，预测该策略的状态价值函数$v(\pi)$。这一过程一般称为策略评估。

control

在已知状态集$S$，动作集$A$，模型状态转化概率矩阵$P$，即时奖励$R$，衰减因子$\gamma$的条件下，求解最优的状态价值函数$v_*$和最优策略$\pi_*$。

从mode-based的方面去看这两个问题其实更好理解，在了解模型机制的基础上，预测所有可能的状态价值函数，然后基于预测的值，来选取最优价值函数和最优策略，这个过程被称为策略迭代。

动态规划

动态规划是一种可以求解强化学习两个基本问题的一种方式，其理论依据是贝尔曼方程。状态价值函数的贝尔曼方程如下：

$v_\pi=\sum_{a\epsilon A}\pi(a|s)(R_a^s+\gamma\sum_{{s'}\epsilon S}P_{ss'}^av_\pi(s'))$

通过这个公式可以看出，当前迭代周期某状态$s$的状态价值，可以通过上一个迭代周期内的状态价值来计算更新。这就满足了使用动态规划的两个条件，问题的最优解可以由子问题的最优解构成且可以通过较小的子问题状态递推出较大子问题的状态。

策略评估

结合贝尔曼方程，预测问题求解的过程如下：

$v_{k+1}^\pi(s)=\sum_{a\epsilon A}\pi(a|s)(R_s^a+\gamma\sum_{{s'}\epsilon S}P_{ss'}^av_k^\pi(s'))$

其中$v_k(s)$表示第$k$轮状态$s$的价值函数。

策略迭代

控制问题的求解一般可以使用greedy策略。对于当前状态$s_t$，选择后续所有可能转移到的状态集合$S_{t+1}$中，状态价值最大的那个状态对应的策略$\pi$。

整个策略迭代过程可以理解为以下两个过程：

1. 使用当前策略$\pi$评估计算当前策略的状态价值$v(s)$。

2. 根据状态价值$v(s)$根据一定的方法（比如贪婪法）更新策略$\pi$。

重复迭代以上两个过程，最终得到收敛的策略$\pi_*$和状态价值$v_*$。

蒙特卡洛法

蒙特卡洛法是一种通过采样近似求解问题的方法。与动态规划不同，蒙特卡洛法不需要考虑交互过程中的状态转化，其通过采样若干完整的交互状态序列来估计状态的真实值。

完整的交互状态序列指的是从开始到终点的交互序列，可以在迭代的过程中产生。通过多组完整的交互状态序列进行来近似的估计状态价值，之后便可以求解预测和控制问题了。

由于蒙特卡洛法是通过采样的方式来估计状态价值，不需要考虑交互过程中状态的转化，因此属于mode-free的强化学习求解方法。反观动态规划，由于考虑状态的转化，因此属于mode-based的强化学习求解方法。

策略评估

使用蒙特卡洛法进行策略评估的理论依据是状态价值函数的定义：

$v_\pi(s)=E_\pi(G_t|S_t=s)=E_\pi(R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+...|S_t=s)$

从公式上可以看出，每个状态的价值函数，等于其后续所有的奖励与对应的衰减乘积求和的期望。

因此，对于一个策略$\pi$，如果采样得到的完整的$T$个交互状态序列如下：

$S_1,A_1,R_2,S_2,A_2,...,S_t,A_t,R_{t+1},...,R_T,S_T$

那么对于$t$时刻的状态价值函数可以通过下面的方式进行求解：

$\begin{gathered} G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+...\gamma^{T-t-1}R^T\\ v_\pi(s)\approx average(G_t),s.t.S_t=s \end{gathered}$

如此一来，就简单的解决了预测问题，不过还可以进行进一步的优化。在上式中，计算状态价值函数需要使用到后续所有奖励的均值，这意味着必须存储相关的所有奖励的值，而且其存储量会随着采样数量的增加而增加。

为了解决这个问题，引入了累计更新平均值的方法，即下面这个公式：

$\begin{aligned} \mu_k&=\frac{1}{k}\sum_{j=0}^kx_j\\ &=\frac{1}{k}(x_k+\sum_{j=0}^{k-1}x_j)\\ &=\frac{1}{k}(x_k+(k-1)\mu_{k-1})\\ &=\mu_{k-1}+\frac{1}{k}(x_k-\mu_{k-1}) \end{aligned}$

其中$\mu_k$表示第$k$轮迭代的均值，$\mu_{k-1}$表示第$k-1$轮迭代的均值。

参考这个公式，我们可以将状态价值公式的计算改写为：

$\begin{gathered} N_k(S_t)=N_{k-1}(S_t)+1\\ V_k(S_t)=V_{k-1}(S_t)+\frac{1}{N_k(S_t)}(G_t-V_{k-1}(S_t)) \end{gathered}$

这样一来，只需要保存上一轮的次数和对应的收获，即可求解当前轮次的均值。如果数据量过大，以至于$N_k(S_t)$无法准确的计算，还可以使用一个系数$\alpha$来代替，将更新公式改为：

$V_k(S_t)=V_{k-1}(S_t)+\alpha(G_t-V_{k-1}(S_t))$

根据状态价值函数的求解公式，同时可以类推出动作价值函数的求解公式：

$Q_k(S_t,A_t)=Q_{k-1}(S_t,A_t)+\alpha(G_t-Q_{k-1}(S_t,A_t))$

策略迭代

与动态规划不同，蒙特卡洛法的目标是得到最优动作函数$q_*$而不是最优价值函数$v_*$。同时，蒙特卡洛法在进行策略选取的时候，使用的也不是greedy法，而是$\epsilon$-greedy法。

$\epsilon$-greedy的区别是增加了一个参数$\epsilon$。在进行策略选择时，使用1-$\epsilon$的概率选择当前最大的动作函数对应的动作，$\epsilon$的概率随机在$m$个动作中选取一个动作。用公式表示如下：

$\pi(a|s)= \begin{cases} \epsilon/m+1-\epsilon &\text{if } a^*=\arg\max_{a\epsilon A}Q(s,a)\\ \epsilon/m &\text{else} \end{cases}$

一般来说$\epsilon$的取值一般比较小，且在实际使用中会随着训练的不断迭代而减小。在强化学习训练的过程中，通过这种随机选取动作的方式，可以增加样本的多样性，探索到更多的样本空间。

完整的算法流程如下:

1. 初始化所有的动作价值$Q(s,a)=0$， 状态次数$N(s,a)=0$，采样次数$k=0$，随机初始化一个策略$\pi$。

2. $k=k+1$, 基于策略进行第$k$次蒙特卡罗采样，得到一个完整的状态序列:

   $S_1,A_1,R_2,S_2,A_2,...,S_t,A_t,R_{t+1},...,R_T,S_T$

3. 对于该状态序列里出现的每一状态行为对，计算其收获, 更新其计数和行为价值函数：

   $\begin{gathered} G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+...\gamma^{T-t-1}R^T\\ N(S_t,A_t)=N(S_t,A_t)+1\\ Q(S_t,A_t)=Q(S_t,A_t)+\frac{1}{N(S_t,A_t)}(G_t-Q(S_t,A_t)) \end{gathered}$

4. 基于新计算出的动作价值，更新当前的$\epsilon$-greedy策略：

   $\begin{gathered} \epsilon=\frac{1}{k}\\ \pi(a|s)= \begin{cases} \epsilon/m+1-\epsilon &\text{if } a^*=\arg\max_{a\epsilon A}Q(s,a)\\ \epsilon/m &\text{else} \end{cases} \end{gathered}$

5. 如果所有的$Q(s,a)$收敛，则对应的所有$Q(s,a)$即为最优的动作价值函数$q_*$。对应的策略即为最优策略$\pi_*$。否则转到第二步。

时序差分TD

时序差分法与蒙特卡洛法一样，都是model-free强化学习问题的求解方法。区别在于，时序差分法是在没有采样到完整的交互序列的情况下，通过部分的状态序列去估计状态的价值。

策略评估

考虑状态价值函数的另一种形式：

$v_\pi(s)=E_\pi(R_{t+1}+\gamma{v_{\pi}(S_{t+1})}|S_t=s)$

时序差分法用$R_{t+1}+\gamma{v_{t+1}(s)}$来近似的代替收获$G_t$，使得只需要两个连续的状态和对应的奖励，即可求解。$R_{t+1}+\gamma{V(S_{t+1})}$一般称为TD目标值，$R_{t+1}+\gamma{V(S_{t+1})}-V(S_t)$称为TD误差，用TD目标值近似代替收获的过程称为引导(bootstrapping)。

因此，时序差分$G(t)$的表达式为：

$G(t)=R_{t+1}+\gamma V(S_{t+1})$

时序差分的价值函数迭代式为：

$\begin{gathered} V_k(S_t)=V_{k-1}(S_t)+\alpha(G_t-V_{k-1}(S_t))\\ Q_k(S_t,A_t)=Q_{k-1}(S_t,A_t)+\alpha(G_t-Q_{k-1}(S_t,A_t)) \end{gathered}$

其中$\alpha$是一个值为[0,1]之间的数。

策略迭代

对于时序差分，也可以用$\epsilon$-greedy来进行价值迭代，和蒙特卡罗法的区别主要只是在于收获的计算方式不同。

n步时序差分

普通的时序差分主要关注的是当前时刻以及下一时刻的状态价值，可以理解为向前一步来近似求解。n步时序差分的意思是向前n步来进行求解，其收获$G_t^{(n)}$的表达式如下：

$G_t^{(n)}=R_{t+1}+\gamma R_{t+2}+...+\gamma^{n-1}R_{t+n}+\gamma^nV(S_{t+n})$

当n趋于无穷大时，即覆盖到完整的交互序列时，n步时序差分也就变成了蒙特卡洛。与普通的时序差分相比，n步时序差分因为考虑了向前n步，所以会更加精确一些。

TD($\lambda$)

在使用n步时序差分的时候，这个n是一个超参数，需要通过不断的优化去选择一个最优的值。这一过程比较繁琐，为了解决这个问题，引入了一个值为[0,1]的参数$\lambda$。定义$\lambda$-收获是n从1到$\infty$所有步的收获乘以权重的和，每一步的权重是$(1-\lambda)\lambda^{n-1}$。

这样$\lambda$-收获可以表示为：

$G_t^\lambda=(1-\lambda)\sum_{n=1}^\infty\lambda^{n-1}G_t^{(n)}$

迭代函数可以表示为：

$\begin{gathered} V(S_t)=V(S_t)+\alpha(G_t^\lambda-V(S_t))\\ Q(S_t,A_t)=Q(S_t,A_t)+\alpha(G_t^\lambda-Q(S_t,A_t)) \end{gathered}$

从上面的式子可以看出，当$\lambda$等于0时，算法就变成了普通的时序差分，当$\lambda$等于1时，则变成了蒙特卡洛。因此，TD($\lambda$)就是在两者之间作了一个平衡。