A Closer Look at Small-loss Bounds for Bandits with Graph Feedback

Chung-Wei Lee; Haipeng Luo; Mengxiao Zhang

doi:10.48550/arxiv.2002.00315

Back

Preprint

Open access

A Closer Look at Small-loss Bounds for Bandits with Graph Feedback

Chung-Wei Lee, Haipeng Luo and Mengxiao Zhang

ArXiv.org

Cornell University

06/23/2020

DOI: 10.48550/arxiv.2002.00315

Files and links (1)

url

https://doi.org/10.48550/arXiv.2002.00315View

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 small-loss bounds for adversarial multi-armed bandits with graph feedback, that is, adaptive regret bounds that depend on the loss of the best arm or related quantities, instead of the total number of rounds. We derive the first small-loss bound for general strongly observable graphs, resolving an open problem of Lykouris et al. (2018). Specifically, we develop an algorithm with regret O~(κL∗−−−√) where κ is the clique partition number and L∗ is the loss of the best arm, and for the special case of self-aware graphs where every arm has a self-loop, we improve the regret to O~(min{αT−−−√,κL∗−−−√}) where α≤κ is the independence number. Our results significantly improve and extend those by Lykouris et al. (2018) who only consider self-aware undirected graphs. Furthermore, we also take the first attempt at deriving small-loss bounds for weakly observable graphs. We first prove that no typical small-loss bounds are achievable in this case, and then propose algorithms with alternative small-loss bounds in terms of the loss of some specific subset of arms. A surprising side result is that O~(T−−√) regret is achievable even for weakly observable graphs as long as the best arm has a self-loop. Our algorithms are based on the Online Mirror Descent framework but require a suite of novel techniques that might be of independent interest. Moreover, all our algorithms can be made parameter-free without the knowledge of the environment.

Computer Science - Learning

Statistics - Machine Learning

Details

Title: Subtitle: A Closer Look at Small-loss Bounds for Bandits with Graph Feedback
Creators: Chung-Wei Lee
Haipeng Luo
Mengxiao Zhang
Resource Type: Preprint
Publication Details: ArXiv.org
Publisher: Cornell University; Ithaca, New York
DOI: 10.48550/arxiv.2002.00315
eISSN: 2331-8422
Language: English
Date posted: 06/23/2020
Academic Unit: Business Analytics
Record Identifier: 9984701825802771

Metrics

6 Record Views