×

Denumerable-armed bandits. (English) Zbl 0771.90100

It is well known that finite-armed bandit problems with independent arms and discounting are solved by dynamic allocation (or Gittins) index policies. This result is generalized to the case of a countably infinite number of arms presenting necessary and sufficient conditions for the existence of optimal policies. In addition, structural results are proved concerning the “survival” of arms. For stationary bandits (each arm has the same prior) special properties are shown. Possible applications of these bandit models are discussed including job search, matching and voting problems.

MSC:

90C40 Markov and semi-Markov decision processes
90B35 Deterministic scheduling theory in operations research
91B40 Labor market, contracts (MSC2010)
91B12 Voting theory
PDFBibTeX XMLCite
Full Text: DOI Link