马尔可夫决策过程

马尔可夫决策过程（Markov Decision Process，简称 MDP）是强化学习的数学基础。几乎所有强化学习问题都可以形式化为 MDP，理解 MDP 对于掌握强化学习至关重要。2024年图灵奖授予了强化学习领域的奠基人 Richard Sutton 和 Andrew Barto，正是表彰他们在 MDP 框架下发展出的强化学习理论与算法。

什么是马尔可夫决策过程？

马尔可夫决策过程是对序贯决策问题的数学建模。所谓序贯决策，就是智能体需要在一系列时间步上做出决策，每个决策不仅影响当前的即时奖励，还会影响未来的状态和奖励。

MDP 的核心假设是马尔可夫性：当前状态包含了做出最优决策所需的所有信息，未来的发展只依赖于当前状态和当前动作，而与过去的历史无关。这个假设大大简化了问题，使得我们可以用数学方法来分析和求解。

马尔可夫性的直观理解

想象你在下棋。当你面对当前的棋盘局面时，你只需要考虑当前的棋子分布，而不需要关心这盘棋之前是怎么走到这个局面的。无论之前走了多少步，当前局面已经包含了所有决策所需的信息。这就是马尔可夫性的体现。

但在某些情况下，马尔可夫性并不成立。比如在扑克牌游戏中，你只能看到自己的手牌和公共牌，无法看到对手的牌，这就是部分可观测的情况。此时需要使用部分可观测马尔可夫决策过程（POMDP）来建模。

MDP 的形式化定义

一个马尔可夫决策过程由五元组 $(S, A, P, R, \gamma)$ 定义：

状态空间 S

状态空间是所有可能状态的集合。状态是对环境当前情况的完整描述。

有限状态空间：状态数量有限，如棋盘游戏中的局面， $S = \{s_1, s_2, ..., s_n\}$
无限状态空间：状态数量无限或连续，如机器人的位置坐标

状态的选择至关重要。一个好的状态表示应该：

包含决策所需的全部信息（满足马尔可夫性）
足够简洁，避免冗余信息
便于学习和泛化

import numpy as np

class GridWorldState:
    def __init__(self, row, col):
        self.row = row
        self.col = col
    
    def to_vector(self):
        return np.array([self.row, self.col])
    
    def __eq__(self, other):
        return self.row == other.row and self.col == other.col
    
    def __hash__(self):
        return hash((self.row, self.col))

states = [GridWorldState(r, c) for r in range(4) for c in range(4)]
print(f"状态空间大小: {len(states)}")

动作空间 A

动作空间是智能体可执行的所有动作的集合。

离散动作空间：动作数量有限，如 $A = \{上, 下, 左, 右\}$
连续动作空间：动作是连续值，如方向盘转角 $\theta \in [-\pi, \pi]$

动作空间的设计需要考虑：

动作是否足够表达智能体的意图
动作空间的维度（高维动作空间更难学习）
动作的物理约束

from enum import Enum

class Action(Enum):
    UP = 0
    DOWN = 1
    LEFT = 2
    RIGHT = 3

actions = list(Action)
print(f"动作空间: {[a.name for a in actions]}")

状态转移概率 P

状态转移概率 $P(s'|s,a)$ 描述了在状态 $s$ 执行动作 $a$ 后转移到状态 $s'$ 的概率。这定义了环境的动态特性。

$P(s'|s,a) = \mathbb{P}[S_{t+1}=s' | S_t=s, A_t=a]$

状态转移概率满足归一化条件：

$\sum_{s' \in S} P(s'|s,a) = 1, \quad \forall s \in S, a \in A$

确定性环境：对于每个状态-动作对，只有唯一的下一状态。

$P(s'|s,a) = \begin{cases} 1 & \text{如果 } s' = f(s,a) \\ 0 & \text{其他} \end{cases}$

随机环境：状态转移具有随机性，如冰面滑行问题。

class StochasticEnvironment:
    def __init__(self, slip_prob=0.3):
        self.slip_prob = slip_prob
    
    def get_transition_probs(self, state, action):
        intended_next = self.get_intended_next(state, action)
        slip_states = self.get_slip_states(state, action)
        
        probs = {intended_next: 1 - self.slip_prob}
        for slip_state in slip_states:
            probs[slip_state] = probs.get(slip_state, 0) + self.slip_prob / len(slip_states)
        
        return probs

奖励函数 R

奖励函数 $R(s,a,s')$ 定义了智能体在状态 $s$ 执行动作 $a$ 并转移到状态 $s'$ 时获得的即时奖励。奖励函数引导智能体学习期望的行为。

$R(s,a,s') = \mathbb{E}[R_{t+1} | S_t=s, A_t=a, S_{t+1}=s']$

有时奖励函数简化为 $R(s,a)$ 或 $R(s)$ ，只依赖于当前状态或状态-动作对。

奖励设计的原则：

反映目标：奖励应该反映任务目标，而非如何完成任务
稀疏 vs 密集：稀疏奖励（如游戏胜负）更难学习，但更符合真实目标
避免奖励黑客：智能体可能找到获取高奖励但不完成目标的漏洞

def reward_function(state, action, next_state, goal_state, trap_states):
    if next_state == goal_state:
        return 10.0
    elif next_state in trap_states:
        return -10.0
    else:
        return -0.1

def shaped_reward(state, action, next_state, goal_state):
    distance_before = np.linalg.norm(np.array(state) - np.array(goal_state))
    distance_after = np.linalg.norm(np.array(next_state) - np.array(goal_state))
    return distance_before - distance_after

折扣因子 γ

折扣因子 $\gamma \in [0, 1]$ 决定了未来奖励的重要性：

$\gamma = 0$ ：完全短视，只关心即时奖励
$\gamma = 1$ ：完全远视，未来奖励与即时奖励同等重要
$0 < \gamma < 1$ ：平衡即时和未来奖励

折扣因子的作用是让累积奖励有界。考虑无限时间步的累积奖励：

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

如果奖励有界（ $|R_t| \leq R_{max}$ ），则回报有界：

$|G_t| \leq \sum_{k=0}^{\infty} \gamma^k R_{max} = \frac{R_{max}}{1-\gamma}$

折扣因子的选择：

任务类型	推荐 $\gamma$	原因
短期任务	0.9 ~ 0.95	近期奖励更重要
长期任务	0.99 ~ 0.999	需要长远规划
无限任务	0.99	确保回报有界

def compute_discounted_return(rewards, gamma=0.99):
    G = 0
    returns = []
    for r in reversed(rewards):
        G = r + gamma * G
        returns.insert(0, G)
    return returns

rewards = [1, 1, 1, 1, 1]
returns = compute_discounted_return(rewards, gamma=0.9)
print(f"折扣回报: {returns}")

马尔可夫性的数学表述

马尔可夫性是 MDP 的核心假设，它要求状态具有"充分统计量"的性质：

$\mathbb{P}[S_{t+1}|S_t, A_t, S_{t-1}, A_{t-1}, ...] = \mathbb{P}[S_{t+1}|S_t, A_t]$

这意味着：

当前状态包含了预测未来所需的所有信息
历史信息对未来预测没有额外贡献
我们不需要记住完整的历史轨迹

马尔可夫性的证明思路

假设状态 $S_t$ 是马尔可夫的，那么对于任意历史 $H_t = (S_0, A_0, R_1, ..., S_t)$ ：

$\mathbb{P}[S_{t+1}|S_t, A_t] = \mathbb{P}[S_{t+1}|H_t, A_t]$

这个等式成立的条件是状态 $S_t$ 包含了历史 $H_t$ 中所有与未来相关的信息。

实际问题中的马尔可夫性

很多实际问题并不完全满足马尔可夫性：

部分可观测问题：

扑克牌游戏：只能看到自己的手牌
机器人导航：传感器有噪声和盲区

历史依赖问题：

股票交易：需要历史价格趋势
对话系统：需要理解对话上下文

解决方案：

状态增强：将历史信息编码到状态中

class AugmentedState:
    def __init__(self, current_obs, history_length=10):
        self.current_obs = current_obs
        self.history = []
        self.history_length = history_length
    
    def update(self, obs, action, reward):
        self.history.append((obs, action, reward))
        if len(self.history) > self.history_length:
            self.history.pop(0)
        self.current_obs = obs
    
    def to_vector(self):
        history_features = np.concatenate([
            np.concatenate([o, [a], [r]]) 
            for o, a, r in self.history
        ])
        return np.concatenate([self.current_obs, history_features])

使用循环神经网络：自动学习历史表示

import torch
import torch.nn as nn

class RNNStateEncoder(nn.Module):
    def __init__(self, obs_dim, hidden_dim=64):
        super().__init__()
        self.lstm = nn.LSTM(obs_dim, hidden_dim, batch_first=True)
    
    def forward(self, obs_sequence):
        output, (h_n, c_n) = self.lstm(obs_sequence)
        return h_n[-1]

POMDP 建模：显式建模信念状态

策略

策略 $\pi$ 定义了智能体的行为方式，它是一个从状态到动作的映射。

确定性策略

确定性策略直接给出一个动作：

$\pi(s) = a$

确定性策略的优点是简单明确，但缺乏探索性。

class DeterministicPolicy:
    def __init__(self, state_dim, action_dim):
        self.policy_table = {}
    
    def __call__(self, state):
        return self.policy_table.get(state, 0)
    
    def update(self, state, action):
        self.policy_table[state] = action

随机策略

随机策略给出动作的概率分布：

$\pi(a|s) = \mathbb{P}[A=a | S=s]$

随机策略的优点：

天然具有探索性
可以表示最优随机策略
在部分可观测环境中更有优势

import numpy as np

class StochasticPolicy:
    def __init__(self, state_dim, action_dim):
        self.action_dim = action_dim
        self.policy_table = {}
    
    def get_probs(self, state):
        if state not in self.policy_table:
            return np.ones(self.action_dim) / self.action_dim
        return self.policy_table[state]
    
    def sample(self, state):
        probs = self.get_probs(state)
        return np.random.choice(self.action_dim, p=probs)
    
    def update(self, state, action_probs):
        self.policy_table[state] = action_probs

最优策略

最优策略 $\pi^*$ 是能够最大化期望累积奖励的策略：

$\pi^* = \arg\max_\pi \mathbb{E}\left[\sum_{t=0}^{\infty} \gamma^t R_t \bigg| \pi\right]$

对于有限 MDP，最优策略一定存在，且可以是确定性的。

价值函数

价值函数评估状态或状态-动作对的"好坏"，是强化学习的核心概念。

状态价值函数 V(s)

状态价值函数 $V^\pi(s)$ 表示从状态 $s$ 开始，遵循策略 $\pi$ 所能获得的期望回报：

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

状态价值函数可以递归定义：

$V^\pi(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a) \left[ R(s,a,s') + \gamma V^\pi(s') \right]$

这就是著名的贝尔曼期望方程。

def compute_state_value(env, policy, state, gamma=0.99, num_samples=1000):
    total_return = 0
    for _ in range(num_samples):
        s = state
        done = False
        G = 0
        t = 0
        while not done:
            a = policy.sample(s)
            s_next, r, done = env.step(s, a)
            G += (gamma ** t) * r
            s = s_next
            t += 1
        total_return += G
    return total_return / num_samples

动作价值函数 Q(s,a)

动作价值函数 $Q^\pi(s,a)$ 表示在状态 $s$ 执行动作 $a$ 后，遵循策略 $\pi$ 所能获得的期望回报：

$Q^\pi(s,a) = \mathbb{E}_\pi\left[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \bigg| S_t = s, A_t = a\right]$

动作价值函数与状态价值函数的关系：

$Q^\pi(s,a) = \sum_{s'} P(s'|s,a) \left[ R(s,a,s') + \gamma V^\pi(s') \right]$

V 与 Q 的关系

状态价值可以表示为动作价值的期望：

$V^\pi(s) = \sum_{a} \pi(a|s) Q^\pi(s,a)$

对于确定性策略 $\pi(s) = a$ ：

$V^\pi(s) = Q^\pi(s, \pi(s))$

这个关系非常重要，它是许多强化学习算法的基础。

最优价值函数

最优状态价值函数 $V^*(s)$ 是所有策略中最大的状态价值：

$V^*(s) = \max_\pi V^\pi(s)$

最优动作价值函数 $Q^*(s,a)$ 是所有策略中最大的动作价值：

$Q^*(s,a) = \max_\pi Q^\pi(s,a)$

最优策略可以通过最优动作价值函数获得：

$\pi^*(s) = \arg\max_a Q^*(s,a)$

最优性原理

最优价值函数满足贝尔曼最优方程：

$V^*(s) = \max_a \sum_{s'} P(s'|s,a) \left[ R(s,a,s') + \gamma V^*(s') \right]$

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

贝尔曼最优方程是最优策略存在的理论基础。

示例：网格世界 MDP

让我们用一个完整的网格世界例子来理解 MDP 的各个组成部分：

import numpy as np
import matplotlib.pyplot as plt

class GridWorldMDP:
    def __init__(self, size=4, goal_states=None, trap_states=None, 
                 goal_reward=1.0, trap_reward=-1.0, step_reward=-0.01,
                 slip_prob=0.0, gamma=0.99):
        self.size = size
        self.states = [(r, c) for r in range(size) for c in range(size)]
        self.actions = ['up', 'down', 'left', 'right']
        self.action_effects = {
            'up': (-1, 0), 'down': (1, 0), 
            'left': (0, -1), 'right': (0, 1)
        }
        
        self.goal_states = goal_states or [(size-1, size-1)]
        self.trap_states = trap_states or []
        self.goal_reward = goal_reward
        self.trap_reward = trap_reward
        self.step_reward = step_reward
        self.slip_prob = slip_prob
        self.gamma = gamma
    
    def is_valid_state(self, state):
        r, c = state
        return 0 <= r < self.size and 0 <= c < self.size
    
    def get_next_state(self, state, action):
        dr, dc = self.action_effects[action]
        next_state = (state[0] + dr, state[1] + dc)
        if self.is_valid_state(next_state):
            return next_state
        return state
    
    def get_transition_probs(self, state, action):
        if state in self.goal_states or state in self.trap_states:
            return {state: 1.0}
        
        probs = {}
        intended_next = self.get_next_state(state, action)
        
        if self.slip_prob == 0:
            probs[intended_next] = 1.0
        else:
            probs[intended_next] = 1 - self.slip_prob
            for other_action in self.actions:
                if other_action != action:
                    slip_next = self.get_next_state(state, other_action)
                    probs[slip_next] = probs.get(slip_next, 0) + self.slip_prob / 3
        
        return probs
    
    def get_reward(self, state, action, next_state):
        if next_state in self.goal_states:
            return self.goal_reward
        elif next_state in self.trap_states:
            return self.trap_reward
        return self.step_reward
    
    def is_terminal(self, state):
        return state in self.goal_states or state in self.trap_states
    
    def render(self, values=None, policy=None):
        fig, ax = plt.subplots(1, 1, figsize=(8, 8))
        
        for r in range(self.size):
            for c in range(self.size):
                state = (r, c)
                if state in self.goal_states:
                    color = 'green'
                elif state in self.trap_states:
                    color = 'red'
                else:
                    color = 'white'
                
                rect = plt.Rectangle((c, self.size - 1 - r), 1, 1, 
                                      facecolor=color, edgecolor='black')
                ax.add_patch(rect)
                
                if values is not None and state in values:
                    ax.text(c + 0.5, self.size - 1 - r + 0.7, 
                           f'{values[state]:.2f}', ha='center', va='center')
                
                if policy is not None and state in policy and not self.is_terminal(state):
                    action = policy[state]
                    arrows = {'up': '↑', 'down': '↓', 'left': '←', 'right': '→'}
                    ax.text(c + 0.5, self.size - 1 - r + 0.3, 
                           arrows[action], ha='center', va='center', fontsize=20)
        
        ax.set_xlim(0, self.size)
        ax.set_ylim(0, self.size)
        ax.set_aspect('equal')
        ax.axis('off')
        plt.show()

mdp = GridWorldMDP(size=4, slip_prob=0.2)
print(f"状态空间大小: {len(mdp.states)}")
print(f"动作空间大小: {len(mdp.actions)}")

state = (0, 0)
action = 'right'
probs = mdp.get_transition_probs(state, action)
print(f"\n从状态 {state} 执行动作 '{action}' 的转移概率:")
for next_state, prob in probs.items():
    print(f"  -> {next_state}: {prob:.2f}")

输出：

状态空间大小: 16
动作空间大小: 4

从状态 (0, 0) 执行动作 'right' 的转移概率:
  -> (0, 1): 0.80
  -> (1, 0): 0.07
  -> (0, 0): 0.07
  -> (0, 0): 0.07

MDP 的扩展形式

无限状态空间 MDP

当状态空间是连续的（如机器人位置），需要使用函数近似方法：

$V(s) \approx V_\theta(s)$

其中 $\theta$ 是函数近似器的参数。

部分可观测 MDP (POMDP)

POMDP 扩展了 MDP，引入观测空间和观测概率：

$\text{POMDP} = (S, A, P, R, \Omega, O, \gamma)$

其中：

$\Omega$ 是观测空间
$O(o|s',a)$ 是在执行动作 $a$ 后到达状态 $s'$ 时观测到 $o$ 的概率

多智能体 MDP

多个智能体同时决策，需要考虑博弈论：

$G = (N, S, \{A_i\}_{i=1}^N, P, \{R_i\}_{i=1}^N, \gamma)$

其中 $N$ 是智能体数量，每个智能体有自己的动作空间和奖励函数。

小结

马尔可夫决策过程是强化学习的数学框架，它由五元组 $(S, A, P, R, \gamma)$ 定义：

状态空间 S：所有可能的状态，需要满足马尔可夫性
动作空间 A：所有可能的动作，可以是离散或连续的
状态转移概率 P：环境的动态特性，可以是确定性或随机的
奖励函数 R：引导学习的信号，设计需要反映任务目标
折扣因子 γ：平衡即时和未来奖励，确保回报有界

理解 MDP 是学习强化学习算法的基础。下一章将介绍贝尔曼方程，它描述了价值函数之间的递推关系，是求解 MDP 的关键工具。

参考文献

Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.
Puterman, M. L. (2014). Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons.
Bertsekas, D. P. (2019). Reinforcement Learning and Optimal Control. Athena Scientific.

什么是马尔可夫决策过程？​

马尔可夫性的直观理解​

MDP 的形式化定义​

状态空间 S​

动作空间 A​

状态转移概率 P​

奖励函数 R​

折扣因子 γ​

马尔可夫性的数学表述​

马尔可夫性的证明思路​

实际问题中的马尔可夫性​

策略​

确定性策略​

随机策略​

最优策略​

价值函数​

状态价值函数 V(s)​

动作价值函数 Q(s,a)​

V 与 Q 的关系​

最优价值函数​

最优性原理​

示例：网格世界 MDP​

MDP 的扩展形式​

无限状态空间 MDP​

部分可观测 MDP (POMDP)​

多智能体 MDP​

小结​

参考文献​