Decomposition methods for solving Markov decision processes with multiple models of the parameters
研究了当奖励或转移概率参数不确定时，决策者考虑多个参数模型并寻找优化期望或最差性能策略的马尔可夫决策过程，提出了分支切割和基于策略的分支定界解法，实验表明后者显著优于混合整数规划方法。
We consider the problem of decision-making in Markov decision processes (MDPs) when the reward or transition probability parameters are not known with certainty. We study an approach in which the decision maker considers multiple models of the parameters for an MDP and wishes to find a policy that optimizes an objective function that considers the performance with respect to each model, such as maximizing the expected performance or maximizing worst-case performance. Existing solution methods rely on mixed-integer program (MIP) formulations, but have previously been limited to small instances, due to the computational complexity. In this article, we present branch-and-cut and policy-based branch-and-bound (PB-B&B) solution methods that leverage the decomposable structure of the problem and allow for the solution of MDPs that consider many models of the parameters. Numerical experiments show that a customized implementation of PB-B&B significantly outperforms the MIP-based solution methods and that the variance among model parameters can be an important factor in the value of solving these problems.