Finite-Sample Guarantees for Best-Response Learning Dynamics in Zero-Sum Matrix Games

• URL: http://arxiv.org/abs/2407.20128v2
• Date: Wed, 7 Aug 2024 19:04:48 GMT
• Title: Finite-Sample Guarantees for Best-Response Learning Dynamics in Zero-Sum Matrix Games
• Authors: Fathima Zarin Faizal, Asuman Ozdaglar, Martin J. Wainwright,
• Abstract summary: We study best-response type learning dynamics for two player zero-sum matrix games. We consider two settings that are distinguished by the type of information that each player has about the game and their opponent's strategy.
• Score: 22.380293155135096
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study best-response type learning dynamics for two player zero-sum matrix games. We consider two settings that are distinguished by the type of information that each player has about the game and their opponent's strategy. The first setting is the full information case, in which each player knows their own and the opponent's payoff matrices and observes the opponent's mixed strategy. The second setting is the minimal information case, where players do not observe the opponent's strategy and are not aware of either of the payoff matrices (instead they only observe their realized payoffs). For this setting, also known as the radically uncoupled case in the learning in games literature, we study a two-timescale learning dynamics that combine smoothed best-response type updates for strategy estimates with a TD-learning update to estimate a local payoff function. For these dynamics, without additional exploration, we provide polynomial-time finite-sample guarantees for convergence to an $\epsilon$-Nash equilibrium.

Related papers

• From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications [54.49053278073321]
  We show that for a large family of games, there exists a simple black-box reduction that transforms the average iterates of an uncoupled learning dynamics into the last iterates of a new uncoupled learning dynamics.<n>Our reduction applies to games where each player's utility is linear in both their own strategy and the joint strategy of all opponents.
  arXiv  Detail & Related papers  (2025-06-04T00:24:14Z)
• Guarantees for Self-Play in Multiplayer Games via Polymatrix Decomposability [2.2636685010313364]
  Self-play is a technique for machine learning in multi-agent systems where a learning algorithm learns by interacting with copies of itself. We show that in two-player constant-sum games, self-play that reaches Nash equilibrium is guaranteed to produce strategies that perform well against any post-training opponent. For the first time, our results identify a structural property of multiplayer games that enable performance guarantees for the strategies produced by a broad class of self-play algorithms.
  arXiv  Detail & Related papers  (2023-10-17T18:33:21Z)
• All by Myself: Learning Individualized Competitive Behaviour with a Contrastive Reinforcement Learning optimization [57.615269148301515]
  In a competitive game scenario, a set of agents have to learn decisions that maximize their goals and minimize their adversaries' goals at the same time. We propose a novel model composed of three neural layers that learn a representation of a competitive game, learn how to map the strategy of specific opponents, and how to disrupt them. Our experiments demonstrate that our model achieves better performance when playing against offline, online, and competitive-specific models, in particular when playing against the same opponent multiple times.
  arXiv  Detail & Related papers  (2023-10-02T08:11:07Z)
• ApproxED: Approximate exploitability descent via learned best responses [61.17702187957206]
  We study the problem of finding an approximate Nash equilibrium of games with continuous action sets. We propose two new methods that minimize an approximation of exploitability with respect to the strategy profile.
  arXiv  Detail & Related papers  (2023-01-20T23:55:30Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. We model players' strategies using artificial neural networks. This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
  arXiv  Detail & Related papers  (2022-11-29T05:16:41Z)
• A Ranking Game for Imitation Learning [22.028680861819215]
  We treat imitation as a two-player ranking-based Stackelberg game between a $textitpolicy$ and a $textitreward$ function. This game encompasses a large subset of both inverse reinforcement learning (IRL) methods and methods which learn from offline preferences. We theoretically analyze the requirements of the loss function used for ranking policy performances to facilitate near-optimal imitation learning at equilibrium.
  arXiv  Detail & Related papers  (2022-02-07T19:38:22Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  Learning from repeated play in a fixed zero-sum game is a classic problem in game theory and online learning. We develop a single parameter-free algorithm that simultaneously enjoys favorable guarantees under three performance measures. Our algorithm is based on a two-layer structure with a meta-algorithm learning over a group of black-box base-learners satisfying a certain property.
  arXiv  Detail & Related papers  (2022-01-30T06:10:04Z)
• L2E: Learning to Exploit Your Opponent [66.66334543946672]
  We propose a novel Learning to Exploit framework for implicit opponent modeling. L2E acquires the ability to exploit opponents by a few interactions with different opponents during training. We propose a novel opponent strategy generation algorithm that produces effective opponents for training automatically.
  arXiv  Detail & Related papers  (2021-02-18T14:27:59Z)
• Independent Policy Gradient Methods for Competitive Reinforcement Learning [62.91197073795261]
  We obtain global, non-asymptotic convergence guarantees for independent learning algorithms in competitive reinforcement learning settings with two agents. We show that if both players run policy gradient methods in tandem, their policies will converge to a min-max equilibrium of the game, as long as their learning rates follow a two-timescale rule.
  arXiv  Detail & Related papers  (2021-01-11T23:20:42Z)
• On the Impossibility of Convergence of Mixed Strategies with No Regret Learning [10.515544361834241]
  We study convergence properties of the mixed strategies that result from a general class of optimal no regret learning strategies. We consider the class of strategies whose information set at each step is the empirical average of the opponent's realized play.
  arXiv  Detail & Related papers  (2020-12-03T18:02:40Z)
• Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
  We consider a repeated sequential game between a learner, who plays first, and an opponent who responds to the chosen action. We propose a novel algorithm for the learner when playing against an adversarial sequence of opponents. Our results include algorithm's regret guarantees that depend on the regularity of the opponent's response.
  arXiv  Detail & Related papers  (2020-07-10T09:33:05Z)
• Deep Reinforcement Learning for FlipIt Security Game [2.0624765454705654]
  We describe a deep learning model in which agents adapt to different classes of opponents and learn the optimal counter-strategy. We apply our model to FlipIt, a two-player security game in which both players, the attacker and the defender, compete for ownership of a shared resource. Our model is a deep neural network combined with Q-learning and is trained to maximize the defender's time of ownership of the resource.
  arXiv  Detail & Related papers  (2020-02-28T18:26:24Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  We investigate the increasingly important and common game-solving setting where we do not have an explicit description of the game but only oracle access to it through gameplay. During a limited-duration learning phase, the algorithm can control the actions of both players in order to try to learn the game and how to play it well. Our motivation is to quickly learn strategies that have low exploitability in situations where evaluating the payoffs of a queried strategy profile is costly.
  arXiv  Detail & Related papers  (2020-02-24T20:30:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.