Week 2: 序贯决策建模 - 马尔可夫决策过程 (MDP)

回顾：强化学习核心要素

上周我们介绍了强化学习的基本概念：

智能体 (Agent): 学习者和决策者。
环境 (Environment): 智能体交互的外部世界。
状态 (State, S): 环境的当前状况。
动作 (Action, A): 智能体可以采取的操作。
奖励 (Reward, R): 对动作的即时反馈。
策略 (Policy, π): 智能体的行为方式 (状态 -> 动作)。
值函数 (Value Function, V/Q): 状态或状态-动作对的长期价值评估。
核心挑战: 平衡探索 (Exploration) 与利用 (Exploitation)。

本周我们将深入探讨如何形式化地描述智能体与环境交互的序贯决策过程，引入核心框架——马尔可夫决策过程 (Markov Decision Process, MDP)。

马尔可夫性质 (Markov Property)

直观理解

马尔可夫性质是 MDP 的基础假设。通俗地说，它指的是 “未来只取决于现在，而与过去无关”。

更具体地：给定当前状态 \(S_t\)，未来的状态 \(S_{t+1}\) 和奖励 \(R_{t+1}\) 的概率分布，只依赖于当前状态 \(S_t\) 和采取的动作 \(A_t\)，而与 \(S_t\) 之前的任何状态、动作或奖励 \((S_0, A_0, R_1, S_1, A_1, ..., R_t)\) 都无关。

数学表达: \[P(S_{t+1}, R_{t+1} | S_t, A_t, S_{t-1}, A_{t-1}, ..., S_0, A_0) = P(S_{t+1}, R_{t+1} | S_t, A_t)\]

关键假设

当前状态 \(S_t\) 必须完全捕捉所有与未来决策相关的信息。如果 \(S_t\) 缺失了某些重要历史信息，那么马尔可夫性质就不成立。

商业近似 (Approximation in Business)

在现实商业世界中，严格的马尔可夫性质很少完全满足。历史信息（如客户过去的购买行为、长期的市场趋势）往往对未来有影响。

然而，我们可以通过精心设计状态表示 (State Representation) 来近似满足马尔可夫性质：

包含关键历史信息: 将重要的历史摘要信息纳入当前状态。
- 例子 (定价): 状态可以包含过去 7 天的平均销售额、竞争对手过去 24 小时的价格变动次数等。
- 例子 (库存): 状态可以包含上个月的销售总量、供应商近期的交货延迟情况等。
关注相关信息: 忽略那些对未来决策影响微乎其微的遥远历史。

状态设计的艺术

选择合适的状态表示是 RL 应用成功的关键之一。状态既要足够简洁以避免维度灾难，又要足够丰富以近似满足马尔可夫性质，捕捉决策所需的核心信息。这是一个需要在实践中不断调整和优化的过程。

马尔可夫决策过程 (MDP)

MDP 是对满足马尔可夫性质的序贯决策问题的数学描述。一个 MDP 由以下五个要素定义：

\(S\) (State Space): 所有可能的状态的集合。可以是离散的（如棋盘格位置、库存等级）或连续的（如价格、温度、机器人关节角度）。
\(A\) (Action Space): 所有可能的动作的集合。同样可以是离散的（如上下左右、买入/卖出/持有）或连续的（如油门踩踏力度、投资组合权重）。
\(P\) (Transition Probability Function): 状态转移概率。\(P(s' | s, a) = P(S_{t+1}=s' | S_t=s, A_t=a)\) 表示在状态 \(s\) 采取动作 \(a\) 后，转移到状态 \(s'\) 的概率。对于环境中所有 \(s, a, s'\)，概率之和必须为 1: \(\sum_{s' \in S} P(s' | s, a) = 1\)。
\(R\) (Reward Function): 奖励函数。\(R(s, a, s')\) 表示在状态 \(s\) 采取动作 \(a\) 并转移到状态 \(s'\) 后获得的即时奖励。有时也简化为 \(R(s, a)\) 或 \(R(s)\)。
\(\gamma\) (Discount Factor): 折扣因子，\(0 \leq \gamma \leq 1\)。用于衡量未来奖励相对于当前奖励的重要性。

回报 (Return) 与折扣因子 (Discount Factor)

智能体的目标是最大化累积奖励 (Cumulative Reward)，也称为回报 (Return)。

对于一个从时间 \(t\) 开始的完整决策序列（称为一个 回合 (episode) 或 轨迹 (trajectory)），回报 \(G_t\) 定义为：

\[G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... = \sum_{k=0}^\infty \gamma^k R_{t+k+1}\]

折扣因子 \(\gamma\) (Gamma):
- \(\gamma\) 接近 0: 智能体更关注即时奖励，变得“短视”(Myopic)。适用于只关心短期效果的场景。
- \(\gamma\) 接近 1: 智能体更关注未来奖励，变得“远见”(Far-sighted)。适用于需要长期规划的场景。
- \(\gamma = 1:\) (无折扣) 适用于有明确终点的回合制任务 (Episodic Tasks)，如棋类游戏。需要保证回合有限，否则回报可能无限大。
- \(\gamma < 1:\) 适用于持续性任务 (Continuing Tasks)（没有明确终点），或者为了数学上的收敛性。它确保了即使在无限长的序列中，回报也是有限的。

商业含义：短视 vs. 远见

短视 (\(\gamma \approx 0\)): 一个促销活动只关注当天的销售额提升 (\(R_{t+1}\))，不考虑对品牌形象或长期客户关系的潜在损害 (未来的 \(R\))。
远见 (\(\gamma \approx 1\)): 一个研发投资决策，虽然短期内 \(R_{t+1}\) 可能是负的（投入成本），但期望未来能带来巨大的回报 (\(\gamma^k R_{t+k+1}\))。折扣因子体现了对未来收益的不确定性或时间价值的考量。

策略与价值函数

策略 (Policy, \(\pi\))

策略 \(\pi\) 定义了智能体在每个状态下如何选择动作。

确定性策略 (Deterministic Policy): \(\pi: S \to A\)。对于每个状态 \(s\)，策略指定一个唯一的动作 \(a = \pi(s)\)。
- 例子: 如果库存 < 10，则订购 50。
随机性策略 (Stochastic Policy): \(\pi: S \times A \to [0, 1]\)。对于每个状态 \(s\) 和动作 \(a\)，策略指定一个概率 \(\pi(a|s) = P(A_t=a | S_t=s)\)。对于任意状态 \(s\)，所有动作的概率之和为 1: \(\sum_{a \in A} \pi(a|s) = 1\)。
- 例子: 如果库存 < 10，则有 80% 概率订购 50，有 20% 概率订购 60 (可能为了探索)。

随机策略的优势

随机策略在学习过程中通常更优，因为它允许探索。

随机策略的劣势

随机策略在评估时通常更困难，因为需要对所有可能的动作进行加权平均。

策略的来源:

基于规则 (Rule-based): 人工设定的简单规则（如 IF-THEN）。

基于规则策略的劣势

基于规则的策略可能无法适应复杂的环境变化，且难以推广到新的场景。

学习得到 (Learned): 通过 RL 算法从经验中学习到的最优或近似最优策略。这是我们的重点。

学习得到策略的劣势

学习得到的策略可能需要更长的训练时间，并且可能需要更多的计算资源。

价值函数 (Value Functions)

价值函数用于评估遵循特定策略 \(\pi\) 时，某个状态或状态-动作对的“好坏”程度（即预期的未来累积回报）。

状态值函数 (State-Value Function, \(V_{\pi}(s)\)):
- 定义: \(V_{\pi}(s) = E_{\pi} [G_t | S_t=s] = E_{\pi} [\sum_{k=0}^\infty \gamma^k R_{t+k+1} | S_t=s]\)
- 含义: 从状态 \(s\) 开始，遵循策略 \(\pi\)，预期能够获得的总折扣回报。它衡量了处于状态 \(s\) 的长期价值。
动作值函数 (Action-Value Function, \(Q_{\pi}(s, a)\)):
- 定义: \(Q_{\pi}(s, a) = E_{\pi} [G_t | S_t=s, A_t=a] = E_{\pi} [\sum_{k=0}^\infty \gamma^k R_{t+k+1} | S_t=s, A_t=a]\)
- 含义: 在状态 \(s\) 下，首先采取动作 \(a\)，然后继续遵循策略 \(\pi\)，预期能够获得的总折扣回报。它衡量了在状态 \(s\) 下采取动作 \(a\) 的长期价值。

\(V_{\pi}\) vs. \(Q_{\pi}\)

\(V_{\pi}(s)\) 评估的是状态的好坏。
\(Q_{\pi}(s, a)\) 评估的是状态-动作对的好坏。
如果我们知道了 \(Q_{\pi}(s, a)\)，就很容易选择动作：在状态 \(s\) 下，选择使得 \(Q_{\pi}(s, a)\) 最大的那个动作 \(a\) (或者根据 \(\pi(a|s)\) 的概率选择)。因此，\(Q\) 函数对于决策更直接。
\(V_{\pi}(s)\) 和 \(Q_{\pi}(s, a)\) 的关系: \(V_{\pi}(s) = \sum_{a \in A} \pi(a|s) Q_{\pi}(s, a)\) (对于随机策略) 或 \(V_{\pi}(s) = Q_{\pi}(s, \pi(s))\) (对于确定性策略)。

Bellman 期望方程 (Bellman Expectation Equation)

Bellman 方程是 RL 中最核心的方程之一，它建立了当前状态（或状态-动作对）的价值与其后继状态价值之间的关系。

\(V_{\pi}\) 的 Bellman 期望方程:

\[ \begin{aligned} V_{\pi}(s) &= E_{\pi} [R_{t+1} + \gamma V_{\pi}(S_{t+1}) | S_t=s] \\ &= \sum_{a \in A} \pi(a|s) \sum_{s' \in S} P(s' | s, a) [R(s, a, s') + \gamma V_{\pi}(s')] \end{aligned} \]

直观解读: 一个状态 \(s\) 的价值 \(V_{\pi}(s)\) 等于：

根据策略 \(\pi(a|s)\) 选择一个动作 \(a\)。
环境根据 \(P(s' | s, a)\) 转移到一个后继状态 \(s'\)，并给出即时奖励 \(R(s, a, s')\)。
从后继状态 \(s'\) 开始继续遵循策略 \(\pi\)，预期获得未来的折扣价值 \(\gamma V_{\pi}(s')\)。
对所有可能的动作 \(a\) 和所有可能的后继状态 \(s'\) 进行加权平均（根据策略概率和转移概率）。

\(Q_{\pi}\) 的 Bellman 期望方程:

\[ \begin{aligned} Q_{\pi}(s, a) &= E_{\pi} [R_{t+1} + \gamma Q_{\pi}(S_{t+1}, A_{t+1}) | S_t=s, A_t=a] \\ &= \sum_{s' \in S} P(s' | s, a) [R(s, a, s') + \gamma \sum_{a' \in A} \pi(a'|s') Q_{\pi}(s', a')] \end{aligned} \]

(利用 \(V_{\pi}\) 和 \(Q_{\pi}\) 的关系)

直观解读: 在状态 \(s\) 采取动作 \(a\) 的价值 \(Q_{\pi}(s, a)\) 等于：

环境根据 \(P(s' | s, a)\) 转移到一个后继状态 \(s'\)，并给出即时奖励 \(R(s, a, s')\)。
在后继状态 \(s'\)，智能体根据策略 \(\pi(a'|s')\) 选择下一个动作 \(a'\)。
从状态 \(s'\) 采取动作 \(a'\) 开始继续遵循策略 \(\pi\)，预期获得未来的折扣价值 \(\gamma Q_{\pi}(s', a')\)。
对所有可能的后继状态 \(s'\) 和所有可能的下一个动作 \(a'\) 进行加权平均。或者更简洁地：等于即时奖励 \(R\) 加上所有可能的后继状态 \(s'\) 的折扣价值 \(\gamma V_{\pi}(s')\) 的期望。

确定性情况的 Bellman 方程

在确定性环境中，状态转移是确定的，即给定状态 \(s\) 和动作 \(a\)，下一个状态 \(s'\) 是唯一确定的。此时，Bellman 方程可以简化为：

\(V_{\pi}\) 的确定性 Bellman 方程:

\[ V_{\pi}(s) = R(s, \pi(s)) + \gamma V_{\pi}(s') \]

其中 \(s'\) 是执行动作 \(\pi(s)\) 后确定转移到的下一个状态。

\(Q_{\pi}\) 的确定性 Bellman 方程:

\[ Q_{\pi}(s, a) = R(s, a) + \gamma Q_{\pi}(s', \pi(s')) \]

其中 \(s'\) 是执行动作 \(a\) 后确定转移到的下一个状态。

直观解读: 在确定性情况下，Bellman 方程更加简洁明了：当前状态（或状态-动作对）的价值等于即时奖励加上下一个状态的折扣价值。这反映了确定性环境中决策的因果链更加直接和可预测。

商业解读：价值 = 即时收益 + 未来预期价值

Bellman 方程深刻地体现了商业决策中的权衡：当前的决策不仅要考虑即时的收益/成本 (\(R_{t+1}\))，还要考虑它对未来状态 (\(S_{t+1}\)) 以及从那个状态出发能够获得的长期价值 (\(\gamma V_{\pi}(S_{t+1})\)) 的影响。一个好的决策是在这两者之间取得最优平衡。

Bellman 方程的意义

Bellman 方程是强化学习中最核心的数学工具之一，具有以下重要意义：

递归关系: 将复杂的长远价值计算分解为即时奖励和未来价值的简单组合，使得价值计算可以递归进行。
理论基础: 为各种强化学习算法（如值迭代、策略迭代、Q-learning等）提供了坚实的数学基础。
最优性原理: 体现了动态规划的最优子结构性质，即最优策略的子策略也是最优的。
计算效率: 通过将问题分解为更小的子问题，大大提高了计算效率，避免了直接计算长期回报的复杂性。
统一框架: 为不同强化学习问题提供了一个统一的数学框架，使得各种算法可以在同一理论基础上进行比较和改进。
实际应用: 在商业决策中，Bellman 方程帮助我们将复杂的长期决策问题分解为可管理的步骤，在考虑即时收益的同时也兼顾长期价值。
后续方法的基础: 几乎所有重要的强化学习算法都建立在 Bellman 方程之上：
- 值迭代 (Value Iteration): 直接基于 Bellman 最优方程
- 策略迭代 (Policy Iteration): 使用 Bellman 期望方程进行策略评估
- Q-learning: 通过 Bellman 最优方程更新 Q 值
- 深度 Q 网络 (DQN): 使用神经网络近似 Bellman 方程
- 策略梯度方法: 间接利用 Bellman 方程计算优势函数

Bellman 方程的证明

主要思想：

Bellman 方程的证明基于动态规划的思想，通过将长期回报分解为即时奖励和未来折扣回报来建立递归关系。核心在于利用马尔可夫性质和期望的线性性质，将复杂的长期回报期望值分解为更简单的组成部分。

数学推导过程：

从定义出发： \[V_{\pi}(s) = E_{\pi} [G_t | S_t=s] = E_{\pi} [\sum_{k=0}^\infty \gamma^k R_{t+k+1} | S_t=s]\]
将回报分解为即时奖励和未来折扣回报： \[G_t = R_{t+1} + \gamma G_{t+1}\]
代入期望表达式： \[V_{\pi}(s) = E_{\pi} [R_{t+1} + \gamma G_{t+1} | S_t=s]\]
利用期望的线性性质： \[V_{\pi}(s) = E_{\pi} [R_{t+1} | S_t=s] + \gamma E_{\pi} [G_{t+1} | S_t=s]\]
展开第一个期望项： \[E_{\pi} [R_{t+1} | S_t=s] = \sum_{a \in A} \pi(a|s) \sum_{s' \in S} P(s'|s,a) R(s,a,s')\]
展开第二个期望项： \[E_{\pi} [G_{t+1} | S_t=s] = \sum_{a \in A} \pi(a|s) \sum_{s' \in S} P(s'|s,a) V_{\pi}(s')\]
将两部分合并： \[V_{\pi}(s) = \sum_{a \in A} \pi(a|s) \sum_{s' \in S} P(s'|s,a) [R(s,a,s') + \gamma V_{\pi}(s')]\]
得到最终的 Bellman 期望方程： \[V_{\pi}(s) = \sum_{a \in A} \pi(a|s) \sum_{s' \in S} P(s'|s,a) [R(s,a,s') + \gamma V_{\pi}(s')]\]

Q 函数的推导类似，只是从状态-动作对 (s,a) 开始。

Python & Gym/Gymnasium 环境介绍

为了进行 RL 实验，我们需要一个标准化的方式来定义和交互环境。OpenAI Gym (以及其后续维护版本 Gymnasium) 是目前最流行的 Python 工具包。

Gym/Gymnasium 核心概念

环境 (Env): 模拟 RL 问题的接口。
make(env_id): 创建一个特定环境的实例 (e.g., gym.make("CartPole-v1"))。
reset(): 初始化环境，返回初始状态 (observation) 和可能的附加信息 (info)。
step(action): 在环境中执行一个动作，返回：
- observation (object): 新的状态。
- reward (float): 执行动作后获得的奖励。
- terminated (bool): 回合是否因为达到终止状态而结束 (e.g., 游戏胜利/失败, CartPole 倒下)。
- truncated (bool): 回合是否因为达到时间限制或其他非终止条件而结束 (e.g., 达到最大步数)。
- info (dict): 包含调试或辅助信息的字典。
render(): (可选) 可视化环境当前状态。
close(): 关闭环境，释放资源。
observation_space: 描述状态空间的结构和范围 (e.g., Box, Discrete)。
action_space: 描述动作空间的结构和范围 (e.g., Box, Discrete)。

安装指导

推荐使用 pip 进行安装。建议在虚拟环境中安装以避免包冲突。

# 创建并激活虚拟环境 (可选但推荐)
python -m venv rl_env
# Windows: .\rl_env\Scripts\activate
# macOS/Linux: source rl_env/bin/activate

# 安装 Gymnasium 核心库
pip install gymnasium

# 安装一些经典控制环境和 Box2D 环境 (可能需要额外依赖)
pip install gymnasium[classic_control,box2d]

Gym vs. Gymnasium

Gymnasium 是 Gym 的一个积极维护的分支，API 基本兼容但有一些改进（例如 step 返回 5 个值）。在本课程中，我们将主要使用 Gymnasium，但有时可能仍会沿用 Gym 的叫法。

简单示例：随机智能体

import gymnasium as gym
import time

# 创建 CartPole 环境
# CartPole: 目标是让杆保持竖直不倒
# 状态: [车位置, 车速度, 杆角度, 杆角速度] (连续)
# 动作: 0 (向左推), 1 (向右推) (离散)
env = gym.make("CartPole-v1", render_mode="human") # render_mode="human" 用于可视化

# 重置环境，获取初始状态
observation, info = env.reset(seed=42) # 设置 seed 保证可复现

total_reward = 0
for _ in range(1000):
    # 渲染环境 (显示窗口)
    env.render()

    # 随机选择一个动作
    action = env.action_space.sample() # 从动作空间随机采样

    # 执行动作，获取反馈
    observation, reward, terminated, truncated, info = env.step(action)

    total_reward += reward
    print(f"Action: {action}, Reward: {reward:.2f}, Terminated: {terminated}, Truncated: {truncated}")
    print(f"Observation: {observation}")

    # 如果回合结束 (倒下或达到最大步数)，则重置
    if terminated or truncated:
        print(f"Episode finished after {_ + 1} timesteps. Total reward: {total_reward}")
        total_reward = 0
        observation, info = env.reset()
        time.sleep(1) # 暂停一下，方便观察

# 关闭环境
env.close()

下周任务

下周的 Lab 1 将让大家更深入地熟悉 Gym/Gymnasium 环境，并尝试定义一个简单的商业场景。

下周预告: 最优决策与 Bellman 最优方程，Lab 1 热身

回顾：强化学习核心要素

马尔可夫性质 (Markov Property)

直观理解

商业近似 (Approximation in Business)

马尔可夫决策过程 (MDP)

回报 (Return) 与 折扣因子 (Discount Factor)

策略与价值函数

策略 (Policy, \(\pi\))

价值函数 (Value Functions)

Bellman 期望方程 (Bellman Expectation Equation)

Python & Gym/Gymnasium 环境介绍

Gym/Gymnasium 核心概念

安装指导

简单示例：随机智能体

回报 (Return) 与折扣因子 (Discount Factor)