深度强化学习基础
该篇内容为学习 JoyRL Book 时所记录笔记，GitHub 项目地址：JoyRL-Book

# 绪论

# 强化学习相关概念

# 试错学习

试错学习（trial and error learning），即在不断地尝试和试错中学习到正确的策略。这个概念一开始是和行为心理学等工作联系在一起的，主要包括以下几个关键部分：

• 尝试：采取一系列动作或行为来尝试解决问题或实现目标。
• 错误：在尝试的过程中可能会出现错误，这些错误可能是环境的不确定性导致的，也可能是自身的不当行为导致的。
• 结果：每次尝试的后果，无论是积极的还是消极的，都会对下一次尝试产生影响。
• 学习：通过不断地尝试并出现错误，自身会逐渐积累经验，了解哪些动作或行为会产生有利的结果，从而在下一次尝试中做出更加明智的选择。

试错学习是强化学习中最鲜明的要素之一，但并不是强化学习的全部，强化学习还包含其它的学习形式例如观察学习（对应模仿学习、离线强化学习等技术）。

# 序列决策

在学习过程中个人做出的每一次尝试都是是一次决策（decision），每一次决策都会带来相应的结果，这个结果可能是即时的，也可能是延时的。我们把好的结果称为奖励（reward），坏的结果称为惩罚（punishment），或者负的奖励。最终通过一次次的决策来实现目标，这个目标通常是以最大化累积的奖励来呈现的，这个过程就是序列决策（sequential decision making）过程。

强化学习就是解决序列决策问题的有效方法之一。换句话说，对于任意问题，只要能够建模成序列决策问题或者带有鲜明的试错学习特征，就可以使用强化学习来解决，并且这是截至目前最为高效的方法之一。

# 强化学习方向概述

强化学习在游戏、机器人、金融等众多领域均有应用，其技术方向也很丰富。强化学习的典型应用有：多智能体强化学习、从数据中学习、探索策略、实时环境、多任务强化学习等等。

# 深度学习与强化学习

深度学习在强化学习中扮演的角色主要是提供了一个强大的函数拟合能力，使得智能体能够处理复杂、高维度和非线性的环境。
深度学习与强化学习之间的关系相当于眼睛和大脑的关系，眼睛是帮助大脑决策更好地观测世界的工具，对于一些没有眼睛的动物例如蚯蚓也可以通过其他的感官来观测并解析状态。再比如，同样大脑水平下，即相同的强化学习算法条件下，正常人要比双目失明的人日常的决策要更方便。但是，即使深度学习部分是相同的，例如正常大人和小孩都能通过眼睛观测世界，然由于大脑决策水平的差异也会让两者表现有所差异。
总而言之，深度与强化在更复杂的环境下缺一不可。最后，尽管强化学习算法很多，但基本上就分为两类，即基于价值的和基于策略梯度的算法，这两种算法各有优势，根据实际需要选择即可。

# 马尔可夫决策过程

马尔可夫决策过程是强化学习的基本问题模型之一，它能够以数学的形式来描述智能体在与环境交互的过程中学到一个目标的过程。这里智能体充当的是作出决策或动作，并且在交互过程中学习的角色，环境指的是智能体与之交互的一切外在事物，不包括智能体本身。状态指的是在执行动作时观测到的一些信息。
下图描述了马尔可夫决策过程中智能体与环境的交互过程。智能体每一时刻都会接收环境的状态，并执行动作，进而接收到环境反馈的奖励信号和下一时刻的状态。

智能体与环境之间是在一系列离散的时步（time step）交互的，一般用 t 来表示，t=0，1，2,... (这里的 t=0 和 t=1 之间是跟现实时间无关的，取决于智能体每次交互并获得反馈所需要的时间)。在每个时 t , 智能体会观测或者接收到当前环境的状态 $s_t$ , 根据这个状态 $s_t$ 执行动作 $a_t$ 。执行完动作之后会收到一个奖励 $r_{t+1}$ , 同时环境也会收到动作的影响变成新的状态，并且在 t+1 时步被智能体观测到，如此循环得到交互过程轨迹如下：

$$s_0, a_0, r_1, s_1, a_1, r_2, ... , s_t, a_t, r_{t+1}, ...$$

此外，在强化学习中我们通常考虑的是有限马尔可夫决策过程（Finite MDP），即 t 是有限的，这个上限一般用 T 表示，也就是当前交互过程中的最后一个时步或最大步数，从 t=0 和 t+T 这一段时步我们称为一个回合（episode），比如游戏中的一局。

# 马尔可夫性质

马尔可夫决策过程的一个前提，即马尔可夫性质。

$$P (s_{t+1}|s_t)=P (s_{t+1}|s_0,s_1,...,s_t)$$

上式表示在已知所有之前的状态 $s_0,s_1,...,s_t$ 的条件下，下一个状态 $s_{t+1}$ 发生的概率与在已知当前状态 $s_t$ 的条件下，下一个状态 $s_{t+1}$ 发生的概率相等。

在给定历史状态 $s_0,s_1,...,s_t$ 的情况下，某个状态的未来只与当前状态 $s_t$ 有关，与历史的状态无关。

这个性质其实对于很多问题有着非常重要的指导意义的，因为这允许我们在没有考虑系统完整历史的情况下预测和控制其行为。实际问题中，有很多例子其实是不符合马尔可夫性质的，比如我们所熟知的棋类游戏，因为在我们决策的过程中不仅需要考虑到当前棋子的位置和对手的情况，还需要考虑历史走子的位置例如吃子等。但是在具体的情境下，当我们要解决问题不能严格满足马尔可夫性质的条件时，是可以结合其他的方法来辅助强化学习进行决策的。

# 回报

马尔可夫决策过程中智能体的目标是最大化累积的奖励，通常我们把这个累积的奖励称为回报（Return），用 $G_t$ 表示，最简单的回报公式可写作：

$$G_t=r_{t+1}+r_{t+2}+...+r_{T}$$

其中 T 表示最后一个时步，也就是每回合的最大步数。这个公式其实只适用于有限步数的情境，例如玩一局游戏，无论输赢每回合总是会在有限的步数内会以一个特殊的状态结束，这样的状态称之为终止状态。但也有一些情况是没有终止状态的，换句话说智能体会持续与环境交互，比如人造卫星在发射出去后会一直在外太空作业直到报废或者被回收，这样的任务称之为持续性任务。在持续性任务中上述公式不适用，因为此时 $T = \infty$。

为了解决这个问题，引入一个折扣因子（discount factor）$\gamma$，并可以将回报表示为：

$$G_t=r_{t+1}+ \gamma r_{t+2} + \gamma^2 r_{t+3} +... = \sum ^{T = \infty} _ {k=0} \gamma^k r_{t+k+1}$$

其中 $\gamma$ 取值范围在 0 到 1 之间，它表示了我们在考虑未来奖励时的重要程度，控制着当前奖励和未来奖励之间的权衡。换句话说，它体现了我们对长远目标的关注度。当 $\gamma = 0$ 时，我们只会关心当前的奖励，而不会关心将来的任何奖励。而当 $\gamma$ 接近 1 时，我们会对所有未来奖励都给予较高的关注度。
这样做的好处是会让当前时步的回报 $G_t$ 跟下一个时步的回报 $G_{t+1}$ 是有所关联的，对于所有 t < T ，有下式：

$$G_t \overset {\text {.}}{=} r_{t+1}+ \gamma r_{t+2} + \gamma^2 r_{t+3} + \gamma^3 r_{t+4} ...$$

$$= r_{t+1}+ \gamma ( r_{t+2} + \gamma r_{t+3} + \gamma^2 r_{t+4} +... )$$

$$= r_{t+1}+ \gamma G_{t+1}$$

# 状态转移矩阵

当前主要讨论有限状态马尔可夫决策过程（finite MDP），即状态的数量必须是有限的，无论是离散的还是连续的。如果状态数是无限的，此时通常会用另一种方式来对问题进行建模，称之为泊松（Poission）过程，又称为连续时间马尔可夫过程。然而在绝大部分强化学习实践场景中，泊松过程并不常见，对相关理论感兴趣可自行研究。
既然状态数有限，我们就可以用一种状态流向图的形式表示智能体与环境交互过程中的走向。举个例子，学生在上课时一般会有三种状态，认真听讲、玩手机和睡觉，分别用 $s_1, s_2$ 和 $s_3$ 表示。我们知道在马尔可夫决策过程中一般所有状态之间都是可以相互切换的，当学生在认真听讲时能切换到玩手机或者睡觉的状态，在睡觉时也可能继续睡觉，也可能醒过来认真听讲或者玩手机。如下图所示，图中每个曲线箭头表示指向自己，比如当学生在认真听讲即处于状态 $s_1$ 时，会有 0.2 的概率继续认真听讲。当然也会分别有 0.4 和 0.4 的概率玩手机（$s_2$）或者睡觉（$s_3$）。此外，当学生处于状态 $s_2$ 时，也会有 0.2 的概率会到认真听讲的状态（$s_1$），像这种两个状态之间能互相切换的情况我们用一条没有箭头的线连接起来，参考无向图的表示。

整张图表示了马尔可夫决策过程中的状态流向，这其实跟数字电路中有限状态机的概念是一样的。严格意义上来讲，这张图中并没有完整地描述出马尔可夫决策过程，因为没有包涵动作、奖励等元素，所以一般我们称之为马尔可夫链（Markov Chain），又叫做离散时间的马尔可夫过程（Markov Process），跟马尔可夫决策过程一样，都需要满足马尔可夫性质。因此我们可以用一个概率来表示状态之间的切换，比如
$P_{12} = P (S_{t+1} = s_2 | S_t = s_1) = 0.4$ 表示当前时步的状态 $s_1$ 在下一个时步切换到 $s_2$ 的概率，我们把这个概率称为状态转移概率（State Transition Probability）。拓展到所有状态我们可以表示为下式：

$$P_{ss'}= P (S_{t+1} = s' | S_t = s)$$

即当前状态是 s 时，下一个状态是 s' 的概率，其中大写的 S 表示所有状态的集合，即 $S$ = {$s_1$, $s_2$, $s_3$} 。
由于状态数是有限的，将其概率绘制成表格如下：

在数学上也可以用矩阵来表示，如下：

$$P_{ss'} = \left [ \begin {matrix} 0.2 & 0.4 & 0.4 \\ 0.2 & 0.5 & 0.3 \\ 0.1 & 0.3 & 0.6 \end {matrix} \right]$$

这个矩阵就叫做状态转移矩阵（State Transition Matrix），拓展到所有状态可表示为:

$$P_{ss'} = \left ( \begin {matrix} p_{11} & p_{12} & \cdots & p_{1n} \\ p_{21} & p_{22} & \cdots & p_{2n} \\ \cdots & \cdots & \cdots & \cdots \\ p_{n1} & p_{n2} & \cdots & p_{nn} \end {matrix} \right)$$

其中 n 表示状态数，注意对于同一个状态所有状态转移概率加起来是等于 1 的，即 $p_{n1} + p_{n2} + \cdots +p_{nn} = 1$ 。
还有一个非常重要的点就是， 状态转移矩阵是环境的一部分 ，跟智能体是没什么关系的，而智能体会根据状态转移矩阵来做出决策。在这个例子中老师是智能体，学生的状态不管是认真听讲、玩手机还是睡觉这些老师是无法决定的，老师只能根据学生的状态做出决策，比如看见学生玩手机就提醒一下等等。
此外， 在马尔可夫链（马尔可夫过程）的基础上增加奖励元素就会形成马尔可夫奖励过程（Markov reward process, MRP） ，在马尔可夫奖励过程基础上增加动作的元素就会形成马尔可夫决策过程，也就是强化学习的基本问题模型之一。其中马尔可夫链和马尔可夫奖励过程在其他领域例如金融分析会用的比较多，强化学习则重在决策。
到这里我们就可以把马尔可夫决策过程描述成一个现今天常用的写法，即用一个五元组来表示 :

$$<S,A,R,P,\gamma>$$

其中 S 表示状态空间，即所有状态的集合，A 表示动作空间，R 表示奖励函数，P 表示状态转移矩阵，$\gamma$ 表示折扣因子。

# 动态规划

# 动态规划的编程思想

先看一道经点面试题：一个机器人位于一个 $ m\times n$ 网格的左上角 （起始点在下图中标记为 “S” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角即终点（在下图中标记为 “F” ）。我们需要解决的问题是在这个过程中机器人可以有多少条不同的路径到达终点。

使用动态规划的做法，动态规划的解法主要有几个步骤：确定状态，写出状态转移方程和寻找边界条件。
在这个例题中我们首先可以定一个 $f (i,j)$，表示从左上角即坐标为 $(0,0)$ 到坐标 $(i,j)$ 的路径数量，其中 $i \in [0,m)$ 以及 $j \in [0,n)$。由于机器人只能向右或者向下走，所以当机器人处于 $(i,j)$ 的位置时，它的前一个坐标只能是上边一格 $(i,j-1)$ 或者左边一格 $(i-1,j)$ ，这样一来就能建立出一个状态之间的关系，如式:

$$f (i,j)=f (i-1,j) + f (i,j-1)$$

即走到当前位置 $(i,j)$ 的路径数量等于走到前一个位置 $(i,j-1)$ 和 $(i-1,j)$ 的所有路径之和，这个就是状态转移方程。

此外我们需要考虑一些边界条件，因为在状态转移方程中 $i$ 和 $j$ 是不能等于 0 的，比如都等于 0 的时候会出现
$f (0,0) = f (-1,0) + f (0,-1)$ ，因此我们需要额外判断 $i$ 和 $j$ 等于 0 的情况。如下图 所示，首先考虑 $i=0,j=0$ 的情况，即 $f (0,0)$ ，显然此时机器人在起始点，从起始点到起始点 $(0,0)$ 对应的路径数量必然是 1，对于 $i \neq 0,j=0$，此时机器人会一直沿着网格左边沿往下走，这条路径上的所有 $f (i,j)$ 也都会是 1，$i = 0,j \neq 0$ 的情况同理。

因此状态转移方程可以完善为：

$$f (i,j) = \begin {cases} 1 & i=0, j = 0 \\ 1 & i=0, j \neq 0 \\ 1 & i \neq 0, j = 0 \\ f (i-1,j) + f (i,j-1) \end {cases}$$

因此可以写出如下代码

def solve (m,n):

    # 初始化边界条件

    f = [[1] * n] + [[1] + [0] * (n - 1) for _ in range (m - 1)] 

    # 状态转移

    for i in range (1, m):

        for j in range (1, n):

            f [i][j] = f [i - 1][j] + f [i][j - 1]

    return f [m - 1][n - 1]

一般 动态规划问题有三个性质，最优化原理、无后效性和有重叠子问题 。其中有重叠子问题不是动态规划问题的必要条件。无后效性指的是即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关，这其实就是前面所说的马尔可夫性质。而最优化原理是指，如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。马尔可夫决策过程的目标是最大化累积回报，根据回报公式，要解决 $G_{t+1}$ 的问题，可以一次拆分成解决 $G_t,G_{t-1}, \cdots,G_1 $ 的问题，这其实就满足动态规划性质中的最优化原理。综合以上两点，我们可以利用动态规划的思想来解决强化学习问题，具体解决方法参考后面讲解的价值迭代和策略迭代算法。

# 状态价值函数和动作价值函数

在马尔可夫决策过程中，每个状态是有一定的价值的，可以定义为：

$$V_{\pi} (s) = \mathbb {E}[R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots | S_t = s]$$

$$=\mathbb {E}[G_t | S_t =s]$$

这就是状态价值函数（state-value function），从特定状态出发，按照某种策略 $\pi$ 进行决策所能得到的回报期望值，注意这里的回报是带有折扣因子 $\gamma$ 的。
另外引入动作的元素后会有一个 $Q$ 函数，也叫做 动作价值函数（action-value function），即

$$Q_{\pi}(s,a)=\mathbb {E}[G_t|s_t=s,a_t=a]$$

由于我们遵循策略 $\pi$ 来选择动作，我们可以将 $V_ \pi (s)$ 表达为采取所有可能动作的期望回报的加权平均，其中每个动作的权重是该动作在给定状态下根据策略 $\pi$ 被选择的概率 $\pi (a|s)$

$$V_{\pi} (s) = \sum _{a \in A} \pi (a|s) \cdot \mathbb {E}[G_t|s_t=s,a_t=a]$$

将动作价值函数代入得到

$$V_{\pi} (s) = \sum _{a \in A} \pi (a|s) Q_{\pi}(s,a)$$

其中 $\pi (a|s)$ 表示策略函数，一般指在状态 $s$
下执行动作 $a$ 的概率分布。公式表示在给定状态 $s$ 的情况下，智能体所有动作的价值期望（所有动作价值函数乘以对应动作的概率之和）就等于该状态的价值，这其实就是利用了数学中的全期望公式。

# 贝尔曼方程

类比于回报公式 $G_t = R_{t+1} + \gamma G_{t+1}$ ，也可以对状态价值函数和动作价值函数做一个类似的推导，如下：

$$V_{\pi}(s)= \mathbb {E}_ \pi [R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3}+ \cdots |S_t =s]$$

根据马尔可夫性质，未来回报依赖于下一个状态 $S_{t+1}$ 而不是历史状态，因此可以将期望回报分解为立即回报和从下一个状态开始的期望回报的折现

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

立即回报 $R_{t+1}$ 是在状态 $s$ 下采取某个动作后立即获取的回报，它可以通过策略 $\pi$ 和状态转移概率 $p (s'|s)$ 来计算。由于我们考虑的是状态价值函数，不关心采取的具体动作，因此我们可以将立即回报写为状态 $s$ 的函数 $R (s)$

$$R (s) = \sum_{a \in A} \pi (a|s) \sum_{s' \in S} p (s'|s,a) r (s,a,s')$$

其中 $r (s,a,s')$ 是从状态 $s$ 采取动作 $a$ 到达状态 $s'$ 时获得的立即回报。
对于第二项，我们需要考虑从状态 $s$ 转移到所有可能状态 $s'$ 的概率，并计算在这些状态下的价值函数的期望值。由于我们遵循策略 $\pi$ ，我们可以将 $V_\pi (S_{t+1})$ 写为 $V_\pi (s')$ 的加权平均，权重是转移到每个状态的概率：

$$\mathbb {E}_\pi [V_\pi (S_{t+1})|S_t =s] =\sum_(s' \in S) p (s'|s) V_\pi (s')$$

这里的 $p (s'|s)$ 是从状态 $s$ 转移到状态 $s'$ 的概率，它可以通过策略 $\pi$ 和状态转移概率 $p (s'|s,a)$ 来计算

$$p (s'|s)=\sum_{a \in A} \pi (a|s) p (s' |s,a)$$

将上述两部分的期望回报代入原始的期望回报表达式中，得到状态价值函数的贝尔曼方程

$$V_{\pi}(s)=R (s)+{\gamma} \sum_{s' \in S} p (s'|s) V_{\pi}(s')$$

类似的，动作价值函数贝尔曼方程推导为：

$$Q_\pi (s,a)=R (s,a)+\gamma \sum_{s' \in S} p (s' |s,a) \sum_{a' \in A} \pi (a'|s') Q_\pi (s',a')$$

在最优策略 $\pi$ 下，状态价值函数也是最优的，相应的动作价值函数也最优。我们的目标是使得累积的回报最大化，那么最优策略下的状态价值函数可以表示为：

$$V^*(s) = \max_{a \in \mathcal {A}} \left ( R (s, a) + \gamma \sum_{s' \in \mathcal {S}} P (s'|s, a) V^*(s') \right)$$

这个公式叫做贝尔曼最优方程（Bellman optimality equation）, 对于动作价值函数也是同理

$$Q^*(s, a) = R (s, a) + \gamma \sum_{s' \in \mathcal {S}} P (s'|s, a) \max_{a' \in \mathcal {A}} Q^*(s', a')$$

# 策略迭代

在最优策略下，对应的状态和动作价值函数也都是最优的。但是实际求解中在优化策略的过程中，同时我们还需要优化状态和动作价值函数，这其实是一个多目标优化的问题。
策略迭代算法的思路是分成两个步骤，首先固定策略 $\pi$ 不变，然后估计对应的状态价值函数 $V$ ，这一叫做策略估计（policy evaluation）。然后根据估计好的状态价值函数 $V$
结合策略推算出动作价值函数 $Q$，并对 $Q$ 函数优化然后进一步改进策略，这一步叫策略改进（policy improvement）。在策略改进的过程中一般是通过贪心策略来优化的，即定义策略函数为：

$$\pi (a|s) = \max_{a \in \mathcal {A}} Q (s,a)$$

策略迭代算法的伪代码如下

初始化策略 π

重复直到收敛：

    1. 策略评估（Policy Evaluation）:

        对于所有状态 s：

            V (s) <- R (s, π(s)) + γ ∑ p (s'|s,π(s)) V (s')

        直到 V (s) 的变化小于某个阈值

    2. 策略改进（Policy Improvement）:

        对于所有状态 s：

            Q (s, a) <- R (s, a) + γ ∑ p (s'|s, a) V (s')

        对于所有状态 s：

            π(s) <- argmax_a Q (s, a)

# 价值迭代

价值迭代算法相对于策略迭代更加直接，它直接根据以下公式来迭代更新。

$$V (s) \leftarrow \max_{a \in \mathcal {A}} \left ( R (s, a) + \gamma \sum_{s' \in \mathcal {S}} P (s'|s, a) V (s') \right)$$

价值迭代首先将所有的状态价值初始化，然后不停地对每个状态迭代，直到收敛到最优价值 $V^*$，并且根据最优价值推算出最优策略 $\pi^*$ 。
价值迭代算法伪代码如下

初始化 V (s) 对于所有状态 s

重复直到收敛：

    对于所有状态 s：

        Q (s, a) <- R (s, a) + γ ∑ p (s'|s, a) V (s')

        V (s) <- max_a Q (s, a)

    直到 V (s) 的变化小于某个阈值

对于所有状态 s：

    π(s) <- argmax_a Q (s, a)

这种情况下，其实比策略迭代算法要慢得多，尽管两种方法都需要多次遍历。但是在策略迭代算法中考虑了中间每个时步可能遇到的最优策略并及时加以改进，这意味着就算策略在早期并不完美（也许需要改进），策略迭代仍能够更快地接近最优解。

# 免模型预测

# 有模型与免模型

在前面的章节中，均默认了状态转移概率是已知的，这种情况下的算法称为有模型算法，但是对于大部分情况下的智能体，环境是未知的，这种情况下的算法称为免模型算法。
有模型的强化学习尝试先学习一个环境模型，它可以是环境的动态（例如，给定一个状态和一个动作，预测下一个状态）或奖励（给定一个状态和一个动作，预测奖励）。一旦有了这个环境模型，智能体可以使用它来计划最佳的行动策略，例如通过模拟可能的未来状态来预测哪个动作会导致最大的累积奖励。它的优点很明显，即可以在不与真实环境交互的情况下进行学习，因此可以节省实验的成本。但缺点是，这种模型往往是不完美的，或者是复杂到难以学习和计算。
免模型直接学习在特定状态下执行特定动作的价值或优化策略。它直接从与环境的交互中学习，不需要建立任何预测环境动态的模型。其优点是不需要学习可能是较为复杂的环境模型，更加简单直接，但是缺点是在学习过程中需要与真实环境进行大量的交互。注意，除了动态规划之外，基础的强化学习算法都是免模型的。

# 预测与控制

前面提到很多经典的强化学习算法都是免模型的，换句话说在这种情况下环境的状态转移概率是未知的，这种情况下会去近似环境的状态价值函数，这其实跟状态转移概率是等价的，我们把这个过程称为预测。换句话说，预测的主要目的是估计或计算环境中的某种期望值，比如状态价值函数 $V (s)$ 或动作价值函数 $Q (s,a)$ 。例如，我们正在玩一个游戏，并想知道如果按照某种策略玩游戏，我们的预期得分会是多少。
而控制的目标则是找到一个最优策略，该策略可以最大化期望的回报。换句话说，你不仅想知道按照某种策略你的预期得分是多少，还想知道如何选择动作以最大化这个得分。控制问题通常涉及两个相互交替的步骤：策略评估（使用当前策略估计值函数）和策略改进（基于当前的值函数更新策略）。
在实际应用中，预测和控制问题经常交织在一起。例如，在使用 Q-learning（一种免模型的控制算法）时，我们同时进行预测 (更新 $Q$ 值) 和控制 (基于 $Q$ 值选择动作)。很多时候我们不能一蹴而就解决好控制问题，而需要先解决预测问题，进而解决控制问题。

# 蒙特卡洛估计

蒙特卡洛估计方法在强化学习中是免模型预测价值函数的方式之一，本质是一种统计模拟方法。
假设需要计算一个不规则图形的面积，这种情况下是很难通过规则或者积分的方式得到结果的。蒙特卡洛基于这样的想法：使用计算机程序生成大量均匀分布坐标点，让所有坐标点组成的范围能够完全覆盖不规则图形。然后统计出图形内的点数，通过它们占总点数的比例和坐标点生成范围的面积就可以求出图形面积。
假设上一章节的机器人在 $m \times n$ 需要寻找最短路径。我们用机器人的位置表示不同状态，即 $s_1,s_2,s_3,s_4$ ，机器人只能向下或者向右走，对应动作 $a_1 $ 和 $ a_2$ ，起点坐标 $(0,0)$ ，即初始状态 $S_0 = s_1$ ，设定机器人每走一步接收到奖励为 $-1$ ，折扣因子 $\gamma = 0.9$。

使用蒙特卡洛方法，采样大量的轨迹，对于每个轨迹计算对应状态的回报然后取平均近似，称之为经验平均回报（empirical mean return）。根据大数定律，只要采样的轨迹数量足够多，计算出的经验平均回报就能趋近于实际的状态价值函数。当然，蒙特卡洛方法有一定的局限性，即只适用于有终止状态的马尔可夫决策过程。
蒙特卡洛方法主要分成两种算法，一种是首次访问蒙特卡洛（first-visit Monte Carlo,FVMC）方法，另外一种是每次访问蒙特卡洛（every-visit Monte Carlo,EVMC）方法。FVMC 方法主要包含两个步骤，首先是产生一个回合的完整轨迹，然后遍历轨迹计算每个状态的回报。注意，只在第一次遍历到某个状态时会记录并计算对应的回报。而在 EVMC 方法中不会忽略统一状态的多个回报。
使用 FVMC 估算某个马尔可夫决策过程（MDP）状态值函数的伪代码：

初始化：

    对于所有状态 s，V (s) = 0

    N (s) = 0，对于所有状态 s

    策略 π 用于选择动作

    G = 0

对于每个 episode（序列）:

    初始化 S，为当前状态

    终止 = False

    生成一个序列，直到达到终止状态:

        选择动作 A 根据策略 π

        执行动作 A，获得奖励 R 和下一个状态 S'

        S = S'

        如果是终止状态，则终止 = True

        G = G + R

        如果 S' 是第一次访问:

            N (S') = N (S') + 1

            V (S') = V (S') + (G - V (S'))

    直到 终止

使用 EVMC 估算某个马尔可夫决策过程（MDP）状态值函数的伪代码：

初始化：

    对于所有状态 s，V (s) = 0

    N (s) = 0，对于所有状态 s

    策略 π 用于选择动作

    G = 0

对于每个 episode（序列）:

    初始化 S，为当前状态

    终止 = False

    生成一个序列，直到达到终止状态:

        选择动作 A 根据策略 π

        执行动作 A，获得奖励 R 和下一个状态 S'

        S = S'

        如果是终止状态，则终止 = True

        G = G + R

        N (S) = N (S) + 1

        V (S) = V (S) + (G - V (S))

    直到 终止

FVMC 是一种基于回合的增量式方法，具有无偏性和收敛快的优点，但是在状态空间较大的情况下，依然需要训练很多个回合才能达到稳定的结果。而 EVMC 则是更为精确的预测方法，但是计算的成本相对也更高。

# 时序差分估计

时序差分估计方法是一种基于经验的动态规划方法，它结合了蒙特卡洛和动态规划的思想。最简单的时序差分可以表示为：

$$V (s_t) \leftarrow V (s_t) + \alpha [r_{t+1} + \gamma V (s_{t+1} - V (s_t))]$$

这种算法一般称为单步时序差分 (one-step TD)，即 $TD (0)$ 。可以看到，在这个更新过程中使用了当前奖励和后继状态的估计，这是类似于蒙特卡罗方法的；但同时也利用了贝尔曼方程的思想，将下一状态的值函数作为现有状态值函数的一部分估计来更新现有状态的值函数。此外，时序差分还结合了自举（bootstrap）的思想，即未来状态的价值是通过现有的估计 $r_{t+1} + \gamma V (s_{t+1})$ （也叫做时序差分目标）进行计算的，即使用一个状态的估计值来更新该状态的估计值，没有再利用后续状态信息的计算方法。这种方法的好处在于可以将问题分解成只涉及一步的预测，从而简化计算。此外，$ \delta = r_{t+1} + \gamma V (s_{t+1}) - V (s_t)$
被定义为时序差分误差（TD error）。
但有一点需要注意的是，由于基于时步的学习方式，并且终止状态没有下一步，比如当 $V (s_t)$ 是终止状态时，$\gamma V (s_{t+1})$ 是没有意义的。因此时序差分方法在实践过程中会把终止状态单独做一个判断，即将对应未来状态的估计值设置为 $0$ ，然后更新当前状态的估计值，这个过程也被称作回溯，如下式所示，后面所有基于时序差分的方法都会有这样的一个判断。

$$\begin {cases} V (s_t) \leftarrow V (s_t) + \alpha [r_{t+1} - V (s_t)] & \text {对于终止状态} V (s_t) \\ V (s_t) \leftarrow V (s_t) + \alpha [r_{t+1} + \gamma V (s_{t+1}) - V (s_t)] & \text {对于非终止状态} V (s_t) \end {cases}$$

# 时序差分和蒙特卡洛的比较

时序差分方法和蒙特卡洛方法之间的差异如下图

• 时序差分方法可以在线学习（online learning），每走一步就可以更新，效率高。蒙特卡洛方法必须等游戏结束时才可以学习。
• 时序差分方法可以从不完整序列上进行学习。蒙特卡洛方法只能从完整的序列上进行学习。
• 时序差分方法可以在连续的环境下（没有终止）进行学习。蒙特卡洛方法只能在有终止的情况下学习。
• 时序差分方法利用了马尔可夫性质，在马尔可夫环境下有更高的学习效率。蒙特卡洛方法没有假设环境具有马尔可夫性质，利用采样的价值来估计某个状态的价值，在不是马尔可夫的环境下更加有效。

# n 步时序差分

把时序差分方法进一步拓展，之前只是向前自举了一步，即 $TD (0)$ ，我们可以调整为两步，利用两步得到的回报来更新状态的价值，调整 $n$ 步就是 $n$ 步时序差分 (n-step TD)，如下式

$$n=1 (TD) \ \ \ G^{(1)}_t = r_{t+1} + \gamma V (s_{t+1})$$

$$n=2 \ \ \ G^{(2)}_t = r_{t+1} +\gamma r_{t+2} + \gamma^2 V (s_{t+2})$$

$$n= \infty (MC) \ \ \ G^{(\infty)}_t = r_{t+1} + \gamma r_{t+2} + \cdots +\gamma^{T-t-1} r_T$$

我们会发现当 $n$ 趋近于无穷大时，就变成了蒙特卡洛方法，因此可以通过调整自举的步数，来实现蒙特卡洛方法和时序差分方法之间的权衡。这个 $n$ 我们通常会用 $\lambda$ 来表示，即 $TD (\lambda)$ 方法。
以下是一些常见的方法来选择合适的 $\lambda$

• 网格搜索 (Grid Search)：对于给定的一组 $\lambda$ 值，可以通过网格搜索方法在这些值中进行遍历，并评估每个值对应的算法性能。选择在验证集上表现最好的 $\lambda$ 值作为最终的选择。
• 随机搜索 (Random Search)：随机选择一组 $\lambda$ 值，在验证集上评估每个值对应的算法性能。通过多次随机搜索，可以得到更好 $\lambda$ 值。
• 自适应选择：在训练过程中逐渐适应地调整 $\lambda$ 的取值。例如，可以在训练的早期使用较小的 $\lambda$ 值，以更多地依赖单步 TD 误差来减小偏差；在训练的后期逐渐增大 $\lambda$ 值，以更多地依赖多步回报来减小方差。
• 交叉验证 (Cross-validation)：将数据集划分为多个子集，交叉验证不同的 $\lambda$ 值，并平均它们的性能评估结果。这样可以更好地估计不同 $\lambda$ 值的泛化性能。
• 经验取值：在某些情况下，根据先前的经验或已知的任务特性，可以选择一些常用的 $\lambda$ 取值作为初始值，并进一步微调。

需要注意的是，无论使用哪种方法，$\lambda$ 的最佳取值可能因任务、环境和算法的不同而异。因此，选择合适的 $\lambda$ 值是一个实验过程，需要根据具体问题进行调整。在实际应用中，可以结合多种方法来找到最佳的 $\lambda$ 值，以获得更好的性能。

# 免模型控制

# Q-learning 算法

在前章节中我们知道，动作价值函数体现了策略与状态价值函数之间的联系。 因此，为了解决控制问题，我们只需要直接预测动作价值函数，然后在决策时选择动作价值即 $Q$ 值最大对应的动作即可。这样一来，策略和动作价值函数同时达到最优，相应的状态价值函数也是最优的，这就是 $Q-learning$ 算法的思路。
$Q-learning$ 算法更新公式如下：

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

而在时序差分方法中，状态价值函数的更新公式如下：

$$V (s_t) \leftarrow V (s_t) + \alpha [r_{t+1} + \gamma V (s_{t+1}) - V (s_t)]$$

两者的更新方式都是基于时序差分的更新方法。不同的是，动作价值函数更新时是直接拿最大未来动作价值 $\gamma \max_{a} Q (s_{t+1},a)$ 来估计的，而在状态价值函数更新中相当于是拿对应的平均值来估计的。这就会导致这个估计相当于状态价值函数中的估计更不准确，一般称为 Q 值的过估计 ，当然这个过估计仅仅限于以 $Q-learning$ 为基础的算法，不同的算法为了优化这个问题使用了不同的估计方式。

# Q 表格

$Q-learning$ 算法的核心即为上面提到的更新公式，但是仍需要了解算法的相关概念，$Q$ 表格和探索策略。
关于 $Q$ 表格，我们依旧沿用前面机器人寻找终点的问题，现在稍微更改条件：将网格变成 $3 \times 3$ ，不再限制机器人的运动方向，可以向上、下、左、右任意移动，当然每次只能走一格，不能移除边界，奖励函数不变。
我们将机器人的位置当成状态，此时有 9 个状态，4 种动作 $a_1,a_2,a_3,a_4$ (分别对应上、下、左、右)。
而 Q 函数，即状态价值函数是输入状态和动作，输出一个值，由于这里的状态和动作都是离散的，因此可以用一个表格来表示，即 $Q$ 表格

表格的横和列对应状态和动作，数值表示对应的 $Q$ 值，比如最左上角的值表示 $Q (s_1,a_1) = 0$ 。在实践中，我们可以给所有的 $Q$ 预先设一个随机值，此处为了方便全部初始化为 $0$。
值得注意的是，表格中终止状态对应的值必须为 $0$ ，比如此处的终止状态 $s_9$ 对应的 $Q (s_9,a_1)$ ,$Q (s_9,a_1)$ ,$Q (s_9,a_1)$ ,$Q (s_9,a_1)$ 必须为
$0$ ，并且也不参与 $Q$ 值的更新。
现在我们讲讲 $Q$ 值的更新过程与前面涉及的状态价值更新类似。不同的是，状态价值的更新是蒙特卡洛方法，$Q$ 值更新是时序差分方法。具体的做法是，让机器人自行在网格中走动，走到一个状态，就把对应的 $Q$ 值更新一次，将这个过程称为探索。

# 探索策略

理论上，直接根据 $Q$ 函数（即每次选择 $Q$ 值最大对应的动作）来探索是没有问题的。但是由于在探索的过程中 $Q$ 值也是估计出来的，然后还需要利用先前的估计值来更新 $Q$ 值（也就是自举的过程），换句话说，由于自举依赖于先前的估计值，因此这可能会导致估计出的价值函数存在某种程度上的偏差。
$Q-learning$ 算法采用的探索策略名为 $\epsilon - greedy$。该策略指智能体在探索过程中会以 $1-\epsilon$ 的概率按照 $Q$ 函数执行动作，剩下 $\epsilon$ 概率执行随机动作。通常 $\epsilon$ 的值会设置的很小，例如 $0.1$ 。因此通常在实践中，$\epsilon$ 的值还会随着时步的增长而衰减，比如从 $0.1$ 衰减到 $0.01$。
确切的说，以 $1-\epsilon$ 的概率执行动作的过程称之为 利用 (exploitation) ，而以 $\epsilon$ 的概率随机动作的过程称之为 探索 (exploration) 。探索的多少难以定论，这就是大多数强化学习情景中需要面临的探索 - 利用窘境 (exploration-exploitation dilemma)。我们需要在探索和利用之间做一个权衡，这与深度学习中的偏差 - 方差权衡 (Bias-Variance Tradeoff) 如出一辙。
$Q-learning$ 算法的伪代码如下

初始化 Q 表，Q (s,a) 任意设定或为 0，终止状态对应 Q 值必须为 0

for 回合数 = 1, M do:

    初始化状态 s

    for 时步 = 1, T do:

        根据某种策略（如 ε-greedy 策略）选择动作 a

        执行动作 a，观察奖励 r 和新状态 s'

        根据更新公式更新策略

        更新 s ← s'

        a ← 从 Q 表中基于当前策略选择的新动作

    end for

end for

# Sarsa 算法

$Sarsa$ 算法与 $Q-learning$ 是非常类似，但是模式却不同的两类算法，$Q-learning$ 算法被认为是 Off-Policy 算法，而 $Sarsa$ 算法则是 $On-Policy$。
但在形式上，两个算法只是在 $Q$ 值的更新公式上有所不同，$Sarsa$ 算法使用如下更新公式

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

$Sarsa$ 算法直接用下一个状态和动作对应的 $Q$ 值来作为估计值，而 $Q-learning$ 算法则是用下一个状态对应的最大 $Q$ 值。

# 同策略与异策略

尽管 $Q-learning$ 算法和 $Sarsa$ 算法仅在一行更新公式上有所区别，但这两种算法代表的是截然不同的两类算法。我们注意到， $Sarsa$ 算法在训练的过程中当前策略来生成数据样本，并在其基础上进行更新。换句话说，策略评估和策略改进过程是基于相同的策略完成的，这就是 同策略算法 。相应地，像 $Q-learning$ 算法这样从其他策略中获取样本然后利用它们来更新目标策略，我们称作 异策略算法 。
也就是说，异策略算法基本上是从经验池或者历史数据中进行学习的。这两类算法有着不同的优缺点，同策略相对来说更加稳定，但是效率较低。而异策略通常来说更加高效，但是需要让获取样本的策略和更新的策略具备一定的分布匹配条件，以避免偏差。

# Q-learning 算法实践

# 定义训练

强化学习训练会迭代很多个回合（$M$），在每回合中，首先重置环境回到初始化的状态，智能体根据状态选择动作，然后环境反馈中下一个状态和对应的奖励，同时智能体会更新策略，直到回合结束。这其实就是马尔可夫决策过程中智能体与环境互动的过程，写成一段通用的代码如下：

for i_ep in range (train_eps): # 遍历每个回合

    # 重置环境，获取初始状态

    state = env.reset ()  # 重置环境，即开始新的回合

    while True: # 对于比较复杂的游戏可以设置每回合最大的步长，例如 while ep_step<100，即最大步长为 100。

        # 智能体根据策略采样动作

        action = agent.sample_action (state)  # 根据算法采样一个动作

        # 与环境进行一次交互，得到下一个状态和奖励

        next_state, reward, terminated, _ = env.step (action)  # 智能体将样本记录到经验池中

        agent.memory.push (state, action, reward, next_state, terminated) 

        # 智能体更新策略

        agent.update (state, action, reward, next_state, terminated)  

        # 更新状态

        state = next_state  

        # 如果终止则本回合结束

        if terminated:

            break

# 定义算法

强化学习中有几个要素，智能体、环境、经验池（经回放），在实践中也需要逐一定义这些要素。我们一般首先定义智能体，或者说算法，在 $Python$ 中一般定义为类即可。再考虑一下智能体在强化学习中主要负责哪些工作。

# 采样动作

首先在训练中需要采样动作与环境交互，我们可以定义一个类方法，命名为 sample_action ，如下：

class Agent:

    def __init__():

        pass

    def sample_action (self, state):

        ''' 采样动作，训练时用

        '''

        self.sample_count += 1

        # epsilon 是会递减的，这里选择指数递减

        self.epsilon = self.epsilon_end + (self.epsilon_start - self.epsilon_end) * math.exp (- self.sample_count/self.epsilon_decay) 

        # e-greedy 策略

        if np.random.uniform (0, 1) > self.epsilon:

            action = np.argmax (self.Q_table [str (state)]) # 选择 Q (s,a) 最大对应的动作

        else:

            action = np.random.choice (self.n_actions) # 随机选择动作

        return action

这里采用 $\epsilon - greedy$ 策略，其中 $\epsilon$ 会随着采样的步数指数衰减。 在 $Q-learning$ 算法中还有一个重要的元素，即 $Q$ 表，$Q$ 表的作用是输入状态和动作，输出一个即可，我们可以用一个二维的数组来表示，比如 Q_table [0][1] = 0.1 可以表示 $Q (s_0,a_1) = 0.1$（注意 $Python$ 里下标是从 $0$ 开始）。而在我们的示例代码中用了一个默认字典来表示，如下：

self.Q_table  = defaultdict (lambda: np.zeros (n_actions))

这样的好处是从数据结构上来说，默认字典是哈希表结构，二维数组是线性表结构，从哈希表拿出数据的速度会比线性表快。

# 预测动作

此外对于每个智能体在训练中和在测试中采取动作的方式一般是不一样的，因为在训练中需要增加额外的探索策略，而在测试中只需要输出 $Q$
值对应最大的动作即可，如下：

class Agent:

    def __init__():

        pass

    def predict_action (self,state):

        ''' 预测或选择动作，测试时用

        '''

        action = np.argmax (self.Q_table [str (state)])

        return action

# 更新方法

所有强化学习算法的采样动作和预测动作方式几乎是比较固定的，对于每个智能体来说最核心的还是更新网络的方式，在 $Q-learning$ 算法中的更新方式较为简单，而且不需要经验回放，如下：

def update (self, state, action, reward, next_state, terminated):

    Q_predict = self.Q_table [str (state)][action] 

    if terminated: # 终止状态

        Q_target = reward  

    else:

        Q_target = reward + self.gamma * np.max (self.Q_table [str (next_state)]) 

    self.Q_table [str (state)][action] += self.lr * (Q_target - Q_predict)

其中 self.lr 就是更新公式中的 $\alpha$（学习率）。

# 定义环境

训练选用一个低难度的环境： CliffWalking-v0 （中文名 “悬崖寻路” ）。如下图所示，整个环境中共有 48 个网格，其中黄色网格（标号为 36）为起点，绿色网格（标号为 47）为终点，红色的网格表示悬崖，智能体的目标是以最短的路径从起点到终点，并且避开悬崖。

在做强化学习算法时更重要的是要对环境本身的状态、动作和奖励了解。在本环境中，状态根据智能体所处网格的编号确定，动作分为上右下左，分别对应 $a_1,a_2,a_3,a_4$ 。当智能体走到白色网格 (包括起点) 奖励为 $-1$ ，到达终点获得奖励 0，走到边沿、悬崖或终点时结束本回合。
该环境由 OpenAI Gym 开发，它提供了一套标准化的环境，包括经典的控制理论问题和游戏，代码封装较好，只需要一行代码就能定义好环境，如下:

env = gym.make ('CliffWalking-v0')

在 Gym 中我们可以通过以下方式获取环境的状态数和动作数:

n_states = env.observation_space.n # 状态数

n_actions = env.action_space.n # 动作数

print (f"状态数：{n_states}， 动作数：{n_actions}")

# 设置参数

由于 $Q-learning$ 算法的超参数（需要人工调整的参数）比较少，其中 $\gamma$（折扣因子）比较固定，设置在 $0.9$ 到 $0.999$ 之间，一般设置成 $0.99$ 即可。而学习率 $\alpha$ 在本章节中设置的比较大，为 $0.1$ ，实际更复杂的环境和算法中学习率是小于 $0.01$ ，因为太大很容易发生过拟和的问题，只是本节的环境和算法都比较简单，为了收敛得更快所以设置较大。此外由于我们探索策略中的 $\epsilon$ 是会随着采样步数衰减的，在实践过程中既不能让它衰减得太快也不能让它衰减得太慢，因此需要合理设置如下参数：

self.epsilon_start = 0.95 #  e-greedy 策略中 epsilon 的初始值

self.epsilon_end = 0.01 #  e-greedy 策略中 epsilon 的最终值

self.epsilon_decay = 200 #  e-greedy 策略中 epsilon 的衰减率

# 开始训练

这里给出完整的训练代码

# -*- coding:utf--8 -*-

import numpy as np

import math

import torch

from collections import defaultdict

# 定义模型

class Qlearning (object):

    def __init__(self,cfg):

        ''' 智能体类

        Args:

            cfg (class): 超参数类

        '''

        self.n_actions = cfg.n_actions 

        self.exploration_type = 'e-greedy' # 探索策略如 e-greedy ，boltzmann ，softmax， ucb 等

        self.lr = cfg.lr 

        self.gamma = cfg.gamma    

        self.epsilon = cfg.epsilon_start

        self.sample_count = 0  

        self.epsilon_start = cfg.epsilon_start

        self.epsilon_end = cfg.epsilon_end

        self.epsilon_decay = cfg.epsilon_decay

        self.Q_table  = defaultdict (lambda: np.zeros (self.n_actions)) # 使用嵌套字典来表示 Q (s,a)，并将指定所有的 Q_table 创建时， Q (s,a) 初始设置为 0

    def sample_action (self, state):

        ''' 以 e-greedy 策略训练时选择动作 

        Args:

            state (array): 状态

        Returns:

            action (int): 动作

        ''' 

        if self.exploration_type == 'e-greedy':

            action = self._epsilon_greedy_sample_action (state)

        else:

            raise NotImplementedError

        return action

    def predict_action (self,state):

        ''' 预测动作

        Args:

            state (array): 状态

        Returns:

            action (int): 动作

        '''

        if self.exploration_type == 'e-greedy':

            action = self._epsilon_greedy_predict_action (state)

        else:

            raise NotImplementedError

        return action

    def _epsilon_greedy_sample_action (self, state):

        ''' 

        采用 epsilon-greedy 策略进行动作选择 

        Args: 

            state (array): 状态

        Returns: 

            action (int): 动作

        ''' 

        self.sample_count += 1

        # epsilon 值需要衰减，衰减方式可以是线性、指数等，以平衡探索和开发

        self.epsilon = self.epsilon_end + (self.epsilon_start - self.epsilon_end) * \

            math.exp (-1. * self.sample_count/self.epsilon_decay) 

        if np.random.uniform (0, 1) > self.epsilon:

            action = np.argmax (self.Q_table [str (state)]) # 选择具有最大 Q 值的动作

        else:

            action = np.random.choice (self.n_actions) # 随机选择一个动作

        return action

    def _epsilon_greedy_predict_action (self,state):

        ''' 

        使用 epsilon-greedy 算法进行动作预测 

        Args: 

            state (array): 状态

        Returns: 

            action (int): 动作 

        ''' 

        action = np.argmax (self.Q_table [str (state)])

        return action

    def update (self, state, action, reward, next_state, done):

        ''' 更新模型

        Args:

            state (array): 当前状态 

            action (int): 当前动作 

            reward (float): 当前奖励信号 

            next_state (array): 下一个状态 

            done (bool): 表示是否达到终止状态 

        '''

        Q_predict = self.Q_table [str (state)][action] 

        if done: # 终止状态 

            Q_target = reward  

        else:

            Q_target = reward + self.gamma * np.max (self.Q_table [str (next_state)]) 

        self.Q_table [str (state)][action] += self.lr * (Q_target - Q_predict)

    def save_model (self,path):

        '''

        保存模型

        Args:

            path (str): 模型存储路径 

        '''

        import dill

        from pathlib import Path

        # 确保存储路径存在 

        Path (path).mkdir (parents=True, exist_ok=True)

        torch.save (

            obj=self.Q_table,

            f=path+"Qleaning_model.pkl",

            pickle_module=dill

        )

        print ("Model saved!")

    def load_model (self, path):

        '''

        根据模型路径导入模型

        Args:

            fpath (str): 模型路径

        '''

        import dill

        self.Q_table =torch.load (f=path+'Qleaning_model.pkl',pickle_module=dill)

        print ("Mode loaded!")

# 定义模型训练与测试

def train (cfg, env, agent):

    ''' 训练

    '''

    print ("开始训练！")

    rewards = []  # 记录所有回合的奖励

    steps = []

    for i_ep in range (cfg.train_eps):

        ep_reward = 0  # 一轮的累计奖励 

        ep_step = 0

        state = env.reset (seed = cfg.seed)  # 重置环境并获取初始状态

        for _ in range (cfg.max_steps):

            ep_step += 1

            action = agent.sample_action (state)  # 采样动作 

            if cfg.new_step_api:

                next_state, reward, terminated, truncated , info = env.step (action)  # 更新环境并返回新状态、奖励、终止状态、截断标志和其他信息（使用 OpenAI Gym 的 new_step_api）

            else:

                next_state, reward, terminated, info = env.step (action)  # 更新环境并返回新状态、奖励、终止状态和其他信息（使用 OpenAI Gym 的 old_step_api） 

            agent.update (state, action, reward, next_state, terminated)  # 更新 agent

            state = next_state  # 更新状态 

            ep_reward += reward  # 增加奖励 

            if terminated:

                break

        steps.append (ep_step)

        rewards.append (ep_reward)

        if (i_ep + 1) % 10 == 0:

            print (f"回合：{i_ep+1}/{cfg.train_eps}，奖励：{ep_reward:.2f}")

    print ("完成训练！")

    return {'rewards':rewards}

def test (cfg, env, agent):

    print ("开始测试！")

    rewards = []  # 记录所有回合的奖励

    steps = []

    for i_ep in range (cfg.test_eps):

        ep_reward = 0  # 一轮的累计奖励 

        ep_step = 0

        state = env.reset (seed = cfg.seed)  # 重置环境并获取初始状态 

        for _ in range (cfg.max_steps):

            if cfg.render:

                env.render ()

            ep_step += 1

            action = agent.predict_action (state)  # 预测动作 

            next_state, reward, terminated, truncated , info = env.step (action)

            state = next_state  # 更新状态 

            ep_reward += reward  # 增加奖励

            if terminated:

                break

        steps.append (ep_step)

        rewards.append (ep_reward)

        print (f"回合：{i_ep+1}/{cfg.test_eps}，奖励：{ep_reward:.2f}")

    print ("完成测试")

    env.close ()

    return {'rewards':rewards}

# 定义环境

import gymnasium as gym

import os

import random

def all_seed (env,seed = 1):

    ''' 万能的 seed 函数

    '''

    env.reset (seed=seed) # env config

    np.random.seed (seed)

    random.seed (seed)

    torch.manual_seed (seed) # config for CPU

    torch.cuda.manual_seed (seed) # config for GPU

    os.environ ['PYTHONHASHSEED'] = str (seed) # config for python scripts

    # config for cudnn

    torch.backends.cudnn.deterministic = True

    torch.backends.cudnn.benchmark = False

    torch.backends.cudnn.enabled = False

def env_agent_config (cfg):

    env = gym.make (cfg.env_name) # 创建环境

    all_seed (env,seed=cfg.seed)

    print (env.observation_space.shape)

    n_states = env.observation_space.n

    n_actions = env.action_space.n

    print (f"状态空间维度：{n_states}，动作空间维度：{n_actions}")

    # 更新 n_states 和 n_actions 到 cfg 参数中

    setattr (cfg, 'n_states', n_states)

    setattr (cfg, 'n_actions', n_actions) 

    setattr (cfg, 'action_space', env.action_space) 

    agent = Qlearning (cfg)

    return env,agent

# 设置参数

import matplotlib.pyplot as plt

import seaborn as sns

class Config:

    def __init__(self) -> None:

        ## 通用参数

        self.env_name = "CliffWalking-v0" # name of environment

        self.new_step_api = True # whether to use new step api of gym

        self.wrapper = None # wrapper of environment

        self.render = False # whether to render environment

        self.render_mode = "human" # 渲染模式，"human" 或者 "rgb_array"

        self.algo_name = "Qlearning" # name of algorithm

        self.mode = "train" # train or test

        self.mp_backend = "mp" # 多线程框架，ray 或者 mp (multiprocessing)，默认 mp

        self.seed = 1 # random seed

        self.device = "cuda" # device to use

        self.train_eps = 500 # number of episodes for training

        self.test_eps = 10 # number of episodes for testing

        self.eval_eps = 10 # number of episodes for evaluation

        self.eval_per_episode = 5 # evaluation per episode

        self.max_steps = 1000 # max steps for each episode

        self.load_checkpoint = False

        self.load_path = "tasks" # path to load model

        self.show_fig = False # show figure or not

        self.save_fig = True # save figure or not

        ## Qlearing 参数

        self.epsilon_start = 0.95 # epsilon 初始值

        self.epsilon_end = 0.01 # epsilon 终止值

        self.epsilon_decay = 300 # epsilon 衰减率

        self.gamma = 0.90 # 奖励折扣因子

        self.lr = 0.1 # 学习率

def smooth (data, weight=0.9):  

    ''' 用于平滑曲线，类似于 Tensorboard 中的 smooth 曲线

    '''

    last = data [0] 

    smoothed = []

    for point in data:

        smoothed_val = last * weight + (1 - weight) * point  # 计算平滑值

        smoothed.append (smoothed_val)                    

        last = smoothed_val                                

    return smoothed

def plot_rewards (rewards,title="learning curve"):

    sns.set_theme (style="whitegrid")

    plt.figure ()  # 创建一个图形实例，方便同时多画几个图

    plt.title (f"{title}")

    plt.xlim (0, len (rewards))  # 设置 x 轴的范围

    plt.xlabel ('episodes')

    plt.plot (rewards, label='rewards')

    plt.plot (smooth (rewards), label='smoothed')

    plt.legend ()

    plt.show ()

# 开始训练

# 获取参数

cfg = Config () 

# 训练

env, agent = env_agent_config (cfg)

res_dic = train (cfg, env, agent)

plot_rewards (res_dic ['rewards'], title=f"training curve on {cfg.device} of {cfg.algo_name} for {cfg.env_name}")  

# 测试

res_dic = test (cfg, env, agent)

plot_rewards (res_dic ['rewards'], title=f"testing curve on {cfg.device} of {cfg.algo_name} for {cfg.env_name}")  # 画出结果

# 结果分析

根据代码输出的图表，我们发现训练曲线从 50 回合开始收敛，此时智能体学习到了最优策略。同时收敛值在 13 左右波动，波动的原因正是存在 0.01 的随机探索概率。

# 消融实验

为了探究 $\epsilon$ 是随采样步数衰减好还是恒定不变好，我们可以做一个消融实验 (Ablation) ，设定 $\epsilon$ 恒定为 0.1，如下

# 将初始值和最终值设置为一样，这样 epsilon 就不会衰减

self.epsilon_start = 0.1 #  e-greedy 策略中 epsilon 的初始值