On Similarities between Inference in Game Theory and Machine Learning

Iead Rezek, David S. Leslie, Steven Reece, Stephen J. Roberts, Alex Rogers, Rajdeep K. Dash, Nicholas R. JenningsJAIR 2008 · DOI · OpenReview

TL;DR

This paper bridges the gap between game theory and machine learning by demonstrating a deep equivalence between inference in repeated games and variational learning algorithms. By leveraging insights from each field, the authors develop novel algorithms for both game theory (moderated fictitious play) and machine learning (fictitious variational play and derivative action variational learning) that exhibit improved convergence properties.

What Problem Does This Paper Address?

Traditionally, game theory and machine learning have been treated as distinct fields. However, this paper argues that there are significant commonalities, particularly in the problem of making inferences based on past observations. The challenge is to formalize these connections to enable cross-fertilization of ideas and development of improved algorithms. Specifically, the paper addresses how to improve learning algorithms in both domains by drawing analogies between concepts like "best responses" in game theory and "inference" in machine learning.

Methods

The paper proposes several novel algorithms by drawing analogies between the two fields:

  • Moderated Fictitious Play: Inspired by Bayesian inference in machine learning, this approach modifies standard fictitious play by integrating over the distribution of opponent strategies rather than using a simple empirical average. This leads to a more robust learning process.
  • Fictitious Variational Play: This algorithm is derived by viewing the mean-field variational learning algorithm as a Cournot adjustment process in a partnership game. By analogy with fictitious play, an improved update rule is proposed, leading to better convergence, especially in strongly connected graphical models.
  • Derivative Action Variational Learning Algorithm (DAVA): This algorithm incorporates insights from "dynamic fictitious play" into the variational mean-field method. It adds a derivative term to the update rule, acting as an "anticipatory" component that speeds up convergence, particularly in non-stationary environments.

Datasets

The paper uses synthetic data for evaluating the algorithms. Specifically:

  • A simple coordination game is used to demonstrate the convergence properties of moderated fictitious play.
  • A synthetic dataset generated from a mixture of 3 Gaussian distributions with a non-linear mapping function is used to evaluate DAVA.
  • Real-world medical magnetic resonance data (T2 and proton density spin sequences) is used to test DAVA on a clustering problem.

Key Insights and Ideas

  • Equivalence of Inference: The core insight is that inference in game theory (specifically, learning in games) and variational learning in machine learning are fundamentally equivalent. This equivalence provides a powerful framework for cross-pollination.
  • Bayesian Moderation for Fictitious Play: Applying Bayesian inference principles (integrating over uncertainty) to fictitious play leads to "moderated fictitious play," which is more likely to converge to payoff-dominant Nash equilibria, especially in coordination games.
  • Game Theory for Variational Learning: Viewing variational learning as a game allows for the application of game-theoretic concepts like fictitious play and Cournot adjustment to improve variational learning algorithms. This leads to algorithms like "fictitious variational play" that overcome issues like "thrashing."
  • Dynamic Learning for Robustness: Incorporating dynamic elements from game theory (like dynamic fictitious play) into variational learning results in algorithms like DAVA that can adapt to changing environments and exhibit faster convergence.
  • Adaptive Classifiers as Game Players: The paper suggests that adaptive classifiers, common in machine learning, can be viewed as models of players learning from each other in dynamic game-theoretic settings, offering a path towards more practical applications in non-stationary environments.

Key Results

  • Moderated Fictitious Play: Demonstrated to be more likely than standard fictitious play to converge to a payoff-dominant Nash equilibrium in a simple coordination game.
  • Fictitious Variational Play: Shown to exhibit better convergence properties in highly connected graphical models compared to standard mean-field variational learning, mitigating "thrashing" behavior.
  • Derivative Action Variational Learning Algorithm (DAVA):
    • On synthetic data, DAVA converged more quickly than the standard variational algorithm, with median convergence rate improvements of up to 28% for certain parameter settings.
  • On real-world medical imaging data (MR scans), DAVA achieved segmentation in approximately half the time of the standard segmentation algorithm.
  • DAVA's performance was sensitive to a derivative coefficient ($\gamma$), with moderate values offering a good balance between speed and robustness.

Limitations and Future Work

  • Theoretical Guarantees for Continuous Variables: While convergence is proven for discrete variables in fictitious variational play, an equivalent theorem for continuous random variables is still needed, though the authors suggest it might be achievable with further work.
  • Extending DAVA: The authors believe further improvements to DAVA are possible by applying the derivative term to other parameters of the mixture model, not just the means.
  • Large-Scale Real-World Data: The authors plan to further analyze the performance of moderated fictitious play and the variational algorithms on larger, real-world datasets.
  • Dynamic Environments: The paper highlights the potential of adaptive classifiers for non-stationary environments and suggests further research into using dynamic estimators for strategies and environmental parameters to make game-theoretic learning more broadly applicable.

Summary updated

Abstract

In this paper, we elucidate the equivalence between inference in game theory and machine learning. Our aim in so doing is to establish an equivalent vocabulary between the two domains so as to facilitate developments at the intersection of both fields, and as proof of the usefulness of this approach, we use recent developments in each field to make useful improvements to the other. More specifically, we consider the analogies between smooth best responses in fictitious play and Bayesian inference methods. Initially, we use these insights to develop and demonstrate an improved algorithm for learning in games based on probabilistic moderation. That is, by integrating over the distribution of opponent strategies (a Bayesian approach within machine learning) rather than taking a simple empirical average (the approach used in standard fictitious play) we derive a novel moderated fictitious play algorithm and show that it is more likely than standard fictitious play to converge to a payoff-dominant but risk-dominated Nash equilibrium in a simple coordination game. Furthermore we consider the converse case, and show how insights from game theory can be used to derive two improved mean field variational learning algorithms. We first show that the standard update rule of mean field variational learning is analogous to a Cournot adjustment within game theory. By analogy with fictitious play, we then suggest an improved update rule, and show that this results in fictitious variational play, an improved mean field variational learning algorithm that exhibits better convergence in highly or strongly connected graphical models. Second, we use a recent advance in fictitious play, namely dynamic fictitious play, to derive a derivative action variational learning algorithm, that exhibits superior convergence properties on a canonical machine learning problem (clustering a mixture distribution).
BibTeX
@article{rezek2008similarities,
  author = {Iead Rezek and David S. Leslie and Steven Reece and Stephen J. Roberts and Alex Rogers and Rajdeep K. Dash and Nicholas R. Jennings},
  title = {{On Similarities between Inference in Game Theory and Machine Learning}},
  journal = {J. Artif. Intell. Res.},
  year = {2008},
  doi = {10.1613/jair.2523},
}
Figure