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

Nishant A. Mehta
5/6/2023
cs.LG

No confident code implementation found for this paper. 2 possible matches can be shown below.

Abstract

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(α) + 3$ for $α$ the independence number of the feedback graph.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. 2 weaker matches are hidden by default — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

On the Minimax Regret for Online Learning with Feedback Graphs

85% match2023

Online Learning with Feedback Graphs: The True Shape of Regret

83% match2023

Regret Analysis for Randomized Gaussian Process Upper Confidence Bound

83% match2024

Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits

82% match2026

Graph Feedback Bandits with Similar Arms

82% match1 repo2024

Graph Feedback Bandits on Similar Arms: With and Without Graph Structures

82% match1 repo2025

Cite this paper

@article{mehta2023improved,
  title  = {An improved regret analysis for UCB-N and TS-N},
  author = {Nishant A. Mehta},
  year   = {2023},
  eprint = {2305.04093},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2305.04093v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2305.04093.svg)](https://codeofpaper.com/paper/2305.04093)

Discussion