# Understanding the Complexity Gains of Single-Task RL with a Curriculum

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 81 of its 107 references that are in the map.
- First posted on arXiv 24 Dec 2022.

## Builds on (most cited first, 30 of 81)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [D4RL: Datasets for Deep Data-Driven Reinforcement Learning](https://mlsanity.com/paper/2004.07219/) (2020)
- [Gradient Surgery for Multi-Task Learning](https://mlsanity.com/paper/2001.06782/) (2020)
- [Soft Actor-Critic Algorithms and Applications](https://mlsanity.com/paper/1812.05905/) (2018)
- [Meta-World: A Benchmark and Evaluation for Multi-Task and Meta Reinforcement Learning](https://mlsanity.com/paper/1910.10897/) (2019)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [Solving Rubik's Cube with a Robot Hand](https://mlsanity.com/paper/1910.07113/) (2019)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Policy Distillation](https://mlsanity.com/paper/1511.06295/) (2015)
- [Curriculum Learning for Reinforcement Learning Domains: A Framework and Survey](https://mlsanity.com/paper/2003.04960/) (2020)
- [#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.04717/) (2016)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Emergent Complexity and Zero-shot Transfer via Unsupervised Environment Design](https://mlsanity.com/paper/2012.02096/) (2020)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Automatic Goal Generation for Reinforcement Learning Agents](https://mlsanity.com/paper/1705.06366/) (2017)
- [Visual Reinforcement Learning with Imagined Goals](https://mlsanity.com/paper/1807.04742/) (2018)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [MT-Opt: Continuous Multi-Task Robotic Reinforcement Learning at Scale](https://mlsanity.com/paper/2104.08212/) (2021)
- [Contextual Markov Decision Processes](https://mlsanity.com/paper/1502.02259/) (2015)
- [Go-Explore: a New Approach for Hard-Exploration Problems](https://mlsanity.com/paper/1901.10995/) (2019)
- [Modular Multitask Reinforcement Learning with Policy Sketches](https://mlsanity.com/paper/1611.01796/) (2016)
- [Reverse Curriculum Generation for Reinforcement Learning](https://mlsanity.com/paper/1707.05300/) (2017)
- [Bridging the Gap Between Value and Policy Based Reinforcement Learning](https://mlsanity.com/paper/1702.08892/) (2017)

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

- [Cal-QL: Calibrated Offline RL Pre-Training for Efficient Online Fine-Tuning](https://mlsanity.com/paper/2303.05479/) (2023)
- [General In-Hand Object Rotation with Vision and Touch](https://mlsanity.com/paper/2309.09979/) (2023)
- [e3: Learning to Explore Enables Extrapolation of Test-Time Compute for LLMs](https://mlsanity.com/paper/2506.09026/) (2025)
- [RLIF: Interactive Imitation Learning as Reinforcement Learning](https://mlsanity.com/paper/2311.12996/) (2023)
- [Accelerating Exploration with Unlabeled Prior Data](https://mlsanity.com/paper/2311.05067/) (2023)
- [Leveraging Skills from Unlabeled Prior Data for Efficient Online Exploration](https://mlsanity.com/paper/2410.18076/) (2024)
- [Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Data](https://mlsanity.com/paper/2411.03810/) (2024)
- [RICE: Breaking Through the Training Bottlenecks of Reinforcement Learning with Explanation](https://mlsanity.com/paper/2405.03064/) (2024)
- [Low-Switching Policy Gradient with Exploration via Online Sensitivity Sampling](https://mlsanity.com/paper/2306.09554/) (2023)
- [On the Benefit of Optimal Transport for Curriculum Reinforcement Learning](https://mlsanity.com/paper/2309.14091/) (2023)
- [From Trainee to Trainer: LLM-Designed Training Environment for RL with Multi-Agent Reasoning](https://mlsanity.com/paper/2606.17682/) (2026)
- [Sample Efficient Myopic Exploration Through Multitask Reinforcement Learning with Diverse Tasks](https://mlsanity.com/paper/2403.01636/) (2024)
- [Quantifying Assistive Robustness Via the Natural-Adversarial Frontier](https://mlsanity.com/paper/2310.10610/) (2023)
- [A Unified Algorithmic Framework for Hybrid Reinforcement Learning in Tabular MDPs with Shifted Transition Dynamics](https://mlsanity.com/paper/2607.25207/) (2026)
- [TEACH: Temporal Variance-Driven Curriculum for Reinforcement Learning](https://mlsanity.com/paper/2512.22824/) (2025)
- [Self Paced Gaussian Contextual Reinforcement Learning](https://mlsanity.com/paper/2603.23755/) (2026)
- [Curriculum reinforcement learning with measurable task representation learning](https://mlsanity.com/paper/2605.23372/) (2026)

## Abstract (arXiv)

Reinforcement learning (RL) problems can be challenging without well-shaped rewards. Prior work on provably efficient RL methods generally proposes to address this issue with dedicated exploration strategies. However, another way to tackle this challenge is to reformulate it as a multi-task RL problem, where the task space contains not only the challenging task of interest but also easier tasks that implicitly function as a curriculum. Such a reformulation opens up the possibility of running existing multi-task RL methods as a more efficient alternative to solving a single challenging task from scratch. In this work, we provide a theoretical framework that reformulates a single-task RL problem as a multi-task RL problem defined by a curriculum. Under mild regularity conditions on the curriculum, we show that sequentially solving each task in the multi-task RL problem is more computationally efficient than solving the original single-task problem, without any explicit exploration bonuses or other exploration strategies. We also show that our theoretical insights can be translated into an effective practical learning algorithm that can accelerate curriculum learning on simulated robotic tasks.