Two-Phase Policy Classes for Multi-Context Restless Bandits

Restless multi-armed bandits are widely used for sequential resource allocation, yet all existing theory assumes a fixed activation budget. In practice, many applications involve multiple operating contexts with distinct dynamics, and the decision of how to distribute budget across these contexts is as important as which arms to activate within each. We formalize this as the contextual budget bandit (CBB), a two-phase optimization where the upper level allocates per-context budgets under a global capacity constraint and the lower level selects arms under hard per-period limits. We introduce a hierarchy of two-phase policy classes capturing this structure. Our main result shows that, for exchangeable arm types, the optimal policy belongs to a tractable class we call aggregate-state-dependent priority: the type-priority may depend on how many arms of each type are engaged, but not on which specific arms. We prove this via permutation invariance of the value function. Surprisingly, fixed-priority index policies are not always optimal: a portfolio effect causes the priority between types to reverse depending on same-type depth, starting at three arms. A gap bound shows that Lagrangian index policies lose at most a vanishing fraction of the optimum as the number of arms grows. Computational validation across 112,000 randomly generated instances confirms the aggregate-class optimality at 100% and quantifies the portfolio effect at 2–17% of instances. On a food rescue volunteer engagement application, the Mirror Descent Value Iteration (MDVI) algorithm achieves 0.0–3.2% gap from the LP bound, scaling to $N=2,000$ arms in 10 minutes.