Denumerable-Armed Bandits

Abstract

This paper studies the class of denumerable-armed (i.e. finite- or countably infinitearmed) \nbandit problems with independent arms and geometric discounting over an \ninfinite horizon, in which each arm generates rewards according to one of a finite number \nof distributions, or "types." The number of types in the support of an arm, as also the \ntypes themselves, are allowed to vary across the arms. We derive certain continuity and \ncurvature properties of the dynamic allocation (or Gittins) index of Gittins and Jones \n(1974), and provide necessary and sufficient conditions under which the Gittins-Jones \nresult identifying all optimal strategies for finite-armed bandits may be extended to \ninfinite-armed bandits. We then establish our central result: at each point in time, the \narm selected by an optimal strategy will, with strictly positive probability, remain an \noptimal selection forever. More specifically, for every such arm, there exists (at least) one \ntype of that arm such that, when conditioned on that type being the arm's "true" type, \nthe arm will survive forever and continuously with nonzero probability. When the reward \ndistributions of an arm satisfy the monotone likelihood ratio property (MLRP), the \nsurvival prospects of an arm improve when conditioned on types generating higher \nexpected rewards; however, we show how this need not be the case in the absence of \nMLRP. Implications of these results are derived for the theories of job search and \nmatching, as well as other applications of the bandit paradigm.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 101 citations exist upstream.