Multi-Armed Bandits and the Gittins Index

Abstract

Summary A plausible conjecture (C) has the implication that a relationship (12) holds between the maximal expected rewards for a multi-project process and for a one-project process (F and φi respectively), if the option of retirement with reward M is available. The validity of this relation and optimality of Gittins' index rule are verified simultaneously by dynamic programming methods. These results are partially extended to the case of so-called “bandit superprocesses”.