Skip to main navigation Skip to search Skip to main content

Bandits with side observations: Bounded vs. logarithmic regret

  • Sorbonne Université
  • Université Paris-Saclay
  • Criteo

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

6 Citations (Scopus)

Abstract

We consider the classical stochastic multi-armed bandit but where, from time to time and roughly with frequency e, an extra observation is gathered by the agent for free. We prove that, no matter how small e is the agent can ensure a regret uniformly bounded in time. More precisely, we construct an algorithm with a regret smaller than Σi log(1/ϵ)/Δi, up to multiplicative constant and log log terms. We also prove a matching lower-bound, stating that no reasonable algorithm can outperform this quantity.

Original languageEnglish
Title of host publicationUncertainty in Artificial Intelligence - Proceedings of the 34th Conference, UAI 2018
EditorsAmir Globerson, Amir Globerson, Ricardo Silva
PublisherAssociation For Uncertainty in Artificial Intelligence (AUAI)
Pages467-476
Number of pages10
ISBN (Electronic)9781510871601
Publication statusPublished - 1 Jan 2018
Externally publishedYes
Event34th Conference on Uncertainty in Artificial Intelligence, UAI 2018 - Monterey, United States
Duration: 6 Aug 2018 → 10 Aug 2018

Publication series

Name34th Conference on Uncertainty in Artificial Intelligence 2018, UAI 2018
Volume1

Conference

Conference34th Conference on Uncertainty in Artificial Intelligence, UAI 2018
Country/TerritoryUnited States
CityMonterey
Period6/08/18 → 10/08/18

Fingerprint

Dive into the research topics of 'Bandits with side observations: Bounded vs. logarithmic regret'. Together they form a unique fingerprint.

Cite this