{"id":"be32d738-7cdd-4318-815c-bb8f606f3748","arxiv_id":"2502.02486","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Contextual bandits with general function approximation can achieve regret scaling with cumulative reward variance and only logarithmically with the reward range, using Catoni robust mean estimators, with a matching lower bound for the leading term.","lead":"This paper designs contextual bandit algorithms whose regret depends on the cumulative variance of rewards rather than the worst-case reward range, using Catoni's robust mean estimator. It also proves a matching lower bound, so the leading variance term is tight.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The unknown-variance bound in Theorem 5 is not polylog in R under Assumption 1: the omitted (sqrt c_eta + sigma_eta) factor can be Theta(R) for a valid heavy-tailed noise, so the advertised log-R dependence for VACB is unsupported.","rationale":"The reader's verdict of CONDITIONAL is appropriate. The known-variance Theorem 2 and the lower bound appear well supported by the detailed appendices; I do not see a fatal flaw there. My primary concern is the unknown-variance theorem's advertised logarithmic dependence on R, which is the unique selling point of VACB. Under Assumption 1, c_eta and sigma_eta are instance-dependent constants that may grow with R, and the formal Theorem 5 bound then has a Theta(R) term. This is a correctness risk in the claim, not a disagreement with current consensus: it means the stated theorem does not deliver the promised improvement over prior R dF ln N_F bounds without extra assumptions. The issue is localized and fixable by adding explicit polylog-R moment-ratio assumptions or by revising the abstract and Table 1, so conditional acceptance rather than rejection is the right outcome. The leftover 'fixable error' note in Appendix C.1 supports treating the current proof as incomplete. I partially agree with the reader: the reader focused on whether the learner must know sigma_eta and c_eta, while my main issue is that even with this knowledge the bound can carry a polynomial R dependence through those same constants.","tokens_in":991,"tokens_out":3378,"duration_ms":180970,"concrete_test":"Set the noise distribution to independent draws with P(eta=±1)=(1-R^{-2})/2 and P(eta=±R)=1/(2R^2) in a two-armed bandit with a one-dimensional linear class, so dim_{1,T}(F)=O(1) and log N(F,upsilon)=O(log T). Verify Assumption 1 holds with sigma_eta=O(1), c_eta=Theta(R^2), then evaluate the second term of Theorem 5; it becomes Theta(R), showing the bound is not logarithmic in R. Also re-derive Lemma 15 with the final plug-in f_hat_{t-1} used consistently; if inequality (10) fails, the unknown-variance proof is incomplete as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Assumption 1 only requires the existence of constants sigma_eta and c_eta; it does not constrain how they may depend on the reward range R. Take eta with P(eta=±1)=(1-R^{-2})/2 and P(eta=±R)=1/(2R^2). Then E[eta]=0, E[eta^2]=1, and Var[eta^2]=Theta(R^2), so sigma_eta=O(1), c_eta=Theta(R^2), and Assumption 1 holds with sigma_t=1. For this valid instance, the formal Theorem 5 bound contains a lower-order term Lf * dim_{1,T}(F) * (log N(F, upsilon))^{3/4} * (sqrt(c_eta)+sigma_eta), which is Theta(R) for fixed Lf, dim, and log N. The Table 1 row for VACB and the abstract suppress this factor, claiming only ~O(dF sqrt( sum sigma_t^2 ln N_F ) + dF (ln N_F)^{3/4}). That suppressed factor is exactly the difference from prior R dF ln N_F bounds. This is not merely a knowability issue: even an oracle that knows sigma_eta and c_eta gets a bound that can scale polynomially with R unless one adds a separate assumption such as c_eta, sigma_eta = O(polylog R). The paper should either state that assumption explicitly or weaken the log-R claim. Additionally, the admitted 'fixable error' in Appendix C.1 around the f_hat versus f_hat_{t-1} plug-in in Var_hat_t means Theorem 3 is not fully proven as printed.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper develops contextual bandit algorithms for general function approximation when rewards are heavy-tailed with bounded conditional variance, aiming for regret that scales with cumulative variance rather than with the worst-case range R. The known-variance algorithm (Catoni-OFUL) uses Catoni's mean estimator to robustify an excess-loss regression oracle and claims a regret bound of ~O(Lf sqrt(sum_t sigma_t^2 * dim(F) log N_F) + Lf dim(F) log N_F), i.e. polylog R. A two-arm lower bound in Theorem 1 shows the leading variance term is minimax optimal. For unknown variances, the paper proposes a peel-based variance-agnostic algorithm (VACB) with a robust plug-in variance estimator and claims a similar variance-based bound with a fourth-moment factor, also polylog R. An alternative candidate-set algorithm is given in Appendix D.","tokens_in":46310,"tokens_out":10909,"duration_ms":93705,"significance":"If the known-variance theorem is correct, it is a substantial step: it removes the polynomial R dependence previously present for general function classes and matches the lower bound. The proof appears detailed and uses a genuine uniform-in-theta Catoni concentration inequality. The lower bound is a clean two-instance argument and does not rely on the upper-bound machinery. The unknown-variance result, by contrast, is not yet established as advertised: the formal theorem contains an unacknowledged factor (sqrt(c_eta) + sigma_eta) that can be polynomial in R under Assumption 1, and the appendix contains an admitted gap in the proof of the variance-estimation lemma. With those items fixed and the assumptions made explicit, this would be a strong paper.","major_comments":[{"comment":"The proof of Lemma 15 contains an explicit note: \"There is a fixable error. Now, I change the plug-in in Var_hat_t from f_hat_t to f_hat_{t-1}, and change the analysis above, so now the upper and lower bound is reasonable.\" Since this note states that the printed argument as it stands is not the correct one, and since Lemma 15 is the load-bearing variance-estimation accuracy step for Theorem 5 (Lemma 16, and hence Theorem 3/5), the unknown-variance upper bound is not fully proven as printed. I would ask for a complete rewrite of this part, with consistent notation (Lemma 15 labels the quantity Vart(f_hat_t) while the estimator on the right-hand side is defined with f_hat_{t-1}).","section":"Appendix C.1, Lemma 15"},{"comment":"The formal regret bound in Theorem 5 contains the factor Lf * dim_{1,T}(F) * (log N)^{3/4} * (sqrt(c_eta) + sigma_eta). Under Assumption 1, c_eta and sigma_eta are unconstrained relative to the reward range R. For the valid noise distribution eta defined by P(eta=+-1)=(1-R^{-2})/2 and P(eta=+-R)=1/(2R^2), we have E[eta]=0, E[eta^2] approx 2, and Var[eta^2] = Theta(R^2), so Assumption 1 holds with bounded sigma_eta and c_eta = Theta(R^2). For this instance the displayed lower-order term is Theta(R), not polylog(R), so the advertised logarithmic R dependence for VACB (abstract, Table 1, informal Theorem 3) does not follow from the stated assumptions. The authors need to either add an explicit condition such as c_eta, sigma_eta = O(polylog(R)) or weaken the claim.","section":"Theorem 5, Table 1, abstract"},{"comment":"Algorithm 2 and Theorem 5 require knowledge of sigma_eta and c_eta: gamma = 1/(sigma_eta T^{3/2}) in Theorem 5, and Table 3 parameters (theta_{t,l}^{Var}, theta_t^l, beta_t^l) depend on sigma_eta and c_eta. The paper does not state that the learner must know these global bounds. Without stating this, the \"unknown-variance\" algorithm cannot be instantiated as described, and the abstract's claim that the method \"remove[s] the need for cumbersome variance estimation\" is not literally accurate. This is a structural assumption about the algorithm, distinct from the regret-bound claim, and should be stated explicitly in the main text.","section":"Algorithm 2, Theorem 5"}],"minor_comments":[{"comment":"The conclusion states that the known-variance algorithm \"enjoys a variance-based regret bound with only polynomial dependence on R\", which contradicts Theorem 2/4's polylog R claim; this should be corrected to \"polylogarithmic\".","section":"Section 5"},{"comment":"The phrase \"For any t in [t]\" appears with the same symbol t on both sides; it should be \"for any i in [t]\" or \"for any t in [T]\".","section":"Section 4.2, proof sketch, Part II"},{"comment":"The definition of theta_t^{Var} is inconsistent across the appendix: Lemma 12 uses (4(2 sigma_eta^2 + c_eta + L_f^2 + 16 rho^2 beta_{t-1})^2)^{-1}, Lemma 15 uses (12(2 sigma_eta^2 + c_eta + L_f^2 + 16 rho^2 beta_{t-1}^2))^{-1}, and Lemma 16 and Table 3 use different forms with 2^{-2l+4}. Please reconcile all occurrences and check that the constants in the proofs match the algorithm specification.","section":"Appendix C.1, Lemmas 12, 15, 16"},{"comment":"The row for Heavy-OFUL (Huang et al., 2024) is left blank with only a footnote reference; the table would be more readable if the explicit bound were shown directly or stated as identical to AdaOFUL in the table body.","section":"Table 1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript appears to have been posted with an unfinished appendix: the \"There is a fixable error\" note inside the proof of Lemma 15 suggests the unknown-variance section was not ready for publication as submitted. I also found that the advertised log-R claim for the unknown-variance algorithm is not supported by the stated assumptions, because the (sqrt(c_eta)+sigma_eta) factor can be polynomial in R. I do not see grounds for rejection if the authors add the needed assumption, correct the proof, and fully rewrite the variance-estimation part, but I would want to verify the corrected Lemma 15-16 chain carefully."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the known-variance half is a real result and the lower bound is fine, but the unknown-variance half, as written, does not deliver the advertised log-R bound. The paper deserves a serious referee, but it needs major revision before acceptance.\n\nWhat is new: for general function approximation with heavy-tailed rewards and known per-round variances, the Catoni-OFUL bound sqrt(sum sigma_t^2 * d_F ln N_F) + d_F ln N_F with only log R dependence is a genuine improvement over OLS/DistUCB, which carry R d_F ln N_F terms. The uniform-in-theta Catoni concentration lemma is a useful device, and the two-instance lower bound for the leading variance term is standard and sound.\n\nWhere it breaks: Theorem 5 and the VACB row in Table 1 claim ~O(d_F sqrt(sum sigma_t^2 ln N_F) + d_F (ln N_F)^{3/4}) with only logarithmic R. The actual bound in Theorem 5 contains an additive term L_f dim_{1,T}(F) (log N)^{3/4} (sqrt(c_eta) + sigma_eta). Assumption 1 places no constraint on how c_eta scales with R. There are valid heavy-tailed noises with unit variance and c_eta ~ R^2 (e.g., sparse ±R spikes), so that term is Theta(R). The log-R claim for VACB is unsupported. The abstract and Table 1 suppress that factor. This is not a knowability issue; an oracle that knows sigma_eta and c_eta still gets a linear-in-R term. The bound needs an explicit assumption like c_eta, sigma_eta = O(polylog R), or the claim must be weakened.\n\nThere are two further problems, both real but smaller. The unknown-variance algorithm silently requires knowing sigma_eta and c_eta (in gamma, the bonus, and the Catoni theta); the paper never states this, which is a mismatch with the 'variance-agnostic' framing. And Appendix C.1 contains an admitted 'fixable error': the plug-in variance estimator uses \\hat f_t instead of \\hat f_{t-1}; with that change the proof appears patchable, but as printed Theorem 3 is not fully proven.\n\nThe known-variance analysis is detailed and, as far as I checked, coherent; I did not verify every algebraic step. Citation pattern looks honest, and the comparison table helps.\n\nWho this is for: people working on variance-aware bandits or robust mean estimation in decision making. They will want the known-variance result; they should not quote the unknown-variance bound in its current form. Recommend: send to peer review, condition on fixing the unknown-variance analysis (the c_eta/R issue and the plug-in error) and either adding the parameter-knowledge assumption to the theorem or re-framing the contribution.","headline":"Known-variance result is solid; unknown-variance log-R claim doesn't survive contact with Assumption 1.","tokens_in":46910,"tokens_out":2710,"would_cite":false,"duration_ms":25774,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G35","62L05","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"Contextual bandits can achieve variance-scale regret under heavy-tailed rewards.","keywords":["contextual bandits","heavy-tailed rewards","Catoni estimator","variance-aware regret","general function approximation","eluder dimension","unknown variance","robust statistics"],"falsifier":"Run the two-armed bandit from the paper's lower-bound construction with known variances: one arm deterministic and the other heavy-tailed with variance $\\sigma^2$ and large range $R$. If any algorithm's regret grows polynomially in $R$ rather than tracking $\\sqrt{\\sum_t \\sigma_t^2}$, the claimed logarithmic-$R$ dependence fails.","tokens_in":45756,"feed_emoji":"🎰","tokens_out":5739,"duration_ms":58966,"temperature":0.7,"pith_summary":"The paper claims that contextual bandits with general function approximation can enjoy regret governed by the cumulative variance of the rewards rather than by their worst-case range $R$, even when rewards are heavy-tailed. Its known-variance algorithm, Catoni-OFUL, builds confidence sets from Catoni's robust mean estimator applied to excess-loss terms, and attains regret $\\tilde{O}\\bigl(\\sqrt{\\sum_{t} \\sigma_t^2 \\cdot d_F \\ln N_F} + d_F \\ln N_F\\bigr)$ with $R$ appearing only logarithmically. For unknown variances, the peeling-based Variance-Agnostic Catoni Bandit reaches $\\tilde{O}\\bigl(d_F \\sqrt{\\sum_t \\sigma_t^2 \\ln N_F} + d_F (\\ln N_F)^{3/4}(\\sqrt{c_\\eta}+\\sigma_\\eta)\\bigr)$ under an assumption relating fourth moments to variances. A matching lower bound $\\Omega(\\sqrt{\\mathbb{E}\\sum_t \\sigma_t^2})$ shows the leading variance term cannot be improved. If correct, these bounds make heavy-tailed or large-range rewards far less costly than earlier range-dependent guarantees suggested.","feed_headline":"Variance, not reward range, sets bandit regret","feed_subtitle":"Heavy-tailed rewards no longer force a range-sized penalty; new bounds are logarithmic in R and match a lower bound.","key_machinery":"The load-bearing object is Catoni's mean estimator, the unique zero of $\\sum_i \\Psi(\\theta(Z_i-x))$ with $\\Psi(x)=\\log(1+x+x^2/2)$ for $x\\ge 0$ and its antisymmetric counterpart for $x<0$. Its concentration inequality, made uniform over the parameter $\\theta$, gives an excess-loss estimate whose error depends on the cumulative variance of the noise and only logarithmically on its bound $R$. Around this, the paper builds variance-weighted OFUL confidence sets using eluder dimension as the function-class complexity measure; the unknown-variance algorithm adds a SupLinUCB-style peeling hierarchy in which each level uses a plug-in Catoni variance estimator, replacing per-round variances with weights derived from the uncertainty level.","core_discovery":"The central discovery is that robustifying the excess loss, not the reward estimate, is what carries variance-aware regret to general function classes. Over the sample history, the algorithm forms variance-weighted squared losses and replaces the noise cross term with a Catoni estimator whose concentration error scales with the sum of variances rather than with $R$. This keeps the true function in the confidence set with a radius depending only logarithmically on $R$. The same device is extended to unknown per-round variances by layering uncertainty levels and estimating one aggregate variance with another Catoni estimate; the resulting regret matches the known-variance bound up to an extra eluder-dimension and logarithmic factor. The paper also constructs two-armed bandit instances showing that any algorithm must pay $\\sqrt{\\text{sum of chosen-action variances}}$ in the leading term, so the variance term in the upper bound is optimal.","pith_inferences":["Editorial inference: because the unknown-variance algorithm's parameters require the global bounds $\\sigma_\\eta$ and $c_\\eta$, the result is best read as removing per-round variance estimation rather than removing all knowledge about variance; an algorithm that must discover even those global constants would need an additional adaptation layer.","Editorial inference: the same robust-excess-loss construction may transfer to adversarial corruption and to Markov decision processes with nonlinear function approximation, since those settings also use weighted-regression confidence sets; the paper itself lists these as future directions.","Editorial inference: the candidate-set variant of Catoni-OFUL suggests the min-max optimization in the main algorithm is not essential, and a randomized choice from a robust candidate set may be substantially easier to implement in practice."],"forward_implications":["With known variances, any realizable general function class gets $\\tilde{O}\\bigl(\\sqrt{\\sum_t \\sigma_t^2 \\, d_F \\ln N_F} + d_F \\ln N_F\\bigr)$ regret, so deterministic rewards leave only a complexity term and $R$ is never polynomial in the bound.","With unknown variances, the same robustness holds up to an extra factor $d_F$ and a $(\\ln N_F)^{3/4}(\\sqrt{c_\\eta}+\\sigma_\\eta)$ term, so no separate function class for predicting per-round variance is needed.","The lower bound shows that the leading regret term must scale with the variances of the actions the algorithm actually chooses, not with the variances of the optimal policy's actions.","For linear function classes, the eluder dimension is logarithmic in the dimension, so the bounds reduce to roughly $d\\sqrt{\\sum_t \\sigma_t^2}$-style guarantees while removing the range dependence present in earlier linear heavy-tailed results."],"supporting_citations":[{"why":"Supplies the Catoni mean estimator whose concentration properties drive the robust excess-loss estimates.","marker":"Audibert and Catoni (2011)"},{"why":"Provides the survey presentation of Catoni and heavy-tailed mean estimation that the paper follows.","marker":"Lugosi and Mendelson (2019)"},{"why":"Defines the eluder dimension used as the function-class complexity measure in all regret bounds.","marker":"Russo and Van Roy (2013)"},{"why":"Supplies the variance-weighted regression machinery and regret decomposition used in the known-variance analysis.","marker":"Zhou and Gu (2022)"},{"why":"Supplies the peeling and SupLinUCB-style exploration structure adapted for the unknown-variance algorithm.","marker":"Zhao et al. (2023b)"},{"why":"Extends peeling to general function approximation and serves as the baseline the unknown-variance result improves.","marker":"Pacchiano (2024)"},{"why":"Gives the prior linear heavy-tailed unknown-variance bound whose variance-estimation step the paper avoids.","marker":"Li and Sun (2024)"},{"why":"Provides the prior heavy-tailed linear bandit result with moment assumptions that the known-variance guarantee extends beyond linear classes.","marker":"Huang et al. (2024)"},{"why":"Supplies the Catoni concentration lemma that the paper's uniform-in-$\n\\theta$ concentration result builds on.","marker":"Wei et al. (2020)"},{"why":"Supplies the sensitivity lemma used to control Catoni estimates over covering elements and over the parameter range.","marker":"Wagenmaker et al. (2022)"}],"fun_headline_variants":["Variance, not range, drives contextual bandit regret","Heavy-tailed rewards tamed: regret scales with variance","Catoni-based bandits: logarithmic cost in reward range","Variance-aware regret bounds for heavy-tailed bandits","Robust contextual bandits: variance, not range, matters"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the unknown-variance bound, the algorithm's parameters require the learner to know the global bounds $\\sigma_\\eta$ and $c_\\eta$ on the noise variance and its fluctuation; if those constants are truly unavailable, the variance-agnostic guarantee cannot be instantiated.","fun_headline_variants_meta":{"raw":{"variants":["Variance, not range, drives contextual bandit regret","Heavy-tailed rewards tamed: regret scales with variance","Catoni-based bandits: logarithmic cost in reward range","Variance-aware regret bounds for heavy-tailed bandits","Robust contextual bandits: variance, not range, matters"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000174,"raw_usage":{"total_tokens":1260,"prompt_tokens":902,"completion_tokens":358,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":518,"completion_tokens_details":{"reasoning_tokens":277}},"tokens_in":518,"tokens_out":358,"duration_ms":4220,"temperature":1.0,"reasoning_tokens":277,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T11:58:32.159523+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the two-armed bandit from the paper's lower-bound construction with known variances: one arm deterministic and the other heavy-tailed with variance $\\sigma^2$ and large range $R$. If any algorithm's regret grows polynomially in $R$ rather than tracking $\\sqrt{\\sum_t \\sigma_t^2}$, the claimed logarithmic-$R$ dependence fails.","supporting_citations":[{"cited_title":"and Catoni, O","cited_arxiv_id":null,"evidence_quote":"Supplies the Catoni mean estimator whose concentration properties drive the robust excess-loss estimates."},{"cited_title":"and Mendelson, S","cited_arxiv_id":null,"evidence_quote":"Provides the survey presentation of Catoni and heavy-tailed mean estimation that the paper follows."},{"cited_title":"and Van Roy, B","cited_arxiv_id":null,"evidence_quote":"Defines the eluder dimension used as the function-class complexity measure in all regret bounds."},{"cited_title":"Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs","cited_arxiv_id":"2205.11507","evidence_quote":"Supplies the variance-weighted regression machinery and regret decomposition used in the known-variance analysis."},{"cited_title":"Second Order Bounds for Contextual Bandits with Function Approximation","cited_arxiv_id":"2409.16197","evidence_quote":"Extends peeling to general function approximation and serves as the baseline the unknown-variance result improves."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the prior heavy-tailed linear bandit result with moment assumptions that the known-variance guarantee extends beyond linear classes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Catoni concentration lemma that the paper's uniform-in-$\n\\theta$ concentration result builds on."},{"cited_title":"J., Chen, Y., Simchowitz, M., Du, S., and Jamieson, K","cited_arxiv_id":null,"evidence_quote":"Supplies the sensitivity lemma used to control Catoni estimates over covering elements and over the parameter range."}],"review_version":1}