Continual Learning In Environments With Polynomial Mixing Times

By Matthew Riemer, Sharath Chandra Raparthy, Ignacio Cases, G. Subbaraj, Maximilian Puelma Touzel, Irina Rish. 2021

17 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “Moreover, the partially observable view puts emphasis on different aspects of the problem by focusing less on non-stationarity and more on related complications like non-Markovian observations and non-ergodic environments (or even ergodic environments with very high mixing times (Riemer et al., 2022”