【基础】价值迭代（Value Iteration）算法详解

# 1. 价值迭代算法概述**

价值迭代算法是一种用于解决马尔可夫决策过程（MDP）的动态规划算法。它通过迭代更新价值函数来找到MDP的最佳策略，该策略最大化从当前状态开始的长期奖励。价值迭代算法广泛应用于强化学习、运筹学和经济学等领域。

# 2. 价值迭代算法的理论基础

### 2.1 马尔可夫决策过程（MDP）

马尔可夫决策过程（MDP）是一种用于建模顺序决策问题的数学框架。它由以下元素组成：

- **状态空间（S）：**所有可能的状态集合。
- **动作空间（A）：**在每个状态下可采取的所有动作集合。
- **转移概率（P）：**从状态 s 执行动作 a 转移到状态 s' 的概率。
- **奖励函数（R）：**在状态 s 执行动作 a 后获得的立即奖励。
- **折扣因子（γ）：**未来奖励的衰减因子（0 ≤ γ ≤ 1）。

### 2.2 贝尔曼方程

贝尔曼方程是价值迭代算法的核心方程。它定义了状态 s 在给定策略 π 下的价值函数 Vπ(s)：

Vπ(s) = max_a [R(s, a) + γ Σ_{s' ∈ S} P(s' | s, a) Vπ(s')]

其中：

- `max_a` 表示对所有可能的动作 a 求最大值。
- `R(s, a)` 是在状态 s 执行动作 a 后获得的立即奖励。
- `γ` 是折扣因子。
- `P(s' | s, a)` 是从状态 s 执行动作 a 转移到状态 s' 的概率。
- `Vπ(s')` 是状态 s' 在给定策略 π 下的价值。

### 2.3 价值函数的收敛性

价值迭代算法通过迭代更新价值函数 V(s) 来求解贝尔曼方程。在每次迭代中，算法使用以下更新规则：

V^(k+1)(s) = max_a [R(s, a) + γ Σ_{s' ∈ S} P(s' | s, a) V^k(s')]

其中：

- `V^(k+1)(s)` 是第 k+1 次迭代后状态 s 的价值。
- `V^k(s')` 是第 k 次迭代后状态 s' 的价值。

当价值函数满足以下收敛条件时，算法停止迭代：

|V^(k+1)(s) - V^k(s)| < ε

其中：

- `ε` 是一个预定义的容差值。

**代码块：**

def value_iteration(mdp, max_iterations=100, tolerance=1e-6):
    """
    执行价值迭代算法。

    参数：
        mdp: 马尔可夫决策过程对象。
        max_iterations: 最大迭代次数。
        tolerance: 价值函数收敛的容差值。

    返回：
        价值函数 V(s) 的字典。
    """

    V = {s: 0 for s in mdp.states}  # 初始化价值函数

    for _ in range(max_iterations):
        delta = 0  # 记录价值函数的最大变化量

        for s in mdp.states:
            v_old = V[s]
            V[s] = max_a(R(s, a) + γ * Σ_{s' ∈ S} P(s' | s, a) V[s'])

            delta = max(delta, abs(V[s] - v_old))

        if delta