Abstract
Due to the non-stationary environment, learning in multi-agent systems is a challenging problem. This paper first introduces a new gradient-based learning algorithm, augmenting the basic gradient ascent approach with policy prediction. We prove that this augmentation results in a stronger notion of convergence than the basic gradient ascent, that is, strategies converge to a Nash equilibrium within a restricted class of iterated games. Motivated by this augmentation, we then propose a new practical multi-agent reinforcement learning (MARL) algorithm exploiting approximate policy prediction. Empirical results show that it converges faster and in a wider variety of situations than state-of-the-art MARL algorithms.
Introduction
In standard single-agent Reinforcement Learning (RL), the environment is assumed to be stationary. However, in Multi-Agent Systems (MAS), multiple agents learn simultaneously, making the environment non-stationary from any single agent's perspective. This non-stationarity often causes standard RL algorithms to fail or oscillate endlessly. While existing MARL algorithms like IGA, WoLF-PHC, or GIGA-WoLF address some issues, they often suffer from weak convergence—guaranteeing only average payoffs rather than stable strategies—or rely on unrealistic assumptions, such as knowing the opponent's payoff matrix or exact actions.
Methods: From Theory to Practice
The authors propose a two-phase approach to achieve strong convergence in decentralized systems using policy prediction.
IGA with Policy Prediction (IGA-PP)
The theoretical foundation is Infinitesimal Gradient Ascent with Policy Prediction (IGA-PP). Unlike standard IGA, where an agent updates its strategy based on the opponent's current strategy, IGA-PP uses a forecasted strategy. By calculating the derivative of the opponent's strategy, the agent anticipates future moves. This anticipation transforms the typical oscillatory trajectories of gradient ascent into convergent spirals.
Practical Implementation: PGA-APP
To move beyond the theoretical requirement of knowing the opponent's strategy derivative, the authors introduce Policy Gradient Ascent with Approximate Policy Prediction (PGA-APP). This algorithm uses standard Q-learning to estimate action values and approximates the opponent's policy gradient using the local TD-error—the difference between a specific action's Q-value and the state's average reward. This allows agents to "simulate" policy prediction using only local reward signals, making it viable for decentralized real-world applications.
Experimental Results
The algorithms were evaluated across several interactive environments, showing superior performance over state-of-the-art baselines:
- Normal-Form Games: In benchmarks like Matching Pennies and Shapley’s Game, PGA-APP consistently converged to Nash equilibria, even in 3-player scenarios where baselines like WPL and WoLF-PHC failed.
- Distributed Task Allocation (DTAP): In a 10x10 grid network, PGA-APP achieved an Average Total Service Time (ATST) of $24.89 \pm 0.82$, significantly outperforming GIGA-WoLF ($30.30$) and WPL ($34.25$).
- Network Routing: In irregular grid simulations, PGA-APP minimized packet delays with an Average Delivery Time (ADT) of $9.86 \pm 0.29$, beating GIGA-WoLF ($10.22$) and WPL ($11.60$).
Key Insights and Discussion
The core insight of this work is that anticipation cures oscillation. In competitive games, standard gradient ascent often leads to unstable orbits or saddle points. By predicting the opponent's trajectory, IGA-PP forces the system toward a stable focus.
While the mathematical proof for convergence is currently limited to 2-player, 2-action iterated general-sum games, empirical evidence suggests the principle holds in more complex, N-player environments. However, the algorithm is sensitive to hyperparameters, particularly the prediction length and learning rates, which require careful tuning. Future work will focus on extending formal proofs and developing adaptive mechanisms to automatically tune these parameters.
Summary updated