贝尔曼方程的艺术。
引子
我在科研生涯的第一篇工作就已经接触过RL了，当时的需求是：从文本和图片中分别提取出三元组，通过一种训练方法让这两组三元组之间的相似度尽可能高。选择RL的原因也很简单——提取三元组是没办法进行反向传播的，所以，就用不了SFT，只能用RL。
在最近的工作中，也遇到了一些需要RL的情况，苦于理论知识不充足，吃了很多苦头，这篇文章就记录一下对于常有的RL算法的学习。
强化学习是这样一种学习方法，它要求模型基于环境做一些行为，然后根据行为进行奖励或惩罚。
马尔可夫决策过程
马尔可夫性
马尔可夫性是这样的一种性质，下一时间步的取值分布完全由当前时间步的取值决定：
$$
\rm{P}(S_{t+1}|S_t) = \rm{P}(S_{t+1}|S_1, S_2,\cdots, S_t)
$$
比如说有穷自动机（DFA），下一时刻的取值完全由当前状态决定，和过去的状态没有关系，这便是马尔可夫性质的一个示例。
马尔可夫决策过程
马尔可夫决策过程就是在马尔可夫过程（有穷自动机）上加上了状态转移的奖励。
假设我们的目标是教会一个智能体在一个2D迷宫中找出口，那么，在每一时刻，智能体的下一步行动有四种取值：前后左右。对于每一个状态我们可以将奖励设置为：与终点距离的倒数。
到这里还不够。我们需要设置一个优化目标。很显然的是，我们的目标是让最后的奖励值最大：
$$
G = \rm\sum_{i=0}^n Reward(A_i)
$$
通常情况下，我们会对不同时间步的奖励做一个系数，这样避免出现循环行为（左右移动交替）：
$$
G = \rm\sum_{i=0}^n \gamma^i Reward(A_i)
$$
这个$\gamma$是一个在0~1范围内的系数，这个值越偏向于0，就越看重短时间内的奖励，越偏向于1，就更在意长期奖励。
贝尔曼方程
贝尔曼方程的含义是，「今日之价值，为今日之收获，与明日之价值」：
$$
\rm V(s_t) = Reward(S_t)+\gamma E(V_{t+1}|S_t=s_t)
$$
也就是当前状态获得到的奖励，和下一时间步价值期望之和。
这是怎么来的？我们知道，一个时间步的价值，就是这个时间步到最终，所能获取到的奖励总和：
$$
\rm V(s_t)=E(G_t|S_t=s_t)
$$
其中：
$$
\rm G_t=\sum_{i=t}^n\gamma^{i-t} Reward(s_i)
$$
这里，我们将行动的奖励，也在一定程度上看作是状态的奖励，那么：
$$
\rm V(s_t)=E(Reward(s_t)+\gamma G_{t+1}|S_t=s_t)=Reward(s_t)+\gamma E(G_{t+1}|S_t=s_t)
$$
对于$\rm E(G_{t+1}|S_t)$而言，根据双重期望定理：
$$
\rm E(G_{t+1}|S_t=s_t) = E(E(G_{t+1}|S_t=s_t,S_{t+1}=s_{t+1}))=\sum_{s_{t+1}}E(G_{t+1}|S_{t+1}=s_{t+1})P(s_{t+1}|s_{t})
$$
这个式子也就是：
$$
\rm E(G_{t+1}|S_t=s_t) = \sum_{s_{t+1}}V(s_{t+1})P(s_{t+1}|s_{t})=E(V_{t+1}|S_t=s_t)
$$
到这里还不够，因为我们在这个过程中还没有明确行为带来的影响，如果将行动也引入进来那么：
$$
\rm V(s_t) =Reward(s_t)+\gamma E(G_{t+1}|S_t=s_t, A_t=a_t)
$$
那么，依旧按照双重期望定理进行推理，最终可以得到这样一个式子：
$$
\rm V(s_t) =Reward(s_t)+\gamma \sum_{s_{t+1}}[V(s_{t+1})\sum_{a_t}P(s_{t+1}| s_t,a_t)\pi(a_t|s_t)]
$$
其中，$\rm \pi(a_t|s_t)$是在当前策略下，状态$\rm s_t$下选取行动$a_t$的概率，而这，就是我们要优化的目标。
最后这个式子，感性认知就是，「今日之价值，为今日之收获，与不同行动下，明日之价值」。
Q-Learning
通过贝尔曼方程，我们知道，我们优化的目标，就是优化在不同状态下，做不同行动的概率。当然，这个最优策略我们是不知道的，也很难求解，我们需要一些方法来学习到这个策略。
我们可以通过不断试错进行学习，这便是Q- Learning的基本思想——「不断试错，尝试拟合到最优策略」。
Q-Learning的流程是这样的：
- 初始化一个Q表，用于记录在不同状态下，进行不同行为的奖励。
- 每一step如下运算：
- 根据当前的状态$s$，通过一定的规则，选择一个行为$a$。
- 执行行为$a$，每个行为都有一个奖励$r$，也达到了一个新的状态$s’$。
- 更新$Q(s,a)$为$Q(s,a) + \alpha [r+\gamma \max_{a’} Q(s’,a’) - Q(s,a)]$。
这里，更新的函数我们需要注意一下，尤其是它的增量，其中$\alpha$是一个系数，控制更新的步长，可以理解为学习率，$\max_{a’} Q(s’,a’)$就是$s’$状态下，取不同行动，理论上能获得的最高奖励，当然，奖励是不断累积的，我们更关注的是「相比于原来的奖励提升了多少」，所以需要减去一个$Q(s,a)$。
将最后这个增量，$\alpha$看作学习率，剩下的部分看作loss，就可以应用深度学习的方法进行优化，这便是DQN的基本思想。
TRPO
Q-Learning的思想就是，我有一套旧的策略，我可以在旧策略的每一步进行优化，用它来学出更好的策略，而TRPO则不同——「我想让策略变得更好，所以我需要根据环境进行交互」。
TRPO的数学推导极其巧妙，我在这里只写下一个粗浅的过程，遮盖了很多细节。
TRPO关注于起始状态的收获，也就是说，它的优化目标是：
$$
\rm J(\pi) = V^\pi(s_0) = E(G_t|S_0=s_0)
$$
为了优化这个目标，我们需要聚焦于新旧策略之间的差值：
$$
\rm J(\pi_{new})-J(\pi_{old})
$$
这个差值为正，就算做提升。
回顾贝尔曼方程：
$$
\rm V^\pi(s)=\sum_{a}\pi(a|s)Q^\pi(s,a)
$$
那么我们可以定义这样一个优势函数，就是指某一状态，采取某一行动，能够产生多大的差值：
$$
\rm A^{\pi}(s,a)=Q^\pi(s,a)-V(s)
$$
回看我们的「新旧策略之间的差值」，这个式子可以变成：
$$
\rm J(\pi_{new}) = J(\pi_{old}) + \sum E_{s_t,a_t\sim\pi_{new}}[\rho_{\pi_{new}}(s_t)A^{\pi_{old}}(s_t,a_t)]
$$
其中：
$$
\rm \rho_{\pi_{new}}(s) = \sum_{i=o}\gamma^i P(s_i = s)
$$
但是，我们压根不知道新策略是怎么样啊，这里TRPO的作者做了一个非常大胆的近似——假设新策略和旧策略非常接近，那么它们的状态占有率$\rho$几乎是一样的。所以，目标函数变成了：
$$
\rm J(\pi_{old}) +E_{s_t,a_t\sim\pi_{new}}[\sum_{t=0}\gamma^t \frac{\pi_{new}(a_t|s_t)}{\pi_{old}(a_t|s_t)}A^{\pi_{old}}(s_t,a_t)]
$$
这里，$\pi_{new}$是一个临时的，在当前参数点周围的一个状态，因为我们对新状态一无所知，所以只能用周边的一个点进行近似。我们该怎么确定这个点离我们多远？加约束。这个约束就是让新旧策略之间的KL散度值小于某一个阈值即可：
$$
\rm KL(\pi_{old}||\pi_{new}) < \delta
$$
这里，$\pi_{new}$也可以叫做$\pi_{\theta}$。
PPO
PPO是对TRPO的改进，因为——计算TRPO的约束实在是太麻烦了。
TRPO的优化任务是：
$$
\rm L^{TRPO}(\theta)=E_{s,a\sim \pi_{old}}(r(\theta)\cdot A)\ \ s.t.\ \ \rm KL(\pi_{old}||\pi_{\theta}) < \delta
$$
而PPO的优化任务是：
$$
\rm L^{PPO}(\theta) =E_{s,a\sim \pi_{old}}(\min (r(\theta)\cdot A, clip(r(\theta), 1-\epsilon, 1+\epsilon)\cdot A))
$$
其中，$r(\theta)$就是$\frac{\pi_{new}(a_t|s_t)}{\pi_{old}(a_t|s_t)}$。
其中，clip函数的意思是，如果$r(\theta)$在$1-\epsilon$和$1+\epsilon$之间，就保持不变，如果太大，就变成$1+\epsilon$，如果太小就是$1-\epsilon$。
PPO函数相当于对TRPO函数的KL散度运算进行了优化，规避了KL散度的复杂运算。