mlsanityData to 7 Oct 2026

Reinforcement Learning With Reward Machines in Stochastic Games

arXiv 2305.17372 ↗First posted 27 May 2023cs.MA cs.AI cs.GTcited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 18 of its 50 references that are in the map. First posted on arXiv 27 May 2023.

Builds on

18 of 50 references.

References · 18

  1. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,704
  2. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,519
  3. 2017Counterfactual Multi-Agent Policy Gradientscited by 733
  4. 2018QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 697
  5. 2017Value-Decomposition Networks For Cooperative Multi-Agent Learningcited by 490
  6. 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 189
  7. 2017Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observabilitycited by 143
  8. 2017Stabilising Experience Replay for Deep Multi-Agent Reinforcement Learningcited by 114
  9. 2019Joint Inference of Reward Machines and Policies for Reinforcement Learningcited by 56
  10. 2017Lenient Multi-Agent Deep Reinforcement Learningcited by 35
  11. 2021Learning in Nonzero-Sum Stochastic Games with Potentialscited by 25
  12. 2020Active Finite Reward Automaton Inference and Reinforcement Learning Using Queries and Counterexamplescited by 23
6 more
  1. 2016Extending the OpenAI Gym for robotics: a toolkit for reinforcement learning using ROS and Gazebocited by 18
  2. 2020Learning Non-Markovian Reward Models in MDPscited by 11
  3. 2020Extended Markov Games to Learn Multiple Tasks in Multi-Agent Reinforcement Learningcited by 9
  4. 2020Online Learning of Non-Markovian Reward Modelscited by 9
  5. 2017Explore, Exploit or Listen: Combining Human Feedback and Policy Model to Speed up Deep Reinforcement Learning in 3D Worldscited by 8
  6. 2019Non-Cooperative Inverse Reinforcement Learningcited by 7

Built on by

Not cited yet.