Fast-pivoting parametric solution and index policies for structured Markov decision processes: Multi-gear bandits

José Niño Mora

DES - Working Papers. Statistics and Econometrics. WS from Universidad Carlos III de Madrid. Departamento de Estadística

Abstract: We study finite-state multi-gear bandits, Markov decision processes modeling projects with ordered resource levels. Under indexability, a dynamic allocation index (DAI) encodes optimal single-project policies for every resource price. These solutions support Lagrangian bounds and feasible heuristic policies for weakly coupled resource-constrained multi-project problems. We strengthen prior verification results based on partial conservation laws and establish analytical criteria for indexability relative to a posited policy family whose choice is guided by insight into model structure. We also extend fast-pivoting Gittins and Whittle index methods to compute the DAI for multi-gear bandits. When marginal work positivity is known, the linear algebra cost is at most cubic in the state count and linear in the gear count; checking positivity makes the gear-count dependence quadratic. A theoretical variant using fast matrix multiplication reduces this cost to subcubic order in the state count for fixed gear count. The results extend to average costs. Benchmarks show substantial runtime gains of blocked fast-pivoting over alternative index implementations. An age-only model of capped age of incorrect information (AoII) over Rayleigh-fading links illustrates the methods. In heterogeneous AoII simulations, a knapsack-and-index policy reduces estimated mean cost by up to 56 percent relative to myopic allocation. Simulations show the policy's relative mean-cost gap to the average-cost Lagrangian bound decreasing with project count, providing numerical evidence consistent with asymptotic optimality. The gap falls below 0.5 percent in the largest systems tested (1,600 projects).

Keywords: Markov; Processes; Multi-Gear; Bandits; Indexability; Fast; Pivoting; Resource; Allocation. (search for similar items in EconPapers)
Date: 2026-10-27
New Economics Papers: this item is included in nep-ppm
References: Add references at CitEc
Citations:

Downloads: (external link)
https://e-archivo.uc3m.es/rest/api/core/bitstreams ... fbf45f1eb930/content (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cte:wsrepe:51080

Access Statistics for this paper

More papers in DES - Working Papers. Statistics and Econometrics. WS from Universidad Carlos III de Madrid. Departamento de Estadística
Bibliographic data for series maintained by Ana Poveda ().