# A Reduction from Reinforcement Learning to No-Regret Online Learning

arXiv: https://arxiv.org/abs/1911.05873 · HTML: https://mlsanity.com/paper/1911.05873/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Nov 2019.

## Built on by (most cited first, 10 of 10)

- [Proximal Point Imitation Learning](https://mlsanity.com/paper/2209.10968/) (2022)
- [Dealing with unbounded gradients in stochastic saddle-point optimization](https://mlsanity.com/paper/2402.13903/) (2024)
- [Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrations](https://mlsanity.com/paper/2112.14004/) (2021)
- [Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization](https://mlsanity.com/paper/2210.12057/) (2022)
- [Continuous Online Learning and New Insights to Online Imitation Learning](https://mlsanity.com/paper/1912.01261/) (2019)
- [Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs](https://mlsanity.com/paper/2205.09056/) (2022)
- [Efficiently Solving Discounted MDPs with Predictions on Transition Matrices](https://mlsanity.com/paper/2502.15345/) (2025)
- [Near Optimal Policy Optimization via REPS](https://mlsanity.com/paper/2103.09756/) (2021)
- [Non-Markovian policies occupancy measures](https://mlsanity.com/paper/2205.13950/) (2022)
- [BET: Explaining Deep Reinforcement Learning through The Error-Prone Decisions](https://mlsanity.com/paper/2401.07263/) (2024)

## Abstract (arXiv)

We present a reduction from reinforcement learning (RL) to no-regret online learning based on the saddle-point 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 online-learning 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 generative-model oracle. For any γ-discounted tabular RL problem, with probability at least 1-δ, it learns an ε-optimal policy using at most tildeOleft(frac|S||A|log(frac1δ)(1-γ)4ε2right) samples. Furthermore, this algorithm admits a direct extension to linearly parameterized function approximators for large-scale applications, with computation and sample complexities independent of |S|,|A|, though at the cost of potential approximation bias.