Faster saddle-point optimization for solving large-scale Markov decision processes

By Joan Bas-Serrano, Gergely Neu. 2019

14 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Ofir Nachum
2. Bo Dai
3. Sergey Levine
4. Lihong Li
5. Mengjiao Yang
6. Dale Schuurmans
7. George Tucker
8. Nan Jiang

In Management Science and Operations Research

1. Ofir Nachum
2. Bo Dai
3. Mengjiao Yang
4. Dale Schuurmans
5. Lihong Li
6. Nan Jiang
7. Sergey Levine
8. Masatoshi Uehara

Citations in the corpus

• Reinforcement Learning via Fenchel-Rockafellar Duality (2020, background): “Moreover, the bilinear nature of the Lagrangian can lead to instability or poor convergence in optimization (Dai et al., 2017; Bas-Serrano and Neu, 2019).”
• Off-Policy Evaluation via the Regularized Lagrangian (2020, background): “Another line of work, more similar to the present paper, is to optimize the Lagrangian of the linear program that characterizes the value function [2, 4, 29].”