Multiarmed Bandit Allocation Indices

Part 1 Main ideas: decision processes; bandit processes and simple families of alternative bandit processes; a first index theorem; jobs; the index theorem for jobs with no pre-emption; knapsacks; different discount functions; stochastic discounting; ongoing bandit processes; multiple processes. Part 2 Central theory: a necessary condition for an index; splicing bandit process portions; equivalent constant reward rates and forwards induction for arbitrary decision processes; more splicing and proof of the index theorem for a SFABP; near optimality of nearly index policies, and the gamma - O limit; bandit superprocesses and simple families of alternative superprocesses; the index theorem for superprocesses; stoppable bandit processes; the index theorem for a FABP with precedence constraints; precedence constraints forming an out-tree; FABPs with arrivals; minimum EWFT for the M/G/1 queue. Part 3 General properties of the indices: dependence on discount parameter; monotone indices; monotone jobs. Part 4 Jobs with continuously-varying effort allocations: competing research projects; continuous-time jobs; optimal policies for queues of jobs. Part 5 Multi-population random sampling (theory): jobs and targets; use of monotonicity properties; general methods of calculation - use of invariance properties; random sampling times; Brownian reward process; asymptotically normal reward processes. Part 6 Multi-population random sampling (calculations): normal reward process (known variance); normal reward process (mean and variance both unknown); Bernoulli reward process; exponential reward process; exponential target process; Bernoulli/exponential target process. Part 7 Search theory: a discrete search problem; two-person zero-sum games; a game of hide and seek; hide and seek in continuous time. Part 8 In conclusion: the Whittle index theorem; permutation schedules and sub-optimality; more about the Brownian reward process; more proofs, generalizations and extensions.