A Reduction from Reinforcement Learning to NoRegret Online Learning
[edit]
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:35143524, 2020.
Abstract
We present a reduction from reinforcement learning (RL) to noregret online learning based on the saddlepoint formulation of RL, by which "any" online algorithm with sublinear regret can generate policies with provable performance guarantees. This new perspective decouples the RL problem into two parts: regret minimization and function approximation. The first part admits a standard onlinelearning analysis, and the second part can be quantified independently of the learning algorithm. Therefore, the proposed reduction can be used as a tool to systematically design new RL algorithms. We demonstrate this idea by devising a simple RL algorithm based on mirror descent and the generativemodel oracle. For any $\gamma$discounted tabular RL problem, with probability at least $1\delta$, it learns an $\epsilon$optimal policy using at most $\tilde{O}\left(\frac{\SSÅ\log(\frac{1}{\delta})}{(1\gamma)^4\epsilon^2}\right)$ samples. Furthermore, this algorithm admits a direct extension to linearly parameterized function approximators for largescale applications, with computation and sample complexities independent of $\SS$,$Å$, though at the cost of potential approximation bias.
Related Material


