Axi's Blog

Back
RL 学习笔记（3）：马尔可夫决策过程Blur image
/ Update
7 min read
Hero Image

RL 学习笔记（3）：马尔可夫决策过程

马尔可夫决策过程
views | comments

引言#

本章介绍马尔可夫决策过程 (Markov Decision Process, MDP)，它是强化学习中用于建模完全可观测环境下的序贯决策问题的标准框架。我们将从基础的马尔可夫性质开始，逐步构建马尔可夫过程 (MP)、马尔可夫奖励过程 (MRP)，最终引出 MDP 及其核心概念，如策略、价值函数和贝尔曼方程。

马尔可夫性质与过程 (Markov Property and Processes)#

马尔可夫性质 (Markov Property)#

  • 定义: 当前状态 StS_t 包含了预测未来所需的所有历史信息。即下一状态 St+1S_{t+1} 的概率分布仅依赖于当前状态 StS_t。 P[St+1∣St]=P[St+1∣S1,…,St]\mathbb{P}[S_{t+1} | S_t] = \mathbb{P}[S_{t+1} | S_1, \dots, S_t]
  • 意义: 当前状态是未来的“充分统计量”，历史信息可被丢弃。环境状态 SeS^e 通常假定满足此性质。

马尔可夫过程 (Markov Process, MP) / 马尔可夫链 (Markov Chain)#

  • 定义: 一个满足马尔可夫性质的随机状态序列，是描述无外部控制（动作）和奖励的系统动态的模型。由元组 (S,P)(\mathcal{S}, \mathcal{P}) 定义：
    • S\mathcal{S}: （有限）状态集合。
    • P\mathcal{P}: 状态转移概率矩阵，Pss′=P[St+1=s′∣St=s]\mathcal{P}_{ss'} = \mathbb{P}[S_{t+1}=s' | S_t=s]。

马尔可夫奖励过程 (Markov Reward Process, MRP)#

  • 定义: 在 MP 基础上增加了奖励和折扣因子。由元组 (S,P,R,γ)(\mathcal{S}, \mathcal{P}, \mathcal{R}, \gamma) 定义：
    • S,P\mathcal{S}, \mathcal{P}: 同 MP。
    • R\mathcal{R}: 奖励函数，Rs=E[Rt+1∣St=s]\mathcal{R}_s = \mathbb{E}[R_{t+1} | S_t=s] (离开状态 ss 的期望立即奖励)。
    • γ\gamma: 折扣因子 (γ∈[0,1]\gamma \in [0, 1])。
  • 回报 (Return) GtG_t: 从 tt 时刻开始的折扣累积奖励。 Gt=∑k=0∞γkRt+k+1=Rt+1+γGt+1G_t = \sum_{k=0}^\infty \gamma^k R_{t+k+1} = R_{t+1} + \gamma G_{t+1}
  • 状态价值函数 (State-Value Function) v(s)v(s): 在 MRP 中，从状态 ss 开始的期望回报。 v(s)≐E[Gt∣St=s]v(s) \doteq \mathbb{E}[G_t | S_t = s]
  • MRP 的贝尔曼方程 (Bellman Equation for MRP): 描述了状态价值与其后继状态价值的关系。 v(s)=Rs+γ∑s′∈SPss′v(s′)v(s) = \mathcal{R}_s + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'} v(s') 矩阵形式: v=R+γPvv = \mathcal{R} + \gamma \mathcal{P} v，可直接求解 v=(I−γP)−1Rv = (I - \gamma \mathcal{P})^{-1} \mathcal{R} (对于小型 MRP)。

马尔可夫决策过程 (Markov Decision Process, MDP)#

MDP 在 MRP 基础上引入了动作和策略，用于形式化完全可观测的 RL 问题。

  1. 定义: 由元组 (S,A,P,R,γ)(\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma) 定义：

    • S\mathcal{S}: 有限状态集。
    • A\mathcal{A}: 有限动作集 (可能依赖于状态 A(s)\mathcal{A}(s))。
    • P\mathcal{P}: 状态转移概率函数，Pss′a=P[St+1=s′∣St=s,At=a]\mathcal{P}_{ss'}^a = \mathbb{P}[S_{t+1}=s' | S_t=s, A_t=a]。
    • R\mathcal{R}: 奖励函数，Rsa=E[Rt+1∣St=s,At=a]\mathcal{R}_s^a = \mathbb{E}[R_{t+1} | S_t=s, A_t=a]。
    • γ\gamma: 折扣因子。

  2. 核心假设: 环境完全可观测 (Ot=SteO_t = S_t^e) 且状态满足马尔可夫性质。

  3. 与相关模型的关系:

    • MAB: 可视为单状态 MDP。
    • POMDP (部分可观测 MDP): 当 Ot≠SteO_t \neq S_t^e 时使用。需要维护信念状态 (Belief State) 并在此空间上求解。

策略与价值函数 (Policy and Value Functions in MDPs)#

在 MDP 中，智能体的行为由策略决定，价值函数用于评估策略的好坏。

  1. 策略 (Policy) π\pi:

    • 定义: 智能体在状态 ss 选择动作 aa 的规则，通常是概率分布 π(a∣s)=P[At=a∣St=s]\pi(a|s) = \mathbb{P}[A_t=a | S_t=s]。
    • 特性: 通常假定是稳态的 (stationary) 和马尔可夫的 (Markovian)。

  2. 固定策略下的 MDP:

    • 给定策略 π\pi，MDP 退化为一个 MRP (S,Pπ,Rπ,γ)(\mathcal{S}, \mathcal{P}^\pi, \mathcal{R}^\pi, \gamma)，其中：
      • Pss′π=∑aπ(a∣s)Pss′a\mathcal{P}_{ss'}^\pi = \sum_a \pi(a|s) \mathcal{P}_{ss'}^a (策略下的状态转移概率)
      • Rsπ=∑aπ(a∣s)Rsa\mathcal{R}_s^\pi = \sum_a \pi(a|s) \mathcal{R}_s^a (策略下的期望奖励)

  3. MDP 的价值函数 (依赖于策略 π\pi):

    • 状态价值函数 vπ(s)v_\pi(s): 从状态 ss 开始，遵循策略 π\pi 的期望回报。 vπ(s)≐Eπ[Gt∣St=s]v_\pi(s) \doteq \mathbb{E}_\pi [G_t | S_t = s]
    • 动作价值函数 qπ(s,a)q_\pi(s, a): 从状态 ss 开始，执行动作 aa，然后遵循策略 π\pi 的期望回报。 qπ(s,a)≐Eπ[Gt∣St=s,At=a]q_\pi(s, a) \doteq \mathbb{E}_\pi [G_t | S_t = s, A_t = a]

  4. 贝尔曼期望方程 (Bellman Expectation Equation):

    • 描述了给定策略 π\pi 下 vπv_\pi 和 qπq_\pi 满足的一致性条件 (线性方程)。
    • vπ(s)v_\pi(s) 的方程: vπ(s)=∑a∈Aπ(a∣s)qπ(s,a)=∑a∈Aπ(a∣s)(Rsa+γ∑s′∈SPss′avπ(s′))v_\pi(s) = \sum_{a \in \mathcal{A}} \pi(a|s) q_\pi(s, a) = \sum_{a \in \mathcal{A}} \pi(a|s) \left( \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a v_\pi(s') \right)
    • qπ(s,a)q_\pi(s, a) 的方程: qπ(s,a)=Rsa+γ∑s′∈SPss′avπ(s′)=Rsa+γ∑s′∈SPss′a∑a′∈Aπ(a′∣s′)qπ(s′,a′)q_\pi(s, a) = \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a v_\pi(s') = \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a \sum_{a' \in \mathcal{A}} \pi(a'|s') q_\pi(s', a')

最优性 (Optimality in MDPs)#

RL 的目标是找到使期望回报最大化的最优策略。

  1. 最优价值函数:

    • 最优状态价值函数 v∗(s)v_*(s): 所有策略中可能达到的最大期望回报。 v∗(s)=max⁡πvπ(s)v_*(s) = \max_\pi v_\pi(s)
    • 最优动作价值函数 q∗(s,a)q_*(s, a): 执行动作 aa 后遵循最优策略能达到的最大期望回报。 q∗(s,a)=max⁡πqπ(s,a)q_*(s, a) = \max_\pi q_\pi(s, a)

  2. 最优策略 π∗\pi_*:

    • 定义: 能够达到最优价值函数的策略，即 vπ∗(s)=v∗(s)v_{\pi_*}(s) = v_*(s) 对所有 ss 成立。
    • 存在性: 至少存在一个最优策略，且总能找到确定性的最优策略。
    • 从 q∗q_* 导出 π∗\pi_*: 通过贪心选择： π∗(a∣s)=1  ⟺  a=arg⁡max⁡a′∈Aq∗(s,a′)\pi_*(a|s) = 1 \iff a = \arg\max_{a' \in \mathcal{A}} q_*(s, a')
    • 从 v∗v_* 导出 π∗\pi_* (需要模型): 通过一步前看来选择： π∗(a∣s)=1  ⟺  a=arg⁡max⁡a′∈A(Rsa′+γ∑s′Pss′a′v∗(s′))\pi_*(a|s) = 1 \iff a = \arg\max_{a' \in \mathcal{A}} \left( \mathcal{R}_s^{a'} + \gamma \sum_{s'} \mathcal{P}_{ss'}^{a'} v_*(s') \right)

  3. 贝尔曼最优方程 (Bellman Optimality Equation):

    • 描述了最优价值函数 v∗v_* 和 q∗q_* 必须满足的一致性条件 (非线性方程)。
    • v∗(s)v_*(s) 的方程: v∗(s)=max⁡a∈Aq∗(s,a)=max⁡a∈A{Rsa+γ∑s′∈SPss′av∗(s′)}v_*(s) = \max_{a \in \mathcal{A}} q_*(s, a) = \max_{a \in \mathcal{A}} \left\{ \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a v_*(s') \right\}
    • q∗(s,a)q_*(s, a) 的方程: q∗(s,a)=Rsa+γ∑s′∈SPss′av∗(s′)=Rsa+γ∑s′∈SPss′amax⁡a′∈Aq∗(s′,a′)q_*(s, a) = \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a v_*(s') = \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a \max_{a' \in \mathcal{A}} q_*(s', a')
    • 特性: 由于 max⁡\max 算子，方程是非线性的，通常无法直接求解。
    • 求解方法: 需使用迭代算法，如价值迭代、策略迭代 (动态规划，需要模型) 或 Q学习、Sarsa (强化学习，无需模型)。
RL 学习笔记（3）：马尔可夫决策过程
https://axi404.top/blog/rl-note-3
Author 阿汐
Published at April 10, 2025
Copyright CC BY-NC-SA 4.0
Buy me a cup of coffee ☕.

RL 学习笔记（4）：动态规划

RL 学习笔记（2）：赌博机问题
Comment seems to stuck. Try to refresh?✨