Arbitrary side observations in bandit problems

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


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
Issue number4 SPEC. ISS.
StatePublished - May 2005

All Science Journal Classification (ASJC) codes

  • Applied Mathematics


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


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

Cite this