Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits

Mengxiao Zhang

doi:10.48550/arxiv.2608.15996

Back

Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits

Preprint

Open access

Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits

Mengxiao Zhang

arXiv

08/17/2026

DOI: 10.48550/arxiv.2608.15996

Files and links (1)

url

https://doi.org/10.48550/arxiv.2608.15996View

Preprint (Author's original) This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

We study second-order path-length regret in adversarial K -armed bandits against oblivious loss sequences. Bubeck et al. [2019] designed an algorithm that achieves [formula ommitted] regret, where Q_(∞,1)is the first-order path length, and left open whether [formula omitted] regret is achievable under bandit feedback, where Q_(∞,2)is the second-order path length. Somewhat surprisingly, we resolve this question positively by showing that with a more involved analysis, the exact same algorithm of Bubeck et al. [2019] achieves [formula omitted] expected regret when Q_(∞,2)is known, where Tis the horizon. This matches the Ω(√K̅Q̅_̅(̅∞̅,̅2̅)̅) lower bound up to logarithmic factors and additive terms. We further remove the knowledge of Q_(∞,2)using an adaptive restart scheme whose path-length estimator has uniformly bounded increments.

Computer Science - Learning

Details

Title: Subtitle: Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits
Creators: Mengxiao Zhang
Resource Type: Preprint
Publication Details: arXiv
DOI: 10.48550/arxiv.2608.15996
ISSN: 2331-8422
Publisher: arXiv
Language: English
Date posted: 08/17/2026
Academic Unit: Business Analytics
Record Identifier: 9985219918402771

Metrics

1 Record Views