强化学习基石：马尔可夫决策过程（MDP）详解

摘要：马尔可夫决策过程（Markov Decision Process, MDP）是强化学习的核心理论框架。本文将从基础概念出发，深入剖析MDP的数学原理、核心要素、价值函数与贝尔曼方程，并通过实例帮助读者建立完整的知识体系。

1. 引言：从马尔可夫性到序列决策

在强化学习中，智能体（Agent）需要在环境中通过试错来学习最优策略。这一过程本质上是一个序列决策问题，而马尔可夫决策过程正是描述这类问题的强大数学工具。

马尔可夫性（Markov Property）是MDP的基石：系统的未来状态仅依赖于当前状态，而与历史状态无关。即：
$$P(s_{t+1}|s_t,s_{t-1},...,s_0)=P(s_{t+1}|s_t)$$

这一"无记忆性"特性极大地简化了复杂决策问题的建模难度。

2. MDP的数学定义

一个马尔可夫决策过程可以用五元组 formally 定义：

$$\mathcal{M}=(\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma )$$

其中每个元素都扮演着至关重要的角色。

3. MDP的五个核心要素详解

3.1 状态空间 $\mathcal{S}$（State Space）

状态空间是所有可能状态的集合。状态必须包含决策所需的全部信息：

• 离散状态：如网格世界中的格子位置 {1,2,...,N}\{1, 2, ..., N\}{1,2,...,N}
• 连续状态：如机器人的关节角度、速度等

# 示例：网格世界状态
states = [(i, j) for i in range(5) for j in range(5)]  # 5x5网格

3.2 动作空间 $\mathcal{A}$（Action Space）

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

• 离散动作：如{上, 下, 左, 右}
• 连续动作：如方向盘转动角度 $[-90°,90°]$

# 离散动作示例
actions = ['up', 'down', 'left', 'right']

3.3 状态转移概率 $\mathcal{P}$（Transition Probability）

$\mathcal{P}$ 定义了环境动力学，即执行动作后状态转移的概率分布：

$$\mathcal{P}(s^{\prime }|s,a)=P(s_{t+1}=s^{\prime }|s_t=s,a_t=a)$$

关键特性：

• 转移概率仅依赖当前状态$s$和动作$a$（马尔可夫性）
• 环境可能是确定性的或随机的
• 智能体无法控制转移概率，只能通过选择动作间接影响

3.4 奖励函数 $\mathcal{R}$（Reward Function）

奖励函数为状态转移提供即时反馈：

$$\mathcal{R}(s,a,s^{\prime })=E[r_t|s_t=s,a_t=a,s_{t+1}=s^{\prime }]$$

设计原则：

• 奖励塑造（Reward Shaping）对学习效率至关重要
• 稀疏奖励 vs 密集奖励
• 奖励范围通常归一化到 $[-1,1]$ 或 $[0,1]$

def reward_function(state, action, next_state):
    if next_state == goal_state:
        return +10.0  # 到达目标
    elif next_state in obstacles:
        return -5.0   # 撞到障碍物
    else:
        return -0.1   # 每步的微小惩罚（鼓励快速到达）

3.5 折扣因子 $\gamma$（Discount Factor）

$\gamma \in [0,1]$ 用于权衡即时奖励与未来奖励的重要性：

• $\gamma =0$：只关心即时奖励（短视）
• $\gamma \to 1$：更重视长期回报
• 数学上保证无穷序列的总回报收敛

$$G_t=r_t+\gamma r_{t+1}+{\gamma }^2{r}_{t+2}+...=\sum _{k=0}^{\infty }{\gamma }^k{r}_{t+k}$$

4. 策略与价值函数

4.1 策略 $\pi$（Policy）

策略是状态到动作的映射，描述智能体的行为方式：

• 确定性策略：$\pi (s)\to a$
• 随机性策略：$\pi (a|s)=P(A_t=a|S_t=s)$

目标是找到最优策略 ${\pi }^{\ast }$ 以最大化期望回报。

4.2 状态价值函数 $V^{\pi }(s)$

在策略$\pi$下，状态$s$的期望回报：

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

4.3 动作价值函数 $Q^{\pi }(s,a)$

在状态$s$执行动作$a$后，遵循策略$\pi$的期望回报：

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

两者关系：
$$V^{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a|s)\cdot Q^{\pi }(s,a)$$

5. 贝尔曼方程：动态规划的核心

5.1 贝尔曼期望方程

价值函数可以递归地表示：

状态价值函数：
$$V^{\pi }(s)=\sum _a\pi (a|s)\sum _{s^{\prime }}\mathcal{P}(s^{\prime }|s,a)\left[\mathcal{R}(s,a,s^{\prime })+\gamma V^{\pi }(s^{\prime })\right]$$

动作价值函数：
$$Q^{\pi }(s,a)=\sum _{s^{\prime }}\mathcal{P}(s^{\prime }|s,a)\left[\mathcal{R}(s,a,s^{\prime })+\gamma \sum _{a^{\prime }}\pi (a^{\prime }|s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })\right]$$

5.2 贝尔曼最优方程

最优价值函数满足：

$$V^{\ast }(s)=\underset{a}{\max }\sum _{s^{\prime }}\mathcal{P}(s^{\prime }|s,a)\left[\mathcal{R}(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime })\right]$$

$$Q^{\ast }(s,a)=\sum _{s^{\prime }}\mathcal{P}(s^{\prime }|s,a)\left[\mathcal{R}(s,a,s^{\prime })+\gamma \underset{a^{\prime }}{\max }{Q}^{\ast }(s^{\prime },a^{\prime })\right]$$

最优策略：
$${\pi }^{\ast }(s)=\arg \underset{a}{\max }{Q}^{\ast }(s,a)$$

6. MDP的求解方法

6.1 动态规划方法

策略迭代（Policy Iteration）：

1. 策略评估：计算当前策略的价值函数
2. 策略改进：基于价值函数更新策略
3. 重复直至收敛

价值迭代（Value Iteration）：

• 直接迭代贝尔曼最优方程
• 每次迭代更新：$V_{k+1}(s)={\max }_a{\sum }_{s^{\prime }}\mathcal{P}(s^{\prime }|s,a)[\mathcal{R}(s,a,s^{\prime })+\gamma V_k(s^{\prime })]$

6.2 蒙特卡洛方法

• 通过采样轨迹估计价值函数
• 无需环境模型（无需知道$\mathcal{P}$）
• 适用于片段式任务（Episodic Tasks）

6.3 时序差分学习

结合动态规划和蒙特卡洛的优点：

• Q-learning：离策略学习
  $$Q(s,a)\leftarrow Q(s,a)+\alpha [r+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime })-Q(s,a)]$$

• SARSA： on-policy学习
  $$Q(s,a)\leftarrow Q(s,a)+\alpha [r+\gamma Q(s^{\prime },a^{\prime })-Q(s,a)]$$

7. 实例：GridWorld网格世界

考虑一个5x5的网格世界：

  0  1  2  3  4
0 S  .  .  .  .
1 .  X  .  .  .
2 .  .  .  X  .
3 .  X  .  .  .
4 .  .  .  .  G

• 状态：agent的位置坐标
• 动作：上下左右
• 转移：动作有80%概率成功，20%随机方向
• 奖励：每步-0.1，到达目标(G)+10，碰到障碍(X)-5
• 折扣因子：$\gamma =0.9$

Python实现：

import numpy as np

class GridWorldMDP:
    def __init__(self, size=5):
        self.size = size
        self.states = [(i, j) for i in range(size) for j in range(size)]
        self.actions = ['up', 'down', 'left', 'right']
        self.gamma = 0.9
        self.obstacles = [(1,1), (3,1), (2,3)]
        self.goal = (4,4)
        self.start = (0,0)
        
    def get_transitions(self, state, action):
        """返回转移概率、下一状态、奖励的列表"""
        if state == self.goal or state in self.obstacles:
            return [(1.0, state, 0.0)]  # 终止状态
        
        transitions = []
        intended_prob = 0.8
        random_prob = 0.2
        
        # 尝试执行动作
        next_state = self._move(state, action)
        reward = self._get_reward(state, action, next_state)
        transitions.append((intended_prob, next_state, reward))
        
        # 随机动作
        for a in self.actions:
            if a != action:
                next_state = self._move(state, a)
                reward = self._get_reward(state, a, next_state)
                transitions.append((random_prob/3, next_state, reward))
        
        return transitions
    
    def _move(self, state, action):
        """根据动作移动"""
        i, j = state
        if action == 'up': i = max(0, i-1)
        elif action == 'down': i = min(self.size-1, i+1)
        elif action == 'left': j = max(0, j-1)
        elif action == 'right': j = min(self.size-1, j+1)
        return (i, j)
    
    def _get_reward(self, state, action, next_state):
        """获取奖励"""
        if next_state == self.goal:
            return 10.0
        elif next_state in self.obstacles:
            return -5.0
        return -0.1

# 价值迭代求解
def value_iteration(mdp, theta=1e-6):
    V = {s: 0 for s in mdp.states}
    
    while True:
        delta = 0
        for s in mdp.states:
            if s == mdp.goal or s in mdp.obstacles:
                continue
                
            v = V[s]
            # 贝尔曼最优更新
            action_values = []
            for a in mdp.actions:
                q_value = 0
                for prob, s_next, reward in mdp.get_transitions(s, a):
                    q_value += prob * (reward + mdp.gamma * V[s_next])
                action_values.append(q_value)
            
            V[s] = max(action_values)
            delta = max(delta, abs(v - V[s]))
        
        if delta < theta:
            break
    
    return V

# 运行求解
mdp = GridWorldMDP()
V_optimal = value_iteration(mdp)

# 输出结果
print("最优价值函数:")
for i in range(5):
    row = []
    for j in range(5):
        row.append(f"{V_optimal[(i,j)]:.2f}")
    print("\t".join(row))

输出示例：

最优价值函数:
5.21	5.84	6.49	7.11	7.32
4.58	0.00	7.32	8.11	8.32
3.95	4.58	8.11	0.00	9.21
3.32	0.00	8.95	9.79	10.00
2.68	3.32	4.58	5.84	0.00

8. MDP与强化学习的关系

MDP为强化学习提供了严格的理论框架：

特性	MDP理论	强化学习实践
状态转移	已知$\mathcal{P}$	通常未知，需学习
奖励函数	已知$\mathcal{R}$	可能已知或未知
求解方法	动态规划	蒙特卡洛、TD、策略梯度等
假设	完全可观测	可能部分可观测（POMDP）

扩展模型：

• POMDP（部分可观测MDP）：引入观测概率
• 连续MDP：状态/动作空间连续
• 多智能体MDP：博弈论与MDP结合

9. 总结与最佳实践

核心要点回顾

1. 五元组：$(\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma )$ 完整定义了决策问题
2. 贝尔曼方程：提供了价值函数的递归计算方式
3. 最优性原理：最优策略可通过最大化Q值获得
4. 求解思路：评估 → 改进的迭代过程

设计MDP的建议

1. 状态设计：确保满足马尔可夫性，包含必要信息
2. 奖励塑造：避免稀疏奖励，提供有效引导信号
3. 折扣因子：根据任务时间跨度调整（长期任务用较大$\gamma$）
4. 动作空间：平衡表达能力与搜索复杂度

参考文献

1. Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press.
2. Puterman, M. L. (2014). Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons.
3. Silver, D. (2015). “Markov Decision Processes”. UCL Course on RL.