强化学习—基础部分

多臂老虎机问题

多臂老虎机问题是概率论中的一个经典的问题，也属于是强化学习的范畴。例如对于一个拥有多个拉杆的老虎机，每拉动一根拉杆都对应着一个关于奖励的概率分布 R，每次拉动一根拉杆都能从它对应的奖励概率分布中得到一个奖励 r。在每一根拉杆的奖励概率分布都未知的情况下，需要在探索其他拉杆的获奖概率和根据经验选择最多的拉杆中进行权衡，选择什么样的操作策略能使得累积奖励最高就是多臂老虎机的问题。

epsilon 贪婪算法

完全贪婪算法就是在每一时刻采取期望奖励估计值最大的动作，这就是纯粹的利用，而没有探索，所以通常要对其进行一些修改，就有了 $\epsilon$ 贪婪算法。

$\epsilon$ 贪婪算法是强化学习和多臂老虎机问题中最经典的探索-利用平衡策略，核心是通过参数 $\epsilon$ 控制随机探索与最优利用的比例，在最大化即时奖励的同时避免陷入局部最优。

在每个决策步中，算法都有两种选择：

• Exploitation：以概率 $1-\epsilon$ 选择当前已知的最优动作，也就是价值最高的动作
• Exploration：以 $\epsilon$ 的概率随机从动作空间中选择任一动作

$\epsilon$ 取值在 $0\sim1$ 之间，一般在标准强化学习任务中会选择 $0.1\sim0.2$ 之间，不过具体的值还是要根据不同的任务做出特别的调整。固定 $\epsilon$ 易导致探索不足（后期仍频繁随机）或收敛缓慢（前期探索不够），因此通常随训练进程减小 $\epsilon$ ，可以做出一些改进。

• 指数衰减： $\epsilon(t)=\epsilon_{end}+(\epsilon_{start}-\epsilon_{end})e^{-\lambda t}$ ，其中 $\lambda$ 为衰减系数
• 线性衰减： $\epsilon(t)=\max(\epsilon_{end},\epsilon_{start}kt)$ ，其中 $k$ 为每步衰减量
• 分段衰减：按照训练阶段设定不同的 $\epsilon$ 值
• 反比例函数： $\epsilon(t)=\frac{1}{t}$
• 自适应调整：根据最近奖励波动或探索收益动态调整 $\epsilon$ 值

上置信界算法

对于上述的老虎机问题，其中某第一根拉杆只被拉动过一次，而第二根拉杆被拉动过很多次，此时已经对它的奖励分布有了大致的把握，而第一根拉杆由于只被拉动过一次，所以它的不确定性很高，也就是探索价值越大，探索之后有可能会发现它的期望奖励很大。所以此时引入不确定性度量 $U(a)$ ，会随着每一个动作被尝试次数的增加而减小，可以利用这个不确定性来综合考虑现有的期望奖励估值和不确定性。

上置信界算法是一类用于是一类用于解决多臂老虎机问题的经典机器学习算法，核心思想是通过计算每个动作的置信区间上界来平衡探索与利用的权衡问题，在每次决策时选择具有最高上置信界的动作。UCB 算法的理论基础是霍夫丁不等式，该不等式为随机变量的期望提供了概率上的置信区间。对于独立同分布的随机变量 $X_1,\cdots,X_n$ ，取值范围为 $[0,1]$ ，其经验期望值为 $\bar{X}=\frac{1}{n}\sum_jX_j$ ，则有

$P(E(x)-\bar{X}\leq\delta)\geq1- e^{-2n\delta^2}$

其中不等式中的 $\delta$ 就是不确定性度量。给定一个概率 $p=e^{-2n\delta^2}$ ，根据上述不等式，则有 $E(x)\leq\bar{X}+\delta$ 的概率至少为 $1-p$ ，当 $p$ 很小时，那它就以很大概率成立，而 $\bar{X}+\delta$ 就是期望的上界，这就是在上置信界算法中用到上置信界，后面动作策略的选择都是依靠它来实现。但是，为了保证 $E(x)\leq\bar{X}+\delta$ 能稳定成立，就需要选择合适的 $\delta$ ，一般会利用当下按下按钮的总次数来定义。例如这里定义 $p=\frac{N-1}{N}$ ，它会随着拉动拉杆的次数而不断增大，同时也会小于 1，在此条件下，对应的 $\delta=\sqrt{\frac{\log N}{2n}}$ ，为了在使用中避免除零的情况，要将其变为 $\delta=\sqrt{\frac{\log N}{2(n+1)}}$ ，这里公式中的 $n$ 就是对应拉杆被拉动的次数，在此问题中应该写作 $\delta=\sqrt{\frac{\log N}{2(N(a_t)+1)}}$

另外还以在得到的上置信界加上系数 $c$ ，用以控制不确定性的比重，写作 $\bar{X}+c\delta$

汤普森采样算法

汤普森采样算法是先假设拉动每根拉骨干的奖励服从一个特定的概率分布，然后根据拉动每根拉杆的期望奖励来进行选择，但是由于计算所有拉杆期望奖励的代价较高，所以汤普森采样算法使用采样的方式，也就是根据当前每个动作奖励的概率分布进行一轮采样，得到一组各根拉杆的奖励样本，选择奖励最大的动作。

在实际使用中，通常选择 Beta 分布对当前每个动作的奖励概率分布进行建模，也就是当某个拉杆被选择了 $k$ 次，其中 $m_1$ 次奖励为 1， $m_2$ 次奖励为 0，则该拉杆的奖励服从 $Beta(m_1+1,m_2+1)$ 分布。

这里顺便介绍一下 Beta 分布，Beta 分布的概率密度函数为

$f(x;\alpha,\beta)=\frac{\Gamma(\alpha+\beta)}{\Gamma(\alpha)\Gamma(\beta)}x^{\alpha-1}(1-x)^{\beta-1}$

它的均值为 $\frac{\alpha}{\alpha+\beta}$ ，方差为 $\frac{\alpha\beta}{(\alpha+\beta)^2(\alpha+\beta+1)}$

玻尔兹曼探索

玻尔兹曼探索是强化学习或多臂老虎机问题中非均匀探索的经典策略，与 $\epsilon$ 贪婪算法同为探索-利用平衡的核心方法，它与 $\epsilon$ 贪婪算法的核心区别就是利用动作价值来分配探索概率，而非利用 $\epsilon$ 贪婪的均等随机探索，探索更高效，更适合动作空间较大且希望减少无效探索的场景。

该策略基于玻尔兹曼分布，将动作的 $Q$ 值转化为概率分布 $Q$ 值越高的动作被选中的概率就越大，同时引入温度参数 $T$ 来控制探索程度，而 $T$ 越大探索性越强， $T$ 越小越偏向于利用最优动作

首先在将动作的价值转换到玻尔兹曼概率分布空间上，公式如下

$P(a)=\frac{\exp(\frac{Q(a)}{T})}{\sum_{a_i\in A} \exp(\frac{Q(a_i)}{T})}$

其中 $T$ 是玻尔兹曼分布的温度系数，温度系数越小玻尔兹曼探索策略就越接近贪心策略，温度系数越大玻尔兹曼探索策略就越接近均匀策略。当 $T=1$ 时，玻尔兹曼探索策略也被称为 softmax 探索策略。计算出所有动作的概率之后，就可以根据概率分布来采样动作，公式为

$a_t=\arg softmax Q_t(a)$

另外由于在实际使用中，直接计算 $\exp$ 容易出现指数溢出的问题，因此在实际使用中会先对 $Q$ 做中心化处理，不改变概率分布，但能避免溢出。

$P(a)=\frac{\exp(\frac{Q(a)}{T})}{\sum_{a_i\in A}\exp(\frac{Q(a_i)}{T})}$

与 $\epsilon$ 贪婪探索方法中固定的 $\epsilon$ 一致，固定的温度 $T$ 会导致两个问题：前期 $T$ 太小导致探索不足，而后期 $T$ 太大导致无效探索过多，所以在应用中会使用随进程衰减的 $T$ 的策略

高斯探索策略

高斯探索策略是基于高斯分布的随机扰动实现的软探索方法，核心是对当前最优确定性动作添加高斯分布的随机噪声，形成带探索的随机动作选择策略，也可适配于离散动作空间

高斯探索的动作采样公式分一维连续动作和高维连续动作，它通过向确定性策略中加入随机噪声来实现探索，而高维是一维的自然扩展。

$a\sim\pi(s)+\epsilon\\\epsilon\sim\mathcal{N}(0,\sigma^2)$

其中 Exploitation 由确定性的策略 $\pi(s)$ 完成，Exploration 由服从高斯分布的噪声完成，具体的做法就是对每个动作的价值施加一个随机的噪声，然后选择价值最大的动作作为当前的动作。实际使用如下

$Q_t^{noise}(a)=Q_t(a)+\epsilon\\a_t=\underset{a\in A}{\arg\max} Q_t^{noise}(a)$

高维连续动作是一维连续动作的扩展，其中的噪声 $\epsilon\sim\mathcal{N}(0,\Sigma)$ 中的 $\Sigma$ 就是协方差矩阵，用于刻画各个动作维度的噪声相关性和各自的波动程度。实际应用中，为降低计算复杂度，通常将其设计为对角协方差矩阵。

另外，固定的 $\sigma$ 会存在与上述方法中固定参数一样的问题，也就是初期探索不足，后期探索过多，可以采用 $\sigma$ 随着迭代次数单调递减的策略，实现初期 Exploration 较多而后期 Exploitation 更多，衰减方法如下

• 指数衰减 $\sigma(t)=\sigma_0\gamma^t$ ，其中 $\gamma\in(0,1)$
• 线性衰减 $\sigma(t)=\sigma_0(1-\frac{t}{T})$
• 对数衰减 $\sigma(t)=\frac{\sigma_0}{\log(t+2)}$

马尔可夫过程算法

马尔可夫性质

马尔可夫性质是概率论中的一个概念，描述了一种随机过程的特性：当一个随机过程在给定现在状态以及所有过去状态的情况下，其未来状态的条件概率分布仅依赖于当前状态，也就是说在给定现在状态时，它与过去状态是条件独立的，那么此随机过程即具有马尔可夫性质。它的数学表达式为

$P(X_{t+1}=s_{t+1}\vert X_t=s_t,\cdots,X_0=s_0)=P(X_{t+1}=s_{t+1}\vert X_t=s_t)$

其中 $P(X_{t+1}=s_{t+1}\vert X_t=s_t)$ 是转移概率

对于连续状态来说，马尔可夫性质的公式如下

$P(X_{t+\Delta t}=j\vert X_t=i,X_s=s,s<t)=P(X_{t+\Delta t}=j\vert X_t=i)$

马尔可夫过程

马尔可夫过程指的是具有马尔可夫性质的随机过程，也被称为马尔可夫链。通常使用一个元组来描述马尔可夫过程 $\{S,P\}$ ，其中 $S$ 是有限数量的状态集合， $P$ 是状态转移矩阵，定义了所有状态对之间的转移概率。对于有 $n$ 个状态的马尔可夫过程，公式如下

$S=\{s_1,\cdots,s_n\}\\P=\begin{bmatrix}P(s_1\vert s_1)&\cdots&p(s_n\vert s_1)\\\vdots&\ddots&\vdots\\P(s_n\vert s_1)&\cdots&P(s_n\vert s_n)\end{bmatrix}$

其中 $P(s_i\vert s_j)$ 表示状态 $s_j$ 转移到 $s_i$ 的概率，而且从某个状态出发，到达其他概率的和必须为 1，即状态转移矩阵的行和为 1，即 $\sum_i P(s_i\vert s_j)=1$ 。给定一个马尔可夫过程，就可以从某个状态出发，根据状态转移矩阵生成一个状态序列

离散时间马尔可夫链 DTMC

离散时间马尔科夫链是马尔可夫过程中最基础最广泛的分支，核心特征就是时间离散和状态离散，且满足无后效性（即满足马尔可夫性质），是建模机器人状态切换、设备故障预测、路径规划等工程问题的重要工具

一个 DTMC 由以下三个关键要素完全定义

• 状态空间 $S$ ，是系统所有可能状态的集合
• 状态转移概率矩阵 $P$ ：其元素 $P_{ij}$ 表示从状态 $s_j$ 转移到状态 $s_i$ 的一步概率 $P_{ij}=P(S_{t+1}=s_i\vert S_t=s_j)$ 。状态转移概率矩阵的行的和为 1，即从任意状态 $i$ 出发，必定会转移到某个状态（包括自身）
• 初始分布 $\pi_0$

根据状态之间的可达性和转移特性，可以将状态分类

• 状态可达：从状态 $s_i$ 出发，经过有限步能以正概率到达状态 $s_j$
• 状态互通：如果 $s_i$ 可达 $s_j$ 且 $s_j$ 也可达 $s_i$ ，则称它们互通，互通的状态组成一个联通类
• 常反态：从该状态出发，在未来必定会返回的状态
• 瞬过态：从该状态出发，有正概率永不返回的状态
• 周期性：如果一个状态返回自身可能的时间步长有最大公约数 $d>1$ ，则称该状态是周期为 $d$

在 DTMC 中，对于一个不可约且非周期的 DTMC，无论从哪个状态开始，经过长时间演化之后，系统处于各个状态的概率会收敛到一个固定的分布，称为平稳分布，记作向量 $\pi$ 。其中 $\pi$ 满足如下的方程

• 平稳性方程： $\pi\times p=\pi$ ，即如果已经处于分布 $\pi$ ，则经过一次转移之后，状态分布仍为 $\pi$
• 概率归一化： $\sum_i\pi_i=1$ ，且 $\pi_i\geq0$

对于不可约且非周期的 DTMC，对于任意的初始分布 $\pi_0$ 来说都满足 $\underset{n\rightarrow \infty}{\lim}P^n\pi_0=\pi$ ，这就意味着无论初始分布如何，经过充分长的时间之后，处于状态 $s_j$ 的概率都趋近于 $\pi_j$ ，也就是 $\pi$ 为稳态分布

连续时间马尔可夫链 CTMC

连续时间马尔可夫链是时间连续但状态离散的马尔可夫过程，核心特征是系统在任意状态的停留一段时间之后转移到另一个状态（停留的时间满足指数分布），且状态转移仅依赖当前状态（即满足马尔可夫性质），弥补了离散时间马尔可夫链（DTMC）时间步固定的局限性，更适合建模机器人状态监控、设备可靠性分析等动态连续过程

CTMC 在时间维度上是连续的，它由三个要素组成

• 状态空间 $S$ ，是系统所有可能状态的集合
• 转移速率矩阵 $Q$ ，矩阵中的每个元素 $q_{ij}(i\not=j)$ 表示从状态 $s_i$ 到状态 $s_j$ 的转移速率， $q_{ii}=-\sum_{j\not=i}q_{ij}$ 表示从状态 $s_i$ 离开的总速率。另外速率矩阵的行和为 0，即 $\sum_jq_{ij}=0$
• 初始分布 $\pi_0$ 向量

对于一个概率向量，满足 $\pi Q=0$ 且 $\sum_i\pi_i=1$ ，则该向量被称为平稳分布。当 $t\rightarrow\infty$ 时，状态分布收敛到与初始分布无关的平稳分布 $\pi$ 。在 CTMC 中，状态可达性与 DTMC 中的一致，即从状态 $i$ 出发，经过有限时间能以正概率到达状态 $j$ 。

隐马尔可夫模型 HMM

隐马尔可夫模型（Hidden Markov Model, HMM）是状态不可直接观测的马尔可夫链扩展模型，它的核心特征是，系统的隐状态服从马尔可夫性质，但只能通过与隐状态相关的观测序列间接推断。

HMM 的核心是双随机过程，包含隐状态的马尔可夫转移过程（不可观测）和隐状态到观测的随机生成过程（可观测）。HMM 的核心要素如下

• 隐状态空间 S：系统不可观测的核心状态集合
• 观测空间 O：可以直接观测的观测值集合
• 初始隐状态分布 $\pi$ ，其中 $\pi_i=P(S_0=s_i)$ 为初始时刻隐状态为 $s_i$ 的概率
• 状态转移矩阵 $A$ ：其中 $a_{ij}=P(S_{t+1}=s_j\vert S_t=s_i)$ ，表示隐藏状态转移概率
• 观测概率矩阵 $B$ ：其中 $b_{ik}=P(O_t=o_k\vert S_t=s_i)$ ，表示隐状态生成观测的概率。假设当前的观测仅依赖当前隐状态，与其他状态和观测无关

马尔可夫奖励过程

在马尔可夫过程的基础上加入奖励函数 $r$ 和折扣因子 $\gamma$ ，就可以得到马尔可夫奖励过程，它是由四个元素组成的 $\{S,P,r,\gamma\}$ 。其中的奖励因子 $r(s)$ 是指转移到该状态时可以获得的奖励， $\gamma$ 是折扣因子，取值范围为 $[0,1)$ ，当 $\gamma$ 接近 0 时，表示更考虑短期奖励，接近 1 时表示更关注长期奖励。

在一个马尔可夫奖励过程中，从 $t$ 时刻状态 $s_t$ 开始，直到终止状态时，所有的奖励之和称为回报，公式如下

$G_t=R_t+\gamma R_{t+1}+\cdots=\sum_k\gamma^kR_{t+k}$

价值函数

在马尔可夫奖励过程中，一个状态的期望回报被称为这个状态的价值，所有的状态的价值就组成了价值函数，价值函数的输入为某个状态，输出为这个状态的价值，将价值函数写作如下形式

$\begin{aligned}V(s)&=E[G_t\vert S_t=s]\\&=E[R_t+\gamma R_t+\cdots\vert S_t=s]\\&=E[R_t+\gamma G_{t+1}\vert S_t=s]\\&=E[R_t+\gamma V(s_{t+1})\vert S_t=s]\end{aligned}$

在上述公式中，分为两个部分，第一部分 $E[R_t\vert S_t=s]$ 是即时奖励的期望，另一部分 $E[\gamma V(s_{t+1})\vert S_t=s]$ 可以根据从状态 $s$ 出发的状态转移概率得到

$V(s)=r(s)+\gamma\sum_{s^\prime\in S} P(s^\prime\vert s)V(s^\prime)$

这就是贝尔曼方程，方程对状态空间中的每一个状态都成立，可以将其写成矩阵的形式，即

$\begin{bmatrix}V(s_1)\\\vdots\\V(s_n)\end{bmatrix}=\begin{bmatrix}r(s_1)\\\vdots\\r(s_n)\end{bmatrix}+\gamma\begin{bmatrix}P(s_1\vert s_1)&\cdots&p(s_n\vert s_1)\\\vdots&\ddots&\vdots\\P(s_n\vert s_1)&\cdots&P(s_n\vert s_n)\end{bmatrix}\begin{bmatrix}V(s_1)\\\vdots\\V(s_n)\end{bmatrix}$

对方程进行求解，即可得到

$V=(I-\gamma P)^{-1}R$

直接求解只适合求解小规模的马尔可夫过程，对于较大规模的求解可以使用动态规划、蒙特卡洛和时序差分算法等

贝尔曼方程

Bellman 方程又叫做动态规划方程，表示动态规划问题中相邻状态关系的方程，某些决策问题可以按照时间或者空间划分为多个阶段的，每个阶段做出决策从而使得整个过程取得效果最优的多阶段决策问题，可以用动态规划方法求解

定义

• $G_t$ 是时间从 $t$ 到结束的累积奖赏，对回报值采取一定的折扣来计算，就是对于长期累计的奖赏的回报衰减

  $G_t=R_{t}+\lambda R_{t+1}+\cdots=\sum_{k}\gamma^kR_{t+k}$

• $V_\pi(s)$ 是策略为 $\pi$ 的状态-价值函数，也就是状态 $s$ 下预计回报的期望值

  $V_\pi(s)={E}[G_t\vert S_t=s]\\=\sum_{a\in A}\pi(a\vert s)Q_\pi(s,a)\\V_\pi(s)=E[R_t+\gamma V_\pi(s_{t+1})\vert S_t=s]$

• $Q_\pi(s,a)$ 是策略为 $\pi$ 的状态-动作价值函数，即状态 $s$ 下采取行动 $a$ 预计累计回报的期望值

  $Q_\pi(s,a)=\mathbb{E}[G_t\vert S_t=s,A_t=a]\\=r(s,a)+\gamma\sum_{s^\prime\in S}P(s_t\vert s,a)V_\pi(s_t)\\Q_\pi(s,a)=E[R_t+\gamma Q_\pi(s_{t+1},a_{t+1})]$

最优 Bellman 方程

• 最优策略的状态价值函数值满足

  $V_\pi^\star(s)=\underset{a\in A}{\max}\{r(s,a)+\gamma\sum_{s^\prime\in S}P(s^\prime\vert s,a)V_\pi^\star(s^\prime)\}$

• 最优策略的动作价值函数满足

  $Q_\pi^\star(s,a)=r(s,a)+\gamma\sum_{s^\prime\in S}P(s^\prime\vert s,a)\underset{a^\prime\in A}{\max}Q_\pi^\star(s^\prime,a^\prime)$

Bellman 期望方程

• 状态价值函数值的期望方程

  $V_\pi(s)=E[R_t+\gamma V_\pi(s_{t+1})\vert S_t=s]\\=\sum_{a\in A}\pi(a\vert s)\Big(r(s,a) + \gamma\sum_{s_{t+1}\in S}P(s_{t+1}\vert s,a)V_\pi(s_{t+1})\Big)$

• 动作价值函数值的期望方程

  $Q_\pi(s,a)=E[R_t+\gamma Q_\pi(s_{t+1},a_{t+1}]\\=r(s,a)+\gamma\sum_{s_{t+1}\in S}P(s_{t+1}\vert s,a)\sum_{a_{t+1}\in A}\pi(a_{t+1}\vert s,a)Q^\pi(s_{t+1})$

马尔可夫决策过程 MDP

马尔可夫决策过程是序贯决策问题的数学框架，马尔可夫决策过程是在马尔可夫奖励过程的基础上增加了动作，用于改变马尔可夫这个随机过程。马尔可夫决策过程由元组 $\{S,A,P,r,\gamma\}$ ，用如下字母表示

• 状态空间 $S$ ，是系统所有可能的状态集合
• 动作空间 $A$ ，是智能体可执行的动作集合
• 转移概率 $P(s_{t+1}\vert s_t,a_t)$ ，在状态 $s_t$ 执行动作 $a_t$ 转移到 $s_{t+1}$ 的概率
• 奖励函数 $R(s_{t},a_t,s_{t+1})$ ，从 $s_t$ 经 $a_t$ 转移到 $s_{t+1}$ 获得的即时奖励
• 折扣因子 $\gamma\in[0,1]$ ，是未来奖励的权重衰减系数，当 $\gamma=0$ 时关注即时奖励，当 $\gamma=1$ 时关注长期奖励

MDP 的所有决策逻辑都基于马尔可夫性质，即未来状态和奖励仅依赖于当前状态和动作。MDP 的策略 $\pi$ 定义了智能体在不同状态下的动作选择规则，分为两种类型

• 随机性策略： $\pi(a\vert s)=P(A_t=a\vert X_t=s)$ ，表示在状态 $s$ 下选择动作 $a$ 的概率，满足 $\sum_{a\in A}\pi(a\vert s)=1$
• 确定性策略： $\pi(s)=a$ ，表示在状态 $s$ 下必然选择动作 $a$ ，是随机性策略的特里 $\pi(a\vert s)=1$ ，其余动作概率为 0

MDP 的策略是它的核心优化对象，目标是找到最优策略 $\pi^\star$ ，使得长期累积奖励最大化。价值函数用于衡量 MDP 中某状态或某动作的长期价值，分为状态价值函数和动作价值函数，均基于策略 $\pi$ 来定义的，如下

• 累积奖励：定义从 $t$ 时刻开始的长期累积奖励 $G_t=R_{t+1}+\lambda R_{t+2}+\cdots=\sum_{k}\gamma^kR_{t+k+1}$ ， $\gamma$ 是长期建立衰减权重，避免累积奖励发散
• 状态价值函数：从状态 $s$ 出发，遵循策略 $\pi$ 获得的累积奖励期望 $V_\pi(s)=E_\pi[G_t\vert X_t=s]$
• 动作价值函数：从状态 $s$ 出发，执行动作 $a$ 之后遵循策略 $\pi$ 获得的累积奖励期望 $Q_\pi(s,a)=E_\pi[G_t\vert X_t=s,A_t=a]$

状态价值函数与动作价值函数可以互相推导

$V_\pi(s)=\sum_{a\in A}\pi(a\vert s)Q_\pi(s,a)$

在实际使用中需要计算动作价值函数和在某一策略之下的状态价值函数。此时可以将 MDP 转化为 MRP 的方法，之后利用 MRP 来求解。当给定一个 MDP 和策略 $\pi$ 之后，可以将其转化为 MRP，首先是将策略的动作进行边缘化，就可以得到没有动作的 MRP 了，对于某一个状态，根据策略将所有的动作的概率与执行该动作之后得到的奖励之和就可以被认为是一个 MRP 在该状态下的奖励

$r^\prime(s)=\sum_{a\in A}\pi(a\vert s)r(s,a)$

之后计算采取动作的概率与使 $s$ 转移到 $s^\prime$ 的概率的乘积，再累积所有动作下的乘积，就能得到状态从 $s$ 转移到 $s^\prime$ 的转移概率矩阵

$P^\prime(s^\prime\vert s)=\sum_{a\in A}\pi(a\vert s)P(s^\prime\vert s,a)$

然后就构建出了一个 MRP $\{S,P^\prime,r^\prime,\gamma\}$ ，可以发现，MRP 与 MDP 的状态价值函数是一样的，就可以利用 MRP 中计算状态价值函数的解析解来计算这个 MDP 中的状态价值函数。知道了状态价值函数之后，可以计算动作价值函数

$Q_\pi(s,a)=r(s,a)+\gamma\sum_{s^\prime\in S}P(s^\prime\vert s,a)V_\pi(s^\prime)$

然后选择最大动作价值函数来选择动作。但是这种方法在 MDP 的状态动作集合比较大的时候不太适用，所以可以使用其他方法来计算。

蒙特卡洛方法

蒙特卡洛方法也被称为模拟统计方法，是一种基于概率统计的数值计算方法。运用蒙特卡洛方法时，通常使用重复随机抽样，然后运用概率统计的方法来从抽样结果中归纳出希望得到的目标的数值估计。

在上述的 MDP 中，可以使用蒙特卡洛方法来估计一个策略在一个马尔可夫决策过程中的状态价值，而它的状态价值就是它的期望回报，那么用策略在 MDP 上采样很多条序列，计算从这个状态出发的回报，再求它的期望即可。

$V^\pi(s)=E_\pi[G_t\vert S_t=s]\approx\frac{1}{N}\sum_i^NG_t^{(i)}$

在一条序列中，有可能没有出现对应的状态，或者出现了多次这样的状态，可以在它每一次出现时计算它的回报。当然也可以在每条序列中，只在第一次该状态出现时计算它的回报，而之后再次出现它时，就忽略掉。当然也可以用策略 $\pi$ 从状态 $s$ 开始采样序列，据此来计算状态价值。

1. 使用策略 $\pi$ 采样若干条序列
2. 对于每条序列中的每一个时间步的状态 $s$ 进行操作
   1. 更新状态 $s$ 的计数器 $N(s)=N(s)+1$
   2. 更新状态 $s$ 的回报期望 $V(s)=V(s)+\frac{1}{N(s)}(G-V(s))$

根据大数定律可以得到，当 $N(s)\rightarrow\infty$ 时，有 $V(s)\rightarrow V_\pi(s)$ ，即得到状态价值函数

占用度量

实际上在不同策略下，计算得到的价值函数是不一样的，这是由于在同一 MDP 中，不同的策略会访问到的状态的概率分布是不一样的。首先定义 MDP 的初始状态分布 $v_0(s)$ 就是初始时刻智能体在状态为 $s$ 的概率，利用 $P^\pi_t(s)$ 表示采取策略 $\pi$ 使得智能体在 $t$ 时刻达到状态 $s$ 的概率，则有 $P_0^\pi(s)=v_0(s)$ ，然后定义一个策略的状态访问分布

$v^\pi(s)=(1-\alpha)\sum_{t=0}\alpha^tP_t^\pi(s)$

其中 $\alpha$ 是用于使概率之和为 1 的归一化因子， $P_t^\pi(s)$ 表示采取策略 $\pi$ 使得智能体在 $t$ 时刻状态为 $s$ 的概率。上述公式还可以写作如下形式

$v^\pi(s)=(1-\alpha)v_0(s)+\alpha\sum_{a\in A}\sum_{s^\prime\in S}P(s\vert s^\prime,a)\pi(a\vert s^\prime)v^\pi(s^\prime)$

此外可以定义策略的占用度量

$\rho^\pi(s,a)=(1-\alpha)\sum_{t=0}\alpha^tP_t^\pi(s)\pi(a\vert s)=v^\pi(s)\pi(a\vert s)$

占用度量拥有如下的性质

• 当智能体分别以策略 $\pi_1$ 和 $\pi_2$ 和同一个 MDP 交互得到的占用度量 $\rho^{\pi_1}$ 和 $\rho^{\pi_2}$ 满足 $\pi_1==\pi_2\Leftrightarrow\rho^{\pi_1}=\rho^{\pi_2}$
• 给定一个合法占用度量 $\rho$ ，可以生成该占用度量的唯一策略为 $\pi_\rho(a\vert s)=\frac{\rho(s,a)}{\sum_{a^\prime\in A}\rho(s,a^\prime)}$

动态规划算法

动态规划算法是程序设计算法中非常重要的内容，动态规划的基本思想是将待求解问题分解为若干个子问题，先求解子问题，然后从这些子问题的解得到目标问题的解，动态规划会保存已解决的子问题的答案，然后再求解目标问题的过程中，需要这些子问题的答案时，就可以直接利用，避免重复计算。

基于动态规划的强化学习算法主要有两种：策略迭代和价值迭代。策略迭代有两部分组成：策略评估和策略提升，策略迭代中的策略评估使用贝尔曼期望方程来得到一个策略的状态价值函数，这是一个动态规划的过程。而价值迭代直接使用贝尔曼最优方程来进行动态规划，得到最终的最优状态价值函数。

它的总体流程如下

$\pi_0\underset{Evaluation}{\longrightarrow}V_{\pi_0}\underset{Improvement}{\longrightarrow}\pi_1\longrightarrow\cdots\longrightarrow\pi_\star$

策略迭代

策略迭代是基于模型的强化学习中动态规划算法的核心形式之一，核心思想就是通过策略评估+策略改进的循环迭代，逐步优化策略，最终收敛到能使累积奖励期望最大化的最优策略 $\pi$ 。算法的前提使环境模型已知，即状态转移概率 $P(s^\prime\vert s,a)$ 和奖励函数 $R(s,a,s^\prime)$ 是明确已知的

策略迭代的本质就是评估当前策略的好坏，再根据评估结果优化策略，两个步骤交替进行，直到策略不再发生变化，此时的策略就是最优策略。

策略评估

策略评估这一过程用于计算一个策略的状态价值函数，对于之前的 Bellman 期望方程

$V_\pi(s)=\sum_{a\in A}\pi(a\vert s)\Big(r(s,a)+\gamma\sum_{s^\prime\in S}P(s^\prime\vert s,a)V_\pi(s^\prime)\Big)$

其中 $\pi(a\vert s)$ 是策略 $\pi$ 在状态 $s$ 下采取动作 $a$ 的概率，当已知奖励函数和状态转移函数时，可以根据下一个状态的价值来计算当前状态的价值。根据动态规划的思想，可以把计算下一个可能状态的价值当作一个子问题，把计算当前状态的价值看作当前问题，得知子问题的解之后即可求解得到当前问题。更一般的考虑所有状态，就变成了用上一轮的状态价值函数来计算当前轮的状态价值函数

$V_{k+1}(s)=\sum_{a\in A}\pi(a\vert s)\Big(r(s,a)+\gamma\sum_{s^\prime\in S}P(s^\prime\vert s,a)V_k(s^\prime)\Big)$

使用中可以选定任意初始值 $V^{(0)}$ 。当迭代次数 $k\rightarrow\infty$ 时，序列 $\{V_{k}\}$ 会收敛到 $V_\pi$ ，所以根据此来计算得到一个策略的状态价值函数，在使用中由于需要不断地做贝尔曼期望方程迭代，策略评估会消耗很大的计算代价。实际使用中，如果某一轮的 $\underset{s\in S}{\max}\vert V_{k+1}(s)-V_k(s)\vert$ 的值非常小，则可以提前结束策略评估，这样可以提升效率，得到的价值会接近真实的价值。

策略提升

使用策略评估计算得到当前策略的状态价值函数之后，可以据此来改进该策略。假设此时对于策略 $\pi$ ，由于已知其价值 $V_\pi$ ，也就是知道了在策略 $\pi$ 下从每一个状态 $s$ 出发最终得到的期望回报。假设智能体在状态 $s$ 时采用动作 $a$ ，而之后的动作依旧遵循策略 $\pi$ ，此时得到的期望回报其实就是 $Q_\pi(s,a)$ ，如果 $Q_\pi(s,a)>V_\pi(s)$ ，则说明在状态 $s$ 下采取动作 $a$ 会比原来的策略 $\pi(s\vert a)$ 获得更高的期望回报。

假设存在一个确定性的策略，在任一状态 $s$ 下，都满足

$Q_\pi(s,\pi^\prime(s))\geq V_\pi(s)$

所以在任意状态 $s$ 下，都有

$\begin{aligned}V_\pi(s)&\leq Q_\pi(s,\pi^\prime(s))\\&=E_{\pi^\prime}[R_t+\gamma V_\pi(s_{t+1})\vert S_t=s]\\&\leq E_{\pi^\prime}[R_t+\gamma Q_\pi(s_{t+1},\pi^\prime(s_{t+1}))\vert S_t=s]\\&\vdots\\&\leq E_{\pi^\prime}[R_t+\gamma R_{t+1}+\gamma^2R_{t+2}+\cdots\vert S_t=s]\\&=V_{\pi^\prime}(s)\end{aligned}\\\Downarrow\\V_{\pi^\prime}(s)\geq V_\pi(s)$

这就是策略提升定理，所以可以贪心地在每一个状态选择动作价值最大的动作，即

$\pi^\prime(s)=\underset{a}{\argmax}Q_\pi(s,a)=\underset{a}{\argmax}\{r(s,a)+\gamma\sum_{s^\prime}P(s^\prime\vert s,a)V_\pi(s^\prime)\}$

可以构造贪婪策略 $\pi^\prime(s)$ 满足策略提升定理的条件，所以策略 $\pi^\prime(s)$ 会至少与 $\pi(s)$ 一样好。根据这个贪婪算法选取动作从而得到新的策略的过程称为策略提升。

迭代算法的流程如下

• 随机初始化策略函数 $\pi(s)$ 和状态价值函数 $V(s)$
• 策略评估循环
  • 对每一个状态，计算状态价值函数 $V(s)$
  • 比较计算前后的 $V(s)$ ，如果它们的差值的最大值小于设定的阈值，就结束循环
• 策略提升
  • 根据策略评估循环计算出的状态价值函数反向求解出最优策略 $\pi(s)$
• 最后判断经过策略评估和策略提升之后的策略是否收敛，否则就再次进行策略评估+策略提升的步骤

根据策略提升定理，更新之后的策略的状态价值满足单调性，即 $V^{k+1}\geq V_k$ ，而且假设 MDP 的状态空间大小为 $\vert S\vert$ ，动作空间大小为 $\vert A\vert$ ，因此所有的策略个数为 $\vert A\vert^{\vert S\vert}$ 是有限的，所以策略迭代能在有限步数之内找到其中的最优策略

价值迭代

策略迭代中的策略评估需要很多轮才能收敛到某一策略的状态函数，这需要很大的计算量，特别是状态和动作空间比较大时。价值迭代算法的原理就是，它只在策略评估时进行一轮价值更新，然后直接根据更新之后的价值进行策略提升操作。价值迭代被认为是一种策略评估只进行了一轮更新的策略迭代算法，在价值迭代中不存在显式的策略，而是维护一个状态价值函数

价值迭代是一种动态规划过程，利用的是最优 Bellman 方程

$V^\star(s)=\underset{a\in A}{\max}\{r(s,a)+\gamma\sum_{s^\prime\in S}P(s^\prime\vert s,a)V^\star(s^\prime)\}$

将其写作迭代更新的方式

$V_{k+1}(s)=\underset{a\in A}{\max}\{r(s,a)+\gamma\sum_{s^\prime\in S}P(s^\prime\vert s,a)V_{k}(s^\prime)\}$

价值迭代就是按照这个方式更新的，迭代直到 $V_{k+1}=V_k$ 时，价值函数收敛，它就是 Bellman 最优方程的不动点，此时正对应着最优状态价值函数 $V^\star(s)$ ，之后利用下面的公式，从中恢复出最优策略即可

$\pi(s)=\underset{a\in A}{\argmax}\{r(s,a)+\gamma\sum_{s^\prime\in S}P(s^\prime\vert s,a)V_{k+1}(s^\prime)\}$

价值迭代的算法流程如下

• 随机初始化状态价值函数 $V(s)$
• 进行循环迭代，求解 $V(s)$ ，求解到 $V(s)$ 收敛之后，结束循环
• 根据求解得到的 $V(s)$ 恢复出最优策略 $\pi(s)$

它与策略迭代不同的一点就是，它不需要在初始化的策略上进行迭代，而是直接求解最优的 Bellman 方程，之后从中恢复出一个最优的策略。下面证明一下价值迭代的可收敛性

定义一个 Bellman 最优算子 $T$

$V_{k+1}(s)=TV_k(s)=\underset{a\in A}{\max}\{r(s,a)+\gamma\sum_{s^\prime\in S}P(s^\prime\vert s,a)V_{k}(s^\prime)\}$

引入压缩算子：即若 $O$ 为一个算子，且满足 $\Vert OV-OV^\prime\Vert\leq\Vert V-V^\prime\Vert$ ，则称 $O$ 为压缩算子。所以可以证明 $T$ 是一个 $\gamma$ 压缩算子

$\begin{aligned}\Vert TV-TV^\prime\Vert_\infty&=\underset{s\in S}{\max}\Big\vert\underset{a\in A}{\max}\{r(s,a)+\gamma\sum_{s^\prime\in S}P(s^\prime\vert s,a)V(s^\prime)\}-\underset{a\in A}{\max}\{r(s,a)+\gamma\sum_{s^\prime\in S}P(s^\prime\vert s,a)V^\prime(s^\prime)\}\Big\vert\\&\leq\underset{s\in S,a\in A}{\max}\Big\vert r(s,a)+\gamma\sum_{s^\prime\in S}P(s^\prime\vert s,a)V(s^\prime)-r(s,a)-\gamma\sum_{s^\prime\in S}P(s^\prime\vert s,a)V^\prime(s^\prime)\Big\vert\\&=\gamma\underset{s\in S,a\in A}{\max}\sum_{s^\prime\in S}P(s^\prime\vert s,a)\Big\vert V(s^\prime)-V^\prime(s^\prime)\Big\vert\\&\leq\gamma\underset{s\in S,a\in A}{\max}\sum_{s^\prime\in S}P(s^\prime\vert s,a)\underset{s^\prime\in S}{\max}\Big\vert V(s^\prime)-V^\prime(s^\prime)\Big\vert\\&=\gamma\Vert V-V^\prime\Vert_\infty\end{aligned}$

可以得出 $T$ 是一个 $\gamma$ 压缩因子，此时将 $V^\prime$ 设为最优的价值函数 $V^\star$ ，则有

$\Vert V_{k+1}-V^\star\Vert_\infty=\Vert TV_k-TV^\star\Vert_\infty\leq\gamma\Vert V_k-V^\star\Vert_\infty\leq\cdots\leq\gamma^{k+1}\Vert V_0-V^\star\Vert_\infty$

这就意味着当 $\gamma\leq1$ 时，随着迭代次数的不断增加， $V_k$ 会越来越接近于 $V^\star$ ，于是价值迭代是收敛的

时序差分算法

上面的动态规划算法，要求与智能体交互的环境是完全已知的，此时智能体并不需要和环境真正交互来采样数据，直接使用动态规划算法就能解出最优的价值或策略。但是在大部分场景下并不现实，机器学习的主要方式都是在数据分布未知的情况下对具体的数据点来对模型做出更新的，其马尔可夫决策过程的状态转移概率是无法写出来的，也就无法直接进行动态规划。此时智能体只能和环境进行交互，通过采样得到的数据来学习，即无模型的强化学习。

时序差分算法是强化学习领域的核心技术之一，它巧妙结合了动态规划的自举思想与蒙特卡洛方法的采样思想，解决了无模型环境下的价值函数估计与策略优化问题，时序差分算法最大的创新在于无需等待完整序列结束即可更新价值估计，以实现在线策略学习。

• 在线策略学习：要求使用在当前策略下采样得到的样本进行学习，一旦策略被更新，当前的样本就被放弃了。在线策略学习中，用于采样（行为策略）和更新（目标策略）的策略是同一个策略，即边采样边更新
• 离线策略学习：使用经验回放池将之前采样得到的样本收集起来再次利用。离线策略学习中，采样数据的策略（行为策略）与用数据来更新的策略（目标策略）不是一样的

时序差分是一种用于估计一个策略的价值函数的方法，结合了蒙特卡洛和动态规划的思想。它与蒙特卡洛方法的相似之处在于可以从样本数据中学习，不需事先已知环境，与动态规划方法的相似之处在于可以根据 Bellman 方程的思想，利用后续的价值估计来更新当前状态的价值估计。

利用先前的蒙特卡洛方法中的价值函数增量更新的公式，将其中的 $\frac{1}{N(s)}$ 替换为 $\alpha$ ，表示对价值估计的更新步长，可以将 $\alpha$ 取一个常数。时序差分算法不需要像蒙特卡洛方法中获得整个序列的采样之后才能计算这一次的回报，只需要当前步结束即可进行计算，即时序差分算法用当前获得的奖励加上下一个状态的价值估计来作为在当前状态会获得的回报，如下

$\begin{aligned}V(s_t)&=V(s_t)+\alpha[G_t-V(s_t)]\\&=V(s_t)+\alpha[r_t+\gamma V(s_{t+1})-V(s_t)]\end{aligned}$

其中 $r_t+\gamma V(s{t+1})-V(s_t)$ 被称为时序差分误差，时序差分算法将其于步长的乘积作为状态价值的更新量。此时在时序差分算法中，就可以每采样一步利用时序差分算法来更新状态价值估计，此时使用的 $V(s_{t+1})$ 是估计值。

Sarsa 算法

在不知道奖励函数和状态转移函数的情况下，可以直接利用时序差分算法来估计动作价值函数 $Q$

$Q(s_t,a_t)=Q(s_t,a_t)+\alpha[r_t+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)]$

然后利用贪婪算法选取在某个状态下动作价值最大的那个动作，即 $\underset{a\in A}{\argmax}Q(s,a)$ ，此时用贪婪算法根据动作价值选择动作来和环境交互，再根据得到的数据用时序差分算法更新动作价值估计。如果在策略提升中一直根据贪婪算法得到一个确定性的策略，可能会导致某些状态动作对永远没有在序列中出现，以至于无法对其动作价值进行估计，进而无法保证策略提升之后的策略比先前的好。简单常用的解决方案就是采用 $\epsilon$ 贪婪策略，即选择策略时以 $\epsilon$ 的概率选择随机的动作。

根据上述的介绍就可以得到 Sarsa 算法，该动作的状态更新用到了当前状态 $s$ ，当前动作 $a$ ，获得的奖励 $r$ ，下一个状态 $s^\prime$ 和下一个动作 $a^\prime$ 。Sarsa 算法的流程如下

• 初始化动作价值函数 $Q(s,a)$ ，需要覆盖到所有的状态和动作。设置学习率、折扣因子和探索率 $\epsilon$
• 对于每个训练回合
  • 重置环境，得到初始状态
  • 用 $\epsilon$ 策略根据 $Q$ 选择当前状态 $s$ 下的动作 $a$
  • 对于每个时间步
    • 执行动作得到环境反馈的 $r,s_{t+1}$ ，利用 $\epsilon$ 策略根据 $Q$ 选择当前状态 $s_{t+1}$ 下的动作 $a^\prime$
    • 更新动作价值函数 $Q(s_t,a_t)=Q(s_t,a_t)+\alpha[r_t+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)]$
    • 更新当前状态 $s$ 和对应的动作 $a$

多步 Sarsa

蒙特卡洛方法利用当前状态之后每一步的奖励而不使用任何价值估计，该方法是无偏的，由于每一步的状态转移都有不确定性，而每一步的状态采取的动作所得到的不一样的奖励都会累加，这极大地影响到了最终的价值估计，但是具有比较大的方差。

时序差分算法只利用一步奖励和下一个状态的价值估计，只关注了一步状态换衣，用到了一步的奖励，所以具有非常小的方差，但是它是有偏的，因为用到了下一个状态的价值估计而不是真实的价值。

为了将上述两种方法的优势结合起来，可以使用多步时序差分的算法，也就是使用 $n$ 步的奖励，然后使用之后状态的价值估计，也就是

$G_t=r_t+\gamma Q(s_{t+1},a_{t+1})\\\Downarrow\\G_t=r_t+\gamma r_{t+1}+\cdots+\gamma^n Q(s_{t+n},a_{t+n})$

对此也提出了多步 Sarsa 算法，对其动作价值函数的更新公式做了一些改变

$Q(s_t,a_t)=Q(s_t,a_t)+\alpha[r_t+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)]\\\Downarrow\\Q(s_t,a_t)=Q(s_t,a_t)+\alpha\Big[r_t+\gamma r_{t+1}+\cdots+\gamma^nQ(s_{t+n},a_{t+n})-Q(s_t,a_t)\Big]$

多步 Sarsa 的工作流程如下

• 初始化动作价值函数 $Q(s,a)$ ，需要覆盖到所有的状态和动作。设置学习率、折扣因子和探索率 $\epsilon$
• 对于每个训练回合
  • 重置环境，得到初始状态
  • 用 $\epsilon$ 策略根据 $Q$ 选择当前状态 $s$ 下的动作 $a$
  • 初始化训练过程中的状态列表、动作列表和奖励列表
  • 对于每个时间步
    • 执行动作得到环境反馈的 $r,s_{t+1}$ ，利用 $\epsilon$ 策略根据 $Q$ 选择当前状态 $s_{t+1}$ 下的动作 $a^\prime$
    • 将当前状态、动作和奖励分别保存到对应的列表中
    • 当队列长度足够长时才开始更新动作价值函数 $Q(s_t,a_t)=Q(s_t,a_t)+\alpha\Big[r_t+\gamma r_{t+1}+\cdots+\gamma^nQ(s_{t+n},a_{t+n})-Q(s_t,a_t)\Big]$
    • 当队列结束时，且队列长度够长，则更新从 $N-n+1$ 到 $N$ 步的动作价值函数，每一步的更新都利用它之后的所有步来更新
    • 更新当前状态 $s$ 和对应的动作 $a$

Sarsa(λ)

Sarsa(λ) 是基础的 Sarsa 的扩展，基础的 Sarsa 相当于是 Sarsa(0)，它引入了资格迹机制，通过整合多步 TD 信息实现偏差-方差的更优权衡，相比于基础的 Sarsa 具有更快的收敛速度和更强的学习效率。引入的资格迹通过记录每个状态动作对 $(s,a)$ 的近期访问痕迹，衡量该状态动作对对当前 TD 误差的贡献度，实现多步回报的加权整合。

对于状态动作对 $(s,a)$ 来说，其资格迹 $e_t(s,a)$ 表示该状态动作对在近期被访问的程度，以及其对当前 TD 误差的贡献率。当智能体访问其状态动作对时，该状态动作对会被激活，每经过一个时间步，所有的状态动作对的资格迹会按照 $\gamma\lambda$ 指数衰减，资格迹越高，说明该状态动作对在近期被访问频率越高，对当前的 TD 贡献越大，它所对应的 Q 表更新幅度也越大。资格迹的更新公式如下

• 衰减：在每个时间步内，所有状态动作对的资格迹都按 $\gamma\lambda$ 衰减
• 激活：当前访问的资格迹加 1

在每个训练回合开始前，资格迹表 $e$ 都需要初始化为 0。另外就是它新引入的参数 $\lambda$ ，用于控制多步信息的权重分配，它的取值如下

• $\lambda=0$ 等价于基础的 Sarsa，仅考虑单步信息，无资格迹累积
• $\lambda=1$ 等价于蒙特卡洛版本的 Sarsa 算法，考虑完整序列的多步信息，资格迹累积全程不衰减
• $0<\lambda<1$ 整合单步到多步的所有信息，资格迹按指数衰减，平衡收敛速度与稳定性，一般取 $0.6\sim0.9$

它的整体训练流程如下

• 初始化动作价值函数，设置超参数
• 对于每个训练回合
  • 重置环境，得到初始状态，初始化资格迹表
  • 用 $\epsilon$ 策略根据 $Q$ 选择当前状态 $s$ 下的动作 $a$
  • 对于每个时间步
    • 执行动作得到环境反馈的 $r,s_{t+1}$ ，利用 $\epsilon$ 策略根据 $Q$ 选择当前状态 $s_{t+1}$ 下的动作 $a^\prime$
    • 计算 TD 误差 $\delta_t=r_t+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)$
    • 更新资格迹 $e=\lambda e$
    • 激活当前状态动作对的资格迹 $e(s_t,a_t)=e(s_t,a_t)+1$
    • 更新动作价值函数 $Q(s_t,a_t)=Q(s_t,a_t)+\alpha\delta_te(s_t,a_t)$
    • 更新当前状态 $s$ 和对应的动作 $a$

Expected Sarsa

Expected Sarsa 是在基础的 Sarsa 算法的基础上改进的算法，属于同策略时序差分控制算法，核心创新是使用下一状态下所有动作的期望价值代替基础 Sarsa 中实际选择的单个动作价值，从而大幅度降低更新过程的方差，让训练更稳定。

它将状态价值函数的更新替换为期望价值

$Q(s_t,a_t)=Q(s_t,a_t)+\alpha[r_t+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)]\\\Downarrow\\Q(s_t,a_t)=Q(s_t,a_t)+\alpha[r_t+\gamma\sum_{a\in A}\pi(a\vert s_{t+1})Q(s_{t+1},a)-Q(s_t,a_t)]$

其中的策略 $\pi(a\vert s)$ 是基于 $\epsilon$ 贪婪策略定制的，它的计算规则如下

$\pi(a^\star\vert s)=1-\epsilon+\frac{\epsilon}{n}\\\pi(a\vert s)=\frac{\epsilon}{n}$

它的整体训练流程如下

• 初始化动作价值函数 $Q(s,a)$ ，需要覆盖到所有的状态和动作。设置学习率、折扣因子和探索率 $\epsilon$
• 对于每个训练回合
  • 重置环境，得到初始状态
  • 用 $\epsilon$ 策略根据 $Q$ 选择当前状态 $s$ 下的动作 $a$
  • 对于每个时间步
    • 执行动作得到环境反馈的 $r,s_{t+1}$
    • 利用 $\epsilon$ 贪婪策略，更新策略 $\pi(a\vert s)$
    • 更新动作价值函数 $Q(s_t,a_t)=Q(s_t,a_t)+\alpha[r_t+\gamma\sum_{a\in A}\pi(a\vert s_{t+1})Q(s_{t+1},a)-Q(s_t,a_t)]$
    • 更新当前状态 $s$ 和对应的动作 $a$

Q-Learning

除了 Sarsa 算法之外，还有一种时序差分算法 Q-Learning，它与 Sarsa 最大区别在于它们的时序差分更新方式不一样

$Q(s_t,a_t)=Q(s_t,a_t)+\alpha[r_t+\gamma \underset{a\in A}{\max}Q(s_{t+1},a)-Q(s_t,a_t)]$

Q-Learning 算法是一个 off-policy 算法，意味着它学习的策略（目标策略）与探索的策略（行为策略）可以不同。训练流程如下

• 初始化动作价值函数 $Q(s,a)$ ，需要覆盖到所有的状态和动作。设置学习率、折扣因子和探索率 $\epsilon$
• 对于每个训练回合
  • 重置环境，得到初始状态
  • 对于每个时间步
    • 用 $\epsilon$ 贪婪策略算法根据 $Q$ 选择当前状态 $s_t$ 下的动作 $a_t$
    • 得到环境反馈的 $r,s_{t+1}$
    • 更新动作价值函数 $Q(s_t,a_t)=Q(s_t,a_t)+\alpha[r_t+\gamma \underset{a\in A}{\max}Q(s_{t+1},a)-Q(s_t,a_t)]$
    • 更新当前状态 $s$

下面来证明 Q-Learning 算法的收敛性：参考自文章 《Convergence of Q-learning: a simple proof》

在文章 《On the Convergence of Stochastic Iterative Dynamic Programming Algorithms》中曾提出：假设一个随机的过程 $\Delta_{t+1}(x)=(1-\alpha_t(x))\Delta_t(x)+\alpha_t(x)F_t(x)$ ，如果满足以下的条件时，那么它将收敛到 0

• $\sum_t\alpha_t(x)=\infty$
• $\sum_t\alpha_t^2(x)<\infty$
• $\Vert E[F_t(x)]\Vert_q\leq\gamma\Vert\Delta_t\Vert_q$
• $var(F_t(x))\leq C(1+\Vert\Delta_t\Vert_q^2)$ 其中 $C$ 是一个大于零的常数

对于上述的 Q-Learning 方法，在 $t$ 时间步时给定一个数据 $(s_t,a_t,r_t,s_{t+1})$ ，则它的更新公式为

$Q_{t+1}(s_t,a_t)=Q_t(s_t,a_t)+\alpha_t(s_t,a_t)[r_t+\gamma \underset{a\in A}{\max}Q_t(s_{t+1},a)-Q_t(s_t,a_t)]$

令更新步长 $\alpha$ 与时间 $t$ 有关，并且有 $0\leq \alpha_t(s,a)\leq1$ ，将其重写为如下的形式

$Q_{t+1}(s_t,a_t)=(1-\alpha_t(s_t,a_t))Q_t(s_t,a_t)+\alpha_t(s_t,a_t)[r_t+\gamma \underset{a\in A}{\max}Q_t(s_{t+1},a)]$

假设 $\alpha_t$ 满足上述的前两个条件，即 $\sum_t\alpha_t(x)=\infty$ 和 $\sum_t\alpha_t^2(x)<\infty$ ，之后上述公式左右两侧都减去 $Q^\star(s_t,a_t)$ ，令 $\Delta_t(s_t,a_t)=Q_{t}(s_t,a_t)-Q^\star(s_t,a_t)$

$\Delta_{t+1}(s_t,a_t)=(1-\alpha_t(s_t,a_t))\Delta_{t}(s_t,a_t)+\alpha_t(s_t,a_t)[r_t+\gamma \underset{a\in A}{\max}Q_t(s_{t+1},a)-Q^\star(s_t,a_t)]$

之后开始证明后面的两个条件，此时定义

$F_t(s_t,a_t)=r_t+\gamma \underset{a\in A}{\max}Q_t(s_{t+1},a)-Q^\star(s_t,a_t)$

可以基于环境状态转移的概率分布，可以求得期望值为

$E[F_t(s_t,a_t)]=r_t+\gamma\sum_{s\in S}P(s\vert s_t,a_t)\underset{a\in A}{\max}Q_t(s,a)-Q^\star(s_t,a_t)$

可以定义一个算子 $T$ ，使得

$TQ_t(s_t,a_t)=r_t+\gamma\sum_{s\in S}P(s\vert s_t,a_t)\underset{a\in A}{\max}Q_t(s,a)$

并且由于 $Q^\star$ 是最优的动作函数，所以它针对迭代算子达到了收敛点，也就是满足 $Q^\star=TQ^\star$ ，所以上述的期望值可以写作

$E[F_t(s_t,a_t)]=TQ_t(s_t,a_t)-TQ^\star(s_t,a_t)$

根据上述价值迭代的章节中，已经证明过 $T$ 是一个压缩算子，所以有

$\Vert E[F_t(s_t,a_t)]\Vert_\infty=\Vert TQ_t(s_t,a_t)-TQ^\star(s_t,a_t)\Vert_\infty\leq\gamma\Vert Q_t-Q^\star\Vert_\infty=\gamma\Vert\Delta_t\Vert_\infty$

即证明了第三个条件，进一步推导，计算 $F_t$ 的方差

$\begin{aligned}var(F_t(s_t,a_t))&=E[(F_t(s_t,a_t)-E[F_t(s_t,a_t)])^2]\\&=E[(r_t+\gamma \underset{a\in A}{\max}Q_t(s_{t+1},a)-Q^\star(s_t,a_t)-TQ_t(s_t,a_t)+TQ^\star(s_t,a_t))^2]\\&=E[(r_t+\gamma\underset{a\in A}{\max}Q_t(s_{t+1},a)-TQ_t(s_t,a_t))^2]\\&=var(r_t+\gamma\underset{a\in A}{\max}Q_t(s_{t+1},a))\end{aligned}$

由于奖励 $r_t$ 是有界的（保证奖励偏差的方差有界和 Q 值有界），所以存在一个常数 $C$ 使得

$var(F_t(s_t,a_t))\leq C(1+\Vert\Delta_t\Vert_q^2)$

即证明了第四个条件，故 $\Delta_t$ 能收敛到 0，也就是 $Q_t$ 能收敛到 $Q^\star$ 。需要注意这个结论只适用于有限状态或优先动作空间得 Q-Learning 方法，如果扩展到连续空间时，奖励有界只能保证方差有界，但无法保证收敛性

Double Q-Learning

Double Q-Learning 是 Q-Learning 的一种改进算法，用于解决 Q-Learning 中的过估计问题。过估计问题是由于 Q-Learning 在更新 Q 值时使用了最大化未来的 Q 值，这就导致 Q 值被系统高估，从而影响算法性能和稳定性。在 Double Q-Learning 算法中引入两个独立的 Q 值函数来减少这种偏差。它的算法的流程如下

• 初始化两个 Q 值函数 $Q_A(s,a)$ 和 $Q_B(s,a)$ ，设置学习率 $\alpha$ 和折扣因子 $\gamma$
• 对于每个训练回合
  • 重置环境，得到初始状态
  • 在每个时间步 $t$ 时
    • 用 $\epsilon$ 策略根据 $Q$ 选择当前状态 $s$ 下的动作 $a$
    • 执行动作，得到环境反馈的 $r,s_{t+1}$
    • 更新 Q 值时，利用如下的公式随机选择更新 $Q_A$ 或 $Q_B$ ，更新时要用另一个函数来评估目标值
    • 更新 $Q_A(s,a)\leftarrow Q_A(s,a)+\alpha[R_{t+1}+\gamma\kern 2ptQ_B(s_{t+1},a^\prime)-Q_A(s,a)]$ ，其中 $a^\prime=\underset{a^\prime}{\arg\max}Q_A(s_{t+1},a^\prime)$
    • 更新 $Q_B(s,a)\leftarrow Q_B(s,a)+\alpha[R_{t+1}+\gamma\kern 2ptQ_A(s_{t+1},a^\prime)-Q_B(s,a)]$ ，其中 $a^\prime=\underset{a^\prime}{\arg\max}Q_B(s_{t+1},a^\prime)$
    • 更新当前状态 $s$
• 重复直到 Q 值函数收敛或达到预定的训练步数

Multi Q-Learning

Multi Q-Learning 是 Q-Learning 的一种扩展方法，旨在通过引入多个 Q 值函数来进一步减少估计偏差，并且提高算法的稳定性和性能。与 Double Q-Learning 类似，Multi Q-Learning 的核心思想是通过多个独立的 Q 值函数来分散估计误差，从而避免单一 Q 值函数可能导致的过估计或欠估计问题。它的算法的流程如下

• 初始化 $n$ 个 Q 值函数 $Q_1(s,a),\cdots,Q_n(s,a)$ ，设置学习率 $\alpha$ 和折扣因子 $\gamma$
• 对于每个训练回合
  • 重置环境，得到初始状态
  • 在每个时间步 $t$
    • 随机选择一个 Q 值函数 $Q_i$ ，用 $\epsilon$ 策略根据 $Q_i$ 选择当前状态 $s$ 下的动作 $a$
    • 执行动作，得到环境反馈的 $r,s_{t+1}$
    • 更新 Q 值时，使用选择的 $Q_i$ 进行更新 $Q_i(s,a)\leftarrow Q_i(s,a)+\alpha[r+\frac{\gamma\sum_{j\not=i}\underset{a^\prime}{\max}\kern 2ptQ_j(s^\prime,a^\prime)}{n-1}-Q_i(s,a)]$
    • 更新之后，重新随机选择 Q 值函数 $Q_i$ 进行下一时间步的更新，也就是每个时间步都随机选择 Q 值函数来进行更新和动作选择
    • 更新当前状态 $s$
• 重复动作直到 Q 值函数收敛或达到预定的训练步数

Ensemble Q-Learning

Ensemble Q-Learning 是一种基于集成学习（Ensemble Learning）的强化学习算法，旨在结合多个 Q 值函数的预测结果来提高算法的稳定性，鲁棒性和性能。相比于单一的 Q 值函数，该算法通过结合多个模型的预测结果，可以减少估计误差，避免过拟合，并且在复杂的环境中表现会更好。算法流程如下

• 初始化 $n$ 个独立的 Q 值函数，每一个 Q 值函数可以是一个独立的神经网络，初始化回放缓冲区
• 对于每个训练回合
  • 重置环境，得到初始状态
  • 在每个时间步 $t$
    • 用 $\epsilon$ 策略根据所有的 $Q$ 函数的集成结果选择当前状态 $s$ 下的动作 $a=\underset{a}{\arg\max}\frac{1}{n}\sum^nQ_i(s,a)$
    • 执行动作，得到环境反馈的 $r,s_{t+1}$
    • 更新 Q 值时，使用随机选择的 $Q_i$ 进行更新 $Q_i(s,a)\leftarrow Q_i(s,a)+\alpha[r+\gamma\underset{a}{\max}Q_i(s_{t+1},a)-Q_i(s,a)]$ ，或者也可以按照这个公式更新所有的 Q 值函数
    • 更新当前状态 $s$

Weighted Multi Q-Learning

Weighted Multi Q-Learning 是 Multi Q-Learning 的一种改进方法，通过为多个 Q 值函数赋予不同的权重来进一步优化 Q 值估计的准确性和稳定性，通过每个 Q 值的表现动态调整其权重，从而更加高效地结合多个模型预测结果

• 初始化 $n$ 个 Q 值函数，并且初始化其对应的权重 $w$ ，一般初始权重设置为相等的
• 对于每个训练回合
  • 重置环境，得到初始状态
  • 在每个时间步 $t$
    • 随机选择一个 Q 值函数 $Q_i$ ，用 $\epsilon$ 贪婪策略算法根据 $Q_i$ 选择当前状态 $s_t$ 下的动作 $a_t$
    • 执行动作，得到环境反馈的 $r,s_{t+1}$
    • 对于每个 Q 值函数，计算其 TD 误差 $\delta_i=r+\gamma\underset{a^\prime}{\max}\sum w_jQ_j(s_{t+1},a^\prime)-Q_i(s_{t},a_t)$ ，使用传统的 Q 学习更新规则进行更新 $Q_i(s_{t},a_t)= Q_i(s_{t},a_t)+\alpha\delta_i$
    • 根据 TD 误差更新每个函数对应的权重 $w_i=\frac{1}{\vert\delta_i\vert+\epsilon}$ ，其中 $\epsilon$ 时一个很小的正数，用于避免除零错误，更新之后归一化权重使得 $\sum_i^nw_i=1$
    • 更新当前状态 $s$

Dyna-Q 算法

强化学习算法有两个重要的指标：一个是算法收敛后的策略在初始状态下的期望回报，另一个是样本复杂度，即算法达到收敛结果需要在真实环境中采样的样本数量。

Dyna-Q 算法是一个经典的基于模型的全规划学习算法，Dyna-Q 使用一种叫做 Q-planning 的方法来基于模型生成一些模拟数据，然后使用模拟数据和真实数据一起来改进策略。Q-planning 每次选取一个曾经访问过的状态 $s$ ，采取一个曾经在该状态下执行过的动作 $a$ ，通过模型得到转移后的状态 $s^\prime$ 以及奖励 $r$ ，并且根据这个模拟的数据 $(s,a,r,s^\prime)$ 用 Q-Learning 的方式更新动作价值函数。

Dyna-Q 在每次与环境进行交互执行一次 Q-Learning 之后，Dyna-Q 会执行 n 次 Q-planning，这个次数 n 是一个可选择的超参数，当其为 0 时就是普通的 Q-Learning。它的算法的具体流程如下

• 初始化价值函数 $Q(s,a)$ 和模型 $M(s,a)$
• 对于每个训练回合
  • 重置环境，得到初始状态
  • 在每个时间步 $t$
    • 用 $\epsilon$ 贪婪策略算法根据 $Q$ 选择当前状态 $s_t$ 下的动作 $a_t$
    • 执行动作，得到环境反馈的 $r,s_{t+1}$
    • 更新 Q 值函数，即 $Q(s_t,a_t)=Q(s_t,a_t)+\alpha[r_t+\gamma \underset{a\in A}{\max}Q(s_{t+1},a)-Q(s_t,a_t)]$
    • 更新模型 $M(s,a)=(r,s_{t+1})$
    • 进行 n 次 Q-Planning：随机选择一个曾经访问过的状态 $s_m$ ，采取一个曾经在状态 $s_m$ 下执行过的动作 $a_m$ ，然后从模型中读取对应的 $(r_m,s_{m+1})=M(s_m,a_m)$ ，根据这些信息更新 Q 值函数
    • 更新当前状态 $s$

Dyna-Q+

Dyna-Q+ 是对标准 Dyna-Q 算法的关键改进，它解决了标准的 Dyna-Q 算法无法适应动态或非平稳环境的局限性，同时保留了 Dyna-Q 高样本效率的优势。标准的 Dyna-Q 假设环境是静态、平稳且确定性的（环境的状态转移规律始终不变），但是在真实场景中，环境有可能是动态变化的。当环境发生变化时，标准的 Dyna-Q 就存在明显的缺陷：智能体会依赖历史经验构建的旧模型进行规划，容易陷入次优路径锁定，无法主动探索因环境变化而产生的新最优解，甚至会因为过时的模型信息导致学习偏差。

Dyna-Q+ 的核心创新点为：在保留 Dyna-Q 真实经验+模拟经验的双轨学习框架的基础上，引入探索奖励机制，鼓励智能体重新访问长期未被访问的状态动作对 $(s,a)$ ，探索奖励的大小与 $(s,a)$ 的未访问时长正相关，未访问时间越久，探索奖励越高，探索动机越强。所以 Dyna-Q+ 相对于 Dyna-Q 来说，需要额外维护一个访问时序记录器，记作 $\tau(s,a)$ ，用于记录每个状态动作对从上一次被访问到当前的步数间隔。

探索奖励的经典计算方式为

$r_e=k\sqrt{\tau(s,a)}$

其中

• $k$ 是探索奖励稀疏，用于控制探索奖励的权重，通常取较小值，太大会导致智能体对之前的状态太过于关注，导致智能体停滞不前
• $\sqrt{\tau(s,a)}$ 对闲置时长取平方根，避免探索奖励随时间增长过快，保证学习稳定性

在 Q-planning 步骤中，模型返回的奖励不再是单纯的历史记录奖励 $r_m$ ，而是叠加探索奖励后的总奖励 $r_{total}=r_m+r_e$

Dyna-Q+ 算法的完整流程如下

• 初始化价值函数 $Q(s,a)$ 和模型 $M(s,a)$
• 将访问时序记录初始化为 0
• 对于每个训练回合
  • 重置环境，得到初始状态
  • 在每个时间步中
    • 用 $\epsilon$ 贪婪策略算法根据 $Q$ 选择当前状态 $s_t$ 下的动作 $a_t$
    • 执行动作，得到环境反馈的 $r,s_{t+1}$
    • 更新 Q 值函数，即 $Q(s_t,a_t)=Q(s_t,a_t)+\alpha[r_t+\gamma \underset{a\in A}{\max}Q(s_{t+1},a)-Q(s_t,a_t)]$
    • 所有已被访问过的 $\tau(s,a)=\tau(s,a)+1$
    • 更新模型 $M(s,a)=(r,\tau(s,a),s_{t+1})$
    • 进行 n 次 Q-Planning：随机选择一个曾经访问过的状态 $s_m$ ，采取一个曾经在状态 $s_m$ 下执行过的动作 $a_m$ ，然后从模型中读取对应的 $(r_m,\tau(s,a),s_{m+1})=M(s_m,a_m)$ ，根据这些信息计算出 $r=r_m+k\sqrt{\tau(s,a)}$ 来更新 Q 值函数
    • 更新当前状态 $s$

Prioritized Dyna-Q

Prioritized Dyna-Q 是 Dyna-Q 的另一种变种，核心目标是优化标准的 Dyna-Q 的规划效率，解决标准 Dyna-Q 规划阶段随机采样经验的低效性问题，让有限的 Q-planning 步数产生更大的学习效益。

标准的 Dyna-Q 的 Q-planing 阶段采用均匀随机采样策略，即从历史所有以访问的 $(s,a)$ 对中随机选取样本进行模拟更新，这种采样方式存在着明显的缺陷

• 经验价值不均等：不同的 $(s,a)$ 对的 Q 值估计偏差差异巨大，有些样本的 Q 值与真实价值差距很大，更新的收益就比较高，而有些样本的 Q 值已经接近最优了，更新的收益就很低
• 计算资源浪费：均匀采样会将大量规划步数消耗在低价值样本上，高价值样本的更新机会不足，导致规划效率偏低，无法最大化模拟经验的价值
• 收敛速度受限：即使增大规划步数，由于低效采样，价值函数的收敛速度也难以得到大幅提升，尤其在复杂的离线任务中

所以 Prioritized Dyna-Q 的改进核心就是让规划优先聚焦高价值经验。它的创新核心就是以时序差分误差作为经验价值的评判标准，优先选择 $\delta_t$ 比较大的状态动作对进行规划更新。其中 $\delta_t=r_t+\gamma \underset{a\in A}{\max}Q(s_{t+1},a)-Q(s_t,a_t)$ 越大，说明该 $(s,a)$ 的 Q 值估计偏差越大，对其进行更新能带来更大的优化收益，更快地修正价值函数的错误。

在实际中，相比于标准的 Dyna-Q 来说，它需要额外维护一个 PriorityHeap ，用于存储 $(\delta_t,s_t,a_t)$ 元组。步骤如下

• 初始化价值函数 $Q(s,a)$ 、模型 $M(s,a)$ 和优先级堆 $(\delta_t,s_t,a_t)$
• 对于每个训练回合
  • 重置环境，得到初始状态
  • 在每个时间步 $t$
    • 用 $\epsilon$ 贪婪策略算法根据 $Q$ 选择当前状态 $s_t$ 下的动作 $a_t$
    • 执行动作，得到环境反馈的 $r,s_{t+1}$
    • 计算时序差分误差 $\delta_t=r_t+\gamma \underset{a\in A}{\max}Q(s_{t+1},a)-Q(s_t,a_t)$
    • 更新 Q 值函数，即 $Q(s_t,a_t)=Q(s_t,a_t)+\alpha\delta_t$
    • 更新模型 $M(s,a)=(r,s_{t+1})$
    • 更新时序差分误差表 PriorityHeap ，如果该 $(s_t,a_t)$ 在其中已存在，则更新它的 $\delta_t$
    • 进行 n 次 Q-Planning：每次从 PriorityHeap 中选择一个具有最大 $\delta_t$ 的状态动作对，将其从中取出，然后从模型中读取对应的 $(r_m,s_{m+1})=M(s_m,a_m)$ ，根据这些信息更新 Q 值函数，再把计算之后的 $(\delta_t,s_t,a_t)$ 加入到 PriorityHeap 中
    • 更新当前状态 $s$

Dyna-2

Dyna-2 是 Dyna-Q 的进阶算法，它的核心是引入分层规划机制，解决标准 Dyna-Q 再复杂任务中因为单步动作机制导致搜索空间大，规划效率低的问题，是专门面向复杂离散任务的变体。

标准的 Dyna-Q 均基于单步动作进行规划，每次规划仅执行一个单步动作与更新 Q 值的过程，在简单任务中较为高效，而在复杂任务中，由于状态空间呈指数级增长，单步规划需要遍历大量状态，计算开销加剧；另外单步规划仅关注下一步，无法快速找到全局路径，容易陷入局部最优。

而 Dyna-2 的核心点就是将单步规划升级为分层规划，通过高层抽象规划+底层基础规划的协同，大幅压缩规划的搜索空间，提升复杂任务的学习与规划效率。

• 任务分层：将复杂任务分解为高层抽象任务和低层基础任务
  • 高层抽象工作：从当前区域到目标区域
  • 低层抽象工作：走单步到达抽象区域的边界
• 动作分层：
  • 低层动作：单步动作，是最细粒度的动作，对应基础状态空间
  • 高层动作：宏动作，由多个单步组成的动作序列，对应抽象状态空间
• 模型分层：同时维护低层基础模型和高层抽象模型
  • 低层基础模型：单步动作的状态转移和奖励
  • 高层抽象模型：宏动作的状态转移和奖励
• 规划分层：先通过高层抽象模型快速规划宏动作路径，再通过低层基础模型细化单步动作序列，双向协同更新 Q 值

完整流程如下

• 初始化阶段
  • 初始化低层：基础 $Q_0(s,a)$ 表初始化为 0，基础模型 $M_0(s,a)$
  • 初始化高层：抽象 $Q_1(S,A)$ 表初始化为 0，抽象模型 $M_1(S,A)$
• 定义状态映射 $f(s)$ ，定义 $S$ 和宏动作分解映射 $g(A)\rightarrow[a_1,a_2,\cdots]$
• 设置超参数：低层学习率 $\alpha_0$ ，高层学习率 $\alpha_1$ ，探索率 $\epsilon$ ，折扣因子 $\gamma$ ，低层规划步数 $n_0$ ，高层规划步数 $n_1$
• 对于每个训练回合
  • 重置环境，得到初始状态 $s$ ，通过映射 $f(s)$ 得到初始抽象状态 $S_t$
  • 用 $\epsilon$ 贪婪策略从抽象 $Q_1$ 表中选择最优宏动作 $A_t$ 。将宏动作 $A_t$ 分解为单步动作序列 $[a_1,a_2,\cdots,a_k]=g(A_t)$
  • 在低层执行时：依次执行单步动作 $a_1,\cdots,a_k$ ，每执行一个单步动作 $a_t$ ：
    • 执行动作，得到环境反馈的 $r,s_{t+1}$
    • 更新低层 $Q_0$ 表，即 $Q_0(s_t,a_t)=Q_0(s_t,a_t)+\alpha_0[r_t+\gamma \underset{a\in A}{\max}Q_0(s_{t+1},a)-Q_0(s_t,a_t)]$
    • 更新模型 $M_0(s,a)=(r,s_{t+1})$
    • 更新当前状态 $s$
  • 执行完动作序列之后，计算宏动作累积奖励 $R_t=\sum_t\gamma^{t-1}r_t$ ，并得到新的抽象状态 $S_{t+1}=f(s)$
  • 基于宏动作更新高层 $Q_1$ 表 $Q_1(S_t,A_t)=Q_1(S_t,A_t)+\alpha_1[R_t+\gamma \underset{A}{\max}Q_1(S_{t+1},A)-Q_1(S_t,A_t)]$
  • 更新抽象模型 $M_1(S_t,A_t)=(R_t,S_{t+1})$
  • 与标准 Dyna-Q 一致，随机采样单步动作对
  • 低层规划：进行 $n_0$ 次低层 Q-Planning：随机选择一个曾经访问过的状态 $s_m$ ，采取一个曾经在状态 $s_m$ 下执行过的动作 $a_m$ ，然后从模型中读取对应的 $(r_m,s_{m+1})=M_0(s_m,a_m)$ ，根据这些信息更新 Q 值函数
  • 高层规划：进行 $n_1$ 次低层 Q-Planning：随机选择一个曾经访问过的状态 $S_m$ ，采取一个曾经在状态 $S_m$ 下执行过的动作序列 $A_m$ ，然后从模型中读取对应的 $(R_m,S_{m+1})=M_0(S_m,A_m)$ ，根据这些信息更新 Q 值函数
  • 若 $s$ 为终止状态，则开始下一回合训练，否则继续到回合训练的第二步：选择当下最优抽象动作，继续执行训练