3.1 MDP、回报与 Bellman 方程：状态必须保留预测未来所需的信息

强化学习研究序贯决策：一个动作影响眼前奖励，也改变后续状态和可选动作。只给当前这一步打分，可能把未来的麻烦记到别人的账上。MDP 用状态、转移和回报表示这条因果链，本课用 Bellman 备份检查长期价值如何传播。

本课目标

• 用 MDP 明确状态、动作、转移、奖励、初始分布和终止；
• 判断状态表示是否满足 Markov property；
• 区分 policy value、action value 与 optimal value；
• 用 Bellman expectation/optimality equation 做动态规划。

1. MDP 的完整要素

有限 Markov Decision Process 常写为：

$$(\mathcal{S},\mathcal{A},P,R,\gamma ,{\rho }_0).$$

• $\mathcal{S}$：状态；
• $\mathcal{A}(s)$：状态下合法动作；
• $P(s^{\prime }\mid s,a)$：转移分布；
• $R$：奖励分布或期望，可依赖 $s,a,s^{\prime }$；
• $\gamma$：折扣；
• ${\rho }_0$：初始状态分布。

还要说明 episode 何时终止，以及时间限制属于任务还是采样器。任务本身只有固定步数时，倒计时结束可以是真正 terminal，剩余时间应进入状态以保持 Markov 性；无限期任务被采样上限截断时，仍需估计后续价值。具体区别见 Gymnasium 的时间限制说明。

2. Markov property 是表示假设

状态 $S_t$ 满足 Markov 性，当给定当前状态和动作后，未来与更早历史无关：

$$P(S_{t+1},R_{t+1}\mid S_0,A_0,\dots ,S_t,A_t)=P(S_{t+1},R_{t+1}\mid S_t,A_t).$$

这不表示现实没有记忆，而是状态已包含预测未来需要的信息。

只用机器人坐标可能不够：电量、门状态、过去是否拿到钥匙都会影响后续。若观测不能确定隐藏状态，问题更接近 POMDP；策略可能需要 belief state 或历史/记忆网络。

3. Reward 与 return

即时奖励 $R_{t+1}$ 由环境给出，return 汇总未来：

$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots .$$

有限 episode 可使用 $\gamma =1$，前提是回报有限；continuing task 常用 $\gamma <1$ 或 average-reward formulation。

$\gamma$ 不只是“耐心”：它也影响目标、有效 horizon 和数值稳定性。不能简单说越接近 1 只是“收敛更慢”。

4. Policy、V 与 Q

策略 $\pi (a\mid s)$ 定义动作分布。

$$V^{\pi }(s)=E_{\pi }[G_t\mid S_t=s],$$$$Q^{\pi }(s,a)=E_{\pi }[G_t\mid S_t=s,A_t=a].$$

最优值：

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

值依赖奖励、折扣、终止和环境分布。换一个奖励单位或 horizon，Q 数字不可直接比较。

5. Bellman expectation equation

对固定策略：

$$V^{\pi }(s)=\sum _a\pi (a\mid s)\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma V^{\pi }(s^{\prime })].$$

它把长期回报拆成一步奖励和下一状态价值。若模型 $P,R$ 已知，可迭代更新所有状态直到变化足够小，完成 iterative policy evaluation。

“变化足够小”是数值停止条件，不等于真实策略价值绝对误差必然小；误差界依赖 contraction 条件与阈值。

6. Bellman optimality equation

$$V^{\ast }(s)=\underset{a}{max}\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma V^{\ast }(s^{\prime })].$$

Value iteration 重复应用最优 Bellman backup。下面的 Python 3 片段（partial）用于有限状态、有限奖励和 0≤gamma<1 的折扣模型。outcomes 提供 (概率, 后继, 奖励, 是否终止)，每个状态动作下的概率和须为 1；无合法动作的状态视为终局。未在预算内达到阈值会明确失败，不把中间结果当收敛结果。

def value_iteration(states, actions, outcomes, gamma, tolerance, max_sweeps=10000):
    from math import isfinite

    if not 0 <= gamma < 1:
        raise ValueError("this implementation requires 0 <= gamma < 1")
    if not isfinite(tolerance) or tolerance <= 0:
        raise ValueError("tolerance must be positive and finite")
    states = tuple(states)
    value = {s: 0.0 for s in states}

    for _ in range(max_sweeps):
        updated = {}
        max_change = 0.0
        for state in states:
            candidates = []
            for action in actions(state):
                q = sum(
                    probability * (
                        reward + (0.0 if terminal else gamma * value[next_state])
                    )
                    for probability, next_state, reward, terminal
                    in outcomes(state, action)
                )
                candidates.append(q)
            updated[state] = max(candidates) if candidates else 0.0
            max_change = max(max_change, abs(updated[state] - value[state]))
        value = updated
        if max_change < tolerance:
            return value
    raise RuntimeError("value iteration did not reach tolerance")

例如状态 S 执行动作后确定到 A、奖励 0，A 再确定到终局、奖励 2，取 gamma=0.9。从零开始，第一轮得到 V(A)=2、V(S)=0，第二轮得到 V(S)=1.8。这能检查同步更新是否意外读取本轮新值。提取策略时，选择期望 backup 最大的合法动作，并明确平局策略。

7. Policy iteration

Policy iteration 交替：

1. evaluation：求当前 $V^{\pi }$；
2. improvement：对 $V^{\pi }$ 做 one-step greedy；
3. 策略稳定时停止。

精确 evaluation 可能昂贵；modified policy iteration 只做若干 sweep。Value iteration 可看成把 evaluation 和 improvement 更紧地交错。

8. Model-based 与 model-free

• model-based：拥有或学习 $P,R$，再规划；
• model-free：直接学 value/policy，不显式构造完整转移模型。

“model-free”不表示没有环境假设，也不表示样本更省。已知模型时不利用它可能浪费信息；学到错误模型则会造成规划偏差。Dyna 等方法把真实交互和模型生成更新结合。

9. Reward specification

奖励是优化目标，不是愿望描述。检查：

• 是否遗漏长期副作用；
• proxy 能否被 gaming；
• 多目标权重是否有单位依据；
• 终止奖励和每步奖励是否改变行为；
• 奖励在部署时是否可观测；
• 不同群体/场景是否承受未计入成本。

Reward shaping 能改善探索，但随意添加距离奖励可能改变最优策略。Potential-based shaping 在特定条件下可保持策略不变，仍要验证实现。

常见误区

• 状态就是传感器当前值：部分可观测时历史仍影响未来。
• MDP 一定未知转移：已知模型可直接规划。
• gamma 只是训练技巧：它定义了目标的一部分。
• 奖励越密集越好学且不改目标：塑形可能引入新最优行为。

练习

1. 为带门、钥匙和电量的迷宫定义最小 Markov state。
2. 写出三状态 MDP 的 Bellman equations 并手算一次 backup。
3. 比较 value iteration 与 policy iteration 的 sweep 数。
4. 构造一个 reward hacking 行为并修订目标与约束。

小结

MDP 把连续决策变成可计算对象。Bellman 方程成立的前提是状态足以预测未来，奖励与终止准确表达目标；算法无法补救一个遗漏关键历史或错误激励的环境模型。

下一课在不知道转移概率时从样本学习：Monte Carlo 与 Temporal-Difference 怎样形成 Q-learning，又需要哪些探索和收敛条件。