An improved regret analysis for UCB-N and TS-N
Not on the map. Why?
Abstract (arXiv)
In the setting of stochastic online learning with undirected feedback graphs, Lykouris et al. (2020) previously analyzed the pseudo-regret of the upper confidence bound-based algorithm UCB-N and the Thompson Sampling-based algorithm TS-N. In this note, we show how to improve their pseudo-regret analysis. Our improvement involves refining a key lemma of the previous analysis, allowing a log(T) factor to be replaced by a factor log2(α) + 3 for α the independence number of the feedback graph.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 1 of its 4 references that are in the map. First posted on arXiv 6 May 2023.
Builds on
1 of 4 references.
References · 1
- 2019Feedback graph regret bounds for Thompson Sampling and UCBcited by 17
Built on by
Not cited yet.