第3章. 有限马尔可夫决策过程

第3章. 有限马尔可夫决策过程#

马尔可夫决策过程（Markov Decision Processes，MDPs）是对序贯决策的一种形式化描述，在这种过程中，动作既会影响即时奖励，也会影响后续状态，进而影响未来的奖励。因此，必须考虑即时奖励和延迟奖励之间的权衡。

回顾一下，在多臂老虎机问题中，我们估计每个动作 \(a\) 的价值 \(q_\star(a)\)。而在马尔可夫决策过程中，我们需要估计在每个状态 \(s\) 下每个动作 \(a\) 的价值 \(q_\star(s, a)\)（状态-动作价值），或者在最优动作选择下每个状态 \(s\) 的价值 \(v_\star(s)\)（状态价值）。这些符号的含义将在本章后面进行解释。

3.1 智能体-环境接口（Agent-Environment Interface）#

  • 马尔可夫决策过程的图示：马尔可夫决策过程旨在直接描述智能体与环境之间的交互学习问题，以实现某个目标，图示如下：

    Agent Environment Interaction

    • 解释：

      • 智能体（Agent）：学习者和决策者。

      • 环境（Environment）：智能体与之交互的实体，包括智能体之外的一切。

      • 交互过程：在时间步 \(t\)，智能体接收环境状态 \(S_t \in S\) 的表示，在此基础上选择一个动作 \(A_t \in A(s)\)。作为结果，它随后会收到一个数值奖励 \(R_{t + 1} \in R \subset \mathbb{R}\)，并进入一个新的环境状态 \(S_{t + 1} \in S\)。

      • 轨迹（Trajectory）：由交互过程产生的序列：\(s_0, a_0, r_1, s_1, a_1, r_2, ... , s_t, a_t, r_{t + 1}\)（有时在讨论马尔可夫决策过程时，我们会直接提及这类序列）。

  • 马尔可夫决策过程的动态特性：在一个有限马尔可夫决策过程（Finite MDP）中（集合 \(S\)、\(A\)、\(R\) 都具有有限个元素，因此 \(S_t\)、\(R_t\) 具有明确定义的离散概率分布，且仅依赖于前一个状态和动作，即马尔可夫性质（Markov Property）），有限马尔可夫决策过程的动态特性可以用以下形式表示：

    \[\begin{split} p(s', r | s, a) \dot= Pr(S_{t+1}=s', R_{t+1}=r | A_t=a, S_t=s) \\ \text{with} \sum_{s' \in S} \sum_{ r\in R} p(s', r | s, a) = 1, \text{for all} \ s \in S, a \in A(s) \end{split}\]

  • 有用的推导：在已知马尔可夫决策过程的动态特性后，我们可以计算出关于环境的任何我们想知道的信息：

    • 状态转移概率（State-transition Probability）：

      \[ p(s' | s, a) \dot= Pr(S_{t+1}=s' | A_t=a, S_t=s) = \sum_{r \in R}p(s', r | s, a) \]

    • 状态-动作对的期望奖励（Expected Reward for State-Action Pairs）：

      \[ r(s,a) \dot= E[R_{t+1}|S_t=s, A_t=a] = \sum_{r \in R} r \sum_{s' \in S}p(s', r|s, a) \]

    • 状态-动作-下一状态三元组的期望奖励（Expected Reward for State-Action-Next-State Triples）：

      \[ r(s, a, s') \dot= \mathbb{E}[R_t \mid S_{t-1} = s, A_{t-1} = a, S_t = s'] = \sum_{r \in \mathcal{R}} r \frac{p(s', r \mid s, a)}{p(s' \mid s, a)}. \]

3.2 关于奖励和回报（About Rewards and Returns）#

3.2.1 目标和奖励（Goals and Rewards）#

  • 奖励的定义：在强化学习中，智能体的目标或目的通过一个特殊的标量信号来形式化，这个信号称为奖励（Reward）（\(R_t \in R\)），它从环境传递给智能体。

    请注意，奖励信号是你向智能体传达你希望它实现的目标的方式，而不是你希望它如何实现目标，即奖励信号不考虑实现过程。

  • 奖励假设：通过最大化累积奖励来使智能体表现出期望行为的想法基于奖励假设（Reward Hypothesis）：即我们所说的所有目标和目的都可以被视为最大化奖励累积和的期望值。

3.2.2 回报和回合（Returns and Episodes）#

  • 目标：一般来说，我们寻求最大化一系列奖励的期望回报（Expected Return） \(G_t\)：

    • 对于回合制任务（Episodic Tasks）：

      \[ G_t \dot= R_{t+1} + R_{t+2} + ... + R_{T} \]

    • 对于连续任务（Continuing Tasks）：

      \[\begin{split} \begin{align*} G_t \ &\dot= \ R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... \\ &= \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \\ &= R_{t+1} + \gamma \times G_{t+1} \end{align*} \end{split}\]

  • 两种类型任务的详细信息：

    • 回合制任务：回合在一个称为**终止状态（Terminal State）**的特殊状态下结束，随后重置到一个标准的起始状态或从起始状态的标准分布中采样得到的状态。请注意：

      • 下一个回合的开始与前一个回合的结束方式无关。

      • 所有回合都可以被认为在同一个终止状态结束。

      • 符号 \(S^+\) 用于表示所有非终止状态加上终止状态的集合。

    • 连续任务：相反，连续任务是指智能体-环境交互不会自然地分解为可识别的回合，而是无限制地持续进行的任务。请注意，在连续情况下：

      • \(\gamma \in (0,1)\) 称为折扣率（Discount Rate），用于表示智能体对即时奖励和未来奖励的偏好。\(\gamma\) 越接近 1，智能体就越”有远见”。

      • 尽管 \(G_t\) 是无穷多项的和，但如果奖励是非零且恒定的，并且 \(\gamma \in (0,1)\)，那么它仍然是有限的。

      • 连续任务的特殊情况：如果奖励信号始终为 +1，那么：

        \[ G_t = \sum_{k=0}^{\infty} \gamma^k = \frac{1}{1 - \gamma} \]

      • 符号 \(S\) 用于表示所有非终止状态的集合。

  • 两种类型任务的示例：平衡杆问题（可以是回合制或连续任务）

    Example of Cart-Pole

    • 目标：对沿着轨道移动的小车施加力，以使铰接在小车上的杆子不倒下。每次失败后，杆子会重置为垂直状态。

    • 回合制视角：

      • 描述：这个任务可以被视为回合制任务，自然的回合就是反复尝试平衡杆子的过程。

      • 奖励：在这种情况下，奖励可以是在每次未发生失败的时间步给予 \(+1\)。

      • 回报：每个时间的回报将是直到失败的步数。

    • 连续视角：

      • 描述：我们也可以将其视为连续任务，使用折扣。

      • 奖励：在这种情况下，每次失败的奖励为 \(-1\)，其他时间为零。

      • 回报：那么每个时间步的回报将与 \(-\gamma^K\) 相关，其中 \(K\) 是失败前的时间步数。通过尽可能长时间地保持杆子平衡来最大化回报。

3.2.3 回合制和连续任务的统一表示（Unified Notation for Episodic and Continuing Tasks）#

在实践中，当我们讨论回合制任务时，几乎不需要区分不同的回合。通过将回合终止视为进入一个特殊的吸收状态（Absorbing State），可以将这两种类型的任务统一起来。这个吸收状态只会转移到自身，并且只会产生零奖励。

Absorbing State

因此，回合制和连续任务的期望回报现在都可以写成 \(G_t = \sum_{k = 0}^{\infty} \gamma^k R_{t + k + 1}\)

3.3 策略和价值函数（Policies and Value Functions）#

几乎所有的强化学习算法都涉及估计价值函数（Value Functions），即关于状态（或状态-动作对）的函数，用于估计智能体处于给定状态（或采取特定动作）的好坏程度。在本节中，我们首先定义策略：

  • 定义：形式上，**策略（Policy）**是从状态到选择每个可能动作的概率的映射：

    \[ \pi(a|s) = Pr(A_t=a|S_t=s) \]

    然后我们介绍用于递归计算价值函数（包括状态价值函数和动作价值函数）的贝尔曼方程（Bellman Equations）和贝尔曼最优方程（Bellman Optimality Equations）。

3.3.1 贝尔曼方程（可选课程视频）#

  • 在策略 \(\pi\) 下状态 \(s\) 的价值函数（State-Value Function under Policy \(\pi\)）：是从状态 \(s\) 开始并随后遵循策略 \(\pi\) 时的期望回报：

    \[\begin{split} \begin{align*} v_\pi(s) \ &\dot= \ \mathbb{E}_{\pi}[G_t|S_t=s] \\ &= \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty}\gamma^k R_{t+k+1} | S_t=s\right] \\ &= \colorbox{lightyellow}{$\sum_a \pi(a|s)q(s,a)$} \\ &= \sum_a \pi(a|s) \sum_{s', r}p(s', r|s, a) [r + \gamma \mathbb{E}_{\pi}[G_{t+1}|S_{t+1}=s']] \\ &= \colorbox{lightyellow}{$\sum_a \pi(a|s) \sum_{s', r}p(s', r|s, a) [r + \gamma v_\pi(s')]$} \quad (\text{Bellman equation for} \ v_\pi) \end{align*} \end{split}\]

    • 状态是价值函数的自变量，即对于每个输入状态，状态价值函数会赋予一个相应的状态值。

    • 状态价值函数总是由策略定义的，当改变策略时，得到的状态价值函数通常会不同。

    • 上面的最终方程称为关于 \(v_\pi\) 的贝尔曼方程，它表达了一个状态的价值与其后继状态的价值之间的关系。可以借助下面关于 \(v_\pi\) 的回溯图（Backup Diagram）来理解贝尔曼方程：

      Backup diagram for v

      回溯操作（从底部的 \(s'\) 到顶部的 \(s\)）将价值信息从后续状态传递回当前状态。

  • 策略 \(\pi\) 下的动作价值函数（Action-Value Function under Policy \(\pi\)）：是指从状态 \(s\) 开始，采取动作 \(a\)，并随后遵循策略 \(\pi\) 时的期望回报：

    \[\begin{split} \begin{align*} q_\pi(s,a) \ &\dot= \ \mathbb{E}_{\pi}[G_t|S_t=s, A_t=a] \\ &= \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty}\gamma^k R_{t+k+1} | S_t=s, A_t=a\right] \\ &= \colorbox{lightyellow}{$\sum_{s', r} p(s', r|s, a) (r + \gamma v(s'))$} \\ &= \sum_{s', r} p(s', r|s, a) (r + \gamma \sum_{a'} \pi(a'|s')\mathbb{E}_{\pi}[G_{t+1}|S_{t+1}=s', A_{t+1}=a']) \\ &= \colorbox{lightyellow}{$\sum_{s', r} p(s', r|s, a) [r+ \gamma \sum_{a'} \pi(a'|s') q_\pi(s', a')]$} \quad (\text{Bellman equation for} \ q_\pi) \end{align*} \end{split}\]

    • 同样，\(q_\pi(s,a)\) 是状态 \(s\) 和动作 \(a\) 的函数，并且是针对策略 \(\pi\) 唯一定义的。

    • 关于 \(q_\pi(s,a)\) 的贝尔曼方程可以借助下面的回溯图来理解：

      Backup diagram for 1

  • Gridworld示例（课程视频）

    观看与以下图片链接的视频，它给出了在网格世界环境中如何计算贝尔曼方程的生动示例。如果图片不可点击，请点击 此链接

    Video: Gridworld Example

3.3.2 贝尔曼最优方程 (可选课程视频)#

  • 最优策略（Optimal Policy）：如果您觉得文本定义过于抽象，这个课程视频 会深入介绍最优策略。

    • 更优或相等策略：如果对于所有的 \(s \in S\)，都有 \(v_\pi(s) \ge v_{\pi'}(s)\)，则定义策略 \(\pi\) 比另一个策略 \(\pi'\) 更优或相等。

      • 最优策略（\(\pi_\star\)）：一个 最优策略 \(\pi_\star\) 是比任何其他策略都更优或相等的策略。形式上：

        • \(\pi_\star\) 一定存在。

        • 可能存在多个最优策略。

  • 最优价值函数（Optimal Value Functions）：

    • 最优状态价值函数：最优状态价值函数（Optimal State-Value Function） 定义为：

    \[ v_\star(s) \dot= \max_{\pi} v_\pi(s) \text{ 对于所有的 } s \in S \]

    • 最优动作价值函数：最优动作价值函数（Optimal Action-Value Function） 定义为：

    \[ q_\star(s, a) \dot= \max_{\pi} q_\pi(s, a) \text{ 对于所有的 } s \in S, a \in A(s) \]

  • 贝尔曼最优方程（Bellman Optimality Equation）：

    • 对于 \(v_\star(s)\)（也写作 \(v_{\pi_\star}(s)\)）：

    \[\begin{split} \begin{align*} v_\star(s) &= \colorbox{lightyellow}{$ \underset{a \in A(s)}{\max} q_\star(s,a)$} \\ &= \underset{a}{\max} E_{\pi_\star}[R_{t+1} + \gamma G_{t+1} | S_t=s, A_t=a] \\ &= \underset{a}{\max} E_{\pi_\star}[R_{t+1} + \gamma v_\star(s') | S_t=s, A_t=a] \\ &= \colorbox{lightyellow}{$ \underset{a}{\max} \sum_{s', r}p(s',r|s,a) (r+\gamma v_\star(s'))$} \end{align*} \end{split}\]

    • 对于 \(q_\star(s,a)\)（也写作 \(q_{\pi_\star}(s,a)\)）：

    \[\begin{split} \begin{align*} q_\star(s,a) &= E_{\pi_\star}[R_{t+1} + \gamma v_\star(s') | S_t=s, A_t=a] \\ &= \colorbox{lightyellow}{$ \underset{s', r}{\sum} p(s', r|s,a) [r+\gamma v_\star(s')] $}\\ &= \colorbox{lightyellow}{$ \underset{s', r}{\sum} p(s', r|s,a) [r+ \gamma \ \max_a q_\star(s',a')]$} \end{align*} \end{split}\]

    • 同样，借助下面这两个回溯图可以轻松记住贝尔曼最优方程：

      Backup diagram for $v_{\star}$ and $q_{\star}$

      • 请记住，\(v_\star(s) = \underset{a \in A(s)}{\max} q_\star(s,a)\) 是推导两个贝尔曼最优方程的关键。

  • 我们在做什么：此时您可能很容易对我们正在做的事情感到困惑。简而言之，强化学习过程最终需要的是（近似）最优策略，它支持我们（或者应该说，智能体）的决策。

    可以通过最优价值函数推导出最优策略，而最优价值函数可以通过贝尔曼最优方程求解。更详细地说：

    • 贝尔曼最优方程实际上是一个方程组，每个状态对应一个方程。因此，如果有 \(n\) 个状态，那么就有 \(n\) 个包含 \(n\) 个未知数的方程。如果环境的动态特性 \(p\) 是已知的，那么原则上可以求解这个方程组得到 \(v_\star\)。

    • 任何相对于最优状态价值函数 \(v_\star\) 是贪婪的策略都是最优策略，因为 \(v_\star\) 已经考虑了所有可能的未来行为的奖励后果。

    在现实中，最优动作价值函数 \(q_\star\) 通常更受欢迎，有了它，无需了解环境的动态特性就可以做出决策。（另一方面，\(v_\star\) 只有在环境动态特性已知——即可能的后续状态及其值已知时才能用于决策）

3.4 总结#

  • 关键要点：

    1. 马尔可夫决策过程基础：

      • 马尔可夫决策过程对序贯决策进行建模，其中动作会影响即时和未来的奖励。

      • 马尔可夫性质表明，下一个状态仅取决于当前状态和动作。

    2. 智能体 - 环境交互：

      • 智能体做出决策；环境提供状态和奖励反馈。

      • 轨迹是一系列状态、动作和奖励： \((s_0, a_0, r_1, s_1, a_1, r_2, \ldots)\)。

    3. 马尔可夫决策过程动态特性：

      • 转移概率：\(p(s', r | s, a) = \Pr(S_{t+1} = s', R_{t+1} = r | S_t = s, A_t = a)\)。

      • 期望奖励： \(r(s, a) = \mathbb{E}[R_{t+1} | S_t = s, A_t = a]\)。

    4. 奖励与回报：

      • 奖励信号定义了智能体应该实现的目标，而不是如何实现它。

      • 回报 \(G_t\) 是奖励的累积和：

        • 回合制任务：\(G_t = R_{t+1} + R_{t+2} + \ldots + R_T\)。

        • 持续任务： \(G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}\)， 其中 \(\gamma\) 是折扣因子 \((0 < \gamma < 1)\)。

    5. 策略与价值函数：

      • 策略 \(\pi\) 将状态映射到动作概率：\(\pi(a|s) = \Pr(A_t = a | S_t = s)\)。

      • 状态价值函数 \(v_\pi(s)\)： \(v_\pi(s) = \mathbb{E}_\pi[G_t | S_t = s]\)。

      • 动作价值函数 \(q_\pi(s, a)\)： \(q_\pi(s, a) = \mathbb{E}_\pi[G_t | S_t = s, A_t = a]\)。

    6. 贝尔曼（最优）方程：有关其推导，请参考 3.3 节

    Note

    显式求解贝尔曼最优方程为寻找最优策略提供了一条途径，从而解决强化学习问题。然而，这种解决方案很少直接有用——它至少依赖于三个在实践中很少成立的假设：

    1. 我们准确知道环境的动态特性\(p\)；

    2. 我们有足够的计算资源来完成解决方案的计算；以及

    3. 马尔可夫性质。

    即使在满足条件 1 和 3 的简单表格设置中，状态的数量也可能轻易超出任何当前超级计算机的处理能力。因此，还有其他强化学习方法可以理解为 近似求解贝尔曼最优方程，将在后续章节中介绍。

Contents