{"id":"942eeb89-cc4e-46d2-8d1e-5c2953da69f0","arxiv_id":"1909.02506","paper_version":3,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The AVE algorithm achieves O~(sqrt(M^2 A H^4 n log^3 |F|)) cumulative regret for episodic MDPs with low Bellman rank and realizable function approximation.","lead":"An online reinforcement learning algorithm called AVE learns near-optimal policies in huge state spaces while keeping total regret around the square root of the number of trials. It is the first such guarantee under low Bellman rank and realizable function approximation, extending a prior PAC-learning method.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Assumption 2.2 (closedness under concatenation) is load-bearing in Lemma 5.6 and is not mild: shared-parameter function classes violate it without necessarily losing low Bellman rank.","rationale":"The reader and I identify the same load-bearing point: Assumption 2.2 is used in an essential way in the volumetric argument (Lemma 5.6, Appendix C) and in the recursive construction in Algorithm 2. The proof as written is internally consistent under the stated assumptions, and I found no independent error in the concentration arguments or the doubling trick. However, the paper's framing—first sqrt(n)-regret under realizability and low Bellman rank—should be qualified: Assumption 2.2 is substantively restrictive and is not shown to hold for common shared-representation function classes. The proposed test would determine whether the restriction is real by exhibiting a natural class with low Bellman rank whose closure has higher rank. If the test confirms the rank increase, the theorem's parameter M must be understood as the rank of the closed class, not the original class, which narrows the claimed contribution. I therefore recommend a conditional acceptance: the authors should either prove Assumption 2.2 for meaningful nonlinear classes, or explicitly state the theorem with the closure assumption and discuss how it interacts with Bellman rank. This is a scope concern, not a proof invalidation, so REJECT would be too strong; UNCHANGED would understate the gap between the abstract and the theorem.","tokens_in":39595,"tokens_out":11388,"duration_ms":121664,"concrete_test":"Construct a two-layer MDP with A=2 and features φ_1, φ_2 such that F = {f_θ(x_h, a) = θ^T φ_h(x_h, a) : θ ∈ R^d} (shared θ) satisfies realizability and Assumption 1.2 with Bellman rank M=1. Compute the Bellman rank M′ of the concatenation closure F^concat = ∏_h F_h (layer-specific θ_h). If M′ > M, then closing F under concatenation changes the problem parameter, and Lemma 5.6 cannot be repaired by enlarging F without weakening the guarantee to M′. This settles whether Assumption 2.2 is a substantive restriction on the central claim.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central theorem is valid only under Assumption 2.2, and the proof cannot be trivially extended when it fails. In Appendix C (proof of Lemma 5.6), the recursive elimination analysis needs the equation |E(f, π_g, h)| = |E(g, π_g, h)| = |⟨ν_h(g), ξ_h(f)⟩| for g = g′ ∘_{h′} f. The first equality only uses g(x_h, ·) = f(x_h, ·) for h′ < h, but the second applies Assumption 1.2, which requires both f and g to lie in F. Assumption 2.2 is exactly what places the concatenated function in F. The same issue appears in Algorithm 2, Line 3, where Check is called on the distribution {(g ∘_h f, P_k(f))}; without closure, these are not hypotheses to which the Bellman factorization applies. The paper calls Assumption 2.2 “very mild,” but that is not argued. For a natural linear class F = {f_θ(x_h, a) = θ^T φ_h(x_h, a) with a single shared θ}, layer-wise concatenations with different θ_h are not in F, while realizability and low Bellman rank can still hold. Enlarging F to its layer-wise product can increase the Bellman rank, so this is not a harmless normalization; the advertised dependence on M is on the rank of the closed class. The abstract's claim of sqrt(n)-regret under “realizability and low Bellman rank” therefore overstates the scope.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Adaptive Value-function Elimination (AVE), an online reinforcement learning algorithm for finite-horizon stochastic MDPs with large state spaces and function approximation. Under realizability (Assumption 1.1) and a low Bellman rank condition (Assumption 1.2), the algorithm maintains an active hypothesis class, selects policies by optimism, estimates Bellman errors adaptively, and eliminates hypotheses using contextual-bandit-style importance weighting. The main result, Theorem 5.9 and Corollary 5.10, states that with high probability the cumulative regret over n trajectories is O~(sqrt(M^2 A H^4 n log^3 |F|)), where M is the Bellman rank, A is the number of actions, H is the horizon, and F is the hypothesis class. The paper also extends the result to infinite hypothesis classes using Natarajan and pseudo dimensions. The proof is detailed and largely self-contained, with concentration arguments and a volumetric elimination analysis in the appendices.","tokens_in":39848,"tokens_out":5951,"duration_ms":63257,"significance":"If the theorem holds as stated, this is a significant contribution: it would give the first square-root-regret bound for general value function approximation in stochastic MDPs under realizability and low Bellman rank, improving on the PAC-style guarantees of OLIVE and on black-box online-to-batch conversions. The paper's technical core is credible: the reduction of each elimination step to a contextual bandit problem is a genuinely useful idea, and the appended concentration and volumetric arguments are careful and specific. The claimed dependence on the Bellman rank M and on log |F| is attractive. However, the advertised scope is broader than what is actually proved: the regret bound is conditional on Assumption 2.2 (closedness under layer-wise concatenation), which is load-bearing and materially restricts the function classes covered. The central theorem appears sound under that assumption, but the paper must clearly state the assumption in its main theorem and temper the abstract's claim that the result holds under only realizability and low Bellman rank.","major_comments":[{"comment":"Assumption 2.2 is load-bearing for the proof of Lemma 5.6 and hence for the main regret bound. In Appendix C, the volumetric argument needs the identity |E(f, π_g, h)| = |E(g, π_g, h)| for g = g' ∘_{h'} f. The first equality follows from agreement of g and f from layer h' onward, but the second uses Assumption 1.2, which applies only when both functions lie in F. The text explicitly invokes Assumption 2.2 to conclude g ∈ F. Without this assumption, the concatenated function g may be outside F, so neither E(f, π_g, h) nor E(g, π_g, h) is covered by the Bellman factorization. The same issue arises at Algorithm 2, Line 3, where Check is called on the distribution {(g ∘_h f, P_k(f))}_{f ∈ G}; these concatenated objects are not known to be hypotheses in F. Thus Theorem 5.9 and Corollary 5.10 are proved only for function classes closed under layer-wise concatenation, and the abstract's claim of a sqrt(n)-regret result under 'realizability and low Bellman ranks' overstates the scope.","section":"Assumption 2.2, Appendix C (proof of Lemma 5.6), Algorithm 2 Line 3"},{"comment":"The claim that Assumption 2.2 is 'very mild' is not supported, and enlarging the function class to force closure is not a harmless normalization. For example, a natural linear class F = {f_θ(x_h, a) = θ^T φ_h(x_h, a) with a single parameter vector θ shared across layers} satisfies realizability and low Bellman rank in many settings, but the layer-wise concatenation of two hypotheses with different θ_h is generally not in F. The argument that independent per-layer approximation is 'almost always used' is a statement about practice, not a mathematical guarantee, and it does not cover shared-representation models. Moreover, the Bellman rank M of the closure of F can be larger than the rank of F, so the advertised dependence on M is on the rank of the enlarged class. The paper should either prove that closure preserves low Bellman rank up to a bounded factor, or explicitly state separately that the regret bound holds for a class satisfying Assumption 2.2 and indicate how restrictive this is.","section":"Section 2.3, Assumption 2.2"}],"minor_comments":[{"comment":"The label 'pesudo-learn' should be 'pseudo-learn'.","section":"Algorithm 2, Line 7"},{"comment":"In the display after Eq. (37), the term '(12 + 4)ǫ_k' should presumably be '(12H + 4)ǫ_k', consistent with the surrounding inequalities.","section":"Section 5.3, proof of Lemma 5.3"},{"comment":"The phrase 'Pesudo dimension' appears both in the main text and in Definition 6.2; it should be 'pseudo dimension'.","section":"Definition 6.2 and surrounding text"},{"comment":"The theorem statements should explicitly list Assumptions 1.1, 1.2, 2.1, and 2.2 rather than leaving them implicit from Section 2, because Assumption 2.2 is not a standard part of the low-Bellman-rank framework and is used essentially in the proof.","section":"Theorem 5.9 and Corollary 5.10"},{"comment":"The constants c_1 through c_4 (and c_5 through c_7 in Appendix E) are only specified as 'large enough universal constants'; giving explicit values or a table of dependencies would make the sample-size choices easier to verify.","section":"Appendix B"}],"recommendation":"major_revision","confidential_remarks":"The main issue is the mismatch between the advertised claim and the assumptions actually needed. The technical proof appears sound conditional on Assumption 2.2, and I think the paper is a solid theoretical contribution once the scope is stated accurately. I would recommend major revision rather than rejection, and I would ask the authors to either prove that low Bellman rank is preserved under taking the layer-wise closure of F or to explicitly acknowledge that the result holds only for closed classes and adjust the abstract and title accordingly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper delivers the first sqrt(n)-regret guarantee for stochastic MDPs with general value function approximation under realizability and low Bellman rank. That is real. The reduction of policy elimination to contextual bandits, replacing OLIVE's random-action exploration, is a genuine technical step, and the appendices give a detailed proof with explicit sample sizes. The result does not rest on curve-fitting; it is an upper bound proved from stated assumptions.\n\nThe soft spot is Assumption 2.2 (closedness under concatenation). The proof of Lemma 5.6 in Appendix C needs concatenated functions like g' ∘_{h'} f to remain in F, and the paper calls the assumption \"very mild\" without much support. It is not mild for natural function classes. A linear class with a shared parameter vector across layers violates the assumption, and enlarging F to its layer-wise closure can increase the Bellman rank. So the advertised dependence on M is actually the rank of the closed class, not necessarily of the original F. The abstract's \"realizability and low Bellman rank\" is therefore an overstatement; the honest statement is \"realizability, low Bellman rank, and closedness under concatenation.\" The paper does list Assumption 2.2 explicitly, so the result is still sound within its scope. But the claim that the assumption is benign should have been argued or at least discussed with examples.\n\nOther issues are minor: uninstantiated universal constants, some typos, and the usual reviewer burden of checking a long recursive argument without machine assistance. I did not find circular reasoning or a hidden fitting step. The citation pattern is appropriate, building on OLIVE and Dudik et al., and the related work section is accurate.\n\nWho gets value from this: RL theorists working on function approximation and exploration. It is a significant step that fills a known gap between PAC guarantees and online regret for structured MDPs. It is not a practitioner's paper.\n\nMy recommendation: send it to peer review. It deserves a serious referee despite the Assumption 2.2 concern, and the authors should be asked to clarify the scope of that assumption and either weaken it or justify its mildness. The central argument is sound under the stated conditions.","headline":"First sqrt(n)-regret for low Bellman rank MDPs, with a load-bearing closedness assumption that deserves scrutiny.","tokens_in":40441,"tokens_out":1665,"would_cite":true,"duration_ms":21177,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","90C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"A new algorithm, Adaptive Value-function Elimination, achieves the first √n cumulative regret bound for stochastic MDPs with general value function approximation under realizability and low Bellman rank.","keywords":["reinforcement learning","regret minimization","Markov decision processes","Bellman rank","function approximation","policy elimination","contextual bandits","online learning"],"falsifier":"Construct a finite stochastic MDP with realizability and low Bellman rank that satisfies the deterministic-initial-state assumption but violates closedness under concatenation, using for example a shared-representation function class; run AVE and observe either that the optimal function is eliminated or that cumulative regret grows linearly with n.","tokens_in":39351,"feed_emoji":"🤖","tokens_out":6603,"duration_ms":68681,"temperature":0.7,"pith_summary":"The paper claims that an agent can explore a Markov decision process whose state space is too large to enumerate, using a function class that contains the optimal Q-function, and still pay only square-root cumulative regret. The setting assumes a low Bellman rank: every Bellman error E(f,π_g,h) factorizes as an inner product of two vectors in R^M. The proposed algorithm, Adaptive Value-function Elimination (AVE), repeatedly eliminates hypotheses with large Bellman error, and the key move is to run each elimination step as a contextual bandit problem so that exploration costs little regret. If correct, this is the first √n-regret guarantee for stochastic MDPs with general value function approximation under realizability and low Bellman rank.","feed_headline":"First √n-regret guarantee for general value-function RL","feed_subtitle":"AVE turns every policy elimination step into a contextual bandit, so exploration costs little regret.","key_machinery":"The central object is the Bellman error functional E(f,π_g,h), and the central identity is the policy loss decomposition f(x1,π_f(x1)) − $V^{{π_f}}$(x1) = Σ_{h=1}^H E(f,π_f,h), which converts value suboptimality into accumulated Bellman error. The low-Bellman-rank assumption factorizes E(f,π_g,h) = ⟨ν_h(g), ξ_h(f)⟩ with values in R^M, so each elimination step can be viewed as cutting a slab through the set of vectors ξ_h(f); a volumetric argument adapted from OLIVE shows each such cut shrinks the minimum covering ellipsoid's volume by at least a constant factor, bounding the total number of eliminations by a polynomial in M and H. To avoid the regret cost of random exploration, AVE solves the elimination step as a contextual bandit: it finds a distribution P_k over hypotheses with low-variance importance-sampling weights, runs policies sampled from it, and uses active elimination with a doubling trick to discard poor hypotheses before measuring Bellman errors.","core_discovery":"Under realizability (Assumption 1.1) and low Bellman rank (Assumption 1.2), plus two mild conditions—known deterministic initial state and closedness under layer-wise concatenation—AVE runs n trajectories with policies that improve over time, and with probability at least 1−1/(nH) its expected regret is O~(√($M^{2}$ A $H^{4}$ n $log^{3}$ |F|)), where M is the Bellman rank, A the number of actions, H the horizon, and F the hypothesis class. The proof hinges on the policy-loss decomposition f(x1,π_f(x1)) − $V^{{π_f}}$(x1) = Σ_{h=1}^H E(f,π_f,h): a hypothesis's value error equals its accumulated Bellman error, so eliminating hypotheses with large Bellman error is the right way to control regret. AVE replaces OLIVE's random-action roll-ins with low-variance sampling distributions borrowed from contextual bandit algorithms; active elimination and expert weighting ensure the policies actually executed are near-optimal while information about all remaining hypotheses is collected. A volumetric argument shows each elimination shrinks the covering ellipsoid of the Bellman-error vectors by a constant factor, so only polynomially many elimination phases occur in M and H.","pith_inferences":["The same contextual-bandit elimination recipe could plausibly convert other PAC elimination algorithms into √n-regret learners, provided a factorization analogous to Bellman rank holds.","The result suggests exploration difficulty in reinforcement learning is governed by the Bellman rank rather than the ambient state dimension, so problem classes with small M should be empirically much easier than tabular worst cases.","Closedness under concatenation is a real restriction in practice: neural networks with shared feature layers do not generally contain every layer-wise splice; testing whether AVE-style elimination fails on such classes, or relaxing the assumption via a wider class, is a direct next step.","A Bernstein-style concentration bound is what removes one factor of A in the infinite-hypothesis analysis, hinting that similar variance-aware arguments could sharpen other elimination-based RL guarantees."],"forward_implications":["An averaging over AVE's n policies yields a PAC guarantee, so √n regret and sample-efficient batch learning come from the same run.","The regret bound is polynomial in M, A, H and log|F| but does not depend directly on the state-space size, so exponential or infinite state spaces are tractable when function approximation is good.","A naive explore-first-then-exploit strategy built from the OLIVE PAC guarantee only achieves ~O(n^{2/3}) regret; AVE's √n rate shows elimination can be interleaved with exploration without losing.","The same algorithm extends to infinite hypothesis classes: if the policy class has Natarajan dimension d_Π and the value class has pseudo-dimension d_V, regret is O~(√(M^2 A H^4 n(d_Π + d_V))), replacing log|F| with the statistical dimension.","The doubling trick over error levels means policies with large Bellman error are never run for many trajectories, which is why the cumulative gap stays √n rather than linear."],"supporting_citations":[{"why":"Supplies the OLIVE policy-elimination algorithm, the low-Bellman-rank assumption, and the volumetric argument that AVE adapts to bound elimination phases.","marker":"[1]"},{"why":"Provides the active elimination and expert weighting techniques for contextual bandits that AVE uses to explore without random actions.","marker":"[2]"},{"why":"Gives the coordinate-descent algorithm that computes the low-variance sampling distribution P_k and bounds its support size.","marker":"[38]"},{"why":"The doubling trick that lets AVE adaptively estimate Bellman errors while limiting how long a bad policy is run.","marker":"[21]"},{"why":"Bernstein-style uniform concentration bound used for infinite hypothesis classes and to improve the dependence on the action number A.","marker":"[42]"},{"why":"Ellipsoid volume-reduction result behind the volumetric argument bounding the number of elimination steps.","marker":"[44]"},{"why":"Natarajan dimension used to measure the complexity of infinite policy classes in the extension.","marker":"[40]"},{"why":"Pseudo-dimension used to measure the complexity of infinite value classes in the extension.","marker":"[41]"}],"fun_headline_variants":["First √n regret for RL with any value function class","AVE achieves √n regret under low Bellman rank","RL regret √n without tabular assumptions","√n regret for MDPs with low Bellman rank","Contextual bandit trick yields √n regret for RL"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the proof to go through, the function class must be closed under concatenation: any function assembled by taking one hypothesis per layer must itself lie in F; when this fails, the recursively constructed roll-in policies can fall outside the class and the elimination analysis no longer applies.","fun_headline_variants_meta":{"raw":{"variants":["First √n regret for RL with any value function class","AVE achieves √n regret under low Bellman rank","RL regret √n without tabular assumptions","√n regret for MDPs with low Bellman rank","Contextual bandit trick yields √n regret for RL"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000953,"raw_usage":{"total_tokens":4091,"prompt_tokens":996,"completion_tokens":3095,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":612,"completion_tokens_details":{"reasoning_tokens":3017}},"tokens_in":612,"tokens_out":3095,"duration_ms":21744,"temperature":1.0,"reasoning_tokens":3017,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:48:38.534221+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a finite stochastic MDP with realizability and low Bellman rank that satisfies the deterministic-initial-state assumption but violates closedness under concatenation, using for example a shared-representation function class; run AVE and observe either that the optimal function is eliminated or that cumulative regret grows linearly with n.","supporting_citations":[{"cited_title":"Schapire","cited_arxiv_id":null,"evidence_quote":"Supplies the OLIVE policy-elimination algorithm, the low-Bellman-rank assumption, and the volumetric argument that AVE adapts to bound elimination phases."},{"cited_title":"Efficient optimal learning for contextual bandits","cited_arxiv_id":null,"evidence_quote":"Provides the active elimination and expert weighting techniques for contextual bandits that AVE uses to explore without random actions."},{"cited_title":"Taming the monster: A fast and simple algorithm for contextual bandits","cited_arxiv_id":null,"evidence_quote":"Gives the coordinate-descent algorithm that computes the low-variance sampling distribution P_k and bounds its support size."},{"cited_title":"Gambling in a rigged casino: The adversarial multi-armed bandit problem","cited_arxiv_id":null,"evidence_quote":"The doubling trick that lets AVE adaptively estimate Bellman errors while limiting how long a bad policy is run."},{"cited_title":"Rates of convergence in the central limit the orem for empirical processes","cited_arxiv_id":null,"evidence_quote":"Bernstein-style uniform concentration bound used for infinite hypothesis classes and to improve the dependence on the action number A."},{"cited_title":"On minimum volume ellipsoids containing part of a give n ellipsoid","cited_arxiv_id":null,"evidence_quote":"Ellipsoid volume-reduction result behind the volumetric argument bounding the number of elimination steps."},{"cited_title":"On learning sets and functions","cited_arxiv_id":null,"evidence_quote":"Natarajan dimension used to measure the complexity of infinite policy classes in the extension."},{"cited_title":"Decision theoretic generalizations of the pac mo del for neural net and other learning applications","cited_arxiv_id":null,"evidence_quote":"Pseudo-dimension used to measure the complexity of infinite value classes in the extension."}],"review_version":1}