Hedging in games: Faster convergence of external and swap regrets

2020/06/08 by Xi Chen, Binghui Peng, Chen, Xi +1 · 8 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Channel (broadcasting) #Combinatorics #Computer Science and Game Theory (cs.GT) #Computer science #Data Structures and Algorithms (cs.DS) #Economics #FOS: Computer and information sciences #Game Theory and Applications #Hedge #Mathematical economics #Mathematics #Rate of convergence #Regret #Reinforcement Learning in Robotics #Statistics #Swap (finance) #Telecommunications #Upper and lower bounds #cs.DS #cs.GT

paper · pdf · doi:10.48550/arxiv.2006.04953

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2020/06/08 · arxiv created 2020/10/19 · arxiv updated 2020/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the setting where players run the Hedge algorithm or its optimistic variant to play an n-action game repeatedly for T rounds. 1) For two-player games, we show that the regret of optimistic Hedge decays at O( 1/T ^5/6 ), improving the previous bound O(1/T^3/4) by Syrgkanis, Agarwal, Luo and Schapire (NIPS'15) 2) In contrast, we show that the convergence rate of vanilla Hedge is no better than Ω(1/ √(T)), addressing an open question posted in Syrgkanis, Agarwal, Luo and Schapire (NIPS'15). For general m-player games, we show that the swap regret of each player decays at rate O(m^1/2 (n/T)^3/4) when they combine optimistic Hedge with the classical external-to-internal reduction of Blum and Mansour (JMLR'07). The algorithm can also be modified to achieve the same rate against itself and a rate of O(√(n/T)) against adversaries. Via standard connections, our upper bounds also imply faster convergence to coarse correlated equilibria in two-player games and to correlated equilibria in multiplayer games.

Citations

• Online Learning with Predictable Sequences
• Acceleration through Optimistic No-Regret Dynamics

Cited by

• Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games
• Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games
• Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Games
• Efficient Kernelized Learning in Polyhedral Games Beyond Full-Information: From Colonel Blotto to Congestion Games
• Optimism Without Regularization: Constant Regret in Zero-Sum Games
• From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications
• Pointwise Convergence in Games with Conflicting Interest
• Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization

Related

• Exponentially fast convergence to (strict) equilibrium via hedging
• Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Games
• Near-Optimal No-Regret Learning in General Games
• Learning in Games: Robustness of Fast Convergence
• Fast swap regret minimization and applications to approximate correlated equilibria