# Provably Efficient Lifelong Reinforcement Learning with Linear Function Approximation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 35 references that are in the map.
- First posted on arXiv 1 Jun 2022.

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

- [Efficiently Identifying Task Groupings for Multi-Task Learning](https://mlsanity.com/paper/2109.04617/) (2021)
- [Contextual Markov Decision Processes](https://mlsanity.com/paper/1502.02259/) (2015)
- [Multi-Task Reinforcement Learning with Context-based Representations](https://mlsanity.com/paper/2102.06177/) (2021)
- [Multi-Task Reinforcement Learning with Soft Modularization](https://mlsanity.com/paper/2003.13661/) (2020)
- [Multi-task Deep Reinforcement Learning with PopArt](https://mlsanity.com/paper/1809.04474/) (2018)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Dynamic Weights in Multi-Objective Deep Reinforcement Learning](https://mlsanity.com/paper/1809.07803/) (2018)
- [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (2020)
- [Sample Complexity of Multi-task Reinforcement Learning](https://mlsanity.com/paper/1309.6821/) (2013)
- [Markov Decision Processes with Continuous Side Information](https://mlsanity.com/paper/1711.05726/) (2017)
- [A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost](https://mlsanity.com/paper/2101.00494/) (2021)
- [From Machine Learning to Robotics: Challenges and Opportunities for Embodied Intelligence](https://mlsanity.com/paper/2110.15245/) (2021)
- [Lifelong Robotic Reinforcement Learning by Retaining Experiences](https://mlsanity.com/paper/2109.09180/) (2021)
- [Lipschitz Lifelong Reinforcement Learning](https://mlsanity.com/paper/2001.05411/) (2020)
- [Provably Efficient Multi-Task Reinforcement Learning with Model Transfer](https://mlsanity.com/paper/2107.08622/) (2021)
- [Safe Policy Search for Lifelong Reinforcement Learning with Sublinear Regret](https://mlsanity.com/paper/1505.05798/) (2015)
- [Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2011.13034/) (2020)
- [Learning Efficiently Function Approximation for Contextual MDP](https://mlsanity.com/paper/2203.00995/) (2022)
- [Online learning in MDPs with side information](https://mlsanity.com/paper/1406.6812/) (2014)
- [TempLe: Learning Template of Transitions for Sample Efficient Multi-task RL](https://mlsanity.com/paper/2002.06659/) (2020)
- [Continuous Control with Contexts, Provably](https://mlsanity.com/paper/1910.13614/) (2019)

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

- [Sample Complexity Characterization for Linear Contextual MDPs](https://mlsanity.com/paper/2402.02700/) (2024)
- [Driving Beyond Privilege: Distilling Dense-Reward Knowledge into Sparse-Reward Policies](https://mlsanity.com/paper/2512.04279/) (2025)

## Abstract (arXiv)

We study lifelong reinforcement learning (RL) in a regret minimization setting of linear contextual Markov decision process (MDP), where the agent needs to learn a multi-task policy while solving a streaming sequence of tasks. We propose an algorithm, called UCB Lifelong Value Distillation (UCBlvd), that provably achieves sublinear regret for any sequence of tasks, which may be adaptively chosen based on the agent's past behaviors. Remarkably, our algorithm uses only sublinear number of planning calls, which means that the agent eventually learns a policy that is near optimal for multiple tasks (seen or unseen) without the need of deliberate planning. A key to this property is a new structural assumption that enables computation sharing across tasks during exploration. Specifically, for K task episodes of horizon H, our algorithm has a regret bound tildeO(√(d3+d^prime d)H4K) based on O(dHlog(K)) number of planning calls, where d and d^prime are the feature dimensions of the dynamics and rewards, respectively. This theoretical guarantee implies that our algorithm can enable a lifelong learning agent to accumulate experiences and learn to rapidly solve new tasks.