马尔可夫决策过程

马尔可夫决策过程（Markov Decision Process，简称 MDP）是强化学习的数学基础。几乎所有强化学习问题都可以形式化为 MDP，理解 MDP 对于掌握强化学习至关重要。

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

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

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

MDP 的形式化定义

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

状态空间 S

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

有限状态空间：状态数量有限，如棋盘游戏中的局面
无限状态空间：状态数量无限或连续，如机器人的位置坐标

# 示例：网格世界环境的状态空间
# 4x4 网格，共 16 个状态
states = list(range(16))  # S = {0, 1, 2, ..., 15}

动作空间 A

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

离散动作空间：动作数量有限，如上下左右
连续动作空间：动作是连续值，如方向盘转角

# 示例：网格世界的动作空间
actions = [0, 1, 2, 3]  # A = {上, 下, 左, 右}

状态转移概率 P

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

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

# 示例：确定性环境的状态转移
# 在状态 0 执行"向右"动作，一定转移到状态 1
transition = {
    (0, 1): 1,  # (state, action) -> next_state
}

# 示例：随机环境的状态转移
# 在冰面滑行，有概率滑到其他位置
transition_prob = {
    (0, 'right'): {1: 0.33, 4: 0.33, 0: 0.34},  # 可能滑到不同位置
}

奖励函数 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)$ ，只依赖于当前状态或状态-动作对。

# 示例：网格世界的奖励函数
def reward(state, action, next_state):
    if next_state == goal_state:
        return 1.0    # 到达目标获得正奖励
    elif next_state in trap_states:
        return -1.0   # 掉入陷阱获得负奖励
    else:
        return -0.01  # 每走一步给予小惩罚，鼓励快速到达目标

折扣因子 γ

折扣因子 $\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}$

其中 $G_t$ 是从时刻 $t$ 开始的累积折扣奖励，称为回报。

# 示例：计算折扣回报
gamma = 0.99
rewards = [1, 1, 1, 1, 1]  # 奖励序列

returns = 0
for t, r in enumerate(rewards):
    returns += (gamma ** t) * r

print(f"折扣回报: {returns:.4f}")  # 折扣回报: 4.9010

马尔可夫性

马尔可夫性是 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]$

这意味着：

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

为什么马尔可夫性重要？

简化决策：只需要考虑当前状态，不需要处理复杂的历史
理论保证：在马尔可夫假设下，存在最优策略
计算可行：可以使用动态规划等方法求解

实际问题中的马尔可夫性

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

部分可观测：智能体只能看到部分状态，如扑克牌游戏
历史依赖：某些决策需要参考历史信息

解决方案：

使用状态增强，将历史信息编码到状态中
使用循环神经网络处理序列信息
使用部分可观测马尔可夫决策过程（POMDP）建模

策略

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

确定性策略

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

$\pi(s) = a$

def deterministic_policy(state):
    if state == 0:
        return 'right'
    elif state == 1:
        return 'down'
    else:
        return 'left'

随机策略

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

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

import numpy as np

def stochastic_policy(state):
    if state == 0:
        return {'right': 0.7, 'down': 0.3}
    else:
        return {'left': 0.5, 'right': 0.5}

def sample_action(state):
    probs = stochastic_policy(state)
    actions = list(probs.keys())
    probabilities = list(probs.values())
    return np.random.choice(actions, p=probabilities)

最优策略

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

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

价值函数

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

状态价值函数 V(s)

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

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

def state_value(env, policy, state, gamma=0.99, num_episodes=1000):
    total_returns = 0
    for _ in range(num_episodes):
        env.reset()
        env.state = state
        returns = 0
        t = 0
        done = False
        while not done:
            action = policy(env.state)
            next_state, reward, done, _ = env.step(action)
            returns += (gamma ** t) * reward
            t += 1
        total_returns += returns
    return total_returns / num_episodes

动作价值函数 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} | S_t = s, A_t = a\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)$

示例：网格世界 MDP

让我们用一个简单的网格世界例子来理解 MDP：

import numpy as np

class GridWorldMDP:
    def __init__(self, size=4):
        self.size = size
        self.states = list(range(size * size))
        self.actions = [0, 1, 2, 3]  # 上、下、左、右
        self.goal = size * size - 1  # 目标在右下角
        
    def transition(self, state, action):
        row, col = state // self.size, state % self.size
        
        if action == 0:    # 上
            row = max(0, row - 1)
        elif action == 1:  # 下
            row = min(self.size - 1, row + 1)
        elif action == 2:  # 左
            col = max(0, col - 1)
        elif action == 3:  # 右
            col = min(self.size - 1, col + 1)
            
        next_state = row * self.size + col
        return next_state
    
    def reward(self, state, action, next_state):
        if next_state == self.goal:
            return 1.0
        return -0.01  # 每步小惩罚
    
    def is_terminal(self, state):
        return state == self.goal

mdp = GridWorldMDP()
print(f"状态空间大小: {len(mdp.states)}")
print(f"动作空间大小: {len(mdp.actions)}")
print(f"从状态 0 向右移动: 状态 {mdp.transition(0, 3)}")
print(f"到达目标的奖励: {mdp.reward(0, 3, 15)}")

输出：

状态空间大小: 16
动作空间大小: 4
从状态 0 向右移动: 状态 1
到达目标的奖励: 1.0

小结

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

状态空间 S：所有可能的状态
动作空间 A：所有可能的动作
状态转移概率 P：环境的动态特性
奖励函数 R：引导学习的信号
折扣因子 γ：平衡即时和未来奖励

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

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

MDP 的形式化定义​

状态空间 S​

动作空间 A​

状态转移概率 P​

奖励函数 R​

折扣因子 γ​

马尔可夫性​

为什么马尔可夫性重要？​

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

策略​

确定性策略​

随机策略​

最优策略​

价值函数​

状态价值函数 V(s)​

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

V 与 Q 的关系​

最优价值函数​

示例：网格世界 MDP​

小结​