不确定MDP中极小极大遗憾策略选择：数学建模与仿真验证

Optimizing Minimax Regret in Uncertain MDPs with Small Sets of Policies数学框架、算法实现与仿真验证这篇内容不是某个开源仓库也不是一个可直接 pip install 的工具包而是一个偏学术的研究主题在转移概率和奖励参数不确定的马尔可夫决策过程中如何从一个小规模的候选策略集合里选出“最不后悔”的策略。如果你正在做鲁棒决策、强化学习策略评估、或基于有限策略库的决策系统这篇文章可以直接收藏。问题的核心可以用一句话概括给定一组候选策略例如专家经验、历史策略、离线训练得到的策略库当真实环境模型未知时我们希望选出的策略在最坏情况下的遗憾尽可能小。这里“遗憾”指的是某个策略在真实环境中的累计回报与真实环境下最优策略的累计回报之间的差距。本文会带你完成三件事第一把极小极大遗憾问题写成可计算的优化问题第二给出枚举型和小样本型两种算法实现第三用网格世界和库存管理两个经典场景完成仿真验证并给出可复制的 Python 代码。文章适合以下读者正在研究鲁棒 MDP、模型误差下的策略选择、离线强化学习策略库筛选问题的同学需要用有限候选策略应对环境参数漂移的工程决策者以及想快速理解 minimax regret 概念并动手复现结果的算法工程师。1. 核心概念与数学模型先说清楚几个概念否则后续代码无从谈起。标准的马尔可夫决策过程可以表示为 $M (S, A, P, R, \gamma)$其中 $S$ 是状态集合$A$ 是动作集合$P(s|s,a)$ 是状态转移概率$R(s,a)$ 是立即奖励$\gamma \in [0,1)$ 是折扣因子。一个确定性策略 $\pi: S \rightarrow A$ 指定每个状态下应该执行的动作。在大多数实际场景中我们并不知道确切的转移概率 $P$ 和奖励 $R$。也就是说真实模型 $\theta^*$ 位于一个不确定集合 $\Theta$ 中。常见的不确定集合有两种建模方式不确定集合类型表达方式典型场景参数区间型$P(ss,a) \in [p_{min}, p_{max}]$概率单纯形型$P(\cdots,a) \in \Delta(S)$ 且满足 TV 距离约束矩约束型只约束均值、方差等矩信息数据稀缺但有一阶二阶统计量对于某个确定的模型参数 $\theta \in \Theta$设 $\pi_\theta^*$ 是模型 $\theta$ 下的最优策略$V^{\pi}_{\theta}(s_0)$ 是策略 $\pi$ 在初始状态 $s_0$ 下的折扣累计回报。策略 $\pi$ 在模型 $\theta$ 下的遗憾定义为$$ \text{Regret}{\theta}(\pi) V^{\pi{\theta}^*}{\theta}(s_0) - V^{\pi}{\theta}(s_0) $$这个值越大说明策略 $\pi$ 在模型 $\theta$ 下与最优策略的差距越大。本文关注的不是在整个策略空间 $\Pi$ 上寻优而是给定一个较小的候选策略集合 $\Pi_{cand} {\pi_1, \pi_2, \dots, \pi_K}$其中 $K$ 通常从几个到几十个不会太大。目标是最小化最坏情况遗憾$$ \min_{\pi \in \Pi_{cand}} ; \max_{\theta \in \Theta} ; \text{Regret}_{\theta}(\pi) $$这个目标与经典鲁棒优化中的“最大化最坏情况累计回报”不同。后者只关心收益下限而极小极大遗憾关心的是“我选的策略比事后诸葛亮差多少”。在许多决策场景中遗憾准则是更自然的选择因为决策者往往可以事后知道哪个策略本来是最好的。一个小规模策略集合带来的关键性质是无需遍历整个策略空间。这意味着遗憾评估和策略选择可以在策略维度上做到指数级简化主要的计算瓶颈转移到对参数空间 $\Theta$ 的搜索上。这正是本文算法设计的出发点。2. 适用场景与使用边界极小极大遗憾策略适用于哪些场景从实际项目经验来看至少要满足以下三个条件之一。第一候选策略本身是离散且有限的。例如医疗决策中医生给出的几种治疗方案、交通信号控制中的几套固定配时方案、工业生产中的几类调度规则。这些场景没有天然的策略参数梯度可用候选策略集合是人为定义好的规模很小。第二环境模型的不确定性可以用集合来描述。注意这里的不确定不是概率分布而是置信区间或约束集。如果环境参数是平稳随机变量且有足够数据估计完整分布那么贝叶斯方法或风险敏感强化学习可能更合适。反过来当样本量小、分布估计不可靠时不确定集合加遗憾准则就更稳。第三决策过程可能重复进行且每次决策后都能观察到真实模型的某个侧面。遗憾准则的意义在于“事后可评价”如果永远无法获知真实模型下哪个策略是最优的那么遗憾优化就缺乏验证基础。使用边界也要说清楚。首先不确定集合 $\Theta$ 的大小直接影响求解难度当状态-动作空间较大且不确定集合是高维乘积结构时最坏情况搜索本身就是一个复杂优化问题不能指望暴力枚举。其次候选策略集合如果构造得太差即使遗憾最小也是矮子里拔将军因此候选策略的覆盖度很重要。再次该方法只处理“参数不确定”不处理“非平稳环境中的分布漂移”如果环境变化过于剧烈需要引入在线学习或自适应机制。另外需要强调如果这个模型被用于真实决策系统涉及用户数据、医疗方案、金融操作等场景必须完成合规审查确保数据使用已获授权决策结果经过人工复核。鲁棒优化降低的是模型误差风险不能替代业务层面的安全约束。3. 环境准备与实验脚手架本文的仿真代码使用 Python 实现依赖非常少标准科学计算环境即可运行。下面给出示例环境配置实际使用时根据自身机器调整版本。3.1 依赖清单依赖用途推荐版本范围Python主语言3.8 及以上NumPy数组运算、线性规划接口1.24 及以上SciPy线性规划求解、优化器1.10 及以上Matplotlib结果可视化3.6 及以上tqdm实验进度显示4.60 及以上安装命令pip install numpy scipy matplotlib tqdm3.2 MDP 工具类我们不引入完整的强化学习库而是自己写一个轻量级 MDP 模拟器便于后续替换不确定集合和策略求解方式。import numpy as np class MDP: 有限状态、有限动作的折扣 MDP def __init__(self, n_states, n_actions, transition, reward, gamma0.9): self.n_states n_states self.n_actions n_actions self.transition transition # shape: (n_states, n_actions, n_states) self.reward reward # shape: (n_states, n_actions) self.gamma gamma def policy_evaluation(self, policy): 策略评估解线性方程组 V R_pi gamma * P_pi * V 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 policy[s] P_pi[s, :] self.transition[s, a, :] R_pi[s] self.reward[s, a] A np.eye(self.n_states) - self.gamma * P_pi V np.linalg.solve(A, R_pi) return V def value_iteration(self): 值迭代求解最优策略 V np.zeros(self.n_states) policy np.zeros(self.n_states, dtypeint) for _ in range(10000): delta 0.0 for s in range(self.n_states): q_values self.reward[s, :] self.gamma * self.transition[s, :, :] V new_v np.max(q_values) delta max(delta, abs(new_v - V[s])) V[s] new_v if delta 1e-12: break for s in range(self.n_states): q_values self.reward[s, :] self.gamma * self.transition[s, :, :] V policy[s] np.argmax(q_values) return V, policy这段代码基于全状态空间枚举式的值迭代实现适合中小规模 MDP。对于大状态空间可以替换成近似动态规划或其他强化学习求解器后续算法框架不变。3.3 项目目录结构robust_mdp_experiments/ ├── mdp.py # MDP 基础类 ├── uncertainty.py # 不确定集合定义 ├── regret_optimizer.py # 极小极大遗憾策略选择算法 ├── experiments/ │ ├── gridworld.py # 网格世界实验 │ └── inventory.py # 库存管理实验 └── results/ # 结果输出目录先创建results目录保存实验输出这里不做强制要求但建议养成分类管理的习惯。4. 极小极大遗憾优化算法设计与实现从计算角度核心问题是求解$$ \min_{\pi \in \Pi_{cand}} ; \max_{\theta \in \Theta} ; \left[ V_{\theta}^{\pi_{\theta}^*}(s_0) - V_{\theta}^{\pi}(s_0) \right] $$当 $\Theta$ 是连续集合时这是一个双层优化问题。外层是离散策略选择内层是连续参数空间上的最坏情况搜索。本文分三步解耦对每个候选策略 $\pi$构造遗憾函数 $f_\pi(\theta)$在内层搜索 $f_\pi(\theta)$ 在 $\Theta$ 上的最大值得到策略 $\pi$ 的最坏遗憾外层比较所有候选策略选出最坏遗憾最小的策略。真正困难的是第 2 步即对每个策略求解最坏遗憾。本文给出两种方法。4.1 方法一顶点枚举法当不确定集合 $\Theta$ 是多面体且遗憾函数关于 $\theta$ 在 $\Theta$ 上是凸函数时最大值一定可以在多面体的某个顶点达到。因此可以通过枚举不确定集合的顶点来求解最坏遗憾。def worst_case_regret_by_vertices(mdp_base, policy, vertices, gamma0.9, s00): 枚举不确定集合顶点计算策略 policy 的最坏遗憾 vertices: list of transition tensors每个都是形状 (S,A,S) 的合法概率张量 worst_regret -np.inf worst_vertex None for idx, theta in enumerate(vertices): mdp MDP(mdp_base.n_states, mdp_base.n_actions, theta, mdp_base.reward, gamma) # 求解当前参数下的最优策略值 V_opt, optimal_policy mdp.value_iteration() # 评价候选策略在当前参数下的值函数 V_pi mdp.policy_evaluation(policy) regret V_opt[s0] - V_pi[s0] if regret worst_regret: worst_regret regret worst_vertex idx return worst_regret, worst_vertex顶点枚举的优点是实现简单、结果精确。缺点是顶点数量可能随不确定集合维度指数增长。在状态转移概率张量的每个元素都有独立区间的情况下顶点数量会非常庞大。因此这个方法只适合不确定集合并行维度较低、或者稀疏支撑结构的场景。4.2 方法二投影梯度上升法当不确定集合是连续凸集但顶点枚举不可行时可以使用基于梯度的搜索。对每个候选策略 $\pi$在 $\Theta$ 上做投影梯度上升逼近最坏遗憾参数。关键一步是计算遗憾函数关于转移概率的梯度。用价值函数表达后可以通过灵敏度分析获得近似梯度。主循环如下def worst_case_regret_by_gradient(mdp_base, policy, theta_init, step_size0.1, max_iter100, projectionNone, gamma0.9, s00): theta theta_init.copy() best_regret -np.inf best_theta theta.copy() for _ in range(max_iter): mdp MDP(mdp_base.n_states, mdp_base.n_actions, theta, mdp_base.reward, gamma) V_opt, _ mdp.value_iteration() V_pi mdp.policy_evaluation(policy) regret V_opt[s0] - V_pi[s0] if regret best_regret: best_regret regret best_theta theta.copy() # 数值梯度近似对转移概率的每个分量做扰动 grad np.zeros_like(theta) eps 1e-5 for s in range(mdp_base.n_states): for a in range(mdp_base.n_actions): for s_next in range(mdp_base.n_states): theta_plus theta.copy() theta_plus[s, a, s_next] eps # 重新归一化保证是合法概率 theta_plus[s, a] / theta_plus[s, a].sum() mdp_plus MDP(mdp_base.n_states, mdp_base.n_actions, theta_plus, mdp_base.reward, gamma) V_opt_plus, _ mdp_plus.value_iteration() V_pi_plus mdp_plus.policy_evaluation(policy) regret_plus V_opt_plus[s0] - V_pi_plus[s0] grad[s, a, s_next] (regret_plus - regret) / eps theta theta step_size * grad if projection is not None: theta projection(theta) return best_regret, best_theta数值梯度法在小规模 MDP 上可以跑通但复杂度高不适合大规模状态空间。更实际的方案是推导解析梯度或者使用自动微分框架。对于本文的仿真实验数值梯度已经足够。实际项目需要时可改用 PyTorch 实现并利用反向传播加速。4.3 外层策略选择外层遍历所有候选策略即可def select_minimax_policy(candidate_policies, mdp_base, theta_vertices, gamma0.9, s00, use_gradientFalse): worst_regrets [] for pi in candidate_policies: if use_gradient: theta_init np.random.dirichlet(np.ones(mdp_base.n_states)) theta_init np.broadcast_to(theta_init, (mdp_base.n_states, mdp_base.n_actions, mdp_base.n_states)).copy() regret_val, _ worst_case_regret_by_gradient( mdp_base, pi, theta_init, projectionproject_to_simplex) else: regret_val, _ worst_case_regret_by_vertices( mdp_base, pi, theta_vertices, gamma, s0) worst_regrets.append(regret_val) print(fPolicy {pi} worst-case regret {regret_val:.6f}) best_idx int(np.argmin(worst_regrets)) return best_idx, worst_regrets需要补充的是投影函数project_to_simplex的作用是将梯度上升后的转移概率矩阵投影回概率单纯形保证每一行仍然是合法的概率分布。5. 功能测试 1网格世界中的策略选择仿真网格世界是验证 MDP 算法的标准场景。本次实验使用一个 6x6 的网格状态数 36动作数 4上、下、左、右折扣因子 $\gamma0.9$目标状态为右下角。5.1 实验设计候选策略集合设置为 4 个手动构造的策略策略 A偏向向下和向右移动适合奖励分布偏向目标区域的环境策略 B偏向向上和向左移动适合存在捷径但方向不同的环境策略 C均匀随机策略保证一定探索性策略 D最短路径贪心策略总是选择曼哈顿距离更小的方向。不确定集合构造如下真实转移概率以某个基准转移矩阵为中心每个 $(s,a)$ 行允许在基准值的 ±10% 范围内扰动再投影回概率单纯形。def build_gridworld_uncertainty(base_transition, seed42): rng np.random.default_rng(seed) n_states base_transition.shape[0] n_actions base_transition.shape[1] vertices [] # 顶点枚举简化版对每个动作行做扰动 for _ in range(50): theta base_transition.copy() for s in range(n_states): for a in range(n_actions): noise rng.uniform(-0.1, 0.1, n_states) theta[s, a] noise theta[s, a] np.clip(theta[s, a], 0, None) if theta[s, a].sum() 0: theta[s, a] / theta[s, a].sum() vertices.append(theta) return vertices5.2 运行结果与分析运行实验后会得到每个候选策略的最坏遗憾值。典型结果为策略 A 的最坏遗憾最小策略 B 在最坏情况下的表现最差策略 C 的遗憾介于中间。这里的核心观察是按期望累计回报排序的策略排名与按最坏遗憾排序的排名可能不一致。策略 A 的单点最优性能可能不是最高但在参数扰动下表现稳因此遗憾最小。这正是极小极大遗憾准则与普通性能评估的差异所在。将结果输出为表格策略 最坏遗憾 均值遗憾 计算时间(s) A 1.234 0.310 0.42 B 3.452 0.512 0.41 C 2.180 0.405 0.40 D 2.562 0.378 0.38注意以上数字是仿真生成的示例具体数值取决于随机种子和游走策略这里关注的是排序关系和对比方法。6. 功能测试 2库存管理中的批量策略评估第二个实验是单周期库存管理问题。状态是当前库存量0 到 20动作是补货量0 到 10需求分布参数不确定。6.1 实验设计与代码候选策略为三种常见补货规则基库存策略当库存低于阈值 $L$ 时补货到 $U$固定数量策略每次固定补货 5 件不补货策略仅消耗库存。需求分布使用离散泊松近似但需求均值 $\lambda$ 不确定假设 $\lambda \in [3, 7]$。由于需求分布不确定这里通过离散化需求概率向量构建不确定集合。def inventory_reward(state, action, demand_dist): 库存成本持有成本 缺货损失 next_stock max(0, state action - demand_dist) holding 0.5 * next_stock shortage 2.0 * max(0, demand_dist - (state action)) return -(holding shortage)由于需求分布参数连续这里使用投影梯度上升法搜索最坏遗憾不再使用顶点枚举。6.2 批量运行实际工程中往往需要对多个不确定集合参数批量运行策略选择实验。可以通过一个简单的循环完成def batch_experiment(candidate_policies, lambdas, mdp_base, n_repeat10): results [] for lam in lambdas: for rep in range(n_repeat): theta_init build_inventory_uncertainty(lam) best_idx, regrets select_minimax_policy( candidate_policies, mdp_base, theta_init, use_gradientTrue) results.append({ lambda: lam, repeat: rep, best_policy: best_idx, worst_regrets: regrets }) return results批量运行建议把中间结果实时写入 CSV 或 jsonl 文件避免程序中断后数据丢失。同时给每个任务加上种子和日志方便复现。6.3 结果解读库存实验通常会出现以下规律当需求均值很小时不补货策略的遗憾很小因为不会产生大量积压成本当需求均值较大时基库存策略的优势显现固定数量策略在中间区间较稳但两端表现波动。这里的“小型候选策略集合”体现出工程价值不需要精确知道 $\lambda$ 的具体值只需要从少量现成的补货规则中选一个就能把最坏后悔控制在可接受范围。7. 性能观测与资源占用运行极小极大遗憾优化时需要关注计算资源的消耗。从经验上讲瓶颈主要在三处。第一是值迭代求解最优策略的次数。在方法一顶点枚举中内层需要为每个顶点调用一次完整的值迭代在方法二梯度上升中每一步梯度计算可能包含多次策略评估。当状态数量达到数千时Python 的纯循环实现会明显变慢。第二是梯度计算的开销。数值梯度法需要对转移矩阵的每个元素做扰动并重新评估复杂度为 $O(S^2 A T_{eval})$其中 $T_{eval}$ 是单次策略评估的开销。建议在更大规模实验中使用解析梯度或自动微分。第三是候选策略数量 $K$。遗憾优化需要为每个候选策略单独搜最坏情况$K$ 从 5 增加到 50总时间近似线性增加。内存方面转移概率张量的大小是 $S \times A \times S$。以 1000 状态、4 动作为例一个 float64 的转移张量约为 32MB梯度计算时如果复制多份内存会成倍增加。建议使用np.copy时注意释放中间变量或者改用 PyTorch 张量并利用原地操作。显存概念在这个纯 CPU 实验中不适用。如果后续使用神经网络逼近值函数并改用 GPU 加速才需要考虑显存占用。本文实验全部在 CPU 上完成普通笔记本即可运行。8. 常见问题与排查方法在实际复现和扩展中会遇到一些问题下面按优先级整理。问题现象可能原因排查方式解决方案值迭代不收敛折扣因子接近 1 或奖励尺度异常检查折扣因子和奖励量级调低折扣因子对奖励做归一化顶点枚举结果始终相同不确定集合构造得太窄打印扰动前后的转移概率差异增大扰动范围检查顶点是否覆盖到边界梯度上升过程震荡步长过大或投影方式不匹配打印每步的遗憾值和参数变化减小步长引入动量或 Adam 式更新转移概率行求和不为 1扰动后未归一化检查噪声添加逻辑每次扰动后用行归一化修正策略评估出现无穷大值转移概率矩阵奇异或折扣因子为 1检查矩阵条件数使用带小正则项的线性求解器批量实验进程卡住单次最坏情况搜索超时添加迭代次数上限和打印日志为每个任务设置超时时间超时跳过结果不可复现随机种子未固定检查 numpy 全局种子和每个实验的种子在入口处设置np.random.seed(42)函数worst_case_regret_by_gradient太慢数值梯度计算量过大使用 cProfile 分析耗时换解析梯度减少状态动作空间排查时最重要的一点是先验证单个策略的遗憾计算再扩展到策略选择。单独调用policy_evaluation和value_iteration确认单点数值合理后再观察最坏情况搜索是否合理。9. 最佳实践与扩展方向9.1 工程实践建议第一候选策略集合的构建要讲究覆盖度。如果候选策略之间相关性过高极小极大遗憾选择很难带来实际收益。建议从不同逻辑来源构造候选策略例如基于启发式的、基于历史数据的、基于简化模型的优化策略。第二不确定集合的标定需要结合数据。不要随意设置 ±10% 的扰动范围应该根据历史样本的置信区间或专家知识确定。不确定集合过小会低估风险过大会使优化结果过于保守。第三建议先跑一次小规模简化版验证代码逻辑后再扩大实验。示例中可以先在 4x4 网格上跑通再切到 6x6最后再上库存实验。第四对每个实验任务设置唯一标识的随机种子并把参数配置以 JSON 文件形式保存。这样做的好处是故障复现和结果对比都非常方便。9.2 算法扩展方向本文的框架可以沿多个方向扩展。方向一从确定性策略扩展到随机策略。候选策略如果是混合策略则外层不再是简单的枚举而需要在概率单纯形上做优化这可以写成一个小规模非线性规划问题。方向二从离线策略选择扩展到在线策略切换。如果环境在一段时间后会发生变化可以周期性重新计算极小极大遗憾形成一个简单而有效的自适应决策机制。方向三引入贝叶斯遗憾。如果除了不确定集合还能得到参数的后验分布可以把最坏遗憾替换为期望遗憾此时优化目标变成贝叶斯风险最小化计算方式完全不同。方向四与离线强化学习结合。候选策略可以来自多个离线训练 checkpoint使用极小极大遗憾准则作为模型选择指标比单纯看离线评估分数更稳健。9.3 使用边界提醒需要再次强调极小极大遗憾准则天然偏向保守。在候选策略中它倾向于选择“最坏情况下损失最小”的策略而不是“平均表现最好”的策略。如果业务场景追求的是平均收益最大化而不是风险控制那么这套框架可能不是最优选择。建议在项目开始时明确决策准则不要混用。10. 总结与后续动作这次实现的极小极大遗憾优化框架核心价值是把“不确定 MDP 中从少量候选策略中做选择”这个抽象问题落成了一套可运行的算法流程。你首先应该验证的是最小的网格世界实验确认值迭代、策略评估和遗憾计算三个环节正确再把候选策略批量跑通。最容易踩的坑有两个一是不确定集合构造不合理导致结果无区分度二是数值梯度步长不当导致优化不稳定。后续可以继续扩展的方向包括把数值梯度替换为解析梯度或自动微分、把策略评估与值迭代换成神经网络近似求解器、把候选策略集合扩展到混合策略空间。对决策系统而言这套框架可以作为离线策略保险的一种通用评估手段在模型参数不确定、样本量不足时给出一个保守且可解释的选择建议。建议收藏备用尤其是当你需要处理“只有少量策略可选又不确定环境参数”的决策问题时直接把文中的算法骨架拿过去改造即可。