Integrating Sample-Based Planning and Model-Based Reinforcement Learning
Open accessThe DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
Abstract
Recent advancements in model-based reinforcement learning have shown that the dynamics of many structured domains (e.g. DBNs) can be learned with tractable sample complexity, despite their exponentially large state spaces. Unfortunately, these algorithms all require access to a planner that computes a near optimal policy, and while many traditional MDP algorithms make this guarantee, their computation time grows with the number of states. We show how to replace these over-matched planners with a class of sample-based planners — whose computation time is independent of the number of states — without sacrificing the sample-efficiency guarantees of the overall learning algorithms. To do so, we define sufficient criteria for a sample-based planner to be used in such a learning system and analyze two popular sample-based approaches from the literature. We also introduce our own sample-based planner, which combines the strategies from these algorithms and still meets the criteria for integration into our learning system. In doing so, we define the first complete RL solution for compactly represented (exponentially sized) state spaces with efficiently learnable dynamics that is both sample efficient and whose computation time does not grow rapidly with the number of states.
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
Markov decision processes: Discrete stochastic dynamic programming
Hazeghi, K., & Puterman, M. L. (1995) · Journal of the American Statistical Association · doi:10.2307/2291177 · Cited by 8,037
Stochastic dynamic programming with factored representations
Boutilier, C., Dearden, R., & Goldszmidt, M. (2000) · Artificial Intelligence · doi:10.1016/s0004-3702(00)00033-3 · Cited by 361
Cited by
A Survey of Monte Carlo Tree Search Methods
Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., & Colton, S. (2012) · IEEE Transactions on Computational Intelligence and AI in Games · doi:10.1109/tciaig.2012.2186810 · Cited by 2,970
“Relative pruning was found to increase the win rate of the Go program L IN G O against GNU G O 3.8 by approximately 3% [106].”
BackgroundInfluentialLee, J. H., Shin, J., & Realff, M. J. (2018) · Computers & Chemical Engineering · doi:10.1016/j.compchemeng.2017.10.008 · Cited by 387
The ubiquity of model-based reinforcement learning
Doll, B. B., Simon, D. A., & Daw, N. D. (2012) · Current Opinion in Neurobiology · doi:10.1016/j.conb.2012.08.003 · Cited by 380
Deliberation for autonomous robots: A survey
Ingrand, F., & Ghallab, M. (2017) · Artificial Intelligence · doi:10.1016/j.artint.2014.11.003 · Cited by 309
“A few structured representations have been explored, among which: factored MDPs with compact DBN-like representations [219], hierarchical RL methods [60, 144], and relational RL methods [67].”
Background
Metadata
- Authors
- Walsh, T., Goschin, S., & Littman, M.
- Venue
- Proceedings of the AAAI Conference on Artificial Intelligence
- Published
- 2010-07-03
- Volume
- 24
- Issue
- 1
- Pages
- 612-617
- ISSN
- 2159-5399 (ISSN-L)
- 2374-3468
- OpenAlex
- W1515308897
- Cited by
- 104
- References
- 2
- FWCI
- 10.14
- Type
- conference paper
- 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.