Optimistic Online Learning in Symmetric Cone Games

• URL: http://arxiv.org/abs/2504.03592v3
• Date: Tue, 26 Aug 2025 02:12:10 GMT
• Title: Optimistic Online Learning in Symmetric Cone Games
• Authors: Anas Barakat, Wayne Lin, John Lazarsfeld, Antonios Varvitsiotis,
• Abstract summary: symmetric cone games (SCGs)<n>Online learning algorithm: Optimistic Symmetric Cone Multiplicative Weights Updates (OSCMWU)<n>We prove that the symmetric cone negative entropy is strongly convex with respect to the trace-one norm.
• Score: 5.4831302830611195
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce symmetric cone games (SCGs), a broad class of multi-player games where each player's strategy lies in a generalized simplex (the trace-one slice of a symmetric cone). This framework unifies a wide spectrum of settings, including normal-form games (simplex strategies), quantum games (density matrices), and continuous games with ball-constrained strategies. It also captures several structured machine learning and optimization problems, such as distance metric learning and Fermat-Weber facility location, as two-player zero-sum SCGs. To compute approximate Nash equilibria in two-player zero-sum SCGs, we propose a single online learning algorithm: Optimistic Symmetric Cone Multiplicative Weights Updates (OSCMWU). Unlike prior methods tailored to specific geometries, OSCMWU provides closed-form, projection-free updates over any symmetric cone and achieves an optimal $\tilde{\mathcal{O}}(1/\epsilon)$ iteration complexity for computing $\epsilon$-saddle points. Our analysis builds on the Optimistic Follow-the-Regularized-Leader framework and hinges on a key technical contribution: We prove that the symmetric cone negative entropy is strongly convex with respect to the trace-one norm. This result extends known results for the simplex and spectraplex to all symmetric cones, and may be of independent interest.

Related papers

• Approximating fixed size quantum correlations in polynomial time [8.099700053397278]
  We show that $varepsilon$-additive approximations of the optimal value of fixed-size two-player free games can be computed in time.<n>Our main result is based on novel Bose-symmetric quantum de Finetti theorems tailored for constrained quantum separability problems.
  arXiv  Detail & Related papers  (2025-07-16T15:01:45Z)
• Computing Game Symmetries and Equilibria That Respect Them [77.72705755558839]
  We study the computational of identifying and using symmetries in games. We find a strong connection between game symmetries and graph automorphisms. We show that finding a Nash equilibrium that respects a given set of symmetries is exactly as hard as Brouwer fixed point and gradient descent problems.
  arXiv  Detail & Related papers  (2025-01-15T16:15:16Z)
• Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation [52.16923999754027]
  We give an algorithm for computing a Stackelberg extensive-form correlated equilibrium.<n>We also give an efficient algorithm for approximately computing an optimal extensive-form correlated equilibrium.<n>Our algorithm for approximately optimal EFCE is, to our knowledge, the first that achieves 3 desiderata simultaneously.
  arXiv  Detail & Related papers  (2024-12-22T09:12:05Z)
• Last-Iterate Convergence of Payoff-Based Independent Learning in Zero-Sum Stochastic Games [31.554420227087043]
  We develop learning dynamics that are payoff-based, convergent, rational, and symmetric between the two players. In the matrix game setting, the results imply a complexity of $O(epsilon-1)$ to find the Nash distribution. In the game setting, the results also imply a complexity of $O(epsilon-8)$ to find a Nash equilibrium.
  arXiv  Detail & Related papers  (2024-09-02T20:07:25Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
  We introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $mathcalO(d/epsilon)$ to $epsilon$-Nash equilibria. This quadratic speed-up sets a new benchmark for computing $epsilon$-Nash equilibria in quantum zero-sum games.
  arXiv  Detail & Related papers  (2023-11-17T20:38:38Z)
• Hierarchies for Semidefinite Optimization in $\mathcal{C}^\star$-Algebras [0.0]
  This paper presents a way for finite-dimensional relaxations of general cone programs on $mathcalCstar$-algebras. We show that well-known hierarchies for generalized problems like NPA but also Lasserre's hierarchy and to some extend symmetry reductions of generic SDPs.
  arXiv  Detail & Related papers  (2023-09-25T09:01:30Z)
• Multiplicative Updates for Online Convex Optimization over Symmetric Cones [28.815822236291392]
  We introduce the Symmetric-Cone Multiplicative Weights Update (SCMWU), a projection-free algorithm for online optimization over the trace-one slice of an arbitrary symmetric cone. We show that SCMWU is equivalent to Follow-the-Regularized-Leader and Online Mirror Descent with symmetric-cone negative entropy as regularizer.
  arXiv  Detail & Related papers  (2023-07-06T17:06:43Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  We study multi-agent general-sum Markov games with nonlinear function approximation. We focus on low-rank Markov games whose transition matrix admits a hidden low-rank structure on top of an unknown non-linear representation.
  arXiv  Detail & Related papers  (2022-10-30T22:58:22Z)
• 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)
• Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
  We study the problem of finding optimal correlated equilibria of various sorts in extensive-form games. We introduce a new algorithm for computing optimal equilibria in all three notions.
  arXiv  Detail & Related papers  (2022-03-14T15:21:18Z)
• An algorithmic solution to the Blotto game using multi-marginal couplings [27.35514815248438]
  We describe an efficient algorithm to compute solutions for the general two-player Blotto game on n battlefields with heterogeneous values. Our algorithm samples from an eps-optimal solution in time O(n2 + eps-4) independently of budgets and battlefield values. In the case of asymmetric values where optimal solutions need not exist but Nash equilibria do, our algorithm samples from an eps-Nash equilibrium with similar complexity.
  arXiv  Detail & Related papers  (2022-02-15T11:07:31Z)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  We show that if all agents in a multi-player general-sum normal-form game employ Optimistic Multiplicative Weights Update (OMWU), the external regret of every player is $O(textrmpolylog(T))$ after $T$ repetitions of the game. We extend their result from external regret to internal regret and swap regret, thereby establishing uncoupled learning dynamics that converge to an approximate correlated equilibrium.
  arXiv  Detail & Related papers  (2021-11-11T01:19:53Z)
• 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)
• Multiplicative updates for symmetric-cone factorizations [0.0]
  We introduce and analyze the symmetric-cone multiplicative update (SCMU) algorithm for computing cone factorizations. We show that the squared loss objective is non-decreasing along the trajectories of the SCMU algorithm.
  arXiv  Detail & Related papers  (2021-08-02T09:23:39Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games. In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap. In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret.
  arXiv  Detail & Related papers  (2020-02-17T17:04:16Z)

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.