在真实项目中我们经常遇到一类棘手问题MDP 的转移概率并不是固定值而是一个模糊区间。想象你在做一个仓库机器人调度系统机器人在不同货架区域的搬运成功率受地面摩擦、货物重量分布影响你只能给出“大概在 0.7 到 0.9 之间”这样的估计又或者你在做网络流量调度链路拥塞概率会随业务波动你能确定的只是一个合理范围。此时按传统强化学习思路直接基于点估计训练策略结果可能在真实环境里严重偏离预期。而如果把所有不确定参数都按最坏情况处理策略往往又过于保守实际收益低到无法接受。这就是本文要讨论的核心问题在不确定 MDPUncertain MDPs中如何用尽量少的候选策略找到最不后悔的决策。minimax regret 在这里提供了一个中间路线——它不追求在最坏场景下收益最大而是追求“无论真实环境落在哪个点我们选的策略与那个环境下最优策略之间的差距尽量小”。更关键的是标题后半句small sets of policies。不是在全策略空间做全局搜索而是从你手里已有的少数几个策略里挑一个最稳的。这个思路非常贴近工程实践模型可以有很多套但能上线的往往就那么几套。本文会从基础概念讲起然后解释为什么“小策略集合”是这类问题的关键设计自由度接着给一个可直接运行的 Python 最小示例最后说明常见坑和落地建议。无论你是做算法策略的同学还是搞决策优化的工程师都可以把它当作一个入门 minimax regret 决策的实操指南。1. 这篇文章真正要解决的问题先看一个常见场景。某团队做一个智能投放系统状态是用户活跃度等级动作是“减少投放”“维持投放”“加大投放”。转移概率依赖外部流量环境而流量环境的波动范围是已知区间。训练时如果只取均值概率策略在流量较差月份可能崩盘如果按最坏情况做 robust MDP策略又会在大促月错过放量机会。团队真正需要的是一个既不会在坏月份过度损失、又能在好月份吃到红利的折中策略。minimax regret 解决的就是这个“折中”问题。它不问你“最坏情况下的绝对收益是多少”而是问“你选的策略相比真实环境下的最优策略差了多少”。这个差值叫 regret。然后你选一个策略让这个 regret 在所有可能环境上的最大值尽可能小。换句话说它追求的是“任何环境下都不会差太多”而不是“某个环境下做到最好”。这与经典 robust MDP 有本质区别。经典 robust MDP 的目标是最大化最坏情况累计收益也就是 max-min 形式。它在安全关键场景里很有用但在商业、调度、推荐这类场景中往往显得过于悲观。minimax regret 的立场是我不知道真实环境是哪一个但我拒绝因为一个极端的坏场景就放弃在大多数场景下的正常表现。还有一层现实原因绝大多数业务团队并没有在全策略空间搜索的能力和必要。你手里可能只有基于历史数据训练的策略 A、规则专家写的策略 B、线上正在运行的老策略 C。你要做的不是再搜出一个从未见过的策略 D而是从 A、B、C 里选一个在任何环境认知下都相对靠谱的。这正是“small sets of policies”的实际价值它把一个理论优化问题变成了工程上完全可控的策略评估与选择问题。这篇文章适合三类读者一是正在做强化学习落地、但环境模型并不精确的工程师二是做决策优化、需要给业务方解释“为什么选这个策略”的算法同学三是对鲁棒决策、遗憾最小化这类课题感兴趣、想快速跑通最小示例的研究生。2. 基础概念与核心原理2.1 不确定性 MDP 是什么标准的马尔可夫决策过程MDP由状态集合 S、动作集合 A、转移概率 P、奖励函数 R 和折扣因子 γ 组成。所谓“不确定性 MDP”是指转移概率 P 不是一个精确已知的矩阵而是属于一个不确定集合 U。形式化一点我们关心的转移概率不是单个值而是一个区间。例如P(s | s, a) ∈ [L(s,a,s), U(s,a,s)]这种模型在文献里也叫区间 MDPInterval MDP或鲁棒 MDP 的变体。区别在于普通 MDP 里策略的优化目标是最大化期望回报而在不确定性 MDP 里由于 P 不确定你没法直接算出一个唯一的最优策略价值必须定义“最优”的语义。常见的语义有两种一种是 max-min即让最坏情况下的价值最大化另一种是 minimax regret即让最大遗憾最小化。本文后面全部围绕第二种展开。2.2 什么是 RegretRegret 的中文直译是“遗憾”在决策论里通常表示如果你知道真实环境参数 P你本来能拿到的最优回报与你实际使用的策略 π 拿到的回报之间的差距。假设 V*(P) 表示已知真实环境 P 时的最优价值V^π(P) 表示策略 π 在环境 P 下的价值那么 Regret 的定义为Regret(P, π) V*(P) - V^π(P)这个值越大说明你在环境 P 下的表现离“完美决策”越远等于 0 说明你已经是最优。如果你能把 Regret 控制在一个较小范围内就相当于给决策上了一道保险即使我对真实环境判断有误损失也是有限的而不是灾难性的。2.3 Minimax Regret 的优化目标因为真实 P 落在不确定集合 U 里所以要考虑所有可能的 P。minimax regret 的策略选择目标写成π* argmin_{π ∈ Π_candidate} max_{P ∈ U} [ V*(P) - V^π(P) ]外层是 min表示我们要选一个策略内层是 max表示要考虑最坏情况下的遗憾。合起来就是“选择一个让最大遗憾最小的策略”。这里有一个非常容易被忽略的细节内层的 V*(P) 是根据真实环境 P 算出来的最优价值不是根据不确定集算出来的“鲁棒最优价值”。也就是说我们在评价一个策略有多好时参照物是“如果早知道真实环境我能做到的最好成绩”。这比 max-min 更贴近现实竞争逻辑——业务上最怕的不是绝对收益低而是别人做得好、你做得差。2.4 Robust MDP 与 Minimax Regret 的对比维度Robust MDPmax-minMinimax Regret优化目标最大化最坏情况收益最小化最大遗憾决策风格极度保守倾向防守防守中保留进攻空间参照基准自身绝对收益不同环境下的最优策略适合场景安全关键系统、灾难规避商业决策、调度、推荐、博弈对不确定集的敏感度由最坏点完全决定由各场景相对差距决定计算复杂度通常较高取决于候选策略与场景数从表里可以看出一件事minimax regret 更符合“既要活下去又要抓机会”的决策需求。它不是不防守而是防守方式更聪明——它不让自己在最坏场景下被拉开太大差距。3. 为什么“小策略集合”是关键3.1 残酷的现实策略空间太大理论上的最优策略可能存在于整个策略空间中但由于状态数和动作数通常很大穷举所有确定性策略并不可行。更麻烦的是即使理论上能找到全局 minimax regret 最优策略这个策略也往往形态复杂、无法解释、难以部署。“small sets of policies”提供了一个工程视角的解法不追求在整个策略空间搜索而是先给定一个候选策略集合 Π_candidate。这个集合可以来自业务经验、历史策略、已有算法产物甚至专家直觉。目标变成在 Π_candidate 内选一个 max regret 最小的策略。这样一来问题复杂度大大降低你只需对每个候选策略、每个不确定性场景做价值评估然后做比较和选择。整个流程可以并行也可以用很小的算力完成。3.2 策略集合本身就是设计自由度很多新手会问候选策略集合怎么给答案是这本身就是决策设计的一部分。集合给得大覆盖面广但评估成本高且可能选到“只在一个场景好、其他场景特别差”的策略集合给得小评估成本低但可能漏掉真正优秀的折中方案。在实际项目里更合理的做法是先根据业务知识准备 3 到 10 个语义可解释的策略再计算它们各自在所有极端场景下的 regret。如果发现某个策略无论在哪类场景都明显劣于其他策略直接淘汰如果发现个别策略之间存在互补性可以进一步考虑混合策略或随机策略作为扩展候选。3.3 边界场景与极端策略的规律从很多论文和实证研究里可以观察到一个稳定规律minimax regret 的最优解通常不会落在不确定集合“内部”的某个温和点上而是由不确定集合边界上的极端场景主导。原因其实很直观。Regret 是 V*(P) 与 V^π(P) 的差值而这两个函数对 P 一般近似线性或凸。线性函数的最值出现在区间端点凸函数的最值也倾向于出现在顶点。所以你在评估策略的时候优先关注的不是所有中间概率而是每个转移概率取左端点或右端点所组成的极端场景。这就是为什么小集合策略可以成立我们并不是在所有连续不确定集上做积分或随机采样而是把注意力集中在少数关键边界场景上。这既降低了计算量也保留了决策的鲁棒性。3.4 从全空间搜索到策略评估的两步法理解了上面的逻辑你会发现这类问题可以拆成两步第一步构造候选策略集合 Π_candidate。数量可以小但覆盖业务上的几种典型打法。 第二步针对不确定集 U 的重要场景一般是边界顶点评估每个候选策略的表现计算 max regret最后选择最小值对应的策略。这两个步骤完全可以用工程手段落地策略用表格映射表示场景用数组枚举价值用贝尔曼方程求解。接下来我们用实际例子演示这个过程。4. 算法流程拆解为了更好地理解完整实现先给出一个通用的计算流程。整个过程分为四个阶段阶段一定义不确定性集合 U。这里的核心是把每个转移概率表达成区间并注意保证概率合法性。阶段二构建候选策略集合 Π_candidate。每个策略需要明确规定在每个状态下执行哪个动作。阶段三对每个场景计算所有策略的价值。这里的“场景”是从不确定集 U 中选取的代表点通常是边界端点。阶段四计算每个策略的 max regret再取 min。最终胜出的策略就是 minimax regret 最优策略。伪代码如下def minimax_regret_selector(scenarios, policies, eval_fn): scenarios: 不确定性场景列表 policies: 候选策略列表 eval_fn: 给定场景和策略返回策略在该场景下的价值 regret_records {p: [] for p in policies} for env in scenarios: # 1. 在当前环境下评估每个候选策略的价值 values {p: eval_fn(env, p) for p in policies} # 2. 当前环境下的最优价值作为参照 best_value max(values.values()) # 3. 记录每个策略在该场景下的 regret for p in policies: regret_records[p].append(best_value - values[p]) # 4. 每个策略取最大 regret再选最小 max_regret {p: max(vals) for p, vals in regret_records.items()} best_policy min(max_regret, keymax_regret.get) return max_regret, best_policy这里的核心是eval_fn。它负责解一个给定场景下的价值函数。为简单起见我们用一个固定初始状态或初始分布的价值来比较。工程中如果状态很多通常用值迭代或线性规划如果状态数较少可以直接解贝尔曼方程。5. 完整 Python 示例在一个小型不确定 MDP 上计算 Minimax Regret现在用一个可直接运行的最小示例跑通整个流程。这个示例刻意做得小目的不是模拟工业级规模而是把计算逻辑讲透。5.1 问题设定我们设计一个两状态、两动作的 MDP状态 0正常状态。状态 1异常状态。两个动作分别为动作 A高风险策略。在状态 0 下奖励高但转移到正常状态的概率较低在状态 1 下积极修复但会付出代价。动作 B保守策略。在状态 0 下奖励低但切换到正常状态的概率较高在状态 1 下放任不管没有即时惩罚。为了体现“不同极端场景最优策略会切换”的特点我们把转移概率设成区间状态 0 执行 A转移到状态 0 的概率区间为 [0.3, 0.5]状态 0 执行 B转移到状态 0 的概率区间为 [0.7, 0.9]状态 1 执行 A转移到状态 0 的概率区间为 [0.8, 0.9]状态 1 执行 B转移到状态 0 的概率区间为 [0.2, 0.4]奖励设置如下R(0, A) 20R(0, B) 6R(1, A) -10R(1, B) 0折扣因子 γ 取 0.9。初始状态固定为状态 0价值函数以状态 0 的期望总回报为比较标准。候选策略来自两个动作在状态 0 和状态 1 上的任意组合共 4 个策略。这个例子里候选策略数量小但整个计算流程与大规模场景是一致的。5.2 完整可运行代码import numpy as np import itertools # 状态与动作 states [0, 1] actions [A, B] gamma 0.9 # 奖励 R[s][a] R { 0: {A: 20.0, B: 6.0}, 1: {A: -10.0, B: 0.0}, } # 不确定转移参数 theta(s, a) 从状态 s 执行动作 a 后转移到状态 0 的概率区间 theta_bounds { (0, A): (0.3, 0.5), (0, B): (0.7, 0.9), (1, A): (0.8, 0.9), (1, B): (0.2, 0.4), } # 候选策略集合每个策略是 {状态: 动作} policies [] for a0 in actions: for a1 in actions: policies.append({0: a0, 1: a1}) # 为不确定集合生成所有边界场景每个参数取左端点或右端点 keys list(theta_bounds.keys()) scenarios [] for choices in itertools.product([0, 1], repeatlen(keys)): theta {} for key, choice in zip(keys, choices): theta[key] theta_bounds[key][choice] scenarios.append(theta) def policy_value(policy, theta, init_state0): 在 theta 确定的 MDP 中计算指定策略从 init_state 出发的期望回报。 # 构建转移矩阵 P[s][s] P np.zeros((2, 2)) for s in states: a policy[s] p0 theta[(s, a)] P[s, 0] p0 P[s, 1] 1 - p0 # 奖励向量 r np.array([R[s][policy[s]] for s in states]) # 解贝尔曼方程V r gamma * P V (I - gamma * P) V r I np.eye(2) V np.linalg.solve(I - gamma * P, r) return V[init_state] def minimax_regret_selector(scenarios, policies, eval_fn): 给定场景列表和策略列表返回最大遗憾字典和最优策略。 regret_records {tuple(policy.items()): [] for policy in policies} for theta in scenarios: values {} for policy in policies: key tuple(policy.items()) values[key] eval_fn(policy, theta) best_value max(values.values()) for key, v in values.items(): regret_records[key].append(best_value - v) max_regret {key: max(vals) for key, vals in regret_records.items()} best_key min(max_regret, keymax_regret.get) # 将 key 转回 dict方便阅读 best_policy dict(best_key) return max_regret, best_policy # 执行计算 max_regrets, best_policy minimax_regret_selector(scenarios, policies, policy_value) # 打印每个策略的最大遗憾 print( 各候选策略的 Max Regret ) for key, regret in sorted(max_regrets.items(), keylambda x: x[1]): print(f策略 {dict(key)} max regret {regret:.4f}) print(\n Minimax Regret 最优策略 ) print(最优策略, best_policy)将以上代码保存为minimax_regret_demo.py然后执行python minimax_regret_demo.py5.3 关键逻辑解释代码里有几个值得注意的地方。第一我们用theta[(s, a)]表示“从状态 s 执行动作 a 后转移到状态 0 的概率”另一个状态的概率直接用1 - p0这样就避免了“所有动作概率和必须为 1”的校验问题。第二价值函数通过线性方程求解。对一个小型 MDP 来说np.linalg.solve是最稳定的方式如果状态数很大可以改成值迭代或策略迭代。第三场景生成使用了笛卡尔积。每个不确定参数取左右端点最终生成2^4 16个极端场景。这种做法的好处是覆盖了不确定集的所有角落也符合 minimax regret 最优解倾向于出现在边界点的判断。如果参数再多场景数会指数增长届时需要改用场景采样或启发式选点。第四比较策略优劣时我们固定以状态 0 的期望回报作为标准。这是业务上的一个选择初始状态分布决定了你更看重哪个状态下的表现。如果业务认为状态 1 更重要就需要改成初始状态分布加权例如 0.5 * V0 0.5 * V1。6. 运行结果与效果验证代码运行后会打印两部分内容。第一部分是每个候选策略对应的 max regret第二部分是最优策略的映射。预期输出结构如下 各候选策略的 Max Regret 策略 {0: A, 1: A} max regret ... 策略 {0: A, 1: B} max regret ... 策略 {0: B, 1: A} max regret ... 策略 {0: B, 1: B} max regret ... Minimax Regret 最优策略 最优策略 {0: ..., 1: ...}如何判断结果是否正确首先检查 16 个场景是否全部成功解出值没有 NaN 或 inf。其次观察每个策略的 max regret 是否都是非负数。理论上 regret 一定大于等于 0如果出现负数说明best_value计算错了。最后看最优策略它应该是所有候选策略中 max regret 最小值对应的策略。这个策略未必是某个场景下表现最好的策略但在所有场景上的最大差距最小。如果你的输出出现了 NaN优先检查折扣因子是否小于 1以及转移区间端点是否落在 [0, 1] 之外。这个示例中参数都经过设计正常情况下运行即可。还可以手动验证一个极端场景。比如取theta(0, A) 0.5、theta(0, B) 0.7、theta(1, A) 0.9、theta(1, B) 0.4用代码里的policy_value单独计算每个策略的价值再与场景最优值对比就能手工核对 regret 的计算过程。7. 常见问题与排查思路问题现象可能原因排查方式解决方案计算出 NaN 或 inf折扣因子 γ 大于等于 1检查 gamma 配置将 γ 设为小于 1例如 0.9概率区间不合法θ 区间端点不在 [0,1] 内打印 theta_bounds 检查修正区间保证每个 θ 落在 [0,1]所有策略 max regret 都为 0候选策略里有一个在所有场景都最优打印各场景最优策略调整奖励或转移区间增加策略竞争性场景数量爆炸参数太多笛卡尔积过大打印场景数使用边界点采样或启发式选点策略选择不符合业务预期初始状态分布设置不合理检查 eval_fn 中的 init_state改用初始状态分布加权价值线性方程求解失败转移矩阵与折扣因子导致矩阵奇异检查 P 与 gamma改用值迭代替代直接求解其中“初始状态分布”是最容易忽略的问题。同一个策略如果以状态 0 的期望回报为标准和以状态 1 为标准可能得到完全不同的 minimax regret 结论。这在很多业务里并不是理论问题而是定义问题。建议在项目开始时就明确业务最关心哪个状态、哪个入口场景。另外如果策略池里有明显被支配的策略比如某个策略在 16 个场景里没有一个场景是最优的它通常也不会成为 minimax regret 的胜者。可以先删掉这类策略减少后续计算压力。8. 实际应用场景与落地建议8.1 机器人路径规划与调度机器人所在环境的转移概率经常受地面条件、负载、传感器噪声影响。工程上可以用几套预设策略来应对保守绕路、快速直行、混合策略。在实际部署前把所有历史环境参数整理成不确定区间用本文流程计算各策略的 max regret选一个兜底性能最好的方案上线。相比 max-min 策略minimax regret 策略不会因为某个极端坏场景就把所有任务都切换成龟速模式更符合仓储、物流、配送的运营目标。8.2 供应链库存与采购决策库存管理里需求量本身就是一个不确定参数。候选策略可以是“多备货”“少备货”“动态调整”。需求区间可以从历史分位数估计。用 minimax regret 选策略能保证需求无论落在区间的哪一端你的库存决策都不会比“提前知道需求”的最佳决策差太多。尤其在双十一、大促这类需求波动场景这个思路比纯 max-min 更实用。8.3 网络流量调度与资源分配网络流量矩阵通常只有区间估计。候选策略包括固定路由、负载均衡、备份路径切换。因为流量场景在一天内会剧烈变化用 minimax regret 选出的策略能在不同流量组合下都保持不错的资源利用率。少数几个策略也便于运维团队理解和维护不会出现“理论上最优但没人敢改”的黑盒策略。8.4 金融与投资策略选择在投资组合里资产收益率的协方差矩阵很难精确估计通常只能给出区间。候选策略可以是保守组合、均衡组合、进取组合。minimax regret 方法不会因为某个极端行情就把组合完全推向现金也不会因为追求高收益而在普遍场景下大幅跑输。它选出的策略往往在“任何市场环境下都不至于太难看”这个意义上更符合长期投资目标。8.5 与在线学习的结合方式minimax regret 是一种静态稳健决策适合在无法快速获取真实环境反馈时使用。如果系统允许在线交互推荐的做法是第一周先部署 minimax regret 选出的策略保证基础表现。同时用线上数据不断收窄转移概率区间。两周后基于更窄的区间重新评估候选策略如果某个旧策略的 max regret 显著上升就更换策略。这种“先稳健、后精细”的做法