Skip to content

约 2935 个字 5 张图片 预计阅读时间 15 分钟 共被读过 次

#RL

第2章 马尔可夫决策过程（MDP）总结

2.1 马尔可夫过程（MP）

2.1.1 马尔可夫性质

  • 定义：未来状态仅依赖当前状态，与历史无关：
\[ p(X_{t+1} | X_{0:t}) = p(X_{t+1} | X_t) \]
  • 意义：简化状态转移建模，无需考虑完整历史。

2.1.2 马尔可夫链

  • 状态转移矩阵：描述状态间转移概率的矩阵：

$$

P = \begin{pmatrix}
p(s_1|s_1) & \cdots & p(s_N|s_1) \
\vdots & \ddots & \vdots \
p(s_1|s_N) & \cdots & p(s_N|s_N)
\end{pmatrix}
$$

  • 示例：图2.2中的4状态马尔可夫链，转移概率如
    image.png

2.2 马尔可夫奖励过程（MRP）

2.2.1 回报与价值函数

  • 回报：折扣奖励之和：
\[ G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \dots \]
  • 价值函数：期望回报：
\[ V(s) = \mathbb{E}[G_t | s_t = s] \]
使用折扣因子 \(\lambda\) 的原因
  • 有些马尔可夫过程是带环的，它并不会终结，我们想避免无穷的奖励
  • 我们并不能建立完美的模拟环境的模型，我们对未来的评估不一定是准确的，我们不一定完全信任模型，因为这种不确定性，所以我们对未来的评估增加一个折扣。我们想把这个不确定性表示出来，希望尽可能快地得到奖励，而不是在未来某一个点得到奖励
  • 如果奖励是有实际价值的，我们可能更希望立刻就得到奖励，而不是后面再得到奖励（现在的钱比以后的钱更有价值）。最后，我们也更想得到即时奖励
  • 有些时候可以把折扣因子设为 0（γ=0），我们就只关注当前的奖励。我们也可以把折扣因子设为 1（γ=1），对未来的奖励并没有打折扣，未来获得的奖励与当前获得的奖励是一样的。折扣因子可以作为强化学习智能体的一个超参数（hyperparameter）来进行调整，通过调整折扣因子，我们可以得到不同动作的智能体

2.2.2 贝尔曼方程

  • 公式：状态价值分解为即时奖励与未来折扣价值：
\[ V(s) = R(s) + \gamma \sum_{s'} p(s'|s) V(s') \]
  • 矩阵形式：
\[ \begin{align} V &= R + \gamma P V \quad \Rightarrow \quad \\ V &= (I - \gamma P)^{-1} R \end{align} \]
  • 解法：
    • 蒙特卡洛采样：
      从某个状态开始，把小船放到状态转移矩阵里面，让它“随波逐流”，这样就会产生一个轨迹。产生一个轨迹之后，就会得到一个奖励，那么直接把折扣的奖励即回报 \(g\) 算出来。算出来之后将它积累起来，得到回报 \(G_{t}\) ​。当积累了一定数量的轨迹之后，我们直接用 \(G_{t}\) ​ 除以轨迹数量，就会得到某个状态的价值。
      image.png
    • 动态规划
      一直迭代贝尔曼方程，直到价值函数收敛，我们就可以得到某个状态的价值。我们通过自举（bootstrapping) 的方法不停地迭代贝尔曼方程，当最后更新的状态与我们上一个状态的区别并不大的时候，更新就可以停止，我们就可以输出最新的 V′(s) 作为它当前的状态的价值。这里就是把贝尔曼方程变成一个贝尔曼更新（Bellman update），这样就可以得到状态的价值。
      image.png

2.3 马尔可夫决策过程（MDP）

2.3.1 核心概念

  • 动作空间：状态转移和奖励函数依赖动作：
\[ p(s'|s,a), \quad R(s,a) \]
  • 策略：动作选择概率分布：
\[ \pi(a|s) = p(a_t=a | s_t=s) \]

2.3.2 价值函数与Q函数

  • 状态价值函数：
\[ V_\pi(s) = \mathbb{E}_\pi[G_t | s_t = s] \]
  • 动作价值函数（Q函数）：
\[ Q_\pi(s,a) = \mathbb{E}_\pi[G_t | s_t = s, a_t = a] \]
  • 关系：
\[ V_\pi(s) = \sum_a \pi(a|s) Q_\pi(s,a) \]

2.3.3 贝尔曼期望方程

  • 状态价值方程：
\[ V_\pi(s) = \sum_a \pi(a|s) \left( R(s,a) + \gamma \sum_{s'} p(s'|s,a) V_\pi(s') \right) \]
  • Q函数方程：
\[ Q_\pi(s,a) = R(s,a) + \gamma \sum_{s'} p(s'|s,a) V_\pi(s') \]

2.3.4 备份图（Backup Diagram）

  • 定义：用于可视化价值函数和Q函数的迭代关系，表示状态或动作的价值如何从后续状态传播。
  • 符号说明：
  • 空心圆圈：状态节点。
  • 实心圆圈：动作节点。
  • 箭头：价值传递路径。
  • 核心逻辑：
  • 状态价值函数：从状态节点出发，汇总所有动作的期望价值（图2.10）。
  • Q函数：从动作节点出发，汇总所有后续状态的期望价值（图2.12）。
  • 公式关联：

$$
V_\pi(s) = \sum_a \pi(a|s) \left( R(s,a) + \gamma \sum_{s'} p(s'|s,a) V_\pi(s') \right)

$$

2.3.5 策略评估（Policy Evaluation）

  • 目标：计算给定策略 \(\pi\) 的状态价值函数 \(V_\pi(s)\)。
  • 方法：
  • 同步备份：每次迭代更新所有状态的价值（资源消耗大）。
  • 异步备份：仅更新部分状态，提高效率（如优先更新变化大的状态）。
  • 迭代公式：
\[ V_{k+1}(s) = \sum_a \pi(a|s) \left( R(s,a) + \gamma \sum_{s'} p(s'|s,a) V_k(s') \right) \]

2.3.6 预测与控制

预测（Prediction）

  • 输入：MDP + 策略 \(\pi\)。
  • 输出：价值函数 \(V_\pi(s)\)。
  • 示例：评估随机策略在网格世界中的价值。

控制（Control）

  • 输入：MDP。
  • 输出：最优价值函数（optimal value function) \(V^*\) 和最优策略（optimal policy） \(\pi^*\) 。
  • 方法：策略迭代、价值迭代。
  • 示例：网格世界中找到最短路径。

2.3.7 动态规划（Dynamic Programming）

  • 适用条件：
  • 最优子结构：问题可分解为子问题。
  • 重叠子问题：子问题重复出现，可缓存结果。
  • MDP中的应用：
  • 已知状态转移概率 \(p(s'|s,a)\) 和奖励函数 \(R(s,a)\)。
  • 通过贝尔曼方程递归求解价值函数。

2.3.8 马尔可夫决策过程中的策略评估

  • 步骤：
    1. 初始化价值函数 \(V_0(s)=0\)。
    2. 迭代应用贝尔曼期望方程直至收敛。
  • 示例：小网格世界中随机策略的评估。

2.3.9 马尔可夫决策过程控制

  • 目标：寻找最优策略 \(\pi^*\)，最大化长期奖励。
  • 核心方法：
  • 策略迭代：交替进行策略评估与改进。
  • 价值迭代：直接优化价值函数，再提取策略。

2.3.10 策略迭代（Policy Iteration）

  • 步骤：
    1. 策略评估：计算当前策略的价值函数 \(V_\pi\)。
    2. 策略改进：贪心更新策略 \(\pi'(s) = \arg\max_a Q_\pi(s,a)\)。
    3. 重复直至策略稳定。
  • 特点：保证收敛到最优策略，但计算量大。
    image.png

2.3.11 价值迭代（Value Iteration）

  • 核心方程：贝尔曼最优方程：
\[ V_{k+1}(s) = \max_a \left( R(s,a) + \gamma \sum_{s'} p(s'|s,a) V_k(s') \right) \]
  • 步骤：
    1. 初始化 \(V_0(s)=0\)。
    2. 迭代更新价值函数至收敛。
    3. 提取最优策略：\(\pi^*(s) = \arg\max_a Q^*(s,a)\)。
  • 特点：快速收敛，但忽略中间策略。
    image.png

2.3.12 策略迭代 vs 价值迭代

对比维度 策略迭代 价值迭代
核心方程 贝尔曼期望方程 贝尔曼最优方程
步骤 评估→改进→循环 直接迭代价值函数→提取策略
收敛速度 慢（需完整策略评估） 快（仅优化价值函数）
中间策略有效性 每一步策略均有效 中间价值函数无策略意义
适用场景 需精确策略优化 快速求最优价值

2.3.13 预测与控制总结

任务 输入 输出 核心方法
预测 MDP + 策略 \(\pi\) \(V_\pi(s)\) 贝尔曼期望方程迭代
控制 MDP \(V^*\), \(\pi^*\) 策略迭代/价值迭代

2.4 关键词

马尔可夫性质（Markov property，MP）：如果某一个过程未来的状态与过去的状态无关，只由现在的状态决定，那么其具有马尔可夫性质。换句话说，一个状态的下一个状态只取决于它的当前状态，而与它当前状态之前的状态都没有关系。

马尔可夫链（Markov chain）： 概率论和数理统计中具有马尔可夫性质且存在于离散的指数集（index set）和状态空间（state space）内的随机过程（stochastic process）。

状态转移矩阵（state transition matrix）：状态转移矩阵类似于条件概率（conditional probability），其表示当智能体到达某状态后，到达其他所有状态的概率。矩阵的每一行描述的是从某节点到达所有其他节点的概率。

马尔可夫奖励过程（Markov reward process，MRP）： 本质是马尔可夫链加上一个奖励函数。在马尔可夫奖励过程中，状态转移矩阵和它的状态都与马尔可夫链的一样，只多了一个奖励函数。奖励函数是一个期望，即在某一个状态可以获得多大的奖励。

范围（horizon）：定义了同一个回合（episode）或者一个完整轨迹的长度，它是由有限个步数决定的。

回报（return）：把奖励进行折扣（discounted），然后获得的对应的奖励。

贝尔曼方程（Bellman equation）：其定义了当前状态与未来状态的迭代关系，表示当前状态的价值函数可以通过下个状态的价值函数来计算。贝尔曼方程因其提出者、动态规划创始人理查德 ⋅⋅ 贝尔曼（Richard Bellman）而得名，同时也被叫作“动态规划方程”。贝尔曼方程即 V(s)=R(s)+γ∑s′∈SP(s′∣s)V(s′)V(s)=R(s)+γ∑s′∈S​P(s′∣s)V(s′) ，特别地，其矩阵形式为 V=R+γPVV=R+γPV。

蒙特卡洛算法（Monte Carlo algorithm，MC algorithm）： 可用来计算价值函数的值。使用本节中小船的例子，当得到一个马尔可夫奖励过程后，我们可以从某一个状态开始，把小船放到水中，让它随波流动，这样就会产生一个轨迹，从而得到一个折扣后的奖励 gg 。当积累该奖励到一定数量后，用它直接除以轨迹数量，就会得到其价值函数的值。

动态规划算法（dynamic programming，DP）： 其可用来计算价值函数的值。通过一直迭代对应的贝尔曼方程，最后使其收敛。当最后更新的状态与上一个状态差距不大的时候，动态规划算法的更新就可以停止。

Q函数（Q-function）： 其定义的是某一个状态和某一个动作所对应的有可能得到的回报的期望。

马尔可夫决策过程中的预测问题：即策略评估问题，给定一个马尔可夫决策过程以及一个策略 ππ ，计算它的策略函数，即每个状态的价值函数值是多少。其可以通过动态规划算法解决。

马尔可夫决策过程中的控制问题：即寻找一个最佳策略，其输入是马尔可夫决策过程，输出是最佳价值函数（optimal value function）以及最佳策略（optimal policy）。其可以通过动态规划算法解决。

最佳价值函数：搜索一种策略 ππ ，使每个状态的价值最大，V∗V∗ 就是到达每一个状态的极大值。在极大值中，我们得到的策略是最佳策略。最佳策略使得每个状态的价值函数都取得最大值。所以当我们说某一个马尔可夫决策过程的环境可解时，其实就是我们可以得到一个最佳价值函数。