On Gittins' index theorem in continuous time
We give a new and comparably short proof of Gittins' index theorem for dynamic allocation problems of the multi-armed bandit type in continuous time under minimal assumptions. This proof gives a complete characterization of optimal allocation strategies as those policies which follow the current leader among the Gittins indices while ensuring that a Gittins index is at an all-time low whenever the associated project is not worked on exclusively. The main tool is a representation property of Gittins index processes which allows us to show that these processes can be chosen to be pathwise lower semi-continuous from the right and quasi-lower semi-continuous from the left. Both regularity properties turn out to be crucial for our characterization and the construction of optimal allocation policies.
Year of publication: |
2007
|
---|---|
Authors: | Bank, Peter ; Küchler, Christian |
Published in: |
Stochastic Processes and their Applications. - Elsevier, ISSN 0304-4149. - Vol. 117.2007, 9, p. 1357-1371
|
Publisher: |
Elsevier |
Keywords: | Gittins index Multi-armed bandits Representation theorem |
Saved in:
Saved in favorites
Similar items by person
-
Scenario reduction in stochastic programming with respect to discrepancy distances
Henrion, René, (2009)
-
Optimization of dispersed energy supply : stochastic programming with recombining scenario trees
Epe, Alexa, (2009)
-
Scenario reduction in stochastic programming with respect to discrepancy distances
Henrion, René, (2009)
- More ...