Introduction
Reinforcement Learning (RL) has seen significant success in single-agent environments, yet multi-agent reinforcement learning (MARL) remains a frontier fraught with complexity. A primary challenge in MARL is the assumption of the Markov property—the idea that the current state contains all necessary information for decision-making. In many real-world scenarios, rewards are non-Markovian, depending on a specific history of events. When these complex tasks are situated within a stochastic game—where multiple agents compete or cooperate—standard algorithms often fail to converge. This paper introduces QRM-SG (Q-learning with Reward Machines for Stochastic Games), a framework designed to solve non-Markovian tasks in multi-agent settings by integrating finite-state automata known as Reward Machines.
The Challenge of Non-Markovian Stochastic Games
In a standard Markov Decision Process (MDP), the reward function is a mapping from the current state and action to a scalar. However, tasks like "collect a key, then open a door" require memory. In multi-agent systems, this is compounded by the strategic interactions of agents. Existing MARL methods, such as Multi-Agent Deep Deterministic Policy Gradient (MADDPG) or Nash Q-learning, typically struggle with these history-dependent rewards because they lack a formal mechanism to track and exploit the temporal structure of the task. The authors aim to bridge this gap by providing a formal way to encode temporal rewards and a learning rule that guarantees convergence to a Nash equilibrium.
The QRM-SG Framework
The authors propose QRM-SG to bridge the gap between temporal logic and game theory. The algorithm relies on three core pillars:
1. Reward Machines (RM)
Reward Machines are Mealy machines (a type of finite-state automaton) that represent the high-level structure of a task. By using logical propositions from the environment (e.g., "Agent A is at Base 1"), the RM transitions between internal states and provides rewards. This allows the decomposition of a massive, complex task into smaller, manageable Markovian sub-problems.
2. State Augmentation
To restore the Markov property, QRM-SG "augments" the environment's state space with the internal state of each agent's Reward Machine. This transformation allows the agents to treat the history-dependent problem as a standard stochastic game over the expanded state space.
3. Nash Stage Games and Convergence
At each learning step, agents solve a "stage game" to determine their optimal actions relative to their opponents' strategies. QRM-SG utilizes the Lemke-Howson method to find Nash equilibria in these stage games. The authors provide a formal mathematical proof demonstrating that QRM-SG will converge to the Q-functions of a Nash equilibrium, provided the stage games possess a global optimum or a saddle point.
Experimental Evaluation
The researchers evaluated QRM-SG using a custom PAC-MAN variant in grid-world environments. Testing was conducted on $6 \times 6$ and $12 \times 12$ grids across three case studies of increasing complexity. In the most demanding scenario (Case Study II), an agent had to navigate to its base, destroy an opponent's base, recharge, and finally capture the opponent.
Baselines
QRM-SG was compared against standard Nash Q-learning and MADDPG, as well as Nash-QAS and MADDPG-AS. These "augmented state" versions were provided with the Reward Machine state but lacked the specific QRM-SG update logic, testing whether the algorithm's structure—rather than just the data—was the key to success.
Key Results
The experimental results highlight the robustness of the QRM-SG approach:
- Superior Convergence: QRM-SG was the only algorithm to consistently find the Nash equilibrium across all case studies. Standard baselines often resulted in sub-optimal behaviors where agents failed to execute the full sequence required for high rewards.
- Learning Efficiency: In Case Study II, QRM-SG reached the equilibrium in approximately 1,000 episodes. In contrast, state-of-the-art baselines like MADDPG failed to converge even after 16,000 episodes.
- Scalability: The algorithm successfully scaled to a $12 \times 12$ grid. Despite the significantly larger state space, QRM-SG found the Nash equilibrium in roughly 21,000 episodes.
- General-Sum Flexibility: Unlike many MARL frameworks restricted to zero-sum or purely cooperative games, QRM-SG proved effective in general-sum games where agents have independent, potentially conflicting goals.
Discussion and Limitations
While QRM-SG represents a significant advancement, several challenges remain for future work:
- Computational Complexity: The Lemke-Howson method is efficient for two-player games, but calculating Nash equilibria for $N$-player games is PPAD-complete. Scaling to many agents remains a hurdle.
- Discrete vs. Continuous: The current implementation uses tabular Q-learning. Extending this to Deep RL using actor-critic methods is a necessary step for continuous state spaces.
- Known Reward Machines: The paper assumes the Reward Machine structure is provided by an expert. A promising future direction is learning the Reward Machine itself from environment interactions while simultaneously learning the game strategy.
Conclusion
QRM-SG provides a mathematically grounded and empirically successful method for solving complex, non-Markovian tasks in multi-agent stochastic games. By leveraging Reward Machines to structure the learning process, the algorithm ensures convergence to Nash equilibria where traditional MARL methods falter.
Summary updated