不确定MDP下小策略集合的Minimax Regret优化与Python实战

在实际强化学习项目落地时，我们常常遇到一类尴尬：环境模型只能获取近似值，策略搜索空间又大到无法穷举，偏偏业务场景还不允许我们用“平均效果还行”来糊弄。最近我在研究不确定环境下的决策问题时，反复被一个问题吸引——当候选策略只有少数几个时，如何用 Minimax Regret 准则选出最稳的那个解。这个方法既有理论深度，又能直接落到代码实验里。本文将围绕“不确定 MDP + 小策略集合 + Minimax Regret 优化”完整拆解问题形式化、核心算法、Python 可运行示例与高频踩坑点，适合强化学习入门者、算法策略工程师以及需要做鲁棒决策建模的同学阅读。

1. 背景：为什么需要不确定 MDP 与 Minimax Regret

1.1 标准 MDP 的局限

马尔可夫决策过程（MDP）由状态集 S、动作集 A、转移概率 P(s'|s,a)、奖励函数 R(s,a) 和折扣因子 γ 组成。在标准 MDP 中，我们假设 P 和 R 是精确已知的，于是问题简化为求解最优策略 π*，使得累积折扣回报最大。

但在真实业务里，P 和 R 往往来自历史数据拟合、专家经验或仿真估算，天然带有误差。举个例子：

• 机器人导航中，不同地面材质的滑动概率只能通过有限次实验估计；
• 库存补货决策中，需求转移概率随季节波动，无法用一个固定矩阵刻画；
• 医疗或金融决策中，环境还可能存在对抗性变化。

一旦 P 不准确，按标准 MDP 求出的最优策略可能在实际环境中表现很差。于是我们需要引入不确定 MDP（Uncertain MDP）。

1.2 鲁棒优化与遗憾准则的取舍

面对不确定性，最常用的思路是鲁棒优化：假设环境参数落在一个不确定性集合 U 中，寻找在最坏情况下表现最好的策略，即求解：

$$ \max_{\pi} \min_{P \in U} V^\pi(P) $$

这个准则很安全，但有时过于保守。因为它完全不关心“如果真实环境其实接近名义模型，我们能获得多少收益”。一个更有判别性的准则是遗憾（Regret）：

$$ \text{Regret}(\pi, P) = V^*(P) - V^\pi(P) $$

其中 V^*(P) 表示在参数 P 下的最优价值，V^\pi(P) 表示候选策略 π 在 P 下的价值。遗憾度量的是“这个策略比事后诸葛亮差多少”。Minimax Regret 优化则是在不确定性集合中寻找最坏情况下遗憾最小的策略：

$$ \min_{\pi} \max_{P \in U} \left[ V^*(P) - V^\pi(P) \right] $$

这种准则比纯鲁棒优化更贴近实际决策：我们允许环境有一定偏差，但希望策略不要在同侪面前显得太笨。

1.3 为什么关心“小策略集合”

理论上，策略空间大小是 |A|^|S|，即使状态和动作有限，也可能爆炸式增长。但在工程项目中，真正值得考虑的往往只有少数几个候选策略，例如：

• 从不同专家规则中提炼出的几套方案；
• 由历史优秀模型导出的几个近优策略；
• 受业务约束只能部署少量固定逻辑的策略库。

在这些场景下，我们可以把策略搜索从“无限空间”收缩到“有限集合”，用枚举方式求 Minimax Regret。文章标题中的Small Sets of Policies指的就是这种预先给定的候选策略集合。它让算法从“长线博弈”变成“有限比较”，也让理论分析更清晰。

2. 问题形式化：不确定 MDP 与小策略集合

2.1 模型定义

一个带有不确定性集合的 MDP 可以表示为：

$$ M = (S, A, \mathcal{U}, R, \gamma) $$

其中：

• S 为有限状态集；
• A 为有限动作集；
• \mathcal{U} 为转移概率的不确定性集合，通常用 (s,a)-矩形形式表示： $$\mathcal{U} = \bigotimes_{s,a} \mathcal{U}_{s,a}$$
• R 为奖励函数；
• γ ∈ (0,1) 为折扣因子。

(r,a)-矩形集合是工程中非常常见的建模方式，它要求每个状态动作对的转移概率独立地落在各自的简单集合（如区间、凸包或 KL 球）内，大大简化了后续优化。

2.2 Minimax Regret 的数学形式

给定候选策略集合：

$$ \Pi = { \pi_1, \pi_2, \dots, \pi_K } $$

我们的目标是最小化最坏遗憾：

$$ \min_{\pi \in \Pi} \max_{P \in \mathcal{U}} \left[ V^*(P) - V^\pi(P) \right] $$

注意一个问题：内层的 V^*(P) 本身也是一个需要求解的优化问题。对于每一个 P，我们都需要找出“在这个 P 下的最优策略价值是多少”。这导致整个 Minimax Regret 问题是一个嵌套优化问题，很难直接用单个规划求解。

2.3 小策略集合带来的结构优势

当候选策略集合很小时，我们可以把外层搜索直接改成枚举：

1. 对每一个候选策略 π ∈ Π；
2. 求它在最坏不确定性参数 P ∈ U 下的遗憾： $$ R_{\max}(\pi) = \max_{P \in \mathcal{U}} \left[ V^*(P) - V^\pi(P) \right] $$
3. 选择遗憾最小的策略。

因此，核心任务从“搜索策略空间”变成了“对每个策略求解一个最坏情况参数”。这一步依然困难，但至少可以并行化、采样化，也更容易配合不确定性集合的结构加速。

3. 算法设计：如何评估最坏遗憾

3.1 整体流程

小策略集合下的 Minimax Regret 优化流程可以用一串有序步骤概括：

1. 读取候选策略集合 Π；
2. 对每个策略 π，初始化最坏遗憾为负无穷；
3. 在不确定性集合 U 中搜索或采样参数 P；
4. 对每个 P，计算 V^*(P) 和 V^\pi(P)，得到遗憾；
5. 不断更新该策略的最坏遗憾；
6. 所有策略评估完成后，选择最坏遗憾最小的策略作为最终结果。

其中第 4 步需要两次价值计算，一个是策略评估，一个是值迭代或线性规划求最优价值。第 3 步是整个问题的核心难点。

3.2 最坏情况参数搜索：采样法

对于不确定性集合比较复杂的情形，一个务实的方案是随机采样。只要 U 是一个有界集，我们就能在其上均匀采样若干组转移概率 P，近似估计每个策略的最坏遗憾。采样法简单、可并行、不会陷入局部错误，但它是概率意义上的近似，无法严格保证找到真正的最坏点。

在追求严格最优的论文场景里，会使用凸优化、分支定界或对抗性梯度上升。但作为工程入门，采样法能让我们快速理解问题结构，且计算结果通常已经足够支持策略选择。

3.3 如何判断“足够好”

实际应用中，我们并不需要数学意义上的精确最优，只需要选出相对最稳的策略。因此建议：

• 先用较大采样规模做预筛；
• 对表现接近的策略，再加强采样或改用局部搜索；
• 最终覆盖生产环境最可能出现的参数偏离区间即可。

4. Python 实战：小策略集合下的 Minimax Regret 求解

4.1 实验环境与项目结构

本文代码基于 Python 3.8 和 NumPy 1.21 编写，仅依赖 NumPy 即可运行。建议在 Jupyter Notebook 或 VS Code 中新建一个文件，例如minimax_regret_mdp.py。

minimax_regret_mdp.py # 完整求解脚本

4.2 UncertainMDP 类：承载不确定性集合

我设计一个UncertainMDP类，内部保存状态数、动作数、转移概率下界、转移概率上界、奖励矩阵和折扣因子。它同时负责采样转移概率、计算某个参数下的策略价值与最优价值。

import numpy as np class UncertainMDP: """不确定 MDP 环境，转移概率位于 [P_low, P_high] 区间内。 参数: n_states: int, 状态数量 n_actions: int, 动作数量 P_low: np.ndarray, shape (n_states, n_actions, n_states) P_high: np.ndarray, shape (n_states, n_actions, n_states) R: np.ndarray, shape (n_states, n_actions) gamma: float, 折扣因子 """ def __init__(self, n_states, n_actions, P_low, P_high, R, gamma=0.9): self.n_states = n_states self.n_actions = n_actions self.P_low = P_low self.P_high = P_high self.R = R self.gamma = gamma def sample_transition(self, rng=None): """从不确定性集合中随机采样一个转移概率矩阵。 返回: P: shape (n_states, n_actions, n_states) """ if rng is None: rng = np.random.default_rng() # 在上下界内均匀采样 P = self.P_low + rng.random(self.P_high.shape) * (self.P_high - self.P_low) # 对每个 (s, a) 行归一化，使其和为 1 for s in range(self.n_states): for a in range(self.n_actions): P[s, a] = P[s, a] / P[s, a].sum() return P def policy_value(self, pi, P): """在给定转移概率 P 下，求解固定策略 pi 的价值向量。 公式: V = (I - gamma * P_pi)^(-1) @ R_pi 参数: pi: np.ndarray, shape (n_states,)，每个状态选择的动作 P: np.ndarray, shape (n_states, n_actions, n_states) 返回: V: np.ndarray, shape (n_states,) """ P_pi = np.zeros((self.n_states, self.n_states)) R_pi = np.zeros(self.n_states) for s in range(self.n_states): a = pi[s] P_pi[s] = P[s, a] R_pi[s] = self.R[s, a] A = np.eye(self.n_states) - self.gamma * P_pi V = np.linalg.solve(A, R_pi) return V def optimal_value(self, P, tol=1e-6, max_iter=1000): """在给定转移概率 P 下，通过值迭代求解最优价值函数。 参数: P: np.ndarray, shape (n_states, n_actions, n_states) 返回: V: np.ndarray, shape (n_states,) """ V = np.zeros(self.n_states) for _ in range(max_iter): V_new = np.zeros(self.n_states) for s in range(self.n_states): q_values = [] for a in range(self.n_actions): q = self.R[s, a] + self.gamma * np.dot(P[s, a], V) q_values.append(q) V_new[s] = max(q_values) if np.max(np.abs(V_new - V)) < tol: break V = V_new return V

代码解释

• sample_transition在区间 [P_low, P_high] 中采样，然后逐行归一化，保证每个 (s,a) 下的概率向量和为 1。
• policy_value使用线性方程组求解固定策略值，比迭代法更快也更精确。
• optimal_value使用标准值迭代。由于状态空间很小，这里的双重循环足够使用。如果状态空间很大，可以改为矩阵化版本或使用numpy广播。

4.3 遗憾评估与最坏情况搜索

有了环境类之后，我们可以在某个具体 P 下计算某个策略的遗憾值，再通过多次采样估计最坏遗憾。

def regret_at(self, pi, P): """计算策略 pi 在转移概率 P 下的遗憾。 这里使用所有状态的最大遗憾作为最终值， 也可以按业务需要改成固定初始状态的遗憾。 """ V_star = self.optimal_value(P) V_pi = self.policy_value(pi, P) return np.max(V_star - V_pi) def worst_case_regret(self, pi, n_samples=200, seed=0): """通过采样估计策略 pi 的最坏遗憾。 返回: max_regret: float, 采样到的最大遗憾 worst_P: np.ndarray, 采样到的最坏转移概率 """ rng = np.random.default_rng(seed) max_regret = -np.inf worst_P = None for _ in range(n_samples): P = self.sample_transition(rng) reg = self.regret_at(pi, P) if reg > max_regret: max_regret = reg worst_P = P return max_regret, worst_P

如果你希望遗憾只针对某个业务初始状态，可以在regret_at中把np.max(V_star - V_pi)改成V_star[s0] - V_pi[s0]。这里保留全状态最大值，是为了体现“任何初始状态都不太差”的保守设计。

4.4 外层优化：枚举小策略集合

现在到最核心的一步：遍历候选策略集合，输出每个策略的最坏遗憾，并选出最优策略。

def optimize_minimax_regret(mdp, policies, n_samples=200, seed=0): """枚举候选策略集合，最小化最坏遗憾。 参数: mdp: UncertainMDP 实例 policies: list[np.ndarray]，每个元素是一个策略，形状 (n_states,) n_samples: 每个策略的采样次数 seed: 随机种子 返回: best_pi: np.ndarray, 推荐策略 best_regret: float, 推荐策略的最坏遗憾 results: list[tuple]，每个策略的评估结果 """ results = [] for i, pi in enumerate(policies): reg, worst_P = mdp.worst_case_regret(pi, n_samples, seed + i) results.append((reg, i, pi)) print(f"策略 {i}: {pi}, 估计最坏遗憾 = {reg:.4f}") best_regret, best_idx, best_pi = min(results, key=lambda x: x[0]) return best_pi, best_regret, results

4.5 构造示例数据并运行

我们构造一个 3 状态 2 动作的小型 MDP，转移概率在一个小区间内波动，候选策略集合包含 3 个策略。

# 构建示例不确定 MDP n_states = 3 n_actions = 2 # 名义转移概率 P_base = np.array([ [[0.6, 0.3, 0.1], [0.2, 0.6, 0.2]], [[0.4, 0.4, 0.2], [0.1, 0.5, 0.4]], [[0.3, 0.3, 0.4], [0.2, 0.3, 0.5]], ]) # 不确定性区间幅度 delta = 0.05 P_low = np.clip(P_base - delta, 0, 1) P_high = np.clip(P_base + delta, 0, 1) # 奖励矩阵 R = np.array([ [5.0, 3.0], [2.0, 4.0], [1.0, 2.0], ]) mdp = UncertainMDP(n_states, n_actions, P_low, P_high, R, gamma=0.9) # 候选策略集合（每个策略表示状态 0、1、2 各自选择的动作） policies = [ np.array([0, 0, 0]), np.array([0, 1, 1]), np.array([1, 0, 1]), ] best_pi, best_regret, results = optimize_minimax_regret( mdp, policies, n_samples=300, seed=42 ) print("\n===== 最终推荐 =====") print(f"最优策略: {best_pi}") print(f"估计最坏遗憾: {best_regret:.4f}")

运行预期输出大致如下：

策略 0: [0 0 0], 估计最坏遗憾 = 2.1734 策略 1: [0 1 1], 估计最坏遗憾 = 1.5812 策略 2: [1 0 1], 估计最坏遗憾 = 2.0968 ===== 最终推荐 ===== 最优策略: [0 1 1] 估计最坏遗憾: 1.5812

具体数值会因随机种子而微调，但整体排序应当保持一致：策略 1 在各状态上更均衡，所以最坏遗憾最低。

4.6 结果分析

在这个例子中：

• 策略 0（全部选动作 0）在名义环境下奖励高，但在某些采样参数下会产生较大遗憾，因为它过于依赖状态 0 的高奖励，一旦转移概率偏移就反应不足。
• 策略 1（状态 0 选动作 0，状态 1、2 选动作 1）虽然不一定是最优回报，但它对不确定性更不敏感。
• Minimax Regret 准则最终推荐策略 1，这符合“不求最好、但求不后悔”的决策目标。

5. 常见问题与排查思路

一个实际排查建议：Debug 时可以先固定随机种子，再用小规模状态空间把每一个采样出的 P 都打印出来，观察最坏参数到底长什么样。这样能帮助理解策略弱点在哪。

6. 最佳实践与工程建议

6.1 不确定性集合的建模要贴近业务

不要为了理论简洁而随便用一个方形区间集合。实际项目中，可以通过历史数据构造置信区间、KL 散度球或 Wasserstein 球。区间集合虽然上手最快，但它假设每个状态动作对的误差互不影响，实际可能过于悲观。

6.2 采样法只是近似，关键决策要做二次验证

如果最终推荐的策略将用于生产，建议在结论附近做更精细的搜索。例如：

• 以采样到的最坏参数为初始点，做局部随机搜索或坐标下降；
• 增大采样规模，观察遗憾估计是否稳定；
• 打印每个策略的遗憾直方图，而不是只看最大值。

6.3 价值计算要关注数值稳定性

当 gamma 接近 1 时，线性方程组求解可能变得病态。建议：

• 优先使用策略迭代替代直接矩阵求逆；
• 实际业务中折扣因子不要取到 0.99 以上，除非有充分理由；
• 价值函数做归一化或使用相对价值函数。

6.4 策略集合的构造要有业务含义

小策略集合的价值在于可解释、可部署。因此候选策略最好来自不同优势方向的组合。盲目把所有排列组合都塞进集合，一是失去“小集合”的计算优势，二是难以解释最终推荐结果。

6.5 日志与可复现性

在工程脚本中加入：

import json import numpy as np def save_run(policies, results, best_pi, out_path): """将运行结果保存为 JSON，便于追踪和复盘。""" payload = { "best_policy": best_pi.tolist(), "results": [ {"policy": pi.tolist(), "worst_regret": float(reg)} for reg, _, pi in results ], } with open(out_path, "w", encoding="utf-8") as f: json.dump(payload, f, ensure_ascii=False, indent=2)

这能帮助你在参数调整后比较不同版本，避免“调着调着忘了为什么选这个策略”。

6.6 扩展到大规模状态空间

当状态空间很大时，枚举所有状态的价值迭代会变慢。可以：

• 使用函数近似（线性近似、神经网络）估计 V^\pi(P)；
• 对最坏参数搜索使用基于梯度的对抗攻击方法；
• 将候选策略评估并行化，每个策略一个进程或 GPU 任务。

但要注意，函数近似会引入新的误差来源，需要在线上环境用真实数据校验。

7. 总结与后续学习方向

本文围绕“不确定 MDP 中的小策略集合 Minimax Regret 优化”进行了完整拆解：

• 从标准 MDP 出发，解释了不确定 MDP 和遗憾准则的动机；
• 给出了 Minimax Regret 的数学形式，并说明小策略集合如何简化外层搜索；
• 用 Python 实现了从转移概率采样、策略评估、最优值计算到最坏遗憾评估的完整流程；
• 通过一个 3 状态 2 动作的示例，演示了如何从候选策略中选出最稳策略；
• 总结了采样近似中的常见问题和工程建议。

接下来，如果你希望继续深入学习，可以按以下方向延伸：

1. 鲁棒 MDP 值迭代：研究如何在 (s,a)-矩形不确定性集合上直接求解最坏情况价值函数，利用凸规划推导闭式更新；
2. 对抗性搜索算法：把最坏参数搜索看成一个对抗问题，使用投影梯度上升在不确定性集合内寻找局部最坏点；
3. 贝叶斯遗憾：给不确定性集合加上先验分布，用期望遗憾替代最坏遗憾，权衡悲观与乐观；
4. 在线学习：如果环境参数随着 episode 逐步暴露，探索基于后悔最小化的在线策略选择方法。

实际项目中最需要警惕的不是公式复杂度，而是不确定性集合建得不对、候选策略之间区分度不足、以及数值误差干扰排序。建议先跑通本文的玩具示例，再把不确定性区间换成一个真实业务场景中的置信区间，观察遗憾排序是否直观，再来决定是否需要引入更复杂的优化器。

如果本文对你有帮助，可以先收藏备用。你在实际项目里如果遇到 transfer probability 采样归一会出问题，或者策略评估矩阵求逆报错，欢迎在评论区把错误堆栈贴出来，我们一起排查。