Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning

Yichen Chen, Mengdi Wang

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 minim…