David silver 强化学习 Lecture 5

课程主页：https://www.davidsilver.uk/teaching/

这里回顾David silver 强化学习 Lecture 5的课程内容，这一讲简单介绍了不基于模型的控制。

介绍

上一讲介绍不基于模型的预测，即对未知的MDP预测其价值函数；这一讲介绍不基于模型的控制，即对于未知的MDP优化其价值函数。

On-Policy Monte-Carlo Control

• 关于$V(s)$做策略提升需要MDP模型：

  $$\pi^{\prime}(s)=\underset{a \in \mathcal{A}}{\operatorname{argmax}} \mathcal{R}_{s}^{a}+\mathcal{P}_{s s^{\prime}}^{a} V\left(s^{\prime}\right)$$

• 关于$Q(s,a)$做策略提升不需要模型

  $$\pi^{\prime}(s)=\underset{a \in \mathcal{A}}{\operatorname{argmax}} Q(s, a)$$

$\epsilon-$贪婪搜索

这里老师举了一个例子：

• 有两扇门在我们面前
• 打开左门得到$0$奖励，$V(\text{left})=0$
• 打开右门得到$+1$奖励，$V(\text{right})=+1$
• 打开右门得到$+3$奖励，$V(\text{right})=+2$
• 打开右门得到$+2$奖励，$V(\text{right})=+2$
• 我们是否选择了最好的门呢?

上述问题的答案显然是否定的，但是如果按照通常的方法则会一直选右门，为了解决这个问题，可以使用$\epsilon-$贪婪搜索：

• $\epsilon-$贪婪搜索是确保连续搜索的最简单方法
• 思路是以非零概率尝试所有$m$个动作
• 以$1-\epsilon$的概率选择贪婪动作
• 有$\epsilon$的概率随机选择一个动作

$$\pi(a | s)=\left\{\begin{array}{ll}{\epsilon / m+1-\epsilon} & {\text { if } a^{*}=\underset{a \in \mathcal{A}}{\operatorname{argmax}} Q(s, a)} \\ {\epsilon / m} & {\text { otherwise }}\end{array}\right.$$

$\epsilon-$贪婪策略提升

关于$\epsilon-$贪婪搜索有如下定理：

定理

对于任意$\epsilon-$贪婪策略$\pi$，关于$q_\pi$的$\epsilon-$贪婪策略$\pi ‘$是一个提升，$v_{\pi^{\prime}}(s) \geq v_{\pi}(s)$

证明：

$$\begin{aligned} q_{\pi}\left(s, \pi^{\prime}(s)\right) &=\sum_{a \in \mathcal{A}} \pi^{\prime}(a | s) q_{\pi}(s, a) \\ &=\epsilon / m \sum_{a \in \mathcal{A}} q_{\pi}(s, a)+(1-\epsilon) \max _{a \in \mathcal{A}} q_{\pi}(s, a) \\ & \geq \epsilon / m \sum_{a \in \mathcal{A}} q_{\pi}(s, a)+(1-\epsilon) \sum_{a \in \mathcal{A}} \frac{\pi(a | s)-\epsilon / m}{1-\epsilon} q_{\pi}(s, a) \\ &=\sum_{a \in \mathcal{A}} \pi(a | s) q_{\pi}(s, a)=v_{\pi}(s) \end{aligned}$$

其中不等号是因为最大值大于等于所有值的加权和。

由上式可得

$$v_{\pi^{\prime}}(s) \geq v_{\pi}(s)$$

GLIE

GLIE的全称为Greedy in the Limit with Infinite Exploration

• 所有状态-动作对都经过了无数次探索，

  $$\lim _{k \rightarrow \infty} N_{k}(s, a)=\infty$$

• 策略收敛到贪婪策略

  $$\lim _{k \rightarrow \infty} \pi_{k}(a | s)=1\left(a=\underset{a^{\prime} \in \mathcal{A}}{\operatorname{argmax}} Q_{k}\left(s, a^{\prime}\right)\right)$$

例如，$\epsilon-$贪婪是GLIE如果$\epsilon_k =\frac 1 k$

GLIE MC控制

• 利用$\pi:\left\{S_{1}, A_{1}, R_{2}, \ldots, S_{T}\right\} \sim \pi$采样$k$幕

• 在每一幕中，对每个状态$S_t$和动作$A_t$，

  $$\begin{array}{l}{N\left(S_{t}, A_{t}\right) \leftarrow N\left(S_{t}, A_{t}\right)+1} \\ {Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\frac{1}{N\left(S_{t}, A_{t}\right)}\left(G_{t}-Q\left(S_{t}, A_{t}\right)\right)}\end{array}$$

• 基于新的动作价值函数改进策略

  $$\begin{array}{l}{\epsilon \leftarrow 1 / k} \\ {\pi \leftarrow \epsilon-g \operatorname{reed} y(Q)}\end{array}$$

上述方法的有效性由如下定理保证：

定理

GLIE MC收敛到最优动作价值函数，$Q(s, a) \rightarrow q_{*}(s, a)$

On-Policy Temporal-Difference Learning

• 自然的想法：在我们的循环中使用TD而不是MC
  • 将TD应用于$Q(S, A)$
  • 使用$\epsilon-$贪婪策略提升
  • 实时更新

$\text{Sarsa}(\lambda)$

一个具体例子是$\text{Sarsa}(\lambda)$，思路如下：

$$Q(S, A) \leftarrow Q(S, A)+\alpha\left(R+\gamma Q\left(S^{\prime}, A^{\prime}\right)-Q(S, A)\right)$$

伪代码为：

Sarsa的收敛性

Sarsa的收敛性由如下定理保证：

定理

Sarsa在如下条件下收敛到最优动作价值函数$Q(s, a) \rightarrow q_{*}(s, a)$

• 策略$\pi_t(a|s)$是GLIE序列

• 步长大小$\alpha_t$满足：

  $$\begin{array}{l}{\sum_{t=1}^{\infty} \alpha_{t}=\infty} \\ {\sum_{t=1}^{\infty} \alpha_{t}^{2}<\infty}\end{array}$$

$n$步Sarsa

• 考虑如下$n$步回报：

  $$\begin{aligned}{n=1} &&(\text{Sarsa}) &&G_{t}^{(1)}=R_{t+1}+\gamma Q\left(S_{t+1}\right) \\ {n=2} && &&{G_{t}^{(2)}=R_{t+1}+\gamma R_{t+2}+\gamma^{2} Q\left(S_{t+2}\right)} \\{\vdots} && &&{\vdots} \\ {n=\infty} && (\text{MC}) && G_{t}^{(\infty)}=R_{t+1}+\gamma R_{t+2}+\ldots+\gamma^{T-1} R_{T}\end{aligned}$$

• 定义$n$步回报

  $$G_{t}^{(n)}=R_{t+1}+\gamma R_{t+2}+\ldots+\gamma^{n-1} R_{t+n}+\gamma^{n} Q\left(S_{t+n}\right)$$

• $n$步Sarsa根据$n$步Q回报更新$Q(s,a)$

  $$Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha\left(q_{t}^{(n)}-Q\left(S_{t}, A_{t}\right)\right)$$

$\text{Sarsa}(\lambda)$的前向视角

$\text{Sarsa}(\lambda)$和$\text{TD}(\lambda)$的思路一致，可以用下图表示：

• $q^{\lambda}$回报结合了所有$n$步$Q$回报$q_t^{(n)}$

• 使用权重$(1-\lambda) \lambda^{n-1}$

  $$q_{t}^{\lambda}=(1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} q_{t}^{(n)}$$

• $\text{Sarsa}(\lambda)$的前向视角（Forward-view）

  $$Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha\left(q_{t}^{\lambda}-Q\left(S_{t}, A_{t}\right)\right)$$

$\text{Sarsa}(\lambda)$的反向视角

• 类似$\text{TD}(\lambda)$，首先定义合格轨迹：

$$\begin{array}{l}{E_{0}(s)=0} \\ {E_{t}(s)=\gamma \lambda E_{t-1}(s)+\mathbf{1}\left(S_{t}=s,A_t=a\right)}\end{array}$$

• 对于每个状态$s$和动作$a$更新$Q(s,a)$

• 更新项正比于TD-误差$\delta_t$和合格轨迹$E_t(s,a)$

  $$\begin{aligned} \delta_{t} &=R_{t+1}+\gamma Q\left(S_{t+1}, A_{t+1}\right)-Q\left(S_{t}, A_{t}\right) \\ Q(s, a) & \leftarrow Q(s, a)+\alpha \delta_{t} E_{t}(s, a) \end{aligned}$$

$\text{Sarsa}(\lambda)$算法

Off-Policy Learning

• 在遵循策略$\mu(a|s)$

  $$\left\{S_{1}, A_{1}, R_{2}, \ldots, S_{T}\right\} \sim \mu$$

  的条件下，通过评估目标策略$\pi(a|s)$以计算$v_\pi(s)$或$q_\pi(s,a)$

• 为什么这很重要？

  • 通过观察人类或其他智能体学习
  • 重用旧策略$\pi_{1}, \pi_{2}, \ldots, \pi_{t-1}$带来的经验
  • 在遵循探索性策略的同时学习最佳策略
  • 遵循一项策略时了解多种策略

重要性抽样

$$\begin{aligned} \mathbb{E}_{X \sim P}[f(X)] &=\sum P(X) f(X) \\ &=\sum Q(X) \frac{P(X)}{Q(X)} f(X) \\ &=\mathbb{E}_{X \sim Q}\left[\frac{P(X)}{Q(X)} f(X)\right] \end{aligned}$$

Off-Policy MC的重要性抽样

• 通过$\mu$的回报评估$\pi$

• 根据策略之间的相似性得出权重回报$G_t$

• 在整个幕中乘以重要性抽样校正

  $$G_{t}^{\pi / \mu}=\frac{\pi\left(A_{t} | S_{t}\right)}{\mu\left(A_{t} | S_{t}\right)} \frac{\pi\left(A_{t+1} | S_{t+1}\right)}{\mu\left(A_{t+1} | S_{t+1}\right)} \cdots \frac{\pi\left(A_{T} | S_{T}\right)}{\mu\left(A_{T} | S_{T}\right)} G_{t}$$

• 根据校正回报更新价值

  $$V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(G_{t}^{\pi / \mu}-V\left(S_{t}\right)\right)$$

• 当$\pi$是非零但$\mu$是零时无法使用

• 重要性抽样可以大幅减少方差

Off-Policy TD的重要性抽样

• 使用$\mu$生成的TD目标来评估$\pi$

• 通过重要性抽样加权TD目标$R+\gamma V\left(S^{\prime}\right)$

• 只需要一次重要性抽样校正

  $$\begin{aligned} V\left(S_{t}\right) & \leftarrow V\left(S_{t}\right)+ \alpha\left(\frac{\pi\left(A_{t} | S_{t}\right)}{\mu\left(A_{t} | S_{t}\right)}\left(R_{t+1}+\gamma V\left(S_{t+1}\right)\right)-V\left(S_{t}\right)\right) \end{aligned}$$

• 比MC重要性抽样的方差小很多

• 策略只需要在一步中相似

Q-Learning

• 现在我们考行Off-Policy的动作价值$Q(s,a)$的学习

• 不需要重要性抽样

• 下一个动作根据行为策略选择$A_{t+1} \sim \mu\left(\cdot | S_{t}\right)$

• 但是我们考虑替代性的后续动作$A^{\prime} \sim \pi\left(\cdot | S_{t}\right)$

• 并将$Q\left(S_{t}, A_{t}\right)$更新为替代动作的价值

  $$Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha\left(R_{t+1}+\gamma Q\left(S_{t+1}, A^{\prime}\right)-Q\left(S_{t}, A_{t}\right)\right)$$

使用Q-Learning进行Off-Policy控制

• 现在，我们允许动作和目标策略都得到提升

• 目标策略关于$Q(s,a)$贪心

  $$\pi\left(S_{t+1}\right)=\underset{a^{\prime}}{\operatorname{argmax}} Q\left(S_{t+1}, a^{\prime}\right)$$

• 行为策略$\mu$关于$Q(s,a)$是$\epsilon -$贪心

• 那么Q-Learning的目标得到化简：

  $$\begin{aligned} & R_{t+1}+\gamma Q\left(S_{t+1}, A^{\prime}\right) \\=& R_{t+1}+\gamma Q\left(S_{t+1}, \underset{a}{\arg \max } Q\left(S_{t+1}, a^{\prime}\right)\right) \\=& R_{t+1}+\max _{a^{\prime}} \gamma Q\left(S_{t+1}, a^{\prime}\right) \end{aligned}$$

Q-Learning控制算法

根据之前讨论得到如下算法：

$$Q(S, A) \leftarrow Q(S, A)+\alpha\left(R+\gamma \max _{a^{\prime}} Q\left(S^{\prime}, a^{\prime}\right)-Q(S, A)\right)$$

上述算法的有效性由如下定理保证：

定理

Q-learning控制收敛到最优动作价值函数：$Q(s, a) \rightarrow q_{*}(s, a)$

完整算法的伪代码如下：

总结

DP和TD的关系