Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Hedging in games: Faster convergence of external and swap regrets
Authors: Xi Chen, Binghui Peng
NeurIPS 2020 | Venue PDF | 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 EMAIL Binghui Peng Department of Computer Science Columbia University EMAIL |
| 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. |