acceptodds
Under review as a conference paper at ICLR 2027

Corruption-Robust Sparse Linear Contextual Bandits with Knapsack Constraints

Abstract

We study sparse linear contextual bandits with knapsack constraints under joint reward and consumption corruption. Consumption corruption creates a challenge beyond corrupted rewards: it affects not only statistical estimates, but also the recorded budget, resource prices, and stopping decisions that govern future allocation. We develop Robust Optimistic Primal–Dual (ROPD), an estimator-modular framework that combines corruption-aware confidence widths with online resource prices and a budget-safety rule. With concrete sparse implementation, ROPD achieves regret against a clean population-LP benchmark of under forced exploration and population-design coverage, and under on-policy realized-design coverage, for a supplied valid corruption bound under the stated proportional-budget scaling and fixed model/design parameters. When the corruption level is unknown, Shared-Grid adapts confidence radii around common point estimates fitted to a single realized history, incurring explicit initialization and master-comparison costs; its sharper on-policy guarantee additionally requires recommendation coverage. Both methods preserve observed budgets on every realization and bound clean resource violation by cumulative consumption corruption. These results connect corruption-robust sparse estimation with resource accounting, pricing, and stopping in high-dimensional online allocation.

Primary area:
learning theory
Keywords:
Contextual Bandits with Knapsacks, Adversarial Corruption, Online Learning

Reviews

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

The paper studies sparse linear contextual bandits with knapsack constraints under joint reward and consumption corruption. It proposes Robust Optimistic Primal-Dual (ROPD), an estimator-modular framework that couples corruption-aware confidence widths with online resource pricing and a safety rule on observed budgets, and provides regret guarantees against a clean population-LP benchmark. With a concrete norm-constrained Lasso implementation, the paper derives regret bounds of order Õ(T^{2/3} + Γ T^{1/3}) under forced exploration with population-design coverage and Õ(√T + Γ) under on-policy realized-design coverage, and introduces a Shared-Grid scheme that adapts to unknown corruption using shared estimates on the realized history.

Critical strengths

• Addresses open problem. The paper addresses a genuinely important gap between corruption-robust contextual bandits and contextual bandits with knapsack constraints. The gap is important because corrupted consumption affects future allocation via budget accounting and dual variables, not merely statistical estimation.

• Joint regret and resource-control analysis. The paper provides a neat treatment of corruption that disentangles its statistical and resource-allocation effects, yielding regret guarantees alongside exact observed-budget feasibility and bounds on clean-resource violation.

• Empirical Evaluation. While limited in scope, the inclusion of empirical results is well appreciated. The results provide some evidence supporting that the proposed mechanisms behave as intended and offer some support for the practical relevance of the theoretical findings.

Critical weaknesses

• Strongest regret guarantees rely on difficult-to-verify trajectory conditions. The strongest OP guarantees are conditional on trajectory-level coverage assumptions (Conditions 4 and 5). While the paper proves the regret bounds under these assumptions, the analysis does not show that ROPD or Shared-Grid generate trajectories satisfying these conditions. Condition 5 is especially notable because it is introduced precisely because the default EXP4.P smoothing does not automatically provide a horizon-independent recommendation coverage ratio. Thus, the strongest results are conditional on realized-path properties rather than algorithmically verified properties, and should be interpreted as conditional performance results rather than fully algorithmic regret guarantees.

• Conservative Lagrangian scale parameter. Choice of the Lagrangian scale Z presumes a computable upper bound (e.g., T/B_min); these may be conservative when budgets are small. Since Z directly impacts confidence radii, the corruption budget scaling, and regret guarantees, the impact of misspecification is potentially significant.

• The presentation is unnecessarily dense and notation-heavy. The manuscript introduces many technical components simultaneously and often prioritizes formalism over intuition, making it difficult to identify the central ideas of the paper. This issue is compounded by the introduction of substantial notation and auxiliary quantities before their role is clearly explained. Given the already extensive appendix, the main paper should focus more on conveying the high-level algorithmic and theoretical insights rather than reproducing large amounts of technical machinery. In particular, the importance of Conditions 4 and 5 is easy to miss despite the fact that the strongest regret guarantees rely on them. A clearer roadmap, earlier discussion of the key assumptions, and a more concise treatment of the later proof developments would substantially improve accessibility.

Questions for authors

• Can Conditions 4 and 5 be shown to hold for ROPD or Shared-Grid under additional verifiable assumptions, rather than being treated as trajectory conditions?

• How sensitive are the theoretical guarantees and empirical performance to the choice of Z, and what guidance can be provided when the available upper bounds used to calibrate Z are highly conservative?

Reviewer_7SDrOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies corruptions in sparse linear contextual bandits with knapsack constraints (CBwK). This paper develops algorithms that ensure:

  1. When there's a known upper bound Γ\Gamma on the total corruption, an explicit exploration algo gets T2/3+ΓT1/3T^{2/3}+\Gamma T^{1/3}.
  2. If all outcomes (somehow magically) satisfy a RSC condition required by Lasso, T+Γ\sqrt T+\Gamma is attainable.
  3. Without such a known upper bound, using a meta-algorithm over known-Γ\Gamma algorithms (EXP.4), same rates are attainable.
Critical strengths

No previous paper studied exactly the same setup.

Critical weaknesses
  1. The assumption that realistic actions' outcomes satisfy RSC is never justified. This assumption just makes non-sense. How to ensure coverage is always a hard (if not the hardest) problem in linear cases (e.g., in linear adversarial MDPs that has been many papers improving the exponent of T from 14/15 Luo'21, 8/9 Dai'23, 6/7 Sherman'23, 4/5 Kong'24, and now 3/4 Liu'24, where the only main difficulty is exactly the coverage is insufficient and exploration isn't free). So I'd view all those "on-policy sampling" results as vacuous. All remaining results are boring explicit exploration algorithms, giving 2/3 dependency in T.
  2. Compared to Ma'24, who already combined sparse estimation with primal-dual and obtain the same T2/3T^{2/3} and T\sqrt T bounds in non-corrupted sparse CBwK bounds, the only new ingredient in this paper is corruption. But the corruption part is also standard and not interesting (plus minor: this paper is considering the \ell_infty norm, as discussed in Liu'24). I fail to identify any new technical contribution in this paper beyond putting them together. The main advertised technique, optimism + primal-dual, dates at least back to Agrawal'16. The unknown-Γ\Gamma algo just uses the standard CORRAL / EXP4 stype meta-algorithm framework. The current presentation doesn't exhibit anything new.
  3. The presentation is quite bad, with a lot of non-standard terminologies that are either newly created or adapted from an unrelated literature. One notable example is the "population-LP benchmark," whose formula is so common in either online LP or BwK literature that become customary to be named as "fluid benchmark" (since it's the OPT under the fluid relaxation). I don't quite see the point of introducing a brand new terminology, except for making this paper much harder to read. Other examples, which I am lazy to further justify, include "priced budget" (unrelated to the shadow price / dual variable at all) vs "effective corruption budget", "budget-safety test", "use" vs "consumption" (coexisting in this paper), "price-learning penalty", "override concentration". All make this paper unnecesarily difficult to read.
Questions for authors

See weakness 1-2.

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

$\newcommand{\rew}{\mu^*} \newcommand{\cost}{w^*} \newcommand{\ip}[1]{\langle #1 \rangle} \newcommand{\Bmin}{B_{\mathrm{min}}} \newcommand{\rcl}{r^{\mathrm{cl}}} \newcommand{\ccl}{c^{\mathrm{cl}}} \newcommand{\vobs}{\mathrm{Viol}_{\mathrm{obs}}} \newcommand{\vcl}{\mathrm{Viol}_{\mathrm{clean}}} $

This paper studies finite action contextual linear bandits with knapsacks with feedback corruptions. As in the usual setup without feedback corruptions, arms have associated means \rewa\rew_a and \costa,i\cost_{a,i} for mm cost indices with associated budgets B=(B1,⋯ ,Bm)B = (B_1, \cdots, B_m), and for a context xt,x_t, the clean rewards and costs for arm aa are \ip\rewa,xt\ip{\rew_a, x_t} and \ip\costa,i,xt\ip{\cost_{a,i}, x_t}. Throughout, boundedness is assumed, and contexts are assumed to be drawn iid from a fixed (unknown) distribution. However, instead of observing the rewards and costs directly, the learner sees a copy corrupted in two ways: first by subGaussian noise, and subsequently by an adversary that perturbs each of these signals by adding some ξtr\xi^r_t and ξt,ic\xi^c_{t,i}, and the resulting corrupted signals, clipped to [0,1][0,1], are observed. Naturally, (pseudo)regret is defined relative to the nominal reward. The paper further adopts a setting whereby the arm means are all sparse, but this is dealt with in a modular way. The paper adopts the setting wherein an extra null action with zero reward and consumption is assumed available. The nominal, clean (corrupted by noise), and corrupted-and-clipped rewards are denote r0,\rcl,r^0, \rcl, and rr respectively, and similarly for the costs c0=(c10,⋯ ,cm0)⊤,c^0 = (c^0_1, \cdots, c^0_m)^\top, and analogously the 'clean' and clipped.

The paper follows a classic primal-dual approach, and the adversary is limited in terms of this thus: let Z:=T/\Bmin,Z := T/\Bmin, where \Bmin=min⁡Bi\Bmin = \min B_i (TT can be replaced by any upper bound on the value of the static nominal LP solution, if available). This ZZ is a natural upper bound on the dual variable in the Lagrangian r0−Zλ⊤c0r^0 - Z \lambda^\top c^0, where λ\lambda lives in the simplex, since for any nontrivial solution consumption of a signal must be offset by the reward gained. Let CZ:=∑tmax⁡a∣rt(a)−\rclt(a)∣+Zmax⁡i∣ct,i(a)−\cclt,i(a)∣.C_Z := \sum_t \max_{a} |r_t(a) - \rcl_t(a)| + Z \max_i | c_{t,i}(a) - \ccl_{t,i}(a)|. The adversary is required to satisfy the constraint that CZ≤ΓC_Z \le \Gamma where Γ\Gamma is termed the corruption budget. Recall here that r,cr, c are corrupted and clipped, while \rcl,\ccl\rcl, \ccl are noisy. Both the case of known and unknown Γ\Gamma are studied. This is a "weak adversary" in the sense of Liu et al.

The high level approach taken to constraints is thus: the observed violation signals give a notion of cumulative observed consumption, Ut,i=∑s<tbt(at)U_{t,i} = \sum_{s < t} b_t(a_t). The authors construct operating budgets, and enforce that a non-null action can only be taken if Ut≤Bop−1.U_t \le B^{\mathrm{op}} - 1. This immediately means that the "observed violation" \vobs:=max⁡i(UT,i−Bi)+\vobs := \max_i (U_{T,i} - B_i)_+ is nought. Further, directly by the adversary bound, this in turn implies that the clean violation \vcl:=max⁡i(∑bt,i(at)−Bi)+≤Γ/Z\vcl := \max_i ( \sum b_{t,i}(a_t) - B_i )_+ \le \Gamma/Z. Note that this is a weakening of the usual condition in BwK, which instead demands that \vcl=0\vcl = 0. For known Γ\Gamma, this can clearly be managed by adding a step-back of Γ/Z\Gamma/Z to each budget. The paper does not deal with attaining \vcl=0\vcl = 0 for unknown Γ\Gamma

For known Γ,\Gamma, the approach is somewhat standard: a usual type of estimation is performed to get confidence bounds (inflated to handle the corruption), and it is assumed that these integrate nicely. Given the ucbs, the usual usual optimistic primal-dual method of BwK is employed, with the dual scaling factor Z,Z, and the dual parameters increased in exponential steps of (bt−Bop/T)+(b_t - B^{\mathrm{op}}/T)_+. The main bounds are stated in terms of a high level "interface" imposing these conditions, which gives a bound with three principal components: the cost due to integrating the confidence widths, that of learning the optimal dual parameters, and that of forced exploration (if any is used). The overall flow of the argument is more or less identical to standard BwK: the only place where the corruption enters is the inflated confidence widths to handle it.

To operationalise this bound thus requires one to specify estimation procedures. Since the authors adopt a sparse setting, they propose just using Lasso for this. There's two pieces that are important: handling corruption, and ensuring that the context gives an appropriate condition on the effective design for each action.

  • For the design (i.e., to get a good RSC parameter κ\kappa; specifically a type of l_1 tolerance RSC in the sense of equation (31) of Negahban et al. is used), it is either assumed that the design is good enough after a certain number of samples per action, which gives a additive KnKn burn in cost, where nn is the burn-in needed. Otherwise, this can be enabled by forcing exploration (by picking aa uniformly at some rate). Note that in this forced case, only the samples observed during the forced exploration are used.
  • A Lasso error analysis under corruptions is used. This per se requires a bound on the total corruption applied to the feedback for each aa, for which just Γ\Gamma is used. This dumps an extra Γκn\frac{\Gamma}{\kappa n} term in the radius for each arm when estimation is on the basis of nn samples. Without forced exploration, this sums to KΓ/κlog⁡(T),K \Gamma/\kappa \log(T), while with exploration, this sum blows up inversely with the exploration rate rate. Note that in the forced exploration case, experts only use the feedback gained during this forced exploration.

Overall the regret rates are determined by whether exploration is needed or not:

  • if yes, then balancing the costs of this with exploitation yields a T−1/3T^{-1/3} exploration rate, giving a regret bound of O(K1/3T2/3+K2/3ΓT1/3),O(K^{1/3}T^{2/3} + K^{2/3}\Gamma T^{1/3}), where terms involving dependence on d,s,d,s, et c. are suppressed.
  • if no, then instead a bound of O((KT)1/2+KΓ)O((KT)^{1/2} + K\Gamma) is stated.

This brings us to the case of unknown Γ\Gamma. Herein, the strategy proposed is place an exponential grid over the possible values of Γ\Gamma (which is bounded to (1+Z)T(1+Z)T), and run, in parallel, copies of the strategy for each value, using an EXP.4 routine to select between them. More precisely, the remaining budget levels are tracked in common across all these experts, as is the value of the dual variable λt\lambda_t that they use. Now, things differ a bit depending on whether the forced exploration mode is used or not.

  • In the forced exploration case, experts only use the feedback from forced exploration rounds. This can simply be added on top of the EXP4 routine, and the experts can all be run as-is. Then one only pays the forced exploration regret plus the EXP4 overhead, which scales as O((1+Z)KTlog⁡(TZ))O((1+Z)\sqrt{KT \log(TZ)}).

  • Without forced exploration, each expert consumes all feedback to compute their regression estimates. Now a complication arises: an expert may propose an action many times without receiving feedback for it. To handle this modularly, a condition is introduced which demands that for any Γ\Gamma, the number of times any action has been played must be at least 1/χ1/\chi times the number of times it has been proposed by Γ,\Gamma, up to a slack. Conceptually, this is roughly a bound on the typical delay: one can sort of pretend that this expert picks an action, and then has to wait about χ\chi rounds to get feedback, playing the same action for all χ\chi rounds. Thus, as long as the value Γ\Gamma associated with the expert exceeds CZ,C_Z, the action sequence proposed by this expert will enjoy the known-Γ\Gamma regret bound, up to inflation by a factor of χ\chi in the terms arising from the confidence radius. Adaptivity to CZC_Z follows since there is an optimal Γ∗\Gamma_* in the grid that lies between CZC_Z and 2CZ2C_Z.

    Operationally, it is argued that this χ\chi can be controlled by mixing the EXP.4 proposed law with a uniform of mass pmin,p_{\mathrm{min}}, where this value is taken to scale as Klog⁡(T)/T,\sqrt{K \log(T)/T}, and the associated χ\chi is 2/pmin2/p_{\mathrm{min}}. Note that in such a case, the algorithm for each value in the grid exceeding CZC_Z retains validity with the appropriate confidence radius inflation. It should be noted that the results in this setup cannot be easily adjusted to get a \vcl=0\vcl = 0, since one cannot simply reduce the operating budget without knowing a good bound on CZ,C_Z, and since all elements of the grid share the same operating budget. The paper does not explicitly discuss how this can be done.

Critical strengths

The paper is certainly pertinent to the bandits and online learning community at ICLR. The subject is interesting and timely, and to my understanding the proofs are correct. The setup is presented in a fairly modular way, and the exposition of the approach is mostly okay, although it gets quite dense at places, and one result is written in (IMO) a misleading way. I find the results interesting, although I also think that they follow somewhat straightforwardly from the existing literature (see below).

Critical weaknesses

Overall view: While I find the results interesting, I find the paper in its current state to be incremental: most of the arguments go through in a very standard way, and the main argument that deviates from this is not executed well-enough for the associated result (Cor. 2 part (ii)) to be convincing (the first point below). This limits my recommendation.

  • First, an important point about the claims:

    Ignoring χ\chi in the on-policy unknown Γ\Gamma bound is very very misleading (Table 1 final row and line 475). The sole place I have seen this χ\chi being assigned any value is section D.5, where it is set to 2/qcov,2/q_{\mathrm{cov}}, and qcovq_{\mathrm{cov}} is itself set to pminp_{\mathrm{min}} (line 1113), which in turn is ∼Klog⁡(T)/T\sim \sqrt{K \log(T)/T} (D.3). Similarly, of course, with ncandn_{\mathrm{cand}}. With this value of χ,\chi, the bound of Cor. 2 (ii) is not even sublinear: you get T+TE[Γ∗]T + \sqrt{T} \mathbb{E}[\Gamma_*].

    The question becomes if assuming a constant χ\chi is even reasonable. The authors themselves say that this is not reasonable for EXP4 (which is why the condition is introduced, line 429). Functionally, this needs some sort of argument about versions of Alg. 1 run with a too-small Γ\Gamma, which is not present in the paper. If χ\chi is indeed depending on TT, one can at best tune it to T1/3T^{1/3} by setting pminp_{\mathrm{min}} to T−1/3T^{-1/3} analogously to ϵ\epsilon in the FE case, and end up at the same type of bound in terms of TT-dependence. Of course, in this case, this pminp_{\mathrm{min}} is essentially acting as a forced exploration (albeit I understand that κop\kappa_{\mathrm{op}} and κFE\kappa_{\mathrm{FE}} might be quite distinct).

    Additionally, I think that omitting the Γ\Gamma dependence in Table 1 is quite strange. In fact this is a very strange omission: ultimately, the contribution is about managing the effects of corruption, so the cost terms depending directly on it are natural to specify.

  • The technical novelty relative to the literature is unclear to me. Firstly, let me note that the paper is positioned entirely technically: there is little to no discussion of the practical concerns regarding corruption, or even a simulation. Given this, technical novelty is a critical criterion to judge this paper by. However, IMO, the paper is only incremental in this sense.

    In the case of known Γ\Gamma everything proceeds almost exactly the same as BwK, with two exceptions: at one point in the result, one passes from the regret relative to clean costs to a regret relative to the observed costs, picking up a CZC_Z penalty straightforwardly, and the confidence radii have to be inflated to handle the corrupted reward (such bounds are classical for Lasso). As such, this section more or less reads as putting these two things together, and observing that everything works as before. I am not too familiar with work on model selection in this adversarially perturbed setting, but one must note that the only nontrivial result is for the fixed exploration setup, so the principal challenge whereby the master algorithm does not supply the desired information to the gridded learner is totally moot---then we just end up with a EXP4 guarantee.

    Note that it may be that I am simply missing something about the challenge of executing these steps. If so, then I am afraid it is because the paper never really discusses, in a specific way, what the explicit challenge in the analysis or design is, and how this does not follow from a simple combination of past results. In fact, in the main text, all discussion of related work is entirely about background and comparison of bounds, and this crucial aspect is simply not discussed. This is also true of much of Appx A, where most discussion only delineates differences in the model. The sole exception is lines 715-721, wherein the introduction of the candidate-coverage condition is specified as a distinction. While I agree that this is distinct, I also think that, as outlined above, this condition is not satisfactorily operationalised in the paper.

    The other potential source of novelty I could find is the analysis of perturbed-Lasso with a perturbation-unaware regularisation strength (a version where regularisation varies with the perturbation is standard). Certainly, the ingredients are all standard, but I am not familiar with this result. That said, again no specific claim of novelty is made, and instead all we get is that the conditions used are standard (which I agree with).

  • Lack of lower bounds, and positive violation: the standard BwK literature is concerned strongly with maintaining consumption guarantees (hence the stopping time and null action in the setup). This is often accommodated by a step-back, and it is clear that this can work in the known Γ\Gamma case, but far from obvious in the unknown Γ\Gamma case. Unfortunately, the paper does not address this issue either, instead admitting a positive bound on the clean violations. This is not, in and of itself, a problem: it seems natural that without every observing the consumption directly, one cannot help but violate. However, I think that one needs a lower bound to convincingly make that claim. Without some result saying this, the results of the paper pointedly diverge from the usual consideration in BwK. Of course, more broadly, a lower bound on regret even under a condition of zero observed violation would be interesting, but I don't know that it is crucial.

  • The quality of the writing in the much of the paper is fine, but it gets quite confusing in places. In part this is because things are very densely written, with many easy to miss variables introduced in various paragraphs, to the degree that the Theorem statements themselves get confusing to parse. As an example, is it really necessary to write HTH_T instead of log⁡(T)\log(T) in big-O statements? Or to incorporate the dependence of ϵ\epsilon on various parameters in one part of the statement, but to not do it in another part of the same statement? Section 5 gets especially confusing because the explanations of the "master" method are very terse, essentially amounting to several variable declarations, and because the exposition of the conditions is not very clearly checkpointed. I think this can be much much improved if page 8 were rewritten entirely with a little room to breathe, and especially if one introduced paragraph breaks between talking about the grid and the `master', and between the stuff on FE and OP modes in this setup.

Questions for authors
Reviewer_Fk5nOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary
  • This paper studies sparse linear contextual bandits with knapsack constraints under both reward and resource consumption corruptions. Performance is evaluated against an uncorrupted benchmark.

    • The authors emphsize that corrupted consumption not only complicates estimation, but also directly impacts the budget tracking, dual prices, and the stopping time.
  • The paper proposes optimistic primal-dual algorithms. At each active step, the chosen action maximizes the UCB score on the estimated Lagrangian to balance rewards and consumption, while resource prices are updated online with a budget-safety stopping rule.

    • The framework is estimator-modular, so that any estimator, which satisfies the pointwise confidence (Eq. (10)) and cumulative width bounds (Eq. (12)), is allowed. As a concrete example, the authors analyze a norm-constrained Lasso estimator (Proposition 1, Line 203–210).
    • To establish the Lasso confidence bounds, the analysis relies on restricted strong convexity (RSC) of the retained designs, compared to the compatibility condition in Lasso bandits. Under forced exploration (FE), RSC is derived from a population assumption on the contexts (Assumption 3). Under on-policy learning (OP), it is directly assumed on the algorithm's generated designs (Condition 4).
  • The analysis covers both known and unknown upper bounds Γ\Gamma on the effective corruption budget CZC_Z.

    • Known Γ\Gamma: O~(T2/3+ΓT1/3)\tilde O(T^{2/3} + \Gamma T^{1/3}) under FE, and O~(T+Γ)\tilde O(\sqrt{T} + \Gamma) under OP.
    • Unknown Γ\Gamma: Shared-Grid runs an EXP4.P master over a dyadic grid of corruption candidates that share point estimates from a single realized history. This achieves O~(T2/3+E[Γ⋆]T1/3)\tilde O(T^{2/3} + \mathbb{E}[\Gamma^\star] T^{1/3}) under FE and O~(T+E[Γ⋆])\tilde O(\sqrt{T} + \mathbb{E}[\Gamma^\star]) under OP.
  • Synthetic experiments test both the known and unknown Γ\Gamma settings, comparing the effects of reward versus consumption corruption and checking pathwise budget accounting.

Critical strengths
  1. The paper tackles a practical yet underexplored problem where corruption affects both rewards and recorded resource consumption.

    • Separating the observed budget consumption from true (clean) resource usage makes a lot of sense for real-world allocation problems.
    • In my opinion, the safety rule has the nice feature that the budget guarantees hold regardless of whether the high-probability confidence events hold: the budget is never violated with observed consumptions, and the true budget violation is bounded by the realized consumption corruption Cb(T)C_b(T).
  2. This work provides theoretical bounds for both cases where the Γ\Gamma term is known and unknown.

    • In particular, when the corruption bound Γ\Gamma is unknown, independently updated corruption candidates would need counterfactual action-specific histories that were never collected.
    • The proposed Shared-Grid method neatly sidesteps this by having all corruption candidates share the same Lasso point estimates fitted on a single realized history, differing only in their confidence radii.
    • Because a single noise event validates all Γ≥CZ\Gamma \ge C_Z simultaneously, the analysis can simply plug in the smallest valid grid point Γ⋆≤max⁡1,2CZ\Gamma^\star \le \max\\{1, 2C_Z\\} after the run without taking a union bound over the grid (Lemma 16).
    • Under forced exploration, this recovers the same regret order as the known-Γ\Gamma setting with Γ\Gamma replaced by E[Γ⋆]\mathbb{E}[\Gamma^\star], up to explicit initialization and EXP4.P master-comparison costs.
  3. The proof cleanly tracks where corruption impacts the regret bound.

    • Measuring corruption via an upper bound on its impact, ∣ctr(a)∣+Z∥ctb(a)∥∞\vert{}c^r_t(a)\vert{} + Z\Vert{}c^b_t(a)\Vert{}_\infty, on the Lagrangian score (Eq. (5) and (6)) puts reward and resource corruption on the same scale.
    • This allows Theorem 1 to cleanly separate the direct corruption transfer Γ\Gamma from the estimator's corruption-induced width ψest(Γ)\psi_{\text{est}}(\Gamma).
Critical weaknesses
  1. Although I'm aware that bounding rewards and consumptions in [0,1][0,1] under a linear model is common in the linear contextual bandits with knapsacks literature, I think this assumption is quite restrictive in the high-dimensional sparse setting that motivates the paper.

    • Specifically, with means in [0,1][0,1] and ∥x∥2≤1\Vert{}x\Vert{}_2 \le 1, the features can move the mean only within a narrow range.
    • For example, in the instance of Appendix E.7, d(c2+∑jbj2)≤R2d(c^2+\sum_j b_j^2) \le R^2, so the feature effects shrink like R/dR/\sqrt{d} unless RR grows with d\sqrt{d}; moreover, since ∥x∥2≤1\Vert{}x\Vert{}_2 \le 1, the population curvature in Assumption 3 is at most 1/d1/d (Appendix E.3).
    • Thus, as dd grows, I am concerned that either the sparse features barely affect the means, or a polynomial dependence on dd re-enters through RR and the curvature, which the simplified rates treat as fixed.
  2. The on-policy guarantees assume the design condition rather than derive it.

    • The sharper on-policy rates rely on Condition 4, which requires RSC on the action-specific designs actually generated by the algorithm.
    • As the paper itself notes, this is a condition on the algorithm's own adaptive, corrupted, and possibly stopped trajectory, and the stochastic diversity of contexts (Assumption 3) alone does not imply it.
    • To my knowledge, the Lasso bandit literature typically assumes a condition on the population covariance and then derives the compatibility of the empirical Gram matrix: via forced sampling (Bastani & Bayati, 2020) or via diversity conditions on the contexts such as relaxed symmetry and balanced covariance (Oh et al., 2021; Ariu et al., 2022; see also the comparison in Lee et al., 2025).
  3. Missing related work on online allocation and constrained bandits under corrupted constraints.

    • The literature review misses recent studies in which both rewards and constraints deviate adversarially from a stochastic model, such as Stradi et al. (2024).
    • Their work corrupts the environment itself rather than the observations of a latent clean process, so I'm aware that the settings differ. Still, since a core motivation of the paper also arises from consumption corruption, discussing these differences is needed to properly situate the paper's contribution.to properly situate the paper's contribution.
  • References
    • Ariu et al., (2022). Thresholded Lasso bandit.
    • Lee et al., (2025). Lasso bandit with compatibility condition on optimal arm.
    • Oh et al., (2021). Sparsity-agnostic Lasso bandit.
    • Stradi et al., (2024). Learning constrained Markov decision processes with non-stationary rewards and constraints.
Questions for authors
  1. How is the RSC condition in Eq. (41) related to the compatibility condition commonly used in the Lasso bandit literature?

    • To my knowledge, the compatibility condition on Σ=E[xx⊤]\Sigma = \mathbb{E}[xx^\top] is weaker than positive definiteness of Σ\Sigma, so I wonder whether the forced-exploration result could also be stated under the compatibility condition.
  2. Beyond combining an existing corruption-robust estimator with a standard primal-dual CBwK analysis, could the authors clarify which part of the analysis required a genuinely new technique because of consumption corruption?

  3. Could the authors clarify how the consumption model was set up in the experiments, and whether any experiment uses consumption that varies with sparse features?

    • According to Eq. (86), the presented consumption means do not seem to depend on the context, and since the first coordinate of xx in Eq. (84) is fixed at 0.500.50, each of the Km=6Km = 6 consumption parameters wa,i⋆w^\star_{a,i} would then have a single nonzero entry on this constant coordinate.
  4. Moreover, regarding the experiments, I wonder how the sparse estimator and the corruption-aware widths behave when n≤dn \le d.

    • Appendix E.2 states that the RSC tolerance is essential when n<dn<d, and Appendix E.7 notes that the sufficient sample threshold can be smaller than dd.
    • However, with d=20d=20, K=3K=3, and T≥20,000T \ge 20{,}000, the per-action sample size likely far exceeds dd in the experiments.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.