An improved regret analysis for UCB-N and TS-N
Nishant A. Mehta
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
$\log_2(\alpha) + 3$ for $\alpha$ the independence number of the feedback
graph.