马尔可夫决策过程

概述

马尔可夫决策过程（Markov Decision Process，MDP）是强化学习的数学基础框架。MDP将sequential decision making问题形式化，其中：

• 智能体（Agent）与环境（Environment）交互
• 每个时间步，智能体观测状态并采取动作
• 环境根据动作转移到新状态并给予奖励
• 目标是学习最优策略最大化累积奖励

MDP的核心假设：马尔可夫性——未来仅依赖于当前状态，与历史无关。

MDP五元组

MDP由五元组 $⟨\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma ⟩$ 定义：

符号	名称	说明
$\mathcal{S}$	状态空间	所有可能状态的集合
$\mathcal{A}$	动作空间	所有可能动作的集合
$\mathcal{P}$	转移函数	$\mathcal{P}(s’
$\mathcal{R}$	奖励函数	$\mathcal{R}(s,a,s^{\prime })$ 或 $\mathcal{R}(s,a)$ 表示获得的奖励
$\gamma$	折扣因子	$\gamma \in [0,1]$ 衡量未来奖励的重要性

状态空间与动作空间

根据空间类型，MDP可分为：

类型	状态空间	动作空间
离散-离散	有限集合	有限集合
连续-离散	无限集合（如${\mathbb{R}}^n$）	有限集合
离散-连续	有限集合	无限集合
连续-连续	无限集合	无限集合

转移概率

转移函数满足：

$$\sum _{s^{\prime }\in \mathcal{S}}\mathcal{P}(s^{\prime }|s,a)=1,\forall s\in \mathcal{S},a\in \mathcal{A}$$

对于确定性环境，$\mathcal{P}(s^{\prime }|s,a)\in \{0,1\}$。

奖励函数

奖励函数有两种形式：

• 即时奖励：$\mathcal{R}(s,a)$ 或 $\mathcal{R}(s)$
• 后继奖励：$\mathcal{R}(s,a,s^{\prime })$

奖励的设计对学习效果至关重要，需要根据任务目标精心设计。

折扣因子

折扣因子 $\gamma$ 衡量未来奖励的重要性：

• $\gamma =0$：只考虑即时奖励（“短视”策略）
• $\gamma =1$：同等重视所有未来奖励
• 通常 $\gamma \in [0.9,0.999]$

折扣因子有两个重要作用：

1. 避免无限回报：确保 episodic 和 continuing 任务都有有限回报
2. 体现时间偏好：人类/智能体通常更重视近期收益

策略

定义

策略（Policy）$\pi$ 定义了在每个状态下选择动作的概率分布：

$$\pi (a|s)=P(A_t=a|S_t=s)$$

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

分类

类型	表达式	特点
贪婪策略	$\pi (s)=\arg {\max }_{a}Q(s,a)$	exploit exploit exploit
$ϵ$-贪婪	$\pi (s)=\{\begin{array}{ll}\arg {\max }_{a}Q(s,a)& \text{with prob }1-ϵ\\ \text{random }a& \text{with prob }ϵ\end{array}$	exploration + exploitation
软策略	$\pi(a	s) \propto \exp(Q(s,a)/T)$
随机策略	$\pi (a\Vert s)$	用于连续动作空间

轨迹与回报

轨迹

从初始状态 $S_0$ 开始的轨迹（trajectory）：

$$\tau =(S_0,A_0,R_1,S_1,A_1,R_2,S_2,\dots )$$

注意：$R_t=\mathcal{R}(S_{t-1},A_{t-1},S_t)$ 表示在$t-1$步采取动作后获得的奖励。

回报

从时刻$t$开始的回报（return）$G_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}$$

回报也可递归计算：

$$G_t=R_{t+1}+\gamma G_{t+1}$$

Episodic vs Continuing

类型	描述	示例
Episodes	有终止状态的任务	游戏、机器人抓取
Continuing	无限持续的任务	股票交易、控制系统

价值函数

状态价值函数

状态价值函数（State Value Function）$V^{\pi }(s)$ 表示从状态$s$开始，遵循策略$\pi$的期望回报：

$$V^{\pi }(s)={\mathbb{E}}_{\pi }[G_t|S_t=s]$$

展开：

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

动作价值函数

动作价值函数（Action Value Function）$Q^{\pi }(s,a)$ 表示从状态$s$开始，执行动作$a$后遵循策略$\pi$的期望回报：

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

优势函数

优势函数（Advantage Function）$A^{\pi }(s,a)$ 衡量在状态$s$下执行动作$a$相对于策略$\pi$的平均优势：

$$A^{\pi }(s,a)=Q^{\pi }(s,a)-V^{\pi }(s)$$

• $A^{\pi }(s,a)>0$：动作$a$优于平均
• $A^{\pi }(s,a)<0$：动作$a$劣于平均
• $A^{\pi }(s,a)=0$：动作$a$等于平均

函数关系

$$\begin{array}{rl}{V}^{\pi }(s)& =\sum _{a\in \mathcal{A}}\pi (a|s)Q^{\pi }(s,a)\\ Q^{\pi }(s,a)& =\mathcal{R}(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}\mathcal{P}(s^{\prime }|s,a)V^{\pi }(s^{\prime })\\ V^{\pi }(s)& =\sum _{a\in \mathcal{A}}\pi (a|s)\left[\mathcal{R}(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}\mathcal{P}(s^{\prime }|s,a)V^{\pi }(s^{\prime })\right]\end{array}$$

最优策略

定义

最优策略 ${\pi }^{\ast }$ 是使状态价值函数最大化的策略：

$${\pi }^{\ast }=\arg \underset{\pi }{\max }{V}^{\pi }(s),\forall s\in \mathcal{S}$$

对应的最优价值函数：

$$V^{\ast }(s)=\underset{\pi }{\max }{V}^{\pi }(s),Q^{\ast }(s,a)=\underset{\pi }{\max }{Q}^{\pi }(s,a)$$

最优性条件

策略 ${\pi }^{\ast }$ 为最优，当且仅当：

$${\pi }^{\ast }(a|s)>0⟹a\in \arg \underset{a}{\max }{Q}^{\ast }(s,a)$$

即：最优策略在每个状态下总是选择能最大化最优Q值的动作。

示例：Grid World

问题描述

网格世界：
+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 |
+---+---+---+---+---+
| 5 | 6 | 7 | 8 | 9 |
+---+---+---+---+---+
|10 |11 |12 |13 |14 |
+---+---+---+---+---+

- 智能体可执行4个动作：up, down, left, right
- 目标状态：14（获得+1奖励）
- 边界状态：墙壁（保持原位）
- 其他状态：每步获得-0.1奖励
- 折扣因子：γ = 0.9

Python实现

import numpy as np
 
class GridWorld:
    """简单的4x5网格世界"""
    
    def __init__(self):
        self.n_states = 15  # 0-14
        self.n_actions = 4  # 0:up, 1:down, 2:left, 3:right
        self.gamma = 0.9
        self.reward_target = 1.0
        self.reward_step = -0.1
        
        # 转移概率（确定性环境）
        self.P = np.zeros((self.n_states, self.n_actions, self.n_states))
        self._build_transition()
    
    def _build_transition(self):
        """构建转移概率矩阵"""
        for s in range(self.n_states):
            row, col = s // 5, s % 5
            
            for a in range(self.n_actions):
                # 计算下一个位置
                if a == 0:   # up
                    nr, nc = max(0, row - 1), col
                elif a == 1: # down
                    nr, nc = min(2, row + 1), col
                elif a == 2: # left
                    nr, nc = row, max(0, col - 1)
                else:        # right
                    nr, nc = row, min(4, col + 1)
                
                next_s = nr * 5 + nc
                self.P[s, a, next_s] = 1.0
    
    def step(self, s, a):
        """执行动作，返回(next_state, reward, done)"""
        next_s = np.argmax(self.P[s, a])  # 确定性转移
        reward = self.reward_target if s == 14 else self.reward_step
        done = (s == 14)
        return next_s, reward, done
    
    def reward_fn(self, s, a, next_s):
        """奖励函数"""
        return self.reward_target if s == 14 else self.reward_step
 
 
def evaluate_policy(env, pi, theta=1e-6, max_iterations=1000):
    """策略评估：计算给定策略下的状态价值函数"""
    V = np.zeros(env.n_states)
    
    for _ in range(max_iterations):
        delta = 0
        for s in range(env.n_states):
            v = 0
            for a in range(env.n_actions):
                next_s = np.argmax(env.P[s, a])
                r = env.reward_fn(s, a, next_s)
                v += pi[s, a] * (r + env.gamma * V[next_s])
            delta = max(delta, abs(v - V[s]))
            V[s] = v
        if delta < theta:
            break
    
    return V
 
 
# 均匀随机策略
env = GridWorld()
pi = np.ones((env.n_states, env.n_actions)) / env.n_actions
 
# 评估策略
V = evaluate_policy(env, pi)
print("状态价值函数：")
for row in range(3):
    print([f"{V[row*5+col]:.3f}" for col in range(5)])

输出示例

状态价值函数：
['-0.613', '-0.552', '-0.492', '-0.431', '-0.372']
['-0.672', '-0.610', '-0.548', '-0.486', '-0.424']
['-0.730', '-0.668', '-0.605', '-0.542', '-0.479']

可见越靠近目标状态（右下角），价值越高。

与其他模型的关系

MDP vs 马尔可夫链

马尔可夫链只有状态转移，没有动作和奖励：

• 马尔可夫链：$\mathcal{P}(s^{\prime }|s)$
• MDP：$\mathcal{P}(s^{\prime }|s,a)$ + 动作选择

详见 马尔可夫链。

MDP vs 隐马尔可夫模型

HMM用于推断隐藏状态，MDP用于决策：

• HMM：给定观测序列，推断隐藏状态
• MDP：给定状态，决策动作

详见 隐马尔可夫模型。

参考

---

后续主题

• 贝尔曼方程：价值函数的递归关系
• 动态规划：策略迭代与价值迭代
• Q-Learning：无模型强化学习