Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time

By Mengdi Wang. 2017

26 citations recorded by the source corpus.

We propose a novel randomized linear programming algorithm for approximating the optimal policy of the discounted Markov decision problem. By leveraging the value-policy duality and binary-tree data structures, the algorithm adaptively samples state-action-state transitions and makes exponentiated primal-dual updates. We show that it finds an $\epsilon$-optimal policy using nearly-linear run time in the worst case. When the Markov decision process is ergodic and specified in some special data formats, the algorithm finds an $\epsilon$-optimal policy using run time linear in the total number of state-action pairs, which is sublinear in the input size. These results provide a new venue and complexity benchmarks for solving stochastic dynamic programs.

Subfields: Artificial Intelligence, Computer Networks and Communications, 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 Computer Networks and Communications

1. Bo Dai
2. Ofir Nachum
3. Dale Schuurmans
4. Mengjiao Yang
5. Lihong Li

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): “…for its potential ability to circumvent the optimization challenges of DP-based approaches in exchange for more mature and well-studied techniques associated with convex optimization (De Farias and Van Roy, 2003; Wang et al., 2007; Chen and Wang, 2016; Wang, 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].”