第二部分 · 马尔可夫决策过程 (MDP)

目标：学会用马尔可夫决策过程把一个“做决策”的问题写成数学模型， 理解回报、折扣、价值函数、贝尔曼方程。

强化学习研究的是序贯决策 (sequential decision making)：智能体不断做动作、 看结果、再做下一步。描述这类问题的标准数学框架，就是马尔可夫决策过程 (MDP)。

2.1 马尔可夫性 (Markov Property)

未来只取决于现在，而与过去无关。

用式子表达：

P(s_{t+1} | s_t, s_{t-1}, ..., s_0) = P(s_{t+1} | s_t)

也就是说，只要知道当前状态 s_t，就足以预测下一步——历史信息都已“浓缩”在当前状态里。 「鲁班瞄准」就是个好例子：只要知道目标此刻的位置和速度，就能决定朝哪打， 根本不用回看目标前几秒怎么走过来的。

🎮 王者荣耀里的马尔可夫性：只要当前这一帧的战场快照够完整（双方血量、蓝量、坐标、 技能CD、兵线、塔血……），AI 就能决定下一步该怎么打——它不需要回看前 10 分钟怎么打到这里。 这也解释了为什么开悟的 observation 要设计得那么全：状态必须“自包含”，否则就破坏了马尔可夫性。

2.2 MDP 的五要素

一个 MDP 由五元组 (S, A, P, R, γ) 定义：

交互过程：

在状态 s_t  ──选择动作 a_t──►  环境返回 奖励 r_{t+1} 和 新状态 s_{t+1}  ──►  循环

2.3 回报 (Return) 与折扣

智能体的目标不是最大化“单步奖励”，而是最大化长期累积奖励，称为回报 G_t：

G_t = r_{t+1} + γ·r_{t+2} + γ²·r_{t+3} + ...
    = Σ_{k=0}^{∞} γ^k · r_{t+k+1}

折扣因子 γ 的直觉：

• γ → 0：只看眼前（目光短浅）——只想立刻拿人头，不管会不会被抓；
• γ → 1：非常重视长远（有远见）——愿意猥琐发育、慢慢推塔，为最后赢下这局；
• 折扣还保证了在无限步问题中回报收敛（不会变成无穷大）。

🎮 王者里 γ 就是“贪不贪”的旋钮：调小 → AI 变成只会抢人头的莽夫； 调大 → AI 懂得放弃眼前小利去拿更大的团队目标（塔/主宰/水晶）。

rewards = [1, 1, 1, 1, 1]   # 连续5步各得1
gamma = 0.9
G = sum((gamma**k) * r for k, r in enumerate(rewards))
print(G)   # 4.0951  （越往后的奖励，权重越小）

2.4 策略 (Policy)

策略 π 是智能体的“行为准则”：给定状态，输出动作（或动作的概率分布）。

确定性策略:  a = π(s)
随机性策略:  π(a | s) = 在状态 s 下选择动作 a 的概率

强化学习的终极目标：找到最优策略 π*，使回报的期望最大。

2.5 价值函数 (Value Function)

“价值”衡量从某状态/状态-动作出发，未来能拿到多少回报的期望。

状态价值函数 V

V^π(s) = E_π[ G_t | s_t = s ]

在状态 s、遵循策略 π 时，期望能获得的回报。

动作价值函数 Q

Q^π(s, a) = E_π[ G_t | s_t = s, a_t = a ]

在状态 s 先做动作 a、之后遵循 π 时，期望能获得的回报。Q 函数是很多算法的核心。

2.6 贝尔曼方程 (Bellman Equation)

价值函数满足一个漂亮的递归关系——当前价值 = 即时奖励 + 折扣后的未来价值。

贝尔曼期望方程

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

贝尔曼最优方程

最优价值函数 V* 与 Q* 满足：

V*(s)   = max_a  Σ_{s'} P(s'|s,a) [ R(s,a,s') + γ V*(s') ]
Q*(s,a) = Σ_{s'} P(s'|s,a) [ R(s,a,s') + γ max_{a'} Q*(s',a') ]

一旦有了 Q*，最优策略就是在每个状态选 Q 值最大的动作：π*(s) = argmax_a Q*(s,a)。

2.7 用矩阵求解价值（呼应第一部分）

给定固定策略，把贝尔曼期望方程写成向量形式：

v = r + γ P v      =>      (I - γP) v = r      =>      v = (I - γP)⁻¹ r

import numpy as np

# 一个 2 状态的马尔可夫奖励过程
P = np.array([[0.7, 0.3],
              [0.4, 0.6]])   # 转移矩阵
r = np.array([5.0, -1.0])    # 每个状态的即时奖励
gamma = 0.9

v = np.linalg.solve(np.eye(2) - gamma * P, r)
print("各状态价值:", v)

这正是第一部分那段代码的含义：一次性精确解出所有状态的价值。

2.8 一个直观例子：王者「补刀 vs 撤退」小 MDP

想象一个极简的对线场景。状态：安全、危险、阵亡(终止)。动作：上前补刀 / 后撤。

• 上前补刀：能拿经济，即时奖励 +1，但有较高概率进入 危险（被敌方英雄盯上）；
• 在 危险 里继续 补刀：小概率直接 阵亡（即时奖励 -10）；
• 后撤：没有经济收益，即时奖励 0，但能回到 安全。

这个小例子说明了 RL 的精髓：即时奖励高的动作（贪刀 +1），长期回报未必高（可能送人头 -10）。 价值函数就是用来看穿这一点的工具——它会告诉你"在 危险 状态里，后撤 的长期价值更高"。

2.9 把王者荣耀 1v1 写成一个 MDP（本部分主例）

现在把整套五元组落到真实场景。这就是第一课那张词典表的“数学版”：

• 状态 S：s = [我方血量, 蓝量, x, y, 敌方血量, 敌我距离, 1技能CD, 大招CD, 兵线位置, ...] （开悟真实环境是几百维的 observation 向量）。
• 动作 A：复合动作 a = (移动方向, 是否平A, 用哪个技能, 目标是谁)， 且受 legal_action 掩码约束（回城途中不能放技能等）。
• 转移 P：我方走位+放技能后，下一帧战场是什么样——带随机性（暴击、对手可能闪现躲技能）。
• 奖励 R：一步步的加减分，例如：

# 一个简化的王者 1v1 奖励函数（奖励塑形的雏形，第三部分细讲）
def reward(prev, cur):
    r  = 3.0  * (cur.enemy_killed - prev.enemy_killed)     # 击杀敌方英雄
    r -= 3.0  * (cur.self_killed  - prev.self_killed)      # 自己被击杀
    r += 0.5  * (cur.towers_down  - prev.towers_down)      # 推掉塔
    r += 0.1  * (cur.last_hits    - prev.last_hits)        # 补刀（经济）
    r += 0.01 * (cur.self_hp      - prev.self_hp)          # 血量变化（掉血=负）
    return r

• 折扣 γ：设 0.99，让 AI 为“10 秒后一波推掉塔”而愿意现在忍住不贪刀。

一个决策瞬间：处在状态 s（我残血、敌满血、大招CD 还有 2 秒）→ 策略 π 倾向选“后撤”→ 环境按 P 转移到我方安全撤退的新状态 s'，并给一个略带掉血的奖励 r。这就是 2.2 那张交互图在王者里的一次循环。

而 Q(s, 大招) 这个数，就精确回答了：“此刻这个局势下放大招，长期看值不值？” 整门课的算法（第五部分）都是在想办法把这个 Q 学准。

✅ 小结

• MDP = (S, A, P, R, γ)，建立在马尔可夫性之上；
• 目标是最大化折扣回报 G_t 的期望；
• 价值函数 V/Q 衡量长期回报，满足贝尔曼方程；
• 固定策略下，价值可用线性代数一步解出；最优策略 = 对 Q* 取 argmax。

📝 练习

1. 设 γ=0.8，某段对局奖励序列 [2, 0, 0, 10]（末尾 +10 是推塔），手算并用代码验证回报 G_0。
2. 写出上面「补刀 vs 撤退」小 MDP 的一个具体转移矩阵与奖励向量，并用 np.linalg.solve 求各状态价值。
3. 用一句话解释：为什么 γ 太大或太小都可能让智能体学不好？
4. 证明（思路即可）：V^π(s) = Σ_a π(a|s) Q^π(s,a)。
5. 王者场景：仿照 2.9 的 reward()，加一项“待在敌方防御塔攻击范围内就扣分”，说说这会如何改变 AI 的越塔行为。

📗 延伸参考：ZhiqingXiao/rl-book（贝尔曼方程与动态规划的代码实现，可延伸阅读）

⬅️ 上一部分：第一部分 · 线性代数基础 ➡️ 下一部分：第三部分 · 强化学习基础概念