# Provable Reset-free Reinforcement Learning by No-Regret Reduction

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 40 references that are in the map.
- First posted on arXiv 6 Jan 2023.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [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)
- [Safe Reinforcement Learning via Shielding](https://mlsanity.com/paper/1708.08611/) (2017)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [Safe Reinforcement Learning in Constrained Markov Decision Processes](https://mlsanity.com/paper/2008.06626/) (2020)
- [Learning to Walk in the Real World with Minimal Human Effort](https://mlsanity.com/paper/2002.08550/) (2020)
- [Reset-Free Reinforcement Learning via Multi-Task Learning: Learning Dexterous Manipulation Behaviors without Human Intervention](https://mlsanity.com/paper/2104.11203/) (2021)
- [Leave no Trace: Learning to Reset for Safe and Autonomous Reinforcement Learning](https://mlsanity.com/paper/1711.06782/) (2017)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP](https://mlsanity.com/paper/1901.09311/) (2019)
- [Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2007.11849/) (2020)
- [Safe Reinforcement Learning Using Advantage-Based Intervention](https://mlsanity.com/paper/2106.09110/) (2021)
- [Constrained Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2001.09377/) (2020)
- [Heuristic-Guided Reinforcement Learning](https://mlsanity.com/paper/2106.02757/) (2021)
- [Reset-Free Lifelong Learning with Skill-Space Planning](https://mlsanity.com/paper/2012.03548/) (2020)
- [Safe Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2106.06239/) (2021)
- [Improved Algorithms for Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2006.06359/) (2020)
- [Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs](https://mlsanity.com/paper/2008.00311/) (2020)
- [Provably Efficient Model-Free Constrained RL with Linear Function Approximation](https://mlsanity.com/paper/2206.11889/) (2022)
- [A State-Distribution Matching Approach to Non-Episodic Reinforcement Learning](https://mlsanity.com/paper/2205.05212/) (2022)
- [No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization](https://mlsanity.com/paper/2111.11309/) (2021)
- [The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2205.05653/) (2022)
- [A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2106.01577/) (2021)
- [Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RL](https://mlsanity.com/paper/2206.14057/) (2022)
- [Towards Painless Policy Optimization for Constrained MDPs](https://mlsanity.com/paper/2204.05176/) (2022)

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

- [Survival Instinct in Offline Reinforcement Learning](https://mlsanity.com/paper/2306.03286/) (2023)
- [SafeMimic: Towards Safe and Autonomous Human-to-Robot Imitation for Mobile Manipulation](https://mlsanity.com/paper/2506.15847/) (2025)
- [Harmonic Control Lyapunov Barrier Functions for Constrained Optimal Control with Reach-Avoid Specifications](https://mlsanity.com/paper/2310.02869/) (2023)

## Abstract (arXiv)

Reinforcement learning (RL) so far has limited real-world applications. One key challenge is that typical RL algorithms heavily rely on a reset mechanism to sample proper initial states; these reset mechanisms, in practice, are expensive to implement due to the need for human intervention or heavily engineered environments. To make learning more practical, we propose a generic no-regret reduction to systematically design reset-free RL algorithms. Our reduction turns the reset-free RL problem into a two-player game. We show that achieving sublinear regret in this two-player game would imply learning a policy that has both sublinear performance regret and sublinear total number of resets in the original RL problem. This means that the agent eventually learns to perform optimally and avoid resets. To demonstrate the effectiveness of this reduction, we design an instantiation for linear Markov decision processes, which is the first provably correct reset-free RL algorithm.