- 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
-
Using intermediate solver ambiguity to guide queries, while preserving the solver state across iterations, is a promising approach when optimization is computationally expensive.
-
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
-
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.
-
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
-
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.
-
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?
-
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?
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.