Optimization Online


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

Mengdi Wang(mengdiw***at***princeton.edu)

Abstract: 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 π Learning method in light of the linear duality between the value and policy. The π 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 π learning method finds an ε-optimal policy using the following number of sample transitions O( (τ t∗mix)^2|S||A| / ε^2) , where t∗mix is an upper bound of mixing times across all policies and τ is a parameter character- izing the range of stationary distributions across policies. The π 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 O ̃(1) time, the π learning method gives a sublinear-time algorithm for solving the averaged-reward MDP.


Category 1: Other Topics (Dynamic Programming )


Download: [PDF]

Entry Submitted: 10/17/2017
Entry Accepted: 10/17/2017
Entry Last Modified: 10/17/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society