【强化学习入门笔记】 2.5 Sarsa和Q-learning

本系列为学习赵世钰老师的《强化学习的数学原理》所作的学习笔记.

2.5.1 Sarsa系列

之前介绍的时序差分算法是用来计算给定策略$\pi$和其状态$s$的状态值期望$v_{\pi }(s)$, 那么能不能直接估计动作值期望呢? 这也就是Sarsa方法.

2.5.1.1 Sarsa

给定策略$\pi$, 我们可以用以下算法估计动作值:

$$q_{t+1}\left(s_t,a_t\right)=q_t\left(s_t,a_t\right)-{\alpha }_t\left(s_t,a_t\right)\left[q_t\left(s_t,a_t\right)-\left(r_{t+1}+\gamma q_t\left(s_{t+1},a_{t+1}\right)\right)\right],$$

这就是Sarsa算法, 它的名字来源于上式的输入: $\left(s_t,a_t,r_{t+1},s_{t+1},a_{t+1}\right)$.

实际上, Sarsa算法是一种随机近似方法, 用于求解使用动作值表达的贝尔曼公式:

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

2.5.1.2 Expected Sarsa

如果将TD目标改成期望, 就是Expected Sarsa:

$$q_{t+1}\left(s_t,a_t\right)=q_t\left(s_t,a_t\right)-{\alpha }_t\left(s_t,a_t\right)\left[q_t\left(s_t,a_t\right)-\left(r_{t+1}+\gamma \mathbb{E}\left[q_t\left(s_{t+1},A\right)\right]\right)\right]$$

其中TD目标项中的期望定义为:

$$\mathbb{E}\left[q_t\left(s_{t+1},A\right)\right]=\sum _a{\pi }_t\left(a\mid s_{t+1}\right)q_t\left(s_{t+1},a\right)\doteq v_t\left(s_{t+1}\right)$$

Sarsa中只计算一个$a_{t+1}$带来的动作值$q_t(s_{t+1},a_{t+1})$, Expected Sarsa完整的计算了状态值$v_t\left(s_{t+1}\right)$

同样, Expected Sarsa也是计算一个贝尔曼公式:

$$\begin{gathered} q_{\pi }(s,a)=\mathbb{E}\left[R_{t+1}+\gamma \mathbb{E}\left[q_{\pi }\left(S_{t+1},A_{t+1}\right)\mid S_{t+1}\right]\mid S_t=s,A_t=a\right], \\ \text{ for all }s,a. \end{gathered}$$

其中的期望可以展开成:

$$\mathbb{E}\left[q_{\pi }\left(S_{t+1},A_{t+1}\right)\mid S_{t+1}\right]=\sum _{A^{\prime }}{q}_{\pi }\left(S_{t+1},A^{\prime }\right)\pi \left(A^{\prime }\mid S_{t+1}\right)=v_{\pi }\left(S_{t+1}\right)$$

2.5.1.3 n-step Sarsa

我们回顾一下动作值的定义, 给定状态和动作时, 轨迹$G_t$期望:

$$q_{\pi }(s,a)=\mathbb{E}\left[G_t\mid S_t=s,A_t=a\right]$$

其中$G_t$是指轨迹的discounted return, 定义为:

$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots$$

如果我们额外定义一个上标$n$, 第$n$步时用动作值$q_{\pi }(S_{t+n},A_{t+n})$替代表达式:

$$G_t^{(n)}=R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^n{q}_{\pi }\left(S_{t+n},A_{t+n}\right),$$

• $n=1$时: Sarsa

动作值期望可以写成:

$$q_{\pi }(s,a)=\mathbb{E}\left[G_t^{(1)}\mid s,a\right]=\mathbb{E}\left[R_{t+1}+\gamma q_{\pi }\left(S_{t+1},A_{t+1}\right)\mid s,a\right].$$

随机近似理论求解上式的更新公式为:

$$q_{t+1}\left(s_t,a_t\right)=q_t\left(s_t,a_t\right)-{\alpha }_t\left(s_t,a_t\right)\left[q_t\left(s_t,a_t\right)-\left(r_{t+1}+\gamma q_t\left(s_{t+1},a_{t+1}\right)\right)\right],$$

显然这就是Sarsa算法求解的目标贝尔曼公式

• $n=\infty$时: MC learning

动作值期望可以写成:

$$q_{\pi }(s,a)=\mathbb{E}\left[G_t^{(\infty )}\mid s,a\right]=\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots \mid s,a\right].$$

求解上式的更新公式为:

$$q_{t+1}\left(s_t,a_t\right)=g_t\doteq r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+\dots ,$$

$g_t$是$G_t$的采样, 这实际就是蒙特卡洛方法

• $n=k$时: n-step Sarsa

当我们采用一个这种的固定值$k$时:

$$q_{\pi }(s,a)=\mathbb{E}\left[G_t^{(n)}\mid s,a\right]=\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^n{q}_{\pi }\left(S_{t+n},A_{t+n}\right)\mid s,a\right].$$

它的更新公式为:

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

这也就是n-step Sarsa方法.

不过需要说明的是, 不管$n$定义为多少, 它们的值都是一样的, 只是写法不同:

$$G_t=G_t^{(1)}=G_t^{(2)}=G_t^{(n)}=G_t^{(\infty )}$$

2.5.2 Q-learning

2.5.2.1 定义

Q-learning的更新公式为:

$$q_{t+1}\left(s_t,a_t\right)=q_t\left(s_t,a_t\right)-{\alpha }_t\left(s_t,a_t\right)\left[q_t\left(s_t,a_t\right)-\left(r_{t+1}+\gamma \underset{a\in \mathcal{A}\left(s_{t+1}\right)}{\max }{q}_t\left(s_{t+1},a\right)\right)\right]$$

只有TD目标项有变化, 它不再是Sarsa中的给定动作的动作值: $q_t\left(s_{t+1},a_{t+1}\right)$, 或者是expected Sarsa中的动作值的期望: $\mathbb{E}\left[q_t\left(s_{t+1},A\right)\right]$.

而是最优动作的动作值: ${\max }_{a\in \mathcal{A}\left(s_{t+1}\right)}{q}_t\left(s_{t+1},a\right)$, 同样它也是一个随机近似方法, 要求解的方程为:

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

2.5.2.2 On-policy 和 Off-policy

首先我们定义两个策略概念:

• behavior policy: 行为策略, 用来生成经验样本的策略。
• target policy: 目标策略, 不断更新以趋于最优策略的策略。

当行为策略和目标策略相同时, 这种学习过程称为在on-policy学习(Sarsa, MC learning);

当行为策略和目标策略可以不同(也可以相同)时, 这种学习过程称为在off-policy学习(Q-learning);

On-policy版本的Q-learning算法如上图, 它的策略即用来获取经验数据, 也用来更新策略. 因此它是On-policy的.

上图是Off-policy的Q-learning算法, 它的行为策略${\pi }_b(a\mid s)$是一开始给定的, 会基于${\pi }_b(a\mid s)$获取经验数据. 而更新策略${\pi }_{T,t+1}\left(a\mid s_t\right)$时, 并不更新行为策略, 因此是Off-policy的.

2.5.2.3 例子

我们给出这样一个例子, 假设我们已经知道了它的最优策略(a)和最优状态值分布(b)

并且我们给出一个均匀的行为策略©和它对应的采样结果(d)

当我们使用Q-learning求解时, 结果非常接近真实的最优解, 过程数据如图.

但是当行为策略并不均匀时, 求解质量会变差:

2.5.3 TD算法总结

所有的TD算法实际上, 都是如下的更新形式:

$$q_{t+1}\left(s_t,a_t\right)=q_t\left(s_t,a_t\right)-{\alpha }_t\left(s_t,a_t\right)\left[q_t\left(s_t,a_t\right)-{\bar{q}}_t\right]$$

区别在于, 它们的更新的TD目标${\bar{q}}_t$不一样:

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

以及它们对应的求解目标公式:

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