Reinforcement Learning

术语

情节性 episodic

每经过T个episode后重置状态（比如走迷宫撞墙后回到初始状态）

对于非情节性的MDP需要让 γ < 1 以避免无限积累奖励值

有限状态马尔可夫决策过程 FMDP

大多数RL问题针对的就是FMDP（状态 S、动作 A、状态转移 P(s_t+1|s_ta_t)、即时奖励函数 R(s_t, a_t, s_t+1)、折扣因子 γ

部分可观察马尔可夫决策过程 POMDP

需要对^[1]和^[2]分别讨论

马尔可夫决策问题MDP

策略

策略 $\pi$ 决定了^[3]的状态分布

轨迹 $\tau$ 代表一场游戏的行动轨迹 $(s_0,a_0,s_1,a_1,...)$ ， $\tau\sim\pi$ 表示该轨迹的分布满足指定策略

在强化学习中策略可以看成在某个状态s下选择行为a的概率（或者说选择方案）

强化学习的目标是：找到最优策略 $\pi$ ，使得该策略下的^[3:1]期望最大，即： $\max_{\pi}\int{R\left(\tau\right)}p_{\pi}\left(\tau\right)d\tau$

状态值函数

状态值函数用来评价一个策略是否最优

最优状态值函数 $\upsilon^*\left(s\right)$ ,为在所有策略中值最大的值函数即： $\upsilon^*\left(s\right)=\max_{\pi}\upsilon_{\pi}\left(s\right)$

$q^*\left(s,a\right)=R_{s}^{a}+\gamma\sum_{s'\in S}{P_{ss'}^{a}\max_{a'}q^*\left(s',a'\right)}\\\\\left(1.13\right)$

状态-动作值函数

状态-动作值函数用来决定在状态s下选择行为a的策略

最优状态-行为值函数 $q^*\left(s,a\right)$ 为在所有策略中最大的状态-行为值函数，即： $q^*\left(s,a\right)=\max_{\pi}q_{\pi}\left(s,a\right)$

若已知最优状态-动作值函数，最优策略可通过直接最大化 $q^*\left(s,a\right)$ 来决定：

$\pi_*\left(a|s\right)=\left\{\begin{array}{c} 1\ if\ a=\underset{a\in A}{arg\max}q_*\left(s,a\right)\\ 0\ otherwis\\ \end{array}\right.$

优势函数

值函数 $V(s)$ 是该状态下所有动作值函数关于动作概率的平均值

动作值函数 $Q(s,a)$ 是单个动作所对应的值函数

$Q_{\pi}\left(s,a\right)-V_{\pi}\left(s\right)$ 能评价当前动作值函数相对于平均值的大小，即当前动作的“优势”

贝尔曼方程

描述马尔可夫决策过程中，通过下一个状态来推导当前状态状态值函数/状态行为值函数的过程：

V(s)=\mathbb{E}\left[R_{t+1}+\lambda V\left(S_{t+1}\right) \mid S_{t}=s\right]

Q_{\pi}(s, a)=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma Q_{\pi}\left(S_{t+1}, A_{t+1}\right) \mid S_{t}=s, A_{t}=a\right]

它表明 Value Function 是可以通过迭代来进行计算的，其具体的数学表达为：

V_{\pi}(s)=\sum_{a \in \mathcal{A}} \pi(a \mid s)\left(\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} V_{\pi}\left(s^{\prime}\right)\right)

Q_{\pi}(s, a)=\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} \sum_{a^{\prime} \in \mathcal{A}} \pi\left(a^{\prime} \mid s^{\prime}\right) Q_{\pi}\left(s^{\prime}, a^{\prime}\right)

基于贝尔曼方程，一种浅显的强化学习更新思路是：在当前状态 $s_t$ 下执行状态行为值函数 $Q_\pi(s_t,a_t)$ 最大的行为 $a_t$ ，当游戏结束时，再从终止状态开始逐层用贝尔曼方程去反向更新每一步的状态行为值函数。

强化学习算法分类

值函数最优化——动态规划方法

已知模型(S, A, P, R, γ)，可以用动态规划方法来求解

主要包括策略迭代算法、值迭代、策略搜索方法，我们主要关注前两个
策略最优化——策略优化方法

未知模型参数(P, R, γ)，用强化学习来解决无模型的MDP问题

主要包括蒙特卡罗方法和时间差分方法

策略迭代算法

策略迭代算法包括^[4]和^[5]两个步骤。即先对当前策略进行策略评估，也就是说计算出当前策略所对应的值函数；然后，利用值函数改进当前策略

通过策略评估和策略改进得到最优值函数。从策略迭代的伪代码我们看到，进行策略改进之前需要得到收敛的值函数。

值函数迭代

如果我们在进行一次^[4:1]之后就进行[^策略改善]，则称为值函数迭代算法。

除了基础的值函数迭代外还有很多求解方法，在此不过多展开

- 基于变分法的方法是最早的方法，其局限性是无法求解带有约束的优化问题。
- 基于庞特里亚金最大值原理的方法在变分法基础上进行发展，可以解决带约束的优化问题。
- 相比于这两种经典的方法，动态规划的方法相对独立，主要是利用贝尔曼最优性原理。

蒙特卡洛算法

在计算值函数时，蒙特卡罗方法是利用经验平均代替随机变量的期望。

所谓经验，是指利用该策略做很多次试验，产生很多幕数据。这里一幕是一次试验的意思。由于不知道智能体与环境交互的模型，蒙特卡罗方法是利用经验平均来估计值函数。能否得到正确的值函数，取决于经验。如何获得充足的经验是无模型强化学习的核心所在。

$V\left(S_t\right)\gets V\left(S_t\right)+\alpha\left(G_t-V\left(S_t\right)\right)$

$G_t$ 是状态 $S_t$ 后直到终止状态所有回报的返回值。

在蒙特卡洛方法中必须采用一定的方法保证每个状态都能被访问到。其中一种方法是探索性初始化。所谓探索性初始化是指每个状态都有一定的几率作为初始状态。

温和的探索策略是指在任意状态下，采用动作集中每个动作的概率都大于零。典型的温和策略是 $\varepsilon -soft$ 策略。

根据探索策略（行动策略）和评估的策略是否是同一个策略，蒙特卡罗方法又分为 on-policy 和 off-policy。off-policy 主要使用重要性采样原理。（重要性采样的过程中可以去除状态转移P）

相比于动态规划的方法，蒙特卡罗的方法需要等到每次试验结束，所以学习速度慢，学习效率不高。

时间差分算法

从概念上说是蒙特卡洛方法和DP方法的结合与衍生。简单来说，就是在不等待一局游戏最终的实际结果的情况下，从下一个猜测中学习一个猜测，即根据对下一步状态的估计价值来训练对当前价值的估计。

$V\left(S_t\right)\gets V\left(S_t\right)+\alpha\left(R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_t\right)\right)$

其中 $R_{t+1}+\gamma V\left(S_{t+1}\right)$ 称为TD目标，与蒙特卡洛方法中的 $G_t$ 相对应，两者不同之处是TD目标利用了 bootstrapping 方法估计当前值函数。 $\delta_t=R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_t\right)$ 称为TD偏差。

蒙特卡罗的方法使用的是值函数最原始的定义，该方法利用所有回报的累积和估计值函数。DP 方法和 TD 方法则利用一步预测方法计算当前状态值函数。其共同点是利用了 bootstrapping 方法，不同的是，DP 方法利用模型计算后继状态，而 TD 方法利用试验得到后继状态。

Q-Learning 是典型的 off-policy TD 算法，它的行动采用 ε 贪婪策略来寻找当前状态 s 的行动 a，并进入下一个状态 s’，当进行状态评估时，用贪婪策略寻找让 s’ 值函数最大的 a’，进而更新值函数；而 Sarsa 是典型的 on-policy TD 算法，在行动和评估时都采用 ε 贪婪策略来寻找行动 a 和 a’。

TD 算法也可以通过 n 步值函数估计当前值函数：

$G_{t}^{\left(n\right)}=R_{t+1}+\gamma R_{t+2}+\cdots +\gamma^{n-1}R_{t+n}+\gamma^nV\left(S_{t+n}\right)$

为了保证估计值更加接近真实值，我们对 n 步值函数中的每一步进行加权融合，就是TD(λ)方法：

$G_{t}^{\lambda}=\left(1-\lambda\right)G_{t}^{\left(1\right)}+\left(1-\lambda\right)\lambda G_{t}^{\left(2\right)}+\cdots +\left(1-\lambda\right)\lambda^{n-1}G_{t}^{\left(n\right)} \\ \approx\left[\left(1-\lambda\right)+\left(1-\lambda\right)\lambda +\cdots +\left(1-\lambda\right)\lambda^{n-1}\right]V\left(S_t\right) \\ =V\left(S_t\right)$

TD(λ)的前向观点：

$V\left(S_t\right)\gets V\left(S_t\right)+\alpha\left(G_{t}^{\left(\lambda\right)}-V\left(S_t\right)\right)$

利用TD(λ)的前向观点估计值函数时， $G_{t}^{\lambda}$ 的计算用到了将来时刻的值函数，因此需要等到整个试验结束之后。这跟蒙塔卡罗方法相似。

TD(λ)的后向观点：

$\delta_t=R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_t\right)$

$E_t\left(s\right)=\left\{\begin{array}{l} \gamma\lambda E_{t-1},\ if\ s\ne s_t\\ \gamma\lambda E_{t-1}+1,\ if\ s=s_t\\ \end{array}\right.$

$V\left(s\right)\gets V\left(s\right)+\alpha\delta_tE_t\left(s\right)$

前向观点需要等到一次试验之后再更新当前状态的值函数；而后向观点不需要等到值函数结束后再更新值函数，而是每一步都在更新值函数，是增量式方法。

前向观点在一次试验结束后更新值函数时，更新完当前状态的值函数后，此状态的值函数就不再改变。而后向观点，在每一步计算完当前的TD误差后，其他状态的值函数需要利用当前状态的TD误差进行更新。

在一次试验结束后，前向观点和后向观点每个状态的值函数的更新总量是相等的，都是 $G_{t}^{\lambda}$ 。

很明显TD(λ)是on-poliicy的，一般常用后向观点Sarsa(λ)：

值函数逼近

在表格型强化学习中，值函数对应着一张表。在值函数逼近方法中，值函数对应着一个逼近函数 $\hat{\upsilon}\left(s\right)$ 。从数学角度来看，函数逼近方法可以分为参数逼近和非参数逼近，因此强化学习值函数估计可以分为参数化逼近和非参数化逼近。其中参数化逼近又分为线性参数化逼近和非线性化参数逼近。

所谓参数化逼近，是指值函数可以由一组参数 $\varTheta$ 来近似。我们将逼近的值函数写为： $\hat{\upsilon}\left(s,\theta\right)$ 。

函数逼近 $\hat{\upsilon}\left(s,\theta\right)$ 的过程是一个监督学习的过程，其数据和标签对为： $\left(S_t,U_t\right)$ , 其中 $U_t$
等价于蒙特卡罗方法中的 $G_t$ ，TD方法中的 $r+\gamma Q\left(s',a'\right)$ ，以及 $TD\left(\lambda\right)$ 中的 $G_{t}^{\lambda}$ 。

训练的目标函数为：

$argmin_{\theta}\left(q\left(s,a\right)-\hat{q}\left(s,a,\theta\right)\right)^2$

策略梯度方法

在值函数的方法中，我们迭代计算的是值函数，然后根据值函数对策略进行改进；而在策略搜索方法中，我们直接对策略进行迭代计算，也就是迭代更新参数值，直到累积回报的期望最大，此时的参数所对应的策略为最优策略。

强化学习的目标是找到最优参数 $\theta$ 使得： $\max_{\theta}U\left(\theta\right)=\max_{\theta}\sum_{\tau}{P\left(\tau ;\theta\right)R\left(\tau\right)}$

$R\left(\tau\right)=\sum_{t=0}^H{R\left(s_t,u_t\right)}$

这时，策略搜索方法，实际上变成了一个优化问题。解决优化问题有很多种方法，比如：最速下降法，牛顿法，内点法等等。其中最简单，也是最常用的是最速下降法，此处称为策略梯度的方法。

$\theta_{new}=\theta_{old}+\alpha\nabla_{\theta}U\left(\theta\right)$

$\nabla_{\theta}U\left(\theta\right)\approx\hat{g}=\frac{1}{m}\sum_{i=1}^m{\nabla_{\theta}\log P\left(\tau ;\theta\right)R\left(\tau\right)}$

其中第一项 $\nabla_{\theta}\log P\left(\tau ;\theta\right)$ 是轨迹 $\tau$ 的概率随参数 $\theta$ 变化最陡的方向，参数在该方向进行更新时，若沿着正方向，则该轨迹 $\tau$ 的概率会变大，而沿着负方向进行更新时，该轨迹 $\tau$ 的概率会变小。再看第二项 $R\left(\tau\right)$ ，该项控制了参数更新的方向和步长。 $R\left(\tau\right)$ 为正且越大则参数更新后该轨迹的概率越大； $R\left(\tau\right)$ 为负，则降低该轨迹的概率，抑制该轨迹的发生。因此，策略梯度从直观上进行理解时，我们发现策略梯度会增加高回报路径的概率，减小低回报路径的概率。

TRPO

TRPO主要解决的是选择步长、找到新的策略使得新的回报函数的值单调增或单调不减的问题。一个自然地想法是能不能将新的策略所对应的回报函数分解成旧的策略所对应的回报函数+其他项。只要新的策略所对应的其他项大于等于零，那么新的策略就能保证回报函数单调不减。其实是存在这样的等式，这个等式是2002年Sham Kakade提出来的。TRPO的起点便是这样一个等式：

$\eta\left(\tilde{\pi}\right)=\eta\left(\pi\right)+E_{s_0,a_0,\cdots ~\tilde{\pi}}\left[\sum_{t=0}^{\infty}{\gamma^tA_{\pi}\left(s_t,a_t\right)}\right]$

这里我们用 $\pi$ 表示旧的策略，用 $\tilde{\pi}$ 表示新的策略。其中， $A_{\pi}\left(s,a\right)=Q_{\pi}\left(s,a\right)-V_{\pi}\left(s\right) \\ =E_{s'~P\left(s'|s,a\right)}\left[r\left(s\right)+\gamma V^{\pi}\left(s'\right)-V^{\pi}\left(s\right)\right]$

称为优势函数。

值函数 $V(s)$ 是该状态下所有动作值函数关于动作概率的平均值。而动作值函数 $Q(s,a)$ 是单个动作所对应的值函数， $Q_{\pi}\left(s,a\right)-V_{\pi}\left(s\right)$ 能评价当前动作值函数相对于平均值的大小。所以，这里的优势指的是动作值函数相比于当前状态的值函数的优势。如果优势函数大于零，则说明该动作比平均动作好，如果优势函数小于零，则说明当前动作还不如平均动作好。

对新旧策略回报差进行转化。优势函数的期望可以写成如下式：

$\eta\left(\tilde{\pi}\right)=\eta\left(\pi\right)+\sum_{t=0}^{\infty}{\sum_s{P\left(s_t=s|\tilde{\pi}\right)}}\sum_a{\tilde{\pi}\left(a|s\right)\gamma^tA_{\pi}\left(s,a\right)}$

其中 $P\left(s_t=s|\tilde{\pi}\right)\tilde{\pi}\left(a|s\right)$ 为 $(s,a)$ 的联合概率， $\sum_a{\tilde{\pi}\left(a|s\right)\gamma^tA_{\pi}\left(s,a\right)}$ 为求对动作 $a$ 的边际分布，也就是说在状态s对整个动作空间求和； $\sum_s{P\left(s_t=s|\tilde{\pi}\right)}$ 为求对状态 $s$ 的边际分布，即对整个状态空间求和； $\sum_{t=0}^{\infty}{\sum_s{P\left(s_t=s|\tilde{\pi}\right)}}$ 求整个时间序列的和。

我们定义 $\rho_{\pi}\left(s\right)=P\left(s_0=s\right)+\gamma P\left(s_1=s\right)+\gamma^2P\left(s_2=s\right)+\cdots$ ，则：

$\eta\left(\tilde{\pi}\right)=\eta\left(\pi\right)+\sum_s{\rho_{\tilde{\pi}}\left(s\right)\sum_a{\tilde{\pi}\left(a|s\right)A^{\pi}\left(s,a\right)}}$

如图所示：

通过TRPO的四个技巧，最终TRPO问题化简为：

$maximize_{\theta}E_{s~\pi_{\theta_{old}},a~\pi_{\theta_{old}}}\left[\frac{\pi_{\theta}\left(a|s\right)}{\pi_{\theta_{old}}\left(a|s\right)}A_{\theta_{old}}\left(s,a\right)\right] \\ subject\ to\ E_{s~\pi_{\theta_{old}}}\left[D_{KL}\left(\pi_{\theta_{old}}\left(\cdot |s\right)||\pi_{\theta}\left(\cdot |s\right)\right)\right]\le\delta$

接下来就是利用在旧策略中采样得到数据，求样本均值，解决上述优化问题，得到新的策略，不断迭代。

9.7更新

参考《如何看懂TRPO里所有的数学推导细节?》一文，TRPO的本质是找到一个对强化学习目标函数（累积折扣回报函数）的替代函数（下界函数），不断基于最新的策略找到替代函数的最优点来更新策略，从而完成算法收敛。

作为优化目标的期望折扣奖励 $\eta$ 可被表示为：

$\eta(\pi) = \mathbb{E}_{s_{0},a_{0},\cdots} \left[ \sum_{t=0}^{\infty} \gamma^{t} r(s_{t}) \right] \\$

新策略可在老策略的基础上表示为：

$\eta(\tilde{\pi})=\eta(\pi)+\sum_{s} \rho_{\tilde{\pi}}(s) \sum_{a} \tilde{\pi}(a | s) A_{\pi}(s, a) \\$

其中，任意时刻状态 $s$ 的访问概率 $\rho_{\pi}(s) = P(s_{0}=s) +\gamma P(s_{1} =s) + \gamma^{2} P(s_{2}=s) + \cdots$ 。

TRPO的目标是保证 $\sum_{s} \rho_{\tilde{\pi}}(s) \sum_{a} \tilde{\pi}(a | s) A_{\pi}(s, a) \geq 0$ ，即可使得 $\eta(\tilde{\pi}) \geq \eta(\pi)$ ，也就是说策略改变之后，整体的收益也会增加，从而实现单调递增。

一种直观的想法，我们需要先确定新的策略 $\tilde{\pi}$ ，然后使用这个新的策略得到一定量样本，并最终通过这些样本统计判断这个策略能够满足上述要求，使得策略递增。我们需要不断地去尝试每一个可能的新策略。显然这种做法非常低效，于是需要去找与上述公式的近似且可解的形式。

只要保证更新的幅度不大，就可以用旧的状态访问概率 $\rho_{\pi}(s)$ 替代 $\rho_{\tilde{\pi}}(s)$ ：

$\mathcal{L}_{\pi}(\tilde{\pi}) =\eta({\pi}) + \sum_{s} \rho_{\pi}(s) \sum_{a} \tilde{\pi}(a | s) A_{\pi}(s, a)$

于是就能设计下界函数：

M中的另一项为KL散度： $D_{KL}(P|Q|) = \mathbb{E}_{x} \text{log} \frac{P(x)}{Q(x)}$ ，表示两个分布的距离。更详细地，M中 $C = \frac{4 \varepsilon \gamma}{(1-\gamma)^{2}}$ ， $D_{KL}^{max}(\pi,\tilde{\pi}) = max_{s}D_{KL}(\pi(\cdot|s) || \tilde{\pi}(\cdot |s))$ 。

使用该下界函数，即可寻找一个比较优的新策略。

PPO

PPO 算法是一种新型的 Policy Gradient 算法，Policy Gradient 算法对步长十分敏感，但是又难以选择合适的步长，在训练过程中新旧策略的的变化差异如果过大则不利于学习。PPO 提出了新的目标函数可以在多个训练步骤实现小批量的更新，解决了 Policy Gradient 算法中步长难以确定的问题。其实 TRPO 也是为了解决这个思想但是相比于 TRPO 算法 PPO 算法更容易求解。

DDPG

随机策略的公式为：

$\pi_{\theta}\left(a|s\right)=P\left[a|s;\theta\right]$

确定性策略的公式为：

$a=\mu_{\theta}\left(s\right)$

采用随机策略时，即使在相同的状态，每次所采取的动作也很可能不一样。而确定性策略跟随机策略不同，相同的策略（即 $\theta$ 相同时)，在状态s时，动作是唯一确定的。

确定性策略的优点：需要采样的数据少，算法效率高

随机策略优点：将探索和改进集成到一个策略中

确定性策略无法探索环境，而是利用异策略学习方法，即off-policy，进行学习。异策略是指行动策略和评估策略不是一个策略。这里我们的行动策略是随机策略，以保证充足的探索。评估策略是确定性策略。整个确定性策略的学习框架采用^[6]的方法。

确定性策略异策略AC算法(DPG)的更新过程：

$\delta_t=r_t+\gamma Q^w\left(s_{t+1},\mu_{\theta}\left(s_{t+1}\right)\right)-Q^w\left(s_t,a_t\right)\\\\\ w_{t+1}=w_t+\alpha_w\delta_t\nabla_wQ^w\left(s_t,a_t\right) \\ \theta_{t+1}=\theta_t+\alpha_{\theta}\nabla_{\theta}\mu_{\theta}\left(s_t\right)\nabla_aQ^w\left(s_t,a_t\right)|_{a=\mu_{\theta}\left(s\right)}$

第一行和第二行是利用值函数逼近的方法更新值函数参数，第三行是利用确定性策略梯度的方法更新策略参数。目标值是式中的第一行的前两项，即：

$r_t+\gamma Q^w\left(s_{t+1},\mu_{\theta}\left(s_{t+1}\right)\right)$

DDPG是深度确定性策略，所谓深度是指利用深度神经网络逼近行为值函数 $Q^w\left(s,a\right)$ 和确定性策略 $\mu_{\theta}\left(s\right)$ 。需要修改的就是DPG更新式中的 $w$ 和 $\theta$ ，我们将这里的 $w$ 和 $\theta$ 单独拿出来，利用独立的网络对其进行更新。

DDPG的更新公式为：

$\delta_t=r_t+\gamma Q^{w^-}\left(s_{t+1},\mu_{\theta^-}\left(s_{t+1}\right)\right)-Q^w\left(s_t,a_t\right)\\\\\ \\ w_{t+1}=w_t+\alpha_w\delta_t\nabla_wQ^w\left(s_t,a_t\right) \\ \theta_{t+1}=\theta_t+\alpha_{\theta}\nabla_{\theta}\mu_{\theta}\left(s_t\right)\nabla_aQ^w\left(s_t,a_t\right)|_{a=\mu_{\theta}\left(s\right)} \\ \theta^-=\tau\theta +\left(1-\tau\right)\theta^- \\ w^-=\tau w+\left(1-\tau\right)w^-$

最后，我们给出DDPG的伪代码：

注释

observation ↩︎
state ↩︎
$R=\sum_{t=0}^T{\gamma^t}r_t$ ↩︎ ↩︎
给定策略，通过数值迭代算法不断计算该策略下每个状态的值函数 ↩︎ ↩︎
当已知当前策略的值函数时，在每个状态采用贪婪策略对当前策略进行改进（在某个状态下找最大的动作-状态值函数） ↩︎
Actor-Critic Algorithm. AC算法包括两个同等地位的元素，一个元素是Actor即行动策略，另一个元素是Critic, 即评估，这里是指利用函数逼近方法估计值函数。 ↩︎

强化学习笔记