- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies stochastic bandits with knapsacks under coherent quantum-oracle access to reward and resource-consumption distributions. It proposes two primal-dual algorithms. The problem-independent algorithm combines batched quantum reward estimation with classical, per-pull resource observations and claims an improved regret bound. The problem-dependent algorithm uses quantum estimation to identify optimal arms and non-binding constraints, followed by adaptive allocation using approximate LP solutions. It claims improved dependence on the separation gap and resource dimension in the leading logarithmic-regret term, together with computational improvements from quantum LP solvers.
Critical strengths
The attempt to make adaptive resource allocation robust to approximate LP solutions is an interesting algorithmic direction. The additional binding-resource constraints provide a concrete mechanism for seeking two-sided control of resource residuals, rather than relying only on approximate objective values. This addresses an important interface between optimization accuracy and online allocation. As Remark 1 recognizes, such robustness could also benefit classical approximate-LP implementations, making the idea potentially useful beyond the particular quantum solver.
Critical weaknesses
The innovation of the algorithm is slightly weak. I don't see new insights into quantum algorithms, but rather simply invoking them and providing more fine-grained analysis.
Questions for authors
- Which confidence radii are actually intended in Algorithm 1? Can you provide a proof of Proposition 7 compatible with those radii and retaining the claimed dependence on ?
- After correcting the dual-norm bounds and substituting the accuracy required by Theorem 3, what is the resulting end-to-end running time? In which parameter regimes does it improve on the classical approximate-LP implementation in Remark 1?
Gentle reminder - less than 24 hours left for the author-reviewer discussion
As the author-reviewer discussion period will end in less than 24 hours, we would greatly appreciate it if you could join the discussion and share your thoughts on our response.
Thank you for your time and consideration!