Soft-Interleaved Thompson Sampling for Computationally Efficient Combinatorial Bandits

Combinatorial Thompson Sampling (CTS) is a highly effective policy for sequential decision-making in structurally constrained environments. However, standard CTS relies on "black-box" optimization oracles, which is problematic from two aspects. First, computationally, it repeatedly executes exact offline oracles from scratch, which often incurs polynomial or exponential costs. Second, in problems with local optima, the oracle tends to prematurely commit too early to such optimum, and this highly confines the exploration in next rounds, blinding the policy from reaching the global optimum. To address these limitations, we propose Soft-Interleaved Thompson Sampling (SITS), a novel framework that abandons the black-box exact-oracle approach, and is based on extracting information from non-convergent, iterative "soft" solvers. By interleaving targeted queries directly within the intermediate steps of an iterative solver, our framework identifies and samples ambiguous topological boundaries before a final action is chosen. We demonstrate this approach with two canonical classes of problems, the Maximum Weight Matching problem with a message passing solver, and the Shortest Path problem with a Bellman-Ford solver. Empirical evaluations, including real-world biological sequence alignments, establish that SITS successfully solves problem instances in which CTS fails, while reducing the per-round computational overhead by an order of magnitude, empirically matching the computational scaling of a single offline exact solver.