SDSC6007 课程 4-马尔可夫决策过程

#sdsc6007

English / 中文

强化学习的元素

强化学习包含以下五个核心元素：

• 智能体与环境：智能体执行动作，环境返回观测和奖励

• 奖励信号：标量反馈信号，指示智能体在时间t的表现

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

• 价值函数：预测预期未来奖励（在特定策略下）

• 模型：预测环境的行为/回报

智能体与环境的交互

在每个时间步t：

• 智能体执行动作 $A_t$，接收观测 $O_t$ 和标量奖励 $R_t$

• 环境接收动作 $A_t$，发出观测 $O_{t+1}$ 和标量奖励 $R_{t+1}$

历史是观测、动作和奖励的序列：

$$H_t = O_1, R_1, A_1, \ldots, A_{t-1}, O_t, R_t$$

状态的定义

状态 $S_t$ 是马尔可夫的，当且仅当它包含历史中的所有有用信息：

$$P(S_{t+1} \mid S_t) = P(S_{t+1} \mid S_1, \ldots, S_t)$$

一旦状态已知，历史就可以丢弃。

关键理解：马尔可夫性质意味着"未来只依赖于现在，而不依赖于过去"，这大大简化了问题的建模。

探索与利用的权衡

• 探索：寻找关于环境的更多信息

• 利用：基于当前信息最大化总奖励

• 存在权衡关系（需要平衡两者）

实际例子：

• 选择餐厅：利用（去最喜欢的餐厅）vs 探索（尝试新餐厅）
• 在线广告：利用（显示相关产品）vs 探索（显示不同的广告）
• 选修课程：利用（选择之前最好的老师）vs 探索（尝试新老师）

马尔可夫决策过程介绍

基础与马尔可夫链

马尔可夫链/马尔可夫过程描述了一个无记忆的随机过程（没有奖励和动作），即具有马尔可夫性质的序列 $S_1, S_2, \ldots$

定义：有限状态马尔可夫链是一个元组 $\langle \mathcal{S}, P \rangle$

• $\mathcal{S}$ 是有限状态集合

• $P$ 是状态转移概率矩阵，其中 $p_{ss'} = P(S_{t+1} = s' \mid S_t = s)$

$P \in \mathbb{R}^{S \times S}$ 可表示为：

$$P = \begin{bmatrix} p_{11} & p_{12} & \cdots & p_{1S} \\ p_{21} & p_{22} & \cdots & p_{2S} \\ \vdots & \vdots & \ddots & \vdots \\ p_{S1} & p_{S2} & \cdots & p_{SS} \end{bmatrix}$$

其中矩阵的每一行之和为1。

示例

转移矩阵如下：

From \ To	Lec1	Lec2	Lec3	HW1	IG	FB	Sleep
Lec1		0.7			0.3
Lec2			0.6			0.4
Lec3				0.5	0.25		0.25
HW1							1
IG	0.5				0.2	0.3
FB					0.5	0.5
Sleep							1

马尔可夫奖励过程

马尔可夫奖励过程 = 马尔可夫链 + 奖励（仍然没有动作或固定策略）

定义：MRP是一个元组 $\langle \mathcal{S}, P, r, \gamma \rangle$

• $\mathcal{S}$ 是有限状态集合

• $P$ 是状态转移概率矩阵

• $r$ 是奖励函数，$r_s = \mathbb{E}[R_{t+1} \mid S_t = s]$

• $\gamma$ 是折扣因子，$\gamma \in [0, 1]$

示例：

回报与价值函数

回报 $G_t$ 是从时间步t开始的总折扣奖励：

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

状态价值函数 $v(s)$ 是从状态s开始的预期回报：

$$v(s) = \mathbb{E}[G_t \mid S_t = s]$$

MRP的贝尔曼方程详解

马尔可夫奖励过程（MRP）的贝尔曼方程是强化学习中的核心方程，它建立了状态价值与后续状态价值之间的关系。

1. 方程推导

从价值函数的定义出发：

$$v(s) = \mathbb{E}[G_t \mid S_t = s] = \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \mid S_t = s]$$

将其分解为即时奖励和未来奖励的折现：

$$v(s) = \mathbb{E}[R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} + \cdots) \mid S_t = s]$$

$$v(s) = \mathbb{E}[R_{t+1} + \gamma G_{t+1} \mid S_t = s]$$

利用马尔可夫性和期望的线性性质：

$$v(s) = \mathbb{E}[R_{t+1} \mid S_t = s] + \gamma \mathbb{E}[G_{t+1} \mid S_t = s]$$

$$v(s) = r_s + \gamma \sum_{s' \in \mathcal{S}} p_{ss'} \mathbb{E}[G_{t+1} \mid S_{t+1} = s']$$

$$v(s) = r_s + \gamma \sum_{s' \in \mathcal{S}} p_{ss'} v(s')$$

2. 参数说明

• $v(s)$: 状态s的价值，表示从状态s开始所能获得的期望累积奖励

• $r_s$: 即时奖励的期望值，$r_s = \mathbb{E}[R_{t+1} \mid S_t = s]$

• $\gamma$: 折扣因子（0 ≤ γ ≤ 1）

  • γ = 0：只考虑即时奖励
  • γ → 1：越来越重视未来奖励
  • 通常设为0.9-0.99之间的值

• $p_{ss'}$: 从状态s转移到状态s’的概率

• $\mathcal{S}$: 所有可能的状态集合

3. 矩阵形式

将每个状态的价值组成向量 $v = [v(1), v(2), \ldots, v(S)]^T$，奖励组成向量 $r = [r_1, r_2, \ldots, r_S]^T$，得到矩阵形式：

$$v = r + \gamma P v$$

其中P是状态转移概率矩阵。

4. 解析解

通过代数变换：

$$v - \gamma P v = r$$

$$(I - \gamma P)v = r$$

$$v = (I - \gamma P)^{-1} r$$

注意：该解析解只在状态空间较小时实用，因为矩阵求逆的复杂度为O(S³)。

实际例子

假设有三个状态{A, B, C}，γ=0.9，奖励函数和转移概率如下：

状态	奖励	转移到A	转移到B	转移到C
A	1	0.2	0.5	0.3
B	2	0.1	0.6	0.3
C	-1	0.4	0.4	0.2

建立贝尔曼方程：

$$v(A) = 1 + 0.9(0.2v(A) + 0.5v(B) + 0.3v(C))$$

$$v(B) = 2 + 0.9(0.1v(A) + 0.6v(B) + 0.3v(C))$$

$$v(C) = -1 + 0.9(0.4v(A) + 0.4v(B) + 0.2v(C))$$

转换为矩阵形式：

$$\begin{bmatrix} v(A) \\ v(B) \\ v(C) \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \\ -1 \end{bmatrix} + 0.9 \begin{bmatrix} 0.2 & 0.5 & 0.3 \\ 0.1 & 0.6 & 0.3 \\ 0.4 & 0.4 & 0.2 \end{bmatrix} \begin{bmatrix} v(A) \\ v(B) \\ v(C) \end{bmatrix}$$

解得：

$$v = (I - 0.9P)^{-1} r$$

通过计算可得各状态的具体价值值。

马尔可夫决策过程

马尔可夫决策过程 = 马尔可夫奖励过程 + 动作

定义：MDP是一个元组 $\langle \mathcal{S}, \mathcal{A}, P, r, \gamma \rangle$

• $\mathcal{S}$ 是有限状态集合

• $\mathcal{A}$ 是有限动作集合

• $P$ 是状态转移核，$p_{sas'} = P(S_{t+1} = s' \mid S_t = s, A_t = a)$

• $r$ 是奖励函数，$r_{sa} = \mathbb{E}[R_{t+1} \mid S_t = s, A_t = a]$

• $\gamma$ 是折扣因子，$\gamma \in [0, 1]$

策略

策略 $\pi$ 是给定状态下动作的分布：

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

这称为随机策略。

MDP中的最优性条件

有限视野情况与贝尔曼算子

目标：最大化 $\mathbb{E}[\sum_{t=0}^{T-1} \gamma^t R_{t+1}]$

使用DP算法，我们有：

$$J_{N-t}(s) = \max_{a \in \mathcal{A}} \left( \gamma^{N-t} r_{sa} + \sum_{s' \in \mathcal{S}} p_{sas'} \cdot J_{N-t+1}(s') \right)$$

$$J_N(s) = \gamma^N \times 0 = 0$$

归一化：$v_t(s) = \frac{J_{N-t}(s)}{\gamma^{N-t}}$

$$v_{t+1}(s) = \max_{a \in \mathcal{A}} \left( r_{sa} + \gamma \sum_{s' \in \mathcal{S}} p_{sas'} \cdot v_t(s') \right)$$

$$v_0(s) = 0$$

贝尔曼算子

定义贝尔曼算子 $\mathcal{T}$：

$$(\mathcal{T}v)(s) = \max_{a \in \mathcal{A}} \left( r_{sa} + \gamma \sum_{s' \in \mathcal{S}} p_{sas'} \cdot v(s') \right)$$

定义 $\mathcal{T}^k v(s) = \mathcal{T}(\mathcal{T}^{k-1} v)(s)$（其中 $\mathcal{T}^0 v(s) = v(s)$）

我们可以用 $\mathcal{T}^N v_0 = v_N = J_0$ 解决有限视野问题

对于静态确定性策略 $\pi$，定义策略下的贝尔曼算子 $\mathcal{T}_\pi$：

$$(\mathcal{T}_\pi v)(s) = r_{s\pi(s)} + \gamma \sum_{s' \in \mathcal{S}} p_{s\pi(s)s'} \cdot v(s')$$

贝尔曼算子的性质

单调性引理

考虑 $v, v' \in \mathbb{R}^S$，其中 $v(s) \leq v'(s)$, $\forall s \in \mathcal{S}$：

$$(\mathcal{T}^k v)(s) \leq (\mathcal{T}^k v')(s), \quad s \in \mathcal{S}, k = 1, 2, \ldots$$

同样适用于任何静态策略 $\pi$

如果 $v(s) \leq (\mathcal{T}v)(s)$, $\forall s \in \mathcal{S}$，则：

$$(\mathcal{T}^k v)(s) \leq (\mathcal{T}^{k+1} v)(s), \quad s \in \mathcal{S}, k = 1, 2, \ldots$$

常数偏移引理

对于任何静态策略 $\pi$，标量 $b$, $v \in \mathbb{R}^S$：

$$(\mathcal{T}^k (v + b \cdot 1_S))(s) = (\mathcal{T}^k v)(s) + \gamma^k b, \quad s \in \mathcal{S}, k = 1, 2, \ldots$$

$$(\mathcal{T}_\pi^k (v + b \cdot 1_S))(s) = (\mathcal{T}_\pi^k v)(s) + \gamma^k b, \quad s \in \mathcal{S}, k = 1, 2, \ldots$$

其中 $1_S \in \mathbb{R}^S$ 是全1向量。

命题：DP算法的收敛性

假设

1. 即时奖励 $R_t$ 有界，即对某个常数M，$|R_t| \leq M$

2. $0 < \gamma < 1$

命题

对于任何初始猜测 $v_0 \in \mathbb{R}^S$，对于任何 $s \in \mathcal{S}$：

$$v^\star(s) = \lim_{N \to \infty} (\mathcal{T}^N v_0)(s)$$

其中 $v^\star$ 是最优价值函数，即：

$$v^\star(s_0) = \max_\pi \lim_{K \to \infty} \mathbb{E} \left[ \sum_{t=0}^K \gamma^t R_{t+1} \mid S_0 = s_0 \right]$$

同样，对于固定策略 $\pi$：

$$v_\pi^\star(s) = \lim_{N \to \infty} (\mathcal{T}_\pi^N v_0)(s)$$

深度理解：这个命题表明，无论我们从什么样的初始价值估计开始，通过不断应用贝尔曼算子，最终都会收敛到真正的最优价值函数。

命题：贝尔曼方程

命题

最优价值函数 $v^\star$ 满足对所有 $s \in \mathcal{S}$：

$$v^\star(s) = \max_{a \in \mathcal{A}} \left( r_{sa} + \gamma \sum_{s' \in \mathcal{S}} p_{sas'} \cdot v^\star(s') \right)$$

或等价地：

$$v^\star = \mathcal{T} v^\star$$

而且 $v^\star$ 是这个方程的唯一解（因此，这个方程的解必须是最优价值函数）。

同样，对于任何 $v \in \mathbb{R}^S$，其中 $v \geq \mathcal{T}v$（或 $v \leq \mathcal{T}v$），我们有 $v \geq v^\star$（或 $v \leq v^\star$，分别）。

对于固定策略 $\pi$，相关价值函数 $v_\pi$ 满足：

$$v_\pi(s) = r_{s\pi(s)} + \gamma \sum_{s' \in \mathcal{S}} p_{s\pi(s)s'} \cdot v_\pi(s')$$

或等价地：

$$v_\pi = \mathcal{T}_\pi v_\pi$$

命题：最优性的必要与充分条件

命题

一个静态策略 $\pi$ 是最优的，当且仅当 $\pi(s)$ 对每个 $s \in \mathcal{S}$ 在贝尔曼方程中达到最大值，即：

$$\mathcal{T} v^\star = \mathcal{T}_\pi v^\star$$

含义

1. 首先计算 $v^\star$

2. 对每个 $s \in \mathcal{S}$，选择：

$$a_s \in \arg\max_{a \in \mathcal{A}} \left( r_{sa} + \gamma \sum_{s' \in \mathcal{S}} p_{sas'} \cdot v^\star(s') \right)$$

3. 构建一个策略 $\pi$，使得 $\pi(s) = a_s$

4. 通过构造，$\mathcal{T} v^\star = \mathcal{T}_\pi v^\star$

5. $\pi$ 是最优静态确定性策略

唯一性与随机策略

• 最优策略不是唯一的

• 对于任何 $s \in \mathcal{S}$，可能有多个 $a_s$ 满足上述条件

• 随机选择 $\{a_{s1}, a_{s2}, \ldots, a_{sK}\}$ 中的任何动作在状态s下是最优的

• 随机策略：$\pi(a \mid s) = P(A_t = a \mid S_t = s)$

• 最优随机策略：如果 $a \in \{a_{s1}, a_{s2}, \ldots, a_{sK}\}$，则 $\pi(a \mid s) > 0$，否则 $\pi(a \mid s) = 0$

关键结论：在MDP设置中，最好的确定性策略与最好的随机策略表现一样好，随机策略不会提供额外的优势。