Multi-armed Bandit Allocation Indices (PDF)

Foreword. Foreword to the first edition. Preface. Preface to the first edition. 1 Introduction or Exploration. Exercises. 2 Main Ideas: Gittins Index. 2.1 Introduction. 2.2 Decision processes. 2.3 Simple families of alternative bandit processes. 2.4 Dynamic programming. 2.5 Gittins index theorem. 2.6 Gittins index. 2.7 Proof of the index theorem by interchanging bandit portions. 2.8 Continuous-time bandit processes. 2.9 Proof of the index theorem by induction and interchange argument. 2.10 Calculation of Gittins indices. 2.11 Monotonicity conditions. 2.12 History of the index theorem. 2.13 Some decision process theory. Exercises. 3 Necessary Assumptions for Indices. 3.1 Introduction. 3.2 Jobs. 3.3 Continuous-time jobs. 3.4 Necessary assumptions. 3.5 Beyond the necessary assumptions. Exercises. 4 Superprocesses, Precedence Constraints and Arrivals. 4.1 Introduction. 4.2 Bandit superprocesses. 4.3 The index theorem for superprocesses. 4.4 Stoppable bandit processes. 4.5 Proof of the index theorem by freezing and promotion rules. 4.6 The index theorem for jobs with precedence constraints. 4.7 Precedence constraints forming an out-forest. 4.8 Bandit processes with arrivals. 4.9 Tax problems. 4.10 Near optimality of nearly index policies. Exercises. 5 The Achievable Region Methodology. 5.1 Introduction. 5.2 A simple example. 5.3 Proof of the index theorem by greedy algorithm. 5.4 Generalized conservation laws and indexable systems. 5.5 Performance bounds for policies for branching bandits. 5.6 Job selection and scheduling problems. 5.7 Multi-armed bandits on parallel machines. Exercises. 6 Restless Bandits and Lagrangian Relaxation. 6.1 Introduction. 6.2 Restless bandits. 6.3 Whittle indices for restless bandits. 6.4 Asymptotic optimality. 6.5 Monotone policies and simple proofs of indexability. 6.6 Applications to multi-class queuing systems. 6.7 Performance bounds for the Whittle index policy. 6.8 Indices for more general resource configurations. Exercises. 7

John Gittins, Statistics Department, University of Oxford, UK

Kevin Glazebrook, Department of Management Science, Lancaster University, UK

Richard Weber, Statistical Laboratory, University of Cambridge, UK

Dieses eBook können Sie uneingeschränkt auf allen Geräten der tolino Familie lesen. Zum Lesen auf sonstigen eReadern und am PC benötigen Sie eine Adobe ID.