2025/02/25 by Brian Hu Zhang, Ioannis Anagnostides, Zhang, Brian Hu +12 · 1 voice · 1 citation
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics #cs.GT #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.2502.18582
openalex publication_date 2025/02/25 · arxiv published 2025/02/25 · openalex created_date 2025/10/10 · arxiv updated 2025/12/13 · openalex updated_date 2026/07/30
Φ-equilibria -- and the associated notion of Φ-regret -- are a powerful and flexible framework at the heart of online learning and game theory, whereby enriching the set of deviations Φ begets stronger notions of rationality. Recently, Daskalakis, Farina, Fishelson, Pipis, and Schneider (STOC '24) -- abbreviated as DFFPS -- settled the existence of efficient algorithms when Φ contains only linear maps under a general, d-dimensional convex constraint set X. In this paper, we significantly extend their work by resolving the case where Φ is k-dimensional; degree-ℓ polynomials constitute a canonical such example with k = dO(ℓ). In particular, positing only oracle access to X, we obtain two main positive results: i) a poly(n, d, k, log(1/ε))-time algorithm for computing ε-approximate Φ-equilibria in n-player multilinear games, and ii) an efficient online algorithm that incurs average Φ-regret at most ε using poly(d, k)/ε2 rounds. We also show nearly matching lower bounds in the online learning setting, thereby obtaining for the first time a family of deviations that captures the learnability of Φ-regret. From a technical standpoint, we extend the framework of DFFPS from linear maps to the more challenging case of maps with polynomial dimension. At the heart of our approach is a polynomial-time algorithm for computing an expected fixed point of any ϕ: X → X based on the ellipsoid against hope (EAH) algorithm of Papadimitriou and Roughgarden (JACM '08). In particular, our algorithm for computing Φ-equilibria is based on executing EAH in a nested fashion -- each step of EAH itself being implemented by invoking a separate call to EAH.