# Continual Learning In Environments With Polynomial Mixing Times

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 86 references that are in the map.
- First posted on arXiv 13 Dec 2021.

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

- [Overcoming catastrophic forgetting in neural networks](https://mlsanity.com/paper/1612.00796/) (2016)
- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Progressive Neural Networks](https://mlsanity.com/paper/1606.04671/) (2016)
- [Experience Replay for Continual Learning](https://mlsanity.com/paper/1811.11682/) (2018)
- [When to Trust Your Model: Model-Based Policy Optimization](https://mlsanity.com/paper/1906.08253/) (2019)
- [Learning to Learn without Forgetting by Maximizing Transfer and Minimizing Interference](https://mlsanity.com/paper/1810.11910/) (2018)
- [Progress & Compress: A scalable framework for continual learning](https://mlsanity.com/paper/1805.06370/) (2018)
- [The Option-Critic Architecture](https://mlsanity.com/paper/1609.05140/) (2016)
- [Towards Continual Reinforcement Learning: A Review and Perspectives](https://mlsanity.com/paper/2012.13490/) (2020)
- [DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections](https://mlsanity.com/paper/1906.04733/) (2019)
- [Selective Experience Replay for Lifelong Learning](https://mlsanity.com/paper/1802.10269/) (2018)
- [Learning with Opponent-Learning Awareness](https://mlsanity.com/paper/1709.04326/) (2017)
- [VariBAD: A Very Good Method for Bayes-Adaptive Deep RL via Meta-Learning](https://mlsanity.com/paper/1910.08348/) (2019)
- [AlgaeDICE: Policy Gradient from Arbitrary Experience](https://mlsanity.com/paper/1912.02074/) (2019)
- [Continuous Adaptation via Meta-Learning in Nonstationary and Competitive Environments](https://mlsanity.com/paper/1710.03641/) (2017)
- [Reinforcement Learning via Fenchel-Rockafellar Duality](https://mlsanity.com/paper/2001.01866/) (2020)
- [Learning and Planning in Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2006.16318/) (2020)
- [Consistent On-Line Off-Policy Evaluation](https://mlsanity.com/paper/1702.07121/) (2017)
- [Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation](https://mlsanity.com/paper/1910.07186/) (2019)
- [Off-Policy Deep Reinforcement Learning by Bootstrapping the Covariate Shift](https://mlsanity.com/paper/1901.09455/) (2019)
- [Deep Reinforcement Learning amidst Lifelong Non-Stationarity](https://mlsanity.com/paper/2006.10701/) (2020)
- [Near-optimal Reinforcement Learning in Factored MDPs](https://mlsanity.com/paper/1403.3741/) (2014)
- [A Policy Gradient Algorithm for Learning to Learn in Multiagent Reinforcement Learning](https://mlsanity.com/paper/2011.00382/) (2020)
- [On Lower Bounds for Regret in Reinforcement Learning](https://mlsanity.com/paper/1608.02732/) (2016)
- [Is the Policy Gradient a Gradient?](https://mlsanity.com/paper/1906.07073/) (2019)
- [Optimizing for the Future in Non-Stationary MDPs](https://mlsanity.com/paper/2005.08158/) (2020)
- [Non-Stationary Markov Decision Processes, a Worst-Case Approach using Model-Based Reinforcement Learning, Extended version](https://mlsanity.com/paper/1904.10090/) (2019)
- [Scalable Recollections for Continual Lifelong Learning](https://mlsanity.com/paper/1711.06761/) (2017)
- [Discounted Reinforcement Learning Is Not an Optimization Problem](https://mlsanity.com/paper/1910.02140/) (2019)
- [Organizing Experience: A Deeper Look at Replay Mechanisms for Sample-based Planning in Continuous State Domains](https://mlsanity.com/paper/1806.04624/) (2018)

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

- [A Definition of Continual Reinforcement Learning](https://mlsanity.com/paper/2307.11046/) (2023)
- [Position: Theory of Mind Benchmarks are Broken for Large Language Models](https://mlsanity.com/paper/2412.19726/) (2024)
- [Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic](https://mlsanity.com/paper/2301.12083/) (2023)
- [A Survey of Continual Reinforcement Learning](https://mlsanity.com/paper/2506.21872/) (2025)
- [Revisiting Replay and Gradient Alignment for Continual Pre-Training of Large Language Models](https://mlsanity.com/paper/2508.01908/) (2025)
- [Enabling Realtime Reinforcement Learning at Scale with Staggered Asynchronous Inference](https://mlsanity.com/paper/2412.14355/) (2024)
- [Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles](https://mlsanity.com/paper/2403.11925/) (2024)
- [R^3: On-device Real-Time Deep Reinforcement Learning for Autonomous Robotics](https://mlsanity.com/paper/2308.15039/) (2023)
- [Beyond Sliding Windows: Learning to Manage Memory in Non-Markovian Environments](https://mlsanity.com/paper/2512.19154/) (2025)
- [The Effectiveness of Approximate Regularized Replay for Efficient Supervised Fine-Tuning of Large Language Models](https://mlsanity.com/paper/2512.22337/) (2025)
- [QueryBandits for Hallucination Mitigation: Exploiting Semantic Features for No-Regret Rewriting](https://mlsanity.com/paper/2508.16697/) (2025)
- [Confidence-Controlled Exploration: Efficient Sparse-Reward Policy Learning for Robot Navigation](https://mlsanity.com/paper/2306.06192/) (2023)
- [No One Size Fits All: QueryBandits for Hallucination Mitigation](https://mlsanity.com/paper/2602.20332/) (2026)
- [TetraRL: A Self-Adaptive Runtime for On-Device Deep Reinforcement Learning Systems](https://mlsanity.com/paper/2606.13891/) (2026)

## Abstract (arXiv)

The mixing time of the Markov chain induced by a policy limits performance in real-world continual learning scenarios. Yet, the effect of mixing times on learning in continual reinforcement learning (RL) remains underexplored. In this paper, we characterize problems that are of long-term interest to the development of continual RL, which we call scalable MDPs, through the lens of mixing times. In particular, we theoretically establish that scalable MDPs have mixing times that scale polynomially with the size of the problem. We go on to demonstrate that polynomial mixing times present significant difficulties for existing approaches, which suffer from myopic bias and stale bootstrapped estimates. To validate our theory, we study the empirical scaling behavior of mixing times with respect to the number of tasks and task duration for high performing policies deployed across multiple Atari games. Our analysis demonstrates both that polynomial mixing times do emerge in practice and how their existence may lead to unstable learning behavior like catastrophic forgetting in continual learning settings.