# Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach

arXiv: https://arxiv.org/abs/2304.01946 · HTML: https://mlsanity.com/paper/2304.01946/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Apr 2023.

## Built on by (most cited first, 5 of 5)

- [General Formulation and PCL-Analysis for Restless Bandits with Limited Observability](https://mlsanity.com/paper/2307.03034/) (2023)
- [Model Predictive Control is Almost Optimal for Restless Bandit](https://mlsanity.com/paper/2410.06307/) (2024)
- [Model Predictive Control is almost Optimal for Heterogeneous Restless Multi-armed Bandits](https://mlsanity.com/paper/2511.08097/) (2025)
- [Non-Stationary Restless Multi-Armed Bandits with Provable Guarantee](https://mlsanity.com/paper/2508.10804/) (2025)
- [From Relaxed Indexability to Exact Indexability: A t-Step Approach for Partially Observable Restless Bandits](https://mlsanity.com/paper/2608.24167/) (2026)

## Abstract (arXiv)

This paper develops a polyhedral approach to the design, analysis, and computation of dynamic allocation indices for scheduling binary-action (engage/rest) Markovian stochastic projects which can change state when rested (restless bandits (RBs)), based on partial conservation laws (PCLs). This extends previous work by the author [J. Ni~no-Mora. Restless bandits, partial conservation laws and indexability. Adv. Appl. Probab., vol. 33, 76-98, 2001], where PCLs were shown to imply optimality of index policies with a postulated structure under admissible linear objectives, and they were deployed to obtain sufficient conditions for the existence of Whittle's index and an adaptive-greedy index algorithm. The contributions include: (i) we develop the polyhedral foundation of the PCL framework, based on structural and algorithmic properties of a polytope associated with an accessible set system (F-extended polymatroid); (ii) we present new indices for RBs, motivated by an admission control model, which extend Whittle's and have a significantly increased scope; (iii) we deploy PCLs to obtain both sufficient conditions for the existence of the new indices (PCL-indexability) and a reformulated adaptive-greedy index algorithm; (iv) we interpret PCL-indexability in terms of the economic law of diminishing marginal returns and characterize the index as an optimal marginal cost rate; (v) we carry out a PCL-indexability analysis of the motivating admission control model, which gives, under mild conditions, a new index characterization of optimal threshold policies; and (vi) we apply the latter to present new heuristic index policies for two hard queueing control problems: admission control and routing to parallel queues; and scheduling a multiclass make-to-stock queue with lost sales, both under state-dependent holding cost rates and birth-death dynamics.