强化学习 MDP 值函数 动态规划

模型基础强化学习详解

深入理解马尔可夫决策过程、值函数与Bellman方程

Posted by 冯宇 on July 28, 2024

引言

强化学习（Reinforcement Learning, RL）作为机器学习的重要分支，在游戏AI、机器人控制、自动驾驶等领域取得了令人瞩目的成就。而模型基础强化学习（Model-Based Reinforcement Learning）是强化学习的基石，它假设智能体对环境动态有完整或部分的了解。

本文将深入讲解模型基础强化学习的核心概念，包括马尔可夫决策过程（MDP）、值函数、Bellman方程以及经典的动态规划算法。通过理论推导与代码实现相结合的方式，帮助读者建立扎实的强化学习理论基础。

1. 马尔可夫决策过程（MDP）

1.1 MDP的形式化定义

马尔可夫决策过程是强化学习问题的数学抽象，由一个五元组定义：

\[\text{MDP} = \langle \mathcal{S}, \mathcal{A}, P, R, \gamma \rangle\]

各元素含义：

  • $\mathcal{S}$：状态空间（State Space），所有可能状态的集合
  • $\mathcal{A}$：动作空间（Action Space），所有可能动作的集合
  • $P$：状态转移概率（Transition Probability） \(P(s'|s, a) = \mathbb{P}[S_{t+1}=s' | S_t=s, A_t=a]\)
  • $R$：奖励函数（Reward Function） \(R(s, a, s') = \mathbb{E}[R_{t+1} | S_t=s, A_t=a, S_{t+1}=s']\)
  • $\gamma$：折扣因子（Discount Factor），$\gamma \in [0, 1]$

1.2 马尔可夫性质

马尔可夫性质（Markov Property）是MDP的核心假设：

\[\mathbb{P}[S_{t+1} | S_t] = \mathbb{P}[S_{t+1} | S_1, S_2, \ldots, S_t]\]

含义：未来状态只依赖于当前状态，与历史路径无关。这是一个无记忆性（Memoryless）假设。

数学表达：

\[\mathbb{P}[S_{t+1}=s', R_{t+1}=r | S_0, A_0, R_1, \ldots, S_t, A_t] = \mathbb{P}[S_{t+1}=s', R_{t+1}=r | S_t, A_t]\]

1.3 回报与折扣

回报（Return）是从时刻$t$开始的累积奖励：

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

折扣因子的作用：

  1. 数学收敛性：保证无限时间步的回报有界 \(G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \leq \frac{R_{\max}}{1-\gamma}\)

  2. 不确定性建模：未来的不确定性越大，折扣越重

  3. 偏好即时奖励：符合经济学中的”时间偏好”

递归形式：

\[G_t = R_{t+1} + \gamma G_{t+1}\]

1.4 策略（Policy）

策略$\pi$定义了智能体的行为规则：

\[\pi(a|s) = \mathbb{P}[A_t=a | S_t=s]\]

策略类型：

  • 确定性策略：$a = \pi(s)$
  • 随机性策略：$\pi(a s)$，动作概率分布

最优策略的目标：

\[\pi^* = \arg\max_{\pi} \mathbb{E}_{\pi}[G_t | S_t=s], \quad \forall s \in \mathcal{S}\]

2. 值函数理论

2.1 状态值函数（State-Value Function）

定义：在策略$\pi$下，从状态$s$开始的期望回报

\[V^{\pi}(s) = \mathbb{E}_{\pi}[G_t | S_t=s] = \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \Big| S_t=s\right]\]

展开形式：

\[\begin{align} V^{\pi}(s) &= \mathbb{E}_{\pi}[R_{t+1} + \gamma G_{t+1} | S_t=s] \\ &= \mathbb{E}_{\pi}[R_{t+1} + \gamma V^{\pi}(S_{t+1}) | S_t=s] \end{align}\]

2.2 动作值函数（Action-Value Function）

定义：在状态$s$采取动作$a$，然后遵循策略$\pi$的期望回报

\[Q^{\pi}(s, a) = \mathbb{E}_{\pi}[G_t | S_t=s, A_t=a]\]

与状态值函数的关系：

\[V^{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a|s) Q^{\pi}(s, a)\]

2.3 Bellman期望方程

状态值函数的Bellman期望方程：

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

推导过程：

\[\begin{align} V^{\pi}(s) &= \mathbb{E}_{\pi}[G_t | S_t=s] \\ &= \mathbb{E}_{\pi}[R_{t+1} + \gamma G_{t+1} | S_t=s] \\ &= \sum_a \pi(a|s) \sum_{s'} P(s'|s,a) [R(s,a,s') + \gamma \mathbb{E}_{\pi}[G_{t+1}|S_{t+1}=s']] \\ &= \sum_a \pi(a|s) \sum_{s'} P(s'|s,a) [R(s,a,s') + \gamma V^{\pi}(s')] \end{align}\]

动作值函数的Bellman期望方程：

\[Q^{\pi}(s,a) = \sum_{s' \in \mathcal{S}} P(s'|s,a) \left[R(s,a,s') + \gamma \sum_{a' \in \mathcal{A}} \pi(a'|s') Q^{\pi}(s',a')\right]\]

矩阵形式（用于计算）：

\[\mathbf{V}^{\pi} = \mathbf{R}^{\pi} + \gamma \mathbf{P}^{\pi} \mathbf{V}^{\pi}\]

其中：

  • $\mathbf{V}^{\pi}$：状态值向量
  • $\mathbf{R}^{\pi}$：奖励向量
  • $\mathbf{P}^{\pi}$：转移概率矩阵

解析解：

\[\mathbf{V}^{\pi} = (\mathbf{I} - \gamma \mathbf{P}^{\pi})^{-1} \mathbf{R}^{\pi}\]

2.4 Bellman最优方程

最优状态值函数：

\[V^*(s) = \max_{\pi} V^{\pi}(s), \quad \forall s \in \mathcal{S}\]

最优动作值函数：

\[Q^*(s,a) = \max_{\pi} Q^{\pi}(s,a), \quad \forall s \in \mathcal{S}, a \in \mathcal{A}\]

Bellman最优方程（状态值）：

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

Bellman最优方程（动作值）：

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

关键性质：

  1. 唯一性：最优值函数是唯一的
  2. 多个最优策略：可能存在多个最优策略，但它们共享相同的最优值函数

最优策略的提取：

\[\pi^*(s) = \arg\max_{a \in \mathcal{A}} Q^*(s,a)\]

3. 动态规划算法

动态规划（Dynamic Programming, DP）利用MDP的马尔可夫性质和Bellman方程，通过迭代计算值函数。

3.1 策略评估（Policy Evaluation）

目标：计算给定策略$\pi$的值函数$V^{\pi}$

迭代更新规则：

\[V_{k+1}(s) = \sum_{a \in \mathcal{A}} \pi(a|s) \sum_{s' \in \mathcal{S}} P(s'|s,a) \left[R(s,a,s') + \gamma V_k(s')\right]\]

收敛性：当$k \to \infty$时，$V_k \to V^{\pi}$（压缩映射定理）

算法实现：

import numpy as np

def policy_evaluation(env, policy, gamma=0.9, theta=1e-6):
    """
    策略评估：迭代计算给定策略的状态值函数
    
    参数:
        env: 环境对象，包含状态空间、动作空间、转移概率等
        policy: 策略矩阵 [nS, nA]，policy[s, a] = π(a|s)
        gamma: 折扣因子
        theta: 收敛阈值
    
    返回:
        V: 状态值函数数组 [nS]
    """
    nS = env.nS  # 状态数量
    V = np.zeros(nS)  # 初始化值函数
    
    iteration = 0
    while True:
        delta = 0  # 最大变化量
        V_old = V.copy()
        
        # 对每个状态进行更新
        for s in range(nS):
            v = 0
            # 对所有动作求期望
            for a in range(env.nA):
                # 对所有可能的下一个状态求期望
                for prob, next_state, reward, done in env.P[s][a]:
                    v += policy[s, a] * prob * (reward + gamma * V_old[next_state])
            
            V[s] = v
            delta = max(delta, abs(V[s] - V_old[s]))
        
        iteration += 1
        
        # 检查收敛
        if delta < theta:
            print(f"策略评估收敛于第 {iteration} 次迭代")
            break
    
    return V

3.2 策略改进（Policy Improvement）

策略改进定理：对于确定性策略$\pi$和$\pi’$，如果对所有$s \in \mathcal{S}$有：

\[Q^{\pi}(s, \pi'(s)) \geq V^{\pi}(s)\]

则$\pi’ \geq \pi$，即$V^{\pi’}(s) \geq V^{\pi}(s)$对所有$s$成立。

贪婪策略改进：

\[\pi'(s) = \arg\max_{a \in \mathcal{A}} Q^{\pi}(s,a) = \arg\max_{a \in \mathcal{A}} \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma V^{\pi}(s')]\]

算法实现：

def policy_improvement(env, V, gamma=0.9):
    """
    策略改进：根据值函数生成贪婪策略
    
    参数:
        env: 环境对象
        V: 状态值函数 [nS]
        gamma: 折扣因子
    
    返回:
        policy: 改进后的策略矩阵 [nS, nA]
        policy_stable: 布尔值，指示策略是否稳定
    """
    nS, nA = env.nS, env.nA
    policy = np.zeros([nS, nA])
    policy_stable = True
    
    for s in range(nS):
        # 计算每个动作的Q值
        q_values = np.zeros(nA)
        for a in range(nA):
            for prob, next_state, reward, done in env.P[s][a]:
                q_values[a] += prob * (reward + gamma * V[next_state])
        
        # 选择最优动作（贪婪策略）
        best_action = np.argmax(q_values)
        
        # 检查策略是否改变
        if policy[s, best_action] != 1.0:
            policy_stable = False
        
        # 确定性策略：将概率1分配给最优动作
        policy[s] = np.eye(nA)[best_action]
    
    return policy, policy_stable

3.3 策略迭代（Policy Iteration）

算法流程：

  1. 初始化：任意策略$\pi_0$和值函数$V_0$
  2. 策略评估：计算$V^{\pi_k}$
  3. 策略改进：$\pi_{k+1} = \text{greedy}(V^{\pi_k})$
  4. 重复步骤2-3直到策略稳定

收敛性：策略迭代保证收敛到最优策略$\pi^*$（有限迭代次数）

完整实现：

def policy_iteration(env, gamma=0.9, theta=1e-6, max_iterations=1000):
    """
    策略迭代算法
    
    参数:
        env: 环境对象
        gamma: 折扣因子
        theta: 策略评估收敛阈值
        max_iterations: 最大迭代次数
    
    返回:
        policy: 最优策略
        V: 最优值函数
        iterations: 迭代次数
    """
    nS, nA = env.nS, env.nA
    
    # 初始化随机策略（均匀分布）
    policy = np.ones([nS, nA]) / nA
    
    for i in range(max_iterations):
        # 策略评估
        V = policy_evaluation(env, policy, gamma, theta)
        
        # 策略改进
        new_policy, policy_stable = policy_improvement(env, V, gamma)
        
        if policy_stable:
            print(f"策略迭代收敛于第 {i+1} 次迭代")
            return new_policy, V, i+1
        
        policy = new_policy
    
    print("达到最大迭代次数")
    return policy, V, max_iterations

3.4 值迭代（Value Iteration）

核心思想：直接迭代Bellman最优方程，跳过显式的策略评估步骤

迭代更新规则：

\[V_{k+1}(s) = \max_{a \in \mathcal{A}} \sum_{s' \in \mathcal{S}} P(s'|s,a) \left[R(s,a,s') + \gamma V_k(s')\right]\]

算法实现：

def value_iteration(env, gamma=0.9, theta=1e-6, max_iterations=10000):
    """
    值迭代算法
    
    参数:
        env: 环境对象
        gamma: 折扣因子
        theta: 收敛阈值
        max_iterations: 最大迭代次数
    
    返回:
        policy: 最优策略
        V: 最优值函数
        iterations: 迭代次数
    """
    nS, nA = env.nS, env.nA
    V = np.zeros(nS)
    
    for i in range(max_iterations):
        delta = 0
        V_old = V.copy()
        
        # 对每个状态更新值函数
        for s in range(nS):
            q_values = np.zeros(nA)
            
            # 计算所有动作的Q值
            for a in range(nA):
                for prob, next_state, reward, done in env.P[s][a]:
                    q_values[a] += prob * (reward + gamma * V_old[next_state])
            
            # 取最大Q值
            V[s] = np.max(q_values)
            delta = max(delta, abs(V[s] - V_old[s]))
        
        # 检查收敛
        if delta < theta:
            print(f"值迭代收敛于第 {i+1} 次迭代")
            break
    
    # 提取最优策略
    policy = np.zeros([nS, nA])
    for s in range(nS):
        q_values = np.zeros(nA)
        for a in range(nA):
            for prob, next_state, reward, done in env.P[s][a]:
                q_values[a] += prob * (reward + gamma * V[next_state])
        
        best_action = np.argmax(q_values)
        policy[s, best_action] = 1.0
    
    return policy, V, i+1

3.5 算法对比

特性 策略迭代 值迭代
更新方式 策略评估 + 策略改进 直接更新值函数
每次迭代计算量 高（需完全评估策略） 低（单次扫描）
收敛速度 迭代次数少 迭代次数多
总计算时间 取决于策略评估的精度 通常更快
适用场景 小规模MDP 大规模MDP

复杂度分析：

  • 策略迭代：$O(n^2 m + n^3)$ 每次迭代
    • $n$：状态数
    • $m$：动作数
  • 值迭代：$O(n^2 m)$ 每次迭代

4. 实战案例：冰湖环境（FrozenLake）

4.1 环境介绍

FrozenLake 是OpenAI Gym中的经典网格世界环境：

  • 目标：从起点（S）到达终点（G），避开冰洞（H）
  • 状态空间：4x4网格（16个状态）
  • 动作空间：4个方向（上、下、左、右）
  • 转移动态：有1/3概率滑向侧面方向（冰面滑动）
  • 奖励：到达终点 +1，其他 0
SFFF
FHFH
FFFH
HFFG

4.2 环境实现

import gym

# 创建环境
env = gym.make('FrozenLake-v1', is_slippery=True)

# 环境信息
print(f"状态空间大小: {env.observation_space.n}")
print(f"动作空间大小: {env.action_space.n}")

# 查看转移概率
state = 6
action = 2  # 向右
print(f"\n状态 {state} 采取动作 {action} 的转移:")
for prob, next_state, reward, done in env.P[state][action]:
    print(f"  概率={prob:.2f}, 下一状态={next_state}, 奖励={reward}, 终止={done}")

4.3 策略迭代求解

# 运行策略迭代
policy_pi, V_pi, iters_pi = policy_iteration(env.unwrapped, gamma=0.99)

# 可视化值函数
import matplotlib.pyplot as plt

def visualize_value_function(V, shape=(4, 4)):
    """可视化值函数热力图"""
    plt.figure(figsize=(6, 6))
    V_grid = V.reshape(shape)
    im = plt.imshow(V_grid, cmap='viridis', interpolation='nearest')
    plt.colorbar(im)
    
    # 添加数值标注
    for i in range(shape[0]):
        for j in range(shape[1]):
            text = plt.text(j, i, f'{V_grid[i, j]:.3f}',
                          ha="center", va="center", color="w", fontsize=12)
    
    plt.title('状态值函数热力图')
    plt.xlabel('列')
    plt.ylabel('行')
    plt.tight_layout()
    plt.show()

visualize_value_function(V_pi)

# 可视化策略
def visualize_policy(policy, shape=(4, 4)):
    """可视化策略（箭头表示）"""
    action_symbols = ['↑', '↓', '←', '→']
    policy_grid = np.argmax(policy, axis=1).reshape(shape)
    
    fig, ax = plt.subplots(figsize=(6, 6))
    ax.imshow(np.zeros(shape), cmap='gray', vmin=0, vmax=1)
    
    for i in range(shape[0]):
        for j in range(shape[1]):
            action = policy_grid[i, j]
            ax.text(j, i, action_symbols[action], 
                   ha='center', va='center', fontsize=30, color='red')
    
    ax.set_xticks(range(shape[1]))
    ax.set_yticks(range(shape[0]))
    ax.grid(True, color='black', linewidth=2)
    plt.title('最优策略可视化')
    plt.tight_layout()
    plt.show()

visualize_policy(policy_pi)

4.4 值迭代求解

# 运行值迭代
policy_vi, V_vi, iters_vi = value_iteration(env.unwrapped, gamma=0.99)

print(f"\n策略迭代：{iters_pi} 次迭代")
print(f"值迭代：{iters_vi} 次迭代")

# 对比两种算法的值函数
print("\n值函数差异:")
print(f"最大差异: {np.max(np.abs(V_pi - V_vi))}")
print(f"平均差异: {np.mean(np.abs(V_pi - V_vi))}")

4.5 测试最优策略

def test_policy(env, policy, episodes=100, max_steps=100):
    """测试策略的性能"""
    success_count = 0
    total_rewards = []
    
    for ep in range(episodes):
        state, _ = env.reset()
        episode_reward = 0
        
        for step in range(max_steps):
            # 根据策略选择动作
            action = np.argmax(policy[state])
            state, reward, terminated, truncated, _ = env.step(action)
            episode_reward += reward
            
            if terminated or truncated:
                if reward > 0:  # 到达终点
                    success_count += 1
                break
        
        total_rewards.append(episode_reward)
    
    print(f"\n测试结果（{episodes}局）:")
    print(f"成功率: {success_count/episodes*100:.2f}%")
    print(f"平均奖励: {np.mean(total_rewards):.3f}")
    print(f"奖励标准差: {np.std(total_rewards):.3f}")

test_policy(env, policy_vi)

5. 实践建议与总结

5.1 算法选择指南

使用动态规划的条件：

  1. ✅ 环境模型已知（$P$和$R$）
  2. ✅ 状态空间较小（$<10^6$）
  3. ✅ 需要精确解

选择策略迭代 vs 值迭代：

  • 策略迭代：当动作空间大于状态空间时
  • 值迭代：当状态空间远大于动作空间时

5.2 关键要点回顾

  1. MDP五要素：$\langle \mathcal{S}, \mathcal{A}, P, R, \gamma \rangle$

  2. Bellman方程：
    • 期望方程：评估给定策略
    • 最优方程：求解最优策略
  3. 动态规划算法：
    • 策略迭代：评估 → 改进循环
    • 值迭代：直接迭代最优方程
  4. 广义策略迭代：几乎所有RL算法的框架

5.3 从模型基础到无模型

模型基础强化学习为理解RL提供了坚实的理论基础，但在实际应用中，我们往往无法获得完美的环境模型。下一步学习方向：

  • 无模型方法：Q-Learning、SARSA、策略梯度
  • 函数逼近：处理大规模状态空间
  • 深度强化学习：DQN、A3C、PPO等

参考资源

  1. 经典教材：
    • Sutton & Barto (2018) “Reinforcement Learning: An Introduction”
    • Bertsekas (2019) “Reinforcement Learning and Optimal Control”
  2. 在线课程：
    • David Silver的强化学习课程
    • CS285: Deep Reinforcement Learning (UC Berkeley)
  3. 代码库：

通过本文的学习,你应该已经掌握了强化学习的数学基础和经典算法。模型基础强化学习虽然在实际应用中受到环境模型获取的限制，但它提供的理论框架和分析工具对理解所有RL算法都至关重要。掌握这些基础知识后，你将能够更深入地理解现代深度强化学习算法的设计原理。

💬 交流与讨论

⚠️ 尚未完成 Giscus 配置。请在 _config.yml 中设置 repo_id 与 category_id 后重新部署，即可启用升级后的评论系统。

配置完成后，评论区将自动支持 Markdown 代码高亮与 LaTeX 数学公式渲染，访客回复会同步到 GitHub Discussions，并具备通知功能。

CATALOG
    热门标签
    数据分析 强化学习 机器学习 深度学习 游戏AI MCTS 神经网络 概率图模型 因果推理 DUCG 博弈论 因果推断 Python 大语言模型
    FRIENDS