A Characterization of Perfect Strategies for Mirror Games

• URL: http://arxiv.org/abs/2302.04557v3
• Date: Thu, 11 May 2023 07:45:26 GMT
• Title: A Characterization of Perfect Strategies for Mirror Games
• Authors: Sizhuo Yan, Jianting Yang, Tianshi Yu, Lihong Zhi
• Abstract summary: We associate mirror games with the universal game algebra and use the *-representation to describe quantum commuting operator strategies. An algorithm based on noncommutative Gr"obner basis computation and semidefinite programming is given for certifying that a given mirror game has no perfect commuting operator strategies.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We associate mirror games with the universal game algebra and use the *-representation to describe quantum commuting operator strategies. We provide an algebraic characterization of whether or not a mirror game has perfect commuting operator strategies. This new characterization uses a smaller algebra introduced by Paulsen and others for synchronous games and the noncommutative Nullstellensatz developed by Cimpric, Helton and collaborators. An algorithm based on noncommutative Gr\"obner basis computation and semidefinite programming is given for certifying that a given mirror game has no perfect commuting operator strategies.

Related papers

• Runtime analysis of a coevolutionary algorithm on impartial combinatorial games [1.104960878651584]
  Coevolutionary algorithms (CoEAs) evolve a population of individuals by iteratively selecting the strongest based on their interactions against contemporaries, and using those selected as parents for the following generation. However, the successful application of CoEAs for game playing is difficult due to pathological behaviours such as cycling, an issue especially critical for games with in runtime payoff landscapes. In this paper, we push the scope of analysis to discover an optimal strategy for an impartial game. This result applies to any impartial game, and for many games the implied bound is or quasipolynomial as a function of the number of
  arXiv  Detail & Related papers  (2024-09-06T10:39:17Z)
• Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
  We introduce NeuPL-JPSRO, a neural population learning algorithm that benefits from transfer learning of skills and converges to a Coarse Correlated (CCE) of the game. Our work shows that equilibrium convergent population learning can be implemented at scale and in generality.
  arXiv  Detail & Related papers  (2024-01-10T12:56:24Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  We propose and analyze new fictitious play policy optimization algorithms for zero-sum Markov games with structured but unknown transitions. We prove tight $widetildemathcalO(sqrtK)$ regret bounds after $K$ episodes in a two-agent competitive game scenario. Our algorithms feature a combination of Upper Confidence Bound (UCB)-type optimism and fictitious play under the scope of simultaneous policy optimization.
  arXiv  Detail & Related papers  (2022-07-25T18:29:16Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  We show that regret can be obtained for general convex and compact strategy sets. Our dynamics are on an instantiation of optimistic follow-the-regularized-bounds over an appropriately emphlifted space. Even in those special cases where prior results apply, our algorithm improves over the state-of-the-art regret.
  arXiv  Detail & Related papers  (2022-06-17T12:58:58Z)
• Alternating Mirror Descent for Constrained Min-Max Games [44.46086335474311]
  We study two-player bilinear zero-sum games with constrained strategy spaces. We analyze the alternating mirror descent algorithm, in which each player takes turns to take action following the mirror descent algorithm for constrained optimization.
  arXiv  Detail & Related papers  (2022-06-08T20:48:16Z)
• Strategizing against Learners in Bayesian Games [74.46970859427907]
  We study repeated two-player games where one of the players, the learner, employs a no-regret learning strategy. We consider general Bayesian games, where the payoffs of both the payoffs of both the learner and the learner could depend on the type.
  arXiv  Detail & Related papers  (2022-05-17T18:10:25Z)
• Noncommutative Nullstellens\"atze and Perfect Games [0.0]
  The foundations of classical Algebraic Geometry and Real Algebraic Geometry are the Nullsatz and Positivsatz. This paper concerns commuting operator strategies for nonlocal games. Results are spread over different literatures, hence rather than being terse, our style is fairly expository.
  arXiv  Detail & Related papers  (2021-11-29T20:05:33Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  Two-team zero-sum games are defined as multi-player games where players are split into two competing sets of agents. We focus on the solution concept of Nash equilibria (NE) We show that computing NE for this class of games is $textithard$ for the complexity class $mathrm$.
  arXiv  Detail & Related papers  (2021-11-07T21:15:35Z)
• Discovering Multi-Agent Auto-Curricula in Two-Player Zero-Sum Games [31.97631243571394]
  We introduce a framework, LMAC, that automates the discovery of the update rule without explicit human design. Surprisingly, even without human design, the discovered MARL algorithms achieve competitive or even better performance. We show that LMAC is able to generalise from small games to large games, for example training on Kuhn Poker and outperforming PSRO.
  arXiv  Detail & Related papers  (2021-06-04T22:30:25Z)
• 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.