在环境模型不确定的马尔可夫决策过程(UMDP)中,预先准备并部署少量(k个)策略,用极小极大遗憾准则优化这组策略,是NP-hard问题;作者提出精确嵌套分支定界算法KAPS。实验显示,遗憾下降最大的一步发生在策略数从1增加到2时;单策略情形下KAPS与现有方法质量相当且更常证明最优性。
值得关注:填补了“单一通用策略”和“每个MDP一个专用策略”之间的实用中间地带:在策略数量受现实约束时,提供最优的少量备用策略。 为“先准备少数预案、执行前根据已解析的不确定性选择”的决策场景提供了理论保证和精确算法。 与已有相…