{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,3]],"date-time":"2026-09-03T15:00:51Z","timestamp":1788447651156,"version":"build-2803163510"},"reference-count":43,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Control Optim."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>In this paper, we address the problem of convergence to Nash equilibria in games with rewards that are initially unknown and must be estimated over time from noisy observations. These games arise in many real-world applications, whenever rewards for actions cannot be prespecified and must be learned online, but standard results in game theory do not consider such settings. For this problem, we derive a multiagent version of $\\mathcal{Q}$-learning to estimate the reward functions using novel forms of the $\\epsilon$-greedy learning policy. Using these $\\mathcal{Q}$-learning schemes to estimate reward functions, we then provide conditions guaranteeing the convergence of adaptive play and the better-reply processes to Nash equilibria in potential games and games with more general forms of acyclicity, and of regret matching to the set of correlated equilibria in generic games. A secondary result is that we prove the strong ergoditicity of stochastic adaptive play and stochastic better-reply processes in the case of vanishing perturbations. Finally, we illustrate the efficacy of the algorithms in a set of randomly generated three-player coordination games and show the practical necessity of our results by demonstrating that violations to the derived learning parameter conditions can cause the algorithms to fail to converge.<\/jats:p>","DOI":"10.1137\/120893501","type":"journal-article","created":{"date-parts":[[2013,8,6]],"date-time":"2013-08-06T14:07:18Z","timestamp":1375798038000},"page":"3154-3180","source":"Crossref","is-referenced-by-count":35,"title":["Convergent Learning Algorithms for Unknown Reward Games"],"prefix":"10.1137","volume":"51","author":[{"given":"Archie C.","family":"Chapman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David S.","family":"Leslie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alex","family":"Rogers","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicholas R.","family":"Jennings","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,8,6]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.35.6.867"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1115\/1.2766722"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"P. Auer, N. Cesa-Bianchi, Y. Freund, and R. Schapire (1995),<i>Gambling in a rigged casino: The adversarial multi-armed bandit problem<\/i> in Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS '95), IEEE Computer Society., Washington, D.C., pp. 322-331.","DOI":"10.1109\/SFCS.1995.492488"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177698023"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1956.6.1"},{"key":"atypb6","unstructured":"G. W. Brown (1951),<i>Iterative solution of games by fictitious play<\/i> in Activity Analysis of Production and Allocation T. C. Koopermans, ed., John Wiley, New York, pp. 374-376."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxq023"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1017\/S0269888911000178"},{"key":"atypb9","unstructured":"C. Claus and C. Boutilier (1998),<i>The dynamics of reinforcement learning in cooperative multiagent systems<\/i> in Proceedings of the 15th AAAI National Conference on Artificial Intelligence, AAAI Press, pp. 746-752."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.11.012"},{"key":"atypb11","first-page":"341","volume":"1","author":"Foster D. P.","year":"2006","journal-title":"Theoret. Econom."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.2000.2694"},{"key":"atypb13","unstructured":"D. Fudenberg and D. K. Levine (1998),<i>The Theory of Learning in Games<\/i> MIT Press, Cambridge, MA."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1683"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00153"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"S. Hart and A. Mas-Colell (2001),<i>A Reinforcement Procedure Leading to Correlated Equilibrium<\/i> in Economic Essays, Springer, New York, pp. 181-200.","DOI":"10.1007\/978-3-662-04623-4_12"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2005.05.011"},{"key":"atypb19","unstructured":"D. Isaacson and R. Madsen (1976),<i>Markov Chains: Theory and Applications<\/i> John Wiley, New York."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1994.6.6.1185"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1145\/367211.367250"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.2307\/2951777"},{"key":"atypb23","unstructured":"M. Kearns, M. Littman, and S. Singh (2001),<i>Graphical models for game theory<\/i> in Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence (UAI-01), Morgan Kaufmann, Burlington, MA, pp. 253-260."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012903437976"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.08.005"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"L. Li, M. L. Littman, and T. J. Walsh (2008),<i>Knows what it knows: A framework for self-aware learning<\/i> in Proceedings of the 25th International Conference on Machine Learning (ICML '08), pp. 568-575.","DOI":"10.1145\/1390156.1390228"},{"key":"atypb27","unstructured":"T. Lu, D. P\u00e1l, and M. P\u00e1l (2010),<i>Contextual multi-armed bandits<\/i> in Proceedings of the 13th International Conference on Artificial Intelligence and Statistics (AISTATS '10), pp. 485-492."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/070680199"},{"key":"atypb29","unstructured":"J. Marschak and R. Radner (1972),<i>Economic Theory of Teams<\/i> Yale University Press, New Haven, CT."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1214\/09-AAP651"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1145\/1379759.1379762"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"G. Scutari, S. Barbarossa, and D. P. Palomar (2006),<i>Potential games: A framework for vector power control problems with coupled constraints<\/i> in 31st IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '06), vol. 4, pp. 241-244.","DOI":"10.1109\/ICASSP.2006.1660950"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007678930559"},{"key":"atypb36","unstructured":"R. S. Sutton and A. G. Barto (1998), in<i>Reinforcement Learning<\/i> MIT Press, Cambridge, MA."},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"B. Touri and A. Nedi\u0107 (2010),<i>When infinite flow is sufficient for ergodicity<\/i> in Proceedings of the 49th IEEE Conference on Decision and Control (CDC '10), Atlanta, GA.","DOI":"10.1109\/CDC.2010.5717769"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1680\/ipeds.1952.11259"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1613\/jair.995"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.2307\/2951778"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"H. P. Young (2004),<i>Strategic Learning and Its Limits<\/i> Oxford University Press, Oxford, UK.","DOI":"10.1093\/acprof:oso\/9780199269181.001.0001"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.02.011"}],"container-title":["SIAM Journal on Control and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120893501","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:56:21Z","timestamp":1787320581000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120893501"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/120893501"],"URL":"https:\/\/doi.org\/10.1137\/120893501","relation":{},"ISSN":["0363-0129","1095-7138"],"issn-type":[{"value":"0363-0129","type":"print"},{"value":"1095-7138","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}