acceptodds
Under review as a conference paper at ICLR 2027

Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities

Abstract

Bandits with knapsacks (BwK) is a fundamental model that combines stochastic integer programming with online learning. Classical algorithms for BwK with a time horizon achieve a problem-independent regret bound of and a problem-dependent bound of . In this paper, we initiate the study of the BwK model in the setting of quantum computing, where both reward and resource consumption can be accessed via quantum oracles. We establish both problem-independent and problem-dependent regret bounds for quantum BwK algorithms. For the problem-independent case, we demonstrate that a quantum approach can improve the classical regret bound by a factor of , where is the budget constraint in BwK and denotes the optimal value of a linear programming relaxation of the BwK problem. For the problem-dependent setting, we develop a quantum algorithm using an inexact quantum linear programming solver. This algorithm achieves a quadratic improvement in terms of the problem-dependent parameters, as well as a polynomial speedup of time complexity on the problem's dimensions compared to classical counterparts. Compared to previous works on quantum algorithms for multi-armed bandits, our study is the first to consider bandit models with resource constraints, extending quantum speedups to resource-constrained online learning.

Primary area:
learning theory
Keywords:
bandits with knapsacks, online learning, quantum algorithms, resource-constrained learning, multi-armed bandits

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_ikr9OpenReview ↗
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
  1. 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 BB?
  2. 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?
Reviewer_BitKOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies bandits with knapsacks when the learner has coherent quantum access to reward and resource-consumption distributions. The authors first give a problem-independent primal--dual algorithm that uses quantum estimation for rewards and tracks resource consumption classically at each round. They then develop a problem-dependent algorithm that identifies the optimal LP support and binding resource constraints, and allocates pulls using approximate LP solutions. The claimed improvements concern the regret coefficients, the parameters appearing in the problem-dependent bound, and the computational dependence on the problem dimensions. The results are supported by theoretical regret and runtime analyses.

Critical strengths
  1. The resource constraints make this a worthwhile extension of quantum bandit learning. The learner must account for feasibility and for stopping when a resource is exhausted, so improving reward estimation alone does not settle the problem.
  2. Allowing approximate LP solutions in adaptive resource allocation could make the approach useful in both quantum and classical implementations. I find this aspect promising, provided the errors in the identification argument can be resolved.
Critical weaknesses
  1. I am not convinced that the identification procedure in Algorithm 2 is justified by the stated solver guarantees. Lines 13 and 16 use strict comparisons between LP values, even though the solver is allowed an error of εLPT\varepsilon_{\mathrm{LP}}T. Proposition 8 and Equation (47) show that the desired arms and constraints eventually pass these tests, but do not rule out false positives. For an irrelevant arm ii, the exact values can satisfy OPTi=OPTLP\mathrm{OPT}_i = \mathrm{OPT}_{\mathrm{LP}}. Even without statistical uncertainty, the approximate outputs may satisfy

OPT~LP>OPT~i.\widetilde{\mathrm{OPT}}_{\mathrm{LP}} > \widetilde{\mathrm{OPT}}_i.

For example, the solver could return the exact optimum for the original LP and a feasible solution εLPT\varepsilon_{\mathrm{LP}}T below the optimum for the LP with arm ii removed. The comparison needs an error margin or another form of certification. In addition, line 19 tests ∥C⋅,iL(t)−C⋅,i∥∞>θ\lVert C^L_{\cdot,i}(t) - C_{\cdot,i} \rVert_{\infty} > \theta, which requires the unknown true mean C⋅,iC_{\cdot,i}. Both issues affect the identification and allocation steps used in the problem-dependent regret proof.

  1. The normalization in Appendix C.1 appears to give the wrong bound on the dual solution. After setting ξ′=ξ/T\xi'=\xi/T, the right-hand side in Equation (33) becomes B/T=bB/T=b. The general bound on the dual solution's ℓ1\ell_1 norm is then 1/b=T/B1/b=T/B, rather than 1/B1/B as used in the paper. For instance, max⁡ξ′≥0{ξ′:bξ′≤b}\max_{\xi'\ge 0}\{\xi':b\xi'\le b\} has optimal dual variable 1/b1/b. The reduction in Proposition 2 and Theorem 2 therefore needs to preserve the resulting dependence on bb, unless an additional assumption makes it constant. As it stands, the proof does not establish the claimed runtime dependence.
Questions for authors
  1. Could the authors give a comparison rule for approximate LP outputs that rules out false positives while still ensuring eventual identification under the stated solver guarantees?
  2. How can the test in line 19 of Algorithm 2 be implemented without knowing CC? Would a test based only on observations preserve the allocation argument in Proposition 4?
  3. After correcting the dual-norm bound following Equation (33), what dependence on b=B/Tb=B/T remains in Theorem 2?
Reviewer_BN1QOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies bandits with knapsacks under coherent quantum access to reward and resource-consumption distributions. It proposes two algorithms extending existing classical frameworks. The problem-independent algorithm combines quantum reward estimation with classical, per-pull resource tracking and claims an improved regret bound. The problem-dependent algorithm uses quantum mean estimation to identify optimal arms and non-binding constraints, followed by adaptive resource allocation through approximately solved linear programs.

A central technical component is the analysis of how LP approximation errors affect the normalized arm-selection probabilities and remaining resources. The paper claims improved dependence on instance parameters in the regret bound and a polynomial improvement in computational complexity with respect to problem dimensions. Validation is entirely theoretical; no experiments are presented.

Critical strengths
  1. A well-motivated extension of quantum bandit learning. Resource constraints introduce a meaningful complication beyond ordinary multi-armed bandits: exploration must account for both information acquisition and resource depletion. Investigating whether quantum estimation remains useful in this setting is a worthwhile theoretical question.

  2. The attempt to support approximate LP solutions is technically interesting. The additional constraints in LP (9) and the perturbation analysis in Lemma 10 address how approximate feasibility affects arm-selection probabilities. Establishing such robustness would be useful because LPs are solved repeatedly, and, as Remark 1 observes, the benefit could extend to classical approximate solvers.

Critical weaknesses
  1. The stated regret guarantees are not adequately supported by the interaction model and current analysis. Definition 1 counts each forward or inverse oracle invocation as an arm pull, but it does not specify the realized resource consumption associated with an unmeasured coherent query (if I didn't miss anything). This matters in Phase I of Algorithm 2: resource consumption is estimated coherently, while the algorithm subsequently updates the remaining budget B(t)B^{(t)}. Section 3 explicitly emphasizes the need to track consumption after every pull. A precise rule for resource expenditure, budget observation, and termination during coherent estimation is therefore necessary to establish feasibility and interpret the regret guarantee. There is also a concrete issue in the proof of Theorem 1. Proposition 7 invokes the cumulative-consumption error bound of Badanidiyuru et al., but Eq. (18) uses the radius 3log⁡T/ni(s)\sqrt{3\log T/n_i(s)}, rather than the mean-dependent radius required by the cited argument. With Eq. (18) as written, the deterministic time resource C1,i=bC_{1,i}=b contributes $\sum_{s=1}^{\tau-1}\sqrt{\frac{3\log T}{n_{i(s)}(s)}} \ge (\tau-1)\sqrt{\frac{3\log T}{T}}$ to the first coordinate of the error sum in Eq. (26). For a run lasting Θ(T)\Theta(T) rounds, this is Ω(Tlog⁡T)\Omega(\sqrt{T\log T}). With fixed (m,d)(m,d) and, for example, B=TB=\sqrt T, this exceeds the claimed O(KmB+Kmlog⁡T)O(\sqrt{KmB}+Km\log T) bound, where K=O(log⁡(dT))K=O(\log(dT)). Consequently, the current proof does not establish the stated dependence on (B); a corrected estimator or a different argument is needed.

  2. The claimed dimension-dependent runtime improvement is not established at the LP accuracy required for the regret guarantee. Proposition 2 gives the Phase II LP cost as $\widetilde O \left( \frac{\sqrt{m+d}\log^5T}{\varepsilon_{\mathrm{LP}}^{5/2}} \right).$ However, Theorem 3 requires $\varepsilon_{\mathrm{LP}} \le \frac{2b\theta q\log^2T}{405}, \qquad \theta\le \frac{\min{1,\sigma^2}q}{12k^2},$ where q=min⁡χ,δq=\min{\chi,\delta} and k=min⁡m,dk=\min{m,d}. Substituting this accuracy restriction into the displayed solver-cost expression introduces a k5k^5 factor, in addition to m+d\sqrt{m+d}, together with further instance-parameter dependence. Thus, treating εLP\varepsilon_{\mathrm{LP}} as dimension-independent in the comparison can substantially overstate the improvement. The paper should identify a joint parameter regime in which its regret guarantee and computational advantage hold simultaneously. The comparison should also include the classical approximate-LP variant acknowledged in Remark 1. As presented, Table 2 does not substantiate the broad claim of a polynomial improvement in dimension under the required accuracy.

Questions for authors
  1. What resource consumption is charged to each coherent or inverse oracle call in Phase I of Algorithm 2? How is the remaining budget observed and updated, and how is budget exhaustion handled during a QMC execution?

  2. How is the Phase II test involving the unknown matrix CC in Algorithm 2, line 19, implemented? In Phase I, what prevents additive LP errors from causing false-positive identification? Eq. (47) establishes detection of the desired indices, but the raw comparisons also need to exclude incorrect indices. Please also clarify the loop condition ∣I^∗∣+∣J^′∣≤d|\hat I^*|+|\hat J'|\le d, since correct identification yields equality.

  3. Can you give the full runtime after substituting an admissible εLP\varepsilon_{\mathrm{LP}}, and identify when it improves over a classical solver at matched accuracy? In addition, please explicitly verify condition (71), including the accumulated LP approximation term in Eq. (69), and state any further restrictions on accuracy or TT.

  4. Proposition 7 bounds the cumulative resource-estimation error in terms of the budget BB. However, the confidence intervals in Eq. (18) appear to yield a bound depending on the number of rounds TT instead. What argument gives the stronger dependence on BB ? Is a different confidence interval, such as the mean-dependent one used in the cited classical result, intended?

Comments on the paper

1 comment
AuthorsOpenReview ↗

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!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.