Fictitious Play with Maximin Initialization

• URL: http://arxiv.org/abs/2203.10774v2
• Date: Tue, 22 Mar 2022 02:02:33 GMT
• Title: Fictitious Play with Maximin Initialization
• Authors: Sam Ganzfried
• Abstract summary: Fictitious play is the most accurate scalable algorithm for Nash equilibrium strategies in multiplayer games. We show that the equilibrium approximation error of fictitious play can be significantly reduced by carefully the degree of initial strategies.
• Score: 1.7132914341329848
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Fictitious play has recently emerged as the most accurate scalable algorithm for approximating Nash equilibrium strategies in multiplayer games. We show that the degree of equilibrium approximation error of fictitious play can be significantly reduced by carefully selecting the initial strategies. We present several new procedures for strategy initialization and compare them to the classic approach, which initializes all pure strategies to have equal probability. The best-performing approach, called maximin, solves a nonconvex quadratic program to compute initial strategies and results in a nearly 75% reduction in approximation error compared to the classic approach when 5 initializations are used.

Related papers

• Decoding Game: On Minimax Optimality of Heuristic Text Generation Strategies [7.641996822987559]
  We propose Decoding Game, a comprehensive theoretical framework which reimagines text generation as a two-player zero-sum game between Strategist and Nature. It is shown that the adversarial Nature imposes an implicit regularization on likelihood, and truncation-normalization methods are first order approximations to the optimal strategy under this regularization.
  arXiv  Detail & Related papers  (2024-10-04T23:18:27Z)
• Landscape-Aware Growing: The Power of a Little LAG [49.897766925371485]
  We study the question of how to select the best growing strategy from a given pool of growing strategies. We present an alternative perspective based on early training dynamics, which we call "landscape-aware growing (LAG)"
  arXiv  Detail & Related papers  (2024-06-04T16:38:57Z)
• 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)
• No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization [20.718016474717196]
  We develop an algorithmic framework for solving convex optimization problems using no-regret game dynamics. A common choice for these strategies are so-called no-regret learning algorithms. We show that many classical first-order methods for convex optimization can be interpreted as special cases of our framework.
  arXiv  Detail & Related papers  (2021-11-22T16:10:18Z)
• Provably Efficient Policy Gradient Methods for Two-Player Zero-Sum Markov Games [95.70078702838654]
  This paper studies natural extensions of Natural Policy Gradient algorithm for solving two-player zero-sum games. We thoroughly characterize the algorithms' performance in terms of the number of samples, number of iterations, concentrability coefficients, and approximation error.
  arXiv  Detail & Related papers  (2021-02-17T17:49:57Z)
• Learning to Initialize Gradient Descent Using Gradient Descent [21.02474345607079]
  Non- optimization problems are challenging to solve. As a simple alternative to hand-crafted algorithms, we propose an approach for learning that performs better than random algorithms.
  arXiv  Detail & Related papers  (2020-12-22T16:23:36Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  Motivated by recent increased interest in analysis of optimization algorithms for non- optimization in deep networks and other problems in data, we give an overview of recent results of theoretical optimization algorithms for non- optimization.
  arXiv  Detail & Related papers  (2020-12-11T08:28:51Z)
• Efficient Competitive Self-Play Policy Optimization [20.023522000925094]
  We propose a new algorithmic framework for competitive self-play reinforcement learning in two-player zero-sum games. Our method trains several agents simultaneously, and intelligently takes each other as opponent based on simple adversarial rules. We prove theoretically that our algorithm converges to an approximate equilibrium with high probability in convex-concave games.
  arXiv  Detail & Related papers  (2020-09-13T21:01:38Z)
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles [112.89548995091182]
  We provide the first universal and optimal reduction from contextual bandits to online regression. Our algorithm requires no distributional assumptions beyond realizability, and works even when contexts are chosen adversarially.
  arXiv  Detail & Related papers  (2020-02-12T11:33:46Z)

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.