在实际强化学习项目落地时我们常常遇到一类尴尬环境模型只能获取近似值策略搜索空间又大到无法穷举偏偏业务场景还不允许我们用“平均效果还行”来糊弄。最近我在研究不确定环境下的决策问题时反复被一个问题吸引——当候选策略只有少数几个时如何用 Minimax Regret 准则选出最稳的那个解。这个方法既有理论深度又能直接落到代码实验里。本文将围绕“不确定 MDP 小策略集合 Minimax Regret 优化”完整拆解问题形式化、核心算法、Python 可运行示例与高频踩坑点适合强化学习入门者、算法策略工程师以及需要做鲁棒决策建模的同学阅读。1. 背景为什么需要不确定 MDP 与 Minimax Regret1.1 标准 MDP 的局限马尔可夫决策过程MDP由状态集 S、动作集 A、转移概率 P(s|s,a)、奖励函数 R(s,a) 和折扣因子 γ 组成。在标准 MDP 中我们假设 P 和 R 是精确已知的于是问题简化为求解最优策略 π*使得累积折扣回报最大。但在真实业务里P 和 R 往往来自历史数据拟合、专家经验或仿真估算天然带有误差。举个例子机器人导航中不同地面材质的滑动概率只能通过有限次实验估计库存补货决策中需求转移概率随季节波动无法用一个固定矩阵刻画医疗或金融决策中环境还可能存在对抗性变化。一旦 P 不准确按标准 MDP 求出的最优策略可能在实际环境中表现很差。于是我们需要引入不确定 MDPUncertain 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 小策略集合带来的结构优势当候选策略集合很小时我们可以把外层搜索直接改成枚举对每一个候选策略 π ∈ Π求它在最坏不确定性参数 P ∈ U 下的遗憾 $$ R_{\max}(\pi) \max_{P \in \mathcal{U}} \left[ V^*(P) - V^\pi(P) \right] $$选择遗憾最小的策略。因此核心任务从“搜索策略空间”变成了“对每个策略求解一个最坏情况参数”。这一步依然困难但至少可以并行化、采样化也更容易配合不确定性集合的结构加速。3. 算法设计如何评估最坏遗憾3.1 整体流程小策略集合下的 Minimax Regret 优化流程可以用一串有序步骤概括读取候选策略集合 Π对每个策略 π初始化最坏遗憾为负无穷在不确定性集合 U 中搜索或采样参数 P对每个 P计算 V^*(P) 和 V^\pi(P)得到遗憾不断更新该策略的最坏遗憾所有策略评估完成后选择最坏遗憾最小的策略作为最终结果。其中第 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, gamma0.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, rngNone): 从不确定性集合中随机采样一个转移概率矩阵。 返回: 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, tol1e-6, max_iter1000): 在给定转移概率 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_samples200, seed0): 通过采样估计策略 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_samples200, seed0): 枚举候选策略集合最小化最坏遗憾。 参数: 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, keylambda x: x[0]) return best_pi, best_regret, results4.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, gamma0.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_samples300, seed42 ) 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. 常见问题与排查思路问题现象常见原因解决思路采样到的转移概率矩阵行之和不为 1忘记归一化或上下界采样后直接使用完成均匀采样后按 (s,a) 行归一化遗憾值出现负值值迭代未收敛到最优值 V*导致 V* 偏小增加最大迭代次数或调小 tolnp.linalg.solve报奇异矩阵gamma 过于接近 1或策略导致可约 Markov 链改用策略迭代或适当降低 gamma不同采样规模得到不同推荐策略采样规模不足或最坏点附近误差大增大 n_samples并在候选策略间使用同一随机种子对比候选策略太相似遗憾差异很小策略集合本身区分度不高检查策略是否在关键状态上有实质差异或加入随机化策略全状态遗憾与业务指标不一致使用了所有状态最大值而业务只关心单一初始状态在regret_at中改为初始状态 s0 的差值一个实际排查建议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, encodingutf-8) as f: json.dump(payload, f, ensure_asciiFalse, indent2)这能帮助你在参数调整后比较不同版本避免“调着调着忘了为什么选这个策略”。6.6 扩展到大规模状态空间当状态空间很大时枚举所有状态的价值迭代会变慢。可以使用函数近似线性近似、神经网络估计 V^\pi(P)对最坏参数搜索使用基于梯度的对抗攻击方法将候选策略评估并行化每个策略一个进程或 GPU 任务。但要注意函数近似会引入新的误差来源需要在线上环境用真实数据校验。7. 总结与后续学习方向本文围绕“不确定 MDP 中的小策略集合 Minimax Regret 优化”进行了完整拆解从标准 MDP 出发解释了不确定 MDP 和遗憾准则的动机给出了 Minimax Regret 的数学形式并说明小策略集合如何简化外层搜索用 Python 实现了从转移概率采样、策略评估、最优值计算到最坏遗憾评估的完整流程通过一个 3 状态 2 动作的示例演示了如何从候选策略中选出最稳策略总结了采样近似中的常见问题和工程建议。接下来如果你希望继续深入学习可以按以下方向延伸鲁棒 MDP 值迭代研究如何在 (s,a)-矩形不确定性集合上直接求解最坏情况价值函数利用凸规划推导闭式更新对抗性搜索算法把最坏参数搜索看成一个对抗问题使用投影梯度上升在不确定性集合内寻找局部最坏点贝叶斯遗憾给不确定性集合加上先验分布用期望遗憾替代最坏遗憾权衡悲观与乐观在线学习如果环境参数随着 episode 逐步暴露探索基于后悔最小化的在线策略选择方法。实际项目中最需要警惕的不是公式复杂度而是不确定性集合建得不对、候选策略之间区分度不足、以及数值误差干扰排序。建议先跑通本文的玩具示例再把不确定性区间换成一个真实业务场景中的置信区间观察遗憾排序是否直观再来决定是否需要引入更复杂的优化器。如果本文对你有帮助可以先收藏备用。你在实际项目里如果遇到 transfer probability 采样归一会出问题或者策略评估矩阵求逆报错欢迎在评论区把错误堆栈贴出来我们一起排查。 不确定MDP下小策略集合的Minimax Regret优化与Python实战
在实际强化学习项目落地时我们常常遇到一类尴尬环境模型只能获取近似值策略搜索空间又大到无法穷举偏偏业务场景还不允许我们用“平均效果还行”来糊弄。最近我在研究不确定环境下的决策问题时反复被一个问题吸引——当候选策略只有少数几个时如何用 Minimax Regret 准则选出最稳的那个解。这个方法既有理论深度又能直接落到代码实验里。本文将围绕“不确定 MDP 小策略集合 Minimax Regret 优化”完整拆解问题形式化、核心算法、Python 可运行示例与高频踩坑点适合强化学习入门者、算法策略工程师以及需要做鲁棒决策建模的同学阅读。1. 背景为什么需要不确定 MDP 与 Minimax Regret1.1 标准 MDP 的局限马尔可夫决策过程MDP由状态集 S、动作集 A、转移概率 P(s|s,a)、奖励函数 R(s,a) 和折扣因子 γ 组成。在标准 MDP 中我们假设 P 和 R 是精确已知的于是问题简化为求解最优策略 π*使得累积折扣回报最大。但在真实业务里P 和 R 往往来自历史数据拟合、专家经验或仿真估算天然带有误差。举个例子机器人导航中不同地面材质的滑动概率只能通过有限次实验估计库存补货决策中需求转移概率随季节波动无法用一个固定矩阵刻画医疗或金融决策中环境还可能存在对抗性变化。一旦 P 不准确按标准 MDP 求出的最优策略可能在实际环境中表现很差。于是我们需要引入不确定 MDPUncertain 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 小策略集合带来的结构优势当候选策略集合很小时我们可以把外层搜索直接改成枚举对每一个候选策略 π ∈ Π求它在最坏不确定性参数 P ∈ U 下的遗憾 $$ R_{\max}(\pi) \max_{P \in \mathcal{U}} \left[ V^*(P) - V^\pi(P) \right] $$选择遗憾最小的策略。因此核心任务从“搜索策略空间”变成了“对每个策略求解一个最坏情况参数”。这一步依然困难但至少可以并行化、采样化也更容易配合不确定性集合的结构加速。3. 算法设计如何评估最坏遗憾3.1 整体流程小策略集合下的 Minimax Regret 优化流程可以用一串有序步骤概括读取候选策略集合 Π对每个策略 π初始化最坏遗憾为负无穷在不确定性集合 U 中搜索或采样参数 P对每个 P计算 V^*(P) 和 V^\pi(P)得到遗憾不断更新该策略的最坏遗憾所有策略评估完成后选择最坏遗憾最小的策略作为最终结果。其中第 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, gamma0.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, rngNone): 从不确定性集合中随机采样一个转移概率矩阵。 返回: 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, tol1e-6, max_iter1000): 在给定转移概率 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_samples200, seed0): 通过采样估计策略 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_samples200, seed0): 枚举候选策略集合最小化最坏遗憾。 参数: 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, keylambda x: x[0]) return best_pi, best_regret, results4.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, gamma0.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_samples300, seed42 ) 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. 常见问题与排查思路问题现象常见原因解决思路采样到的转移概率矩阵行之和不为 1忘记归一化或上下界采样后直接使用完成均匀采样后按 (s,a) 行归一化遗憾值出现负值值迭代未收敛到最优值 V*导致 V* 偏小增加最大迭代次数或调小 tolnp.linalg.solve报奇异矩阵gamma 过于接近 1或策略导致可约 Markov 链改用策略迭代或适当降低 gamma不同采样规模得到不同推荐策略采样规模不足或最坏点附近误差大增大 n_samples并在候选策略间使用同一随机种子对比候选策略太相似遗憾差异很小策略集合本身区分度不高检查策略是否在关键状态上有实质差异或加入随机化策略全状态遗憾与业务指标不一致使用了所有状态最大值而业务只关心单一初始状态在regret_at中改为初始状态 s0 的差值一个实际排查建议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, encodingutf-8) as f: json.dump(payload, f, ensure_asciiFalse, indent2)这能帮助你在参数调整后比较不同版本避免“调着调着忘了为什么选这个策略”。6.6 扩展到大规模状态空间当状态空间很大时枚举所有状态的价值迭代会变慢。可以使用函数近似线性近似、神经网络估计 V^\pi(P)对最坏参数搜索使用基于梯度的对抗攻击方法将候选策略评估并行化每个策略一个进程或 GPU 任务。但要注意函数近似会引入新的误差来源需要在线上环境用真实数据校验。7. 总结与后续学习方向本文围绕“不确定 MDP 中的小策略集合 Minimax Regret 优化”进行了完整拆解从标准 MDP 出发解释了不确定 MDP 和遗憾准则的动机给出了 Minimax Regret 的数学形式并说明小策略集合如何简化外层搜索用 Python 实现了从转移概率采样、策略评估、最优值计算到最坏遗憾评估的完整流程通过一个 3 状态 2 动作的示例演示了如何从候选策略中选出最稳策略总结了采样近似中的常见问题和工程建议。接下来如果你希望继续深入学习可以按以下方向延伸鲁棒 MDP 值迭代研究如何在 (s,a)-矩形不确定性集合上直接求解最坏情况价值函数利用凸规划推导闭式更新对抗性搜索算法把最坏参数搜索看成一个对抗问题使用投影梯度上升在不确定性集合内寻找局部最坏点贝叶斯遗憾给不确定性集合加上先验分布用期望遗憾替代最坏遗憾权衡悲观与乐观在线学习如果环境参数随着 episode 逐步暴露探索基于后悔最小化的在线策略选择方法。实际项目中最需要警惕的不是公式复杂度而是不确定性集合建得不对、候选策略之间区分度不足、以及数值误差干扰排序。建议先跑通本文的玩具示例再把不确定性区间换成一个真实业务场景中的置信区间观察遗憾排序是否直观再来决定是否需要引入更复杂的优化器。如果本文对你有帮助可以先收藏备用。你在实际项目里如果遇到 transfer probability 采样归一会出问题或者策略评估矩阵求逆报错欢迎在评论区把错误堆栈贴出来我们一起排查。