Strongly polynomial linear programming solves robust decision problems
Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes
Machine LearningData Structures and Algorithms
Summary
Making decisions when some information is uncertain is hard, especially if you want your choices to stay good even in the worst-case scenarios. The authors study a type of decision problem called robust Markov decision processes, which handle uncertain rewards and outcomes. They show how to represent these problems using one big linear program that can be solved efficiently in polynomial time, meaning the time needed grows reasonably with problem size. This helps find the best strategies robustly, even in complex uncertainty settings.
What this means in practice
- •For operations research analysts: Solve complex decision-making problems robustly when facing uncertain costs or transitions with guaranteed polynomial-time performance.
- •For financial risk managers: Improve modeling of uncertain market behaviors by efficiently finding robust strategies under interval or Wasserstein uncertainty.
A theory result. No direct application yet.
Authors
Han Zhong, Yinyu Ye
Abstract
We study linear programming (LP) representations and strongly polynomial algorithms for robust Markov decision processes (RMDPs) with rational polyhedral state-action rectangular uncertainty in rewards and transitions. By encoding a finite sequence of robust policy-iteration steps, we construct a single LP whose optimal solutions recover the robust optimal value and all optimal stationary randomized policies. At fixed discount, the LP has polynomial dimension and encoding length and can be constructed in strongly polynomial time. We also develop a general complexity analysis of robust policy iteration that combines the cost of minimizing over uncertainty sets with the number of iterations needed to evaluate a policy. For a fixed discount factor, we use this analysis to improve the known complexity bounds for $\ell_1$ and $\ell_\infty$ RMDPs and establish new strongly polynomial bounds for general interval, weighted $\ell_1$, and Wasserstein RMDPs, as well as turn-based stochastic games with these uncertainty sets.