{"id":"7336104b-b4de-43df-9f0c-b24165389194","arxiv_id":"2502.08259","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"OTO balances lower-confidence-bound and upper-confidence-bound play in offline-to-online bandits and matches the better of the two in regret, up to log factors and an additive budget term.","lead":"The paper introduces OTO, a bandit algorithm that switches between a pessimistic LCB policy and an optimistic UCB policy using an exploration budget, and proves regret bounds matching the better of the two at every horizon. It matters because offline-to-online systems face exactly this short-horizon versus long-horizon trade-off, and OTO gives a principled automatic balance instead of a hand-picked switch.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's pointwise claim is false: the proof only bounds the final horizon, and the (T−t)αβ term in the budget lets OTO take an early bad pull that violates Eq. (2).","rationale":"The reader's verdict correctly notes a mismatch between the abstract's 'at any point in time' claim and the theorem's qualification, and the reader's weakest assumption about random offline counts is a real but secondary issue. However, the load-bearing defect is more specific and more severe: the proof of Eq. (2) is a final-horizon argument. The pseudo-budget is shown to be nonnegative at time T, and the simplification that removes the (T−t)αβ term is only valid at t=T. For intermediate t, the same algebra leaves an extra (T−t)αβ term, which is generally large enough to change the algorithm's early decisions. The explicit instance above satisfies all formal conditions of Theorem 1 (both arms have positive offline counts, means in [0,1], 1-subgaussian distributions, δ chosen so the high-probability event has probability at least 1−1/T). At t=1 the budget is positive solely because of the future (T−1)αβ projection, so OTO plays the bad arm 2, incurring logging regret ≈0.5, while the theorem promises ≈0.116. This is a direct counterexample, not a gap in a limiting regime. The paper's experimental claim that OTO explores unsampled arms is consistent with this behavior, but Theorem 1 as stated is not. The verdict should therefore be REJECT rather than CONDITIONAL: the central pointwise guarantee is false, and no parameter tuning within the stated theorem removes the early-time violation without also changing the algorithm or the theorem statement.","tokens_in":29536,"tokens_out":48442,"duration_ms":498932,"concrete_test":"Instantiate K=2, m1=10^4, m2=1, μ1=0.5, μ2=0, T=2000, α=1, δ=1/(2T^2), and step through Algorithm 1 at t=1 with the prescribed confidence bounds. If OTO pulls arm 2 (as the budget computation predicts), then Rlog(1)=10000/10001≈0.5 exceeds the claimed bound (1+α)β≈0.116, falsifying Eq. (2). Alternatively, analytically check the intermediate-time version of the proof: the pseudo-budget argument yields Rlog(t) ≤ t(1+α)β + (T−t)αβ, so Eq. (2) cannot follow for t<T unless the extra term is shown to vanish.","verdict_should_be":"REJECT","load_bearing_attack":"Section 7 proves Eq. (2) only at the final time T: it uses positivity of the pseudo-budget \\tilde B_{\\tilde T}(T) and then sets \\tilde T=T, so the term (T−t)αβ vanishes. The theorem, however, asserts the bound for every 1≤t≤T. Repeating the proof at an intermediate t gives Rlog(t) ≤ t(1+α)β + (T−t)αβ, not t(1+α)β. The missing (T−t)αβ is not harmless: it is exactly the term that makes the budget at early rounds positive. Concrete instance: K=2, m1=10^4, m2=1, μ1=0.5, μ2=0, T=2000, α=1, δ=1/(2T^2). At t=1, \\bar μ_2≈2.88 > \\bar μ_1≈0.53, so U(1)=2; \\underline μ_2(1)=−2.88, γ≈0.41, and B_T(1)=(\\underline μ_2−γ)+(T−1)αβ≈−3.3+116.3>0, so OTO pulls the bad arm 2. Rlog(1)≈0.5, while Eq. (2) gives (1+α)β≈0.116. All concentration events of Lemma 1 hold with probability 1−1/T≈0.9995, so the violation is not a failure of the confidence-bound event. Thus the central 'at any point in time' guarantee is not merely unproved for intermediate t; it is false as stated. A repair would require either proving a horizon-dependent additive term in Eq. (2) or changing the budget to not anticipate future LCB budget when deciding current exploration.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies offline-to-online learning in stochastic multi-armed bandits, where a learner has fixed offline sample counts per arm and then interacts online for a horizon T. It introduces an algorithm, OTO, that switches between a Lower Confidence Bound (LCB) arm and an Upper Confidence Bound (UCB) arm according to a budget that accumulates when LCB is played. The central claimed result, Theorem 1, is that for every time 1 ≤ t ≤ T, OTO achieves, with high probability, a bound on regret against the logging policy comparable to LCB's bound and bounds on regret against the optimal arm comparable to UCB's bounds. The paper also analyzes the regret of UCB and LCB in this setting, and reports synthetic and real-data experiments. The overall goal is to show that OTO automatically interpolates between pessimism and optimism across the offline-to-online spectrum.","tokens_in":29921,"tokens_out":27223,"duration_ms":269273,"significance":"The problem is well motivated and the paper contains useful components: a careful comparison of UCB and LCB under both the logging-policy regret and the optimality regret, a detailed appendix with proofs, and reproducible experimental code. If the anytime guarantee of Theorem 1 were correct, the budget-based interpolation idea would be a valuable contribution to the offline-to-online bandit literature. However, the headline anytime bound on logging regret is false as stated, and the failure is not merely a missing constant in the proof but a consequence of the budget anticipating future LCB plays. This undermines the abstract's central claim, although the final-time bounds and the UCB/LCB analysis may still be salvageable with a modified budget or a weakened theorem.","major_comments":[{"comment":"The claimed pointwise bound Rlog_OTO(t) ≤ t(1 + (1 + 1_{T unknown})α)β for every 1 ≤ t ≤ T is false. The proof in Section 7 only establishes the bound at the final time T: positivity of the pseudo-budget at time T gives (T − T)αβ = 0, which removes the horizon-dependent term. Repeating the same argument at an intermediate t yields Rlog_OTO(t) ≤ t(1 + α)β + (T − t)αβ for the known-horizon case, with an extra (T − t)αβ that does not vanish for t < T. This is not a harmless proof gap: the term (T − t)αβ is exactly what makes the budget positive at early rounds, so the algorithm is allowed to take an early action that violates Eq. (2). A concrete instance is K = 2, m1 = 10^4, m2 = 1, μ1 = 0.5, μ2 = 0, T = 2000, α = 1, δ = 1/(2T^2). For realized offline means such as μhat_1 ≈ 0.5 and μhat_2 ∈ [−2, 2], which occur with probability close to 0.95 under N(0.5,1) and N(0,1) rewards, the concentration inequalities of Lemma 1 hold, yet at t = 1 the budget is positive, OTO pulls arm 2, and Rlog(1) = μ0 ≈ 0.5, while the right-hand side of Eq. (2) is (1 + α)β ≈ 0.116. Thus the theorem's claimed high-probability anytime bound fails on a substantial-probability event, contradicting the stated 1 − 2Tδ guarantee.","section":"Section 7, Theorem 1, Eq. (2)"},{"comment":"The root cause of the pointwise failure is that the budget B_T(t) contains the term (T − t)αβ, which credits the algorithm for LCB plays that have not yet happened but are anticipated by the end of the horizon. This is a non-anticipating violation in the sense that early exploration is justified by future forced LCB plays, so the logging-policy regret at early times can be much larger than the anytime bound claims. A repair should either replace the future term with a term depending only on past LCB plays (e.g., removing (T − t)αβ or using a doubling schedule over the elapsed time), or the main theorem must be weakened to a final-horizon statement. The current abstract and the surrounding text promise an 'at any point in time' guarantee, so this is a load-bearing issue that needs to be resolved before the paper can be accepted.","section":"Section 4, Eq. (1) and Algorithm 1"}],"minor_comments":[{"comment":"The notation for the upper and lower confidence bounds is not consistently rendered: the budget formula and the proof mix ar{\\mu}_i(t) and \\underline{\\mu}_i(t), and the text in Section 4 describes the second term in Eq. (1) as 'a high probability lower bound' although the displayed symbol is ambiguous. Please define both bounds explicitly in Eq. (1) and in Algorithm 1, since the proof's validity depends on which bound appears in the budget.","section":"Section 3 and Eq. (1)"},{"comment":"Several statements use probability 1 − 2T^2δ or an additive 2T^2δ, while Lemma 1 and the union bound in the proofs give 2Tδ. For example, Theorem 3 states probability at least 1 − 2T^2δ, but the proof applies Lemma 1 and a union bound over the two inequalities, yielding 2Tδ. Please align the statement with the proof or explain the additional factor.","section":"Section 5, Theorem 3 and Propositions 1 and 4"},{"comment":"The time-varying δt extension for unknown horizons is presented as a remark without a complete proof. Since Theorem 1 explicitly includes the unknown-horizon case, please either provide a formal proof for δt = δ0/t^2 or clearly label that part as a conjecture or a sketch.","section":"Section 4, Remark 2"},{"comment":"The captions for Figures 5 and 6 include the phrase 'Mean at 78241' (and 'Mean at 78230'), which appears to be a leftover artifact from the experimental log and is not explained in the text. Please remove or explain these values.","section":"Section 6.2, Figures 5 and 6"}],"recommendation":"major_revision","confidential_remarks":"The central anytime guarantee of Theorem 1, Eq. (2), is not merely unproved for intermediate times; it is false on a substantial-probability event for the stated algorithm. This is a correctness issue in the main claim, so I cannot recommend acceptance. I do not recommend rejection because the final-time bound may be recoverable by changing the budget to a non-anticipating form, and the surrounding UCB/LCB analysis and experiments have value. The authors should be asked to either repair the algorithm and theorem or explicitly replace the anytime claim with a final-horizon guarantee; the 'range of parameters m' caveat in Section 4 should also be made precise if the comparison with UCB and LCB is to be claimed as universal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. First, the OTO algorithm and the logging-regret analysis of LCB are genuinely new, and the paper is worth reading. Second, Theorem 1 as stated is false: the \"at any point in time\" guarantee for Rlog does not hold for intermediate t. The proof in Section 7 only works at t=T; repeating it at an intermediate time leaves an extra (T−t)αβ term. The stress-test counterexample is real: at t=1, OTO pulls the bad arm and violates Eq. (2) by a constant factor, all on the confidence event. The budget's future LCB term is the culprit.\n\nWhat's good: the budget mechanism is a nice idea, and the way they separate UCB pulls from LCB pulls to control logging regret is clever. The minimax bounds for UCB and the lower bounds align with Cheung and Lyu (2024), and they cite that work honestly. The proofs are detailed, the code is public, and the experiments on synthetic and Avazu data are sensible, if not extensive.\n\nSoft spots beyond the main theorem: the fixed-offline-counts assumption is explicit but the random-count extension is only conjectured. The unknown-horizon variant is a sketched doubling argument with δt = δ0/t², and they admit it's not fully analyzed. Also, the additive 12K log(K/δ)/(αβ) in Eq. (3) and Eq. (4) is hidden by the abstract's \"nearly as well as\" phrasing, though it is in the theorem.\n\nThe central issue is not a minor gap: the headline anytime guarantee is wrong as written. A repair seems possible—either change the claim to the final horizon, or redefine the budget so it doesn't borrow against future LCB plays when deciding current exploration. But as it stands, the paper overclaims.\n\nThis deserves a serious referee, not a desk reject. The algorithm and analysis framework are worth engaging with, and the flaw is likely fixable. I'd tell the authors to rework Theorem 1 and the abstract. If they fix it, I'd be happy to cite it.","headline":"The OTO algorithm and logging-regret analysis are new and worth reading, but Theorem 1's pointwise anytime guarantee is false as stated.","tokens_in":30453,"tokens_out":4526,"would_cite":false,"duration_ms":43029,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","62L05"],"pacs":[],"model":"deepseek-v4-flash","headline":"One rule matches the best of LCB and UCB in offline-to-online bandits.","keywords":["offline-to-online learning","multi-armed bandits","pessimism and optimism","lower confidence bound","upper confidence bound","regret against logging policy","exploration budget","minimax regret"],"falsifier":"Construct a two-arm instance with $m_1 = m$, $m_2 = 0$, $\\mu_1 = 0.5$, $\\mu_2 = 1$, run OTO with known horizon $T$ and $\\alpha = 1$, and compare its logging-policy regret to the bound $t(1+\\alpha)\\beta$ from Eq. (2). If the empirical regret exceeds that bound by a non-logarithmic factor with high probability, the budget induction in Section 7 is wrong; if OTO ever exceeds both the LCB and UCB regret curves by more than the additive $K$ term, Theorem 1 is violated.","tokens_in":29316,"feed_emoji":"🎰","tokens_out":7237,"duration_ms":67736,"temperature":0.7,"pith_summary":"This paper asks what a learner should do when it inherits offline data and then must interact with the same environment for a known or unknown number of rounds. Short horizons favor the pessimistic Lower Confidence Bound (LCB) algorithm, which stays close to the data-generating policy; long horizons favor the optimistic Upper Confidence Bound (UCB) algorithm, which finds the best arm efficiently. The paper introduces OTO, which plays LCB unless a carefully defined exploration budget proves it can afford UCB's exploration. Its main theorem bounds OTO's regret both against the best arm and against the logging policy, showing that OTO is never much worse than the better of LCB and UCB on either measure, up to logarithmic factors and a tunable budget term. The paper also gives a minimax lower bound for the whole offline-to-online spectrum and shows the same budget idea works when the horizon is unknown via a horizon-doubling proxy.","feed_headline":"One rule matches the best of LCB and UCB in offline-to-online bandits","feed_subtitle":"OTO plays it safe early and explores only once a safety budget proves it can afford the risk.","key_machinery":"The engine is an exploration budget $B_{\\tilde T}(t)$ that accumulates a safe lower bound on how much reward the algorithm has earned and can still earn relative to a benchmark $\\gamma = \\mu_{L(0)}(0) - \\alpha\\beta$, where $L(0)$ is the LCB arm at time zero and $\\alpha$ tunes how strict the budget is. Each play of LCB adds $\\alpha\\beta$ to the budget, while playing UCB charges the budget the gap between UCB's lower confidence value and $\\gamma$; at every round the algorithm plays UCB only if $B_{\\tilde T}(t) > 0$, otherwise it falls back to LCB. The budget is constructed so that the related pseudo-budget stays positive by induction, and this positivity is what converts LCB plays into a guarantee on regret against the logging policy. The bound on regret against optimality then splits into a UCB-style pull-count bound for arms chosen when the budget is high and an LCB-style bound for rounds when the budget is low.","core_discovery":"The central discovery is Theorem 1: for any bandit instance, with probability at least $1 - 2T\\delta$, OTO satisfies $R^{\\mathrm{log}}_{OTO}(t) \\le t(1 + (1 + \\mathbf{1}_{T \\text{ unknown}})\\alpha)\\beta$ and $R_{OTO}(t) \\le \\sum_i \\Delta_i (4\\log(K/\\delta)/\\Delta_i^2 - m_i)_+ + 12K\\log(K/\\delta)/(\\alpha\\beta) + K$, where $\\Delta_i$ is the suboptimality gap, $m_i$ the offline sample count for arm $i$, and $\\beta = (\\sum_i \\sqrt{m_i}/m)\\sqrt{2\\log(K/\\delta)}$ measures the uncertainty in the logging policy's value. Together with a matching minimax lower bound, this says OTO automatically finds the problem-dependent inflection point where optimism overtakes pessimism, keeping the short-horizon safety of LCB without giving up the long-horizon efficiency of UCB. The guarantee holds for both regret against the optimal arm and regret against the logging policy, and it extends to unknown horizons with an extra factor and a time-dependent confidence level.","pith_inferences":["The budget principle is more portable than the specific formula in Algorithm 1; alternative budget definitions with similar guarantees are discussed in the appendix, so the portable insight is bounding how far cumulative reward can fall below a safe benchmark.","If the conjecture that results extend to random offline sample counts holds, the practical gain is substantial: practitioners could drop the fixed-dataset assumption and still use the same guarantees.","A testable extension is to instantiate the budget with confidence intervals for contextual bandits or simple reinforcement-learning value functions; the paper anticipates this transfer but does not prove it.","We read the parameter $\\alpha$ as an application-level trade-off knob: small values favor the logging-policy guarantee and large values favor the optimality guarantee, so choosing it well is part of deploying the method."],"forward_implications":["OTO performs nearly as well as the better of LCB and UCB at any time horizon, for both regret against the optimal arm and regret against the logging policy.","The algorithm needs no prior knowledge of whether deployment is short or long; the budget determines the switch automatically.","When $\\alpha = 0$, OTO reduces to LCB, and larger $\\alpha$ makes it behave more like UCB, so the trade-off is controlled by one parameter.","In the unknown-horizon case, a horizon-doubling proxy preserves the guarantees up to a factor involving $\\alpha$ and an additive cost, with the confidence parameter decaying as $1/t^2$.","The minimax lower bound shows that offline-to-online difficulty depends on the composition of offline data, with the minimum per-arm offline count limiting small-horizon performance and the usual $\\sqrt{KT}$ term emerging for large horizons."],"supporting_citations":[{"why":"Supplies the conservative-bandits formulation that inspired the exploration-budget design.","marker":"Wu et al. (2016)"},{"why":"Provides the weighted-minimax analysis showing LCB outperforms UCB in offline MABs, the starting point for comparing the two algorithms.","marker":"Xiao et al., 2021a"},{"why":"Establishes LCB's adaptivity and its ability to compete with policies covered by offline data, motivating regret against the logging policy as a criterion.","marker":"Rashidinejad et al. (2024)"},{"why":"Gives related offline-to-online minimax bounds that align with the paper's lower bound up to constants.","marker":"Cheung and Lyu (2024)"},{"why":"Shows how offline data reduces online regret in multi-armed bandits, anchoring the offline-to-online setting.","marker":"Shivaswamy and Joachims (2012)"},{"why":"Provides the phase-transition analysis for optimism-driven offline-to-online learning that motivates comparing different horizon regimes.","marker":"Bu et al. (2022)"},{"why":"Supplies a lower bound for offline-to-online regret that the paper builds on in its minimax analysis.","marker":"Gur and Momeni (2022)"},{"why":"Gives the UCB variant whose confidence-bound analysis is the model for OTO's optimistic phase.","marker":"Auer and Ortner (2010)"}],"fun_headline_variants":["OTO matches both LCB and UCB in offline-to-online bandits","OTO: safe early, efficient later—best of LCB and UCB in one policy","OTO finds the sweet spot between LCB safety and UCB efficiency","From LCB to UCB: OTO's adaptive strategy for offline-to-online learning","OTO: one bandit policy that rides the LCB-to-UCB transition"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole proof treats the number of offline samples per arm as fixed, exactly known numbers, and it identifies the logging policy with those counts; if the counts are random, the budget and the bounds do not directly apply, and the paper only conjectures that they would extend with little change.","fun_headline_variants_meta":{"raw":{"variants":["OTO matches both LCB and UCB in offline-to-online bandits","OTO: safe early, efficient later—best of LCB and UCB in one policy","OTO finds the sweet spot between LCB safety and UCB efficiency","From LCB to UCB: OTO's adaptive strategy for offline-to-online learning","OTO: one bandit policy that rides the LCB-to-UCB transition"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000742,"raw_usage":{"total_tokens":3391,"prompt_tokens":1105,"completion_tokens":2286,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":721,"completion_tokens_details":{"reasoning_tokens":2180}},"tokens_in":721,"tokens_out":2286,"duration_ms":14852,"temperature":1.0,"reasoning_tokens":2180,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T05:48:18.770712+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a two-arm instance with $m_1 = m$, $m_2 = 0$, $\\mu_1 = 0.5$, $\\mu_2 = 1$, run OTO with known horizon $T$ and $\\alpha = 1$, and compare its logging-policy regret to the bound $t(1+\\alpha)\\beta$ from Eq. (2). If the empirical regret exceeds that bound by a non-logarithmic factor with high probability, the budget induction in Section 7 is wrong; if OTO ever exceeds both the LCB and UCB regret curves by more than the additive $K$ term, Theorem 1 is violated.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes LCB's adaptivity and its ability to compete with policies covered by offline data, motivating regret against the logging policy as a criterion."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives related offline-to-online minimax bounds that align with the paper's lower bound up to constants."},{"cited_title":"and Joachims, T","cited_arxiv_id":null,"evidence_quote":"Shows how offline data reduces online regret in multi-armed bandits, anchoring the offline-to-online setting."},{"cited_title":"and Momeni, A","cited_arxiv_id":null,"evidence_quote":"Supplies a lower bound for offline-to-online regret that the paper builds on in its minimax analysis."},{"cited_title":"and Ortner, R","cited_arxiv_id":null,"evidence_quote":"Gives the UCB variant whose confidence-bound analysis is the model for OTO's optimistic phase."}],"review_version":1}