Dynamic abstraction in reinforcement learning via clustering
The DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
Abstract
We consider a graph theoretic approach for automatic construction of options in a dynamic environment. A map of the environment is generated on-line by the learning agent, representing the topological structure of the state transitions. A clustering algorithm is then used to partition the state space to different regions. Policies for reaching the different parts of the space are separately learned and added to the model in a form of options (macro-actions). The options are used for accelerating the Q-Learning algorithm. We extend the basic algorithm and consider building a map that includes preliminary indication of the location of "interesting" regions of the state space, where the value gradient is significant and additional exploration might be beneficial. Experiments indicate significant speedups, especially in the initial learning phase.
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
Jain, A. K., Murty, M. N., & Flynn, P. J. (1999) · ACM Computing Surveys · doi:10.1145/331499.331504 · Cited by 13,199 · cited 1×
“We refer the reader to Jain and Dubes (1988) and Hochbaum (1996) for a detailed discussion on the complexity of various variants of clustering algorithms and to Jain et al. (1999) for a survey of the vast number of applications.”
BackgroundWatkins, C. J. C. H., & Dayan, P. (1992) · Machine Learning · doi:10.1007/bf00992698 · Cited by 9,083
Algorithms for Clustering Data
Sarle, W. S. (1990) · Technometrics · doi:10.1080/00401706.1990.10484648 · Cited by 7,865
Cluster Analysis for Applications
(1973) · Elsevier eBooks · doi:10.1016/c2013-0-06161-0 · Cited by 5,080 · cited 1×
“Given a choice of f and g we applied the so-called agglomerative approach (Anderberg, 1973; Jain & Dubes, 1988).”
Method(2012) · Encyclopedia of the Sciences of Learning · doi:10.1007/978-1-4419-1428-6_5086 · Cited by 3,515
Neuronlike adaptive elements that can solve difficult learning control problems
Barto, A. G., Sutton, R. S., & Anderson, C. W. (1983) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/tsmc.1983.6313077 · Cited by 3,233 · cited 2×
“The first approach is to consider a limited space of control strategies and search this space directly (Moriarty et al., 1999), or within an actor-critic framework (see Barto et al., 1983; Baxter & Bartlett, 2001).”
BackgroundBetween MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning
Sutton, R. S., Precup, D., & Singh, S. (1999) · Artificial Intelligence · doi:10.1016/s0004-3702(99)00052-1 · Cited by 3,119 · cited 1×
“The third approach is to decompose the control to a hierarchy of several simpler tasks and learn each of them independently (e.g., Dayan & Hinton, 1993, Dietterich, 2000, Sutton et al., 1999, see Barto & Mahadevan, 2003 for a detailed recent review).”
Approximation Algorithms for NP-Hard Problems
(1997) · ACM SIGACT News · doi:10.1145/261342.571216 · Cited by 3,103 · cited 1×
“We refer the reader to Jain and Dubes (1988) and Hochbaum (1996) for a detailed discussion on the complexity of various variants of clustering algorithms and to Jain et al. (1999) for a survey of the vast number of applications.”
BackgroundSelf-improving reactive agents based on reinforcement learning, planning and teaching
Lin, L.-J. (1992) · Machine Learning · doi:10.1007/bf00992699 · Cited by 1,564 · cited 1×
“Learning an option: After clusters have been chosen, a local policy for reaching neighboring clusters is learned by an Experience Replay (Lin, 1992) procedure.”
MethodHierarchical Reinforcement Learning with the MAXQ Value Function Decomposition
Dietterich, T. G. (2000) · Journal of Artificial Intelligence Research · doi:10.1613/jair.639 · Cited by 1,435 · cited 1×
“The third approach is to decompose the control to a hierarchy of several simpler tasks and learn each of them independently (e.g., Dayan & Hinton, 1993, Dietterich, 2000, Sutton et al., 1999, see Barto & Mahadevan, 2003 for a detailed recent review).”
Cited by
Hierarchical 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
Hierarchically 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
Model-based Reinforcement Learning: A Survey
M. Moerland, T., Broekens, J., Plaat, A., & M. Jonker, C. (2023) · Foundations and Trends in Machine Learning · doi:10.1561/2200000086 · Cited by 524
Identifying useful subgoals in reinforcement learning by local graph partitioning
Şimşek, Ö., Wolfe, A. P., & Barto, A. G. (2005) · Proceedings of the 22nd international conference on Machine learning - ICML '05 · doi:10.1145/1102351.1102454 · Cited by 238
“The utility of access states as subgoals has been argued previously in the literature [9, 10, 11, 12].”
BackgroundLanguage as an Abstraction for Hierarchical Deep Reinforcement Learning
Jiang, Y., Gu, S., Murphy, K., & Finn, C. (2019) · arXiv · doi:10.48550/arxiv.1906.07343 · Cited by 109
Metadata
- Authors
- Mannor, S., Menache, I., Hoze, A., & Klein, U.
- Venue
- Twenty-first international conference on Machine learning - ICML '04
- Publisher
- ACM Press
- Published
- 2004
- Pages
- 71
- OpenAlex
- W2160808139
- Cited by
- 191
- References
- 19
- Type
- conference abstract
- Language
- en
- Open access
- closed
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.