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.

• Publication year

  2007

• Venue

  TOP

• Publication date

  2007-09-27

• Fields of study

  Mathematics, Computer Science, Economics

• Identifiers
  DOI 10.1007/s11750-007-0025-0arXiv 2304.06115
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Dynamic Scheduling of a Multiclass Make-to-Stock Queue

  2015cited by this paper
• Conservation laws, extended polymatroids and multi-armed bandit problems: a unified approach to ind exable systems

  2011influential reference
• A Faster Index Algorithm and a Computational Study for Bandits with Switching Costs

  2008influential reference
• Computing an index policy for bandits with switching penalties

  2007influential reference
• Marginal Productivity Index Policies for Admission Control and Routing to Parallel Multi-server Loss Queues with Reneging

  2007influential reference
• A (2/3)n3 Fast-Pivoting Algorithm for the Gittins Index and Optimal Stopping of a Markov Chain

  2007influential reference
• Characterization and computation of restless bandit marginal productivity indices

  2007influential reference
• Marginal Productivity Index Policies for Scheduling Multiclass Delay-/Loss-Sensitive Traffic with Delayed State Observation

  2007influential reference
• Marginal productivity index policies for scheduling multiclass wireless transmissions

  2006influential reference
• Restless Bandit Marginal Productivity Indices, Diminishing Returns, and Optimal Control of Make-to-Order/Make-to-Stock M/G/1 Queues

  2006cited by this paper
• Open Rectangle-of-Influence Drawings of Inner Triangulated Plane Graphs

  2006cited by this paper
• Restless Bandit Marginal Productivity Indices, Diminishing Returns, and Optimal Control of Make-to-Order/Make-to-Stock M/G/1 Queues

  2006influential reference
• Marginal productivity index policies for scheduling a multiclass delay-/loss-sensitive queue

  2006influential reference
• Optimal bandwidth allocation in a delay channel

  2006cited by this paper
• A Marginal Productivity Index Policy for the Finite-Horizon Multiarmed Bandit Problem

  2005cited by this paper
• A SURVEY ON THE BANDIT PROBLEM WITH SWITCHING COSTS

  2004cited by this paper
• Combined make-to-order and make-to-stock in a food production system

  2004influential reference
• Optimal hysteresis for a class of deterministic deteriorating two-armed Bandit problem with switching costs

  2003cited by this paper
• Continuous-time restless bandit and dynamic scheduling for make-to-stock production

  2003cited by this paper
• Handbook of Markov decision processes : methods and applications

  2002cited by this paper
• Handbook of Markov Decision Processes

  2002cited by this paper
• Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach

  2002influential reference
• ON PARALLEL QUEUING WITH RANDOM SERVER CONNECTIVITY AND ROUTING CONSTRAINTS

  2002influential reference
• A multiobjective control approach to priority queues

  2001cited by this paper
• Restless bandits, partial conservation laws and indexability

  2000influential reference
• Dynamic Scheduling in a Make-to-Stock System: A Partial Characterization of Optimal Policies

  2000cited by this paper
• ON THE OPTIMALITY OF AN INDEX RULE IN MULTICHANNEL ALLOCATION FOR SINGLE-HOP MOBILE NETWORKS WITH MULTIPLE SERVICE CLASSES

  2000influential reference
• Mixed Criteria

  2000cited by this paper
• Numerical linear algebra algorithms and software

  2000influential reference
• The Complexity of Optimal Queuing Network Control

  1999cited by this paper
• Combining make to order and make to stock

  1998cited by this paper
• Dynamic Scheduling in a Make-to-stock System: a Partial Characterisation of Optimal Policies Dynamic Scheduling in a Make-to-stock System: a Partial Characterisation of Optimal Policies

  1998influential reference
• Beyond the cμ rule: Dynamic scheduling of a two-class loss queue

  1998influential reference
• ERROR BOUNDS FOR CALCULATION OF THE GITTINS INDICES

  1997cited by this paper
• Dynamic Scheduling Rules for a Multiproduct Make-to-Stock Queue

  1997cited by this paper
• Scheduling a Make-To-Stock Queue: Index Policies and Hedging Points

  1996influential reference
• Optimal Server Allocation to Parallel Queues with Finite-Capacity Buffers

  1996cited by this paper
• Conservation Laws, Extended Polymatroids and Multiarmed Bandit Problems; A Polyhedral Approach to Indexable Systems

  1996cited by this paper
• Optimal Control: Basics and Beyond

  1996cited by this paper
• Multi-armed bandits with switching penalties

  1996influential reference
• Optimality of monotonic policies for two-action Markovian decision processes, with applications to control of queues with delayed information

  1995cited by this paper
• Recent trends in optimization theory and applications

  1995cited by this paper
• Two approaches to optimal routing and admission control in systems with real-time traffic

  1995cited by this paper
• Static optimization of queueing systems

  1995cited by this paper
• Markov Decision Processes: Discrete Stochastic Dynamic Programming

  1994cited by this paper
• Optimization of Static Traffic Allocation Policies

  1994influential reference
• Switching Costs and the Gittins Index

  1994influential reference
• Markov Decision Processes: Discrete Stochastic Dynamic Programming

  1994cited by this paper
• Dynamic server allocation to parallel queues with randomly varying connectivity

  1993cited by this paper
• On the Gittins Index for Multiarmed Bandits

  1992cited by this paper
• On the duality between routing and scheduling systems with finite buffer space

  1992cited by this paper
• Multiclass Queueing Systems: Polymatroidal Structure and Optimal Scheduling Control

  1992cited by this paper
• Addendum to ‘On an index policy for restless bandits'

  1991cited by this paper
• On an index policy for restless bandits

  1990influential reference
• A celebration of applied probability

  1990cited by this paper
• Multi‐Armed Bandit Allocation Indices

  1990cited by this paper
• On the Optimality of the Generalized Shortest Queue Policy

  1990influential reference
• Optimal intensity control of a queueing system with state-dependent capacity limit

  1990influential reference
• Joining the right queue: a state-dependent decision rule

  1990influential reference
• Multi-armed Bandit Allocation Indices

  1989cited by this paper
• Optimal priority assignment: a time sharing approach

  1989cited by this paper
• Optimality of the shortest line discipline with state-dependent service rates

  1989cited by this paper
• Restless bandits: activity allocation in a changing world

  1988influential reference
• State-dependent allocation of job stream to parallel workstations

  1988cited by this paper
• Characterization and Optimization of Achievable Performance in General Queueing Systems

  1988cited by this paper
• Optimal control of admission to a queueing system

  1985cited by this paper
• Extensions of the multiarmed bandit problem: The discounted case

  1985cited by this paper
• Multi-Armed Bandits with Discount Factor Near One: The Bernoulli Case

  1981cited by this paper
• A Characterization of Waiting Time Performance Realizable by Single-Server Queues

  1980cited by this paper
• Multi‐Armed Bandits and the Gittins Index

  1980cited by this paper
• On the optimal assignment of servers and a repairman

  1980cited by this paper
• Bandit processes and dynamic allocation indices

  1979influential reference
• Queueing systems, Vol. I: Theory

  1977cited by this paper
• Optimality of the shortest line discipline

  1977cited by this paper
• Time-Sharing Service Systems. I

  1975cited by this paper
• Queueing Systems - Vol. 1: Theory

  1975cited by this paper
• Progress in statistics

  1975cited by this paper
• Scheduling for Minimum Total Loss Using Service Time Distributions

  1974cited by this paper
• A relation between stationary queue and waiting time distributions

  1971cited by this paper
• Scheduling with Random Service Times

  1966cited by this paper
• Discrete Dynamic Programming

  1965cited by this paper
• A conservation law for a wide class of queueing disciplines

  1965influential reference
• Discrete Dynamic Programming

  1962cited by this paper
• Three Essays on the State of Economic Science

  1958cited by this paper
• On Sequential Designs for Maximizing the Sum of $n$ Observations

  1956influential reference
• Various optimizers for single‐stage production

  1956cited by this paper
• The computational algorithm for the parametric objective function

  1955cited by this paper
• A PROBLEM IN THE SEQUENTIAL DESIGN OF EXPERIMENTS

  1954cited by this paper
• Contribution à l’étude de la tuberculose trachéo·bronchique

  1945cited by this paper
• The Distribution Of Wealth A Theory Of Wages Interest And Profits

  year unknowncited by this paper

• Improving Upon the generalized c-mu rule: a Whittle approach

  2025cites this paper
• Index policies for campaign promotion strategies in reward-based crowdfunding

  2025cites this paper
• On the sensitivity of restless bandits solutions to uncertainty in the models of the arms

  2025cites this paper
• A Novel Switch-Type Policy Network for Resource Allocation Problems

  2025cites this paper
• A Multiindex Policy for Joint Selection of Subarrays and Operational Mode of Distributed Coherent Aperture Radars

  2025cites this paper
• An Enhanced Lagrangian Index Policy for Beam Scheduling of Colocated MIMO Radars

  2025cites this paper
• Structured Reinforcement Learning for Delay-Optimal Data Transmission in Dense mmWave Networks

  2024cites this paper
• GINO-Q: Learning an Asymptotically Optimal Index Policy for Restless Multi-armed Bandits

  2024cites this paper
• Risk-Aware Decision Making in Restless Bandits: Theory and Algorithms for Planning and Learning

  2024influential citation
• General Formulation and PCL-Analysis for Restless Bandits with Limited Observability

  2023cites this paper
• Coordinated Multiagent Patrolling With State-Dependent Cost Rates: Asymptotically Optimal Policies for Large-Scale Systems

  2023cites this paper
• Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints

  2023cites this paper
• Age of Information Cost Minimization with No Buffers, Random Arrivals and Unreliable Channels: A PCL-Indexability Analysis

  2023cites this paper
• Reinforcement Learning for Dynamic Dimensioning of Cloud Caches: A Restless Bandit Approach

  2023cites this paper
• Coordinated Multi-Agent Patrolling with History-Dependent Cost Rates - Asymptotically Optimal Policies for Large-Scale Systems

  2023cites this paper
• Minimizing the mean slowdown in the M/G/1 queue

  2023cites this paper
• Indexability of Finite State Restless Multi-Armed Bandit and Rollout Policy

  2023influential citation
• Markovian Restless Bandits and Index Policies: A Review

  2023cites this paper
• Partially observable restless bandits with restarts: indexability and computation of Whittle index

  2022cites this paper
• Whittle Index-Based Q-Learning for Wireless Edge Caching With Linear Function Approximation

  2022cites this paper
• Testing indexability and computing Whittle and Gittins index in subcubic time

  2022influential citation
• Model-free Reinforcement Learning for Content Caching at the Wireless Edge via Restless Bandits

  2022cites this paper
• Near-optimality for infinite-horizon restless bandits with many arms

  2022cites this paper
• On Learning Whittle Index Policy for Restless Bandits With Scalable Regret

  2022cites this paper
• Multi-Gear Bandits, Partial Conservation Laws, and Indexability

  2022cites this paper
• On the Whittle index of Markov modulated restless bandits

  2022influential citation
• Index-aware reinforcement learning for adaptive video streaming at the wireless edge

  2022cites this paper
• Empirical Gittins index strategies with ε-explorations for multi-armed bandit problems

  2022cites this paper
• Some performance considerations when using multi-armed bandit algorithms in the presence of missing data

  2022cites this paper
• Reinforcement Learning Augmented Asymptotically Optimal Index Policy for Finite-Horizon Restless Bandits

  2022cites this paper
• An Index Policy for Minimizing the Uncertainty-of-Information of Markov Sources

  2022cites this paper
• Reinforcement Learning for Dynamic Dimensioning of Cloud Caches: A Restless Bandit Approach

  2022cites this paper
• Learning Infinite-Horizon Average-Reward Restless Multi-Action Bandits via Index Awareness

  2022cites this paper
• NeurWIN: Neural Whittle Index Network For Restless Bandits Via Deep RL

  2021cites this paper
• Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Bandits

  2021cites this paper
• Maintenance of a collection of machines under partial observability: Indexability and computation of Whittle index

  2021cites this paper
• Linear Program-Based Policies for Restless Bandits: Necessary and Sufficient Conditions for (Exponentially Fast) Asymptotic Optimality

  2021cites this paper
• Relaxed Indexability and Index Policy for Partially Observable Restless Bandits

  2021cites this paper
• Two families of indexable partially observable restless bandits and Whittle index computation

  2021cites this paper
• A restless bandit model for dynamic ride matching with reneging travelers

  2021cites this paper
• Uncertainty-of-Information Scheduling: A Restless Multiarmed Bandit Framework

  2021cites this paper
• A Restless Bandit Model for Energy-Efficient Job Assignments in Server Farms

  2021cites this paper
• A Novel Implementation of Q-Learning for the Whittle Index

  2021cites this paper
• Scalable Operator Allocation for Multirobot Assistance: A Restless Bandit Approach

  2021cites this paper
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits

  2020cites this paper
• Age-of-Information Bandits

  2020cites this paper
• Resource competition in virtual network embedding

  2020cites this paper
• Restless bandits: indexability and computation of Whittle index

  2020cites this paper
• Fast Two-Stage Computation of an Index Policy for Multi-Armed Bandits with Setup Delays

  2020cites this paper
• Regret of Age-of-Information Bandits

  2020cites this paper
• Exponential Convergence Rate for the Asymptotic Optimality of Whittle Index Policy

  2020influential citation
• Simulation Based Algorithms for Markov Decision Processes and Multi-Action Restless Bandits

  2020cites this paper
• Conditions for indexability of restless bandits and an $\mathcal{O}\!\left(K^3\right)$ algorithm to compute Whittle index

  2020cites this paper
• On the computation of Whittle’s index for Markovian restless bandits

  2020cites this paper
• A Fast-Pivoting Algorithm for Whittle’s Restless Bandit Index

  2020cites this paper
• Resource allocation with observable and unobservable environments

  2020cites this paper
• A Restless MAB-Based Index Policy for UL Pilot Allocation in Massive MIMO Over Gauss–Markov Fading Channels

  2020cites this paper
• Towards Q-learning the Whittle Index for Restless Bandits

  2019cites this paper
• Energy-Efficient Job-Assignment Policy With Asymptotically Guaranteed Performance Deviation

  2019cites this paper
• Constrained Restless Bandits for Dynamic Scheduling in Cyber-Physical Systems

  2019cites this paper
• Handover Optimality in Heterogeneous Networks

  2019cites this paper
• Uplink Pilot Allocation in Massive MIMO over Gauss-Markov Fading Channels

  2019influential citation
• Sequential Decision Making under Uncertainty with Dynamic Resource Constraints

  2019cites this paper
• Multi-Armed Bandits: Theory and Applications to Online Learning in Networks

  2019cites this paper
• Scheduling users in drive-thru Internet: a multi-armed bandit approach

  2019cites this paper
• A unifying computations of Whittle's Index for Markovian bandits

  2019cites this paper
• A User Comfort Model and Index Policy for Personalizing Discrete Controller Decisions

  2018cites this paper
• A Restless Bandit Model for Resource Allocation, Competition, and Reservation

  2018cites this paper
• Load balancing with heterogeneous schedulers

  2018cites this paper
• Asymptotic Optimal Control of Markov-Modulated Restless Bandits

  2018cites this paper
• OPTIMAL TASK OFFLOADING IN FOG-ENABLED NETWORKS VIA INDEX POLICIES

  2018cites this paper
• Restless Bandits in Action: Resource Allocation, Competition and Reservation

  2018cites this paper
• Asymptotically optimal priority policies for indexable and nonindexable restless bandits

  2017influential citation
• Monitoring and control of stochastic systems

  2017cites this paper
• Online Matching with Queueing Dynamics Research

  2017cites this paper
• Scheduling of multi-class multi-server queueing systems with abandonments

  2017influential citation
• Contract Manufacturing Relationships Can Urgun

  2017cites this paper
• Dynamic control in multi-item production/inventory systems

  2017cites this paper
• Contract Manufacturing Relationships

  2017influential citation
• An index rule proposal for scheduling in mobile broadband networks with limited channel feedback

  2017cites this paper
• Wireless Channel Selection with Restless Bandits

  2017cites this paper
• Learning Unknown Service Rates in Queues: A Multiarmed Bandit Approach

  2016cites this paper
• Dynamic Control of Birth-and-Death Restless Bandits: Application to Resource-Allocation Problems

  2016cites this paper
• Approximation algorithms for wireless opportunistic spectrum scheduling in cognitive radio networks

  2016cites this paper
• Optimal dynamic resource allocation to prevent defaults

  2016influential citation
• Regret of Queueing Bandits

  2016cites this paper
• Asymptotically optimal priority policies for indexable and nonindexable restless bandits

  2016cites this paper
• Whittle's Index Policy for Multi-Target Tracking with Jamming and Nondetections

  2016cites this paper
• On the Interaction of Information and Decisions in Dynamic Networked Systems.

  2016cites this paper
• Scheduling of multi-class multi-server queueing systems with abandonments

  2015influential citation
• A Verification Theorem for Threshold-Indexability of Real-State Discounted Restless Bandits

  2015cites this paper
• Asymptotically optimal index policies for an abandonment queue with convex holding cost

  2015cites this paper
• On the asymptotic optimality of greedy index heuristics for multi-action restless bandits

  2015cites this paper
• INDEXABILITY AND OPTIMAL INDEX POLICIES FOR A CLASS OF REINITIALISING RESTLESS BANDITS

  2015cites this paper
• Radio-Aware Service-Level Scheduling to Minimize Downlink Traffic Delay Through Mobile Edge Computing

  2015influential citation
• Weighted Restless Bandit and Its Applications

  2015cites this paper
• A Verification Theorem for Indexability of Discrete Time Real State Discounted Restless Bandits

  2015influential citation
• Stochastic and fluid index policies for resource allocation problems

  2015cites this paper
• Asymptotically optimal index policies for an abandonment queue with convex holding cost

  2015cites this paper
• Index policies for a multi-class queue with convex holding cost and abandonments

  2014cites this paper