{"id":"a1d20504-15b0-44ee-a616-959c58db68f3","arxiv_id":"1908.05814","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A new two-phase UCB algorithm, Safe-LUCB, achieves Õ(√T) regret with a known positive safety gap and Õ(T^{2/3}) regret in the worst case, while keeping every action safe with high probability.","lead":"Safe-LUCB is a bandit algorithm that respects a safety constraint at every round while learning which actions are safe. It proves regret grows like the square root of time when the best safe action has positive slack, and like time to the two-thirds power when it sits on the safety boundary.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3's truncation of Term I at 2 is unjustified: Term I can exceed 2 when Term II is negative, yet both main regret theorems rely on this bound.","rationale":"The reader's verdict is CONDITIONAL, and our stress-test supports that: the most load-bearing defect is in the proof of Lemma 3, not in the uniform-sampling oracle. The reader's stated weakest_assumption concerns the existence of a uniform sampler over D_w and the eigenvalue lower bound λ−; while that is a legitimate practical limitation, it is an oracle assumption that, if granted, does not break the proof. The invalid truncation at (20) is an internal logical gap that affects the proof of both Theorem 2 and Theorem 3 as written. We constructed a parameter setting satisfying Assumptions 1–3 where Term I exceeds 2 while instantaneous regret stays within the trivial bound, demonstrating that the step 'Term I ≤ 2 min(β‖x‖,1)' does not follow from (19) and r_t ≤ 2. This is exactly the sort of issue the stress-test should flag: it is concrete, located precisely (Appendix B.2, equations (19)–(20)), and directly undermines the central claim unless repaired. The gap appears repairable via standard elliptic-potential arguments or by decomposing Term I = r_t − Term II and using a bound on the negative part of Term II; therefore we do not escalate the verdict to REJECT. Since the reader already recommended CONDITIONAL for essentially this reason, our read does not change the verdict.","tokens_in":20262,"tokens_out":24618,"duration_ms":228879,"concrete_test":"Construct the 2D instance above with D0=[−1,1]^2, B=diag(1,ε) for ε=0.01, µ=(0,1), c=0.5. Choose T′≥tδ as in Lemma 1 and any t>T′; set A_t = λI + Σ_{τ=1}^{t−1} x_τ x_τ† and β_t by (7). Run the optimization in Algorithm 1, Step 10 to compute x_t and µ̃_t. Compute Term I = µ†x_t − µ̃_t†x_t and r_t = µ†x_t − µ†x*. If Term I > 2 while r_t ≤ 2, inequality (20) is false, confirming the proof gap. To test repairability, independently re-derive the cumulative bound on ∑Term I using only (19), the decomposition r_t = Term I + Term II, and the existing Lemma 5 bound on Term II; if this yields O(√T log T), the theorem may be salvageable with a modified proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central regret bounds (Theorems 2 and 3) both rely on Lemma 3 in Appendix B.2, which bounds the cumulative contribution of Term I = µ†x_t − µ̃_t†x_t. Inequality (19) gives Term I ≤ 2β_t‖x_t‖_{A_t^{-1}}. The proof then invokes Assumption 2's trivial bound r_t ≤ 2 and concludes Term I ≤ 2 min(β_t‖x_t‖_{A_t^{-1}}, 1) in (20). This step is logically invalid: r_t = Term I + Term II, and Term II can be negative when the optimistic pair (µ̃_t, x_t) achieves a cost below the true optimum (this is exactly the 'regret of safety' scenario the paper discusses). Hence Term I can be much larger than 2 even when r_t ≤ 2. A concrete instance: take d=2, D0=[−1,1]^2, B=diag(1,0.01), µ=(0,1), c=0.5. With a confidence set of radius β/√λ_min ≈ 5, the safe set D^s_t contains x=(0,1), and the minimizer in (9) gives µ̃†x_t ≈ −9, so Term I = 10 while r_t = 2. Under the theorem's parameter choices (e.g., d large, β_T/√λ_min(A_{T'+1}) ≫ 1), this is not a contrived edge case. Because Lemma 3's bound is used directly to control ∑Term I in the proofs of both theorems, the stated regret guarantees do not follow from the written argument without an additional argument that either bounds Term I differently or splits the regret decomposition with the negative part of Term II.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a linear stochastic bandit in which, in addition to minimizing cumulative pseudo-regret, the learner must choose every action so that a linear safety constraint µ†Bx≤c is satisfied, with B and c known but µ unknown. The authors propose Safe-LUCB, a two-phase algorithm: a pure-exploration phase samples actions uniformly from a conservative safe subset Dw in order to guarantee a lower bound on the minimum eigenvalue of the Gram matrix, and a subsequent safe exploration-exploitation phase uses optimism over confidence sets while restricting actions to an estimated safe set. The main results are a problem-dependent regret bound of Õ(√T) when the safety gap Δ=c−µ†Bx* is positive and known, a worst-case Õ(T^{2/3}) bound when Δ=0, and a heuristic extension (GSLUCB) for unknown Δ with simulations.","tokens_in":20596,"tokens_out":20128,"duration_ms":206417,"significance":"The formulation is natural and the safety-gap dichotomy is an insightful contribution: it cleanly separates the regime in which the optimal action can be included in the estimated safe set from the regime in which a residual 'regret of safety' must be paid. The paper also correctly emphasizes the distinction between stage-wise safety constraints and cumulative budget constraints, and it identifies a gap in prior safe Bayesian-optimization work, which provides convergence guarantees but not regret bounds. The two-phase design and the use of the Gram-matrix lower bound to learn the safe set are conceptually clean, and the appendix gives explicit constants and fairly detailed proofs. If the proof gap described below is repaired, this would be a solid first regret analysis for stage-wise safe linear bandits.","major_comments":[{"comment":"The step 'Recall, from Assumption 2, the trivial bound on the instantaneous regret r_t≤2. Thus, Term I≤2 min(β_t‖x_t‖_{A_t^{-1}},1)' is not justified. Since r_t = Term I + Term II and Term II = µ̃_t†x_t−µ†x* can be negative (the optimistic cost estimate can make the chosen action look much better than the true optimal cost), a bound on r_t does not bound Term I. In fact, Term I can exceed 2 even when r_t is small. Inequality (20) is then used in the proof of Lemma 3 to obtain the cumulative Term I bound in Eq. (21), and that cumulative bound is combined with Lemma 4 or Lemma 5 in Appendices B.4 and B.5 to prove Theorems 2 and 3. Thus the written proof of the main regret guarantees does not go through. The gap appears repairable—for example, by bounding r_t directly with a standard OFU argument rather than bounding Term I through the min-cap—but the current derivation is invalid.","section":"B.2, Eq. (20); Lemma 3; Theorems 2 and 3"},{"comment":"The pure-exploration phase is specified only through the instruction 'Randomly choose x_t∈D_w', with an explicit sampling construction in Remark 1 available only when B is invertible. For a general convex body D0 and a general matrix B, the proof of Lemma 1 requires independent exact uniform samples from Dw and the positivity of λmin(E[XX†]); while Assumption 3 does ensure that Dw has nonempty interior and hence that the covariance is full rank, the paper does not state the computational model under which such samples are available. Please state explicitly that an exact uniform sampling oracle over Dw is assumed, or provide an implementable sampling procedure for the general case. This is a clarity/scope issue rather than a mathematical contradiction, but it affects the algorithmic claim made by Theorem 2 and Theorem 3.","section":"2.2, Algorithm 1, and Remark 1"}],"minor_comments":[{"comment":"The statement of Lemma 2 gives probability at least 1−δ, while the appendix version (Lemma 4) gives probability at least 1−2δ after union-bounding the confidence event and the Gram-matrix event; please harmonize these statements and spell out the union bound.","section":"3.3, Lemma 2"},{"comment":"The sentence 'This is done in Figures 2a and 3c' appears to cite the wrong figure: the safe-set plots are in Figure 2, whereas Figure 3 shows average regret curves.","section":"F"},{"comment":"In the paragraph defining the shrunk safe set, 'compared to the original ~D_s_t' should read 'compared to the original D_s_t', and in Eq. (24) the text uses 'C>0' where the constant is denoted c elsewhere.","section":"B.3"},{"comment":"The phrase 'cumulant regret' is used in a few places and should be 'cumulative regret'.","section":"3.3"},{"comment":"The displayed definition of Δ_i^t is garbled; please rewrite it so that the constraint 'v†y_i ≤ v†y for all y∈Y_i^t' is clearly separated from the minimization over v.","section":"E, Eq. (45)"}],"recommendation":"major_revision","confidential_remarks":"The main concern is the invalid step in Eq. (20), which is load-bearing for the regret proofs. I believe the results are likely salvageable with a direct OFU-style bound on r_t, so I recommend major revision rather than rejection. Please also ask the authors to clarify the sampling oracle for the pure-exploration phase and to fix the small probability-level inconsistency between Lemma 2 and Lemma 4."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is the right problem, the safety-gap idea is good, and the two-phase algorithm is sensible—but the proof as written has a real hole in Lemma 3, and both main theorems lean on it. I would not desk-reject this; I would send it back with a request to fix that lemma.\n\nThe formulation is genuinely new as far as I know: a linear bandit where each action must satisfy a per-round constraint µ'Bx ≤ c with unknown µ. The related work on cumulative/budget constraints [14,15] doesn't cover this. Safe-LUCB is a natural extension of LUCB, and the decomposition of instantaneous regret into Term I and the 'regret of safety' Term II is the right way to see the problem. The safety gap Δ = c - µ'Bx* is a clean complexity parameter: positive known Δ gives Õ(√T), zero Δ gives Õ(T^{2/3}). The analysis of Term II via the shrunk safe set and α_t is careful and convincing.\n\nThe soft spot is exactly where the stress-test note puts it. Lemma 3 claims Term I ≤ 2 min(β_t ||x_t||, 1). The first inequality Term I ≤ 2β_t||x_t|| is fine from the confidence set. But the min with 1 is justified by 'r_t ≤ 2', and Term I is not r_t. Term II can be negative when the optimistic pair is overly favorable, so Term I can be much larger than 2 while r_t stays small. The d=2 example in the stress-test is legitimate: it's not contrived. Both Theorems 2 and 3 use Lemma 3 directly, so the printed regret bounds do not follow from the written proof.\n\nThat said, I think the gap is repairable. For the positive-gap case, Term II ≤ 0 once the exploration phase is long enough, so r_t ≤ Term I ≤ 2β||x_t|| and also r_t ≤ 2; then the same elliptic-potential argument bounds ∑ r_t directly, which is what the theorem actually needs. For the zero-gap case you can bound r_t ≤ 2β||x_t|| + Term II and handle the two terms with standard arguments; the third term in Theorem 3 already captures the safety cost. So the central claims are likely true, but they need a corrected lemma, not just a typo.\n\nMinor issue: the pure-exploration phase assumes a uniform sampler over the convex body D_w and a positive minimum eigenvalue of the resulting covariance. For general B that's an oracle; Remark 1 only gives an explicit sampler when B is invertible. That's worth stating as an assumption or a limitation, not a fatal flaw.\n\nBottom line: this deserves a serious referee. The formulation and the safety-gap notion will be cited; the proof needs work. If I were running the review I'd ask for a revised Lemma 3 and a clearer statement about the sampling oracle, then it could be a solid contribution.","headline":"A genuinely new problem formulation and a useful safety-gap analysis, but the proof of Lemma 3 contains a real gap that both regret theorems rely on; the paper is worth engaging with because the fix looks standard.","tokens_in":21151,"tokens_out":10405,"would_cite":true,"duration_ms":95214,"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":"The paper establishes that Safe-LUCB, a two-phase optimistic algorithm, achieves $\\widetilde{O}(\\sqrt{T})$ cumulative regret in linear stochastic bandits with an unknown linear safety constraint whenever the optimal safe action has…","keywords":["linear stochastic bandits","safety constraints","Safe-LUCB","optimism in the face of uncertainty","regret bounds","safe set estimation","pure exploration","confidence ellipsoid"],"falsifier":"A concrete test: choose $\\mathcal{D}_0 = \\{x : \\|x\\|_\\infty \\le 1\\}$, take $B$ singular with a one-dimensional null space along which the constraint is uninformative, and use any practical sampler over $\\mathcal{D}_w$; measure $\\lambda_{\\min}(A_{T'+1})$ for growing $T'$. If it stays near $\\lambda$ instead of growing linearly at rate $\\lambda_-/2$, the eigenvalue lemma underpinning both regret theorems is violated for that sampling choice.","tokens_in":20020,"feed_emoji":"🛡️","tokens_out":8293,"duration_ms":78839,"temperature":0.7,"pith_summary":"This paper introduces a linear stochastic bandit problem in which every chosen action must satisfy a linear safety constraint $\\mu^\\dagger Bx \\le c$ whose parameter vector $\\mu$ is unknown. It proposes Safe-LUCB, a two-phase UCB algorithm that first samples actions uniformly from a conservative inner safe set to estimate $\\mu$, then runs optimism-based safe exploration and exploitation using confidence-region safe sets. The paper's central claim is that the difficulty of the problem is governed by the safety gap $\\Delta = c - \\mu^\\dagger Bx^*$, the slack of the optimal safe action. If $\\Delta > 0$ and a lower bound on it is known, a logarithmic pure-exploration phase suffices and the cumulative regret is $\\widetilde{O}(\\sqrt{T})$, the same order as unconstrained linear bandits; if $\\Delta = 0$, the regret is $\\widetilde{O}(T^{2/3})$. Every played action is safe with probability at least $1-2\\delta$, and the analysis isolates the extra cost, the \"regret of safety,\" paid while the learner's safe set is still a conservative approximation.","feed_headline":"Safe bandit algorithm hits √T regret under unknown safety constraints","feed_subtitle":"A two-phase UCB method learns the safe action set and matches unconstrained linear bandits when the optimum has slack.","key_machinery":"The load-bearing object is the randomized pure-exploration phase over the conservative safe set $\\mathcal{D}_w = \\{x \\in \\mathcal{D}_0 : \\|Bx\\| \\le c/S\\}$. Its covariance $\\Sigma = \\mathbb{E}[XX^\\dagger]$ has minimum eigenvalue $\\lambda_-$, and the Matrix Chernoff inequality converts $T'$ independent uniform draws into the Gram-matrix lower bound $\\lambda_{\\min}(A_{T'+1}) \\ge \\lambda + \\lambda_- T'/2$. That bound is what shrinks the confidence ellipsoid enough for the estimated safe set $\\mathcal{D}^s_t$ to contain $x^*$ when $\\Delta > 0$, and it also controls the regret-of-safety term in the zero-gap case.","core_discovery":"The central discovery is a reduction of the safety problem to control of the weighted norm $\\|Bx^*\\|_{A_t^{-1}}$ through forced random exploration. Safe-LUCB builds a confidence ellipsoid $\\mathcal{C}_t$ around its least-squares estimate $\\hat{\\mu}_t$ and defines the safe decision set $\\mathcal{D}^s_t = \\{x \\in \\mathcal{D}_0 : v^\\dagger Bx \\le c \\text{ for all } v \\in \\mathcal{C}_t\\}$. Because $\\mathcal{D}^s_t$ is a conservative inner approximation of the true safe set, the optimal safe action $x^*$ may lie outside it; the paper isolates the resulting extra regret as Term II and shows it is nonpositive once $\\|Bx^*\\|_{A_t^{-1}} \\le \\Delta/(2\\beta_t)$. The pure-exploration phase guarantees this by making $\\lambda_{\\min}(A_{T'+1}) \\ge \\lambda + \\lambda_- T'/2$ with high probability, so that for $\\Delta > 0$ a phase length of order $\\log T$ puts $x^*$ inside $\\mathcal{D}^s_t$ for every later round. With that, the regret analysis reduces to the standard UCB term and yields $\\widetilde{O}(\\sqrt{T})$; without a positive gap, the best bound is $\\widetilde{O}(T^{2/3})$.","pith_inferences":["Beyond the paper: the $1/\\Delta^2$ dependence of $T_\\Delta$ suggests that for small positive gaps the practical difficulty may be closer to the $\\Delta = 0$ case; an adaptive stopping rule based on the weighted norm $\\|Bx^*\\|_{A_t^{-1}}$ could make the $\\sqrt{T}$ bound available without knowing $\\Delta$ in advance.","Beyond the paper: replacing the uniform sampler on $\\mathcal{D}_w$ with a fixed full-rank design, such as a G-optimal or D-optimal design, would likely preserve Lemma 1 for singular $B$, since the proof only needs independent samples whose covariance has $\\lambda_- > 0$.","Beyond the paper: the zero-gap case is where a matching lower bound is most likely; if $\\Omega(T^{2/3})$ were proved, Safe-LUCB would be rate-optimal for the full problem rather than only for the positive-gap regime.","Beyond the paper: the same two-phase template may transfer to multiple linear safety constraints, with the safety gap replaced by a vector of slacks and the eigenvalue lower bound controlling a sum of weighted norms."],"forward_implications":["With a known positive safety gap, Safe-LUCB's cumulative regret is $\\widetilde{O}(\\sqrt{T})$ (Theorem 2), so the safety constraint, once learned, does not change the asymptotic rate.","When the gap is zero or unknown, the worst-case guarantee is $\\widetilde{O}(T^{2/3})$ (Theorem 3), still sublinear, so average regret $R_T/T$ vanishes.","The pure-exploration phase must last $T_\\Delta$ of order $\\log T$ for $\\Delta > 0$, and $T_\\Delta$ grows like $1/\\Delta^2$, so problems with small slack require substantially more forced exploration.","With probability at least $1-2\\delta$, every action selected by Safe-LUCB satisfies the safety constraint $\\mu^\\dagger Bx_t \\le c$.","In the $K$-armed contextual extension, the same algorithm achieves $\\widetilde{O}(\\sqrt{T})$ regret when each round's safety gap is strictly positive."],"supporting_citations":[{"why":"Supplies the confidence ellipsoid $\\mathcal{C}_t$ and Theorem 1 guaranteeing $\\mu \\in \\mathcal{C}_t$ with probability $1-\\delta$, the backbone of the OFU safe-set construction.","marker":"[2]"},{"why":"Provides the standard LUCB regret decomposition and the determinant argument used to bound Term I over the exploration-exploitation phase.","marker":"[1]"},{"why":"Supplies the Matrix Chernoff inequality used to prove the Gram-matrix lower bound $\\lambda_{\\min}(A_{T'+1}) \\ge \\lambda + \\lambda_- T'/2$ in Lemma 1.","marker":"[28]"},{"why":"The closest prior stage-wise safe bandit model; the positive-gap assumption is reminiscent of its baseline-slack condition and serves as the comparison point for the safety constraint formulation.","marker":"[14]"},{"why":"Provides lower bounds showing that the $\\sqrt{T}$ rate cannot be improved even without safety, justifying the claim that Theorem 2 is optimal up to logarithmic factors.","marker":"[3]"}],"fun_headline_variants":["Safe-LUCB: √T regret for linear bandits with safety","Two-phase safe bandit removes regret gap when slack exists","Learn safe actions conservatively, then exploit for √T","Safe bandit matches unconstrained regret with unknown constraints","Random exploration guarantees safe set, then UCB to √T"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument stands or falls on the pure-exploration phase's ability to draw independent actions from the conservative safe set whose action covariance has a strictly positive minimum eigenvalue ($\\lambda_- > 0$), an ability the paper assumes rather than constructs for general matrices $B$.","fun_headline_variants_meta":{"raw":{"variants":["Safe-LUCB: √T regret for linear bandits with safety","Two-phase safe bandit removes regret gap when slack exists","Learn safe actions conservatively, then exploit for √T","Safe bandit matches unconstrained regret with unknown constraints","Random exploration guarantees safe set, then UCB to √T"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000347,"raw_usage":{"total_tokens":1955,"prompt_tokens":1052,"completion_tokens":903,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":668,"completion_tokens_details":{"reasoning_tokens":819}},"tokens_in":668,"tokens_out":903,"duration_ms":9176,"temperature":1.0,"reasoning_tokens":819,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:07:51.308391+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete test: choose $\\mathcal{D}_0 = \\{x : \\|x\\|_\\infty \\le 1\\}$, take $B$ singular with a one-dimensional null space along which the constraint is uninformative, and use any practical sampler over $\\mathcal{D}_w$; measure $\\lambda_{\\min}(A_{T'+1})$ for growing $T'$. If it stays near $\\lambda$ instead of growing linearly at rate $\\lambda_-/2$, the eigenvalue lemma underpinning both regret theorems is violated for that sampling choice.","supporting_citations":[{"cited_title":"distance","cited_arxiv_id":null,"evidence_quote":"Supplies the Matrix Chernoff inequality used to prove the Gram-matrix lower bound $\\lambda_{\\min}(A_{T'+1}) \\ge \\lambda + \\lambda_- T'/2$ in Lemma 1."},{"cited_title":"Conserva- tive contextual linear bandits","cited_arxiv_id":null,"evidence_quote":"The closest prior stage-wise safe bandit model; the positive-gap assumption is reminiscent of its baseline-slack condition and serves as the comparison point for the safety constraint formulation."},{"cited_title":"Tsitsiklis","cited_arxiv_id":null,"evidence_quote":"Provides lower bounds showing that the $\\sqrt{T}$ rate cannot be improved even without safety, justifying the claim that Theorem 2 is optimal up to logarithmic factors."}],"review_version":1}