{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T09:51:06Z","timestamp":1782467466895,"version":"3.54.5"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[2002,11,1]],"date-time":"2002-11-01T00:00:00Z","timestamp":1036108800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2002,11,1]],"date-time":"2002-11-01T00:00:00Z","timestamp":1036108800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Machine Learning"],"published-print":{"date-parts":[[2002,11]]},"DOI":"10.1023\/a:1017984413808","type":"journal-article","created":{"date-parts":[[2002,12,30]],"date-time":"2002-12-30T09:36:44Z","timestamp":1041241004000},"page":"209-232","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":288,"title":["Near-Optimal Reinforcement Learning in Polynomial Time"],"prefix":"10.1007","volume":"49","author":[{"given":"Michael","family":"Kearns","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Satinder","family":"Singh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"395109_CR1","first-page":"686","volume-title":"Advances in neural information processing systems 2","author":"A. G. Barto","year":"1990","unstructured":"Barto, A. G., Sutton, R. S., & Watkins, C. (1990). Sequential decision problems and neural networks. In D. S. Touretzky (Ed.), Advances in neural information processing systems 2 (pp. 686\u2013693). San Mateo, CA: Morgan Kaufmann."},{"key":"395109_CR2","volume-title":"Dynamic programming: Deterministic and stochastic models","author":"D. P. Bertsekas","year":"1987","unstructured":"Bertsekas, D. P. (1987). Dynamic programming: Deterministic and stochastic models. Englewood Cliffs, NJ: Prentice-Hall."},{"key":"395109_CR3","volume-title":"Parallel and distributed computation: Numerical methods","author":"D. P. Bertsekas","year":"1989","unstructured":"Bertsekas, D. P., & Tsitsiklis, J. N. (1989). Parallel and distributed computation: Numerical methods. Englewood Cliffs, NJ: Prentice-Hall."},{"key":"395109_CR4","volume-title":"Neuro-dynamic programming","author":"D. P. Bertsekas","year":"1996","unstructured":"Bertsekas, D. P., & Tsitsiklis, J. N. (1996). Neuro-dynamic programming. Belmont, MA: Athena Scientific."},{"key":"395109_CR5","unstructured":"Chrisman, L. (1992). Reinforcement learning with perceptual aliasing: The perceptual distinctions approach. In AAAI-92."},{"key":"395109_CR6","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1145\/180139.181019","volume-title":"COLT94: Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory","author":"C. Fiechter","year":"1994","unstructured":"Fiechter, C. (1994). Efficient reinforcement learning. In COLT94: Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory (pp. 88\u201397). New York: ACM Press."},{"key":"395109_CR7","first-page":"116","volume-title":"Machine Learning: Proceedings of the Fourteenth International Conference, ICML97","author":"C. Fiechter","year":"1997","unstructured":"Fiechter, C. (1997). Expected mistake bound model for on-line reinforcement learning. In Machine Learning: Proceedings of the Fourteenth International Conference, ICML97 (pp. 116\u2013124). San Mateo, CA: Morgan Kaufmann."},{"key":"395109_CR8","first-page":"261","volume-title":"Machine Learning: Proceedings of the Twelth International Conference","author":"G. J. Gordon","year":"1995","unstructured":"Gordon, G. J. (1995). Stable function approximation in dynamic programming. In A. Prieditis, & S., Russell (Eds.), Machine Learning: Proceedings of the Twelth International Conference (pp. 261\u2013268). San Mateo, CA: Morgan Kaufmann."},{"key":"395109_CR9","first-page":"695","volume-title":"Advances is neural information processing systems 6","author":"V. Gullapalli","year":"1994","unstructured":"Gullapalli, V., & Barto, A. G. (1994). Convergence of indirect adaptive asynchronous value iteration algorithms. In J. D. Cowan, G. Tesauro, & J. Alspector (Eds.), Advances is neural information processing systems 6 (pp. 695\u2013702). San Mateo, CA: Morgan Kauffman."},{"issue":"6","key":"395109_CR10","doi-asserted-by":"crossref","first-page":"1185","DOI":"10.1162\/neco.1994.6.6.1185","volume":"6","author":"T. Jaakkola","year":"1994","unstructured":"Jaakkola, T., Jordan, M. I., & Singh, S. (1994). On the convergence of stochastic iterative dynamic programming algorithms. Neural Computation, 6:6, 1185\u20131201.","journal-title":"Neural Computation"},{"key":"395109_CR11","first-page":"345","volume-title":"Advances in neural information processing systems 7","author":"T. Jaakkola","year":"1995","unstructured":"Jaakkola, T., Singh, S., & Jordan, M. I. (1995). Reinforcement learning algorithm for partially observable Markov decision problems. In G. Tesauro, D. S. touretzky, & T. K. Leen (Eds.), Advances in neural information processing systems 7 (pp. 345\u2013352). San Mateo, CA: Morgan Kaufmann."},{"key":"395109_CR12","doi-asserted-by":"crossref","unstructured":"Jalali, A., & Ferguson, M. (1989). A distributed asynchronous algorithm for expected average cost dynamic programming. In Proceedings of the 29th Conference on Decision and Control, Honolulu, Hawaii (pp. 1283-1288).","DOI":"10.1109\/CDC.1990.203839"},{"key":"395109_CR13","unstructured":"Kearns, M., & Koller, D. (1999). Efficient reinforcement learning in factored MDPs. In Proceeding of the Sixteenth International Joint Conference on Artificial Intelligence (pp. 740-747). Morgan Kaufmann."},{"key":"395109_CR14","volume-title":"Stochastic systems: Estimation, identification, and adaptive control","author":"P. R. Kumar","year":"1986","unstructured":"Kumar, P. R., & Varaiya, P. P. (1986). Stochastic systems: Estimation, identification, and adaptive control. Englewood Cliffs, N.J.: Prentice Hall."},{"key":"395109_CR15","first-page":"362","volume-title":"Proceedings of the Twelfth International Conference on Machine Learning","author":"M. Littman","year":"1995","unstructured":"Littman, M., Cassandra, A., & Kaelbling., L. (1995). Learning policies for partially observable environments: Scaling up. In A. Prieditis, & S. Russell (Eds.), Proceedings of the Twelfth International Conference on Machine Learning (pp. 362\u2013370). San Francisco, CA: Morgan Kaufmann."},{"key":"395109_CR16","doi-asserted-by":"crossref","unstructured":"Moore, A. W., & Atkeson, C. G. (1993). Prioritized sweeping: Reinforcement learning with less data and less real time. Machine Learning, 12:1.","DOI":"10.1007\/BF00993104"},{"key":"395109_CR17","doi-asserted-by":"crossref","DOI":"10.1002\/9780470316887","volume-title":"Markov decision processes: Discrete stochastic dynamic programming","author":"M. L. Puterman","year":"1994","unstructured":"Puterman, M. L. (1994). Markov decision processes: Discrete stochastic dynamic programming. New York: John Wiley & Sons."},{"key":"395109_CR18","unstructured":"Rummery, G. A., & Niranjan, M. (1994). On-line Q-learning using connectionist systems. Technical Report CUED\/F-INFENG\/TR 166, Cambridge University Engineering Dept."},{"key":"395109_CR19","doi-asserted-by":"crossref","unstructured":"Saul, L., & Singh, S. (1996). Learning curve bounds for markov decision processes with undiscounted rewards. In COLT96: Proceedings of the Ninth Annual ACM Conference on Computational Learning Theory.","DOI":"10.1145\/238061.238084"},{"key":"395109_CR20","first-page":"266","volume-title":"Machine Learning: Proceedings of the Eleventh International Conference","author":"R. E. Schapire","year":"1994","unstructured":"Schapire, R. E., & Warmuth, M. K. (1994). On the worst-case analysis of temporal-difference learning algorithms. In W. W. Cohen, & H. Hirsh (Eds.), Machine Learning: Proceedings of the Eleventh International Conference (pp. 266\u2013274). San Mateo, CA: Morgan Kaufmann."},{"key":"395109_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0323-0","volume-title":"Algorithms for random generation and counting: A Markov chain approach","author":"A. Sinclair","year":"1993","unstructured":"Sinclair, A. (1993). Algorithms for random generation and counting: A Markov chain approach. Boston: Birkhauser."},{"issue":"1","key":"395109_CR22","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1023\/A:1007495401240","volume":"32","author":"S. Singh","year":"1998","unstructured":"Singh, S., & Dayan, P. (1998). Analytical mean squared error curves for temporal difference learning. Machine Learning, 32:1, 5\u201340.","journal-title":"Machine Learning"},{"key":"395109_CR23","volume-title":"Advances in neural information processing systems 7","author":"S. Singh","year":"1995","unstructured":"Singh, S., Jaakkola, T., & Jordan, M. I. (1995). Reinforcement learning with soft state aggregation. In Advances in neural information processing systems 7. San Mateo, CA: Morgan Kaufmann."},{"issue":"3","key":"395109_CR24","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1023\/A:1007678930559","volume":"38","author":"S. Singh","year":"2000","unstructured":"Singh, S., Jaakkola, T., Littman, M. L., & Szepesvari, C. (2000). Convergence results for single-step on-policy reinforcement learning algorithms. Machine Learning, 38:3, 287\u2013308.","journal-title":"Machine Learning"},{"key":"395109_CR25","first-page":"123","volume":"22","author":"S. Singh","year":"1996","unstructured":"Singh, S., & Sutton, R. S. (1996). Reinforcement learning with replacing eligibility traces. Machine Learning, 22, 123\u2013158.","journal-title":"Machine Learning"},{"key":"395109_CR26","first-page":"9","volume":"3","author":"R. S. Sutton","year":"1988","unstructured":"Sutton, R. S. (1988). Learning to predict by the methods of temporal differences. Machine Learning, 3, 9\u201344.","journal-title":"Machine Learning"},{"key":"395109_CR27","first-page":"1038","volume-title":"Advances in neural information processing systems 8","author":"R. S. Sutton","year":"1995","unstructured":"Sutton, R. S. (1995). Generalization in reinforcement learning: Successful examples using sparse coarse coding. In D. S. Touretzky, M. C. Mozer, & M. E. Hasselmo (Eds.), Advances in neural information processing systems 8 (pp. 1038\u20131044). Cambridge, MA: MIT Press."},{"key":"395109_CR28","volume-title":"Reinforcement learning: An introduction","author":"R. S. Sutton","year":"1998","unstructured":"Sutton, R. S., & Barto, A. G. (1998). Reinforcement learning: An introduction. Cambridge, MA: MIT Press."},{"key":"395109_CR29","volume-title":"Handbook of intelligent control: Neural, fuzzy and adaptive approaches","author":"S. B. Thrun","year":"1992","unstructured":"Thrun, S. B. (1992). The role of exploration in learning control. In D. A. White, & D. A. Sofge (Eds.), Handbook of intelligent control: Neural, fuzzy and adaptive approaches. Florence, KY: Van Nostrand Reinhold."},{"issue":"3","key":"395109_CR30","first-page":"185","volume":"16","author":"J. Tsitsiklis","year":"1994","unstructured":"Tsitsiklis, J. (1994). Asynchronous stochastic approximation and Q-learning. Machine Learning, 16:3, 185\u2013202.","journal-title":"Machine Learning"},{"key":"395109_CR31","first-page":"59","volume":"22","author":"J. Tsitsiklis","year":"1996","unstructured":"Tsitsiklis, J., & Roy, B. V. (1996). Feature-based methods for large scale dynamic programming. Machine Learning, 22, 59\u201394.","journal-title":"Machine Learning"},{"key":"395109_CR32","volume-title":"Learning from delayed rewards","author":"C. J. C. H. Watkins","year":"1989","unstructured":"Watkins, C. J. C. H. (1989). Learning from delayed rewards. Ph.D. thesis, Cambridge Univ., Cambridge, England, UK."},{"issue":"3\/4","key":"395109_CR33","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1023\/A:1022676722315","volume":"8","author":"C. J. C. H. Watkins","year":"1992","unstructured":"Watkins, C. J. C. H., & Dayan, P. (1992). Q-learning. Machine Learning, 8:3\/4, 279\u2013292.","journal-title":"Machine Learning"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1017984413808.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1017984413808\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1017984413808.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T11:33:52Z","timestamp":1752147232000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1017984413808"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,11]]},"references-count":33,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2002,11]]}},"alternative-id":["395109"],"URL":"https:\/\/doi.org\/10.1023\/a:1017984413808","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,11]]},"assertion":[{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}