Multi-agent learning in extensive games with complete information

Pu Huang, Katia SycaraProceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems - AAMAS '03 2003 · DOI

TL;DR

This paper tackles the challenge of multi-agent learning in complex, sequential games (extensive games) where all players have perfect information. They introduce two novel algorithms, MLA and MQ-learning, that allow autonomous, self-interested agents to collectively converge to equilibrium strategies without needing to build explicit beliefs about their opponents. This is a significant step towards more robust AI agents capable of strategic interaction.

What Problem Does This Paper Address?

Learning in multi-agent systems is notoriously difficult because each agent's learning environment is constantly shifting due to the learning activities of other agents. This is especially true in sequential decision-making scenarios like extensive games, where players take turns making moves. Traditional game theory often assumes perfect rationality, but this paper focuses on how agents with limited learning capabilities can still reach stable, predictable outcomes (equilibria). Specifically, the authors address the problem of multi-agent learning in complete-information extensive games (CEGs). In these games, the entire game tree is known, and every player can observe all past actions. The challenge is to design learning algorithms that enable multiple agents, each pursuing their own interests, to converge to a sub-game perfect equilibrium (SPE), a strong form of game-theoretic solution, without explicit coordination or belief modeling.

Methods

The paper proposes two reinforcement learning algorithms:

  • Multi-agent Learning Automata (MLA): This algorithm modifies the standard learning automaton approach. In each decision node, an agent updates its probability distribution over actions based on the outcome of the game. The key insight is that by using small learning rates (patience), agents can collectively converge to the SPE. This method reinforces past successes and failures without explicitly storing or updating value estimates for states or actions.
  • MQ-learning (Multi-agent Q-learning): This algorithm extends the concept of Q-learning to the multi-agent setting. Agents maintain Q-values (estimates of future rewards) for state-action pairs. When an agent makes a move, it primarily chooses the action with the highest Q-value but also explores other actions with a small probability (controlled by an exploration threshold, σ). The Q-values are then updated based on the received reward. Similar to MLA, the paper proves that with small exploration thresholds, agents can collectively converge to the SPE.

Both algorithms leverage the tree-like structure of CEGs and the fact that all moves are observable. They are designed to work even when agents only know their own payoffs.

Datasets

Not discussed in the paper. The experiments use a simulated game based on the example game tree provided in Figure 1.

Key Insights and Ideas

  • No Beliefs Necessary for Convergence: A major finding is that agents can collectively converge to a rational outcome (SPE) in CEGs simply by reinforcing their own past experiences (successes/failures) without needing to build explicit models or beliefs about their opponents' strategies. This is a significant departure from traditional game-theoretic learning approaches like fictitious play.
  • Patience is Key: Both MLA and MQ-learning rely on agents being "patient" – using small learning rates (MLA) or small exploration thresholds (MQ-learning). This gradual learning process allows the system to stabilize and converge to equilibrium.
  • CEG Structure is Crucial: The tree-like structure of extensive games and the complete information setting are fundamental to the convergence proofs. These properties allow the problem to be decomposed and analyzed using induction, similar to how single-agent learning in Markov Decision Processes (MDPs) is analyzed.
  • Individual vs. Collective Convergence: The paper distinguishes between an agent learning in a fixed environment (individual convergence, like in standard MDPs) and agents learning in a dynamic environment where others are also learning (collective convergence). Their algorithms are shown to achieve collective convergence.

Key Results

The paper provides theoretical guarantees for both algorithms:

  • MLA: Theorem 1 states that for any ε > 0, there exists a learning rate α such that if all agents use learning rates less than α, their long-run average rewards will converge to within an ε-range of their SPE rewards. This implies collective convergence to the SPE.
  • MQ-learning: Theorem 2 states that for any ε > 0, there exists an exploration threshold σ such that if all agents use exploration thresholds less than σ, the expected Q-values will converge to within an ε-range of the SPE rewards. This also implies collective convergence.

Experimental results (Figures 3, 4, and 5) on the example game demonstrate that both MLA and MQ-learning successfully lead to strategy profiles that are very close to the SPE. For instance, in Figure 4, a smaller learning rate for one player leads to a strategy profile even closer to the SPE.

Limitations and Future Work

  • Incomplete Information: The current work is limited to complete-information extensive games. The authors acknowledge that in games with incomplete information, players cannot always observe past actions, leading to a more complex learning problem akin to Partially Observable Markov Decision Processes (POMDPs). They suggest extending their single-agent learning algorithms for POMDPs to this multi-agent context as future work.
  • Computational Complexity: While convergence is proven, the practical speed of convergence and the computational cost of these algorithms in very large game trees are not extensively discussed.
  • Exploration vs. Exploitation Trade-off: For MQ-learning, the authors note that larger exploration thresholds can accelerate convergence but also enlarge the error range, highlighting the inherent trade-off. Similarly, larger learning rates in MLA can speed up learning but may amplify variance. Finding optimal parameters for these trade-offs in practice remains a challenge.

Summary updated

BibTeX
@inproceedings{huang2003multi,
  author = {Pu Huang and Katia Sycara},
  title = {{Multi-agent learning in extensive games with complete information}},
  booktitle = {Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems - AAMAS '03},
  year = {2003},
  doi = {10.1145/860685.860688},
}
Figure