Arbitrary side observations in bandit problems

Research output: Contribution to journalArticle

11 Scopus citations

Abstract

A bandit problem with side observations is an extension of the traditional two-armed bandit problem, in which the decision maker has access to side information before deciding which arm to pull. In this paper, essential properties of the side observations that allow achievability results with respect to optimal regret are extracted and formalized. The sufficient conditions for good side information obtained here admit various types of random processes as special cases, including i.i.d. sequences, Markov chains, deterministic periodic sequences, etc. A simple necessary condition for optimal regret is given, providing further insight into the nature of bandit problems with side observations. A game-theoretic approach simplifies the analysis and justifies the viewpoint that the side observation serves as an index specifying different sub-bandit machines.

Original languageEnglish (US)
Pages (from-to)903-938
Number of pages36
JournalAdvances in Applied Mathematics
Volume34
Issue number4 SPEC. ISS.
DOIs
StatePublished - May 2005

All Science Journal Classification (ASJC) codes

  • Applied Mathematics

Keywords

  • Adaptive
  • Allocation rule
  • Arbitrary
  • Asymptotic
  • Efficient
  • Evenly distributed
  • Regret
  • Side information
  • Two-armed bandit

Fingerprint Dive into the research topics of 'Arbitrary side observations in bandit problems'. Together they form a unique fingerprint.

  • Cite this