Model free 基础方法

TL;DR

暂无

Bellman 公式中总结了对于 With model RL 的基本原则和更新方式，但是现实中的问题通常不能保证有严谨的公式。本笔记想对 model free RL的基本方法和思想进行一些概括和总结，好对后面的Actor Critic等算法打好基础。此处所说的 model 指的是环境模型，即对环境的状态转移概率和奖励机制进行建模。在拥有 Model 的情况下（类似围棋），智能体可以预知执行某个动作后环境会发生怎样的变化（确定性或随机性）；而 Model-free RL 则是要在不掌握这些环境动态规律的情况下，直接通过与环境的交互来学习策略。

蒙特卡洛方法

蒙特卡罗方法是所有 model free RL 的基础，因为没有了 Model 预测执行某个动作后会发生，就只能通过通过大量采样取平均来近似期望回报，从而估计 $q(s,a)$。

比如说Bellman 公式中的计算出状态价值函数 $v_{{\pi }_k}$ 后可以得到状态-动作价值函数的计算方法：

$$q_{{\pi }_k}(s,a)=\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{{\pi }_k}(s^{\prime }).$$

然而这个方法需要知道系统模型 $\{p(r|s,a),p(s^{\prime }|s,a)\}$ 已知，对于 model free 方法来说，回归定义：

$$\begin{array}{rl}{q}_{{\pi }_k}(s,a)& =\mathbb{E}[G_t|S_t=s,A_t=a]\\ & =\mathbb{E}[R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots |S_t=s,A_t=a],\end{array}$$

也就是累计折扣回报的期望，假定总共 $n$ 轮采样，而第 $i$ 轮回报是 $g_{{\pi }_k}^{(i)}(s,a)$，则蒙特卡罗方法将 $q_{{\pi }_k}(s,a)$ 可以由下列公式近似：

$$q_{{\pi }_k}(s,a)=\mathbb{E}[G_t|S_t=s,A_t=a]\approx \frac{1}{n}\sum _{i=1}^n{g}_{{\pi }_k}^{(i)}(s,a).$$

MC Basic 算法

$$\begin{array}{l}\text{Algorithm 5.1: MC Basic (a model-free variant of policy iteration)}\\ \\ \text{Initialization:}\text{ Initial guess }{\pi }_0.\\ \text{Goal:}\text{ Search for an optimal policy.}\\ \\ \text{For the }k\text{th iteration }(k=0,1,2,\dots ),\text{ do}\\ \text{For every state }s\in \mathcal{S},\text{ do}\\ \text{For every action }a\in \mathcal{A}(s),\text{ do}\\ \text{Collect sufficiently many episodes starting from }(s,a)\text{ by following }{\pi }_k\\ \\ \text{Policy evaluation:}\\ q_{{\pi }_k}(s,a)\approx q_k(s,a)=\text{the average return of all the episodes starting from }(s,a)\\ \\ \text{Policy improvement:}\\ a_k^{\ast }(s)=\arg {\max }_a{q}_k(s,a)\\ {\pi }_{k+1}(a|s)=\{\begin{array}{ll}1& \text{if }a=a_k^{\ast }\\ 0& \text{otherwise}\end{array}\end{array}$$

可以看到这个方法基本就是 Policy iteration 方程的 model free 方法，显示 Policy evaluation 然后接着 Policy improvement。但是注意原来的 PE 是更新状态 $V$ 状态价值函数，此处改为更新 $Q$ 状态-动作价值函数，这是因为在 PI 这步，model-based 方法是通过该方程求解：

$$a^{\ast }=\arg \underset{a}{\max }\sum _{s^{\prime }}p(s^{\prime }|s,a)\left[r(s,a,s^{\prime })+\gamma v_{\pi }(s^{\prime })\right]$$

但是 model free 中，$p(s^{\prime }|s,a)$ 是未知的，所以采用对状态-动作奖励函数进行优化。

$$\text{Collect sufficiently many episodes starting from }(s,a)\text{ by following }{\pi }_k$$

这步的采样深度 $\text{episode length}$ 也会极大影响质量，即从 $(s,a)$ 出发，走几步才停止采样。

整体来说，MC basic 方法过于原始，工程上会采取许多优化方法。比如说把一个策略的 episode 多次利用：

$$s_1\stackrel{a_2}{\to }{s}_2\stackrel{a_4}{\to }{s}_1\stackrel{a_2}{\to }{s}_2\stackrel{a_3}{\to }{s}_5\stackrel{a_1}{\to }\cdots$$

对于这一条轨迹，不仅可以估计 $q(s_1,a_2)$ 的值，并且可以同时估计沿线的所有状态的状态-动作价值函数，比如可以同时利用 $(s_2,a_4),(s_5,a_1)$ 的状态来估值。其中，如果每一个 状态-动作对 只可以将第一次用于估计，则成为 $\text{first-visit}$，否则则成为 $\text{every-visit}$

$\pi (a|s)=\{\begin{array}{ll}1-\epsilon +\frac{\epsilon }{|\mathcal{A}(s)|}& \text{if }a=a^{\ast }\\ \frac{\epsilon }{|\mathcal{A}(s)|}& \text{otherwise}\end{array}$ 这个改进首先是增大了每一个 episode 的利用率，不再是一个轨迹只修改一个 状态动作对的价值函数，而是可以修改整个轨迹中的状态动作对的价值函数，可以利用下一步的 累计折扣回报$g$ 来更新上一步的回报，即 $g\leftarrow \gamma g+r_{t+1}$ 这步。

同时，这个算法是每采样完一个 episode 就评价和更新策略，而不是像经典MC那样采够了足够的轨迹才开始更新。

但是这个方法没法保证每种状态动作对都探索到了，如果没有探索到，因为没有样本，回报会严重不足，可能会导致策略陷入局部最优解。因此算法引入了一些随机性，采用了 $ϵ$-greedy policies 的方法，采用部分随机的方式来改进策略：

$$\pi (a|s)=\{\begin{array}{ll}1-\epsilon +\frac{\epsilon }{|\mathcal{A}(s)|}& \text{for the greedy action }\\ \frac{\epsilon }{|\mathcal{A}(s)|}& \text{for the other}|\mathcal{A}(s)|-1\text{actions}\end{array}$$

最后改进为：

$$\begin{array}{l}\text{Algorithm 5.3: MC }ϵ\text{-Greedy (a variant of MC Exploring Starts)}\\ \\ \text{Initialization:}\text{ Initial policy }{\pi }_0(a|s)\text{ and initial value }q(s,a)\text{ for all }(s,a).\\ \text{Returns}(s,a)=0\text{ and }\text{Num}(s,a)=0\text{ for all }(s,a).\\ ϵ\in (0,1]\\ \\ \text{Goal:}\text{ Search for an optimal policy.}\\ \\ \text{For each episode, do}\\ \text{Episode generation:}\text{ Select a starting state-action pair }(s_0,a_0)\text{ (the exploring starts}\\ \text{condition is not required). Following the current policy, generate an episode of length }T:\\ s_0,a_0,r_1,\dots ,s_{T-1},a_{T-1},r_T.\\ \text{Initialization for each episode: }g\leftarrow 0\\ \text{For each step of the episode, }t=T-1,T-2,\dots ,0,\text{ do}\\ g\leftarrow \gamma g+r_{t+1}\\ \text{Returns}(s_t,a_t)\leftarrow \text{Returns}(s_t,a_t)+g\\ \text{Num}(s_t,a_t)\leftarrow \text{Num}(s_t,a_t)+1\\ \text{Policy evaluation:}\\ q(s_t,a_t)\leftarrow \text{Returns}(s_t,a_t)/\text{Num}(s_t,a_t)\\ \text{Policy improvement:}\\ \text{Let }{a}^{\ast }=\arg {\max }_{a}q(s_t,a)\text{ and}\\ \pi (a|s_t)=\{\begin{array}{ll}1-\frac{|\mathcal{A}(s_t)|-1}{|\mathcal{A}(s_t)|}ϵ,& a=a^{\ast }\\ \frac{1}{|\mathcal{A}(s_t)|}ϵ,& a\ne a^{\ast }\end{array}\end{array}$$

可以看到，当 $ϵ$ 越大的时候，策略越趋向随机来遍历所有状态-动作状态。

随机近似

对于上述的算法中，利用增量的方式求均值的方式，是如何知道其是有效的：

$$w_{k+1}=w_k-\frac{1}{k}(w_k-x_k).$$

对于系数为 $\frac{1}{k}$ 来说，可以通过数学推导来得到结果，但是对于其他系数呢，什么系数能满足这个公式？ 为什么这些系数可以逼近平均数？

Robbins-Monro 公式是来解答这个问题的，即逼近方程解的有效性，由于重心不在这，因此我只是粗略介绍。增量近似和 SGD 算法都是 RM 方程的一种特例。

总体来说，RM 算法想回答一个方程解的问题，我们想求一个方程的根，由此可以等价成求方程的任意解：

$$g(w)=0$$

有了这个方程解，我们可以求出梯度解，得到最优质，或者得到 $g(w)=c$ 这类方程的答案。但是其中的方程 $g$ 是带有随机性的方程，或者说我们只能观测到带有噪音的 $g(w)$，比如说 SGD 或者增量求平均数的时候，我们不知道下一个样本对客观量的偏移量:

$$\tilde{g}(w,\eta )=g(w)+\eta$$

这个 $\eta \in \mathbb{R}$ 是一个观测误差，不一定是高斯分布。

RM 算法保证，可以通过下列方程求解 $g(w)=0$ ：

$$w_{k+1}=w_k-a_k\tilde{g}\left(w_k,{\eta }_k\right),k=1,2,3,\dots$$

其中

• $w_k$是第 $k$ 个根的估计；
• $\tilde{g}\left(w_k,{\eta }_k\right)$ 是第 $k$ 个带噪采样；
• $a_k$ 是个正参数。

只要满足以下条件，则可以保证能求出正确参数：

1. 对所有 $w$ 有 $0<c_1\le {\nabla }_{w}g(w)\le c_2$；
2. ${\sum }_{k=1}^{\infty }{a}_k=\infty$ 且 ${\sum }_{k=1}^{\infty }{a}_k^2<\infty$；
3. $\mathbb{E}[{\eta }_k|{\mathcal{H}}_k]=0$ 且 $\mathbb{E}[{\eta }_k^2|{\mathcal{H}}_k]<\infty$；

其中 ${\mathcal{H}}_k=\{w_k,w_{k-1},\dots \}$，则 $w_k$ 几乎必然收敛到满足 $g(w^{\ast })=0$ 的根 $w^{\ast }$。

证明略，见书第六章。

可以发现求增量平均和 SGD 方法中的参数 $\frac{1}{n}$ 满足其本身是级数发散，平方是级数收敛，正好满足 RM 算法对参数的要求。

TD 算法

把随机近似应用到 model free 估计中就可以得到 TD(Temporal-Difference) 方法。不同于 MC 方法使用统计学的方法，TD 方法采用基于动态规划的随机近似，即基于上文中阐述的随机近似方法。

$$\begin{array}{rl}{v}_{t+1}\left(s_t\right)& =v_t\left(s_t\right)-{\alpha }_t\left(s_t\right)\left[v_t\left(s_t\right)-\left(r_{t+1}+\gamma v_t\left(s_{t+1}\right)\right)\right]\\ v_{t+1}(s)& =v_t(s),\text{ for all }s\ne s_t\end{array}$$

这是由于 $v_{\pi }(s)=\mathbb{E}\left[R_{t+1}+\gamma v_{\pi }\left(S_{t+1}\right)\mid S_t=s\right],s\in \mathcal{S}.$ 因此这就是和求增量平均那个随机近似方法一样，用新的采样和上一步参数来估计下一步参数：$w_{k+1}=w_k-\frac{1}{k}(w_k-x_k).$

$$\underset{\text{new estimate }}{\underbrace{v_{t+1}\left(s_t\right)}}=\underset{\text{current estimate }}{\underbrace{v_t\left(s_t\right)}}-{\alpha }_t\left(s_t\right)[\stackrel{\text{TD error }{\delta }_t}{\overbrace{v_t\left(s_t\right)-(\underset{\text{TD target }{\bar{v}}_t}{\underbrace{r_{t+1}+\gamma v_t\left(s_{t+1}\right)}})}}],$$

这个方程中：

$${\bar{v}}_t\doteq r_{t+1}+\gamma v_t\left(s_{t+1}\right)$$

被称为 TD target ，同时：

$${\delta }_t\doteq v\left(s_t\right)-{\bar{v}}_t=v_t\left(s_t\right)-\left(r_{t+1}+\gamma v_t\left(s_{t+1}\right)\right)$$

被称为 TD error，因为 TD error 度量的是 Bellman 方程的残差，真值 $v_{\pi }(s_t)$ 满足：

$$v_{\pi }(s)=\mathbb{E}[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s]$$

所以当 $v_t=v_{\pi }$ 时，$\mathbb{E}[{\delta }_t|S_t=s_t]=v_{\pi }(s_t)-\mathbb{E}[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s_t]=0$。同时

$$\left|v_{t+1}\left(s_t\right)-{\bar{v}}_t\right|=\left|1-{\alpha }_t\left(s_t\right)\right|\left|v_t\left(s_t\right)-{\bar{v}}_t\right|.$$

所以有：

$$\left|v_{t+1}\left(s_t\right)-{\bar{v}}_t\right|<\left|v_t\left(s_t\right)-{\bar{v}}_t\right|$$

可以保证新的估计值比旧的估计值更接近真值，因此，这个方程可以肯定最后是可以收敛到结果中的。

TD学习	MC学习
增量式（Incremental）：TD学习是增量式的。它可以在接收到一个经验样本后立即更新状态/动作值。	非增量式（Non-incremental）：MC学习是非增量式的。它必须等待一个完整的回合（episode）被收集完毕。这是因为必须计算该回合的折扣回报。
持续任务（Continuing tasks）：由于TD学习是增量式的，它可以处理回合制和持续性任务。持续性任务可能没有终止状态。	回合制任务（Episodic tasks）：由于MC学习是非增量式的，它只能处理在有限步数后终止的回合制任务。
自举（Bootstrapping）：TD学习使用自举，因为状态/动作值的更新依赖于该值的先前估计。因此，TD学习需要对值进行初始猜测。	非自举（Non-bootstrapping）：MC学习不使用自举，因为它可以直接估计状态/动作值，而无需初始猜测。
低估计方差（Low estimation variance）：TD的估计方差低于MC，因为它涉及的随机变量更少。例如，为了估计动作值 $q_{\pi }(s_t,a_t)$，Sarsa仅需三个随机变量的样本：$R_{t+1},S_{t+1},A_{t+1}$。	高估计方差（High estimation variance）：MC的估计方差更高，因为涉及许多随机变量。例如，为了估计 $q_{\pi }(s_t,a_t)$，我们需要样本 $R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots$。假设每个回合的长度为 $L$，且每个状态的动作数量为 $\Vert \mathcal{A}\Vert$，那么在软策略下，有 $\Vert \mathcal{A}{\Vert }^L$ 种可能的回合。如果仅用少数几个回合来估计，估计方差自然会很高。
TD 算法的成立性证明见课本。

但是只有价值函数没法在 model free 的环境中指导动作选择，需要获得状态动作价值函数 $q(s,a)$ 才可以，把 TD 算法自然外推，为了实现自举，需要 $\left(s_t,a_t,r_{t+1},s_{t+1},a_{t+1}\right)$ 这几个状态值，前四个都很好求，都是可以直接由状态或模型得到的，但是最后一个 $a_{t+1}$ 这个下一步动作需要怎么求，这个问题衍生出两个算法，一是 Sarsa 算法，二是 Q-learning 算法。

Sarsa 算法

在 $a_{t+1}$ 如何求解这个问题上，Sarsa 算法决定使用模型给出的策略进行更新：

$$\begin{array}{l}{q}_{t+1}(s_t,a_t)=q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)[q_t(s_t,a_t)-(r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})],\\ q_{t+1}(s,a)=q_t(s,a),\mathrm{for}\mathrm{all}(s,a)\ne (s_t,a_t),\end{array}$$

同 TD algo 一样，$Sarsa$ 是 Bellman 方程的随机近似：

$$q_{\pi }(s,a)=\mathbb{E}\left[R+\gamma q_{\pi }(S^{\prime },A^{\prime })|s,a\right],\mathrm{for}\mathrm{all}\left(s,a\right).$$

之所以要叫 $Sarsa$ 算法是因为这个算法需要 $\left(s_t,a_t,r_{t+1},s_{t+1},a_{t+1}\right)$ 这几个状态值。

$$\begin{array}{l}\text{Algorithm 7.1: Optimal policy learning by Sarsa}\\ \\ \text{Initialization: }{\alpha }_t(s,a)=\alpha >0\text{ for all }(s,a)\text{ and all }t.ϵ\in (0,1).\text{ Initial }{q}_0(s,a)\text{ for all }(s,a).\\ \text{ Initial }ϵ\text{-greedy policy }{\pi }_0\text{ derived from }{q}_0.\\ \\ \text{Goal: }\text{Learn an optimal policy that can lead the agent to the target state from an initial state }{s}_0.\\ \\ \text{For each episode, do}\\ \text{Generate }{a}_0\text{ at }{s}_0\text{ following }{\pi }_0(s_0)\\ \text{If }{s}_t(t=0,1,2,\dots )\text{ is not the target state, do}\\ \text{Collect an experience sample }(r_{t+1},s_{t+1},a_{t+1})\text{ given }(s_t,a_t):\text{ generate }{r}_{t+1},s_{t+1}\\ \text{by interacting with the environment; generate }{a}_{t+1}\text{ following }{\pi }_t(s_{t+1}).\\ \text{Update }q\text{-value for }(s_t,a_t):\\ q_{t+1}(s_t,a_t)=q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)\left[q_t(s_t,a_t)-(r_{t+1}+\gamma q_t(s_{t+1},a_{t+1}))\right]\\ \text{Update policy for }{s}_t:\\ {\pi }_{t+1}(a|s_t)=1-\frac{ϵ}{|\mathcal{A}(s_t)|}(|\mathcal{A}(s_t)|-1)\text{if }a=\arg {\max }_a{q}_{t+1}(s_t,a)\\ {\pi }_{t+1}(a|s_t)=\frac{ϵ}{|\mathcal{A}(s_t)|}\text{otherwise}\\ s_t\leftarrow s_{t+1},a_t\leftarrow a_{t+1}\end{array}$$

可以在书上 P.136 查看例子。

TD learning 可以增大采样深度，即不止依赖下一步的回报值，而是依赖多步的回报：

$$\begin{array}{rl}{q}_{t+n}(s_t,a_t)& =q_{t+n-1}(s_t,a_t)\\ & -{\alpha }_{t+n-1}(s_t,a_t)[q_{t+n-1}(s_t,a_t)-(r_{t+1}+\gamma r_{t+2}+\cdots +{\gamma }^n{q}_{t+n-1}(s_{t+n},a_{t+n})\left)\right].\end{array}$$

这个方法兼采了 MC 方法和 TD 方法的特点，n 愈大，算法愈趋向于 MC 算法，方差大但是 bias 小。 可以看到有几步奖励函数掉的非常厉害，这是因为 $ϵ$-Greedy 选取了次优的动作，导致走向一个很差的轨迹。

Q-learning

同时，为了下一步 $a_{t+1}$ 如何求解上， Q-learning 选择直接使用 $s_{t+1}$ 这个状态空间的 $q$ 值最高的动作：

$$\begin{array}{rl}{q}_{t+1}(s_t,a_t)& =q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)\left[q_t(s_t,a_t)-\left(r_{t+1}+\gamma \underset{a\in \mathcal{A}(s_{t+1})}{\max }{q}_t(s_{t+1},a)\right)\right],\\ q_{t+1}(s,a)& =q_t(s,a),\mathrm{for}\mathrm{all}(s,a)\ne (s_t,a_t),\end{array}$$

这个迭代方式其实是求下列方程的随机近似过程：

$$q(s,a)=\mathbb{E}\left[R_{t+1}+\gamma \underset{a}{\max }q(S_{t+1},a)|S_t=s,A_t=a\right].$$

可以看到 Sarsa 算法依赖自己这个策略来更新，而 Q-learning 单纯使用下一步中的动作空间中状态动作奖励值最大的动作。这实际上是 On-policy 和 Off-policy 的差异。

任何 RL agent 都同时涉及两个策略：行为策略（behavior policy） $\mu$ — 用来和环境交互、产生数据的策略；目标策略（target policy） $\pi$ — 你真正想学/想评估的策略。

On-policy（SARSA）：$\mu =\pi$

行为策略和目标策略是同一个。你用 $ϵ$-greedy 探索，你评估的也是这个 $ϵ$-greedy 策略的 $q_{\pi }$。所以 SARSA 的更新里用 $a_{t+1}$ 是完全自洽的 — $a_{t+1}$ 是从 $\pi$ 采样的，而你要学的就是 $\pi$ 的价值。

这带来一个后果：每次你改进策略（比如降低 $ϵ$），之前收集的数据就”过时”了，因为那些数据是旧策略产生的。所以 on-policy 算法通常不能复用历史数据，sample efficiency 比较差。并且这个 动作状态奖励值是使用 $ϵ$-Greedy 探索而来的，带有一定探索带来的负担，不一定是最佳的。

Off-policy（Q-learning）：$\mu \ne \pi$

行为策略和目标策略是分开的。你可以用任意策略 $\mu$（比如 $ϵ$-greedy，甚至纯随机）来探索，但你学的是贪心最优策略 ${\pi }_{\ast }=\arg {\max }_{a}q(s,a)$ 的价值。

Q-learning 能做到这一点，关键就在 $\max$ 操作。它在算 target 的时候完全不看 $\mu$ 实际选了什么 $a_{t+1}$，直接取 $\max$，相当于隐式地把目标策略定义为贪心策略。所以不管数据是谁产生的，target 的计算都和行为策略无关。

最根本的原因是： Q-learning 求解的是 BoE 的最优解，而 Sarsa 求解的是一个给定策略的 贝尔曼方程。

另外不要和 online/offline 弄混了，这个指的是更新策略的时机。这两个算法都是 online 的算法。

$$\begin{array}{l}\text{Algorithm 7.2: Optimal policy learning via Q-learning (on-policy version)}\\ \\ \text{Initialization: }{\alpha }_t(s,a)=\alpha >0\text{ for all }(s,a)\text{ and all }t.ϵ\in (0,1).\text{ Initial }{q}_0(s,a)\text{ for all }(s,a).\\ \text{ Initial }ϵ\text{-greedy policy }{\pi }_0\text{ derived from }{q}_0.\\ \\ \text{Goal: }\text{Learn an optimal path that can lead the agent to the target state from an initial state }{s}_0.\\ \\ \text{For each episode, do}\\ \text{If }{s}_t(t=0,1,2,\dots )\text{ is not the target state, do}\\ \text{Collect the experience sample }(a_t,r_{t+1},s_{t+1})\text{ given }{s}_t:\text{ generate }{a}_t\text{ following }{\pi }_t(s_t);\\ \text{generate }{r}_{t+1},s_{t+1}\text{ by interacting with the environment.}\\ \text{Update }q\text{-value for }(s_t,a_t):\\ q_{t+1}(s_t,a_t)=q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)\left[q_t(s_t,a_t)-(r_{t+1}+\gamma {\max }_a{q}_t(s_{t+1},a))\right]\\ \text{Update policy for }{s}_t:\\ {\pi }_{t+1}(a|s_t)=1-\frac{ϵ}{|\mathcal{A}(s_t)|}(|\mathcal{A}(s_t)|-1)\text{if }a=\arg {\max }_a{q}_{t+1}(s_t,a)\\ {\pi }_{t+1}(a|s_t)=\frac{ϵ}{|\mathcal{A}(s_t)|}\text{otherwise}\end{array}$$ $$\begin{array}{l}\text{Algorithm 7.3: Optimal policy learning via Q-learning (off-policy version)}\\ \\ \text{Initialization: }\text{Initial guess }{q}_0(s,a)\text{ for all }(s,a).\text{ Behavior policy }{\pi }_b(a|s)\text{ for all }(s,a).\\ {\alpha }_t(s,a)=\alpha >0\text{ for all }(s,a)\text{ and all }t.\\ \\ \text{Goal: }\text{Learn an optimal target policy }{\pi }_T\text{ for all states from the experience samples generated by }{\pi }_b.\\ \\ \text{For each episode }\{s_0,a_0,r_1,s_1,a_1,r_2,\dots \}\text{ generated by }{\pi }_b,\text{ do}\\ \text{For each step }t=0,1,2,\dots \text{ of the episode, do}\\ \text{Update }q\text{-value for }(s_t,a_t):\\ q_{t+1}(s_t,a_t)=q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)\left[q_t(s_t,a_t)-(r_{t+1}+\gamma {\max }_a{q}_t(s_{t+1},a))\right]\\ \text{Update target policy for }{s}_t:\\ {\pi }_{T,t+1}(a|s_t)=1\text{if }a=\arg {\max }_a{q}_{t+1}(s_t,a)\\ {\pi }_{T,t+1}(a|s_t)=0\text{otherwise}\end{array}$$

可以看到 Q-learning 没有陡峭的奖励曲线崩溃，不像 Sarsa，它求得是动作空间中的最优值。

Algorithm	Expression of the TD target ${\bar{q}}_t$ in (7.20)
Sarsa	${\bar{q}}_t=r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})$
$n$-step Sarsa	${\bar{q}}_t=r_{t+1}+\gamma r_{t+2}+\cdots +{\gamma }^n{q}_t(s_{t+n},a_{t+n})$
Q-learning	${\bar{q}}_t=r_{t+1}+\gamma {\max }_a{q}_t(s_{t+1},a)$
Monte Carlo	${\bar{q}}_t=r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+\cdots$

Algorithm	Equation to be solved
Sarsa	BE: $q_{\pi }(s,a)=\mathbb{E}[R_{t+1}+\gamma q_{\pi }(S_{t+1},A_{t+1})\mid S_t=s,A_t=a]$
$n$-step Sarsa	BE: $q_{\pi }(s,a)=\mathbb{E}[R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^n{q}_{\pi }(S_{t+n},A_{t+n})\mid S_t=s,A_t=a]$
Q-learning	BOE: $q(s,a)=\mathbb{E}[R_{t+1}+\gamma {\max }_{a}q(S_{t+1},a)\mid S_t=s,A_t=a]$
Monte Carlo	BE: $q_{\pi }(s,a)=\mathbb{E}[R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots \mid S_t=s,A_t=a]$