Dynamic priority allocation via restless bandit marginal productivity indices

Abstract

This paper surveys recent work by the author on the theoretical and algorithmic aspects of restless bandit indexation as well as on its application to a variety of problems involving the dynamic allocation of priority to multiple stochastic projects. The main aim is to present ideas and methods in an accessible form that can be of use to researchers addressing problems of such a kind. Besides building on the rich literature on bandit problems, our approach draws on ideas from linear programming, economics, and multi-objective optimization. In particular, it was motivated to address issues raised in the seminal work of Whittle (Restless bandits: activity allocation in a changing world. In: Gani J. (ed.) A Celebration of Applied Probability, J. Appl. Probab., vol. 25A, Applied Probability Trust, Sheffield, pp. 287-298, 1988) where he introduced the index for restless bandits that is the starting point of this work. Such an index, along with previously proposed indices and more recent extensions, is shown to be unified through the intuitive concept of ``marginal productivity index'' (MPI), which measures the marginal productivity of work on a project at each of its states. In a multi-project setting, MPI policies are economically sound, as they dynamically allocate higher priority to those projects where work appears to be currently more productive. Besides being tractable and widely applicable, a growing body of computational evidence indicates that such index policies typically achieve a near-optimal performance and substantially outperform benchmark policies derived from conventional approaches.

arXiv comment7 figures

References in corpus (3)

• Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach
• A $(2/3)n^3$ fast-pivoting algorithm for the Gittins index and optimal stopping of a Markov chain
• A faster index algorithm and a computational study for bandits with switching costs

Cited by in corpus (20)

• Asymptotically optimal priority policies for indexable and nonindexable restless bandits
• Uncertainty-of-Information Scheduling: A Restless Multi-armed Bandit Framework
• Congestion Control of TCP Flows in Internet Routers by Means of Index Policy
• A faster index algorithm and a computational study for bandits with switching costs
• Markovian restless bandits and index policies: A review
• LP-based policies for restless bandits: necessary and sufficient conditions for (exponentially fast) asymptotic optimality
• A Verification Theorem for Threshold-Indexability of Real-State Discounted Restless Bandits
• Testing Indexability and Computing Whittle and Gittins Index in Subcubic Time
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits
• A fast-pivoting algorithm for Whittle's restless bandit index
• Multi-gear bandits, partial conservation laws, and indexability
• The Non-Bayesian Restless Multi-Armed Bandit: a Case of Near-Logarithmic Regret
• Simulation Based Algorithms for Markov Decision Processes and Multi-Action Restless Bandits
• Some performance considerations when using multi-armed bandit algorithms in the presence of missing data
• Relaxed Indexability and Index Policy for Partially Observable Restless Bandits
• Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Bandits
• Age of information cost minimization with no buffers, random arrivals and unreliable channels: A PCL-indexability analysis
• Network Utility Maximization over Partially Observable Markovian Channels
• A unifying computations of Whittle's Index for Markovian bandits
• Energy-Efficient Job-Assignment Policy with Asymptotically Guaranteed Performance Deviation