Journal
IISE TRANSACTIONS
Volume 53, Issue 12, Pages 1295-1310Publisher
TAYLOR & FRANCIS INC
DOI: 10.1080/24725854.2020.1869351
Keywords
Markov decision processes; dynamic programming; parameter ambiguity; decomposition; stochastic programming
Funding
- National Science Foundation [DGE-1256260, CMMI-1462060]
Ask authors/readers for more resources
The article explores the issue of decision-making in MDPs with uncertain parameters and introduces new solution methods. Numerical experiments show that the customized implementation significantly outperforms traditional methods, and that the variance among model parameters can be a crucial factor in problem-solving value.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available