Markov Decision Process (MDP)
1. 马尔可夫过程
通常用元组 \(⟨S,P⟩\) 描述一个马尔可夫过程，其中 \(S\) 为有限数量的状态集合，\(P\) 是状态转移矩阵：
\[ P = \begin{bmatrix} P(s_1|s_1) & \cdots & P(s_n|s_1) \\ \vdots & \ddots & \vdots \\ P(s_1|s_n) & \cdots & P(s_n|s_n) \end{bmatrix} \]
对于状态转移矩阵，每一行的和都是 1。直观地理解，每个状态一定会到下一个状态，那么把所有可能到达的状态的概率求和，就为 1。 ### 2. 马尔可夫奖励过程
在马尔可夫过程中加入奖励函数 \(r\) 和折扣因子 \(\gamma\)，就可以得到马尔可夫奖励过程（Markov Reward Process）。一个马尔可夫奖励过程由 \((S, P, r, \gamma)\) 构成，各个组成元素的含义如下：
- \(S\) 是有限状态的集合。
- \(P\) 是状态转移矩阵。
- \(r\) 是奖励函数，某个状态 \(s\) 的奖励 \(r(s)\) 指转移到该状态时可以获得奖励的期望。
- \(\gamma\) 是折扣因子（discount factor），\(\gamma\) 的取值范围为 [0, 1)。引入折扣因子的理由为远期利益具有一定不确定性，有时我们更希望能够尽快获得一些奖励，所以我们需要对远期利益打一些折扣。接近 1 的 \(\gamma\) 更关注长期的累计奖励，接近 0 的 \(\gamma\) 更考虑短期奖励。
2.1 回报
\[ G_t = R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots = \sum_{k=0}^\infty \gamma^k R_{t+k} \]
其中，\(R_t\) 表示在时刻 \(t\) 获得的奖励。
2.2 价值函数
一个状态的期望回报（即从这个状态出发的未来累积奖励的期望）被称为这个状态的价值（value），价值函数的定义 \(V(s) = \mathbb{E}[G_t \mid S_t = s]\)，展开为：
\[ V(s) = \mathbb{E}[G_t \mid S_t = s] = \mathbb{E}[R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots \mid S_t = s] = \mathbb{E}[R_t + \gamma G_{t+1} \mid S_t = s] = \mathbb{E}[R_t \mid S_t = s] + \gamma \mathbb{E}[G_{t+1} \mid S_t = s] = r(s) + \gamma \mathbb{E}[V(S_{t+1}) \mid S_t = s] \]
\(\mathbb{E}[R_t \mid S_t = s] = r(s)\)；另一方面，等式中剩余部分 \(\mathbb{E}[\gamma V(S_{t+1}) \mid S_t = s]\) 可以根据从状态 \(s\) 出发的转移概率得到，即可以得到：
\[ V(s) = r(s) + \gamma \sum_{s' \in S} p(s' \mid s)V(s') \]
上面就是贝尔曼方程（Bellman Equation）。将贝尔曼方程写成矩阵的形式：
\[ \mathbf{V} = \mathbf{R} + \gamma \mathbf{P} \mathbf{V} \]
\[ \begin{bmatrix} V(s_1) \\ V(s_2) \\ \vdots \\ V(s_n) \end{bmatrix} = \begin{bmatrix} r(s_1) \\ r(s_2) \\ \vdots \\ r(s_n) \end{bmatrix} + \gamma \begin{bmatrix} p(s_1 \mid s_1) & \cdots & p(s_n \mid s_1) \\ p(s_1 \mid s_2) & \cdots & p(s_n \mid s_2) \\ \vdots & \ddots & \vdots \\ p(s_1 \mid s_n) & \cdots & p(s_n \mid s_n) \end{bmatrix} \begin{bmatrix} V(s_1) \\ V(s_2) \\ \vdots \\ V(s_n) \end{bmatrix} \]
我们可以直接根据矩阵运算求解，得到以下解析解：
\[ \mathbf{V} = (\mathbf{I} - \gamma \mathbf{P})^{-1} \mathbf{R} \]
3. 马尔可夫决策过程
上面的过程都是自发的，对于 MP 过程是基于概率自发的，对于 MRP 过程基于概率和累积奖励自发，对于马尔可夫决策过程（Markov Decision Process, MDP），他接受来自外界的刺激，称作智能体的动作。与 MRP 的过程十分相似，只是多了一个动作的变量，具体而言，由 \(⟨S,A,P,r,\lambda⟩\) 构成：
- \(S\) 是状态的集合
- \(A\) 是动作的集合
- \(\lambda\) 是折扣因子
- \(r(s,a)\) 是奖励函数
- \(P(s' \mid s,a)\) 是状态转移函数，表示在 \(s\) 状态执行动作 \(a\) 之后到达状态 \(s'\) 的概率
3.1 策略
智能体的策略 (Policy) 通常使用 \(\pi\) 来表示。\(\pi(a \mid s)=P(A_t=a \mid S_t=s)\) 是一个函数，表示在输入状态 \(s\) 情况下采取动作 \(a\) 的概率。分为确定性策略（对于一个状态之后只会执行一个特定的动作）和随机性策略（对于一个状态会得到的是一个概率分布）。
3.2 状态价值函数
\(V^{\pi}(s)=E_{\pi}[G_t \mid S_t=s]\) 定义为从状态 \(s\) 出发，按照策略 \(\pi\) 能获得的期望回报。
3.3 动作价值函数
\(Q^{\pi}(s,a)=E_{\pi}[G_t \mid S_t=s, A_t=a]\) 表示在 MDP 遵循策略 \(\pi\) 的时候，对于当前动作 \(s\) 执行动作 \(a\) 得到的期望回报。
由全概率公式可以得到：
\[ V^{\pi}(s)=\sum_{a\in A}\pi(a \mid s)Q^{\pi}(s,a) \]
类似于 MRP，可以得到下面的公式：
\[ Q^{\pi}(s,a)=E_{\pi}[R_t+\lambda Q^{\pi}(S_{t+1},A_{t+1}) \mid S_t=s,A_t=a] \]
\[ =r(s,a)+\lambda \sum_{s'\in S}(p(s' \mid s,a)\sum_{a'\in A}\pi(a' \mid s')Q^{\pi}(s',a')) \]
3.4 贝尔曼期望方程
\[ V^{\pi}(s)=E_{\pi}[G_t \mid S_t=s]=\sum_{a\in A}\left(\pi(a \mid s)\left(r(s,a)+\lambda\sum_{s'}p(s' \mid s,a)V^{\pi}(s')\right)\right) \]
\[ Q^{\pi}(s,a)=r(s,a)+\lambda \sum_{s'\in S}\left(p(s' \mid s,a)\sum_{a'\in A}\pi(a' \mid s')Q^{\pi}(s',a')\right) \]
3.5 占用度量
首先，我们定义 MDP 的初始状态分布 \(V_0(s)\)，用 \(P_t^{\pi}\) 表示采取策略 \(\pi\) 使得智能体在 \(t\) 时刻状态为 \(s\) 的概率，我们可以定义一个状态访问分布（它描述了在整个时间过程中，智能体有多大概率访问到某个特定状态）：
\[ v^{\pi}(s)=(1-\lambda)\sum_{t=0}^{\infty}\lambda^{t}P_t^{\pi}(s) \]
此外，我们还可以定义策略的占用度量（occupancy measure）：
\[ \rho^\pi(s, a) = (1 - \gamma) \sum_{t=0}^{\infty} \gamma^t P_t^\pi(s) \pi(a \mid s) \]
它表示动作状态对 \((s, a)\) 被访问到的概率。二者之间存在如下关系：
\[ \rho^\pi(s, a) = v^\pi(s) \pi(a \mid s) \]
进一步得出如下两个定理。定理 1：智能体分别以策略 \(\pi_1\) 和 \(\pi_2\) 和同一个 MDP 交互得到的占用度量 \(\rho^{\pi_1}\) 和 \(\rho^{\pi_2}\) 满足：
\[ \rho^{\pi_1} = \rho^{\pi_2} \iff \pi_1 = \pi_2 \]
定理 2：给定一个合法占用度量 \(\rho\)，可生成该占用度量的唯一策略是：
\[ \pi_\rho = \frac{\rho(s, a)}{\sum_{a'} \rho(s, a')} \]
3.6 最优策略
强化学习的目标通常是找到一个策略，使得智能体从初始状态出发能获得最多的期望回报。我们首先定义策略之间的偏序关系：当且仅当对于任意的状态 \(s\) 都有 \(V^{\pi'}(s) \ge V^\pi(s)\) 时，记 \(\pi' \succeq \pi\)。于是存在有限状态和动作集合的 MDP 中，至少存在一个策略比其他所有策略都好或者至少不差于其他所有策略，这个策略就是最优策略（optimal policy）。最优策略可能有很多个，我们都将其表示为 \(\pi^*\)。
最优策略都有相同的状态价值函数，我们称之为最优状态价值函数，表示为：
\[ V^*(s) = \max_\pi V^\pi(s), \quad \forall s \in S \]
同理，我们定义最优动作价值函数为：
\[ Q^*(s, a) = \max_\pi Q^\pi(s, a), \quad \forall s \in S, a \in A \]
为了使 \(Q^\pi(s, a)\) 最大，我们需要在当前的状态动作对 \((s, a)\) 之后都执行最优策略。于是我们得到了最优状态价值函数和最优动作价值函数之间的关系：
\[ Q^*(s, a) = r(s, a) + \gamma \sum_{s' \in S} P(s' \mid s, a) V^*(s') \]
这与在普通策略下的状态价值函数和动作价值函数之间的关系是一样的。另一方面，最优状态价值是选择使得最优动作价值最大的那个动作时的状态价值：
\[ V^*(s) = \max_{a \in A} Q^*(s, a) \]
3.7 贝尔曼最优方程
根据 \(V^*(s)\) 和 \(Q^*(s, a)\) 的关系，我们可以得到贝尔曼最优方程（Bellman Optimality Equation）：
\[ V^*(s) = \max_{a \in A} \{ r(s, a) + \gamma \sum_{s' \in S} p(s' \mid s, a) V^*(s') \} \]
\[ Q^*(s, a) = r(s, a) + \gamma \sum_{s' \in S} P(s' \mid s, a) \max_{a' \in A} Q^*(s', a') \]
动态规划算法
1. 策略迭代算法
1.1 策略评估
随机选定\(V^0\),在贝尔曼期望期望方程上迭代： \[ V^{k+1}(s)=\sum_{a\in A}\pi(a|s)\left(r(s|a)+\gamma\sum_{s'\in S}P(s'|s,a)V^k(s') \right) \] （数学原理可以保证这个的成立）
1.2 策略提升
使用完全贪心的策略,直接贪心的在每个状态选择动作价值最大的那个动作 \[ \pi'(s)=arg max_aQ^{\pi}(s,a) \]
1.3 策略迭代算法
对当前的策略进行策略评估，得到其状态价值函数，然后根据该状态价值函数进行策略提升以得到一个更好的新策略，接着继续评估新策略、提升策略……直至最后收敛到最优策略
1.4 价值迭代算法
在贝尔曼最优方程上进行迭代 \[ V^{k+1}(s)=max_{a\in A}\{r(s|a)+\gamma\sum_{s'\in S}P(s'|s,a)V^k(s')\} \]
时序差分算法
无模型的强化学习：对于大部分的强化学习现实场景，环境的奖励函数和状态转移函数是未知的，因此智能体只能通过和环境进行交互，通过采样到的数据进行学习
1. 时序差分方法
1.1增量更新：
\[ \begin{aligned} Q_k &= \frac{1}{k} \sum_{i=1}^k r_i \\ &= \frac{1}{k} \left( r_k + \sum_{i=1}^{k-1} r_i \right) \\ &= \frac{1}{k} \left( r_k + (k-1)Q_{k-1} \right) \\ &= \frac{1}{k} \left( r_k + kQ_{k-1} - Q_{k-1} \right) \\ &= Q_{k-1} + \frac{1}{k} \left[ r_k - Q_{k-1} \right] \end{aligned} \]
把\(Q_k\)是一种平均值，假设我们的\(r_i\)是逐渐得到的，如果我们等到得到最后一个r的时候再去计算平均值就比较慢，因此，我们可以按照时序顺序来计算，用之前的平均值，加上当前的值与平均值的差距，再乘以一个小因子，相当于每次都给之前的平均值做一个调整。
1.2 公式
\[ V(s_t)\leftarrow V(s_t)+\alpha[r_t+\gamma V(s_{t+1}-V(s_t)] \]
2. Sarsa算法
策略评估已经可以通过时序差分算法实现了，类似的我们可以使用时序差分算法去估计动作价值函数Q: \[ Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha[r_t+Q(s_{t+1},a_{t+1})-Q(s_t,a_t)] \] 如果一直进行完全贪婪选择的话，可能会导致某些状态动作\((s,a)\)永远没有在序列中出现，导致无法对其动作价值进行估计，因此我们采用\(\epsilon\)贪婪策略
3. Q-learning算法
Q-learning基于Bellman方程进行更新。
\[ Q(s, a) \leftarrow Q(s, a) + \alpha \left( r + \gamma \cdot \max_{a'} Q(s', a') - Q(s, a) \right) \]
- \(\max_{a'} Q(s', a')\)：在下一个状态 ( s' ) 下，所有可能动作中Q值最大的动作对应的Q值。
DQN算法
DQN
参考公式30，我们的目标是使\(Q(s,a)\)和TD的目标\(r+\gamma max_{a' \in A}Q(s',a')\)靠近，于是 \[ w^*=arg min_{w}\frac{1}{2N}\sum^N_{i=1}\left[Q_w(s_i,a_i)-\left( r + \gamma \cdot \max_{a'} Q(s', a') - Q(s, a) \right)\right] \]
经验回放
当前状态和上一个状态紧密相关，如果直接使用连续的样本进行训练，数据之间会高度相关，无法满足神经网络训练所需的独立同分布假设，通过经验回放（在训练神经网络的时候不使用agent最近收集的数据，而是从buffer中随机采样若干数据进行训练）打破样本之间的相关性，减少对神经网络训练的负面影响。
目标网络
将损失函数分为两个部分，一个后半部分每次都更新，一个固定住
Double DQN
传统的DQN容易造成过高的估计，于是改写为 \[ r+\gamma Q_{w^-}\left(s',arg max_{a'}Q_w(s',a')\right) \] 其中目标网络的参数记做\(w^-\),训练网络的参数记做\(w\)
Dueling DQN
在 Dueling DQN 中，Q 网络被建模为： \[
Q_{\eta,\alpha,\beta}(s,a)=V_{\eta,\alpha}(s)+A_{\eta,\beta}(s,a)
\] 
分别建模的好处：某些情境下智能体只会关注状态的价值，而并不关心不同动作导致的差异，此时将二者分开建模能够使智能体更好地处理与动作关联较小的状态。
对于这样的Q值的计算，同一个Q值可能对应不同的V，A，因此Dueling DQN 强制最优动作的优势函数的实际输出为 0： \[ Q_{\eta,\alpha,\beta}(s,a)=V_{\eta,\alpha}(s)+A_{\eta,\beta}(s,a)-max_{a'}A_{\eta,\beta}(s,a') \] 也可以使用平均代替最大化操作： \[ Q_{\eta,\alpha,\beta}(s,a)=V_{\eta,\alpha}(s)+A_{\eta,\beta}(s,a)-\frac{1}{|A|}\sum_{a'}A_{\eta,\beta}(s,a') \] 其中\(｜A｜\)表示动作空间中所有可能的动作数量。
策略梯度算法
基于策略的方法则是直接显式的学习一个目标策略
策略梯度
基于策略的方法首先需要将策略参数化。假设目标策略\(\pi_{\theta}\)是一个随机性策略，并且处处可微，将策略学习的目标函数定义为\(J(\theta)=E_{s_0}[V^{\pi_{\theta}}(s_0)]\)，对其求导，然后使用梯队上升方法来最大化这个目标函数。 \[ \nabla_{\theta} J(\theta)=E_{\pi_{\theta}}[Q^{\pi_{\theta}}(s,a)\nabla_{\theta}\ log\ \pi_{\theta}(a|s)] \] 直观的理解就是增大能够得到较高Q值的动作的概率，减少较低Q值的动作的概率
Reinforce算法：有限步数环境下采样轨迹计算相应的价值，利用蒙特卡洛采样 \[ \nabla_{\theta} J(\theta)=E_{\pi_{\theta}}\left[\sum^T_{t=0}\left(\sum^T_{t'=t}\gamma^{t'-t}r_{t'}\right)\nabla_{\theta}\ log\ \pi_{\theta}(a|s)\right] \] 使用当前策略采样，计算当前轨迹每个时刻t往后的回报，记作\(\psi_t\),然后梯度上升 \[ \theta \leftarrow \theta+\alpha\sum_{t}^T\psi_t\nabla_{\theta}\ log\ \pi_{\theta}(a|s) \]
Actor-Critic算法
优化一个带参数的策略，并且额外学习价值函数，帮助策略函数更好的学习
Actor学习策略 \[ \theta \leftarrow \theta+\alpha\sum_{t}^T\psi_t\nabla_{\theta}\ log\ \pi_{\theta}(a|s) \] 其中\(\psi_t\)有多种
Critic学习价值函数，类似DQN，定义损失函数如下 \[ L(w)=\frac{1}{2}(r+\gamma V_{w}(s_{t+1})-V_w(s_t))^2 \]
梯度
\[
\nabla_w L(w)=-(r+\gamma V_{w}(s_{t+1})-V_w(s_t))\nabla_w V_w(s_t)
\]
TRPO算法
策略优化算法通过直接优化策略来找到最优策略，通常使用梯度下降的方法，然而有时会导致策略更新过大，从而使得新策略的性能不稳定甚至变差。因此需要保证新策略不会偏离当前策略太远，进而使得每次更新后策略的性能稳定提升。
定义新旧策略的目标函数的差距： \[ \begin{align} J(\theta')-J(\theta)&=E_{\pi_{\theta'}}\left[\sum^{\infty}_{t=0}\gamma^t[r(s_t,s_t)+\gamma V^{\pi_{\theta}}(s_{t+1})-V^{\pi_{\theta}}(s_{t})]\right]\\ &:=E_{\pi_{\theta'}}\left[\sum^{\infty}_{t=0}\gamma^t A^{\pi_{\theta}}(s_t,a_t) \right]\\ &=\frac{1}{1-\gamma}E_{s\sim v^{\pi_{\theta'}}}E_{a\sim \pi_{\theta'}(·|s)}[A^{\pi_{\theta}}(s,a)] \end{align} \] 利用\(v^{\pi_{\theta}}(s)=(1-\gamma)\sum^{\infty}_{t=0}\gamma^tP^{\pi}_{t}(s)\)因此，只要新的策略保证\(E_{s\sim v^{\pi_{\theta'}}}E_{a\sim \pi_{\theta'}}(·|s)[A^{\pi_{\theta}}(s,a)]\geq 0\)即可。
假设：新旧策略非常接近，状态访问分布变化小。因此直接采用旧策略的状态分布，得到替代的优化目标 \[ L_{\theta}(\theta')=J(\theta)+E_{s\sim v^{\pi_{\theta}}}E_{a\sim \pi_{\theta}(·|s)}[\frac{\pi_{\theta'}(a|s)}{\pi_{\theta}(a|s)}A^{\pi_{\theta}}(s,a)] \] 为了限制新旧策略，因此引入KL散度，整体的优化公式 \[ max_{\theta'}L_{\theta}(\theta') s.t.E_{s\sim v^{\pi_{\theta}}}\left[D_{KL}(\pi_{\theta},\pi_{\theta'})\right] \]
近似求解
参考动手学强化学习
PPO
直接将KL散度放到目标函数中， \[ arg\ max_{\theta'}E_{s\sim v^{\pi_{\theta}}}E_{a\sim \pi_{\theta}(·|s)}[\frac{\pi_{\theta'}(a|s)}{\pi_{\theta}(a|s)}A^{\pi_{\theta}}(s,a)-\beta D_{KL}(\pi_{\theta},\pi_{\theta'})] \]
PPO惩罚
令\(d_k=D_{KL}^{v^{\pi_{\theta}}}(\pi_{\theta},\pi_{\theta'})\),\(\beta\)的更新规则如下： \[ \beta_{k+1}= \begin{cases} \frac{\beta_k}{2},\ 如果\ d_k < \frac{\delta}{1.5} \\ \beta_k*2,\ 如果\ d_k > \delta*1.5 \\ \beta_k, 否则\\ \end{cases} \]
PPO截断
\[ \arg\max_{\theta} \mathbb{E}_{s \sim \nu} \mathbb{E}_{a \sim \pi_{\theta_k}(\cdot|s)} \left[ \min \left( \frac{\pi_{\theta}(a|s)}{\pi_{\theta_k}(a|s)} A^{\pi_{\theta_k}}(s, a), \text{clip} \left( \frac{\pi_{\theta}(a|s)}{\pi_{\theta_k}(a|s)}, 1 - \epsilon, 1 + \epsilon \right) A^{\pi_{\theta_k}}(s, a) \right) \right] \]
相当于限制住优势函数，如果\(A^{\pi_{\theta_k}}(s, a)>0\)，最大化这个式子会增加\(\frac{\pi_{\theta}(a|s)}{\pi_{\theta_k}(a|s)}\)，但是不会超过\(1+\epsilon\)，如果\(A^{\pi_{\theta_k}}(s, a)<0\)，最大化这个式子会减小\(\frac{\pi_{\theta}(a|s)}{\pi_{\theta_k}(a|s)}\)，但是不会超过\(1-\epsilon\)。