动手学强化学习

写在前面：

本文采用的教程为【强化学习的数学原理】课程：从零开始到透彻理解（完结）_哔哩哔哩_bilibili

参考书籍为《动手学强化学习》俞勇著

感谢上述作者做出的贡献

两种人工智能任务类型

预测型任务

• 根据数据预测所需输出 （有监督学习）
• 生成数据实例 （无监督学习）

决策型任务

• 在动态环境中采取动作（强化学习）
• 转变到新的状态
• 获得即时奖励
• 随着时间得推移最大化累计奖励

决策智能的任务和技术分类

上图框出来的任务部分，我们称它们为序贯决策任务

序贯决策

在序贯决策中，智能体序贯地做出一个个决策，并接续看到新的观测，直到最终任务结束

基本概念

强化学习的定义：智能体通过从交互中学习来实现目标的计算方法

下面介绍一些强化学习过程中的基本概念，后面会经常提到这些概念，本文用一个9*9的网格来作为表述这些概念

agent ：智能体，即当前环境下强化学习的对象

State：当前环境下智能体所处的状态，本文用$S_i$表示每一种不同的状态

State Space： 将所有状态放在一起的一个集合 $S={\left\{S_i\right\}}_{i=1}^9$

Action：每种状态下的一系列的可采取得行动，本文用$a_i$表示每一种行动状态

State Transition：在$S_1$状态下 ，进行动作$a_2$,然后下一个状态是什么

$$S_1\stackrel{a_1}{⟶}{S}_2$$

Forbidden area：禁止进入区，$e.g：$在$S_5$状态下 ，进行动作$a_2$,然后下一个状态是什么

$$S_5\stackrel{a_2}{⟶}{S}_6$$

$S_6$为禁止进入区，本文设置并非物理意义上的不可进入，不过进入时会遭受惩罚

Policy：告诉智能体当前状态应进行哪一种行动

Reward：在智能体采取一个动作后得到的一个标量，这个数是正数，代表鼓励这种行为的发生，这个数是负数，代表惩罚，即不希望这种行为发生

注：reward一定依赖于当前的状态和动作

trajectory：状态-动作-奖励链

return：一个trajectory结束后中间会有各种各样的reward，我们对reward求和，得到的返回结果称为return，return是策略好坏的一个评估标准

dicounted reurn（折扣回报）：

引入：

上图中的trajectory是无限长的，在$s_9$会无限循环，此时的return为

$$return=0+0+0+1+1+1+...=\mathrm{\infty }$$

此时的return数列是发散的无法具体计算出它的值，我们如何使它变得收敛呢？

此时我们引入一个新的变量 discount rate（折扣因子） $\gamma \in [0,1)$

将discounted rate和return相结合我们就得到了discounted return（折扣回报）

$$\begin{array}{rl}\text{ discounted return }& =0+\gamma 0+{\gamma }^{2}0+{\gamma }^{3}1+{\gamma }^{4}1+{\gamma }^{5}1+\dots \\ & ={\gamma }^3(1+\gamma +{\gamma }^2+\dots )={\gamma }^3\frac{1}{1-\gamma }\end{array}$$

discounted return的作用

• 使之前发散的return成功收敛
• 能够平衡更远未来和更近未来的reward

Episode：智能体从开始执行任务，根据每个时刻的状态和对应的策略，依次选取一系列动作，直至任务终止的一个完整过程

一个episode通常包括以下几个部分

Initial State（初始状态）：agent从某个初始状态开始。

actions（动作）：agent根据当前的状态选择一个动作。

State Transitions（状态转移）：环境根据agent的动作更新状态。

Rewards（奖励）：环境根据agent的动作和新状态给予智能体一个奖励信号。

Terminal State（终止状态）：一个episode在agent达到终止状态或满足预设的终止条件时结束。例如，游戏结束或达到最大步数限制。

马尔可夫决策过程（MDP）

1.能够检测到理想的状态

2.可以多次尝试

3.系统的下个状态只与当前的状态信息有关，而与更早之前的状态无关，在决策过程中还和当前采取的动作有关

贝尔曼公式（Bellman Equation）

引入

分别计算下面一组图中三种不同policy的return

policy 1

policy 2

policy 3

注：return是指一个trajectory结束后的返回，在policy3中已经出现了两个trajectory，并对其求解了average，return3更像是下文所介绍的state value

如果是一个无限循环的trajectory，如何计算return呢

根据上述过程我们可以发现$v_{i+1}$的值总是依赖于上一个$v_i$,也就是当前的估计值，这个方法叫做bootstrapping（从自身出发不断迭代的过程），我们具体如何求出$v_i$的值呢？

我们把上面的式子写成矩阵的形式

$$\underset{\mathbf{v}}{\underbrace{\left[\begin{array}{l}{v}_1\\ v_2\\ v_3\\ v_4\end{array}\right]}}=\left[\begin{array}{l}{r}_1\\ r_2\\ r_3\\ r_4\end{array}\right]+\left[\begin{array}{l}\gamma v_2\\ \gamma v_3\\ \gamma v_4\\ \gamma v_1\end{array}\right]=\underset{\mathbf{r}}{\underbrace{\left[\begin{array}{l}{r}_1\\ r_2\\ r_3\\ r_4\end{array}\right]}}+\gamma \underset{\mathbf{P}}{\underbrace{\left[\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\end{array}\right]}}\underset{\mathbf{v}}{\underbrace{\left[\begin{array}{l}{v}_1\\ v_2\\ v_3\\ v_4\end{array}\right]}}$$$$v=r+\gamma Pv$$

此公式就是贝尔曼公式的一般形式

State value

在介绍state value之前我们需要先引入一组概念

在得到单步的一个过程后，我们将其推广为一个多步的trajectory，并这个trajectory求解discounted return

基于如上定义，我们来给出state value的具体定义

state value实际上是对上文的discounted return（$G_t$）的expectation（期望值），我们用数学公式具体的定义state value function

注意区分return和state value：

return是指单个trajectory求reward和的过程，而state value是多个trajectory在所有不同概率下求得的return的expectation，前文在引入贝尔曼公式时，在policy 3中的return其实是state value形式，不过之前尚未对state value给出具体定义

推导贝尔曼公式

第一部分：

$$\begin{array}{rl}& \text{ 首先我们计算第一部分}\mathbb{E}[R_{t+1}\mid S_t=s]\text{ : }\\ & \begin{array}{rl}\mathbb{E}[R_{t+1}\mid S_t=s]& =\sum _a\pi (a\mid s)\mathbb{E}[R_{t+1}\mid S_t=s,A_t=a]\\ & =\sum _a\pi (a\mid s)\sum _{r}p(r\mid s,a)r\end{array}\end{array}$$

第二部分：

$$\begin{array}{rl}\mathbb{E}[G_{t+1}\mid S_t=s]& =\sum _{s^{\prime }}\mathbb{E}[G_{t+1}\mid S_t=s,S_{t+1}=s^{\prime }]p(s^{\prime }\mid s)\\ & =\sum _{s^{\prime }}\mathbb{E}[G_{t+1}\mid S_{t+1}=s^{\prime }]p(s^{\prime }\mid s)\\ & =\sum _{s^{\prime }}{v}_{\pi }\left(s^{\prime }\right)p(s^{\prime }\mid s)\\ & =\sum _{s^{\prime }}{v}_{\pi }\left(s^{\prime }\right)\sum _{a}p(s^{\prime }\mid s,a)\pi (a\mid s)\end{array}$$

将两项进行整合：

矩阵与向量形式

对上述式子进行化简

为了将贝尔曼方程写为矩阵形式，我们需要定义每个状态，我们将每种状态定义为$S_i$

对于$S_i$有贝尔曼公式

$$v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$$

假设我们当前有四种状态，$v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$可以用矩阵表达成

求解state value

给定一个policy，使用贝尔曼方程去求解这个state values的过程叫做policy evaluation（政策评估），这个过程是用来评估policy好坏的重要过程，求解中我们使用迭代的方法

$$v_k=r_{\pi }+\gamma P_{\pi }{v}_{k+1}$$

action value

state value：agent从一个状态出发所得到的average return

action value：agent从一个状态出发并进行一个action后所得到的average return

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

状态值函数 $v(s)$和动作值函数$q(s,a)$ 都是用来评估预期回报的工具。$v(s)$评估的是在某个状态下的长期收益，而动作值函数$q(s,a)$评估的是在某个状态下采取特定动作的长期收益。并且在特定策略（如贪婪策略）下，状态值等于所有动作值中的最大值。

贝尔曼最优公式

引入

最优策略（optimal policy）

前文提到state value可以用来衡量一个策略好还是不好，我们做如下定义

$$v_{\pi 1}(s)\ge v_{\pi 2}(s)foralls\in S$$

上述公式说明${\pi }_1$是比${\pi }_2$好的,我们进行推广后得到

一个策略${\pi }^{\ast }$相比其他任意一个策略$\pi$都好（state value比其他的都大），则说明这个${\pi }^{\ast }$是最理想的策略，也就是最优策略

由上述定义我们引出了如下问题

带着这个问题我们来探索贝尔曼最优公式

求解贝尔曼最优公式

$$v(s)=\sum _a\pi (a\mid s)(\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v\left(s^{\prime }\right)),\mathrm{\forall }s\in \mathcal{S}$$

我们对下面这个贝尔曼公式中的策略$\pi$进行改动，将最优问题嵌入贝尔曼公式我们可以得到

$$v(s)=\underset{\pi }{max}\sum _a\pi (a\mid s)(\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v\left(s^{\prime }\right)),\mathrm{\forall }s\in \mathcal{S}$$

此时的策略$\pi$不再是给定，而是需要求解的一个最优策略${\pi }^{\ast }$

为了方便求解${\pi }^{\ast }$，我们将贝尔曼最优公式写成向量-矩阵形式

$$v=\underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }v)$$

在这个式子中，有两个未知量（状态值$v$和策略$\pi$,对任意一个state都要求解出最优的一个$\pi$,我们如何进行求解呢？

有这样一个例子

无论 $x$的值是多少。这里需要让$2x-1-a^2$整体最大，所以$-a^2$就得取最小。因为$a^2$一定大于等于0，因此减去$a^2$的那个数想要最大，必须要让a最小，故$a=0$

运用上面这个例子的思想，我们可以固定$v(s^{\prime })$并求解$\pi$，即给出$v(s^{\prime })$的一个初始值，把初始值给定后,$v(s^{\prime })$变成已知的，即大括号内部可写成$q(s,a)$，它是已知的。下面要做的是把$\pi (a|s)$确定下来。

$$\begin{array}{rl}v(s)& =\underset{\pi }{max}\sum _a\pi (a\mid s)(\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v\left(s^{\prime }\right)),\mathrm{\forall }s\in \mathcal{S}\\ & =\underset{\pi }{max}\sum _a\pi (a\mid s)q(s,a)=\underset{\pi }{max}[\pi (a_1\mid s)q(s,a_1)+\cdots +\pi (a_5\mid s)q(s,a_5)]\\ & \doteq \underset{c_1,\dots ,c_5}{max}[c_{1}q(s,a_1)+\cdots +c_{5}q(s,a_5)],c_1+\cdots +c_5=1\end{array}$$

此时该问题转换为了一个线性规划问题

换句话说假设$q_3$是最大的，那么我们应该把更多的权重（$c_3$）放在$q_3$上，则我们对上述公式做如下化简

求出$\pi$后，我们可以将右边的式子看作自变量是$v$的一个函数，我们会得到一个非常简洁得式子

$$\begin{gathered} f(v):=\underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }v) \\ v=f(v) \end{gathered}$$

如何求解$v=f(v)$呢?

压缩映射定理（Contraction Mapping Theorem）

**不动点（Fixed point）：**点$x$属于集合$X$，$f$是一个映射（或者叫函数），如果满足 $f(x)=x$，则 $x$ 就被称为一个不动点，如何求解这个算法呢，下面给出了一个迭代式的算法

下面我们将压缩映射定理应用到求解贝尔曼最优公式中，我们可以得到：

解的最优性

我们成功求解了贝尔曼最优公式后，假设 $v^{\ast }$是贝尔曼最优方程的解,它满足：

$$v^{\ast }=\underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }{v}^{\ast })$$

我们假设

$${\pi }^{\ast }=\arg \underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }{v}^{\ast })$$

${\pi }^{\ast }$是对应$v^{\ast }$ 的一个最优的策略，也就是把$v^{\ast }$ 固定住，可以求解出来一个$\pi$，这个 $\pi$ 我们用${\pi }^{\ast }$ 来表示，那么把公式 2 代入公式 1，公式 1 可以化成下面的式子，也就是把前面的$\underset{\pi }{max}$去掉了，把它改成了${\pi }^{\ast }$

对于贝尔曼最优公式的解$v^{\ast }$，它是最大的state value，对于任何一个其他的$\pi$，所得到的state value都没有$v^{\ast }$大。那么相应的${\pi }^{\ast }$ 肯定是一个最优的策略，因为${\pi }^{\ast }$ 所对应的$v^{\ast }$就是$v_{\pi }^{\ast }$，它对应的state value达到最大。换句话说，贝尔曼最优公式描述了最优状态值（optimal state value）和最优策略（optimal policy）。

最优策略的一些性质

最优策略的决定因素有哪些

我们从上述贝尔曼最优公式中可以发现：

有三个量(红色)是我们已知的

• 奖励（reward）：$r$
• 概率（System model）：$p(s^{\prime }|s,a),p(r|s,a)$
• 折扣因子：$\gamma$

通过贝尔曼公式我们要求解的是量（黑色）：

• $v(s),v(s^{\prime }),\pi (a|s)$

换句话说，state value，policy的选择（黑色）其实取决于我们已知的三个量（红色），如：如何设计reward机制，怎么选择$\gamma$,系统模型应该是什么样的

下面来看这样一个例子：

如果我们改变$\gamma$的值，从$\gamma =0.9$变为$\gamma =0.5$,此时得到的reward如下图所示

我们发现随着$\gamma$的改变，optimal policy（最优策略）也随之改变，$\gamma$的降低，会让policy变得更为“短视”，换句话说，policy会更关注当前的状况而不是长远的状态。如果我们将$\gamma$降为0，会导致只会选择immediate reward

如果我们改变r，会发生什么变化？

Summary

对引入部分的问题，我们有了如下解答

值迭代与策略迭代算法

值迭代算法（value iteration algorithm）

引入

还记得我们是如何求解贝尔曼最优公式的吗

$$v=f(v)=\underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }v)$$

在上一讲中，我们使用收缩映射定理提出了一种迭代算法：只要用下面这个算法就可以求出它的最优策略（optimal policy）和最优的状态值（optimal state value）

$$v_{k+1}=f\left(v_k\right)=\underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }{v}_k),k=1,2,3\dots$$

这种算法被称为值迭代算法，根据贝尔曼公式的求解过程，我们将值迭代算法分为两步

step 1：在 vk 给定的情况下进行策略更新（policy update），求解 $\pi$，可以得到 $\pi k+1$ 。这一步是处理方程右边的优化问题：

step2：把上一步求解出的 ${\pi }_{k+1}$ 带入第一个式子，第一个式子中下标的 $\pi$ 全部变成 ${\pi }_{k+1}$，然后根据 $v_k$可以求解出来$v_{k+1}$

流程总结：

$$v_k(s)\to q_k(s,a)\to greedypolicy{\pi }_{k+1}(a|s)\to newvalue{v}_{k+1}=\underset{a}{max}{q}_k(s,a)$$

注：此处需要重复迭代更新价值函数，直至价值函数收敛（得到最优状态价值）后，才提取策略（与求解贝尔曼最优方程的过程完全一致）。

下面来看一个值迭代的具体例子

注：$a_1、a_2、a_3、a_4、a_5$分别对应着动作：上、右、下、左、原地不动

策略迭代算法（policy iteration algorithm）

该算法的大体步骤如下：

step1：之前提过，policy evaluation 就是我给定一个策略 $\pi k$（最开始是 ${\pi }_0$)，可以求解它对应的贝尔曼公式，得到 $\pi k$ 对应的 state value $v_{\pi }k$，这样的过程就叫策略评估（policy evaluation）

step2：根据上一步求解出来的$v_{\pi k}$,通过$v_{\pi k}$可求解得出${\pi }_{k+1}$,也就是对策略进行了更新，也就是策略改进（policy improvement）

为什么这种算法能最终能找到一个optimal policy（最优策略）呢？

截断策略值迭代算法（truncated policy iteration algorithm）

蒙特卡洛方法

引入

• 之前学习的内容都是基于model-based的强化学习，本章内容我们从model-based过渡到model-free的强化学习，换句话说，我们如何在没有模型的情况下去估计一些量？

蒙特卡洛估算

下面我们看这样一个例子

投掷硬币，投掷硬币后的结果（正面或背面朝上）用随机变量（random variable）X 表示,如何计算X的期望呢？

• 如果结果为正面朝上，则 $X=+1$
• 如果结果是背面朝上，则 $X=-1$

方法一：基于模型的（model-based）

假设概率模型已知，正面朝上和背面朝上的概率都是 0.5，那么期望就可通过定义简单计算：

$$\mathbb{E}[X]=\sum _{x}xp(x)=1\times 0.5+(-1)\times 0.5=0$$

方法二：不基于模型的（Model-free）

我们重复做了$N$次实验，这$N$次的实验结果分别是$x_1,x_2,x_3,x_n$，得到一个样本序列：$x_1,x_2,x_3,x_n$。那么，均值可以近似为：

$$\mathbb{E}[X]\approx \overline{x}=\frac{1}{N}\sum _{j=1}^N{x}_j$$

期望（expectation）用$\overline{x}$来近似，认为是$\mathbb{E}[X]$

蒙特卡罗估计是指依靠重复随机抽样来解决近似问题的一大类技术。凡是需要做大量的采样实验，最后用实验的结果近似的的方法，都可以称为蒙特卡洛估计的方法。

蒙特卡洛方法（MC-based RL algorithm）

蒙特卡洛方法的关键是如何将策略迭代算法（policy iteration algorithm）转换为无模型算法（model-free）。我们知道策略迭代算法（policy iteration algorithm）是依赖于模型的，但是实际上我们可以把它依赖于模型的那部分给替换掉，替换成 model-free 的模块

让我们来回顾一下策略迭代的步骤

我们从上述流程可知：得到optiaml policy的关键是求出$q_{\pi k}(s,a)$,换句话说也就是action value，我们如何求得action value呢？

有两种算法：

方法一：需要模型的方法（model-based）

这就是value iteration算法所使用的，第一步得到了$v_{\pi k}$，第二步这些概率模型都是知道的，所以就可以求出来 $q_{\pi k}(s,a)$（这些概率代表系统的模型）

方法二：不需要模型（model-free）

这种方法依赖于动作值（action value） $q_{\pi k}(s,a)$ 最原始的定义：就是从当前状态$S$出发，选择动作$a$之后，我所得到的回报（return），这个return是一个随机变量，我求它的期望（expectation）就是动作值（action value）

$$q_{\pi k}(s,a)=\mathbb{E}[G_t|S_t=s,A_t=a]$$

下面我们来看一下具体的算法流程：

下面我们来看这样一个例子

有一个初始策略 ${\pi }_0$（图中绿色箭头），在其他状态策略不错，只是在状态 $s_1,s_3$ 策略不太好。接下来就从 ${\pi }_0$出发，用 MC Basic 算法找到一个最优的策略

这个表格对应着9种state，每个state对应着5种action，所以我们要找到45个$q_{\pi k}(s,a)$,这里我们只讨论$s_1$的情况，以此类推

如果我从一个$（s1,a1）$出发的话，要找$ N$ 个轨迹，对这$ N $条轨迹的 $return$ 求平均，这样才能求出$q_{\pi k}(s_1,a_1)$。但是由于当前的问题很简单，当前的策略（policy）是确定性的（deterministic），当前的环境也是确定性的（deterministic），也就意味着，如果我从一个（s1,a1）出发，不管采样多少次，最后得到的轨迹都是相同的，因此只采样一次就可以，因此只需 one episode 就能得到行动值。

MC Exploring Starts 算法

引入

我们考虑一个网格世界的例子，按照策略$\pi$，我们可以得到一个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 }\dots$$

访问（Visit）：每当episode中出现一个状态-动作对（state-action pair）时，就称为对该状态-动作对的一次访问

在MC basic中我们是如何使用这些数据的呢？

高效使用数据的方法有两种：

• first-visit method：状态-动作对 $(s_{1},a_{2}) $\mathrm{访}\mathrm{问}\mathrm{了}\mathrm{两}\mathrm{次}，\mathrm{而}first-visitmethod\mathrm{只}\mathrm{使}\mathrm{用}\mathrm{第}\mathrm{一}\mathrm{次}\mathrm{访}\mathrm{问}$(s_{1},a_{2})$\mathrm{的}\mathrm{后}\mathrm{面}\mathrm{来}\mathrm{估}\mathrm{计}$(s_{1},a_{2})$，第二次出现的时候就不用它后面的来进行估计了。
• every-visit method：状态-动作对$(s_1,a_2)$访问了两次（第一次和第三次），every-visit method只要访问了，不管是第几次，都可以用它后面的 return 估计 $(s_1,a_2)$的 action value

除了让数据的使用更加高效之外，我们还可以更加高效的去更新策略。更新策略也有也有两种方法：

• 方法一：在策略评估（policy evaluation）步骤中，收集从一个状态-行动对（state-action pair）出发的所有 episode，然后使用平均回报（average return）来近似估计动作值（action value）

注：这是MC basic算法所采用的方法，这种方法的缺陷在于智能体必须等到所有 episode 都收集完毕。这个等待的过程浪费时间，效率低。

• 方法二：使用单个 episode 的回报（return）来立刻估计动作值（action value），然后不要等待，下一步就直接开始改进策略。这样的话，我得到一个 episode 就改进策略，得到一个 episode 就改进策略，效率会提升。

将上面的方法相结合，我们可以得到一种新的算法，MC Exploring Starts

exploring starts（探索启动）

• 探索（exploring）指的是我从每一个$(s,a)$出发，都要有 episode，只有这样我才能用后面生成的这些 reward 来估计 return，进一步估计 action value。如果恰恰有一个 state-action 没有被访问到，那我就可能把这个 action 给漏掉了，但是那个可能就是最优的，所以我们需要确保每个都被访问。

• 启动（starts）意味着我们要访问每个$(s,a)$,从它后面能够生成 reward 的这些数据有两种方法：第一种方法是从每一个 $(s,a) $\mathrm{开}\mathrm{始}\mathrm{都}\mathrm{有}\mathrm{一}\mathrm{个}episode，\mathrm{就}\mathrm{是}start；\mathrm{第}\mathrm{二}\mathrm{种}\mathrm{方}\mathrm{法}\mathrm{是}\mathrm{从}\mathrm{其}\mathrm{他}\mathrm{的}$ (s,a)$ 开始，但是也能经过当前的这个 $(s,a)$，那后面的这些数据也可以估计当前 $(s,a)$ 的 return，这个叫 visit。目前来讲，visit 方法没法确保，它依赖于策略和环境，没法确保从其他的 $(s,a)$ 开始一定能够经过剩下的所有$(s,a)$，下面我们介绍的新方法就是使得 visit 可以做到，这样就可以避免必须从每个$(s,a)$都开始的条件。

exploring starts方法让每次回合的初始状态和初始动作都是随机选择的。这样做是为了确保所有状态-动作对都有被探索的机会。

MC Epsilon-Greedy算法

在实践中，探索启动（exploring starts）是很难实现的。对于许多应用，尤其是涉及与环境物理交互的应用，很难收集到从每一对状态-行动开始的 episode。我们能否取消exploring starts的要求呢？接下来，我们将通过软策略（soft policies）来 证明这一点。

soft policy：如果采取任何动作的概率都是正数，对每一个 action 都有可能去做选择，那么该政策就是soft policy的

$\epsilon -greedypolicy$

当ε较大时，智能体更多地进行探索，以发现未知的动作空间和环境特性；当ε较小时，智能体更多地进行利用，以最大化当前已知的奖励。调整ε的大小可以影响探索和利用之间的权衡，从而影响学习过程的性能。

在了解了$\epsilon -greedy$之后，我们将其嵌入MC的RL算法

我们将之前策略改进步骤改为求解

$${\pi }_{k+1}(s)=\arg \underset{\pi \in {\mathrm{\Pi }}_{\epsilon }}{max}\sum _a\pi (a\mid s)q_{{\pi }_k}(s,a)$$

在求解上面这个问题的时候，不是在所有的策略里面去找，只是在${\pi }_{ϵ}$里面去找。其中，${\pi }_{ϵ}$表示具有固定$ϵ$值的所有$ ε-greedy $策略的集合（这里 $ε $是事先给定的）。

这时候所得到的最优策略是：（把最大的概率仍然给 greedy action，但是会给其他所有 action 都给一个相同的比较小的概率）

$${\pi }_{k+1}(a\mid s)=\{\begin{array}{ll}1-\frac{|\mathcal{A}(s)|-1}{|\mathcal{A}(s)|}\epsilon ,& a=a_k^{\ast }\\ \frac{1}{|\mathcal{A}(s)|}\epsilon ,& a\ne a_k^{\ast }\end{array}$$

随机近似与随机梯度下降

引入

在蒙特卡洛方法中，我们是如何求解期望（平均值）的？

这种计算期望的方法有一个缺点：如果要在一段时间内逐个收集样本，我们必须等到所有样本都收集完毕再求平均。我们如何克服这一缺点呢？

我们使用一种迭代式的算法，收集到几个就暂时先算几个，后面新收集到的只需要不断进行迭代即可。具体算法流程如下：

• 这种算法的优势在于它是渐进式的。一旦收到样本，就可以立即获得平均值估计值。然后，平均估算值就可以立即用于其他目的。在第 k 步的时候，我不需要把前面所有的 xi 全部加起来再求平均，只需要通过上式一步的计算就可以得到一个新的平均数。
• 这个算法代表一种增量式的计算思想：在最开始的时候因为数据量比较小，wk 难以非常精确的逼近$ \mathbb{E}[X]$，即由于样本不足，平均值估计在开始时并不准确（即 $w_k\ne \mathbb{E}[X]$）。不过，有总比没有好，总比一直等到最后才能有一个数来得到一个平均数要强。在这个过程中$w_k$就算不精确，也可以用到其它任务中。随着样本的增多，数据越来越大,$w_k$也会越来越精确的逼近$\mathbb{E}[X]$，估计值会逐渐提高（即当 $k\to \infty \mathrm{时}，w_x\to \mathbb{E}[X]$）。

我们对上述式子进行推广，可得到

$$w_{k+1}=w_k-{\alpha }_k(w_k-x_k)$$

Robbins-Monro algorithm(RM)算法

RM算法是随机近似理论（Stochastic approximation，SA）中非常经典的一个算法。

注：SA 指的是解决寻根（方程求解）或优化问题的一大类随机迭代算法，SA 的强大之处在于它不需要知道目标函数的表达式或其导数或者梯度的表达式。

假设我们想找出方程的根，如果我们不知道g(w)的函数表达式，我们如何进行求解呢？

$$g(w)=0$$

其中$w\in \mathbf{R}$是待解变量，w和g全都是标量

我们可以用RM算法来求解，我们假设最优解是$w^{\ast }$，RM算法是个迭代式的算法，对$w^{\ast }$第k次的估计是$w_k$，第k+1次的估计是$w_{k+1}$

随机梯度下降（stochastic gradient descent）

假设我们的目标是解决以下优化问题：

$$\underset{w}{min}J(w)=\mathbb{E}[f(w,X)]$$

• 目标函数$J$，是$w$的函数，目标是要找到最优的$w$，要优化$w$使得目标函数达到最小。
• 目标函数是$f$的期望,$f$是$w$和随机变量$X$的函数。随机变量$X$的概率分布（probability distribution）已经给定，但我们还不知道。期望是对$X$求期望
• $w\mathrm{和}X$可以是标量或矢量。函数 $f(\ast )$ 是一个标量。

求解这个问题有多种方法，下面给出三种方法：

方法一：梯度下降（gradient descent，GD）

我们的目标是最小化一个目标函数，所以要用梯度下降；如果目标是最大化一个目标函数，就要用梯度上升。

方法二：批量梯度下降（batch gradient descent，BGD）

方法三：随机梯度下降（stochastic gradient descent，SGD）

SGD算法实例

请写出解决这个问题的SGD算法

我们先写出这个问题的GD算法，然后用stochastic gradient代替true gradient，就可得到这个问题求解的SGD算法

$$\begin{array}{rl}{w}_{k+1}& =w_k-{\alpha }_k{\mathrm{\nabla }}_{w}J\left(w_k\right)\\ & =w_k-{\alpha }_k\mathbb{E}\left[{\mathrm{\nabla }}_{w}f(w_k,X)\right]\\ & =w_k-{\alpha }_k\frac{\mathbb{E}}{}[w_k-X]\end{array}$$

替换后有

$$w_{k+1}=w_k-{\alpha }_k{\mathrm{\nabla }}_{w}f(w_k,x_k)=w_k-{\alpha }_k(w_k-x_k)$$

SGD 的基本思路就是从 GD 出发， GD中的期望是不知道的，索性我们干脆把它去掉，用一个采样来近似这个期望，这个就是SGD算法。

用 stochastic gradient 去近似 true gradient，那么它们之间肯定是存在一个误差的，他俩之间的关系式如下：

我们知道RM 算法在满足一定条件下是可以收敛的，我们就知道 SGD 在满足什么条件下也是能够收敛的。下面我们来证明SGD算法是特殊的RM算法

SGD 要解决的问题是去最小化下面这样一个object fuction

$$J(w)=\mathbb{E}[f(w,X)]$$

这个优化问题可以转化为一个寻根问题（a root-finding problem），就是求解一个方程的问题，因为上面的目标函数要达到最优的话，必要条件是它的梯度等于 0

$${\mathrm{\nabla }}_{w}J(w)=\mathbb{E}[{\mathrm{\nabla }}_{w}f(w,X)]=0$$

如果让 g(w) 等于梯度，那么求解最优问题就变成了求解一个方程 g(w)=0 的问题。

那么 g(w)=0 可以用一个 RM 算法来求解。为了求解 RM 算法需要用到数据，也就是 g(w) 算法的表达式我们不知道，但是我们有一些测量，这个测量用 g~ 表示，g~ 是 w 和噪音的函数。

$$\begin{array}{rl}\tilde{g}(w,\eta )& ={\mathrm{\nabla }}_{w}f(w,x)\\ & =\underset{g(w)}{\underbrace{\mathbb{E}[{\mathrm{\nabla }}_{w}f(w,X)]}}+\underset{\eta }{\underbrace{{\mathrm{\nabla }}_{w}f(w,x)-\mathbb{E}[{\mathrm{\nabla }}_{w}f(w,X)]}}\end{array}$$

所以我们根据RM算法的形式可以看出RM算法就是一个SGD算法，换句话说，SGD 算法是求解这样一个特殊问题的 RM 算法。

batch gradient descent，mini-batch gradient descent 和 stochastic gradient descent（批量梯度下降，微型批量梯度下降和随机梯度下降

这里我们假设有一个目标函数$J(w)$，有$n$个采样$x_i$，我要用这样一组数据优化目标函数，有三种方法：BGD，MBGD 和 SGD

$$\begin{array}{rl}& w_{k+1}=w_k-{\alpha }_k\frac{1}{n}\sum _{i=1}^n{\mathrm{\nabla }}_{w}f(w_k,x_i)\\ & w_{k+1}=w_k-{\alpha }_k\frac{1}{m}\sum _{j\in {\mathcal{I}}_k}{\mathrm{\nabla }}_{w}f(w_k,x_j)\\ & w_{k+1}=w_k-{\alpha }_k{\mathrm{\nabla }}_{w}f(w_k,x_k)\end{array}$$

(MBGD)

BGD 每次都要用到 n 个所有的采样，在这个基础上求平均，这个可以说最接近于真实的期望（expectation）；MBGD 不用所有的采样，每次只用全部采样中的一部分，选取一组数使用（总集合的子集），这组数的集合称为 Ik，这组数有 m 个，我在这一组数上进行平均；SGD 就是从集合 {xi} 中随机选择一个 采样出来。

有 n 个数字，我们的目标是求平均值，求平均值的问题可以等价为一个优化问题：

更进一步的，如果 ${\alpha }_k$ =$\frac{1}{k}$，可以把$w_k$显式的形式给求解出来，对于 BGD 的情况

时序差分方法

引入

还记得在上一节中如何用RM算法解决均值估计问题吗？

• 要求解$w$，先把它写成一个函数 $g(w)=w-\mathbb{E}[X]$，求解 $g(w)=0 $\mathrm{的}\mathrm{方}\mathrm{程}，\mathrm{这}\mathrm{个}\mathrm{方}\mathrm{程}\mathrm{求}\mathrm{解}\mathrm{出}\mathrm{来}\mathrm{自}\mathrm{然}\mathrm{可}\mathrm{以}\mathrm{得}\mathrm{到}\mathrm{它}\mathrm{的}\mathrm{解}$ w^{*}=\mathbb{E}[X]$
• 因为我们只能获得 X 的采样 {x}，$w-x$ 是$ g$ 的测量g~

下面我们考虑一个较为复杂的例子

下面再看一个更复杂一点的例子

TD算法

TD 算法是基于数据，不基于模型（model free）实现强化学习的，算法使用的数据如下：这些数据全都是由一个给定的策略 π 所产生的，下面的 TD 算法就是要用这些数据估计 π 所对应的 state value

下面正式给出TD算法的算法流程

TD算法的主要形式一般是上图中的第一个式子，下面我们来详细介绍第一个式子

TD target

TD error

TD误差（TD error）可以解释为创新（innovation），当前我对$v_{\pi }$有一个估计，这个估计可能是不准确的，然后来了一个新的数据，然后把这个数据和我的估计联系到一起，就计算出来了 error，这个 error 的存在说明当前的估计是不准确的，可以用这个 error 来改进我当前的估计，这意味着新的从经验中获得的信息$(s_t,r_{t+1},s_{t+1})$。

TD 算法求解贝尔曼公式

TD算法有什么作用呢？

它可以在没有模型的情况下求解给定策略的贝尔曼公式，下面我们给出一个新的贝尔曼公式

下面我们来求解这个贝尔曼公式

求解model free的贝尔曼公式，我们可以使用RM算法，换句话说，TD算法就是求解贝尔曼公式的一个RM算法

由此我们得到了求解RM算法的公式

这个RM算法中有两个问题需要解决

• 在这个公式中我们要反复得到 r 和 s' 的采样，当前时刻从 s 出发跳到 s'，下一时刻还得从 s 出发跳到 s'，要反复采样。这个和 TD 算法中使用 episode 这种时序的顺序的访问是不一样的
• 上面式子用蓝色标记出来了，在计算$v_{\pi k}$的时候，要用到$v_{\pi }(s_k^{\prime })$也就是$s_k^{\prime }$真实的状态值$v_{\pi }$，但是$v_{\pi }$是不知道的。

解决的方法是

• 要解决第一个问题就是要把一组采样 $(s,r,s^{\prime })$ 替换成一组序列 $ {(s_{t}, r_{t+1}, s_{t+1})}$ ，简而言之就是不是从 s 出发得到 r 然后得到 s'，然后再从 s 出发得到 r 然后得到 s'，而是得到一个 trajectory，如果这个 trajectory 恰巧访问到了 s，就去更新一下 s，如果不访问到 s，那么 s 对应的估计值就保持不动，这样就可以用一个序列对所有 s 的 v 都进行更新。
• 另一个修改是，因为我们事先不知道 $v_{\pi }(s^{\prime })$，这是我们要求的，可以把这个$ v_π(s')$ 替换成$ v_k(s_k')$，也就是替换成 s' 这个状态它的估计值 $v_k$。即用对它的估计值来代替 $v_{\pi }(s^{\prime })$。

注：在第二个解决方案中出现了这样一个问题，在 $v_{\pi }$ 的时候能够收敛，现在给了一个 $v_k$ 是不准确的，还能确保收敛吗？

估计 action value 的 TD 算法 ——Sarsa算法

TD 算法只能估计一个给定策略的 state value，但是我们知道要改进策略的时候需要估计出 action value，这样的话哪个 action value 大，就选择哪个作为新的策略。

下面将介绍一种可以直接估计 action value 的算法——Sarsa。Sarsa 和 TD 算法的形式非常类似，只不过估计得的是 action value。Sarsa 估计出 action value 之后，在做的其实就是 policy evaluation，简单来说就是你给我一个策略，如果把这个策略的 action value 估计出来，但这个还是不能找到最优的策略，强化学习的目的是找到最优策略。那么可以把 Sarsa policy evaluation 这个算法和 policy improvement 那个算法结合起来，就可以找到最优策略

下面我们先来看第一部分，如果你给我一个策略，如何把action value估计出来

因为TD算法都是model free的，所以要有数据，或者说要有经验(experience)。假设我们有一些经验 ${(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})}_t$，这是一个集合，这个集合有很多个不同时刻的 t，每一个时刻所对应的经验是 $s_t,a_t,r_{t+1},s_{t+1},a_{t+1}$

从上文Sarsa算法的流程我们可知

• 算法的每一步都涉及$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$,Sarsa 是 state-action-reward-state-action 的缩写。
• 我们可以用动作值估计 $q(s, a) $代替 TD 算法中的状态值估计 v(s)，从而得到 Sarsa。因此，Sarsa 是动作值版本的 TD 算法。把 TD 算法对状态的估计改成对 action value 的估计，就得到了 Saesa 算法。

刚才的 TD 算法是求解了一个贝尔曼公式，Sarsa 算法也是求解了一个贝尔曼公式，只不过这个贝尔曼公式的形式有所不同。从 Sarsa 算法的表达式来看，它是一种随机逼近（stochastic approximation）算法，可以求解以下方程（以下贝尔曼公式）：

$$q_{\pi }(s,a)=\mathbb{E}[R+\gamma q_{\pi }(S^{\prime },A^{\prime })\mid s,a],\mathrm{\forall }s,a.$$

上面部分我们估计出了 action value，所以下面为了要得到最优的 policy，我们还需要把这个过程和一个 policy improvement 相结合才可以。为此，我们与策略改进（policy improvement）步骤相结合，就得到了常见的Sarsa算法。

Expected Sarsa

Expected Sarsa 算法是 Sarsa 算法的一个变种

n-step Sarsa

我们再来回顾一下action value的基本定义

Q-Learning 算法

Q learning 和 Sarsa 以及之前的算法主要区别是它是直接估计 optimal action value，它不需要去做 policy evaluation 和 policy improvement 这两个之间来回交替运行，因为直接就把最优的 action value 估计出来了，进而得到最优策略。

Sarsa 在求解一个给定策略的贝尔曼方程，而 Q-learning 不是求一个给定策略的贝尔曼方程的 action value，它是在求解一个贝尔曼最优方程

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

此处最后得到的 q 值不是说哪一个策略的 q 值，而是最优的 q 值，当然这个最优 q 值对应的最优的策略。

off-policy和on-policy

在 TD learning 任务中存在两种策略：

• 行为策略（behavior policy）与环境进行交互，用于生成经验样本（experience samples）。
• 目标策略（target policy）是我们一直在更新的，会不断更新，最后这个 target policy 就会达到我们想要的最优策略（optimal policy）。

基于 behavior 策略和 target 策略可以定义两大类强化学习的算法，就是 Off-policy 和 on-policy：

• 当行为策略（behavior policy）与目标策略（target policy）相同时，这种学习被称为 on-policy 学习。也就是说我用这个策略和环境进行交互，然后得到 experience，同时我再改进这个策略，改进完了之后我再用这个策略和环境进行交互，这个就叫 on policy

• 当两者不同时，这种学习被称为 Off-policy。比如我用一个策略和环境进行交互得到大量的经验，然后我用这些经验不断地改进一个策略，然后那个策略最后会收敛到一个最优的策略。

值函数近似（value function approximation）

引入

Q-learning通常使用表格来存储每个状态-动作对的值函数。然而，当状态空间较大时，使用表格会变得不切实际，因为需要存储大量的状态-值对。

基本方法：

通过使用函数来近似值函数，从而有效地处理大型或连续的状态空间。通常，这些函数是参数化的，例如线性函数、神经网络等。通过学习参数，这些函数能够估计任意状态的值函数，而不需要显式地存储每个状态的值。

假设状态 $S$ 的特征向量为$ \Phi(s) $，\mathrm{权}\mathrm{重}\mathrm{参}\mathrm{数}\mathrm{为}$ \mathbf{w}$，则值函数 $V(s)$可以表示为：

$$\hat{v}(s,w)=as+b=\underset{{\varphi }^T(s)}{\underbrace{[s,1]}}\underset{w}{\underbrace{\left[\begin{array}{c}a\\ b\end{array}\right]}}={\varphi }^T(s)w$$

如何找到最优的$\mathbf{w}$

找到objective（loss） function

$$J(w)=\mathbb{E}\left[{(v_{\pi }(S)-\hat{v}(S,w))}^2\right]$$

注：S是一个随机变量，S的概率分布是什么呢

稳态分布（long run behavior）

当经过足够长的时间后，系统的状态概率分布会趋向于一个固定的分布。这个固定的分布称为马尔可夫链的稳态分布。

$$J(w)=\mathbb{E}\left[{(v_{\pi }(S)-\hat{v}(S,w))}^2\right]=\sum _{s\in \mathcal{S}}{d}_{\pi }(s){(v_{\pi }(s)-\hat{v}(s,w))}^2$$

优化算法

梯度下降法

$$\begin{gathered} w_{k+1}=w_k-{\alpha }_k{\mathrm{\nabla }}_{w}J(w_k) \\ {\mathrm{\nabla }}_{w}J(w)={\mathrm{\nabla }}_w\mathbb{E}[(v_{\pi }(S)-\hat{v}(S,w){)}^2] \end{gathered}$$$$\begin{array}{rl}{\mathrm{\nabla }}_{w}J(w)& ={\mathrm{\nabla }}_w\mathbb{E}\left[{(v_{\pi }(S)-\hat{v}(S,w))}^2\right]\\ & =\mathbb{E}\left[{\mathrm{\nabla }}_w{(v_{\pi }(S)-\hat{v}(S,w))}^2\right]\\ & =2\mathbb{E}\left[(v_{\pi }(S)-\hat{v}(S,w))(-{\mathrm{\nabla }}_w\hat{v}(S,w))\right]\\ & =-2\mathbb{E}[(v_{\pi }(S)-\hat{v}(S,w)){\mathrm{\nabla }}_w\hat{v}(S,w)]\end{array}$$

为了替换掉期望$\mathbb{E}$,采用随机梯度下降的方式代替此处批量梯度下降，有公式

$$w_{t+1}=w_t+{\alpha }_t(v_{\pi }\left(s_t\right)-\hat{v}(s_t,w_t)){\mathrm{\nabla }}_w\hat{v}(s_t,w_t),$$

注：$s_t$为随机采样

$v_{\pi }(s_t)$无法得到

$$w_{t+1}=w_t+{\alpha }_t[r_{t+1}+\gamma \hat{v}(s_{t+1},w_t)-\hat{v}(s_t,w_t)]{\mathrm{\nabla }}_w\hat{v}(s_t,w_t)$$

Deep Q-learning

1.初始化

初始化两个神经网络，一个是Q网络（称为行为网络），另一个是目标Q网络。它们的结构通常是深度卷积神经网络（CNN）。

初始化学习率、折扣因子、经验回放缓冲区的大小等。

2.经验回放

在每一轮迭代中，智能体与环境进行交互，收集到的经验（状态、动作、奖励、下一个状态）被存储在经验回放缓冲区中

3.选择动作

在每个时间步，根据当前状态 (s) 从Q网络中选择动作。通常采用ε-greedy策略

4.执行动作

根据选择的动作执行在环境中，观察奖励 (r) 和下一个状态 (s')。

5.训练神经网络

从经验回放缓冲区中随机抽取一批数据，用于训练神经网络。对于每个样本，计算Q-learning的目标值，并利用梯度下降算法更新神经网络的参数。

6.更新目标网络

每隔一定的步数，复制当前的Q网络参数到目标Q网络中。

目标函数

$$J(w)=\mathbb{E}\left[{(R+\gamma \underset{a\in \mathcal{A}\left(S^{\prime }\right)}{max}\hat{q}(S^{\prime },a,w)-\hat{q}(S,A,w))}^2\right]$$

优化算法

$$y\doteq R+\gamma \underset{a\in \mathcal{A}\left(S^{\prime }\right)}{max}\hat{q}(S^{\prime },a,w)$$

设置两个神经网络

经验回放

$$J=\mathbb{E}\left[{(R+\gamma \underset{a\in \mathcal{A}\left(S^{\prime }\right)}{max}\hat{q}(S^{\prime },a,w)-\hat{q}(S,A,w))}^2\right]$$

R，S‘，S，A是随机变量，对随机变量求期望要知道他们的期望，要求均匀分布

采集时是有先后数据的，为了解决这个问题，我们引出经验回放机制即experience replay

策略梯度方法

引入

之前介绍的算法中，policy适用表格的方式表示的。所有状态的行动概率都存储在一个表 π(a|s) 中。表中的每个条目都以状态和行动为索引，每个 state 对应一行，每个 action 对应一列。我们需要通过索引去改变一个量，如下图所示