Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems

By Mengdi Wang. 2017

76 citations recorded by the source corpus.

Consider the problem of approximating the optimal policy of a Markov decision process (MDP) by sampling state transitions. In contrast to existing reinforcement learning methods that are based on successive approximations to the nonlinear Bellman equation, we propose a Primal-Dual $\pi$ Learning method in light of the linear duality between the value and policy. The $\pi$ learning method is model-free and makes primal-dual updates to the policy and value vectors as new data are revealed. For infinite-horizon undiscounted Markov decision process with finite state space $S$ and finite action space $A$, the $\pi$ learning method finds an $\epsilon$-optimal policy using the following number of sample transitions $$ \tilde{O}( \frac{(\tau\cdot t^*_{mix})^2 |S| |A| }{\epsilon^2} ),$$ where $t^*_{mix}$ is an upper bound of mixing times across all policies and $\tau$ is a parameter characterizing the range of stationary distributions across policies. The $\pi$ learning method also applies to the computational problem of MDP where the transition probabilities and rewards are explicitly given as the input. In the case where each state transition can be sampled in $\tilde{O}(1)$ time, the $\pi$ learning method gives a sublinear-time algorithm for solving the averaged-reward MDP.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, 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. Lihong Li
2. Mengdi Wang
3. Zhuoran Yang
4. Joan Bas-Serrano
5. Yihao Feng
6. Gergely Neu
7. Qiang Liu
8. Kaiqing Zhang

In Computational Theory and Mathematics

1. Lihong Li
2. Joan Bas-Serrano
3. Zhuoran Yang
4. Kaiqing Zhang
5. Tamer Basar
6. Gergely Neu
7. Yichen Chen
8. Qiang Liu

In Management Science and Operations Research

1. Lihong Li
2. Mengdi Wang
3. Zhuoran Yang
4. Gergely Neu
5. Joan Bas-Serrano
6. Qiang Liu
7. Yichen Chen
8. Kaiqing Zhang

Citations in the corpus

• A Kernel Loss for Solving the Bellman Equation (2019, background): “Note that there exist other saddle-point formulations for RL, which so far have focused on finite-state MDPs or linear value function approximation (Chen et al., 2018; Wang, 2017).”
• Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, methodology): “Besides the value- and policy-based methods, there also exist RL algorithms based on the linear program formulation of an MDP; see recent efforts in [80, 81].”
• Faster saddle-point optimization for solving large-scale Markov decision processes (2019, methodology): “Then, v ∗ satisfies the following properties: All of these properties can be proven by standard arguments; we refer the reader to Lemma 1 in Wang (2017) for a proof of the first item and Lemma 3 in Neu et al. (2014) for a proof of the second one.”
• Scalable Bilinear π Learning Using State and Action Features (2018, methodology): “The proofs of Lemma 1 and 2 are deferred to the appendix.”