Abstract
We present a reduction from reinforcement learning (RL) to no-regret onlinelearning based on the saddle-point formulation of RL, by which "any" onlinealgorithm with sublinear regret can generate policies with provable performanceguarantees. This new perspective decouples the RL problem into two parts:regret minimization and function approximation. The first part admits astandard online-learning analysis, and the second part can be quantifiedindependently of the learning algorithm. Therefore, the proposed reduction canbe used as a tool to systematically design new RL algorithms. We demonstratethis idea by devising a simple RL algorithm based on mirror descent and thegenerative-model oracle. For any $\gamma$-discounted tabular RL problem, withprobability at least $1-\delta$, it learns an $\epsilon$-optimal policy usingat most$\tilde{O}\left(\frac{|\mathcal{S}||\mathcal{A}|\log(\frac{1}{\delta})}{(1-\gamma)^4\epsilon^2}\right)$samples. Furthermore, this algorithm admits a direct extension to linearlyparameterized function approximators for large-scale applications, withcomputation and sample complexities independent of$|\mathcal{S}|$,$|\mathcal{A}|$, though at the cost of potential approximationbias.