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

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).