2.2.1 计算 $p(\tau | \theta)$#

2.2.1 计算梯度#

通常我们利用梯度方向更新参数, 所以需要计算 $\mathbb{E}_{\tau} [R(\tau)]$ 关于 $\theta$ 的梯度:

这里, 对于任意 $\tau$ :

上式中, $log \ p(s_1)$ 与 Actor 无关, $log \ p(r_t,s_{t+1}|s_t,a_t)$ ,也与 Actor 无关, 因此:

于是:

写成期望的版本:

使用梯度提升更新 Actor 的参数:

2.2.2 改进奖励计算方式#

上边在建模 reward 的时候, 任何 action 的奖励都是正的, 这明显不合理, 因此可以加一个 baseline :

一般的, baseline b 可以取值为截至目前的平均 reward: $b \approx \mathbb{E}\_{\tau} [R(\tau)]$.

此外, 上边式子可以理解为是对 $log \ p(a_t^n|s_t^n,\theta)$ 的一个 sum weight. 其中 $R(\tau^n) - b$ 表示的是, 在 state $s_t$ 时采取 action $a_t$ 时对后来获得的总奖励的影响是多大.

另外还可以从减少 variance 的角度来理解, 可移步至此(点击跳转)

在上边的公式中, 这个 weight 对每个时间步 t 都一样, 均为 $R(\tau^n) - b$. 直觉上, 当前时间步 t 采取的动作, 只能影响 时间步 t 之后的奖励或者状态等. 并且随着时间流逝, 时间步 t 采取的动作对后续的影响应该越来越小, 因此对 $R(\tau)$ 进行修改(忽略 b ):

其中, $\gamma < 1$, baseline 也同步修改. 举个例子, 假设 $\gamma = 0.99, t = 3 , T = 5$:

注意到, 此时 $R(\tau^n)$ 是想评估当前 actor 基于当前 state $s_t$ 和 action $a_t$ 的分数, 不妨记为 $Q^{\pi}(s_t,a_t)$, 而 $b$ 可以理解为度量面对当前 state $s_t$ (不与 action 有关), 这个 actor 平均能够取得的分数, 不妨记为 $V^{\pi}(s_t)$, 那如果把 $Q^{\pi}(s_t,a_t) - V^{\pi}(s_t)$ 记为 $A^{\theta}(s_t,a_t)$, 其实这就是 Value Based 方法 (也就是一个 critic). 二者结合, 就是 Actor - Critic, 我们后续会讨论. 此时, 之前的期望公式就可以写为:

2.3.1 Importance Sampling#

首先介绍一个 trick, 假设我们要计算 $\mathbb{E}_{x \sim p} [f(x)]$ , 但是 $p(x)$ 也许不好计算, 不好得到, 但是我们有一个分布 $q(x)$, 计算很容易, 也很容易积分:

可以看到, 本来是从 $p(x)$ 抽取数据, 现在做到从 $q(x)$ 抽取数据, 并且期望还不变. 但是需要注意的是, 他们的方差是不一样的.

首先:

而:

二者方差差一点, 因此要求 $p(x)$ 和 $q(x)$ 不要差太多.

2.3.2 off - policy#

off-policy 就是利用上边的 importance sampling, 使用另外一个 policy ${\theta_{old}}$ 的 {( $s_t,a_t$ )} 去更新 policy ${\theta}$. 于是,

上式 $p_{\theta}(s_t) \approx p_{\theta_{old}}(s_t)$ 是我们进行的假设, 假设环境在第 t 步出现的状态和 Actor 无关( 看起来不太合适, 这个也是没办法的办法 ). 此外 policy ${\theta_{old}}$ 是固定的, 用来和环境交互, policy ${\theta}$ 是我们要更新的. 更新一段时间后, 我们可以执行 $\theta_{old} <-- \theta$ 以防二者差距太大.

这样, 反推得到:

如果使用 Actor - Critic 的方式评估 $R(\tau)$,之前的期望公式就可以写为:

反推得到

3.2.1 Bellman equation for $V^{\pi}(s)$#

上边这个式子称为 $V^{\pi}(s)$ 的 Bellman equation, 它揭示了当前 $\text{state s}$ 下的 $V^{\pi}$ 与下一时刻的 $\text{state s'}$ 的 $V^{\pi}$ 之间的关系.

3.2.2 Bellman optimality equation for $V^{\pi}(s)$#

从定义上我们有:

上式称为 Bellman optimality equation for $V^{\pi}(s)$

3.2.3 Bellman optimality equation for $Q^{\pi}(s,a)$#

按定义我们有:

上式称为 Bellman optimality equation for $Q^{\pi}(s,a)$

3.3.1 Policy Evaluation#

动态规划的思想就很直观, 直接根据我们之前的 Bellman equation 迭代就行了, 因为 Bellman equation 描述的就是 $\pi_{\ast}$ 本身的性质. 更新迭代公式如下:

上述迭代过程称为 iterative policy evaluation. 此外, 也可以使用 Bellman equation for $Q^{\pi}(s,a)$ 做迭代, 就是直接对 $Q^{\pi}(s,a)$ 迭代. 这个称为 Q-policy Iteration.

3.3.2 Policy Improvement#

我们的目是找一个 policy, 能够面对不同的 state 采取一个 action. 已知

现在我们让 $Q^{\pi}(s,a)$ 最大, 这会得到一个相应的 action $a^{\ast}$ , 如果我们让另外一个 $\pi'$ 每次都能让以下式子成立:

这就意味着, 这个 $\pi'$ 每次都能采取最优的 action. 从而总是有:

于是:

上述过程称为 Policy Improvement. 现在, 如果更新后的 policy 和原始的 policy 一样, 即 $V^{\pi} = V^{\pi'}$, 于是:

可以看到, 这就是 3.2.2 的 Bellman optimality equation for $V^{\pi}(s)$. 换句话说, 此时的 $\pi' = \pi$ 就是最优的 $\pi$.

3.3.3 Policy Iteration#

source from refer Reinforcement Learning: An Introduction

我们使用 Policy Evaluation 去迭代 $V^{\pi}(s)$, 实现让 $V^{\pi}(s)$ 预估的更加准确.

然后, 我们使用 Policy Improvement 去找到一个更好的 $\pi$. 上述过程称为 Policy Iteration.

这个过程 Policy Evaluation 和 Policy Improvement 是交替循环的, 如下:

source from refer Reinforcement Learning: An Introduction

后续, 多个方法思路都是类似的, 上述循环过程称为 Generalized Policy Iteration.

3.3.4 Value Iteration#

Policy Iteration 有 2 个步骤, 首先要让 V 预估准确, 然后再使用 Policy Improvement, 步骤比较繁琐, Value Iteration 的思想是, 直接从 Bellman optimality equation for $V^{\pi}(s)$ 入手 :

上述式子描述的是, 最优的 $\pi_{\ast}$ 能够满足的式子, 于是我们直接使用这个式子进行迭代:

当上式迭代收敛后, 得到的一个预估准确的 V function, 并且 $V(s)$ 的结果就是最优的 $\pi_{\ast}$ 对应的 V 值. 算法如下:

source from refer Reinforcement Learning: An Introduction

3.3.5 DP 方法总结#

DP 方法总体思路为迭代方法, 主要基于 Bellman equation 进行迭代更新. 它基于当前状态, 观察所有可能的下一步来更新. 如图所示:

source from refer Monte Carlo Methods

3.4.1 state value based#

Monte-Carlo 方法就很质朴, 直接基于当前 state, 然后你玩游戏直到结束, 记录分数, 最后求和得到累计奖励 $R$, 然后 minimize 二者的差距:

具体的, 对于某个具体的 state $s$, 收集一批以 s 为起点的 trajectory, 最后计算 reward 的均值作为 $V^{\pi}(s)$:

source from refer Reinforcement Learning: An Introduction

思想如图所示:

source from refer Monte Carlo Methods

3.4.2 state action value based#

但是 state value based 可能比较困难, 因为要预估当前 state 下, 所有 action 的结果. 如果直接预估当前 state 下, 采取一个 action 之后的值可能好一点. 具体的, 收集一批以 state s , action a 为起点的 trajectory , 最后计算 reward 的均值作为 $Q^{\pi}(s,a)$:

source from refer Reinforcement Learning: An Introduction

上述过程也是一个 cycle, 我们使用 Monte-Carlo 方法得到一个预估准确的 Q function, 然后使用这个 Q function 去让 $\pi(s) = \mathop{\arg\max}\limits_{a} \ Q^{\pi}(s,a)$ 实现 improvement 的操作. 这种取 max 的操作也叫做 $greedy$, 考虑到 Exploration/Exploitation trade-off , 如果每次都取 max, 会抑制后续的 exploration. 因此引入 $\epsilon - greedy$, 算法如下:

source from refer Reinforcement Learning: An Introduction

3.5.1 迭代公式#

回顾 $V^{\pi}(s)$ 的定义: 计算 $\pi$ 面对当前 state s 能够获得的奖励, 记 $N_{a}^{k}(s)$ 表示基于当前 state 采样的 action 数目.

抽象一下, 可以表示为下边的迭代公式:

$V_{k -1 }^{\pi}(s)$ 告诉我们当前的预估, $R_{N_{a}^{k}(s)}$ 是真实看到的结果, $R_{N_{a}^{k}(s)} - V_{k -1 }^{\pi}(s)$ 告诉我们应该向实际看到的 reward 方向走, 这很像智能优化中的粒子群算法(关于该算法可以看我的视频讲解).

3.5.2 TD-Prediction#

假设我们的 critic 是准确的, 应该有:

易知:

从而:

上式中, $\gamma V^{\pi}(s_{t+1}) + r_t$ 描述的是向后预估一个 state $s_{t+1}$ 的 value. 然后再回过头来, 结合当前的预估值看预估的准不准, $\gamma V^{\pi}(s_{t+1}) + r_t - V^{\pi}(s_t)$ 也称为 temporal difference error (TD-error).

那如果 $V^{\pi}(s)$ 不准确, 我们可以使用 $\gamma V^{\pi}(s_{t+1}) + r_t$ 来纠正 $V^{\pi}$(因为 $r_t$ 至少是确定的).

于是,可以使用如下迭代公式更新 $V^{\pi}(s)$ :

前边的 Monte-Carlo based 也可以写作如下式子:

所以 Monte-Carlo based 就是直接用真实的、整个 trajectory 的 reward 与 $V^{\pi}(s)$ 做比较, 而 Temporal-difference based 则是向后玩一步或者多步, 剩余的使用 $V^{\pi}$ 进行预估.

当然, 由于现在大家都是 neural network , 因此也可以直接使用梯度下降 minimize 以下差异 DRL Lecture 3: Q-learning:

不过需要注意的是, MC 方法和 TD 方法有时候预估出来的结果可能不一样: source from refer DRL Lecture 3: Q-learning

二者没有说谁对谁错, 只是基于当前的数据, 作出的合理的判断. 不过由于便捷性和效率, 通常使用 TD 方法, 毕竟 MC 方法太磨叽了.

3.5.3 SARSA: ON-POLICY TD CONTROL#

我们也可以直接对 $Q^{\pi}(s,a)$ 进行 TD-Prediction, 该算法也叫 SARSA (State-Action-Reward-State-Action) .

source from refer Reinforcement Learning: An Introduction

这个地方 ON-POLICY 是说我们对下一个 action $s_{t+1}$ 的 Q value 预估用的 policy 和获取下一个 action $s_{t+1}$ 的 policy 是同一个.

3.5.4 Q-Learning: Off-Policy TD Control#

Q Learning 则是直接类似 3.3.4 节的 Value Iteration. 我们可以直接将 improvement 嵌入到更新公式里边, 直接期望 Q function 收敛到最优的 policy $\pi_{\ast}$ 对应的 Q. 算法如下:

source from refer DRL Lecture 3: Q-learning

Q-Learning 也被称为 Off-Policy, 是因为我们计算 $r_t + \mathop{\max}\limits_{a} \ Q^{\pi}(s_{t+1},a)$ 的时候用的是 $\mathop{\max}\limits_{a} \ Q^{\pi}(s_{t+1},a)$, 而不是 $\pi$ 真正想输出的 action.

可以这样理解, 存在一个 $\pi_{\ast}$, 使得:

于是, 每次对下一个 action $s_{t+1}$ 的 Q value 预估的时候, 实际上用的 policy 是 $\pi_{\ast}$, 而基于当前 state $s_t$ 采取 action 的 policy 是 $\pi$. 二者不是同一个, 因此叫 Off-Policy.

这个过程就是”培养” $\pi$, 去尽量向着最优的 $\pi_{\ast}$ 给的方向走.

实作上, 由于大家现在都是 neural network 了, 可以直接使用梯度下降去 $\text{minimize}$ 误差:

算法如下:

[1]. 初始化 Q-function $Q^{\pi}(s,a)$, target Q-function $\tilde{Q^{\pi}}(s,a)$

[2]. 然后对每个 state 都采取 action a, where $a = \mathop{\arg\max}\limits_{a} \ Q^{\pi}(s,a)$

[3]. 这样就能收集到一批 4 元对 : {$s_t,a_t,r_t,s_{t+1}$} 到 buffer 里边(buffer 里边的数据要及时更换, 把太早的丢掉, 用更新的 $Q^{\pi}$ 产生的数据放进去.).

[4]. 从 buffer 里边 sample 一笔数据, {$s_i,a_i,r_i,s_{i+1}$}.

[5]. 由于等式左右两边都在变, 考虑到稳定性, 我们用 target Q-function (fixed) 去替换 $\mathop{\arg\max}\limits_{a} \ Q^{\pi}(s_{i+1},a)$, 于是优化目标变为:

上边的式子还有一个问题, 就是后边

完全是由 Target Net 来选择高分的 action. Double DQN 发现, Target Net 总是高估自己的 action 的分数, 于是提出用 2 个 net 相互制衡, 实作很简单, 直接 action 输出使用正在更新的 $\pi$ 即可, 然后打分还是用 $\tilde{Q^{\pi}}$ :

换个更常见的写法, 优化目标最终变为:

[7]. if step % C = 0, $\tilde{Q^{\pi}} = Q^{\pi}$

这里需要注意的是, $\pi$ 只有一个, 只是 Q function 有 2 个, 其中 $\tilde{Q^{\pi}}$ 的引入只是为了更新的稳定性(如果不考虑稳定性, 那就是原始算法). 但是无论如何, 目标就是要让 $\pi$ 逼近潜在的最优的 $\pi_{\ast}$. (off-policy)

3.5.5 SARSA VS Q-Learning#

这里有一个例子, 图中 Cliff 区域的奖励是 -100, 其他区域奖励为 -1. 可以看到 Q-Learning 尽管每次 action 的选取用到了 $\epsilon - greedy$, 但是我们做 Q 值预测的时候, 总是选择 $\text{max}$ 的, 这就导致最后 Q-Learning 收敛到 optimize policy. 而 SARSA 得到则是相对次优的:

source from refer Reinforcement Learning: An Introduction

3.5.6 DP VS TD#

DP 方法参考 3.3 节. 下边给出 DP 和 TD 方法的区别和联系.

3.5.7 Forward View of TD-$\lambda$#

前边我们只是向后观察 1 步:

我们可以向后观察 2 步:

可以向后观察 k 步:

上式全部为 $Q(s_t,a_t)$, 我们可以使用加权取平均对所有结果, 记:

$\lambda$ 加权平均:

其中, $\frac {1}{1 + \lambda + ... + \lambda^{k-1} }$ 使得权重求和为 1.

source from refer Reinforcement Learning: An Introduction

上述版本称为 Forward View of TD(λ). 原因是我们站在当前 time step 向后观察每个 state 的情况, 越往后的 state, 所分配的更新权重越小(对当前的 state $s_t$ 影响越小):

source from refer Reinforcement Learning: An Introduction

3.5.8 Backward View of TD-$\lambda$#

这里需要引入 eligibility trace. 其定义公式如下:

上述公式的逻辑是这样的. 假设有一个特定的 state s. 如果当前这轮更新 Q 的时候, 遇到的 state 就是 s, 那么

否则, 就是当前 state 是其他的 $\text{s'}$, 那么

如果一个 state s 经常多次出现, 那么属于这个 s 的 $E(s)$ 就会比较大, 反之就会由于 $\gamma \lambda$ 的存在衰减到 0.

此外 Dutch traces, 当 visit 一个 state 时, 会在之前的基础上先做一个衰减, 然后再加 1. 还有一种是 replacing trace, 当 visit 一个 state 时, 直接会把 traces 置为 1 :

source from refer Reinforcement Learning: An Introduction

算法过程如下:

source from refer Reinforcement Learning: An Introduction

需要注意的是, 虽然当前遇到的 state 是 S, 内部的 for 循环在更新 $V(s)$ 的时候, 都使用同一个 $\delta \leftarrow R + \gamma V(S') - V(S)$ 对所有的 state 更新.

这个被称为 Backward View of TD-$\lambda$, 是因为我们对每个 sate s 更新的时候, 是基于当前 state S 的 TD-error, 只不过同时还基于 state s 对应的 $E(s)$. 如果 state s 距当前 state S 很远(表现为出现次数很少, 因为我们按时序 visit state), 那么其 $E(s)$ 就会很小, 最后分配的权重就会很小:

source from refer Reinforcement Learning: An Introduction

3.5.9 Equivalences of TD-$\lambda$#

• $\lambda = 0$

forward view : 这个按定义的计算方式, 易知此时就是 TD(0).

backward view : 当 $\lambda = 0$ 时, 只有当前 state S 对应的 $E(S) = 1$ , 其他的永远恒为 0. 此时就是 TD(0).

对于 Online(实时更新) 和 Offline(重复收集多个 episode 的数据, 最后进行 batch update) 的学习方式, 由于 $\lambda = 0$ 时, TD(0) 的 reward 计算方式 : $G_t = r_t + \gamma V(s_{t+1})$, 此时的 TD-error 就只关注相邻的 2 个 state, 因此最终结果是一样的.

• $\lambda = 1$

forward view 如下: