The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
Near-Optimal Reinforcement Learning in Polynomial Time
Open accessOverview
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
Reinforcement Learning: An Introduction
Sutton, R. S., & Barto, A. G. (1998) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.1998.712192 · Cited by 27,225
Reinforcement Learning: An Introduction
(2005) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2004.842673 · Cited by 24,496
Advances in neural information processing systems 7
(1996) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(96)90463-0 · Cited by 14,281
Watkins, C. J. C. H., & Dayan, P. (1992) · Machine Learning · doi:10.1007/bf00992698 · Cited by 9,083
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
Introduction to Reinforcement Learning
Sutton, R. S., & Barto, A. G. (1998) · The MIT Press eBooks · Cited by 6,855
Markov Decision Processes: Discrete Stochastic Dynamic Programming
Puterman, M. L. (1994) · Wiley Series in Probability and Statistics · doi:10.1002/9780470316887 · Cited by 6,024
Watkins, C. (1989) · OpenGrey (Institut de l'Information Scientifique et Technique) · doi:10.17863/cam.132164 · Cited by 5,297
Parallel and Distributed Computation: Numerical Methods
Bertsekas, D. P., & Tsitsiklis, J. N. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 5,293
Learning to predict by the methods of temporal differences
Sutton, R. S. (1988) · Machine Learning · doi:10.1007/bf00115009 · Cited by 5,148
Cited by
Reinforcement learning in robotics: A survey
Kober, J., Bagnell, J. A., & Peters, J. (2013) · The International Journal of Robotics Research · doi:10.1177/0278364913495721 · Cited by 3,160
Transfer Learning for Reinforcement Learning Domains: A Survey
Taylor, M. E., & Stone, P. (2009) · doi:10.5555/1577069.1755839 · Cited by 1,488
(2015) · Journal of Machine Learning Research · Cited by 1,119
Algorithms for Reinforcement Learning
Szepesvári, C. (2010) · Synthesis Lectures on Artificial Intelligence and Machine Learning · doi:10.1007/978-3-031-01551-9 · Cited by 1,049
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401 · Cited by 976
Information-seeking, curiosity, and attention: computational and neural mechanisms
Gottlieb, J., Oudeyer, P.-Y., Lopes, M., & Baranes, A. (2013) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2013.09.001 · Cited by 784
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
Reinforcement Learning and Markov Decision Processes
van Otterlo, M., & Wiering, M. (2012) · Adaptation, Learning, and Optimization · doi:10.1007/978-3-642-27645-3_1 · Cited by 628
Noisy Networks for Exploration
Fortunato, M., Azar, M. G., Piot, B., Menick, J., Osband, I., Graves, A., Mnih, V., Munos, R., Hassabis, D., Pietquin, O., et al. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.10295 · Cited by 543
An Application of Reinforcement Learning to Aerobatic Helicopter Flight
Abbeel, P., Coates, A., Quigley, M., & Ng, A. Y. (2007) · Advances in Neural Information Processing Systems 19 · doi:10.7551/mitpress/7503.003.0006 · Cited by 535
Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
Shalev-Shwartz, S., Shammah, S., & Shashua, A. (2016) · arXiv · doi:10.48550/arxiv.1610.03295 · Cited by 509
“See also [39, 38, 18, 8].”
VIME: Variational Information Maximizing Exploration
Houthooft, R., Chen, X., Duan, Y., Schulman, J., Turck, F. D., & Abbeel, P. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.09674 · Cited by 472
Deep Exploration via Bootstrapped DQN
Osband, I., Blundell, C., Pritzel, A., & Roy, B. V. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.04621 · Cited by 434
An analysis of model-based Interval Estimation for Markov Decision Processes
Strehl, A. L., & Littman, M. L. (2008) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2007.08.009 · Cited by 428
If multi-agent learning is the answer, what is the question?
Shoham, Y., Powers, R., & Grenager, T. (2007) · Artificial Intelligence · doi:10.1016/j.artint.2006.02.006 · Cited by 410
PAC model-free reinforcement learning
Strehl, A. L., Li, L., Wiewiora, E., Langford, J., & Littman, M. L. (2006) · Proceedings of the 23rd international conference on Machine learning - ICML '06 · doi:10.1145/1143844.1143955 · Cited by 384
Reinforcement learning improves behaviour from evaluative feedback
Littman, M. L. (2015) · Nature · doi:10.1038/nature14540 · Cited by 368
Parameter Space Noise for Exploration
Plappert, M., Houthooft, R., Dhariwal, P., Sidor, S., Chen, R. Y., Chen, X., Asfour, T., Abbeel, P., & Andrychowicz, M. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.01905 · Cited by 346
Reinforcement Learning: A Tutorial Survey and Recent Advances
Gosavi, A. (2009) · INFORMS Journal on Computing · doi:10.1287/ijoc.1080.0305 · Cited by 326
A review of reinforcement learning for autonomous building energy management
Mason, K., & Grijalva, S. (2019) · Computers & Electrical Engineering · doi:10.1016/j.compeleceng.2019.07.019 · Cited by 306
PAC Bounds for Multi-armed Bandit and Markov Decision Processes
Even-Dar, E., Mannor, S., & Mansour, Y. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45435-7_18 · Cited by 298
#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning
Tang, H., Houthooft, R., Foote, D., Stooke, A., Chen, X., Duan, Y., Schulman, J., Turck, F. D., & Abbeel, P. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1611.04717 · Cited by 296
Incentivizing Exploration In Reinforcement Learning With Deep Predictive Models
Stadie, B. C., Levine, S., & Abbeel, P. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1507.00814 · Cited by 280
Autonomous helicopter control using reinforcement learning policy search methods
Bagnell, J. A., & Schneider, J. G. (2002) · Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No.01CH37164) · doi:10.1109/robot.2001.932842 · Cited by 276
Modular Multitask Reinforcement Learning with Policy Sketches
Andreas, J., Klein, D., & Levine, S. (2016) · arXiv · doi:10.48550/arxiv.1611.01796 · Cited by 274
Finding Useful Questions: On Bayesian Diagnosticity, Probability, Impact, and Information Gain.
Nelson, J. D. (2005) · Psychological Review · doi:10.1037/0033-295x.112.4.979 · Cited by 253
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
Go-Explore: a New Approach for Hard-Exploration Problems
Ecoffet, A., Huizinga, J., Lehman, J., Stanley, K. O., & Clune, J. (2019) · arXiv · doi:10.48550/arxiv.1901.10995 · Cited by 205
An information-theoretic approach to curiosity-driven reinforcement learning
Still, S., & Precup, D. (2012) · Theory in Biosciences · doi:10.1007/s12064-011-0142-z · Cited by 165
Safe Exploration in Markov Decision Processes
Moldovan, T. M., & Abbeel, P. (2012) · arXiv · doi:10.48550/arxiv.1205.4810 · Cited by 152
“Provably efficient exploration is a recurring theme in reinforcement learning (Strehl & Littman, 2005; Li et al., 2008; Brafman & Tennenholtz, 2001; Kearns & Singh, 2002; Kolter & Ng, 2009).”
BackgroundMinimax Regret Bounds for Reinforcement Learning
Azar, M. G., Osband, I., & Munos, R. (2017) · arXiv · doi:10.48550/arxiv.1703.05449 · Cited by 124
VariBAD: A Very Good Method for Bayes-Adaptive Deep RL via Meta-Learning
Zintgraf, L., Shiarlis, K., Igl, M., Schulze, S., Gal, Y., Hofmann, K., & Whiteson, S. (2019) · arXiv · doi:10.48550/arxiv.1910.08348 · Cited by 112
(2007) · National Conference on Artificial Intelligence · Cited by 98
Some Considerations on Learning to Explore via Meta-Reinforcement Learning
Stadie, B. C., Yang, G., Houthooft, R., Chen, X., Duan, Y., Wu, Y., Abbeel, P., & Sutskever, I. (2018) · arXiv · doi:10.48550/arxiv.1803.01118 · Cited by 74
“There exists a large body of RL work addressing this problem [10, 5, 11].”
BackgroundKatz, D., Pyuro, Y., & Brock, O. (2008) · Robotics: Science and Systems IV · doi:10.15607/rss.2008.iv.033 · Cited by 70
Contextual Markov Decision Processes
Hallak, A., Di Castro, D., & Mannor, S. (2015) · arXiv · doi:10.48550/arxiv.1502.02259 · Cited by 65
A Survey of Exploration Methods in Reinforcement Learning
Amin, S., Gomrokchi, M., Satija, H., van Hoof, H., & Precup, D. (2021) · arXiv · doi:10.48550/arxiv.2109.00157 · Cited by 41
Count-based exploration with the successor representation
Machado, M. C., Bellemare, M. G., & Bowling, M. (2020) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v34i04.5955 · Cited by 19
PAC Reinforcement Learning with Rich Observations
Krishnamurthy, A., Agarwal, A., & Langford, J. (2016) · arXiv · doi:10.48550/arxiv.1602.02722 · Cited by 13
“Approaches to RL with a weak dependence on these quantities exist (Kearns et al., 2002), but suffer from an exponential dependence on the time horizon—with K actions and a horizon of H , they require K samples.”
iCyberGuard: A FlipIt Game for Enhanced Cybersecurity in IIoT
Chen, X., Cao, W., Chen, L., Han, J., Yang, M., Wang, Z., & Wang, F.-Y. (2024) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2024.3443174 · Cited by 10
Efficient PAC Reinforcement Learning in Regular Decision Processes
Ronca, A., & De Giacomo, G. (2021) · Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2021/279 · Cited by 6
A Study of Global and Episodic Bonuses for Exploration in Contextual MDPs
Henaff, M., Jiang, M., & Raileanu, R. (2023) · arXiv · doi:10.48550/arxiv.2306.03236 · Cited by 1
“Many theoretical works exist which propose provably efficient algorithms for tabular or linear MDPs (Kearns & Singh, 2002; Brafman & Tennenholtz, 2002; Strehl & Littman, 2006; Jin et al., 2020; Cai et al., 2020; Agarwal et al., 2020; Kolter & Ng, 2009; Fruit & Lazaric, 2017; Fruit et al., 2018a;b;…”
Background
Metadata
- Authors
- Kearns, M., & Singh, S.
- Venue
- Machine Learning
- Published
- 2002-11
- Volume
- 49
- Issue
- 2-3
- Pages
- 209-232
- ISSN
- 0885-6125 (ISSN-L)
- 1573-0565
- OpenAlex
- W2489939061
- Cited by
- 792
- References
- 42
- FWCI
- 12.38
- Type
- journal article
- Language
- en
- Open access
- bronze
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.