Robust Learning for Repeated Stochastic Games via Meta-Gaming

Jacob W. CrandallIJCAI 2015

Introduction

Repeated Stochastic Games (RSGs) represent a significant challenge in multi-agent reinforcement learning. Unlike static games, RSGs involve agents navigating through various states where rewards are interdependent. This complexity often leads to the "curse of dimensionality," making traditional learning methods inefficient. This paper, presented at IJCAI 2015, introduces the MEGA (Meta-Gaming) algorithm, which simplifies the strategy space rather than the state space to achieve robust performance in complex, general-sum scenarios.

The Challenge of RSGs

Learning in RSGs is notoriously difficult due to three primary factors:

  1. Astronomical Strategy Space: The number of possible strategies is effectively infinite as they can depend on the entire history of play.
  2. Non-Stationarity: Agents must learn in an environment where opponents are also adapting, creating a "moving target" problem.
  3. Equilibrium Ambiguity: In general-sum games, multiple Nash Equilibria often exist, making it unclear which "optimal" strategy an agent should pursue.

The MEGA Framework

MEGA addresses these challenges by reducing the massive strategy space to a curated set of high-level "expert" strategies ($\Phi_i$). This transformation turns the complex RSG into a manageable Multi-Armed Bandit problem.

Strategy Reduction

The framework identifies three essential modes of social interaction:

  • Leader Strategies: These aim for a specific cooperative "target solution." They include a "trigger" mechanism to punish opponents who attempt exploitation.
  • Follower Strategies: Reactive strategies, such as standard Model-Based Reinforcement Learning (MBRL) and "maximin" strategies, which respond to the opponent's current behavior.
  • Preventative Strategies: These minimize the difference between players' payoffs, preventing "bullying" by the opponent.
Payoff space and solution concepts in RSGs.

The Meta-Learner

By treating these experts as arms in a bandit problem, MEGA employs selection algorithms like S++ or Exp3. This allows the agent to dynamically switch between high-level behaviors based on their observed performance against a specific opponent.

Experimental Evaluation

The MEGA approach was tested across three benchmarks: a Microgrid resource-sharing scenario, a Stochastic Game Prisoners’ Dilemma (SGPD), and a turn-based Block Game.

In the Microgrid scenario, agents must coordinate electricity usage over 2,000 states to avoid blackouts. Results showed that MEGA-S++ (often represented by its "FolkEgal" leader strategy in results) significantly outperformed traditional methods like Counterfactual Regret Minimization (CFR) and standard MBRL.

Microgrid scenario generation and performance comparison.

Key Insights

  • Strategy vs. State Abstraction: MEGA demonstrates that grouping similar behaviors is often more effective than grouping similar states.
  • Preserving Game Properties: The paper proves that this reduction maintains the game's security levels and the existence of Nash Equilibria.
  • Robustness through Punishment: The inclusion of "Leader" strategies with punishment mechanisms makes cooperation the rational choice for opponents, solving coordination problems that stymie myopic learners.

Conclusion

MEGA-S++ consistently achieved the highest average payoffs across all benchmarks. While it requires some upfront computational overhead to define target solutions, its long-term robustness and ability to resist exploitation make it a powerful framework for multi-agent systems. Future work aims to extend this meta-gaming approach to N-player environments.

Summary updated

BibTeX
@inproceedings{crandall2015robust,
  author = {Jacob W. Crandall},
  title = {{Robust Learning for Repeated Stochastic Games via Meta-Gaming}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure