不确定环境里只能备几套策略？这篇论文给出了精确解法

做 AI 决策系统的人，迟早会撞上同一个问题：上线后遇到什么环境，根本没法提前预料。

这比"不知道明天天气"更底层——状态怎么转移、奖励怎么给，连模型本身都是一个未知数。机器人今天跑的是干燥车间，明天可能换成湿滑地面；推荐的用户画像、供应链的到货周期、调度系统里的突发拥堵，都可能在部署前后变得不一样。

传统做法分两路。一是硬着头皮训一个通用策略，在所有可能环境里凑合着跑，但每个环境的表现都谈不上好。二是给每个可能环境单独准备一个策略，但运营上管不过来——合规、审批、部署、测试，每个策略都得过一遍流程，k 一变大就失控。

能不能在两者之间找一个折中：提前准备一小套策略，等部署时环境的不确定性消解了，再从套里挑最合适的那个来用？怎么才算"最优"、选几套最划算，一直没有精确解法。

上周挂在 arXiv 上的一篇新论文——Sterre Lutz 和三位合作者的「Optimizing Minimax Regret in Uncertain MDPs with Small Sets of Policies」——回答的就是这个问题。

论文的核心设定是 k-adaptable policy synthesis。面对的不是单个 MDP，而是一组可能的环境模型（不确定 MDP，UMDP）——状态和动作空间相同，但转移概率和奖励函数可能不同。必须在知道真实环境之前就定好 k 个策略，等不确定性消除后再挑一个执行。目标是在最坏情况下让遗憾（regret，即选的策略和该环境最优策略之间的差距）最小化——也就是 minimax regret。

数学上，他们证明了这个问题是 NP-hard 的——没有那种又快又能保证最优的通用解法。但他们同时给出了 KAPS，一个精确的嵌套分支定界算法，带有针对问题定制的边界和启发式。它不只决定哪些 MDP 共享同一个策略，也同时优化策略本身。两件事一起解。

实验跑了多个 UMDP benchmark，结论很干脆：从 1 个策略增加到 2 个策略，是 regret 下降最陡的一步。再往上加，收益就边际递减了。对做产品的人来说，这是个很实用的信号——当前只部署一个通用策略的话，加上第二个策略可能是单位投入性价比最高的选择。不需要等到 k 很大才看到效果。

在单策略设定下（k=1），KAPS 和已有方法在解质量上持平，但能更频繁地证明找到了最优解。这个"证明最优"的能力，在生产场景里很值钱——得到的策略质量不错，而且有把握它是当前条件下的最优。

这篇是纯理论贡献，作者来自代尔夫特理工大学，不是硅谷产品论文。现场感的部分需要自己动手实现才能拿到。但它的视角很直接：不可能为每个可能性都准备一个策略，但应该知道最少需要准备几个、以及怎么准备才能让最坏情况下的损失最小。

正在做 Agent 系统或者任何需要预部署策略的决策 pipeline 的话，这篇值得花时间读一下。PDF 和 TeX 源码都挂在 arXiv: 2608.02509。14 页、5 张图、2 张表，属于那种可以一个下午吃透的硬理论文章。