American Options, Finite-Fuel Problems, and the Multi-Armed Bandit

Abstract : We show how the optimal stopping, certain singular control problems, and dynamic allocation problems all can be reduced to the same kind of stochastic representation problem. This unifying approach allows for some new (and comparably easy) proofs for classical results such as Gittins' index theorem, and also offers some new insights into the common structure of these optimization problems.