CAM colloquium - March 5

Peter Bank
Columbia University

"Optimal Stopping and the Multi-armed Bandit"

We present an approach to optimal stopping problems which builds on a new type of stochastic representation theorem for the considered payoff process. For American put options, this approach provides a signal process for deriving optimal exercise rules which is universal in the sense that the same signal can be used for any strike. This universal signal process turns out to be closely related to the concept of Gittins Indices used in Operations Research for dealing with multi-armed bandit problems. We give a new proof of optimality for Gittins' index policy which easily applies also to a robustified version of the bandit problem. Closed-form solutions are obtained for homogeneous settings specified in terms of Levy processes or general diffusions. We also discuss some computational aspects and present an algorithm which efficiently constructs the universal signal process.