Continuation-Aware Decisions for Matroid-Constrained Restless Bandits

Restless multi-armed bandit (RMAB) methods often reduce joint decisions to local scalar priorities. We ask whether this representation remains sufficient when feasible active sets form a matroid. An exact three-arm construction shows that state-local scalar scores can fail to represent the optimal policy under a fixed greedy selector, despite independent transitions and additive rewards. We therefore compare feasible sets using the Whittle continuation value. For binary-state RMABs, a low-order continuation approximation can be learned from known dynamics without joint-state value labels. Under explicit regularity, gap, and transition-row coverage assumptions, we prove a conditional expected finite-horizon regret bound of $T{ϵ}_{\mathrm{struct}}+O(\log T)$, where ${ϵ}_{\mathrm{struct}}$ measures the structural error of the true-model frozen policy. Experiments show high decision fidelity under known dynamics and lower frozen-policy Q-loss than plugin and arm-wise optimistic baselines under unknown dynamics. The improvement over the plugin policy is not robust to several distribution shifts, and sparse online fitting can distort early decisions.