Faster saddle-point optimization for solving large-scale Markov decision processes
This work addresses scalability challenges in solving large-scale Markov decision processes, which is important for applications in reinforcement learning and operations research, though it appears incremental as it builds on existing relaxed formulations.
The paper tackles the problem of computing optimal policies in average-reward Markov decision processes by analyzing a linearly relaxed saddle-point formulation, achieving fast convergence rates independent of state space size and identifying issues in prior work.
We consider the problem of computing optimal policies in average-reward Markov decision processes. This classical problem can be formulated as a linear program directly amenable to saddle-point optimization methods, albeit with a number of variables that is linear in the number of states. To address this issue, recent work has considered a linearly relaxed version of the resulting saddle-point problem. Our work aims at achieving a better understanding of this relaxed optimization problem by characterizing the conditions necessary for convergence to the optimal policy, and designing an optimization algorithm enjoying fast convergence rates that are independent of the size of the state space. Notably, our characterization points out some potential issues with previous work.