# A Boosting Approach to Reinforcement Learning

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 47 references that are in the map.
- First posted on arXiv 22 Aug 2021.

## Builds on (most cited first, 18 of 18)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning](https://mlsanity.com/paper/2007.08459/) (2020)
- [Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization](https://mlsanity.com/paper/1804.09554/) (2018)
- [An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap](https://mlsanity.com/paper/2103.12690/) (2021)
- [Gradient Methods for Submodular Maximization](https://mlsanity.com/paper/1708.03949/) (2017)
- [Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity](https://mlsanity.com/paper/1802.08183/) (2018)
- [On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function](https://mlsanity.com/paper/2102.02049/) (2021)
- [Boosting Simple Learners](https://mlsanity.com/paper/2001.11704/) (2020)
- [Optimal and Adaptive Algorithms for Online Boosting](https://mlsanity.com/paper/1502.02651/) (2015)
- [Online Agnostic Boosting via Regret Minimization](https://mlsanity.com/paper/2003.01150/) (2020)
- [Boosting for Online Convex Optimization](https://mlsanity.com/paper/2102.09305/) (2021)
- [Online Boosting Algorithms for Multi-label Ranking](https://mlsanity.com/paper/1710.08079/) (2017)
- [Online Multiclass Boosting](https://mlsanity.com/paper/1702.07305/) (2017)
- [Boosting for Control of Dynamical Systems](https://mlsanity.com/paper/1906.08720/) (2019)
- [Online Boosting with Bandit Feedback](https://mlsanity.com/paper/2007.11975/) (2020)

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

- [When is Agnostic Reinforcement Learning Statistically Tractable?](https://mlsanity.com/paper/2310.06113/) (2023)
- [The Impossibility of Parallelizing Boosting](https://mlsanity.com/paper/2301.09627/) (2023)
- [Boosted Off-Policy Learning](https://mlsanity.com/paper/2208.01148/) (2022)
- [The Cost of Parallelizing Boosting](https://mlsanity.com/paper/2402.15145/) (2024)
- [Sample-Efficient Agnostic Boosting](https://mlsanity.com/paper/2410.23632/) (2024)
- [Sample-Optimal Agnostic Boosting with Unlabeled Data](https://mlsanity.com/paper/2503.04706/) (2025)
- [Understanding Curriculum Learning in Policy Optimization for Online Combinatorial Optimization](https://mlsanity.com/paper/2202.05423/) (2022)
- [Variance-Reduced Conservative Policy Iteration](https://mlsanity.com/paper/2212.06283/) (2022)
- [Oracle-Efficient Reinforcement Learning for Max Value Ensembles](https://mlsanity.com/paper/2405.16739/) (2024)
- [Gradient Boosting Reinforcement Learning](https://mlsanity.com/paper/2407.08250/) (2024)
- [Constructing Ancestral Recombination Graphs through Reinforcement Learning](https://mlsanity.com/paper/2406.12022/) (2024)
- [Upside-Down Reinforcement Learning for More Interpretable Optimal Control](https://mlsanity.com/paper/2411.11457/) (2024)

## Abstract (arXiv)

Reducing reinforcement learning to supervised learning is a well-studied and effective approach that leverages the benefits of compact function approximation to deal with large-scale Markov decision processes. Independently, the boosting methodology (e.g. AdaBoost) has proven to be indispensable in designing efficient and accurate classification algorithms by combining inaccurate rules-of-thumb. In this paper, we take a further step: we reduce reinforcement learning to a sequence of weak learning problems. Since weak learners perform only marginally better than random guesses, such subroutines constitute a weaker assumption than the availability of an accurate supervised learning oracle. We prove that the sample complexity and running time bounds of the proposed method do not explicitly depend on the number of states. While existing results on boosting operate on convex losses, the value function over policies is non-convex. We show how to use a non-convex variant of the Frank-Wolfe method for boosting, that additionally improves upon the known sample complexity and running time even for reductions to supervised learning.