{"id":"93c6b143-94fd-4e00-b3b7-bbf1e061c20b","arxiv_id":"2505.20010","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Constrained bandit algorithms whose regret depends on the realized losses, split into a safety term and a bandit-learning term, with a matching lower bound.","lead":"This paper gives the first data-dependent (small-loss) regret bounds for multi-armed bandits with constraints, showing the regret can shrink when the optimal strategy is good or lies close to a known safe strategy. It introduces two algorithms and a lower bound proving that the two complexity terms are both necessary.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's proof silently drops an additive K/ρ^6 ln term from Lemma 3; under the stated ρ≥12K/T regime this term can dominate the displayed two-term bound, so Eq. (3) is not established as written.","rationale":"The reader's weakest assumption was the knowledge of a strictly feasible strategy x⋄ and its expected costs θ_i (Assumption 2). That is a real scope limitation, but it is explicitly assumed and standard in hard-constraint settings, so it does not expose a flaw in the main argument. The more load-bearing issue is internal to the proof of the central theorem: the additive K/ρ^6 ln term from Lemma 3 is dropped without justification. Because the theorem allows ρ to be as small as 12K/T, this term is not a constant independent of the instance and can dominate the data-dependent terms in the displayed bound. The rest of the algorithmic construction, including the OMD-with-log-barrier analysis and the lower-bound construction, appears coherent; the lower bound's safety argument is valid once the infeasible-arm construction in ν1 is taken into account. However, the exact two-term upper bound in Eq. (3) is not fully supported as written. Since the reader already returned a CONDITIONAL verdict and this concern is a fixable but non-trivial proof gap rather than a refutation of the qualitative result, the verdict should remain unchanged.","tokens_in":29661,"tokens_out":42843,"duration_ms":465527,"concrete_test":"Re-derive the proof of Theorem 4 while keeping the 55296K ln(KTm/δ)/ρ^6 term from Lemma 3 throughout the quadratic inequality, rather than dropping it. Then instantiate K=3, ρ=36/T, and a loss sequence with ℓ_t^T(x⋄−x*)=ℓ_t^T x*=1/T^2 for every t; evaluate numerically whether the retained K/ρ^6 term exceeds the RHS of Eq. (3). If it does, Theorem 4 requires an additive term or a ρ=Ω(1) condition, and Corollary 1's bound should be rechecked.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 3 (Appendix D.1, Eq. (2)) bounds R⋄ by O((K/ρ)√Σ(ℓ_t^T(x⋄−x*))^2 ln(KTm/δ) + (K/ρ^6)ln(KTm/δ)). In the proof of Theorem 4, the 55296K ln(KTm/δ)/ρ^6 term from the T2 analysis appears on the first displayed line and is then silently absorbed into the eO on the next line; it never appears in the stated bound (3). This matters because the theorem explicitly allows ρ as small as 12K/T. For example, K=3 and ρ=36/T are permitted, giving 1/ρ^6=Θ(T^6). For loss sequences with small Σ(ℓ_t^T(x⋄−x*))^2 and small Σℓ_t^T x*, the dropped term dwarfs both the Safety Complexity and Bandit Complexity terms and cannot be regarded as a universal constant hidden by eO, especially since ρ appears explicitly elsewhere in the bound. Thus the proof as written does not establish the exact two-term data-dependent bound; it establishes at best the same expression plus an additive K/ρ^6 ln(KTm/δ) term. The qualitative claim that data-dependent regret bounds are achievable may survive, but the advertised two-term decomposition, and the tightness comparison in Section 5.3, require either an amended statement or an additional condition such as ρ=Ω(1).","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies multi-armed bandits with adversarial losses, stochastic constraint costs, and both soft and hard constraints. For soft constraints it proposes COLB, an OMD-with-log-barrier algorithm over truncated safe decision sets, and proves a high-probability small-loss regret bound of order O~(sqrt(K * sum_t ell_t^T x*)) with sublinear constraint violations. For hard constraints it proposes SOLB, which mixes the COLB iterate with a known strictly feasible strategy x^diamond using an adaptive combination factor. The main result, Theorem 4, claims a data-dependent regret bound consisting of a Safety Complexity term proportional to sqrt(sum_t (ell_t^T(x^diamond - x*))^2) and a Bandit Complexity term proportional to sqrt(K * sum_t ell_t^T x*). Theorem 5 gives a lower bound showing that both terms are necessary, up to the disclosed open question about the 1/rho factor in the Bandit Complexity term. The paper is a first treatment of data-dependent bounds in constrained MABs and contains detailed appendix proofs for both the soft- and hard-constraint results.","tokens_in":30002,"tokens_out":14245,"duration_ms":140648,"significance":"If Theorem 4 is established as stated, this is a meaningful contribution: it extends data-dependent small-loss bounds to constrained MABs, decomposes the regret into interpretable Safety and Bandit Complexity terms, and supports the decomposition with a lower-bound construction. The paper is careful in disclosing the known 1/rho gap between the upper and lower bounds and in generalizing Assumption 2 to the standard strictly-feasible-strategy assumption. The proof machinery is largely standard OMD/log-barrier analysis adapted to changing safe sets, and the appendix is substantial. However, the proof of the central theorem currently drops an additive term that can dominate in the parameter regime explicitly allowed by the theorem statement, so the exact advertised two-term bound is not established as written. The qualitative finding that data-dependent bounds are achievable in hard-constrained bandits may survive, but the precise statement and the tightness comparison in Section 5.3 need repair.","major_comments":[{"comment":"The proof of Theorem 4 silently drops the additive K/rho^6 ln(KTm/delta) term that appears in Lemma 3. In the first displayed line of the proof, after combining Lemma 3 and Lemma 4, the term 55296 K ln(KTm/delta)/rho^6 is present; on the next line it is absorbed into the eO notation and never appears in the stated bound (3). The theorem's definition of eO says it hides only universal constants and logarithmic terms not depending on delta, and rho appears explicitly elsewhere in the bound, so K/rho^6 is not covered by that convention. Since the theorem allows rho as small as 12K/T, taking for example K=3 and rho=36/T makes the dropped term Theta(T^6), which dominates both displayed terms for loss sequences with small Safety and Bandit Complexity. Thus Eq. (3) is not established as written; the proof establishes at best the same expression plus an additive K/rho^6 ln(KTm/delta) term. Please amend the theorem statement, add a condition such as rho=Omega(1), or give a refined argument that removes the term, and revisit Corollary 1 and Section 5.3 accordingly.","section":null},{"comment":"The final step of the proof also omits additive K/eta and K eta ln(1/delta)/rho terms when solving the quadratic inequality in R_T. When L* = sum_t ell_t^T x* is zero and the Safety Complexity term is also zero, Eq. (3) displays a zero bound, while the proof still leaves an additive term of order K/rho times polylog(T, 1/delta) coming from K/eta with eta = rho/(40 H ln T ln(H/delta)). This term depends on rho and delta and is not covered by the stated eO convention. The exact two-term form in Eq. (3) is therefore stronger than what the proof delivers even after the rho^6 term is addressed. The theorem statement should either include these additive terms explicitly or define a precise convention stating which rho- and delta-dependent additive terms are hidden.","section":null}],"minor_comments":[{"comment":"The lower-bound proof asserts that, to be safe with high probability, any algorithm must satisfy P(forall t: x_t(a3) >= epsilon/(epsilon+rho)) >= 1-delta under instance nu_1. This requirement is plausible and standard for confidence-interval-based safety, but it is stated without derivation from the paper's hard-constraint guarantee (Theorem 3). Please add a short argument showing how the confidence intervals and the Slater margin force this lower bound on the probability mass on a3.","section":null},{"comment":"The sentence 'SOLB achieves an optimal dependence on both Delta and omega' should be qualified: in the Bandit Complexity term the upper bound has a 1/rho factor while the lower bound does not, and the paper itself leaves removal of this factor as an open question. The claim is currently stated more strongly than what is proved.","section":null},{"comment":"There is a typo in 'optimal-in-hidsight' (should be 'hindsight'). Please also proofread the notation around eO in the abstract and Section 1, where the tilde symbol is repeatedly lost in rendering.","section":null},{"comment":"The definition of the combination factor gamma_t uses the condition E without explicitly recalling that E is evaluated under the clean event of Lemma 1; adding a sentence that the safety guarantee of Theorem 3 is conditional on E(delta) would improve clarity.","section":null}],"recommendation":"major_revision","confidential_remarks":"The paper is a serious contribution and the main idea is interesting. The problem with Theorem 4 is fixable, either by stating the bound with the extra additive K/rho^6 ln term or by restricting the Slater margin to rho=Omega(1), but it is load-bearing because the current proof does not establish the advertised two-term decomposition. Please also ask the authors to check Corollary 1 and the lower-bound comparison after the theorem statement is amended. I see no grounds for rejection if the technical statement is corrected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real contribution—first data-dependent regret bounds for constrained MABs—but the main theorem as printed isn't established. I checked the appendix; the stress-test concern holds up. In the proof of Theorem 4, the 55296 K ln(KTm/δ)/ρ^6 term from Lemma 3 appears on the first displayed line and then disappears into the final eO. That term is not a universal constant: the theorem allows ρ as small as 12K/T, which makes 1/ρ^6 scale like T^6. On sequences where both advertised terms are small, the dropped term dominates and the two-term decomposition is not proven. The qualitative claim that data-dependent bounds are achievable probably survives, but the statement needs amending—either keep the extra term or add a condition like ρ = Ω(1).\n\nWhat's genuinely good: the hard-constraint algorithm SOLB is a clean construction. The adaptive γ_t mixing of the OMD proposal with a known strictly feasible strategy is exactly the right mechanism for per-round safety, and the Safety Complexity/Bandit Complexity split is a nice way to separate constraint difficulty from bandit learning. The lower bound is intricate: a four-instance construction with KL control and the forced play of the safe action gives the Δ/ρ√T term. That is substantive, careful work.\n\nSoft spots, in proportion. First, the omitted ρ^6 term is load-bearing for the exact statement but likely repairable—requiring ρ bounded below by a constant makes the extra term absorbable and preserves the qualitative message. Second, the soft-constraint result, Theorem 2, is essentially Lee et al.'s OMD-with-log-barrier analysis applied to a safe decision set; the paper is honest about this, but the novelty there is limited. Third, the lower-bound proof has some compressed steps, particularly the transfer from stochastic instances to a fixed adversarial sequence in B_{ω,Δ,T}; the argument is sound in spirit but needs careful reading. Assumption 2 (knowing a strictly feasible strategy and its expected costs) is standard in this literature, not a flaw.\n\nRead this if you work on safe/constrained bandits or small-loss bounds. It should go out to serious referees. The referee should require the authors to fix Theorem 4—by adding the K/ρ^6 term to the bound or by stating the ρ≥Ω(1) regime—before the central claims are taken at face value.","headline":"Genuinely new and worth refereeing, but Theorem 4 as stated is not proven: the proof silently drops a K/ρ^6 term that can dominate the advertised bound unless ρ is bounded below by a constant.","tokens_in":30502,"tokens_out":3823,"would_cite":false,"duration_ms":42635,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that constrained multi-armed bandits with hard per-round constraints admit data-dependent regret bounds, split into a Safety Complexity term and a Bandit Complexity term, with a matching lower bound.","keywords":["constrained multi-armed bandits","hard constraints","data-dependent regret bounds","small-loss bounds","safe exploration","log-barrier OMD","adversarial losses","stochastic constraints"],"falsifier":"Simulate the four stochastic instances constructed in the proof of Theorem 5 with $K=3$, $T=10^4$, $\\rho=0.1$, $\\omega=0.1$, and $\\Delta=0.1$: on the worse of instances $\\nu_2$ and $\\nu_3$, any randomized algorithm's average regret should be at least the claimed $\\Omega(\\Delta\\sqrt{T}/\\rho+\\sqrt{\\omega T})$ lower bound; falling below falsifies the lower bound, while SOLB exceeding the right-hand side of Equation (3) at confidence level $1-5\\delta$ falsifies the upper bound.","tokens_in":29506,"feed_emoji":"🎰","tokens_out":13451,"duration_ms":110653,"temperature":0.7,"pith_summary":"Constrained multi-armed bandits with hard constraints—where every round's decision must satisfy stochastic resource constraints with high probability—have so far been analyzed only through worst-case $\\widetilde{O}(\\sqrt{T})$ regret bounds. This paper asks whether regret can instead depend on the actual loss sequence, and answers yes when losses are adversarial and constraints are stochastic. Its algorithm, SOLB, achieves high-probability regret roughly $\\frac{K\\ln(1/\\delta)}{\\rho}\\sqrt{\\sum_{t=1}^T(\\ell_t^\\top(x^\\diamond-x^*))^2}+\\frac{1}{\\rho}\\sqrt{K\\sum_{t=1}^T\\ell_t^\\top x^*\\ln(1/\\delta)}$, where $x^*$ is the best-in-hindsight feasible strategy and $x^\\diamond$ is a known strictly feasible fallback. The first term, Safety Complexity, measures how far the fallback is from the optimum in loss space, while the second, Bandit Complexity, recovers the unconstrained small-loss rate; a lower bound shows both are inherent. If correct, regret on easy instances can be far below $\\sqrt{T}$ while remaining equivalent to it in the worst case.","feed_headline":"Hard constraints need not cost √T regret","feed_subtitle":"A bandit algorithm's regret splits into safety and learning terms that shrink on easy loss sequences.","key_machinery":"The argument rides on a mix-and-project update. Each round, an OMD-with-log-barrier subroutine—online mirror descent with a log-barrier regularizer and action-dependent learning rates that grow when an arm's probability is too small—proposes a strategy $\\tilde{x}_t$ in the truncated safe decision space $\\tilde{S}_t=\\Omega\\cap S_t^\\circ$, where $\\Omega$ is the simplex truncated away from the boundary by $1/T$ and $S_t^\\circ$ relaxes the estimated cost constraints by $K/T$. SOLB does not play $\\tilde{x}_t$ directly; it plays $x_t=\\gamma_{t-1}x^\\diamond+(1-\\gamma_{t-1})\\tilde{x}_t$, with $\\gamma_{t-1}\\in[0,1]$ chosen from pessimistic cost estimates to pull the decision back toward the known strictly feasible $x^\\diamond$ exactly when $\\tilde{x}_t$ might violate a constraint. This identity splits regret into $R_T^\\diamond=\\sum_{t=1}^T\\gamma_{t-1}\\ell_t^\\top(x^\\diamond-x^*)$ plus $\\tilde{R}_T=\\sum_{t=1}^T(1-\\gamma_{t-1})\\ell_t^\\top(\\tilde{x}_t-x^*)$; Lemma 3 controls the first by the squared-loss distance between $x^\\diamond$ and $x^*$, Lemma 4 controls the second through played and optimal losses, and substituting the tuned learning rate yields the two-term bound.","core_discovery":"The central claim is that data-dependent regret is achievable under hard constraints that bind at every round with high probability. With adversarial losses and i.i.d. stochastic constraint costs, SOLB satisfies every constraint at every round with probability at least $1-\\delta$ and, with probability at least $1-5\\delta$, suffers regret $\\widetilde{O}\\big(\\frac{K\\ln(1/\\delta)}{\\rho}\\sqrt{\\sum_{t=1}^T(\\ell_t^\\top(x^\\diamond-x^*))^2}+\\frac{1}{\\rho}\\sqrt{K\\sum_{t=1}^T\\ell_t^\\top x^*\\ln(1/\\delta)}\\big)$. The Safety Complexity term vanishes when the optimal strategy is essentially the known safe fallback, and the Bandit Complexity term mirrors the small-loss lower bound of unconstrained adversarial bandits up to a $1/\\rho$ factor. The matching lower bound over the constrained small-loss balls $B_{\\omega,\\Delta,T}$ shows that no algorithm can generally drop either dependence, so the two-term decomposition reflects the problem's structure rather than an artifact of the proof.","pith_inferences":["Editorial extension: the Safety Complexity term depends on the chosen fallback $x^\\diamond$, so a learner with several known feasible strategies could plausibly reduce regret by selecting the fallback that minimizes $\\sum_{t=1}^T(\\ell_t^\\top(x^\\diamond-x^*))^2$; the paper does not explore this selection problem.","Editorial extension: the paper leaves open whether the $1/\\rho$ factor in Bandit Complexity can be removed; if a modified learning-rate schedule achieved that, hard constraints would pay only in the Safety Complexity term, which is what one might expect from the constraint layer alone.","Editorial extension: the $\\gamma_t$-mixing construction transfers naturally to constrained linear bandits or constrained MDPs with a known safe policy, where the safe policy plays the role of $x^\\diamond$; testing SOLB-style mixing there would extend the paper's scope.","Editorial extension: the constrained small-loss-ball parametrization by $(\\omega,\\Delta)$ offers a two-dimensional instance-complexity measure that could serve as a common yardstick for future safe online-learning algorithms."],"forward_implications":["In the best case—near-zero optimal loss or $x^*\\approx x^\\diamond$—the bound collapses toward the unconstrained small-loss rate, far below the $\\widetilde{O}(\\sqrt{T})$ typical of hard-constraint algorithms.","In the worst case, where both data-dependent sums scale linearly with $T$, the bound recovers the $\\widetilde{O}(\\sqrt{T})$-scale of prior hard-constraint results while exposing its two sources.","The lower bound tells algorithm designers that no method can make do with only one of the two terms: both the squared-loss gap to the fallback and the optimal cumulative loss are intrinsic to the problem.","Because the guarantee holds with high probability rather than only in expectation, the algorithm is usable in settings where rare constraint violations are unacceptable.","The soft-constraint warm-up delivers high-probability small-loss regret with sublinear cumulative violations, so the technique also applies when per-round safety is not required."],"supporting_citations":[{"why":"It supplies the OMD-with-log-barrier method and its high-probability data-dependent regret analysis, which COLB and SOLB adapt to constrained decision spaces.","marker":"[Lee et al., 2020a]"},{"why":"It establishes the hard-constraint MAB formulation and the prior $\\widetilde{O}(1/\\rho\\sqrt{T})$ guarantee that Theorem 4 decomposes and improves.","marker":"[Pacchiano et al., 2021]"},{"why":"It provides the safe-decision-space and known-strictly-feasible-strategy conventions behind Assumptions 1 and 2, along with the lower bound that COLB's violation rate matches.","marker":"[Bernasconi et al., 2022]"},{"why":"Its impossibility result forces the paper's setting of adversarial losses with stochastic constraint costs.","marker":"[Mannor et al., 2009]"},{"why":"It gives the unconstrained adversarial-bandit lower bound that the Bandit Complexity term mirrors, and its KL-decomposition lemma is used in Theorem 5.","marker":"[Gerchinovitz and Lattimore, 2016]"},{"why":"It supplies the standard bandit lower-bound tool, Lemma A.1, used to relate expectations across the four instances in the proof of Theorem 5.","marker":"[Auer et al., 2002]"},{"why":"It supplies the martingale concentration lemma, Lemma 9, used to bound the squared confidence-width sums inside the proof of Lemma 3.","marker":"[Jin et al., 2020]"},{"why":"It gives the $\\chi^2$-divergence bound used to control the KL divergences between the Bernoulli instances in the lower-bound proof.","marker":"[Tsybakov, 2008]"}],"fun_headline_variants":["Data-dependent regret achieved under hard constraints","Hard constraints don't force worst-case regret","Safety and learning terms split bandit regret","Adaptive regret for constrained MABs on easy losses"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The per-round safety guarantee and the two-term regret bound both presuppose that the learner is handed a strictly feasible strategy $x^\\diamond$ together with its exact expected constraint costs $\\theta_i$ and the resulting margin $\\rho>0$; if that fallback or its exact costs are unavailable, the algorithm has no anchor to mix toward and the theorem's guarantees do not apply.","fun_headline_variants_meta":{"raw":{"variants":["Data-dependent regret achieved under hard constraints","Hard constraints don't force worst-case regret","Safety and learning terms split bandit regret","Adaptive regret for constrained MABs on easy losses"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0002,"raw_usage":{"total_tokens":1399,"prompt_tokens":993,"completion_tokens":406,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":609,"completion_tokens_details":{"reasoning_tokens":349}},"tokens_in":609,"tokens_out":406,"duration_ms":4918,"temperature":1.0,"reasoning_tokens":349,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:03:00.663031+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the four stochastic instances constructed in the proof of Theorem 5 with $K=3$, $T=10^4$, $\\rho=0.1$, $\\omega=0.1$, and $\\Delta=0.1$: on the worse of instances $\\nu_2$ and $\\nu_3$, any randomized algorithm's average regret should be at least the claimed $\\Omega(\\Delta\\sqrt{T}/\\rho+\\sqrt{\\omega T})$ lower bound; falling below falsifies the lower bound, while SOLB exceeding the right-hand side of Equation (3) at confidence level $1-5\\delta$ falsifies the upper bound.","supporting_citations":[],"review_version":1}