The DOI matches its Crossref record; 37 of the 37 references it cites were found in a registry or an index.
Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition
Open accessAbstract
This paper presents a new approach to hierarchical reinforcement learning based on decomposing the target Markov decision process (MDP) into a hierarchy of smaller MDPs and decomposing the value function of the target MDP into an additive combination of the value functions of the smaller MDPs. The decomposition, known as the MAXQ decomposition, has both a procedural semantics---as a subroutine hierarchy---and a declarative semantics---as a representation of the value function of a hierarchical policy. MAXQ unifies and extends previous work on hierarchical reinforcement learning by Singh, Kaelbling, and Dayan and Hinton. It is based on the assumption that the programmer can identify useful subgoals and define subtasks that achieve these subgoals. By defining such subgoals, the programmer constrains the set of policies that need to be considered during reinforcement learning. The MAXQ value function decomposition can represent the value function of any policy that is consistent with the given hierarchy. The decomposition also creates opportunities to exploit state abstractions, so that individual MDPs within the hierarchy can ignore large parts of the state space. This is important for the practical application of the method. This paper defines the MAXQ hierarchy, proves formal results on its representational power, and establishes five conditions for the safe use of state abstractions. The paper presents an online model-free learning algorithm, MAXQ-Q, and proves that it converges with probability 1 to a kind of locally-optimal policy known as a recursively optimal policy, even in the presence of the five kinds of state abstraction. The paper evaluates the MAXQ representation and MAXQ-Q through a series of experiments in three domains and shows experimentally that MAXQ-Q (with state abstractions) converges to a recursively optimal policy much faster than flat Q learning. The fact that MAXQ learns a representation of the value function has an important benefit: it makes it possible to compute and execute an improved, non-hierarchical policy via a procedure similar to the policy improvement step of policy iteration. The paper demonstrates the effectiveness of this non-hierarchical execution experimentally. Finally, the paper concludes with a comparison to related work and a discussion of the design tradeoffs in hierarchical reinforcement learning.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1988) · Cited by 16,582
Bellman, R. E. (2010) · doi:10.1515/9781400835386 · Cited by 14,588
Watkins, C. J. C. H., & Dayan, P. (1992) · Machine Learning · doi:10.1007/bf00992698 · Cited by 9,083
Introduction to Reinforcement Learning
Sutton, R. S., & Barto, A. G. (1998) · The MIT Press eBooks · Cited by 6,855
Watkins, C. (1989) · OpenGrey (Institut de l'Information Scientifique et Technique) · doi:10.17863/cam.132164 · Cited by 5,297
Watkins, C. J. C. H., & Dayan, P. (1992) · Machine Learning · doi:10.1023/a:1022676722315 · Cited by 3,907
(2012) · Encyclopedia of the Sciences of Learning · doi:10.1007/978-1-4419-1428-6_5086 · Cited by 3,515
Dynamic Programming and Markov Processes.
Freimer, M., & Howard, R. A. (1961) · Journal of the American Statistical Association · doi:10.2307/2282268 · Cited by 3,378
Rete: A fast algorithm for the many pattern/many object pattern match problem
Forgy, C. L. (1982) · Artificial Intelligence · doi:10.1016/0004-3702(82)90020-0 · Cited by 2,634
On-line Q-learning Using Connectionist Systems
Rummery, G. A. (1994) · Cited by 1,477
Cited by
Deep learning in neural networks: an overview
Schmidhuber, J. (2015) · Neural Networks · doi:10.1016/j.neunet.2014.09.003 · Cited by 18,570
Brochu, E., Cora, V. M., & de Freitas, N. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1012.2599 · Cited by 2,011
Transfer Learning for Reinforcement Learning Domains: A Survey
Taylor, M. E., & Stone, P. (2009) · doi:10.5555/1577069.1755839 · Cited by 1,488
Benchmarking Deep Reinforcement Learning for Continuous Control
Duan, Y., Chen, X., Houthooft, R., Schulman, J., & Abbeel, P. (2016) · arXiv · doi:10.48550/arxiv.1604.06778 · Cited by 1,114
Recent Advances in Hierarchical Reinforcement Learning
Barto, A. G., & Mahadevan, S. (2003) · Discrete Event Dynamic Systems · doi:10.1023/a:1022140919877 · Cited by 1,024
Action understanding as inverse planning
Baker, C. L., Saxe, R., & Tenenbaum, J. B. (2009) · Cognition · doi:10.1016/j.cognition.2009.07.005 · Cited by 920
Reinforcement Learning and Dynamic Programming Using Function Approximators
Busoniu, L., Babuska, R., De Schutter, B., & Ernst, D. (2017) · CRC Press eBooks · doi:10.1201/9781439821091 · Cited by 919
Transfer Learning in Deep Reinforcement Learning: A Survey
Zhu, Z., Lin, K., Jain, A. K., & Zhou, J. (2023) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2023.3292075 · Cited by 861
“Well-known hierarchical RL frameworks include Feudal learning [44], Options framework [45], Hierarchical Abstract Machines [46], and MAXQ [47].”
MethodHierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation
Kulkarni, T. D., Narasimhan, K., Saeedi, A., & Tenenbaum, J. B. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1604.06057 · Cited by 770
Deep Reinforcement Learning: An Overview
Li, Y. (2017) · arXiv · doi:10.48550/arxiv.1701.07274 · Cited by 762
“, 1999), MAXQ (Dietterich, 2000) – strategic attentive writer to learn macro-actions (Vezhnevets et al.”
BackgroundHierarchically organized behavior and its neural foundations: A reinforcement learning perspective
Botvinick, M. M., Niv, Y., & Barto, A. G. (2009) · Cognition · doi:10.1016/j.cognition.2008.08.011 · Cited by 646
The Option-Critic Architecture
Bacon, P.-L., Harb, J., & Precup, D. (2017) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v31i1.10916 · Cited by 687
Human-level performance in 3D multiplayer games with population-based reinforcement learning
Jaderberg, M., Czarnecki, W. M., Dunning, I., Marris, L., Lever, G., Castañeda, A. G., Beattie, C., Rabinowitz, N. C., Morcos, A. S., Ruderman, A., et al. (2019) · Science · doi:10.1126/science.aau6249 · Cited by 662
Reinforcement learning algorithms: A brief survey
Shakya, A. K., Pillai, G., & Chakrabarty, S. (2023) · Expert Systems with Applications · doi:10.1016/j.eswa.2023.120495 · Cited by 656
Q-Learning Algorithms: A Comprehensive Classification and Applications
Jang, B., Kim, M., Harerimana, G., & Kim, J. W. (2019) · IEEE Access · doi:10.1109/access.2019.2941229 · Cited by 635
Cognitive effort: A neuroeconomic approach
Westbrook, A., & Braver, T. S. (2015) · Cognitive, Affective, & Behavioral Neuroscience · doi:10.3758/s13415-015-0334-y · Cited by 606
Hierarchical models of behavior and prefrontal function
Botvinick, M. M. (2008) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2008.02.009 · Cited by 532
“However, it has been noted in work on computational reinforcement learning that there is a natural relationship between temporal or policy abstraction and state abstraction, the treatment of non-identical stimuli or situations as equivalent [41, 42 ].”
BackgroundThe Geometry of Abstraction in the Hippocampus and Prefrontal Cortex
Bernardi, S., Benna, M. K., Rigotti, M., Munuera, J., Fusi, S., & Salzman, C. D. (2020) · Cell · doi:10.1016/j.cell.2020.09.031 · Cited by 489
Action, Outcome, and Value: A Dual-System Framework for Morality
Cushman, F. (2013) · Personality and Social Psychology Review · doi:10.1177/1088868313495594 · Cited by 473
Hierarchical Reinforcement Learning: A Comprehensive Survey
Pateria, S., Subagdja, B., Tan, A.-H., & Quek, C. (2022) · ACM Computing Surveys · doi:10.1145/3453160 · Cited by 461
Artificial intelligence: foundations of computational agents
(2010) · Choice Reviews Online · doi:10.5860/choice.48-2130 · Cited by 415
Quantum Reinforcement Learning
Dong, D., Chen, C., Li, H., & Tarn, T.-J. (2008) · IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) · doi:10.1109/tsmcb.2008.925743 · Cited by 410
A Closer Look at Invalid Action Masking in Policy Gradient Algorithms
Huang, S., & Ontañón, S. (2022) · The International FLAIRS Conference Proceedings · doi:10.32473/flairs.v35i.130584 · Cited by 435
“This technique is standard in previous work (Dietterich 2000).”
Reinforcement Learning for RoboCup Soccer Keepaway
Stone, P., Sutton, R. S., & Kuhlmann, G. (2005) · Adaptive Behavior · doi:10.1177/105971230501300301 · Cited by 387
Multiobjective Reinforcement Learning: A Comprehensive Overview
Liu, C., Xu, X., & Hu, D. (2015) · IEEE Transactions on Systems, Man, and Cybernetics: Systems · doi:10.1109/tsmc.2014.2358639 · Cited by 361
IQA: Visual Question Answering in Interactive Environments
Gordon, D., Kembhavi, A., Rastegari, M., Redmon, J., Fox, D., & Farhadi, A. (2018) · 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2018.00430 · Cited by 352
Neural Programmer-Interpreters
Reed, S., & de Freitas, N. (2015) · arXiv · doi:10.48550/arxiv.1511.06279 · Cited by 347
“Related problems have been studied in the literature on hierarchical reinforcement learning ( e.g. , Dietterich (2000); Andre & Russell (2001); Sutton et al. (1999) and Schaul et al. (2015)), imitation and apprenticeship learning ( e.g. , Kolter et al. (2008) and Rothkopf & Ballard (2013)) and…”
BackgroundReinforcement Learning: A Tutorial Survey and Recent Advances
Gosavi, A. (2009) · INFORMS Journal on Computing · doi:10.1287/ijoc.1080.0305 · Cited by 326
Recent Advances in Hierarchical Reinforcement Learning
Barto, A. G., & Mahadevan, S. (2003) · Discrete Event Dynamic Systems · doi:10.1023/a:1025696116075 · Cited by 317
Deliberation for autonomous robots: A survey
Ingrand, F., & Ghallab, M. (2017) · Artificial Intelligence · doi:10.1016/j.artint.2014.11.003 · Cited by 309
Probabilistic policy reuse in a reinforcement learning agent
Fernández, F., & Veloso, M. (2006) · Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems · doi:10.1145/1160633.1160762 · Cited by 275
Modular Multitask Reinforcement Learning with Policy Sketches
Andreas, J., Klein, D., & Levine, S. (2016) · arXiv · doi:10.48550/arxiv.1611.01796 · Cited by 274
A Survey on Transfer Learning for Multiagent Reinforcement Learning Systems
Silva, F. L. D., & Costa, A. H. R. (2019) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.11396 · Cited by 273
Robotic Urban Search and Rescue: A Survey from the Control Perspective
Liu, Y., & Nejat, G. (2013) · Journal of Intelligent & Robotic Systems · doi:10.1007/s10846-013-9822-x · Cited by 273
Learning Options in Reinforcement Learning
Stolle, M., & Precup, D. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45622-8_16 · Cited by 261
Finding approximate POMDP solutions through belief compression
Roy, N., Gordon, G., & Thrun, S. (2005) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1496 · Cited by 254
An object-oriented representation for efficient reinforcement learning
Diuk, C., Cohen, A., & Littman, M. L. (2008) · Proceedings of the 25th international conference on Machine learning - ICML '08 · doi:10.1145/1390156.1390187 · Cited by 226
Towards Continual Reinforcement Learning: A Review and Perspectives
Khetarpal, K., Riemer, M., Rish, I., & Precup, D. (2022) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.13673 · Cited by 224
Interplay of approximate planning strategies
Huys, Q. J. M., Lally, N., Faulkner, P., Eshel, N., Seifritz, E., Gershman, S. J., Dayan, P., & Roiser, J. P. (2015) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1414219112 · Cited by 207
Relay Policy Learning: Solving Long-Horizon Tasks via Imitation and Reinforcement Learning
Gupta, A., Kumar, V., Lynch, C., Levine, S., & Hausman, K. (2019) · arXiv · doi:10.48550/arxiv.1910.11956 · Cited by 153
Habits as action sequences: hierarchical action control and changes in outcome value
Dezfouli, A., Lingawi, N. W., & Balleine, B. W. (2014) · Philosophical Transactions of the Royal Society B: Biological Sciences · doi:10.1098/rstb.2013.0482 · Cited by 139
“(a) Planning mistakes Although mistakes can take various forms (see for example [28] for different types of optimality in hierarchical RL), an important type of planning mistake relates to the inflexibility of decisions after offline changes in outcome value.”
BackgroundHierarchical Reinforcement Learning: A Survey and Open Research Challenges
Hutsebaut-Buysse, M., Mets, K., & Latré, S. (2022) · Machine Learning and Knowledge Extraction · doi:10.3390/make4010009 · Cited by 129
System Design Perspective for Human-Level Agents Using Deep Reinforcement Learning: A Survey
Nguyen, N. D., Nguyen, T., & Nahavandi, S. (2017) · IEEE Access · doi:10.1109/access.2017.2777827 · Cited by 100
(2007) · National Conference on Artificial Intelligence · Cited by 98
From motor control to team play in simulated humanoid football
Liu, S., Lever, G., Wang, Z., Merel, J., Eslami, S. M. A., Hennes, D., Czarnecki, W. M., Tassa, Y., Omidshafiei, S., Abdolmaleki, A., et al. (2022) · Science Robotics · doi:10.1126/scirobotics.abo0235 · Cited by 88
RLHF Deciphered: A Critical Analysis of Reinforcement Learning from Human Feedback for LLMs
Chaudhari, S., Aggarwal, P., Murahari, V., Rajpurohit, T., Kalyan, A., Narasimhan, K., Deshpande, A., & Castro da Silva, B. (2026) · ACM Computing Surveys · doi:10.1145/3743127 · Cited by 92
Skill Induction and Planning with Latent Language
Sharma, P., Torralba, A., & Andreas, J. (2022) · Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/2022.acl-long.120 · Cited by 39
AI Research Considerations for Human Existential Safety (ARCHES)
Critch, A., & Krueger, D. (2020) · arXiv · doi:10.48550/arxiv.2006.04948 · Cited by 25
HRLB⌃2: A Reinforcement Learning Based Framework for Believable Bots
Arzate Cruz, C., & Ramirez Uresti, J. A. (2018) · Applied Sciences · doi:10.3390/app8122453 · Cited by 21
Procedural Content Generation: Better Benchmarks for Transfer Reinforcement Learning
Muller-Brockhausen, M., Preuss, M., & Plaat, A. (2021) · 2021 IEEE Conference on Games (CoG) · doi:10.1109/cog52621.2021.9619000 · Cited by 11
Learning with sparse reward in a gap junction network inspired by the insect mushroom body
Wei, T., Guo, Q., & Webb, B. (2024) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1012086 · Cited by 4
“This performance is comparable with the original results for this task presented in the work by Dietterich [37].”
Metadata
- Authors
- Dietterich, T. G.
- Venue
- Journal of Artificial Intelligence Research
- Publisher
- AI Access Foundation
- Published
- 2000-11-01
- Volume
- 13
- Pages
- 227-303
- ISSN
- 1076-9757 (ISSN-L)
- OpenAlex
- W2121517924
- Cited by
- 1,435
- References
- 37
- FWCI
- 29.57
- Type
- journal article
- Language
- en
- Open access
- diamond
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.