强化学习常见算法

强化学习问题一般用马尔可夫决策过程（MDP）表示。 \(M=(S,A,P,r,\rho_0,\gamma)\) ：

• \(S\) 表示状态集合；
• \(A\) 表示动作集合；
• \(P\) 表示状态转移概率，\(P(s'|s,a)\) 表示从状态s，动作a转移到s'的概率；
• \(r\) 是奖励函数；
• \(\rho_0\) 表示初始状态分布；
• \(\gamma\) 是折扣系数。

强化学习的策略 \(\pi(a \mid s)\) 将状态映射到动作空间上的概率分布。 智能体与环境交互产生交互轨迹 \(\{s_0, a_0, r_0, s_1, a_1, r_1, ... \}\) ，最优策略最大化累计奖励 \[ J(\pi) = E_{s_0, a_0, r_0, s_1, a_1, r_1, ... \sim \pi} \sum_{i=0}^\infty \gamma^i r_i \]

值函数用来衡量当前状态/动作下的长期累积奖励。 值函数有两种形式，

• 状态值函数

\[ V_\pi(s) = E_{s_0=s, a_0, r_0, s_1, a_1, r_1, ... \sim \pi} \sum_{i=0}^\infty \gamma^i r_i \]

• 状态动作值函数

\[ Q_\pi(s, a) = E_{s_0=s, a_0=a, r_0, s_1, a_1, r_1, ... \sim \pi} \sum_{i=0}^\infty \gamma^i r_i \] 这二者可以互相转换

\begin{align*} & V_\pi(s) = \sum_{a} \pi(a|s) Q_\pi(s, a) \\ & Q_\pi(s, a) = r(s, a) + \gamma \sum_{s'} P(s' | s, a) V_\pi(s') \end{align*}

二者统称为值函数。

最优策略满足贝尔曼最优方程， \[ V^*(s) = \max_a r(s, a) + \gamma \sum_{s'} P(s'| s,a) V^*(s') \] 给定策略 \(\pi\) ，对应的值函数满足贝尔曼期望方程， \[ V_\pi(s) = \sum_a \pi(a|s) \left[ r(s,a) + \gamma \sum_{s'} P(s' | s,a) V_\pi(s') \right] \] 一个马尔可夫决策过程对应的最优策略可能不是唯一的，但最优值函数是唯一的。 给定最优值函数，最优策略可以通过贪心法获得 \(\arg\max_a Q(s, a)\) 。 因此，搜索最优策略可以转化成寻找最优值函数。

DQN使用神经网络参数化值函数 \(Q(s,a; \theta)\) 。 最优策略对应的贝尔曼方程可以表示为 \[ Q(s, a; \theta^*) = r(s, a) + \gamma \max_{a'} Q(s', a'; \theta^*) \] 对于任意 \((s, a, s')\) 成立。

智能体与环境交互收集很多转移状态 \(\{s_i, a_i, r_i, s_i'\}_{i=1}^n\) 。 DQN最小化以下目标， \[ \min_\theta \frac{1}{n} \sum_{i=1}^n ( Q(s, a; \theta) - (r_i + \gamma \max_{a'} Q(s', a'; \theta_{old})) )^2 \]

DQN主要使用了两个技巧来避免训练不收敛，

• 经验重放（experience replay）。每次训练从中随机抽取 \(n\) 个训练样本，降低序贯数据之间的相关性。
• 延迟目标值函数更新。防止值函数训练过估计（over estimation）。 目标值函数和优化值函数使用不同参数的原因是Q-learning的想法是动态规划。 延迟更新的原因是，因为DQN每次随机更新一小部分状态值，不能保证Q-learning中的压缩映射， 而延迟更新能够从实验上缓解这个问题。请看这里的讨论。

DQN能够使用过去所有状态转移组的原因是，最优值函数在非最优状态转移下也具有动态规划性质。

分布值函数的贝尔曼期望方程如下所示， \[ Z(s,a) \overset{D}{=} R(s,a) + \gamma P^\pi Z(s,a) \] 其中， \(Z(s,a)\) 表示状态动作对 \((s,a)\) 的状态值的分布， \(R(s,a)\) 表示奖励值的分布， \(P^\pi Z(s,a)\) 表示状态转移后的分布， \(\overset{D}{=}\) 表示分布意义下相等。

和DQN一样，DDQN采用动态规划的方式计算目标状态值分布，然后最小化当前状态值分布与目标状态值分布之间的差距。

DDQN使用离散柱状图表示状态值函数的分布。 假设状态值介于 \(V_\min\) 和 \(V_\max\) ，将 \([V_\min, V_\max]\) 均分成 \(N\) 份，每份都有一个分布概率。 从状态值分布 \(Z(s,a)\) 出发，得到奖励值 \(r(s,a)\) （从随机变量 \(R(s,a)\) 中采样产生），然后到达下一个状态 \(s'\) 。 贝尔曼方程表示为，

\begin{align} \hat{Z}(s,a)[i] = \text{bin}(r(s,a) + \gamma \max_a Z(s', a; \theta)[i] \mid V_\min, V_\max, n) \label{eq} \end{align}

其中， \(\text{bin}(\cdot \mid V_\min, V_\max, n)\) 表示将状态值落在 \(V_\min\) 和 \(V_\max\) 之间的 \(n\) 个桶中。 具体来说， \(N\) 个值都有一个概率分布，然后新增了一个值 \(r\) ，改变了 \(N\) 值的状态分布。 \(N\) 个值之间的间隔为 \(\Delta V = (V_\max - V_\min)/N\) 。 对于每个 \(V_i\) 而言，

1. 计算 \(b = (r + \gamma V_i - V_\min) / \Delta V \in [0, N-1]\) ， \(l = \lfloor b \rfloor\) ， \(u = \lceil b \rceil\) 。

2. 更新概率 \(\P_j\) 和 \(\P_{j+1}\) 。初始阶段权重均为零 \(m_j = 0 ~ \forall j\) ，

   \begin{align*} & m_j \leftarrow m_j + \P_j \cdot (b - l) \\ & m_{j+1} \leftarrow m_{j+1} + \P_{j+1} \cdot (u - b) \end{align*}
3. 归一化概率 \(\P_i = m_i / \sum_j m_j\) 。

实现过程中 \(Z(s,a)\) 将状态动作 \(s\) 映射到 \(\mathbb{R}^{|\mathcal{A}| \cdot N }\) 的向量。

A3C算法的核心是基本的actor critic算法，主要用到策略梯度定理（policy gradient theorem）。

分别使用神经网络参数化策略函数 \(\pi_\theta\) 和状态值函数 \(V_\omega\) ，然后迭代求解。

异步更新的方式可以参考优化相关的论文，比如Hogwild!

DDPG主要基于确定性策略梯度定理（Deterministic Policy Gradient Theorem）。

确定性策略梯度定理 确定性策略 \(\mu_\theta\) 的累积奖励期望 \(J(\mu_\theta) = \E_{s_0, a_0, r_0, s_1, \ldots \sim \mu_\theta} \sum_{i=1}^\infty \gamma^i r_i\) 对 \(\theta\) 的导数为 \[ \nabla_\theta J(\mu_\theta) = \E_{s \sim \rho_{\mu_\theta}} \nabla_\theta \mu_\theta(s) \nabla_a Q(s,a; \pi_\theta)|_{a = \mu_\theta(s)} \] 其中 \(\rho_{\mu_\theta}\) 的定义和随机策略中的定义是一致的。 \(\P(s_0 \to s, k, \mu_\theta)\) 表示服从策略 \(\mu_\theta\) 从 \(s_0\) 出发经过 \(k\) 步之后到达 \(s\) 的概率， \(\rho_{\mu_\theta}(s) = \sum_{s_0 \in \mathcal{S}} \P(s_0) \sum_{k=1}^\infty \P(s_0 \to s, k, \mu_\theta)\) 。

DDPG是一个离轨强化学习算法，使用非当前策略的轨迹来更新参数。 在离轨情况下，以上策略梯度可以近似表示为 \[ \nabla_\theta J(\mu_\theta) \approx \E_{s \sim \rho} \nabla_\theta \mu_\theta(s) \nabla_a Q(s,a; \pi_\theta)|_{a = \mu_\theta(s)} \] 这里 \(\rho\) 表示另一个策略下的折扣状态分布。

此外，更新参数的时候，DDPG采用软更新（soft update）的方式： \(\theta \leftarrow \alpha \theta_{new} + (1-\alpha) (\theta_{new} - \theta)\) 。 DDPG通过添加随机扰动的方式增强确定性策略的探索能力，比如添加高斯扰动或者OU随机过程。

根据TRPO定理，为了方便计算，将状态动作空间下的最大化约束换成平均约束，

\begin{equation} \label{eq:trpo} \begin{aligned} \resetcounter & \max_\theta L_{\pi_{old}} (\pi_\theta) \\ & s.t. ~ \E_{s \sim \rho_{\pi_{old}}} KL(\pi_{old}(\cdot \mid s) \| \pi_\theta(\cdot \mid s)) \leq \delta \end{aligned} \end{equation}

这里的优化问题和开头的优化问题几乎是一样的。 我们在实际求解开头的优化问题时，会将优化目标近似处理成 \(L_{\pi_{old}} (\pi_\theta)\) 的形式。

TRPO使用KL散度约束策略变化，求解的优化问题如下，

\begin{align*} & \max_\theta \E_{t} \frac{\pi_\theta(a_t \mid s_t)}{\pi_{old}(a_t \mid s_t)} A(s_t, a_t) \\ & s.t. ~ \E_{s_t \sim \rho_{\pi_{old}}} KL(\pi_{old}(\cdot \mid s_t) \| \pi_\theta(\cdot \mid s_t)) \leq \delta \end{align*}

以上约束优化问题不太容易求解。PPO通过截断比值的方式来简化优化问题， \(\resetcounter\)

\begin{align} \max_\theta ~ \E_{t} \left[ \min( r_t A_t, \text{clip}(r_t, 1-\epsilon, 1+\epsilon) A_t) \right] \label{eq:ppo} \end{align}

其中 \(r_t = \pi_\theta(a_t \mid s_t) / \pi_{old}(a_t \mid s_t)\) 。 clip 操作限制策略比值的变化范围。 假设 \(A_t > 0\) ，那么

\begin{align*} \min( r_t A_t, \text{clip}(r_t, 1-\epsilon, 1+\epsilon) A_t) = \begin{cases} (1 + \epsilon) A_t & r_t > 1 + \epsilon \\ r_t A_t & r_t <= 1 + \epsilon \end{cases} \end{align*}

\(r_t\) 中蕴含参数 \(\theta\) ， \(A_t\) 不含参数 \(\theta\) 。 因此，当 \(r_t > 1 + \epsilon\) 时，上式对 \(\theta\) 的导数为零。 PPO过滤了 \(r_t > 1 + \epsilon\) 的训练样本。

PPO和TRPO都是同轨算法。 PPOd的计算流程和TRPO保持一致，除了求解的优化目标不一样。

SAC 将信息熵加到奖励函数中，优化以下目标 \[ \max_\pi J(\pi) = \sum_{t=0}^T \E_{(s_t,a_t) \sim \rho_\pi} [ \gamma^t r(s_t, a_t) + \alpha H(\pi(\cdot \mid s_t)) ] \] 其中 \(H(\P(\cdot)) = - \sum_x \P(x) \log \P(x)\) 。

奖励函数被修改之后，相应的贝尔曼方程和值函数也发生了变化，

\begin{align*} & T^\pi Q(s_t, a_t) \triangleq r(s_t, a_t) + \gamma \E_{s_{t+1} \sim P} V(s_{t+1}) \\ & V(s_t) = \E_{a_t \sim \pi} [Q(s_t, a_t) - \log \pi(a_t \mid s_t)] \end{align*}

因此，全部由状态值函数构成的贝尔曼方程可以表示如下 \[ T^\pi Q(s_t, a_t) = r(s_t, a_t) + \gamma \E_{s_{t+1} \sim P, a_{t+1} \sim \pi} Q(s_{t+1}, a_{t+1}) + \alpha \E_{s_{t+1} \sim P} H(\pi(\cdot \mid s_{t+1})) \] 容易看出在奖励函数中添加了鼓励探索的信息熵。

SAC的理论分析是在上面的值函数动态规划下进行的。 将策略表示为值函数的指数形式， 使用KL散度距离投影到高斯概率空间， \[ \pi_{new} = \underset{\pi' \in \Pi}{\arg\min} KL \left( \pi'(\cdot \mid s_t) \| \frac{\exp(Q_{\pi_{old}}(s_t, \cdot))}{Z_{\pi_{old}}(s_t)} \right) \]

值函数一般基于贝尔曼方程采用动态规划的方式进行更新， \[ Q(s_t, a_t; \omega) = r(s_t, a_t) + \gamma \max_a Q(s_{t+1}, a; \omega) \] 实验中发现，这种方式估计的值函数是不准的，一般大于真实值。

TD3使用两个值函数来进行值函数估计，值函数目标设为二者之间的较小值， \[ Q(s_t, a_t; \omega) = r_t + \gamma \min ( Q(s_{t+1}, \pi_1(s_{t+1}); \omega_1), Q(s_{t+1}, \pi_1(s_{t+1}); \omega_2) ) \] 这里的动作不是贪心动作。

实际计算中，TD3会对策略给出的动作添加扰动，加大随机力度，缓解过估计。