On the convex formulations of robust Markov decision processes
Preprint
Abstract
Robust Markov decision processes (MDPs) are used for applications of dynamic optimization in uncertain environments and have been studied extensively. Many of the main properties and algorithms of MDPs, such as value iteration and policy iteration, extend directly to RMDPs. Surprisingly, there is no known analog of the MDP convex optimization formulation for solving RMDPs. This work describes the first convex optimization formulation of RMDPs under the classical sa-rectangularity and s-rectangularity assumptions. By using entropic regularization and exponential change of variables, we derive a convex formulation with a number of variables and constraints polynomial in the number of states and actions, but with large coefficients in the constraints. We further simplify the formulation for RMDPs with polyhedral, ellipsoidal, or entropy-based uncertainty sets, showing that, in these cases, RMDPs can be reformulated as conic programs based on exponential cones, quadratic cones, and non-negative orthants. Our work opens a new research direction for RMDPs and can serve as a first step toward obtaining a tractable convex formulation of RMDPs.Keywords
All Related Versions
This publication has 34 references indexed in Scilit:
- Policy mirror descent for reinforcement learning: linear convergence, new sampling complexity, and generalized problem classesMathematical Programming, 2022
- A primal-dual interior-point algorithm for nonsymmetric exponential-cone optimizationMathematical Programming, 2021
- A convex programming-based algorithm for mean payoff stochastic games with perfect informationOptimization Letters, 2017
- Relative entropy optimization and its applicationsMathematical Programming, 2016
- Entropic Value-at-Risk: A New Coherent Risk MeasureJournal of Optimization Theory and Applications, 2011
- Tractable approximate robust geometric programmingOptimization and Engineering, 2007
- A tutorial on geometric programmingOptimization and Engineering, 2007
- Convex measures of risk and trading constraintsFinance and Stochastics, 2002
- Robust solutions of Linear Programming problems contaminated with uncertain dataMathematical Programming, 2000
- Hidden convexity in some nonconvex quadratically constrained quadratic programmingMathematical Programming, 1996