Percentile optimization in uncertain Markov decision processes with application to efficient exploration

ABSTRACT

Markov decision processes are an effective tool in modeling decision-making in uncertain dynamic environments. Since the parameters of these models are typically estimated from data, learned from experience, or designed by hand, it is not surprising that the actual performance of a chosen strategy often significantly differs from the designer's initial expectations due to unavoidable model uncertainty. In this paper, we present a percentile criterion that captures the trade-off between optimistic and pessimistic points of view on MDP with parameter uncertainty. We describe tractable methods that take parameter uncertainty into account in the process of decision making. Finally, we propose a cost-effective exploration strategy when it is possible to invest (money, time or computation efforts) in actions that will reduce the uncertainty in the parameters.

REFERENCES

• 1: A. Ben-Tal , A. Nemirovski, Robust Convex Optimization, Mathematics of Operations Research, v.23 n.4, p.769-805, Nov. 1998 [doi>10.1287/moor.23.4.769]
• 2: Ronen I. Brafman , Moshe Tennenholtz, R-max - a general polynomial time algorithm for near-optimal reinforcement learning, The Journal of Machine Learning Research, 3, p.213-231, 3/1/2003 [doi>10.1162/153244303765208377]
• 3: Calafiore, G., & El Ghaoui, L. (2006). On distributionally robust chance-constrained linear programs. Optimization Theory and Applications, 130, 1--22.
• 4: Charnes, A., & Cooper, W. (1959). Chance constrained programming. Management Science, 6, 73--79.
• 5: Dearden, R., Friedman, N., & Andre, D. (1999). Model-based Bayesian exploration. Proc. of Uncertainty in AI (pp. 150--159).
• 6: Filar, J., Krass, D., & Ross, K. (1995). Percentile performance criteria for limiting average Markov control problems. IEEE Trans. on Automatic Control, 40, 2--10.
• 7: Gelman, A., Carlin, J., Stern, H., & Rubin, D. (2003). Bayesian data analysis, second edition. Chapman & Hall/CRC.
• 8: Robert Givan , Sonia Leach , Thomas Dean, Bounded-parameter Markov decision process, Artificial Intelligence, v.122 n.1-2, p.71-109, Sept., 2000 [doi>10.1016/S0004-3702(00)00047-3]
• 9: Howard, R. (1966). Information value theory. IEEE Trans. on Systems Science and Cybernetics, SSC-2, 22--26.
• 10: Garud N. Iyengar, Robust Dynamic Programming, Mathematics of Operations Research, v.30 n.2, p.257-280, May 2005 [doi>10.1287/moor.1040.0129]
• 11: Michael J. Kearns , Satinder P. Singh, Near-Optimal Reinforcement Learning in Polynominal Time, Proceedings of the Fifteenth International Conference on Machine Learning, p.260-268, July 24-27, 1998
• 12: Lobo, M., Vandenberghe, L., Boyd, S., & Lebret, H. (1998). Applications of second order cone programming. Linear Algebra and its App., 284, 193--228.
• 13: Shie Mannor , Duncan Simester , Peng Sun , John N. Tsitsiklis, Bias and Variance Approximation in Value Function Estimates, Management Science, v.53 n.2, p.308-322, February 2007 [doi>10.1287/mnsc.1060.0614]
• 14: Nemirovski, A., & Shapiro, A. (2006). Convex approximations of chance constrained programs. SIAM Journal on Optimization, 17, 969--996.
• 15: Arnab Nilim , Laurent El Ghaoui, Robust Control of Markov Decision Processes with Uncertain Transition Matrices, Operations Research, v.53 n.5, p.780-798, September-October 2005 [doi>10.1287/opre.1050.0216]
• 16: Prékopa, A. (1995). Stochastic programming. Kluwer Academic Publishers.
• 17: Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, Inc., New York, NY, 1994
• 18: Silver, E. (1963). Markovian decision processes with uncertain transition probabilities or rewards (Technical Report 1). Operations Research Center, MIT.
• 19: Alexander L. Strehl , Michael L. Littman, A theoretical analysis of Model-Based Interval Estimation, Proceedings of the 22nd international conference on Machine learning, p.856-863, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102459]