# Reinforcement Learning With Reward Machines in Stochastic Games

arXiv: https://arxiv.org/abs/2305.17372 · HTML: https://mlsanity.com/paper/2305.17372/

## Key facts

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

## Builds on (most cited first, 18 of 18)

- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [Value-Decomposition Networks For Cooperative Multi-Agent Learning](https://mlsanity.com/paper/1706.05296/) (2017)
- [Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents](https://mlsanity.com/paper/1802.08757/) (2018)
- [Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability](https://mlsanity.com/paper/1703.06182/) (2017)
- [Stabilising Experience Replay for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1702.08887/) (2017)
- [Joint Inference of Reward Machines and Policies for Reinforcement Learning](https://mlsanity.com/paper/1909.05912/) (2019)
- [Lenient Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/1707.04402/) (2017)
- [Learning in Nonzero-Sum Stochastic Games with Potentials](https://mlsanity.com/paper/2103.09284/) (2021)
- [Active Finite Reward Automaton Inference and Reinforcement Learning Using Queries and Counterexamples](https://mlsanity.com/paper/2006.15714/) (2020)
- [Extending the OpenAI Gym for robotics: a toolkit for reinforcement learning using ROS and Gazebo](https://mlsanity.com/paper/1608.05742/) (2016)
- [Learning Non-Markovian Reward Models in MDPs](https://mlsanity.com/paper/2001.09293/) (2020)
- [Extended Markov Games to Learn Multiple Tasks in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2002.06000/) (2020)
- [Online Learning of Non-Markovian Reward Models](https://mlsanity.com/paper/2009.12600/) (2020)
- [Explore, Exploit or Listen: Combining Human Feedback and Policy Model to Speed up Deep Reinforcement Learning in 3D Worlds](https://mlsanity.com/paper/1709.03969/) (2017)
- [Non-Cooperative Inverse Reinforcement Learning](https://mlsanity.com/paper/1911.04220/) (2019)

## 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.