CHAPTER: INTRODUCTION

CHAPTER: BACKGROUND

State Abstraction

CHAPTER: APPROXIMATE STATE ABSTRACTION

CHAPTER: STATE ABSTRACTION IN LIFELONG RL

CHAPTER: STATE ABSTRACTION AS COMPRESSION

Action Abstraction

CHAPTER: FINDING OPTIONS THAT MINIMIZE PLANNING TIME

CHAPTER: THE EXPECTED-LENGTH MODEL OF OPTIONS

CHAPTER: DISCOVERING OPTIONS FOR EXPLORATION

State-Action Abstraction

CHAPTER: VALUE PRESERVING STATE-ACTION ABSTRACTIONS

CHAPTER: CONCLUSION

[Abbeel and Ng, 2004]
Pieter Abbeel and Andrew Y. Ng.
Apprenticeship Learning via Inverse Reinforcement Learning.
In Proceedings of the International Conference on Machine
learning, 2004.

[Abel, 2019]
David Abel.
Concepts in bounded rationality: Perspectives from reinforcement
Master's thesis, Brown University, 2019a.

[Abel, 2019]
David Abel.
A theory of state abstraction for reinforcement learning.
In Proceedings of the Doctoral Consortium of the AAAI
Conference on Artificial Intelligence, 2019b.

[Abel et al., 2016]
David Abel, D. Ellis Hershkowitz, and Michael L. Littman.
Near optimal behavior via approximate state abstraction.
In Proceedings of the International Conference on Machine
Learning, 2016.

[Abel et al., 2017]
David Abel, Dilip Arumugam, Lucas Lehnert, and Michael L. Littman.
Toward good abstractions for lifelong learning.
In NeurIPS Workshop on Hierarchical Reinforcement Learning,

[Abel et al., 2018]
David Abel, Dilip Arumugam, Lucas Lehnert, and Michael L. Littman.
State abstractions for lifelong reinforcement learning.
In Proceedings of the International Conference on Machine
Learning, 2018a.

[Abel et al., 2018]
David Abel, Yuu Jinnai, Yue Guo, George Konidaris, and Michael L. Littman.
Policy and value transfer in lifelong reinforcement learning.
In Proceedings of the International Conference on Machine
Learning, 2018b.

[Abel et al., 2018]
David Abel, Edward C. Willams, Stephen Brawner, Emily Reif, and Michael L.
Bandit-based solar panel control.
In Proceedings of the Conference on Innovative Applications of
Artificial Intelligence, 2018c.

[Abel et al., 2019]
David Abel, Dilip Arumugam, Kavosh Asadi, Yuu Jinnai, Michael L. Littman, and
Lawson L.S. Wong.
State abstraction as compression in apprenticeship learning.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2019a.

[Abel et al., 2019]
David Abel, John Winder, Marie desJardins, and Michael L. Littman.
The expected-length model of options.
In Proceedings of the International Joint Conference on
Artificial Intelligence, 2019b.

[Abel et al., 2020]
David Abel, Nathan Umbanhowar, Khimya Khetarpal, Dilip Arumugam, Doina Precup,
and Michael L. Littman.
Value preserving state-action abstractions.
In Proceedings of the International Conference on Artificial
Intelligence and Statistics, 2020.

[Akrour et al., 2018]
Riad Akrour, Filipe Veiga, Jan Peters, and Gerhard Neumann.
Regularizing reinforcement learning with state abstraction.
In Proceedings of the International Conference on Intelligent
Robots and Systems. IEEE, 2018.

[Aldous and Fill, 1995]
David Aldous and James Fill.
Reversible Markov chains and random walks on graphs.
Technical report, University of California, Berkeley, 1995.

[Amari, 1998]
Shun-Ichi Amari.
Natural gradient works efficiently in learning.
Neural computation, 100 (2):0 251–276, 1998.

[Anand et al., 2015]
Ankit Anand, Aditya Grover, Mausam, and Parag Singla.
ASAP-UCT: abstraction of state-action pairs in UCT.
In Proceedings of the International Joint Conference on
Artificial Intelligence, 2015.

[Anand et al., 2016]
Ankit Anand, Ritesh Noothigattu, Mausam, and Parag Singla.
OGA-UCT: on-the-go abstractions in UCT.
In Proceedings of the International Conference on Automated
Planning and Scheduling, 2016.

[Andre and Russell, 2002]
David Andre and Stuart Russell.
State abstraction for programmable reinforcement learning agents.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2002.

[Archer, 2001]
Aaron Archer.
Two ${O}(\log^* k)$-approximation algorithms for the asymmetric
$k$-center problem.
In Proceedings of the International Conference on Integer
Programming and Combinatorial Optimization, 2001.

[Argall et al., 2009]
Brenna D. Argall, Sonia Chernova, Manuela Veloso, and Brett Browning.
A survey of robot learning from demonstration.
Robotics and autonomous systems, 570 (5):0
469–483, 2009.

[Arimoto, 1972]
Suguru Arimoto.
An algorithm for computing the capacity of arbitrary discrete
memoryless channels.
IEEE Transactions on Information Theory, 180
(1):0 14–20, 1972.

[Asadi, 2015]
Kavosh Asadi.
Strengths, weaknesses, and combinations of model-based and model-free
reinforcement learning.
Master's thesis, University of Alberta, 2015.

[Asadi and Littman, 2017]
Kavosh Asadi and Michael L. Littman.
An alternative softmax operator for reinforcement learning.
In Proceedings of the International Conference on Machine
Learning, 2017.

[Asadi et al., 2018]
Kavosh Asadi, Dipendra Misra, and Michael L. Littman.
Lipschitz continuity in model-based reinforcement learning.
In Proceedings of the International Conference on Machine
Learning, 2018.

[Asadi et al., 2020]
Kavosh Asadi, David Abel, and Michael L. Littman.
Learning state abstractions for transfer in continuous control.
arXiv preprint arXiv:2002.05518, 2020.

[Asmuth et al., 2009]
John Asmuth, Lihong Li, Michael L. Littman, Ali Nouri, and David Wingate.
A Bayesian sampling approach to exploration in reinforcement
In Proceedings of the Conference on Uncertainty in Artificial
Intelligence, 2009.

[Atkeson and Schaal, 1997]
Christopher G. Atkeson and Stefan Schaal.
Robot learning from demonstration.
In Proceedings of the International Conference on Machine
Learning, 1997.

[Attneave, 1954]
Fred Attneave.
Some informational aspects of visual perception.
Psychological Review, 30 (61), 1954.

[Auer and Ortner, 2007]
Peter Auer and Ronald Ortner.
Logarithmic online regret bounds for undiscounted reinforcement
In Advances in Neural Information Processing Systems, 2007.

[Axsäter, 1983]
Sven Axsäter.
State aggregation in dynamic programming — an application to
scheduling of independent jobs on parallel processors.
Operations Research Letters, 20 (4):0
171–176, 1983.

[Bacon et al., 2017]
Pierre-Luc Bacon, Jean Harb, and Doina Precup.
The option-critic architecture.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2017.

[Bagaria and Konidaris, 2020]
Akhil Bagaria and George Konidaris.
Option discovery using deep skill chaining.
In Proceedings of the International Conference on Learning
Representations, 2020.

[Bai and Russell, 2016]
Aijun Bai and Stuart Russell.
Markovian State and Action Abstractions for MDPs via Hierarchical
In Proceedings of the International Joint Conference on
Artificial Intelligence, 2016.

[Barlow, 1961]
Horace B. Barlow.
Possible principles underlying the transformation of sensory
Sensory communication, 1:0 217–234, 1961.

[Barreto et al., 2017]
André Barreto, Will Dabney, Rémi Munos, Jonathan J. Hunt, Tom Schaul,
Hado van Hasselt, and David Silver.
Successor features for transfer in reinforcement learning.
In Advances in Neural Information Processing Systems, 2017.

[Barreto et al., 2019]
André Barreto, Diana Borsa, Shaobo Hou, Gheorghe Comanici, Eser Aygün,
Philippe Hamel, Daniel Toyama, Jonathan Hunt, Shibl Mourad, David Silver, and
Doina Precup.
The option keyboard: Combining skills in reinforcement learning.
In Advances in Neural Information Processing Systems, 2019.

[Bartlett and Mendelson, 2002]
Peter L. Bartlett and Shahar Mendelson.
Rademacher and gaussian complexities: Risk bounds and structural
Journal of Machine Learning Research, 30 (Nov), 2002.

[Barto and Mahadevan, 2003]
Andrew G. Barto and Sridhar Mahadevan.
Recent advances in hierarchical reinforcement learning.
Discrete event dynamic systems, 130 (1-2):0
41–77, 2003.

[Bayer and Glimcher, 2005]
Hannah M. Bayer and Paul W. Glimcher.
Midbrain dopamine neurons encode a quantitative reward prediction
error signal.
Neuron, 470 (1):0 129–141, 2005.

[Bellemare et al., 2013]
Marc G. Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling.
The arcade learning environment: An evaluation platform for general
Journal of Artificial Intelligence Research, 47:0
253–279, 2013.

[Bellemare et al., 2017]
Marc G. Bellemare, Will Dabney, and Rémi Munos.
A distributional perspective on reinforcement learning.
In Proceedings of the International Conference on Machine
Learning, 2017.

[Bellman, 1956]
Richard Bellman.
Dynamic programming and Lagrange multipliers.
Proceedings of the National Academy of Sciences, 420
(10):0 767–769, 1956.

[Bellman, 1957]
Richard Bellman.
A Markovian decision process.
Journal of Mathematics and Mechanics, pages 679–684, 1957.

[Berger, 1971]
Toby Berger.
Rate distortion theory: A mathematical basis for data
Prentice-Hall, 1971.

[Bertsekas, 2018]
Dimitri P. Bertsekas.
Feature-based aggregation and deep reinforcement learning: A survey
and some new implementations.
IEEE/CAA Journal of Automatica Sinica, 60
(1):0 1–31, 2018.

[Bertsekas and Castanon, 1989]
Dimitri P. Bertsekas and David A. Castanon.
Adaptive aggregation methods for infinite horizon dynamic
IEEE Transactions on Automatic Control, 34:0 589–598,

[Bertsekas and Tsitsiklis, 1996]
Dimitri P. Bertsekas and John N. Tsitsiklis.
Neuro-dynamic programming, volume 5.
Athena Scientific Belmont, MA, 1996.

[Blahut, 1972]
Richard Blahut.
Computation of channel capacity and rate-distortion functions.
IEEE transactions on Information Theory, 180
(4):0 460–473, 1972.

[Botvinick and Weinstein, 2014]
Matthew Botvinick and Ari Weinstein.
Model-based hierarchical reinforcement learning and human action
Philosophical Transactions of the Royal Society B: Biological
Sciences, 3690 (1655), 2014.

[Botvinick et al., 2015]
Matthew Botvinick, Ari Weinstein, Alec Solway, and Andrew G. Barto.
Reinforcement learning, efficient coding, and the statistics of
natural tasks.
Current Opinion in Behavioral Sciences, 5:0 71–77,

[Botvinick et al., 2009]
Matthew M. Botvinick, Yael Niv, and Andew G. Barto.
Hierarchically organized behavior and its neural foundations: A
reinforcement learning perspective.
Cognition, 1130 (3):0 262–280, 2009.

[Box, 1976]
George E.P. Box.
Science and statistics.
Journal of the American Statistical Association, 710
(356):0 791–799, 1976.

[Braess, 1968]
Dietrich Braess.
Über ein paradoxon aus der verkehrsplanung.
Unternehmensforschung, 120 (1):0 258–268,

[Braess et al., 2005]
Dietrich Braess, Anna Nagurney, and Tina Wakolbinger.
On a paradox of traffic planning.
Transportation science, 390 (4):0 446–450,

[Brafman and Tennenholtz, 2002]
Ronen I. Brafman and Moshe Tennenholtz.
R-max: A general polynomial time algorithm for near-optimal
reinforcement learning.
JMLR, 30 (Oct):0 213–231, 2002.

[Brémaud, 2013]
Pierre Brémaud.
Markov chains: Gibbs fields, Monte Carlo simulation, and
queues, volume 31.
Springer Science & Business Media, 2013.

[Brockman et al., 2016]
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman,
Jie Tang, and Wojciech Zaremba.
OpenAI gym, 2016.

[Broder and Karlin, 1989]
Andrei Z. Broder and Anna R. Karlin.
Bounds on the cover time.
Journal of Theoretical Probability, 20 (1):0
101–120, 1989.

[Brunskill and Li, 2014]
Emma Brunskill and Lihong Li.
PAC-inspired option discovery in lifelong reinforcement learning.
In Proceedings of the International Conference on Machine
Learning, 2014.

[Brunskill and Li, 2015]
Emma Brunskill and Lihong Li.
The online coupon-collector problem and its application to lifelong
reinforcement learning.
arXiv preprint arXiv:1506.03379, 2015.

[Burridge et al., 1999]
Robert R. Burridge, Alfred A. Rizzi, and Daniel E. Koditschek.
Sequential composition of dynamically dexterous robot behaviors.
The International Journal of Robotics Research, 180
(6):0 534–555, 1999.

[Bylander, 1991]
Tom Bylander.
Complexity results for planning.
In Proceedings of the International Joint Conference on
Artificial Intelligence, volume 10, 1991.

[Bylander, 1994]
Tom Bylander.
The computational complexity of propositional STRIPS planning.
Artificial Intelligence, 690 (1-2):0 165–204,

[Cao and Ray, 2012]
Feng Cao and Soumya Ray.
Bayesian hierarchical reinforcement learning.
In Advances in Neural information Processing Systems, 2012.

[Castro, 2020]
Pablo Samuel Castro.
Scalable methods for computing state similarity in deterministic
Markov decision processes.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2020.

[Castro and Precup, 2011]
Pablo Samuel Castro and Doina Precup.
Automatic construction of temporally extended actions for MDPs
using bisimulation metrics.
In Proceedings of the European Workshop on Reinforcement
Learning, 2011.

[Chapman and Kaelbling, 1991]
David Chapman and Leslie Pack Kaelbling.
Input generalization in delayed reinforcement learning: An algorithm
and performance comparisons.
In Proceedings of the International Joint Conference on
Artificial Intelligence, 1991.

[Chung, 1996]
Fan R.K. Chung.
Spectral graph theory.
American Mathematical Society, 1996.

[Chuzhoy et al., 2005]
Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz,
Robert Krauthgamer, and Joseph Seffi Naor.
Asymmetric $k$-center is $\log^* n$-hard to approximate.
Journal of the ACM, 520 (4):0 538–551, 2005.

[Chvatal, 1979]
Vasek Chvatal.
A greedy heuristic for the set-covering problem.
Mathematics of operations research, 40 (3):0
233–235, 1979.

[Ciosek and Silver, 2015]
Kamil Ciosek and David Silver.
Value iteration with options and state aggregation.
arXiv:1501.03959, 2015.

[Cobo et al., 2011]
Luis C. Cobo, Peng Zang, Charles L. Isbell, and Andrea L. Thomaz.
Automatic state abstraction from demonstration.
In Proceedings of the International Joint Conference on
Artificial Intelligence, 2011.

[Cobo et al., 2012]
Luis C. Cobo, Charles L. Isbell, and Andrea L. Thomaz.
Automatic task decomposition and state abstraction from
In Proceedings of the International Conference on Autonomous
Agents and Multiagent Systems, 2012.

[Cohn et al., 1996]
David A. Cohn, Zoubin Ghahramani, and Michael I. Jordan.
Active learning with statistical models.
Journal of Artificial Intelligence Research, 4:0
129–145, 1996.

[Coulom, 2006]
Rémi Coulom.
Efficient selectivity and backup operators in Monte-Carlo tree
In Proceedings of the International Conference on Computers and
Games, 2006.

[Cover and Thomas, 2012]
Thomas M. Cover and Joy A. Thomas.
Elements of information theory.
John Wiley & Sons, 2012.

[Currie and Tate, 1991]
Ken Currie and Austin Tate.
O-plan: the open planning architecture.
Artificial intelligence, 520 (1):0 49–86,

[da Silva et al., 2012]
Bruno Castro da Silva, George Konidaris, and Andrew G. Barto.
Learning parameterized skills.
In Proceedings of the International Conference on Machine
Learning, 2012.

[da Silva et al., 2014]
Bruno Castro da Silva, George Konidaris, and Andrew G. Barto.
Active learning of parameterized skills.
In Proceedings of the International Conference on Machine
Learning, 2014.

[Dabney et al., 2018]
Will Dabney, Georg Ostrovski, David Silver, and Rémi Munos.
Implicit quantile networks for distributional reinforcement learning.
In Proceedings of the International Conference on Machine
Learning, 2018a.

[Dabney et al., 2018]
Will Dabney, Mark Rowland, Marc G. Bellemare, and Rémi Munos.
Distributional reinforcement learning with quantile regression.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2018b.

[Dabney et al., 2020]
Will Dabney, Zeb Kurth-Nelson, Naoshige Uchida, Clara Kwon Starkweather, Demis
Hassabis, Rémi Munos, and Matthew Botvinick.
A distributional code for value in dopamine-based reinforcement
Nature, pages 1–5, 2020.

[Dann et al., 2017]
Christoph Dann, Tor Lattimore, and Emma Brunskill.
Unifying PAC and regret: Uniform PAC bounds for episodic
reinforcement learning.
In Advances in Neural Information Processing Systems, 2017.

[Dayan, 1993]
Peter Dayan.
Improving generalization for temporal difference learning: The
successor representation.
Neural Computation, 50 (4):0 613–624, 1993.

[Dayan and Balleine, 2002]
Peter Dayan and Bernard W. Balleine.
Reward, motivation, and reinforcement learning.
Neuron, 360 (2):0 285–298, 2002.

[Dayan and Hinton, 1993]
Peter Dayan and Geoffrey E. Hinton.
Feudal reinforcement learning.
In Advances in Neural Information Processing Systems, 1993.

[Dean and Givan, 1997]
Thomas Dean and Robert Givan.
Model minimization in Markov decision processes.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 1997.

[Dearden and Boutilier, 1997]
Richard Dearden and Craig Boutilier.
Abstraction and approximate decision-theoretic planning.
Artificial Intelligence, 890 (1):0 219–283,

[Dietterich, 2000]
Thomas G. Dietterich.
Hierarchical reinforcement learning with the MAXQ value function
Journal of Artificial Intelligence Research,

[Dietterich, 2000]
Thomas G. Dietterich.
State abstraction in MAXQ hierarchical reinforcement learning.
In Advances in Neural Information Processing Systems,

[Digney, 1998]
Bruce L. Digney.
Learning hierarchical control structures for multiple tasks and
changing environments.
In Proceedings of the International Conference on Simulation of
Adaptive Behavior, 1998.

[Dinitz et al., 2012]
Michael Dinitz, Guy Kortsarz, and Ran Raz.
Label cover instances with large girth and the hardness of
approximating basic $k$-spanner.
In International Colloquium on Automata, Languages, and
Programming. Springer, 2012.

[Dinur and Steurer, 2014]
Irit Dinur and David Steurer.
Analytical approach to parallel repetition.
In Proceedings of the ACM Symposium on Theory of Computing,

[Diuk et al., 2008]
Carlos Diuk, Andre Cohen, and Michael L. Littman.
An object-oriented representation for efficient reinforcement
In Proceedings of the International Conference on Machine
Learning, 2008.

[Diuk et al., 2009]
Carlos Diuk, Lihong Li, and Bethany R. Leffler.
The adaptive $k$-meteorologists problem and its application to
structure learning and feature selection in reinforcement learning.
In Proceedings of the International Conference on Machine
Learning, 2009.

[Dowe et al., 2011]
David L. Dowe, José Hernández-Orallo, and Paramjit K. Das.
Compression and intelligence: social environments and communication.
In Proceedings of the International Conference on Artificial
General Intelligence, 2011.

[Du et al., 2019]
Simon S. Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav
Dudík, and John Langford.
Provably efficient RL with rich observations via latent state
In Proceedings of the International Conference on Machine
Learning, 2019.

[Eckstein and Collins, 2018]
Maria Eckstein and Anne Collins.
Evidence for hierarchically-structured reinforcement learning in
In Proceedings of Annual Conference of the Cognitive Science
Society, 2018.

[Erol et al., 1994]
Kutluhan Erol, James Hendler, and Dana S. Nau.
HTN planning: Complexity and expressivity.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 1994.

[Even-Dar and Mansour, 2003]
Eyal Even-Dar and Yishay Mansour.
Approximate equivalence of Markov decision processes.
In Learning Theory and Kernel Machines. Springer, 2003.

[Eysenbach et al., 2019]
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine.
Diversity is all you need: Learning skills without a reward function.
In Proceedings of the International Conference on
Representation Learning, 2019.

[Feng et al., 2004]
Zhengzhu Feng, Richard Dearden, Nicolas Meuleau, and Richard Washington.
Dynamic programming for structured continuous Markov decision
In Proceedings of the Conference on Uncertainty in Artificial
Intelligence, 2004.

[Ferns et al., 2004]
Norm Ferns, Prakash Panangaden, and Doina Precup.
Metrics for finite Markov decision processes.
In Proceedings of the Conference on Uncertainty in Artificial
Intelligence, 2004.

[Ferns et al., 2006]
Norm Ferns, Pablo Samuel Castro, Doina Precup, and Prakash Panangaden.
Methods for computing state similarity in Markov decision
In Proceedings of the Conference on Uncertainty in Artificial
Intelligence, 2006.

[Fiedler, 1973]
Miroslav Fiedler.
Algebraic connectivity of graphs.
Czechoslovak Mathematical Journal, 230 (2):0
298–305, 1973.

[Fikes and Nilsson, 1971]
Richard E. Fikes and Nils J. Nilsson.
STRIPS: A new approach to the application of theorem proving to
problem solving.
Artificial intelligence, 20 (3-4):0 189–208,

[Florensa et al., 2017]
Carlos Florensa, Yan Duan, and Pieter Abbeel.
Stochastic neural networks for hierarchical reinforcement learning.
In Proceedings of the International Conference on Learning
Representations, 2017.

[Fox, 1973]
Bennett L. Fox.
Discretizing dynamic programs.
Journal of Optimization Theory and Applications, 110
(3):0 228–234, 1973.

[François-Lavet et al., 2019]
Vincent François-Lavet, Yoshua Bengio, Doina Precup, and Joelle Pineau.
Combined reinforcement learning via abstract representations.
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 33, 2019.

[Freeman, 1977]
Linton C. Freeman.
A set of measures of centrality based on betweenness.
Sociometry, pages 35–41, 1977.

[Friedman et al., 1977]
Jerome H. Friedman, Jon Louis Bentley, and Raphael Ari Finkel.
An algorithm for finding best matches in logarithmic expected time.
ACM Transactions on Mathematical Software, 30
(3):0 209–226, 1977.

[Fruit and Lazaric, 2017]
Ronan Fruit and Alessandro Lazaric.
Exploration–exploitation in MDPs with options.
In Proceedings of the International Conference on Artificial
Intelligence and Statistics, 2017.

[Fruit et al., 2017]
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Emma Brunskill.
Regret minimization in MDPs with options without prior knowledge.
In Advances in Neural Information Processing Systems, 2017.

[Gardiol and Kaelbling, 2004]
Natalia H. Gardiol and Leslie Pack Kaelbling.
Envelope-based planning in relational MDPs.
In Advances in Neural Information Processing Systems, 2004.

[Gelada et al., 2019]
Carles Gelada, Saurabh Kumar, Jacob Buckman, Ofir Nachum, and Marc G.
DeepMDP: Learning continuous latent space models for representation
In Proceedings of the International Conference on Machine
Learning, 2019.

[Gershman et al., 2015]
Samuel J. Gershman, Eric J. Horvitz, and Joshua Tenenbaum.
Computational rationality: A converging paradigm for intelligence in
brains, minds, and machines.
Science, 3490 (6245):0 273–278, 2015.

[Ghavamzadeh et al., 2006]
Mohammad Ghavamzadeh, Sridhar Mahadevan, and Rajbala Makar.
Hierarchical multi-agent reinforcement learning.
Autonomous Agents and Multi-Agent Systems, 130
(2):0 197–229, 2006.

[Ghosh and Boyd, 2006]
Arpita Ghosh and Stephen Boyd.
Growing well-connected graphs.
In Decision and Control, 2006 45th IEEE Conference on, pages
6605–6611. IEEE, 2006.

[Gigerenzer and Goldstein, 1996]
Gerd Gigerenzer and Daniel G. Goldstein.
Reasoning the fast and frugal way: models of bounded rationality.
Psychological review, 1030 (4):0 650, 1996.

[Giunchiglia and Walsh, 1992]
Fausto Giunchiglia and Toby Walsh.
A theory of abstraction.
Artificial intelligence, 570 (2-3):0 323–389,

[Givan et al., 1997]
Robert Givan, Sonia Leach, and Thomas Dean.
Bounded parameter Markov decision processes.
In European Conference on Planning, 1997.

[Gopalan et al., 2017]
Nakul Gopalan, Marie desJardins, Michael L. Littman, James MacGlashan, Shawn
Squire, Stefanie Tellex, John Winder, and Lawson L.S. Wong.
Planning with abstract Markov decision processes.
In Proceedings of the International Conference on Automated
Planning and Scheduling, 2017.

[Gordon, 1996]
Geoffrey J. Gordon.
Chattering in SARSA($\lambda$).
Technical report, Carnegie Mellon University Learning Lab, 1996.

[Guestrin et al., 2001]
Carlos Guestrin, Daphne Koller, and Ronald Parr.
Max-norm projections for factored MDPs.
In Proceedings of the International Joint Conference on
Artificial Intelligence, 2001.

[Harb et al., 2018]
Jean Harb, Pierre-Luc Bacon, Martin Klissarov, and Doina Precup.
When waiting is not an option: Learning options with a deliberation
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2018.

[Hartmanis and Stearns, 1966]
Juris Hartmanis and Richard E. Stearns.
Algebraic structure theory of sequential machines.
Prentice-Hall, Inc., 1966.

[Harutyunyan et al., 2018]
Anna Harutyunyan, Peter Vrancx, Pierre-Luc Bacon, Doina Precup, and Ann
Learning with options that terminate off-policy.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2018.

[Harutyunyan et al., 2019]
Anna Harutyunyan, Will Dabney, Thomas Mesnard, Mohammad Gheshlaghi Azar, Bilal
Piot, Nicolas Heess, Hado van Hasselt, Gregory Wayne, Satinder Singh, and
Doina Precup.
Hindsight credit assignment.
In Advances in Neural Information Processing Systems, 2019.

[Hauskrecht et al., 1998]
Milos Hauskrecht, Nicolas Meuleau, Leslie Pack Kaelbling, Thomas Dean, and
Craig Boutilier.
Hierarchical solution of Markov decision processes using
In Proceedings of the Conference on Uncertainty in Artificial
Intelligence, 1998.

[Hengst, 2002]
Bernhard Hengst.
Discovering hierarchy in reinforcement learning with HEXQ.
Proceedings of the International Conference on Machine
Learning, 2002.

[Hessel et al., 2018]
Matteo Hessel, Joseph Modayil, Hado van Hasselt, Tom Schaul, Georg Ostrovski,
Will Dabney, Dan Horgan, Bilal Piot, Mohammad Gheshlaghi Azar, and David
Rainbow: Combining improvements in deep reinforcement learning.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2018.

[Ho et al., 2019]
Mark K. Ho, David Abel, Thomas L. Griffiths, and Michael L. Littman.
The value of abstraction.
Current Opinion in Behavioral Sciences, 2019.

[Ho et al., 2020]
Mark K. Ho, David Abel, Jonathan D. Cohen, Michael L. Littman, and Thomas L.
The efficiency of human cognition reflects planned use of information
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2020.

[Hostetler et al., 2014]
Jesse Hostetler, Alan Fern, and Thomas G. Dietterich.
State Aggregation in Monte Carlo Tree Search.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2014.

[Hutter, 2005]
Marcus Hutter.
Universal artificial intelligence: Sequential decisions based
on algorithmic probability.
Springer, 2005.

[Hutter, 2014]
Marcus Hutter.
Extreme state aggregation beyond MDPs.
In Proceedings of the International Conference on Algorithmic
Learning Theory, 2014.

[Hutter, 2016]
Marcus Hutter.
Extreme state aggregation beyond Markov decision processes.
Theoretical Computer Science, 650:0 73–91, 2016.

[Iba, 1989]
Glenn A. Iba.
A heuristic approach to the discovery of macro-operators.
Machine Learning, 30 (4):0 285–317, 1989.

[Isele et al., 2016]
David Isele, Mohammad Rostami, and Eric Eaton.
Using task features for zero-shot knowledge transfer in lifelong
In Proceedings of the International Joint Conference on
Artificial Intelligence, 2016.

[James et al., 2017]
Steven James, George Konidaris, and Benjamin Rosman.
An analysis of Monte Carlo tree search.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2017.

[James et al., 2018]
Steven James, Benjamin Rosman, and George Konidaris.
Learning to plan with portable symbols.
In ICML Workshop on Planning and Learning, 2018.

[Jiang et al., 2014]
Nan Jiang, Satinder Singh, and Richard Lewis.
Improving UCT planning via approximate homomorphisms.
In Proceedings of the International Conference on Autonomous
Agents and Multi-Agent Systems, 2014.

[Jiang et al., 2015]
Nan Jiang, Alex Kulesza, and Satinder Singh.
Abstraction selection in model-based reinforcement learning.
In Proceedings of the International Conference on Machine
Learning, 2015a.

[Jiang et al., 2015]
Nan Jiang, Alex Kulesza, Satinder Singh, and Richard Lewis.
The dependence of effective planning horizon on model accuracy.
In Proceedings of the International Conference on Autonomous
Agents and Multiagent Systems, 2015b.

[Jinnai et al., 2019]
Yuu Jinnai, David Abel, D. Ellis Hershkowitz, Michael L. Littman, and George
Finding options that minimize planning time.
In Proceedings of the International Conference on Machine
Learning, 2019a.

[Jinnai et al., 2019]
Yuu Jinnai, Jee Won Park, David Abel, and George Konidaris.
Discovering options for exploration by minimizing cover time.
In Proceedings of the International Conference on Machine
Learning, 2019b.

[Jinnai et al., 2020]
Yuu Jinnai, Jee Won Park, Marlos C. Machado, and George Konidaris.
Exploration in reinforcement learning with deep covering options.
In Proceedings of the International Conference on Learning
Representations, 2020.

[Jong and Stone, 2005]
Nicholas K. Jong and Peter Stone.
State abstraction discovery from irrelevant state variables.
In Proceedings of the International Joint Conference on
Artificial Intelligence, 2005.

[Jong and Stone, 2008]
Nicholas K. Jong and Peter Stone.
Hierarchical model-based reinforcement learning: R-max +
In Proceedings of the International Conference on Machine
Learning, 2008.

[Jong et al., 2008]
Nicholas K. Jong, Todd Hester, and Peter Stone.
The utility of temporal abstraction in reinforcement learning.
In Proceedings of the International Conference on Autonomous
Agents and Multiagent Systems, 2008.

[Jonschkowski and Brock, 2015]
Rico Jonschkowski and Oliver Brock.
Learning state representations with robotic priors.
Autonomous Robots, 390 (3):0 407–428, 2015.

[Jonsson and Barto, 2001]
Anders Jonsson and Andrew G. Barto.
Automated state abstraction for options using the U-tree algorithm.
In Advances in Neural Information Processing Systems, 2001.

[Kaelbling, 1993]
Leslie Pack Kaelbling.
Hierarchical reinforcement learning: Preliminary results.
In Proceedings of the International Conference on Machine
Learning, 1993.

[Kaelbling et al., 1996]
Leslie Pack Kaelbling, Michael L. Littman, and Andrew W. Moore.
Reinforcement learning: A survey.
Journal of Artificial Intelligence Research, pages 237–285,

[Kaelbling et al., 1998]
Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra.
Planning and acting in partially observable stochastic domains.
Artificial intelligence, 1010 (1-2):0 99–134,

[Kakade, 2003]
Sham Kakade.
On the sample complexity of reinforcement learning.
PhD thesis, University of London, 2003.

[Karl et al., 2017]
Maximilian Karl, Maximilian Soelch, Justin Bayer, and Patrick van der Smagt.
Deep variational Bayes filters: Unsupervised learning of state
space models from raw data.
In Proceedings of the International Conference on Learning
Representations, 2017.

[Kearns and Singh, 2002]
Michael Kearns and Satinder Singh.
Near-optimal reinforcement learning in polynomial time.
Machine learning, 490 (2-3):0 209–232, 2002.

[Kemp and Tenenbaum, 2009]
Charles Kemp and Joshua Tenenbaum.
Structured statistical models of inductive reasoning.
Psychological review, 1160 (1):0 20, 2009.

[Kersting et al., 2004]
Kristian Kersting, Martijn Van Otterlo, and Luc De Raedt.
Bellman goes relational.
In Proceedings of the International Conference on Machine
learning, 2004.

[Khetarpal et al., 2020]
Khimya Khetarpal, Martin Klissarov, Maxime Chevalier-Boisvert, Pierre-Luc
Bacon, and Doina Precup.
Options of interest: Temporal abstraction with interest functions.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2020.

[Kim and Mnih, 2018]
Hyunjik Kim and Andriy Mnih.
Disentangling by factorising.
In Proceedings of the International Conference on Machine
Learning, 2018.

[Kingma and Ba, 2014]
Diederik P. Kingma and Jimmy Ba.
Adam: A method for stochastic optimization.
arXiv preprint arXiv:1412.6980, 2014.

[Kingma and Welling, 2014]
Diederik P. Kingma and Max Welling.
Auto-encoding variational Bayes.
In Proceedings of the International Conference on Learning
Representations, 2014.

[Klein, 2003]
Jon Klein.
BREVE: a 3D environment for the simulation of decentralized
systems and artificial life.
In Proceedings of the International Conference on Artificial
life, 2003.

[Knoblock, 1994]
Craig A. Knoblock.
Automatically generating abstractions for planning.
Artificial Intelligence, 680 (2):0 243–302,

[Kocsis and Szepesvári, 2006]
Levente Kocsis and Csaba Szepesvári.
Bandit based monte-carlo planning.
In In Proceedings of the European Conference on Machine
Learning, 2006.

[Koller and Parr, 1999]
Daphne Koller and Ronald Parr.
Computing factored value functions for policies in structured MDPs.
In Proceedings of the International Joint Conference on
Artificial Intelligence, 1999.

[Konidaris, 2011]
George Konidaris.
Autonomous Robot Skill Acquisition.
PhD thesis, University of Massachusetts Amherst, 2011.

[Konidaris, 2016]
George Konidaris.
Constructing abstraction hierarchies using a skill-symbol loop.
In Proceedings of the International Joint Conference on
Artificial Intelligence, 2016.

[Konidaris, 2019]
George Konidaris.
On the necessity of abstraction.
Current opinion in behavioral sciences, 29:0 1–7,

[Konidaris and Barto, 2006]
George Konidaris and Andrew G. Barto.
Autonomous shaping: Knowledge transfer in reinforcement learning.
In Proceedings of the International Conference on Machine
Learning, 2006.

[Konidaris and Barto, 2007]
George Konidaris and Andrew G. Barto.
Building portable options: Skill transfer in reinforcement learning.
In Proceedings of the International Joint Conference on
Artificial Intelligence, 2007.

[Konidaris and Barto, 2009]
George Konidaris and Andrew G. Barto.
Efficient skill learning using abstraction selection.
In Proceedings of the International Joint Conference on
Artificial Intelligence, 2009a.

[Konidaris and Barto, 2009]
George Konidaris and Andrew G. Barto.
Skill discovery in continuous reinforcement learning domains using
skill chaining.
In Advances in Neural Information Processing Systems,

[Konidaris et al., 2010]
George Konidaris, Scott Kuindersma, Roderic Grupen, and Andrew G. Barto.
Constructing skill trees for reinforcement learning agents from
demonstration trajectories.
In Advances in Neural Information Processing Systems, 2010.

[Konidaris et al., 2011]
George Konidaris, Scott Kuindersma, Roderic Grupen, and Andrew G. Barto.
Autonomous skill acquisition on a mobile manipulator.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2011a.

[Konidaris et al., 2011]
George Konidaris, Sarah Osentoski, and Philip S. Thomas.
Value function approximation in reinforcement learning using the
Fourier basis.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2011b.

[Konidaris et al., 2014]
George Konidaris, Leslie Pack Kaelbling, and Tomás Lozano-Pérez.
Constructing symbolic representations for high-level planning.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2014.

[Konidaris et al., 2015]
George Konidaris, Leslie Pack Kaelbling, and Tomás Lozano-Pérez.
Symbol acquisition for probabilistic high-level planning.
In Proceedings of the International Joint Conference on
Artificial Intelligence, 2015.

[Konidaris et al., 2018]
George Konidaris, Leslie Pack Kaelbling, and Tomás Lozano-Pérez.
From skills to symbols: Learning symbolic representations for
abstract high-level planning.
Journal of Artificial Intelligence Research, 2018.

[Koren, 2003]
Yehuda Koren.
On spectral graph drawing.
In International Computing and Combinatorics Conference, pages
496–508. Springer, 2003.

[Korf, 1983]
Richard E. Korf.
Learning to solve problems by searching for macro-operators.
Technical report, Carnegie Mellon University, 1983.

[Korf, 1985]
Richard E. Korf.
Macro-operators: A weak method for learning.
Artificial intelligence, 260 (1):0 35–77,

[Kroon and Whiteson, 2009]
Mark Kroon and Shimon Whiteson.
Automatic feature selection for model-based reinforcement learning in
factored MDPs.
In Proceedings of the International Conference on Machine
Learning and Applications, 2009.

[Krose and Van Dam, 1992]
Ben J.A. Krose and Joris W.M. Van Dam.
Adaptive state space quantisation for reinforcement learning of
collision-free navigation.
In Proceedings of the International Conference on Intelligent
Robots and Systems, 1992.

[Kulkarni et al., 2016]
Tejas D. Kulkarni, Karthik Narasimhan, Ardavan Saeedi, and Josh Tenenbaum.
Hierarchical deep reinforcement learning: Integrating temporal
abstraction and intrinsic motivation.
In Advances in Neural Information Processing Systems, 2016.

[Lagoudakis and Parr, 2003]
Michail G. Lagoudakis and Ronald Parr.
Least-squares policy iteration.
Journal of Machine Learning research, 40
(Dec):0 1107–1149, 2003.

[Larsen and Skou, 1991]
Kim G. Larsen and Arne Skou.
Bisimulation through probabilistic testing.
Information and computation, 940 (1):0 1–28,

[Lattimore and Szepesvári, 2018]
Tor Lattimore and Csaba Szepesvári.
Bandit algorithms.
preprint, 2018.

[Le et al., 2018]
Hoang M. Le, Nan Jiang, Alekh Agarwal, Miroslav Dudík, Yisong Yue, and Hal
Daumé III.
Hierarchical imitation and reinforcement learning.
In Proceedings of the International Conference on Machine
Learning, 2018.

[LeCun et al., 2015]
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.
Deep learning.
Nature, 5210 (7553):0 436, 2015.

[Lee and Lau, 2004]
Ivan S.K. Lee and Henry Y.K. Lau.
Adaptive state space partitioning for reinforcement learning.
Engineering Applications of Artificial Intelligence,
170 (6):0 577–588, 2004.

[Legg and Hutter, 2007]
Shane Legg and Marcus Hutter.
Universal intelligence: A definition of machine intelligence.
Minds and machines, 170 (4):0 391–444, 2007.

[Lehnert and Littman, 2018]
Lucas Lehnert and Michael L Littman.
Transfer with model features in reinforcement learning.
arXiv preprint arXiv:1807.01736, 2018.

[Lehnert and Littman, 2019]
Lucas Lehnert and Michael L Littman.
Successor features support model-based and model-free reinforcement
arXiv preprint arXiv:1901.11437, 2019.

[Lehnert et al., 2018]
Lucas Lehnert, Romain Laroche, and Harm van Seijen.
On value function representation of long horizon problems.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2018.

[Leike, 2016]
Jan Leike.
Nonparametric General Reinforcement Learning.
PhD thesis, Australian National University, 2016.

[Lesort et al., 2018]
Timothée Lesort, Natalia Díaz-Rodríguez, Jean-Franois Goudou, and
David Filliat.
State representation learning for control: An overview.
Neural Networks, 108:0 379–392, 2018.

[Levine et al., 2016]
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel.
End-to-end training of deep visuomotor policies.
Journal of Machine Learning Research, 170
(1):0 1334–1373, 2016.

[Levy et al., 2019]
Andrew Levy, George Konidaris, Robert Platt, and Kate Saenko.
Learning multi-level hierarchies with hindsight.
In Proceedings of the International Conference on Learning
Representations, 2019.

[Lewis et al., 2014]
Richard L. Lewis, Andrew Howes, and Satinder Singh.
Computational rationality: Linking mechanism and behavior through
bounded utility maximization.
Topics in cognitive science, 60 (2):0
279–311, 2014.

[Li, 2009]
Lihong Li.
A unifying framework for computational reinforcement learning
PhD thesis, Rutgers University, 2009.

[Li et al., 2006]
Lihong Li, Thomas J. Walsh, and Michael L. Littman.
Towards a unified theory of state abstraction for MDPs.
In Proceedings of the International Symposium on Artificial
Intelligence and Mathematics, 2006.

[Li et al., 2011]
Lihong Li, Michael L. Littman, Thomas J. Walsh, and Alexander L. Strehl.
Knows what it knows: A framework for self-aware learning.
Machine Learning, 820 (3):0 399–443, 2011.

[Li et al., 2017]
Zhuoru Li, Akshay Narayan, and Tze-Yun Leong.
An efficient approach to model-based hierarchical reinforcement
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2017.

[Liang et al., 2016]
Yitao Liang, Marlos C. Machado, Erik Talvitie, and Michael Bowling.
State of the art control of atari games using shallow reinforcement
In Proceedings of the International Conference on Autonomous
Agents and Multiagent Systems, 2016.

[Lin, 1992]
Long-Ji Lin.
Self-improving reactive agents based on reinforcement learning,
planning and teaching.
Machine learning, 80 (3-4):0 293–321, 1992.

[Littman and Szepesvári, 1996]
Michael L. Littman and Csaba Szepesvári.
A generalized reinforcement-learning model: Convergence and
In Proceedings of the International Conference on Machine
Learning, 1996.

[Littman et al., 1995]
Michael L. Littman, Thomas L. Dean, and Leslie Pack Kaelbling.
On the complexity of solving Markov decision problems.
In Proceedings of the International Joint Conference on
Artificial Intelligence, 1995.

[MacGlashan, 2013]
James MacGlashan.
Multi-source option-based policy transfer.
PhD thesis, University of Maryland, Baltimore County, 2013.

[Machado et al., 2017]
Marios C. Machado, Marc G. Bellemare, and Michael Bowling.
A Laplacian framework for option discovery in reinforcement
In Proceedings of the International Conference on Machine
Learning, 2017a.

[Machado et al., 2017]
Marlos C. Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro,
and Murray Campbell.
Eigenoption discovery through the deep successor representation.
In Proceedings of the International Conference on Learning
Representations, 2017b.

[Machado et al., 2018]
Marlos C. Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro,
and Murray Campbell.
Eigenoption Discovery through the Deep Successor Representation.
In Proceedings of the International Conference on Learning
Representations, 2018.

[Mahadevan and Maggioni, 2006]
Sridhar Mahadevan and Mauro Maggioni.
Value function approximation with diffusion wavelets and Laplacian
In Advances in Neural Information Processing Systems, 2006.

[Mahadevan and Maggioni, 2007]
Sridhar Mahadevan and Mauro Maggioni.
Proto-value functions: A Laplacian framework for learning
representation and control in Markov decision processes.
Journal of Machine Learning Research, 80
(Oct):0 2169–2231, 2007.

[Maillard et al., 2013]
Odalric-Ambrym Maillard, Phuong Nguyen, Ronald Ortner, and Daniil Ryabko.
Optimal regret bounds for selecting the state representation in
reinforcement learning.
In Proceedings of the International Conference on Machine
Learning, 2013.

[Majeed and Hutter, 2019]
Sultan Javed Majeed and Marcus Hutter.
Performance guarantees for homomorphisms beyond Markov decision
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2019.

[Mandel et al., 2016]
Travis Mandel, Yun-En Liu, Emma Brunskill, and Zoran Popovic.
Efficient Bayesian clustering for reinforcement learning.
In Proceedings of the International Joint Conference on
Artificial Intelligence, 2016.

[Mankowitz et al., 2014]
Daniel J. Mankowitz, Timothy A. Mann, and Shie Mannor.
Time-regularized interrupting options.
In Proceedings of the International Conference on Machine
Learning, 2014.

[Mankowitz et al., 2016]
Daniel J. Mankowitz, Timothy A. Mann, and Shie Mannor.
Adaptive skills adaptive partitions (asap).
In Advances in Neural Information Processing Systems, 2016.

[Mann and Mannor, 2014]
Timothy A. Mann and Shie Mannor.
Scaling up approximate value iteration with options: Better policies
with fewer iterations.
In Proceedings of the International Conference on Machine
Learning, 2014.

[Mann et al., 2015]
Timothy A. Mann, Shie Mannor, and Doina Precup.
Approximate value iteration with temporally extended actions.
Journal of Artificial Intelligence Research, 2015.

[Mannor et al., 2004]
Shie Mannor, Ishai Menache, Amit Hoze, and Uri Klein.
Dynamic abstraction in reinforcement learning via clustering.
In Proceedings of the International Conference on Machine
Learning, 2004.

[McCallum, 1995]
Andrew McCallum.
Reinforcement learning with selective perception and hidden
PhD thesis, University of Rochester, 1995.

[McCarthy et al., 2006]
John McCarthy, Marvin L. Minsky, Nathaniel Rochester, and Claude E. Shannon.
A proposal for the Dartmouth summer research project on
Artificial Intelligence, August 31, 1955.
AI magazine, 270 (4):0 12–12, 2006.

[McGovern, 1998]
Amy McGovern.
acQuire-macros: An algorithm for automatically learning
In NeurIPS Workshop on Abstraction and Hierarchy in
Reinforcement Learning, 1998.

[McGovern and Barto, 2001]
Amy McGovern and Andrew G. Barto.
Automatic discovery of subgoals in reinforcement learning using
diverse density.
In Proceedings of the International Conference on Machine
Learning, 2001.

[McGovern et al., 1997]
Amy McGovern, Richard S. Sutton, and Andrew H. Fagg.
Roles of macro-actions in accelerating reinforcement learning.
In Proceedings of the Grace Hopper Celebration of Women in
Computing, 1997.

[Mehta et al., 2007]
Neville Mehta, Mike Wynkoop, Soumya Ray, Prasad Tadepalli, and Thomas G.
Automatic induction of MAXQ hierarchies.
In NeurIPS Workshop on Hierarchical Organization of Behavior,

[Mehta et al., 2008]
Neville Mehta, Sriraam Natarajan, Prasad Tadepalli, and Alan Fern.
Transfer in variable-reward hierarchical reinforcement learning.
Machine Learning, 730 (3):0 289,

[Mehta et al., 2008]
Neville Mehta, Soumya Ray, Prasad Tadepalli, and Thomas G. Dietterich.
Automatic discovery and transfer of MAXQ hierarchies.
In Proceedings of the International Conference on Machine
Learning, 2008b.

[Mehta et al., 2011]
Neville Mehta, Soumya Ray, Prasad Tadepalli, and Thomas G. Dietterich.
Automatic Discovery and Transfer of Task Hierarchies in
Reinforcement Learning.
AI Magazine, 320 (1):0 35, 2011.

[Melo et al., 2008]
Francisco S. Melo, Sean P. Meyn, and M. Isabel Ribeiro.
An analysis of reinforcement learning with function approximation.
In Proceedings of the International Conference on Machine
Learning, 2008.

[Menache et al., 2002]
Ishai Menache, Shie Mannor, and Nahum Shimkin.
Q-cut - dynamic discovery of sub-goals in reinforcement learning.
In Proceedings of the European Conference on Machine Learning,

[Menashe and Stone, 2018]
Jacob Menashe and Peter Stone.
State abstraction synthesis for discrete models of continuous
In Proceedings of the AAAI Spring Symposium Series, 2018.

[Misra et al., 2019]
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford.
Kinematic state abstraction and provably efficient rich-observation
reinforcement learning.
arXiv preprint arXiv:1911.05815, 2019.

[Mnih et al., 2015]
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness,
Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland,
Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis
Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and
Demis Hassabis.
Human-level control through deep reinforcement learning.
Nature, 5180 (7540):0 529, 2015.

[Mnih et al., 2016]
Volodymyr Mnih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves,
Timothy P. Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu.
Asynchronous Methods for Deep Reinforcement Learning.
In Proceedings of the International Conference on Machine
Learning, 2016.

[Moore, 1994]
Andrew W. Moore.
The parti-game algorithm for variable resolution reinforcement
learning in multidimensional state-spaces.
In Advances in Neural Information Processing Systems, 1994.

[Mosk-Aoyama, 2008]
Damon Mosk-Aoyama.
Maximum algebraic connectivity augmentation is NP-hard.
Operations Research Letters, 360 (6):0
677–679, 2008.

[Mugan and Kuipers, 2008]
Jonathan Mugan and Benjamin Kuipers.
Towards the application of reinforcement learning to undirected
developmental learning.
In Proceedings of the International Conference on Epigenetic
Robots, 2008.

[Mugan and Kuipers, 2009]
Jonathan Mugan and Benjamin Kuipers.
Autonomously learning an action hierarchy using a learned qualitative
state representation.
In Proceedings of the International Joint Conference on
Artificial Intelligence, 2009.

[Mugan and Kuipers, 2011]
Jonathan Mugan and Benjamin Kuipers.
Autonomous learning of high-level states and actions in continuous
IEEE Transactions on Autonomous Mental Development, 40
(1):0 70–86, 2011.

[Mumey and Gedeon, 2003]
Brendan Mumey and Tomáš Gedeon.
Optimal mutual information quantization is NP-complete.
In Neural Information Coding, 2003.

[Nachum et al., 2018]
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine.
Data-efficient hierarchical reinforcement learning.
In Advances in Neural Information Processing Systems, 2018.

[Nachum et al., 2019]
Ofir Nachum, Shixiang Gu, Honglak Lee, and Sergey Levine.
Near-optimal representation learning for hierarchical reinforcement
In Proceedings of the International Conference on Learning
Representations, 2019.

[Newell et al., 1957]
Allen Newell, John Clark Shaw, and Herbert A. Simon.
Empirical explorations of the logic theory machine: a case study in
In Papers presented at the Western Joint Computer Conference:
Techniques for Reliability. ACM, 1957.

[Ng and Russell, 2000]
Andrew Y. Ng and Stuart Russell.
Algorithms for inverse reinforcement learning.
In Proceedings of the International Conference on Machine
Learning, 2000.

[Nicol and Chadès, 2012]
Sam Nicol and Iadine Chadès.
Which states matter? an application of an intelligent discretization
method to solve a continuous pomdp in conservation biology.
PloS one, 70 (2), 2012.

[Odalric-Ambrym et al., 2013]
Maillard Odalric-Ambrym, Phuong Nguyen, Ronald Ortner, and Daniil Ryabko.
Optimal regret bounds for selecting the state representation in
reinforcement learning.
In Proceedings of the International Conference on Machine
Learning, 2013.

[Oh et al., 2017]
Junhyuk Oh, Satinder Singh, and Honglak Lee.
Value prediction network.
In Advances in Neural Information Processing Systems, 2017.

[Ortner et al., 2014]
Ronald Ortner, Odalric-Ambrym Maillard, and Daniil Ryabko.
Selecting near-optimal approximate state representations in
reinforcement learning.
In Proceedings of the International Conference on Algorithmic
Learning Theory, 2014.

[Ortner et al., 2019]
Ronald Ortner, Matteo Pirotta, Alessandro Lazaric, Ronan Fruit, and
Odalric-Ambrym Maillard.
Regret bounds for learning state representations in reinforcement
In Advances in Neural Information Processing Systems, 2019.

[Osband et al., 2013]
Ian Osband, Daniel Russo, and Benjamin Van Roy.
(more) efficient reinforcement learning via posterior sampling.
In Advances in Neural Information Processing Systems, 2013.

[Panigrahy and Vishwanathan, 1998]
Rina Panigrahy and Sundar Vishwanathan.
An ${O}(\log^* n)$ approximation algorithm for the asymmetric
$p$-center problem.
Journal of Algorithms, 270 (2):0 259–268,

[Papadimitriou and Tsitsiklis, 1987]
Christos H. Papadimitriou and John N. Tsitsiklis.
The complexity of Markov decision processes.
Mathematics of Operations Research, 120 (3):0
441–450, 1987.

[Parr, 1998]
Ronald Parr.
Hierarchical Control and Learning for Markov Decision
PhD thesis, University of California, Berkeley, 1998.

[Parr and Russell, 1998]
Ronald Parr and Stuart Russell.
Reinforcement learning with hierarchies of machines.
In Advances in Neural Information Processing Systems, 1998.

[Parr et al., 2008]
Ronald Parr, Lihong Li, Gavin Taylor, Christopher Painter-Wakefield, and
Michael L. Littman.
An analysis of linear models, linear value-function approximation,
and feature selection for reinforcement learning.
In Proceedings of the International Conference on Machine
learning. ACM, 2008.

[Pickett and Barto, 2002]
Marc Pickett and Andrew G. Barto.
PolicyBlocks: An algorithm for creating useful macro-actions in
reinforcement learning.
In Proceedings of the International Conference on Machine
Learning, 2002.

[Precup, 2001]
Doina Precup.
Temporal abstraction in reinforcement learning.
PhD thesis, University of Massachusetts Amherst, 2001.

[Precup and Sutton, 1997]
Doina Precup and Richard S. Sutton.
Multi-time models for reinforcement learning.
In ICML Workshop on Modelling in Reinforcement Learning, 1997.

[Precup and Sutton, 1998]
Doina Precup and Richard S. Sutton.
Multi-time models for temporally abstract planning.
In Advances in Neural Information Processing Systems, 1998.

[Provost et al., 2006]
Jefferson Provost, Benjamin Kuipers, and Risto Miikkulainen.
Developing navigation behavior through self-organizing
distinctive-state abstraction.
Connection Science, 180 (2):0 159–172, 2006.

[Puterman, 2014]
Martin L. Puterman.
Markov decision processes: discrete stochastic dynamic
John Wiley & Sons, 2014.

[Quandt et al., 2017]
Lorna C. Quandt, Yune Sang Lee, and Anjan Chatterjee.
Neural bases of action abstraction.
Biological psychology, 129:0 314, 2017.

[Ranchod et al., 2015]
Pravesh Ranchod, Benjamin Rosman, and George Konidaris.
Nonparametric Bayesian reward segmentation for skill discovery
using inverse reinforcement learning.
In Proceedings of the Conference on Intelligent Robots and
Systems, 2015.

[Ravindran, 2003]
Balaraman Ravindran.
SMDP homomorphisms: An algebraic approach to abstraction in
semi Markov decision processes.
PhD thesis, University of Massachusetts Amherst, 2003.

[Ravindran and Barto, 2002]
Balaraman Ravindran and Andrew G. Barto.
Model minimization in hierarchical reinforcement learning.
In Proceedings of the International Symposium on Abstraction,
Reformulation, and Approximation, 2002.

[Ravindran and Barto, 2003]
Balaraman Ravindran and Andrew G. Barto.
Relativized options: Choosing the right transformation.
In Proceedings of the International Conference on Machine
Learning, 2003a.

[Ravindran and Barto, 2003]
Balaraman Ravindran and Andrew G. Barto.
SMDP homomorphisms: An algebraic approach to abstraction in
semi-Markov decision processes.
In Proceedings of the International Joint Conference on
Artificial Intelligence, 2003b.

[Ravindran and Barto, 2004]
Balaraman Ravindran and Andrew G. Barto.
Approximate homomorphisms: A framework for non-exact minimization in
Markov decision processes.
In Proceedings of the International Conference on Knowledge
Based Computer Systems, 2004.

[Reibman et al., 1989]
Andrew Reibman, Roger Smith, and Kishor Trivedi.
Markov and Markov reward model transient analysis: An overview of
numerical approaches.
European Journal of Operational Research, 400
(2):0 257–267, 1989.

[Riemer et al., 2018]
Matthew Riemer, Miao Liu, and Gerald Tesauro.
Learning abstract options.
In Advances in Neural Information Processing Systems, 2018.

[Rummery and Niranjan, 1994]
Gavin A. Rummery and Mahesan Niranjan.
On-line Q-learning using connectionist systems, volume 37.
University of Cambridge, Department of Engineering Cambridge, UK,

[Russell and Norvig, 2009]
Stuart Russell and Peter Norvig.
Artificial Intelligence: A Modern Approach.
Prentice Hall, 2009.

[Russell and Subramanian, 1995]
Stuart Russell and Devika Subramanian.
Provably Bounded-Optimal Agents.
Journal of Artificial Intelligence Research, 2:0
575–609, 1995.
ISSN 1076-9757.

[Sacerdoti, 1974]
Earl D. Sacerdoti.
Planning in a hierarchy of abstraction spaces.
Artificial Intelligence, 50 (2):0 115 – 135,

[Schmidhuber, 1991]
Jürgen Schmidhuber.
Reinforcement learning in Markovian and non-Markovian
In Advances in Neural Information Processing Systems, 1991.

[Schultz et al., 1997]
Wolfram Schultz, Peter Dayan, and P. Read Montague.
A neural substrate of prediction and reward.
Science, 2750 (5306):0 1593–1599, 1997.

[Schwarz, 1978]
Gideon Schwarz.
Estimating the dimension of a model.
The Annals of Statistics, 60 (2):0 461–464,

[Shalev-Shwartz and Ben-David, 2014]
Shai Shalev-Shwartz and Shai Ben-David.
Understanding Machine Learning: From Theory to Algorithms.
Cambridge University Press, 2014.

[Shannon, 1948]
Claude E. Shannon.
A mathematical theory of communication.
The Bell System Technical Journal, 27:0 379–423,

[Silver and Ciosek, 2012]
David Silver and Kamil Ciosek.
Compositional planning using optimal option models.
In Proceedings of the International Conference on Machine
Learning, 2012.

[Silver et al., 2020]
Tom Silver, Rohan Chitnis, Anurag Ajay, Josh Tenenbaum, and Leslie Pack
Learning skill hierarchies from predicate descriptions and
In AAAI Workshop on Generalization in Planning, 2020.

[Simon, 1957]
Herbert A. Simon.
Models of man; social and rational.
Wiley, 1957.

[Simon, 1972]
Herbert A. Simon.
Theories of bounded rationality.
Decision and organization, 10 (1):0 161–176,

[Sims, 2016]
Chris R. Sims.
Rate–distortion theory and human perception.
Cognition, 152:0 181–198, 2016.

[Sims, 2018]
Chris R. Sims.
Efficient coding explains the universal law of generalization in
human perception.
Science, 3600 (6389):0 652–656, 2018.

[Şimşek and Barto, 2004]
Özgür Şimşek and Andrew G. Barto.
Using relative novelty to identify useful temporal abstractions in
reinforcement learning.
In Proceedings of the International Conference on Machine
Learning. ACM, 2004.

[Şimşek and Barto, 2009]
Özgür Şimşek and Andrew G. Barto.
Skill characterization based on betweenness.
In Advances in Neural Information Processing Systems, 2009.

[Şimşek et al., 2005]
Özgür Şimşek, Alicia P. Wolfe, and Andrew G. Barto.
Identifying useful subgoals in reinforcement learning by local graph
In Proceedings of the International Conference on Machine
Learning, 2005.

[Singh, 1992]
Satinder Singh.
Scaling reinforcement learning algorithms by learning variable
temporal resolution models.
In Proceedings of the International Machine Learning
Conference, 1992.

[Singh et al., 1995]
Satinder Singh, Tommi Jaakkola, and Michael I. Jordan.
Reinforcement learning with soft state aggregation.
In Advances in Neural Information Processing Systems, 1995.

[Singh et al., 2005]
Satinder Singh, Andrew G. Barto, and Nuttapong Chentanez.
Intrinsically motivated reinforcement learning.
In Advances in Neural Information Processing Systems, 2005.

[Snel and Whiteson, 2011]
Matthijs Snel and Shimon Whiteson.
Multi-task reinforcement learning: Shaping and feature selection.
In Proceedings of the European Workshop on Reinforcement
Learning, 2011.

[Solway et al., 2014]
Alec Solway, Carlos Diuk, Natalia Córdova, Debbie Yee, Andrew G. Barto,
Yael Niv, and Matthew Botvinick.
Optimal behavioral hierarchy.
PLoS computational biology, 100 (8):0
e1003779, 2014.

[Stolle and Precup, 2002]
Martin Stolle and Doina Precup.
Learning options in reinforcement learning.
In Proceedings of the International Symposium on Abstraction,
Reformulation, and Approximation, 2002.

[Strehl and Littman, 2005]
Alexander L. Strehl and Michael L. Littman.
A theoretical analysis of model-based interval estimation.
In Proceedings of the International Conference on Machine
Learning, 2005.

[Strehl et al., 2006]
Alexander L. Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L.
PAC model-free reinforcement learning.
In Proceedings of the International Conference on Machine
Learning, 2006.

[Strehl et al., 2009]
Alexander L. Strehl, Lihong Li, and Michael L. Littman.
Reinforcement learning in finite MDPs: PAC analysis.
Journal of Machine Learning Research, 10:0 2413–2444,

[Strouse and Schwab, 2017]
DJ Strouse and David J. Schwab.
The deterministic information bottleneck.
Neural Computation, 290 (6):0 1611–1630,

[Sun et al., 2019]
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford.
Model-based RL in contextual decision processes: PAC bounds and
exponential improvements over model-free approaches.
In Proceedings of the Conference on Learning Theory, 2019.

[Sutter et al., 2015]
Tobias Sutter, David Sutter, Peyman Mohajerin Esfahani, and John Lygeros.
Efficient approximation of channel capacities.
IEEE Transactions on Information Theory, 61:0
1649–1666, 2015.

[Sutton, 1988]
Richard S. Sutton.
Learning to predict by the methods of temporal differences.
Machine Learning, 30 (1):0 9–44, 1988.

[Sutton, 1992]
Richard S. Sutton.
Introduction: The challenge of reinforcement learning.
In Reinforcement Learning, pages 1–3. Springer, 1992.

[Sutton, 1996]
Richard S. Sutton.
Generalization in reinforcement learning: Successful examples using
sparse coarse coding.
In Advances in Neural Information Processing Systems, 1996.

[Sutton, 2004]
Richard S. Sutton.
The reward hypothesis, 2004.

[Sutton and Barto, 1998]
Richard S. Sutton and Andrew G. Barto.
Reinforcement Learning: An Introduction.
MIT Press, 1998.

[Sutton and Barto, 2018]
Richard S. Sutton and Andrew G. Barto.
Reinforcement Learning: An Introduction.
MIT press, 2018.

[Sutton et al., 1999]
Richard S. Sutton, Doina Precup, and Satinder Singh.
Between MDPs and semi-MDPs: A framework for temporal abstraction
in reinforcement learning.
Artificial Intelligence, 1999.

[Sutton et al., 2000]
Richard S. Sutton, David A. McAllester, Satinder Singh, and Yishay Mansour.
Policy gradient methods for reinforcement learning with function
In Advances in Neural Information Processing Systems, 2000.

[Taïga et al., 2018]
Adrien Ali Taïga, Aaron Courville, and Marc G. Bellemare.
Approximate exploration through state abstraction.
arXiv preprint arXiv:1808.09819, 2018.

[Talvitie, 2017]
Erik Talvitie.
Self-correcting models for model-based reinforcement learning.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2017.

[Taylor et al., 2008]
Jonathan Taylor, Doina Precup, and Prakash Panagaden.
Bounding performance loss in approximate MDP homomorphisms.
In Advances in Neural Information Processing Systems, 2008.

[Thrun, 1996]
Sebastian Thrun.
Is learning the $n$-th thing any easier than learning the first?
In Advances in Neural Information Processing Systems, 1996.

[Thrun and Schwartz, 1995]
Sebastian Thrun and Anton Schwartz.
Finding structure in reinforcement learning.
In Advances in Neural Information Processing Systems, 1995.

[Tishby et al., 1999]
Naftali Tishby, Fernando C. Pereira, and William Bialek.
The information bottleneck method.
In Proceedings of the Allerton Conference on Communication,
Control, and Computing, 1999.

[Tiwari and Thomas, 2019]
Saket Tiwari and Philip S. Thomas.
Natural option critic.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2019.

[Topin et al., 2015]
Nicholay Topin, Nicholas Haltmeyer, Shawn Squire, John Winder, Marie
desJardins, and James MacGlashan.
Portable option discovery for automated learning transfer in
object-oriented Markov decision processes.
In Proceedings of the International Joint Conference on
Artificial Intelligence, 2015.

[Tseng, 1990]
Paul Tseng.
Solving ${H}$-horizon, stationary Markov decision problems in time
proportional to $\log({H})$.
Operations Research Letters, 90 (5):0
287–297, 1990.

[Uther and Veloso, 1998]
William T.B. Uther and Manuela M. Veloso.
Tree based discretization for continuous state space reinforcement
In Proceedings of the AAAI Conference on Artificial
Intelligence, 1998.

[Valiant, 1984]
Leslie G. Valiant.
A theory of the learnable.
Communications of the ACM, 270 (11):0
1134–1142, 1984.

[van Hasselt, 2010]
Hado van Hasselt.
Double Q-learning.
In Advances in Neural Information Processing Systems, 2010.

[Van Niekerk et al., 2019]
Benjamin Van Niekerk, Steven James, Adam Earle, and Benjamin Rosman.
Composing value functions in reinforcement learning.
In Proceedings of the International Conference on Machine
Learning, 2019.

[Van Roy, 2006]
Benjamin Van Roy.
Performance loss bounds for approximate value iteration with state
Mathematics of Operations Research, 310 (2):0
234–244, 2006.

[van Seijen and Sutton, 2015]
Harm van Seijen and Richard S. Sutton.
A deeper look at planning as learning from replay.
In Proceedings of the International Conference on Machine
learning, 2015.

[van Seijen et al., 2014]
Harm van Seijen, Shimon Whiteson, and Leon Kester.
Efficient abstraction selection in reinforcement learning.
Computational Intelligence, 300 (4):0
657–699, 2014.

[Vapnik and Chervonenkis, 1971]
Vladimir N. Vapnik and Aleksei Y. Chervonenkis.
On the uniform convergence of relative frequencies of events to their
Theory of Probability & Its Applications, 160
(2):0 264–280, 1971.

[Veness et al., 2011]
Joel Veness, Kee Siong Ng, Marcus Hutter, William Uther, and David Silver.
A Monte-Carlo AIXI approximation.
Journal of Artificial Intelligence Research, 400
(1):0 95–142, 2011.

[Vezhnevets et al., 2017]
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max
Jaderberg, David Silver, and Koray Kavukcuoglu.
Feudal networks for hierarchical reinforcement learning.
In Proceedings of the International Conference on Machine
Learning, 2017.

[Walsh et al., 2006]
Thomas J. Walsh, Lihong Li, and Michael L. Littman.
Transferring state abstractions between MDPs.
In ICML Workshop on Structural Knowledge Transfer for Machine
Learning, 2006.

[Walsh et al., 2009]
Thomas J. Walsh, István Szita, Carlos Diuk, and Michael L. Littman.
Exploring compact reinforcement-learning representations with linear
In Proceedings of the Conference on Uncertainty in Artificial
Intelligence, 2009.

[Walsh et al., 2010]
Thomas J. Walsh, Sergiu Goschin, and Michael L. Littman.
Integrating sample-based planning and model-based reinforcement
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2010.

[Walsh et al., 2011]
Thomas J. Walsh, Daniel K. Hewlett, and Clayton T. Morrison.
Blending autonomous exploration and apprenticeship learning.
In Advances in Neural Information Processing Systems, 2011.

[Watkins and Dayan, 1992]
Christopher J.C.H. Watkins and Peter Dayan.
Machine learning, 80 (3-4):0 279–292, 1992.

[Werchan et al., 2015]
Denise M. Werchan, Anne G.E. Collins, Michael J. Frank, and Dima Amso.
8-month-old infants spontaneously learn and generalize hierarchical
Psychological science, 260 (6):0 805–815,

[Whiteson et al., 2007]
Shimon Whiteson, Matthew E. Taylor, and Peter Stone.
Adaptive tile coding for value function approximation.
Technical report, University of Texas at Austin, 2007.

[Whitt, 1978]
Ward Whitt.
Approximations of dynamic programs, i.
Mathematics of Operations Research, 30 (3):0
231–243, 1978.

[Whitt, 1979]
Ward Whitt.
Approximations of dynamic programs, ii.
Mathematics of Operations Research, 40 (2):0
179–185, 1979.

[Wiering and Schmidhuber, 1997]
Marco Wiering and Jürgen Schmidhuber.
Adaptive Behavior, 60 (2):0 219–246, 1997.

[Williams and Baird, 1993]
Ronald J. Williams and Leemon C. Baird.
Tight performance bounds on greedy policies based on imperfect value
Technical report, College of Computer Science, Northeastern
University, 1993.

[Wilson et al., 2007]
Aaron Wilson, Alan Fern, Soumya Ray, and Prasad Tadepalli.
Multi-task reinforcement learning: a hierarchical Bayesian
In Proceedings of the International Conference on Machine
learning, 2007.

[Winder et al., 2020]
John Winder, Stephanie Milani, Matthew Landen, Erebus Oh, Shane Parr, Shawn
Squire, Marie desJardins, and Cynthia Matuszek.
Planning with abstract learned models while learning transferable
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2020.

[Wolpert, 1996]
David H. Wolpert.
The lack of a priori distinctions between learning algorithms.
Neural computation, 80 (7), 1996.

[Zhang and Whiteson, 2019]
Shangtong Zhang and Shimon Whiteson.
DAC: The double actor-critic architecture for learning options.
In Advances in Neural Information Processing Systems, 2019.