Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning

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|⁴ |A|²σ² /(1-γ)⁶ε² ) iterations/samples for the infinite-horizon discounted-reward MDP and O(|S|⁴ |A|²H⁶σ² /ε² ) for the finite-horizon MDP.