Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning
This work addresses the sample complexity challenge in reinforcement learning for researchers and practitioners, offering a novel method with specific gains.
The paper tackles the problem of online estimation of optimal policies in Markov decision processes by proposing Stochastic Primal-Dual (SPD) methods, achieving an absolute-ε-optimal policy with high probability using sample complexities of O(|S|^4|A|^2σ^2/((1-γ)^6ε^2)) for infinite-horizon and O(|S|^4|A|^2H^6σ^2/ε^2) for finite-horizon MDPs.
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 $\mathcal{O}\left(\frac{|\mathcal{S}|^4 |\mathcal{A}|^2σ^2 }{(1-γ)^6ε^2} \right)$ iterations/samples for the infinite-horizon discounted-reward MDP and $\mathcal{O}\left(\frac{|\mathcal{S}|^4 |\mathcal{A}|^2H^6σ^2 }{ε^2} \right)$ for the finite-horizon MDP.