在环境模型不确定的马尔可夫决策过程(UMDP)中,预先准备并部署少量(k个)策略,用极小极大遗憾准则优化这组策略,是NP-hard问题;作者提出精确嵌套分支定界算法KAPS。实验显示,遗憾下降最大的一步发生在策略数从1增加到2时;单策略情形下KAPS与现有方法质量相当且更常证明最优性。
现实中的序贯决策常面临环境模型不确定。UMDP将可能环境建模为一组共享状态和动作、但转移概率和奖励可能不同的MDP。若在所有可能MDP上优化单一策略,可能牺牲性能;若为每个MDP单独准备一个最优策略,又可能违反运营、监管或可解释性约束(如策略数量受限)。该研究考虑“模型不确定在即将执行前才被解决”的设置,从而可以在提前准备好的有限策略集合中选取最合适的策略…