Timezone: »
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 that suffer from myopic bias and stale bootstrapped estimates. To validate the proposed theory, we study the empirical scaling behavior of mixing times with respect to the number of tasks and task switching frequency for pretrained high performing policies on seven 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.
Author Information
Matthew Riemer (IBM Research)
Sharath Chandra Raparthy (Meta)
Ignacio Cases (Stanford)
Gopeshh Subbaraj (MILA)
Maximilian Puelma Touzel (Universite de Montreal)
Irina Rish (Mila/UdeM/LAION)
More from the Same Authors
-
2021 Spotlight: Invariance Principle Meets Information Bottleneck for Out-of-Distribution Generalization »
Kartik Ahuja · Ethan Caballero · Dinghuai Zhang · Jean-Christophe Gagnon-Audet · Yoshua Bengio · Ioannis Mitliagkas · Irina Rish -
2022 : Learning in Factored Domains with Information-Constrained Visual Representations »
Tyler Malloy · Chris Sims · Tim Klinger · Matthew Riemer · Miao Liu · Gerald Tesauro -
2022 : Multi-Objective GFlowNets »
Moksh Jain · Sharath Chandra Raparthy · Alex Hernandez-Garcia · Jarrid Rector-Brooks · Yoshua Bengio · Santiago Miret · Emmanuel Bengio -
2022 Poster: Influencing Long-Term Behavior in Multiagent Reinforcement Learning »
Dong-Ki Kim · Matthew Riemer · Miao Liu · Jakob Foerster · Michael Everett · Chuangchuang Sun · Gerald Tesauro · Jonathan How -
2021 : Continual Learning In Environments With Polynomial Mixing Times »
Matthew Riemer · Sharath Chandra Raparthy · Ignacio Cases · Gopeshh Subbaraj · Maximilian Puelma Touzel · Irina Rish -
2021 : Live Panel »
Max Welling · Bharath Ramsundar · Irina Rish · Karianne J Bergen · Pushmeet Kohli -
2021 Poster: Adversarial Feature Desensitization »
Pouya Bashivan · Reza Bayat · Adam Ibrahim · Kartik Ahuja · Mojtaba Faramarzi · Touraj Laleh · Blake Richards · Irina Rish -
2021 Poster: Invariance Principle Meets Information Bottleneck for Out-of-Distribution Generalization »
Kartik Ahuja · Ethan Caballero · Dinghuai Zhang · Jean-Christophe Gagnon-Audet · Yoshua Bengio · Ioannis Mitliagkas · Irina Rish -
2019 : Poster Session »
Pravish Sainath · Mohamed Akrout · Charles Delahunt · Nathan Kutz · Guangyu Robert Yang · Joseph Marino · L F Abbott · Nicolas Vecoven · Damien Ernst · andrew warrington · Michael Kagan · Kyunghyun Cho · Kameron Harris · Leopold Grinberg · John J. Hopfield · Dmitry Krotov · Taliah Muhammad · Erick Cobos · Edgar Walker · Jacob Reimer · Andreas Tolias · Alexander Ecker · Janaki Sheth · Yu Zhang · Maciej Wołczyk · Jacek Tabor · Szymon Maszke · Roman Pogodin · Dane Corneil · Wulfram Gerstner · Baihan Lin · Guillermo Cecchi · Jenna M Reinen · Irina Rish · Guillaume Bellec · Darjan Salaj · Anand Subramoney · Wolfgang Maass · Yueqi Wang · Ari Pakman · Jin Hyung Lee · Liam Paninski · Bryan Tripp · Colin Graber · Alex Schwing · Luke Prince · Gabriel Ocker · Michael Buice · Benjamin Lansdell · Konrad Kording · Jack Lindsey · Terrence Sejnowski · Matthew Farrell · Eric Shea-Brown · Nicolas Farrugia · Victor Nepveu · Jiwoong Im · Kristin Branson · Brian Hu · Ramakrishnan Iyer · Stefan Mihalas · Sneha Aenugu · Hananel Hazan · Sihui Dai · Tan Nguyen · Doris Tsao · Richard Baraniuk · Anima Anandkumar · Hidenori Tanaka · Aran Nayebi · Stephen Baccus · Surya Ganguli · Dean Pospisil · Eilif Muller · Jeffrey S Cheng · Gaël Varoquaux · Kamalaker Dadi · Dimitrios C Gklezakos · Rajesh PN Rao · Anand Louis · Christos Papadimitriou · Santosh Vempala · Naganand Yadati · Daniel Zdeblick · Daniela M Witten · Nicholas Roberts · Vinay Prabhu · Pierre Bellec · Poornima Ramesh · Jakob H Macke · Santiago Cadena · Guillaume Bellec · Franz Scherr · Owen Marschall · Robert Kim · Hannes Rapp · Marcio Fonseca · Oliver Armitage · Jiwoong Im · Thomas Hardcastle · Abhishek Sharma · Wyeth Bair · Adrian Valente · Shane Shang · Merav Stern · Rutuja Patil · Peter Wang · Sruthi Gorantla · Peter Stratton · Tristan Edwards · Jialin Lu · Martin Ester · Yurii Vlasov · Siavash Golkar -
2019 : Coffee Break & Poster Session »
Samia Mohinta · Andrea Agostinelli · Alexandra Moringen · Jee Hang Lee · Yat Long Lo · Wolfgang Maass · Blue Sheffer · Colin Bredenberg · Benjamin Eysenbach · Liyu Xia · Efstratios Markou · Jan Lichtenberg · Pierre Richemond · Tony Zhang · JB Lanier · Baihan Lin · William Fedus · Glen Berseth · Marta Sarrico · Matthew Crosby · Stephen McAleer · Sina Ghiassian · Franz Scherr · Guillaume Bellec · Darjan Salaj · Arinbjörn Kolbeinsson · Matthew Rosenberg · Jaehoon Shin · Sang Wan Lee · Guillermo Cecchi · Irina Rish · Elias Hajek -
2018 Poster: Learning Abstract Options »
Matthew Riemer · Miao Liu · Gerald Tesauro -
2016 Workshop: Representation Learning in Artificial and Biological Neural Networks »
Leila Wehbe · Marcel Van Gerven · Moritz Grosse-Wentrup · Irina Rish · Brian Murphy · Georg Langs · Guillermo Cecchi · Anwar O Nunez-Elizalde -
2016 Invited Talk: Learning About the Brain: Neuroimaging and Beyond »
Irina Rish -
2015 Workshop: Machine Learning and Interpretation in Neuroimaging (day 1) »
Irina Rish · Leila Wehbe · Brian Murphy · Georg Langs · Guillermo Cecchi · Moritz Grosse-Wentrup -
2014 Workshop: MLINI 2014 - 4th NIPS Workshop on Machine Learning and Interpretation in Neuroimaging: Beyond the Scanner »
Irina Rish · Georg Langs · Brian Murphy · Guillermo Cecchi · Kai-min K Chang · Leila Wehbe -
2013 Workshop: MLINI-13: Machine Learning and Interpretation in Neuroimaging (Day 2) »
Georg Langs · Brian Murphy · Kai-min K Chang · Paolo Avesani · James Haxby · Nikolaus Kriegeskorte · Susan Whitfield-Gabrieli · Irina Rish · Guillermo Cecchi · Raif Rustamov · Marius Kloft · Jonathan Young · Sina Ghiassian · Michael Coen -
2013 Workshop: MLINI-13: Machine Learning and Interpretation in Neuroimaging (Day 1) »
Georg Langs · Brian Murphy · Kai-min K Chang · Paolo Avesani · James Haxby · Nikolaus Kriegeskorte · Susan Whitfield-Gabrieli · Irina Rish · Guillermo Cecchi · Raif Rustamov · Marius Kloft · Jonathan Young · Sina Ghiassian · Michael Coen -
2012 Workshop: MLINI - 2nd NIPS Workshop on Machine Learning and Interpretation in Neuroimaging (2 day) »
Georg Langs · Irina Rish · Guillermo Cecchi · Brian Murphy · Bjoern Menze · Kai-min K Chang · Moritz Grosse-Wentrup -
2012 Workshop: MLINI - 2nd NIPS Workshop on Machine Learning and Interpretation in Neuroimaging (2 day) »
Georg Langs · Irina Rish · Guillermo Cecchi · Brian Murphy · Bjoern Menze · Kai-min K Chang · Moritz Grosse-Wentrup -
2011 Workshop: Machine Learning and Interpretation in Neuroimaging (MLINI-2011) »
Melissa K Carroll · Guillermo Cecchi · Kai-min K Chang · Moritz Grosse-Wentrup · James Haxby · Georg Langs · Anna Korhonen · Bjoern Menze · Brian Murphy · Janaina Mourao-Miranda · Vittorio Murino · Francisco Pereira · Irina Rish · Mert Sabuncu · Irina Simanova · Bertrand Thirion -
2010 Workshop: Practical Application of Sparse Modeling: Open Issues and New Directions »
Irina Rish · Alexandru Niculescu-Mizil · Guillermo Cecchi · Aurelie Lozano -
2010 Session: Spotlights Session 12 »
Irina Rish -
2010 Session: Oral Session 15 »
Irina Rish -
2009 Poster: Discriminative Network Models of Schizophrenia »
Guillermo Cecchi · Irina Rish · Benjamin Thyreau · Bertrand Thirion · Marion Plaze · Jean-Luc Martinot · Marie Laure Paillere-Martinot · Jean-Baptiste Poline -
2009 Oral: Discriminative Network Models of Schizophrenia »
Guillermo Cecchi · Irina Rish · Benjamin Thyreau · Bertrand Thirion · Marion Plaze · Jean-Luc Martinot · Marie Laure Paillere-Martinot · Jean-Baptiste Poline -
2008 Workshop: New Directions in Statistical Learning for Meaningful and Reproducible fMRI Analysis »
Melissa K Carroll · Irina Rish · Francisco Pereira · Guillermo Cecchi -
2006 Workshop: Novel Applications of Dimensionality Reduction »
John Blitzer · Rajarshi Das · Irina Rish · Kilian Q Weinberger