The Budgeted Multi-armed Bandit Problem

Omid Madani, Daniel J. Lizotte, Russell GreinerCOLT 2004 · OpenReview

Abstract

The following coins problem is a version of a multi-armed bandit problem where one has to select from among a set of objects, say classifiers, after an experimentation phase that is constrained by a time or cost budget. The question is how to spend the budget. The problem involves pure exploration only, differentiating it from typical multi-armed bandit problems involving an exploration/exploitation tradeoff [BF85]. It is an abstraction of the following scenarios: choosing from among a set of alternative treatments after a fixed number of clinical trials, determining the best parameter settings for a program given a deadline that only allows a fixed number of runs; or choosing a life partner in the bachelor/bachelorette TV show where time is limited. We are interested in the computational complexity of the coins problem and/or efficient algorithms with approximation guarantees.
BibTeX
@inproceedings{madani2004budgeted,
  author = {Omid Madani and Daniel J. Lizotte and Russell Greiner},
  title = {{The Budgeted Multi-armed Bandit Problem}},
  booktitle = {Conference on Learning Theory},
  year = {2004},
  url = {https://openreview.net/forum?id=KBPFI4Azywm},
}

Loading related content...

Figure