Metraipolis › archive › dc_fcaedcace3cb

A Logarithmic Regret Bound for Optimistic Hedge in General-Sum Games — arXiv:2609.19677

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.19677
License (as archived): CC0-1.0
Archived: 2026-10-10T03:54:35.584Z
SHA-256 of the archived text: 2f865346baeb9d2a33ad5e8eac257dc0226ddd3bd69f931bd255415af95abd3c
Stable URL of this page: https://metraipolis.com/documento/dc_fcaedcace3cb

How to cite

A Logarithmic Regret Bound for Optimistic Hedge in General-Sum Games — arXiv:2609.19677 — arXiv (en), https://arxiv.org/abs/2609.19677 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fcaedcace3cb (Metraipolis archive dc_fcaedcace3cb, sha256 2f865346baeb9d2a33ad5e8eac257dc0226ddd3bd69f931bd255415af95abd3c)

BibTeX

@misc{dcfcaedcace3cb,
  title = {A Logarithmic Regret Bound for Optimistic Hedge in General-Sum Games — arXiv:2609.19677},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.19677},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fcaedcace3cb; sha256 2f865346baeb9d2a33ad5e8eac257dc0226ddd3bd69f931bd255415af95abd3c},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.19677. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Can simple no-regret dynamics attain smaller regret in self-play than against arbitrary adversaries? In $n$-player general-sum games, Daskalakis et al. 2021 proved an $O(n\log d_i\log^4 T)$ individual regret bound for Optimistic Hedge, which improves upon the classical $O(\sqrt T)$ adversarial regret bound. In this work, we show that Optimistic Hedge with a constant step size can further achieve $O(\sqrt n\log d_i\log T)$ individual external regret under expected loss-vector feedback. The time-averaged play consequently enjoys a coarse correlated equilibrium gap $O(\sqrt n\log d\log T/T)$, where $d=\max_i d_i$. The improvement comes from a larger admissible step size $\eta=\Theta(1/(\sqrt n\log T))$. Our analysis proves factorial bounds on high-order differences of probability-weighted pairwise loss gaps, then applies finite-difference interpolation in a fixed Euclidean norm. These estimates sharpen the analysis of Daskalakis et al. 2021 and yield a logarithmic regret bound.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-18 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2609.19677 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T03:25:20.233Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).