{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:31:08Z","timestamp":1750307468403,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T00:00:00Z","timestamp":1283299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMI-0422133CMMI-0758441"],"award-info":[{"award-number":["DMI-0422133CMMI-0758441"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000147","name":"Division of Civil, Mechanical and Manufacturing Innovation","doi-asserted-by":"publisher","award":["DMI-0422133CMMI-0758441"],"award-info":[{"award-number":["DMI-0422133CMMI-0758441"]}],"id":[{"id":"10.13039\/100000147","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>In this article, we develop a stochastic approximation method to solve a monotone estimation problem and use this method to enhance the empirical performance of the Q-learning algorithm when applied to Markov decision problems with monotone value functions. We begin by considering a monotone estimation problem where we want to estimate the expectation of a random vector, \u03b7. We assume that the components of E {\u03b7} are known to be in increasing order. The stochastic approximation method that we propose is designed to exploit this information by projecting its iterates onto the set of vectors with increasing components. The novel aspect of the method is that it uses projections with respect to the max norm. We show the almost sure convergence of the stochastic approximation method. After this result, we consider the Q-learning algorithm when applied to Markov decision problems with monotone value functions. We study a variant of the Q-learning algorithm that uses projections to ensure that the value function approximation obtained at each iteration is also monotone. Computational results indicate that the performance of the Q-learning algorithm can be improved significantly by exploiting the monotonicity property of the value functions.<\/jats:p>","DOI":"10.1145\/1842713.1842715","type":"journal-article","created":{"date-parts":[[2010,10,5]],"date-time":"2010-10-05T14:38:15Z","timestamp":1286289495000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A stochastic approximation method with max-norm projections and its applications to the Q-learning algorithm"],"prefix":"10.1145","volume":"20","author":[{"given":"Sumit","family":"Kunnumkal","sequence":"first","affiliation":[{"name":"Indian School of Business, Gachibowli, Hyderabad"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huseyin","family":"Topaloglu","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,10,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.41.12.1946"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)00011-O"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"}}Benveniste A. Metivier M. and Priouret P. 1991. Adaptive Algorithms and Stochastic Approximations. Springer.   }}Benveniste A. Metivier M. and Priouret P. 1991. Adaptive Algorithms and Stochastic Approximations. Springer.","DOI":"10.1007\/978-3-642-75894-2"},{"key":"e_1_2_1_4_1","unstructured":"}}Bertsekas D. P. Nedic A. and Ozdaglar A. E. 2003. Convex Analysis and Optimization. Athena Scientific Belmont MA.  }}Bertsekas D. P. Nedic A. and Ozdaglar A. E. 2003. Convex Analysis and Optimization. Athena Scientific Belmont MA."},{"key":"e_1_2_1_5_1","unstructured":"}}Bertsekas D. P. and Tsitsiklis J. N. 1996. Neuro-Dynamic Programming. Athena Scientific Belmont MA.   }}Bertsekas D. P. and Tsitsiklis J. N. 1996. Neuro-Dynamic Programming. Athena Scientific Belmont MA."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.51.6.850.24925"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.2307\/1426040"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.47.8.1101.10231"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.20.6.1077"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.22.5.1008"},{"key":"e_1_2_1_11_1","unstructured":"}}Kosten L. 1973. Stochastic Theory of Service Systems. Pergamon Press New York.  }}Kosten L. 1973. Stochastic Theory of Service Systems. Pergamon Press New York."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1070.0240"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"}}Kushner H. J. and Clark D. S. 1978. Stochastic Approximation Methods for Constrained and Unconstrained Systems. Springer-Verlang Berlin.  }}Kushner H. J. and Clark D. S. 1978. Stochastic Approximation Methods for Constrained and Unconstrained Systems. Springer-Verlang Berlin.","DOI":"10.1007\/978-1-4684-9352-8"},{"key":"e_1_2_1_14_1","unstructured":"}}Kushner H. J. and Yin G. G. 2003. Stochastic Approximation and Recursive Algorithms and Applications. Springer New York.  }}Kushner H. J. and Yin G. G. 2003. Stochastic Approximation and Recursive Algorithms and Applications. Springer New York."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1977.1101561"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(01)00297-1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.10087"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"}}Powell W. B. 2007. Approximate Dynamic Programming: Solving the Curses of Dimensionality. John Wiley New York NY.   }}Powell W. B. 2007. Approximate Dynamic Programming: Solving the Curses of Dimensionality. John Wiley New York NY.","DOI":"10.1002\/9780470182963"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1040.0107"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"}}Puterman M. L. 1994. Markov Decision Processes. John Wiley and Sons Inc. New York.   }}Puterman M. L. 1994. Markov Decision Processes. John Wiley and Sons Inc. New York.","DOI":"10.1002\/9780470316887"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"}}Si J. Barto A. G. Powell W. B. and Wunsch II D. Eds. 2004. Handbook of Learning and Approximate Dynamic Programming. Wiley-Interscience Piscataway NJ.   }}Si J. Barto A. G. Powell W. B. and Wunsch II D. Eds. 2004. Handbook of Learning and Approximate Dynamic Programming. Wiley-Interscience Piscataway NJ.","DOI":"10.1109\/9780470544785"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"}}Sutton R. S. and Barto A. G. 1998. Reinforcement Learning. The MIT Press Cambridge MA.   }}Sutton R. S. and Barto A. G. 1998. Reinforcement Learning. The MIT Press Cambridge MA.","DOI":"10.1109\/TNN.1998.712192"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1080\/07408170590918083"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(02)00187-6"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.580874"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/72.935083"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022689125041"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.46.6.760.11936"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0005-1098(99)00034-5"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.668830"},{"key":"e_1_2_1_31_1","unstructured":"}}Watkins C. J. C. H. 1989. Learning from delayed rewards. Ph.D. thesis Cambridge University Cambridge UK.  }}Watkins C. J. C. H. 1989. Learning from delayed rewards. Ph.D. thesis Cambridge University Cambridge UK."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00992698"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1842713.1842715","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1842713.1842715","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:08:36Z","timestamp":1750248516000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1842713.1842715"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.1145\/1842713.1842715"],"URL":"https:\/\/doi.org\/10.1145\/1842713.1842715","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"type":"print","value":"1049-3301"},{"type":"electronic","value":"1558-1195"}],"subject":[],"published":{"date-parts":[[2010,9]]},"assertion":[{"value":"2008-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-10-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}