# An improved regret analysis for UCB-N and TS-N

arXiv: https://arxiv.org/abs/2305.04093 · HTML: https://mlsanity.com/paper/2305.04093/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 4 references that are in the map.
- First posted on arXiv 6 May 2023.

## Builds on (most cited first, 1 of 1)

- [Feedback graph regret bounds for Thompson Sampling and UCB](https://mlsanity.com/paper/1905.09898/) (2019)

## 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.