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
Neuro-Dynamic Programming: NDP
Bertsekas, D. P. (2001) · Encyclopedia of Optimization · doi:10.1007/0-306-48332-7_333 · Cited by 1,466
Planning in a hierarchy of abstraction spaces
Sacerdoti, E. D. (1974) · Artificial Intelligence · doi:10.1016/0004-3702(74)90026-5 · Cited by 1,155
Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
Boutilier, C., Dean, T., & Hanks, S. (1999) · Journal of Artificial Intelligence Research · doi:10.1613/jair.575 · Cited by 1,074
Reinforcement learning for robots using neural networks
Lin, L.-J. (1992) · Defense Technical Information Center (DTIC) · Cited by 1,042
Learning and executing generalized robot plans
Fikes, R. E., Hart, P. E., & Nilsson, N. J. (1972) · Artificial Intelligence · doi:10.1016/0004-3702(72)90051-3 · Cited by 1,019
On the Convergence of Stochastic Iterative Dynamic Programming Algorithms
Jaakkola, T., Jordan, M. I., & Singh, S. P. (1994) · Neural Computation · doi:10.1162/neco.1994.6.6.1185 · Cited by 770
Reinforcement Learning with Hierarchies of Machines
Parr, R., & Russell, S. (1997) · Cited by 618
Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms
Singh, S., Jaakkola, T., Littman, M. L., & Szepesvári, C. (2000) · Machine Learning · doi:10.1023/a:1007678930559 · Cited by 609
Dayan, P., & Hinton, G. E. (1992) · Cited by 540
O-Plan: The open planning architecture
Currie, K., & Tate, A. (1991) · Artificial Intelligence · doi:10.1016/0004-3702(91)90024-e · Cited by 407
Exploiting Structure in Policy Construction
Boutilier, C. E., Dearden, R., & Goldszmidt, M. (1995) · Cited by 346
Transfer of learning by composing solutions of elemental sequential tasks
Singh, S. P. (1992) · Machine Learning · doi:10.1007/bf00992700 · Cited by 288
Macro-operators: A weak method for learning
Korf, R. E. (1985) · Artificial Intelligence · doi:10.1016/0004-3702(85)90012-8 · Cited by 287
The MAXQ Method for Hierarchical Reinforcement Learning
Dietterich, T. G. (1998) · Cited by 285
Self-citationHierarchical control and learning for markov decision processes
Parr, R., & Russell, S. (1998) · Cited by 221
Hierarchical Solution of Markov Decision Processes using Macro-actions
Hauskrecht, M., Meuleau, N., Kaelbling, L. P., Dean, T., & Boutilier, C. E. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.7381 · Cited by 218
Planning in a hierarchy of abstraction spaces
Sacerdott, E. D. (1973) · Cited by 176
Watkins, C. J. C. H. (1993) · UCL Discovery (University College London) · Cited by 166
On the Convergence of Stochastic Iterative Dynamic Programming Algorithms
Jaakkola, T., Jordan, M. I., & Singh, S. P. (1993) · Defense Technical Information Center (DTIC) · doi:10.21236/ada276517 · Cited by 165
Decomposition Techniques for Planning in Stochastic Domains
Dean, T., & Lin, S. (1995) · International Joint Conference on Artificial Intelligence · Cited by 154
Learning abstraction hierarchies for problem solving
Knoblock, C. A. (1990) · Cited by 133
Between MOPs and Semi-MOP: Learning, Planning & Representing Knowledge at Multiple Temporal Scales
Sutton, R. S., Precup, D., & Singh, S. P. (1998) · Cited by 74
Module-Based Reinforcement Learning: Experiments with a Real Robot
Kalmár, Z., Szepesvári, C., & Lörincz, A. (1998) · Machine Learning · doi:10.1023/a:1007440607681 · Cited by 49
Improved Switching among Temporally Abstract Actions
Sutton, R. S., Singh, S. P., Precup, D., & Ravindran, B. (1998) · Cited by 33
Sutton, R. S., Precup, D., & Singh, S. P. (1998) · ScholarWorks@UMassAmherst (University of Massachusetts Amherst) · Cited by 23
Investigating production system representations for non-combinatorial match
Tambe, M., & Rosenbloom, P. S. (1994) · Artificial Intelligence · doi:10.1016/0004-3702(94)90097-3 · Cited by 20
Transfer of Learning by Composing Solutions of Elemental Sequential Tasks
Singh, S. P. (1992) · Springer eBooks · doi:10.1007/978-1-4615-3618-5_6 · Cited by 20
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
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.