Keynotes

Index Policies for Near-Optimal Dynamic Resource Allocation: The Partial Conservation Laws Approach

José Niño-Mora is Professor of Operations Research and Statistics at Universidad Carlos III de Madrid, where he headed the Department of Statistics from 2018 to 2022. He earned his PhD in Operations Research from MIT in 1995 on a Fulbright fellowship and then held a Marie Curie postdoctoral fellowship at the Université catholique de Louvain. In 2001, he introduced partial conservation laws for stochastic scheduling and restless bandits. He has developed theory and algorithms for marginal productivity index policies in both discrete- and real-state models and demonstrated their effectiveness across a range of models for queueing control, communications scheduling, and treatment adherence. His recent work extends this approach to multi-gear bandits, in which each activity can operate at several resource levels. His verification theorem for threshold-indexability of discounted restless bandits with interval state spaces earned him the 2020 award for the best methodological contribution in operations research, presented jointly by the Spanish Society of Statistics and Operations Research (SEIO) and the BBVA Foundation.

A remote monitor tracks several changing information sources under a shared transmission budget. At each decision epoch, which sources should transmit, and at what level of effort? The answer depends on the current state of each source and on how an update now affects the need for later updates. I will use this scheduling problem as a running example, with performance measured by the age of incorrect information, the time for which the monitor’s estimate of a source has remained incorrect. This is an example of a weakly coupled Markov decision process. Each project—an information source, a queue, or a machine, for example—evolves according to its own state and action, while a shared resource constraint couples the decisions. Index policies assign priorities from individual project states. They often achieve near-optimal performance, and under suitable conditions their optimality gap per project vanishes as the number of projects and the resource budget scale proportionally. Drawing on 25 years of work on partial conservation laws, I will show how they can establish indexability for restless bandits and characterize the Whittle index and extensions thereof as a marginal productivity index. I will then present recent work on multi-gear bandits, where fast-pivoting algorithms compute indices for choosing among successive resource levels. In simulations of the monitoring problem, the relative gap between the index policy’s estimated mean cost and a Lagrangian lower bound decreases as the system grows, falling below 0.5% at 1,600 sources. This provides empirical evidence consistent with asymptotic optimality.

José Niño-Mora

Carlos III University of Madrid, Spain

Scroll to Top