Reinforcement Learning

Fundamentals

强化学习的核心在于使智能体 (agent) 在复杂的环境中最大化获得的奖励。智能体会与环境交互，通过观察环境的状态，采取行动，获得奖励，不断学习，最终找到最优的策略。交互的轨迹 (trajectory) 是状态、行动 (和奖励) 的序列\(\tau = (s_0, a_0, r_1, s_1, a_1, r_2, s_2, a_2, r_3, \cdots)\)。一次完整的交互，或一场游戏，称为一个回合 (episode) 或一个试验 (trial)。

状态是指环境在特定时刻的信息，有些时候是不能直接观察到的，这个时候我们实际获得的是对状态的观测\(o\)，所以我们说有些环境是部分可观测的 (partially observable)，而有些环境是完全可观测的 (fully observable)，部分可观测不会影响RL问题的马尔可夫性。后文统一成状态-观测概率为\(\Omega(o\vert s)\)或\(\Omega(o\vert s,a)\)，有时也简写为\(\Omega(o)\)。

策略是一个函数，它将状态映射到动作的概率分布\(p(a\vert s)\)，分为确定性策略 (deterministic policy) 和随机性策略 (stochastic policy)。确定性策略就是智能体最有可能采取的动作，一般是贪心策略\(\arg\max_a \pi(a\vert s)\)。

价值函数是对未来奖励的预测，有两种价值函数：状态价值函数\(V(s)\)和动作价值函数\(Q(s,a)\)。状态价值函数是从状态\(s\)开始，按照策略\(\pi\)采取行动，未来获得的奖励的期望值；动作价值函数是从状态\(s\)开始，采取行动\(a\)，然后按照策略\(\pi\)采取行动，未来获得的奖励的期望值，它们的关系实际上可以对应到一棵树的节点和边。

\[\begin{aligned} V_\pi(s) &= \mathbb{E}_\pi[G_t\vert S_t=s] \\ &= \mathbb{E}_\pi[\sum_{k=0}^\infty \gamma^k r_{t+k+1}\vert S_t=s] \\ Q_\pi(s,a) &= \mathbb{E}_\pi[G_t\vert S_t=s, A_t=a] \\ &= \mathbb{E}_\pi[\sum_{k=0}^\infty \gamma^k r_{t+k+1}\vert S_t=s, A_t=a] \\ \end{aligned}\]

这里的下标说明我们将在状态\(s_t\)采取动作\(a_t\)获得的即时奖励定义为\(r_{t+1}\)，\(\gamma\)是折扣因子，用于平衡当前奖励和未来奖励的重要性。

为了完善马尔可夫决策过程，我们再补充两个概念，一个是状态转移概率\(p^a_{ss^\prime}=p(s_{t+1}=s^\prime\vert s_t=s, a_t=a)\)，另一个是奖励函数\(r(s,a)=\mathbb{E}[r_{t+1}\vert s_t=s, a_t=a]\)。这里的奖励函数是说在状态\(s\)采取动作\(a\)获得的即时奖励的期望值，要注意与动作价值函数的区别。

学习状态转移概率来描述环境的强化学习算法称为有模型 (model-based) 算法，而只学习价值函数来进行决策的算法称为无模型 (model-free) 算法，后者在实际应用中更为常见。

Bellman Equation

马尔可夫奖励过程就是马尔可夫链和奖励函数的结合，其核心是贝尔曼方程

\[\begin{aligned} V_\pi(s) &= \mathbb{E}_\pi[G_t\vert S_t=s] \\ &= \mathbb{E}_\pi[R_{t+1} + \gamma G_{t+1}\vert S_t=s] \\ &= \mathbb{E}_\pi[R_{t+1}\vert S_t=s] + \gamma \mathbb{E}_\pi[G_{t+1}\vert S_t=s] \\ &= r_\pi(s) + \gamma \sum_{s^\prime} p_\pi(s^\prime\vert s) V_\pi(s^\prime) \\ \end{aligned}\]

注意连接状态和状态的边是动作，这种分支方式对应到了策略函数\(\pi\)，具体来说

\[\begin{aligned} p_\pi(s^\prime\vert s) &= \sum_{a} \pi(a\vert s) p(s^\prime\vert s, a) \\ r_\pi(s) &= \sum_{a} \pi(a\vert s) r(s, a) \\ \end{aligned}\]

请时刻注意这种基于树的思想¹，我们可以由此继续推导状态价值函数和动作价值函数的关系

\[\begin{aligned} Q_\pi(s,a) &= \mathbb{E}_\pi[G_t\vert S_t=s, A_t=a] \\ &= \mathbb{E}_\pi[R_{t+1} + \gamma G_{t+1}\vert S_t=s, A_t=a] \\ &= \mathbb{E}_\pi[R_{t+1}\vert S_t=s, A_t=a] + \gamma \mathbb{E}_\pi[G_{t+1}\vert S_t=s, A_t=a] \\ &= r_\pi(s,a) + \gamma \sum_{s^\prime} p_\pi(s^\prime\vert s, a) V_\pi(s^\prime) \\ V_\pi(s) &= r_\pi(s) + \gamma \sum_{s^\prime} p_\pi(s^\prime\vert s) V_\pi(s^\prime) \\ &= \sum_{a} \pi(a\vert s) (r_\pi(s,a) + \gamma \sum_{s^\prime} p_\pi(s^\prime\vert s, a) V_\pi(s^\prime)) \\ &= \sum_{a} \pi(a\vert s) Q_\pi(s,a) \\ \end{aligned}\]

此外，我们还可以推动出动作价值函数的贝尔曼方程

\[\begin{aligned} Q_\pi(s,a) &= r_\pi(s,a) + \gamma \sum_{s^\prime} p_\pi(s^\prime\vert s, a) V_\pi(s^\prime) \\ &= r_\pi(s,a) + \gamma \sum_{s^\prime} p_\pi(s^\prime\vert s, a)\sum_{a^\prime} \pi(a^\prime\vert s^\prime) Q_\pi(s^\prime, a^\prime) \\ \end{aligned}\]

Policy Evaluation

策略评估是指给定一个策略\(\pi\)，计算其状态价值函数\(V_\pi\)。我们可以使用动态规划的方法，反复迭代贝尔曼方程，直到收敛。

Policy Iteration

策略迭代是由策略评估和策略改进组成的，策略改进的主要想法是最优的状态价值函数是动作价值函数的最大值，所以我们可以贪心地选择动作，然后再评估这个策略。

\[\begin{aligned} V^{\ast}(s) &= \max_a Q^{\ast}(s,a) \\ &= \max_a\left[r(s,a) + \gamma \sum_{s^\prime} p(s^\prime\vert s, a) V^{\ast}(s^\prime)\right]\\ Q^{\ast}(s,a) &= r(s,a) + \gamma \sum_{s^\prime} p(s^\prime\vert s, a) V^{\ast}(s^\prime) \\ &= r(s,a) + \gamma \sum_{s^\prime} p(s^\prime\vert s, a) \max_{a^\prime} Q^{\ast}(s^\prime, a^\prime) \\ \end{aligned}\]

策略迭代每轮在策略评估和策略改进之间切换，直到策略不再改变。

Value Iteration

价值迭代是指在每一步都选择最优的动作，可以理解为在状态价值函数和动作价值函数之间切换，在迭代结束后显式地计算出最优策略。价值迭代说明，如果值函数是最优的，策略通常也是最优的，也可以说价值迭代是迭代了一次的策略迭代。

Mentor Carlo

蒙特卡洛是基于对回合的评估，它的核心思想是在一个回合结束后，我们可以计算每个状态的回报，然后根据这个回报来更新状态价值函数。

\[V(s_t) \leftarrow V(s_t) + \underbrace{\frac{1}{N(s_t)}}_{\text{learning rate}}(\underbrace{\sum_{k=0}^\infty \gamma^k r_{t+k+1}}_{G_t} - V(s_t))\]

Temporal Difference

时序差分是基于对每一步的评估，更新频率更高，也不要求从完整的回合进行学习，有更高的学习效率。

\[V(s_t) \leftarrow V(s_t) + \alpha(r_{t+1} + \gamma V(s_{t+1}) - V(s_t))\]

时序差分也可以扩展到\(n\)步时序差分，当\(n=\infty\)时就是蒙特卡洛。

Bootstrapping

自举是指更新时使用了自己的估计值，蒙特卡洛更新时完全依赖于采样的回报，而时序差分中\(r_{t+1}\)是采样的部分，\(V(s_{t+1})\)是自举的部分。至于动态规划的方法，则是完全自举，参考策略评估。

Tabular Methods

表格型方法是指状态和动作的数量是有限的，我们可以用表格 (\(Q\in \mathbb{R}^{\vert S\vert\times\vert A\vert}\)) 来存储动作价值函数，并使用无模型方法来更新表格。

\(\epsilon\)-Greedy Policy

\(\epsilon\)-贪心策略是指以\(1-\epsilon\)的概率选择最优动作，以\(\epsilon\)的概率随机选择动作，这种策略可以在探索的同时保证策略的提升

\[\begin{aligned} Q_\pi(s,\pi^\prime(s)) &= \sum_a \pi^\prime(a\vert s) Q_\pi(s,a) \\ &= (1-\epsilon) \max_a Q_\pi(s,a) + \underbrace{\frac{\epsilon}{\vert A\vert} \sum_a Q_\pi(s,a)}_{\text{uniformly exploration}} \\ &\geq \frac{\epsilon}{\vert A\vert} \sum_a Q_\pi(s,a) + (1-\epsilon) \sum_a \frac{\pi(a\vert s)-\frac{\epsilon}{\vert A\vert}}{1-\epsilon}Q_\pi(s,a) \\ &= \sum_a \pi(a\vert s) Q_\pi(s,a) = V_\pi(s) \\ \end{aligned}\]

SARSA

顾名思义，Sarsa算法的更新是基于\((s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})\)的，它将原本更新\(V\)的过程替换为了更新\(Q\)的过程，这样我们就可以直接学习到最优策略。

\[Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha(r_{t+1} + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t))\]

Sarsa是同策略方法，同策略是指用下一步实际执行的动作来优化，即估计和决策一致。

Q-Learning

Q学习是异策略方法，它有两个策略，一个是目标策略，一个是决策策略，决策策略是用来决定下一步动作的，而目标策略是用来在更新时计算最优动作的。

\[Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha(r_{t+1} + \gamma \max_{a} Q(s_{t+1}, a) - Q(s_t, a_t))\]

Policy Gradient

轨迹\(\tau\)发生的概率是

\[p_\theta(\tau) = p(s_0)\prod_{t=0}^{T-1} p(s_{t+1}\vert s_t, a_t) \pi_\theta(a_t\vert s_t)\]

如果我们用轨迹的概率对总奖励求期望，就是策略的期望奖励

\[\bar{R}_\theta = \mathbb{E}_{\tau\sim p_\theta(\tau)}[R(\tau)] = \sum_\tau p_\theta(\tau) R(\tau)\]

我们的目标是最大化这个期望奖励，这个奖励是关于策略参数\(\theta\)的函数，所以我们对这个函数求梯度，用以更新策略参数

\[\nabla_\theta \bar{R}_\theta = \sum_\tau R(\tau) \nabla_\theta p_\theta(\tau)\]

由\(\nabla \log p(x) = \frac{1}{p(x)}\nabla p(x)\)，我们可以得到\(\nabla_\theta p_\theta(\tau) = p_\theta(\tau) \nabla_\theta \log p_\theta(\tau)\)，所以

\[\begin{aligned} \nabla_\theta \bar{R}_\theta &= \sum_\tau R(\tau) p_\theta(\tau) \nabla_\theta \log p_\theta(\tau) \\ &= \sum_\tau R(\tau) p_\theta(\tau) \nabla_\theta \sum_{t}\log\pi_\theta(a_t\vert s_t) \\ \end{aligned}\]

这个梯度是关于轨迹的，而轨迹中转态转移是与参数无关的，所以最后的轨迹策略梯度是概率为\(p_\theta(\tau)\)的\(R(\tau)\nabla_\theta \sum_{t}\log\pi_\theta(a_t\vert s_t)\)的期望，在实际应用中可以用采样估计这个期望

\[\nabla_\theta \bar{R}_\theta \approx \frac{1}{N}\sum_{i=1}^N R(\tau_i) \nabla_\theta \sum_{t}\log\pi_\theta(a^i_t\vert s^i_t)\]

Advantage Function

优势函数是指一个状态动作对的价值函数和基准价值函数的差值，这个差值可以用来衡量一个动作相对于基准动作的优势。受此启发，我们可以用优势函数对策略梯度重新加权

\[\nabla_\theta \bar{R}_\theta \approx \frac{1}{N}\sum_{i=1}^N \left[R(\tau_i) - b\right] \nabla_\theta \sum_{t}\log\pi_\theta(a^i_t\vert s^i_t)\]

另外还有一个计算权重的技巧是只计算时间步\(t\)之后的奖励，直观上理解就是一个动作的奖励应该是它之后的奖励，与之前的奖励无关

\[\nabla_\theta \bar{R}_\theta \approx \frac{1}{N}\sum_{i=1}^N \sum_{t=0}^{T-1} \left[\sum_{k=t}^{T-1}\gamma^{k-t}r^i_{k+1} - b\right] \nabla_\theta \log\pi_\theta(a^i_t\vert s^i_t)\]

REINFORCE

经典的REINFORCE算法就是一个策略梯度的例子，它的权重是去掉基线的时间\(t\)之后的累计奖励

\[\nabla_\theta \bar{R}_\theta \approx \frac{1}{N}\sum_{i=1}^N \sum_{t=0}^{T-1} \left[\sum_{k=t}^{T-1}\gamma^{k-t}r^i_{k+1}\right] \nabla_\theta \log\pi_\theta(a^i_t\vert s^i_t)\]

计算REINFORCE的回合奖励时需要完整的回合数据\(\left\{(s_t, a_t, G_t)\right\}\)，\(G_t\)的计算可以根据\(G_t = r_{t+1} + \gamma G_{t+1}\)进行递推。

Importance Sampling

对于策略梯度方法，每次我们更新完梯度后，策略就会发生变化，这样我们就无法再用之前的数据来估计梯度，这就是策略漂移。为了解决这个问题，我们可以使用重要性采样，即用新策略的概率除以旧策略的概率来加权，这样就可以保证期望不变。

重要性采样是指，我们想要从一个分布\(p(x)\)中采样\(x\)，但是\(p\)不可获取，我们只能从另一个分布\(q(x)\)中采样，

\[\begin{aligned} \mathbb{E}_{x\sim p(x)}[f(x)] &= \int p(x)f(x)dx \\ &= \int q(x)\frac{p(x)}{q(x)}f(x)dx \\ &= \mathbb{E}_{x\sim q(x)}\left[\frac{p(x)}{q(x)}f(x)\right] \\ \end{aligned}\]

其中\(\frac{p(x)}{q(x)}\)就是重要性采样的权重，每采样一个样本，我们就可以用这个权重来调整期望。但这不是完美的，因为我们虽然能保证期望一致，但方差却不一定

\[\begin{aligned} Var_{x\sim p(x)}[f(x)] &= \mathbb{E}_{x\sim p(x)}[f(x)^2] - \mathbb{E}_{x\sim p(x)}[f(x)]^2 \\ Var_{x\sim q(x)}[\frac{p(x)}{q(x)}f(x)] &= \mathbb{E}_{x\sim q(x)}[(\frac{p(x)}{q(x)}f(x))^2] - \mathbb{E}_{x\sim q(x)}[\frac{p(x)}{q(x)}f(x)]^2 \\ &= \int q(x)\frac{p^2(x)}{q^2(x)}f^2(x)dx - \left(\int q(x)\frac{p(x)}{q(x)}f(x)dx\right)^2 \\ &= \int p(x)\frac{p(x)}{q(x)}f^2(x)dx - \left(\int p(x)f(x)dx\right)^2 \\ &= \textcolor{blue}{\mathbb{E}_{x\sim p(x)}[\frac{p(x)}{q(x)}f^2(x)]} - \mathbb{E}_{x\sim p(x)}[f(x)]^2 \\ \end{aligned}\]

可以看出方差的差异是由于\(p\)和\(q\)的分布不一致导致的。有了重要性采样，我们就可以把同策略问题变换为异策略问题，即采用一个示范策略\(\pi^\prime\)去与环境交互，对应重要性采样中的\(q\)，而我们要训练的策略是\(\pi\)，对应重要性采样中的\(p\)。这样我们可以重写重要性采样的策略梯度

\[\begin{aligned} \nabla_\theta \bar{R}_\theta &= \mathbb{E}_{\tau\sim p_{\theta^\prime}(\tau)}\left[\frac{p_\theta(\tau)}{p_{\theta^\prime}(\tau)}R(\tau)\nabla_\theta \log p_\theta(\tau)\right] \\ \end{aligned}\]

实际在做策略梯度的时候，我们可以不学习完整轨迹，也可以只学习一个时间步，这样就好像是在对状态动作对进行采样，前提是我们要有对应的优势函数\(A^\theta(s_t, a_t)\)，这样我们就可以重写重要性采样的策略梯度

\[\begin{aligned} &\mathbb{E}_{(s_t, a_t)\sim \pi_{\theta^\prime}}\left[\frac{p_\theta(s_t, a_t)}{p_{\theta^\prime}(s_t, a_t)}A^\theta(s_t, a_t)\nabla_\theta \log p_\theta(a_t\vert s_t)\right] \\ =& \mathbb{E}_{(s_t, a_t)\sim \pi_{\theta^\prime}}\left[\frac{p_\theta(a_t\vert s_t)p_\theta(s_t)}{p_{\theta^\prime}(a_t\vert s_t)p_{\theta^\prime}(s_t)}A^\theta(s_t, a_t)\nabla_\theta \log p_\theta(a_t\vert s_t)\right] \\ \approx& \mathbb{E}_{(s_t, a_t)\sim \pi_{\theta^\prime}}\left[\frac{p_\theta(a_t\vert s_t)}{p_{\theta^\prime}(a_t\vert s_t)}A^\theta(s_t, a_t)\nabla_\theta \log p_\theta(a_t\vert s_t)\right] \\ =& \mathbb{E}_{(s_t, a_t)\sim \pi_{\theta^\prime}}\left[\frac{p_\theta(a_t\vert s_t)\nabla_\theta \log p_\theta(a_t\vert s_t)}{p_{\theta^\prime}(a_t\vert s_t)}A^\theta(s_t, a_t)\right] \\ =& \mathbb{E}_{(s_t, a_t)\sim \pi_{\theta^\prime}}\left[\frac{\nabla_\theta p_\theta(a_t\vert s_t)}{p_{\theta^\prime}(a_t\vert s_t)}A^\theta(s_t, a_t)\right] \\ \end{aligned}\]

根据上式，我们把梯度去掉，还原目标函数，那么重要性采样的策略梯度方法的优化目标函数就是

\[\mathbb{E}_{(s_t, a_t)\sim \pi_{\theta^\prime}}\left[\frac{p_\theta(a_t\vert s_t)}{p_{\theta^\prime}(a_t\vert s_t)}A^{\theta^\prime}(s_t, a_t)\right] \\\]

TRPO

TRPO是Trust Region Policy Optimization的缩写，它的核心思想是在更新策略时，我们要保证策略的更新是在一个可信区域内，这样可以保证策略的稳定性，所谓可信区域就是用KL散度约束

\[J^{\theta^\prime}_{\text{TRPO}}(\theta) = \mathbb{E}_{(s_t, a_t)\sim \pi_{\theta^\prime}}\left[\frac{p_\theta(a_t\vert s_t)}{p_{\theta^\prime}(a_t\vert s_t)}A^{\theta^\prime}(s_t, a_t)\right],\; \text{KL}(\theta, \theta^\prime) \leq \delta\]

PPO

PPO是Proximal Policy Optimization的缩写，它把TRPO的约束条件囊括到了目标函数中，便于优化

\[J^{\theta^\prime}_{\text{PPO}}(\theta) = \mathbb{E}_{(s_t, a_t)\sim \pi_{\theta^\prime}}\left[\frac{p_\theta(a_t\vert s_t)}{p_{\theta^\prime}(a_t\vert s_t)}A^{\theta^\prime}(s_t, a_t)\right] - \beta \text{KL}(\theta, \theta^\prime)\]

PPO2是PPO的一种变体，它把KL散度约束条件去掉，只保留了一个重要性采样的边界

\[J^{\theta^\prime}_{\text{PPO2}}(\theta) \approx \sum_{(s_t, a_t)}\min\left(\frac{p_\theta(a_t\vert s_t)}{p_{\theta^\prime}(a_t\vert s_t)}A^{\theta^\prime}(s_t, a_t), \text{clip}\left(\frac{p_\theta(a_t\vert s_t)}{p_{\theta^\prime}(a_t\vert s_t)}, 1-\epsilon, 1+\epsilon\right)A^{\theta^\prime}(s_t, a_t)\right)\]

Deep Q Network

Actor-Critic

演员评论家是一种结合了策略梯度和动作价值函数的方法，演员是策略网络，评论家是价值网络，演员用来决策，评论家用来评估。有的评论家是基于优势函数的，同时学习状态价值和动作价值，然后用动作价值减去状态价值得到优势函数。