acceptodds
Withdrawn from ICLR 2027

Soft-Interleaved Thompson Sampling for Computationally Efficient Combinatorial Bandits

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Combinatorial Bandits, Thompson Sampling, Active Learning, Information-Directed Sampling, Combinatorial Optimization, Sequential Decision Making

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_aRndOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper introduces SITS, a method that combines posterior sampling with a persistent combinatorial solver and targeted base-arm queries. At each step, the method runs a few solver iterations before selecting which arms to query. For maximum-weight matching, it uses message-passing margins, posterior variance, and belief magnitude to guide query selection. For shortest paths, it focuses on uncertain edges in the symmetric difference between two candidate paths obtained from posterior samples.

Critical strengths
  1. Using intermediate solver ambiguity to guide queries, while preserving the solver state across iterations, is a promising approach when optimization is computationally expensive.

  2. The ablation studies for maximum-weight matching help assess whether the proposed acquisition strategy offers benefits beyond simpler alternatives. Appendix D compares the combined strategy against variance-only and margin-only policies, as well as truncated CTS under different iteration budgets.

Critical weaknesses
  1. The persistent shortest-path solver does not appear to handle changing edge weights correctly. In Algorithm 3, distance labels are initialized only once and are subsequently updated only when a newly sampled route produces a smaller value. However, posterior resampling can also increase edge weights, meaning that a stored distance may no longer correspond to any valid path under the current sample. For example, if a single edge is first sampled with a cost of 1 and then with a cost of 2, its stored distance remains at 1 as long as subsequent samples have costs of at least 1. Using these outdated labels to generate query-by-committee disagreements does not guarantee that the disagreements reflect the current posterior. This is a fundamental algorithmic concern, rather than simply a missing convergence proof. The authors need to explain how outdated labels are corrected or recomputed, or provide a different formal justification for the persistent state used by the algorithm.

  2. The experimental comparison does not clearly separate the benefits of soft solving from differences in the observation model. The paper evaluates simple regret and allows SITS to query individual high-variance edges where candidate paths disagree. These edges do not necessarily form a feasible source-to-destination path. In contrast, standard CTS is described as observing the edges along the feasible action selected by its oracle. If individual base-arm queries are allowed, CPE methods such as CLUCB and TS-Explore, which the paper already cites, would be relevant baselines. However, Section 6 dismisses these methods without evaluating them. If the intended setting instead requires path-constrained semi-bandit feedback, the authors need to explain how SITS satisfies this requirement. Moreover, the poor performance of two cumulative-regret policies in these experiments does not demonstrate a fundamental limitation of exact oracles. An exact oracle finds a global optimum for each sampled problem. Any limitations in exploration therefore arise from the policy or posterior, rather than from the oracle becoming trapped in a local optimum.

Questions for authors
  1. How does the algorithm update distance labels and predecessors when resampling increases an edge weight? Please clarify the complete update rules for the persistent solver state and the query-by-committee procedure. It would also be helpful to include a simple example where the previously preferred path becomes more expensive, to demonstrate that the implementation handles this case correctly.

  2. Does the method allow queries on arbitrary sets of edges within a given budget, or must the queried edges form a feasible super-arm? Under a consistent observation model, how does SITS compare with methods such as TS-Explore and CLUCB, as well as exact-solver-based acquisition strategies?

  3. How does SITS compare with a topological shortest-path algorithm for DAGs and an efficient assignment solver in terms of end-to-end wall-clock time, including both acquisition and recommendation costs? Also, which of the reported scaling results are supported only by empirical evidence, and which parameters, such as accuracy, noise level, and optimality gap, are held fixed across experiments?

Reviewer_N1ayOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies pure exploration in combinatorial multi-armed bandits (CMABs). It argues that standard Combinatorial Thompson Sampling (CTS) relies on a black-box exact optimization oracle, which can prematurely commit to a safe but suboptimal structure and incur substantial computational cost by repeatedly solving the combinatorial problem from scratch. The authors propose Soft-Interleaved Thompson Sampling (SITS), which uses the intermediate states of a nonconverged iterative solver to identify structural ambiguity, combines this signal with posterior uncertainty to query decision-critical edges, and reuses the solver state across rounds. The method is instantiated for maximum-weight matching and shortest-path problems. Experiments suggest that SITS outperforms CTS and CombUCB on instances containing structural traps while substantially reducing solver workload.

Critical strengths
  1. The motivation is clear and concrete. The paper provides intuitive examples showing how standard CTS can become trapped in a safe but suboptimal combinatorial structure. These examples make the exploration limitations introduced by a black-box optimization oracle easy to understand.
  2. The central idea is insightful. Instead of using only the final output of an optimization oracle, SITS extracts exploration signals from intermediate solver states, such as message-passing margins and disagreement between candidate paths. This offers a useful new perspective on exploration in combinatorial bandits.
  3. The method addresses statistical and computational efficiency jointly. SITS queries edges that may alter the global solution while retaining solver states across rounds, thereby attempting to improve exploration and avoid repeatedly solving each sampled optimization problem from scratch.
  4. The experiments and ablations are reasonably convincing. The evaluation covers maximum-weight matching, shortest-path problems, and SARS-CoV-2 sequence alignment. The Pure Variance, Pure Structural Margin, and Truncated CTS ablations support the claim that the gains arise from combining structural information with posterior uncertainty, rather than merely from reducing the number of solver iterations.
Critical weaknesses
  1. The theoretical characterization is limited. The paper primarily provides empirical evidence, but does not establish statistical consistency, sample-complexity guarantees, or a finite-time convergence rate for the simple regret of SITS. It also does not characterize sufficient conditions under which SITS can escape the structural traps that cause CTS to fail. Consequently, it is difficult to determine whether the empirical advantages will extend to broader classes of CMAB instances.
  2. The empirical comparison may not use an equivalent query model. In the shortest-path setting, SITS can directly query individual edges in the disagreement set between two candidate paths, whereas CTS and CombUCB typically receive observations only for edges belonging to the feasible path selected by their optimization oracle. If the baselines are restricted to querying feasible super-arms while SITS may query an arbitrary collection of base arms, the methods operate under different feedback permissions. The paper should clarify the interaction protocol and, ideally, include comparisons under a shared query constraint.
  3. The shortest-path implementation appears to have a potential correctness issue. Algorithm 3 retains the Bellman–Ford distance and predecessor states across rounds even though a new set of edge weights is sampled in every round. Standard Bellman–Ford relaxation can only decrease the stored distances. Therefore, when a newly sampled edge weight increases, a distance computed under an earlier sample may remain artificially low and may no longer represent a valid tentative distance under the current graph. The paper does not explain how such stale states are invalidated or corrected.
Questions for authors
  1. Is state reuse valid in the shortest-path implementation? Each Thompson-sampling round changes the sampled edge weights, but Algorithm 3 retains the Bellman–Ford distance and predecessor states from the previous round. Because standard relaxation only decreases distances, how does the method handle increases in sampled edge weights that make previously stored distances invalid?
  2. Why is Bellman–Ford used as the exact baseline on layered DAGs? A shortest path in a DAG can be computed in linear time using a topological ordering. Would SITS retain its claimed computational advantage if it were compared with an oracle designed specifically for DAG shortest-path problems?
  3. Does the reported computational workload include all additional costs introduced by SITS? In particular, does it account for the two QBC branches, acquisition-score computation, edge ranking, matching decoding, and solver-state copying? Reporting end-to-end time would provide a more complete assessment of computational efficiency.
Reviewer_SUF4OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes Soft-Interleaved Thompson Sampling (SITS) for combinatorial bandits. SITS uses information from partially completed optimization solvers to guide which arms to query, while keeping the solver state across rounds. The authors apply it to maximum weight matching and shortest-path problems. Their experiments report lower simple regret on selected difficult instances and reduced solver computation in the tested settings.

Critical strengths

The paper studies reducing computation in combinatorial bandits while improving exploration. Its idea of using intermediate solver states to guide queries is intuitive, and the experiments on matching and shortest-path problems provide evidence of its potential.

Critical weaknesses
  1. SITS Algorithm is presented as a general framework, but its acquisition rule is designed separately for each problem. The paper should clarify what is new compared with methods for combinatorial pure exploration and disagreement-based sampling. Since reducing computation is also a main claim, the paper should compare SITS with prior oracle-efficient methods and explain how using intermediate solver states differs from reducing the number of oracle calls.

[1] Tongyi Cao(2019), Disagreement-Based Combinatorial Pure Exploration: Sample Complexity Bounds and an Efficient Algorithm

[2] Siwei Wang(2022), Thompson Sampling for (Combinatorial) Pure Exploration

[3] Shintaro Nakamura(2024), Thompson Sampling for Real-Valued Combinatorial Pure Exploration

  1. The 3 by 3 matrix example in section 2.1 depends strongly on its prior. The unexplored edges have prior mean 00 and standard deviation 55, while their true weights are all 1212. Each true value is 2.42.4 standard deviations above the prior mean. The reported low probability of sampling from prior follows from this choice, but the paper does not justify the prior or test prior sensitivity on the same bottleneck instance. This example therefore shows a prior-sensitive failure, but does not by itself show that the exact oracle is the cause. With this reason, I am curious about the experimental result in 50 by 50 matrix (section 2.2), as this result can be driven by above same settings.

  2. The experiments do not fully support the broad claims. The main baselines, CTS and CombUCB, are designed for cumulative regret, while the paper evaluates simple regret. Comparisons with methods designed for combinatorial pure exploration would make the results more convincing. The paper should also define the final recommendation used to compute simple regret and clarify which edge sets can be queried in the shortest-path setting.

  3. There are no theoretical guarantees or proofs. The paper leaves finite-time guarantees for future work. As a result, its convergence and regret claims are supported only by experiments. The observed linear growth in the number of iterations does not prove an O(N3)O(N^3) total runtime unless the number of iterations is also shown to be O(N)O(N).

Questions for authors

Appendix C says to build a matching by sorting edges by ∣Mi,j∣|M_{i,j}|. But a large negative belief may indicate that an edge is strongly disfavored. For example, with 2 by 2 matrix W=(7−2;−46)W=\begin{pmatrix}7&-2 ; -4&6\end{pmatrix}, damping ρ=0.5\rho=0.5, and four message updates, this rule selects the off-diagonal matching with weight −6-6, while the optimal diagonal matching has weight 1313. Did I understand this correctly?

Also, I would like the authors discuss the weaknesses part.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Thank you to the reviewers and withdrawal notice

We thank you for taking the time to review our paper and for providing detailed, constructive feedback. Your insights are extremely helpful.

We have decided to withdraw the manuscript at this stage so that we can thoroughly address these points and strengthen the work for a future venue. We appreciate your time and effort.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.