Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning

Abstract

We study the online estimation of the optimal policy of a Markov decision process (MDP). We propose a class of Stochastic Primal-Dual (SPD) methods which exploit the inherent minimax duality of Bellman equations. The SPD methods update a few coordinates of the value and policy estimates as a new state transition is observed. These methods use small storage and has low computational complexity per iteration. The SPD methods find an absolute--optimal policy, with high probability, using O(|S|^4 |A|^2^2 (1-)^6^2 ) iterations/samples for the infinite-horizon discounted-reward MDP and O(|S|^4 |A|^2H^6^2 ^2 ) for the finite-horizon MDP.

Tasks

Reproductions