Hedging in games: Faster convergence of external and swap regrets
Authors: Xi Chen, Binghui Peng
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | For two-player games, we show that the regret of optimistic Hedge decays at rate O(1/T 5/6), improving the previous bound of O(1/T 3/4) by Syrgkanis, Agarwal, Luo and Schapire [27]. In contrast, we show that the convergence rate of vanilla Hedge is no better than O(1/ T), addressing an open question posed in Syrgkanis, Agarwal, Luo and Schapire [27]. For general m-player games, we show that the swap regret of each player decays at O(m1/2(n log n/T)3/4) when they combine optimistic Hedge with the classical external-to-internal reduction of Blum and Mansour [6]. Via standard connections, our new (swap) regret bounds imply faster convergence to coarse correlated equilibria in two-player games and to correlated equilibria in multiplayer games. Our main technical lemma behind Theorem 5.1 shows that strategies produced by the algorithm of [6] with optimistic Hedge moves very slowly in ℓ1-norm under the adversarial setting (which in turn allows us to apply a stability argument similar to [27]). |
| Researcher Affiliation | Academia | Xi Chen Department of Computer Science Columbia University xichen@cs.columbia.edu Binghui Peng Department of Computer Science Columbia University bp2601@columbia.edu |
| Pseudocode | No | The paper describes algorithms mathematically (e.g., updating rule for Hedge) but does not provide structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any explicit statements about making code open-source or include links to code repositories for the described methodology. |
| Open Datasets | No | This is a theoretical paper and does not mention the use of any datasets for training. |
| Dataset Splits | No | This is a theoretical paper and does not mention any training/validation/test splits or cross-validation. |
| Hardware Specification | No | This is a theoretical paper; no computational experiments requiring specific hardware specifications were performed or reported. |
| Software Dependencies | No | This is a theoretical paper. It does not mention any software dependencies with specific version numbers as it does not involve computational implementation details. |
| Experiment Setup | No | This is a theoretical paper. It does not describe an experimental setup with hyperparameters or system-level training settings. |