{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,30]],"date-time":"2023-09-30T16:44:53Z","timestamp":1696092293532},"reference-count":0,"publisher":"IOS Press","isbn-type":[{"value":"9781643684369","type":"print"},{"value":"9781643684376","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,9,28]],"date-time":"2023-09-28T00:00:00Z","timestamp":1695859200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,9,28]]},"abstract":"<jats:p>We investigate multi-agent reinforcement learning for stochastic games with complex tasks, where the reward functions are non-Markovian. We utilize reward machines to incorporate high-level knowledge of complex tasks. We develop an algorithm called Q-learning with reward machines for stochastic games (QRM-SG), to learn the best-response strategy at Nash equilibrium for each agent. In QRM-SG, we define the Q-function at a Nash equilibrium in augmented state space. The augmented state space integrates the state of the stochastic game and the state of reward machines. Each agent learns the Q-functions of all agents in the system. We prove that Q-functions learned in QRM-SG converge to the Q-functions at a Nash equilibrium if the stage game at each time step during learning has a global optimum point or a saddle point, and the agents update Q-functions based on the best-response strategy at this point. We use the Lemke-Howson method to derive the best-response strategy given current Q-functions. The three case studies show that QRM-SG can learn the best-response strategies effectively. QRM-SG learns the best-response strategies after around 7500 episodes in Case Study I, 1000 episodes in Case Study II, and 1500 episodes in Case Study III, while baseline methods such as Nash Q-learning and MADDPG fail to converge to the Nash equilibrium in all three case studies.<\/jats:p>","DOI":"10.3233\/faia230380","type":"book-chapter","created":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T09:11:48Z","timestamp":1695978708000},"source":"Crossref","is-referenced-by-count":0,"title":["Reinforcement Learning with Reward Machines in Stochastic Games"],"prefix":"10.3233","author":[{"given":"Jueming","family":"Hu","sequence":"first","affiliation":[{"name":"Arizona State University, Tempe, AZ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Rapha\u00ebl","family":"Gaglione","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanze","family":"Wang","sequence":"additional","affiliation":[{"name":"Arizona State University, Tempe, AZ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhe","family":"Xu","sequence":"additional","affiliation":[{"name":"Arizona State University, Tempe, AZ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ufuk","family":"Topcu","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongming","family":"Liu","sequence":"additional","affiliation":[{"name":"Arizona State University, Tempe, AZ"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","ECAI 2023"],"original-title":[],"link":[{"URL":"https:\/\/ebooks.iospress.nl\/pdf\/doi\/10.3233\/FAIA230380","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T09:11:49Z","timestamp":1695978709000},"score":1,"resource":{"primary":{"URL":"https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA230380"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,28]]},"ISBN":["9781643684369","9781643684376"],"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/faia230380","relation":{},"ISSN":["0922-6389","1879-8314"],"issn-type":[{"value":"0922-6389","type":"print"},{"value":"1879-8314","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,28]]}}}