Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning

Understand

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.