{"id":"3a6740cb-8d02-4211-8942-85e1bfdb1332","arxiv_id":"2505.03710","paper_version":1,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"NORA, an optimistic rare-switching actor-critic that targets Q*, achieves square-root-T regret and 1/epsilon-squared trajectory complexity in finite-horizon MDPs with general function approximation, under realizability, completeness, and a bounded Bellman eluder dimension.","lead":"An actor-critic reinforcement learning algorithm called NORA is proved to learn a near-optimal policy with 1/epsilon-squared sample complexity under general function approximation, the first such guarantee for this family of algorithms. A reader interested in RL theory would read this because it resolves an open question and shows how optimism, off-policy critics, and rare policy resets can make exploration efficient.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Optimism lemma uses completeness on f^(t), but Algorithm 2's pointwise argmax need not lie in F, so T f^(t) in G is unjustified and Theorem 2's central step is unproven.","rationale":"The reader correctly identified Generalized Completeness (Assumption 2) as the most fragile load-bearing premise, and Lemma 14 as the place where optimism is established. My stress test sharpens this: the proof applies completeness to f^(t), the pointwise supremum of the confidence set, but Algorithm 2 does not guarantee f^(t) is a member of F. Since Assumption 2 only covers Bellman backups of functions in F, the step Th f^(t)_{h+1} in F(tlast) is unjustified for the stated class of general function approximation. This is an internal gap in the proof of Theorem 2, not a disagreement with an external consensus. It directly affects the central claim of 1/epsilon^2 sample complexity and sqrt(T) regret, because the nonpositivity of the negative Bellman error in Lemma 10 is what removes the tracking-error terms that would otherwise make the bound vacuous. The fix is not purely cosmetic: one needs either a strong closure property of F or a different selection rule for f^(t), and the latter likely requires a new argument. I therefore move the verdict from CONDITIONAL to REJECT as the manuscript stands, while noting that a revised version with an explicit closure or selection assumption and a corrected Lemma 14 could merit reconsideration.","tokens_in":56820,"tokens_out":11731,"duration_ms":120984,"concrete_test":"Re-derive Lemma 14 with f^(t) defined formally as the pointwise supremum f^(t)_h(s,a) = sup_{f in F(tlast)} f_h(s,a) and track where the membership f^(t) in F is used. Then instantiate a two-element class F = {f1, f2} on a finite MDP, e.g. f1(s,a) = a and f2(s,a) = -a on A = {-1,1}, and verify whether the premise of Lemma 17 holds for the upper envelope f^(t). If the premise cannot be verified without an additional closure assumption, the proof has a genuine gap; adding closure under pointwise suprema would need to be checked against the linear-MDP examples and against the claimed generality of Theorem 2.","verdict_should_be":"REJECT","load_bearing_attack":"Algorithm 2 (line 4) sets f^(t)_h(s,a) in argmax_{f in F(tlast)} f_h(s,a) for every (s,a,h). This defines the pointwise upper envelope of the confidence set, not, in general, a single element of F. Lemma 14 then claims, via Lemma 17, that 0 <= L(t)_h(Th f^(t)_{h+1}, f^(t)_{h+1}) - min L <= H^2 beta, and concludes Th f^(t)_{h+1} in F(tlast), yielding optimism f^(t)_h >= T^pi_h f^(t)_{h+1}. But Lemma 17 is stated for f in F, and Assumption 2 only guarantees T f in G for f in F. Nothing in Assumptions 1-3 or the algorithm ensures f^(t) in F; for example, with F = {theta^T phi : ||theta|| <= R}, the pointwise supremum over a ball is phi^T theta_0 + R||phi||, which is not in F. If f^(t) is not in F, completeness G = TF does not apply to it, Lemma 17's premise fails, and the negative-Bellman-error term in Lemma 10 need not be nonpositive. The Theorem 2 regret decomposition and sample-complexity claim therefore rest on an unstated closure or selection condition. This is the load-bearing use of Generalized Completeness identified by the reader, but the sharper failure is that completeness is applied to an object outside F. A repair would require either assuming F is closed under pointwise suprema, which excludes standard linear classes, or modifying the algorithm to select f^(t) in F that is still pointwise optimistic, with a new argument for why such an f exists.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies finite-horizon episodic reinforcement learning with general function approximation and proposes optimistic actor-critic algorithms. As a warm-up, DOUHUA (Algorithm 1) is shown to achieve sqrt(T)-type regret when the policy class does not grow too fast, e.g., under closure under truncated sums. The main contribution is NORA (Algorithm 2), which targets Q*, performs rare-switching critic updates, uses policy resets, and is claimed to achieve regret O(sqrt(dH^5 T log T log|A|) + dH^3 log T + sqrt(beta H^4 T SEC(F,Pi,T))), corresponding to O(1/epsilon^2) sample complexity without reachability or coverage assumptions. The paper also gives hybrid-RL extensions: a non-optimistic algorithm NOAH (Algorithms 3 and 4) using offline data, and an optimistic hybrid version (Algorithm 5). Numerical experiments on a linear-MDP Tetris task and a deep hybrid-RL benchmark are reported.","tokens_in":57141,"tokens_out":23233,"duration_ms":231954,"significance":"If correct, the paper would resolve a well-known open problem: it would be the first actor-critic method with general function approximation and strategic exploration to achieve 1/epsilon^2 sample complexity and sqrt(T)-type regret. The rare-switching/reset mechanism and the hybrid-RL analysis are interesting and potentially reusable. The paper is also careful to position itself against prior work and provides extensive appendices plus reproducibility details for the experiments. However, the central Theorem 2 rests on an optimism proof that is invalid as written, because the pointwise-max critic lies outside the function class to which the completeness and concentration lemmas apply. This is a load-bearing gap that also affects the switching-cost lemma and the optimistic hybrid theorem, so the contribution is not established in its current form.","major_comments":[{"comment":"","section":"§4.2, Algorithm 2 (line 4); Lemma 14 (Appendix B.5.2)"},{"comment":"","section":"Appendix B.5.1, Lemma 13"},{"comment":"","section":"§5.2, Algorithm 5 and Theorem 5"}],"minor_comments":[{"comment":"","section":"Lemma 2"},{"comment":"","section":"Lemma 25"},{"comment":"","section":"Definition 4 and Theorem 4"},{"comment":"","section":"Assumption 3 and abstract"}],"recommendation":"reject","confidential_remarks":"The central gap is the pointwise-max critic: the paper never states or proves that F is closed under pointwise suprema, and the standard linear class example shows that the claimed optimism property is not a local technicality. Since the algorithm as written can select a critic outside F, the completeness assumption G=TF cannot be applied to it. A repair would require either a new assumption that excludes the linear-MDP examples used to motivate the result, or a substantially different optimism construction. I therefore do not see a local fix within the manuscript's current scope. The related-work positioning and the hybrid extensions are otherwise reasonable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Kevin, Wei, and Yuting's paper makes a bold claim: an actor-critic with general function approximation achieving 1/ε² sample complexity and √T regret. The architecture—rare-switching, Q*-targeting critic, policy resets, with SEC/Bellman-eluder complexity—is a plausible and natural resolution of an open problem. The hybrid RL extensions are also thoughtful. Credit where due: the problem selection is good, and the regret decomposition is standard and mostly carefully written. The paper is not a rehash.\n\nThe problem is in the optimism argument, and it is load-bearing. Algorithm 2 (and Algorithm 1, for that matter) chooses f^(t)_h(s,a) = argmax_{f∈F(t_last)} f_h(s,a) pointwise. That is the upper envelope of the confidence set, not necessarily a member of F. Lemma 14 then applies Lemma 17 to f^(t), using Assumption 2 (G = TF) to claim T f^(t) ∈ F(t_last). But Assumption 2 only covers Bellman backups of functions in F. For linear classes, the envelope is not in F; it is in a larger class. Lemma 17's premise fails, and with it the optimism step f^(t) ≥ T^π f^(t+1), the nonpositivity of the negative Bellman error term, and the final regret bound. The same issue appears in Lemma 7 for Algorithm 1, so the \"easy case\" is affected too, though that one can be repaired by the closure-under-truncated-sums assumption that the authors introduce for the policy class.\n\nThe reader's report flagged uncertainty around completeness; the stress-test pinpoints the sharper failure. I agree with the reader's conditional verdict, but I would go further: as written, Theorem 2 is unproven. The fix is not obvious, since assuming F closed under pointwise suprema would rule out linear classes and make the result much less interesting. The authors need to either change the algorithm so the selected optimistic function lies in F, or add a completeness assumption covering the envelope class.\n\nOther soft spots are minor: Lemma 25's statement is ambiguous as noted, Lemma 2 has a misstated covering number, and the \"optimal\" in the title overclaims—no lower bound specific to actor-critics is proven. These don't matter much next to the main gap.\n\nIf the optimism gap is fixed, this could be a strong paper. As it stands, it deserves a serious referee—the idea is important enough to be worth the effort—but it needs major revision. I would not cite the main theorem in its current form.","headline":"The paper's main theorem is unproven: the optimism argument applies completeness to a pointwise envelope that need not belong to F, so the claimed 1/ε² guarantee currently rests on a gap.","tokens_in":57698,"tokens_out":4065,"would_cite":false,"duration_ms":40933,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T05","90C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"An actor-critic algorithm achieves optimal $1/\\epsilon^2$ sample efficiency under general function approximation when strategic exploration is needed.","keywords":["actor-critic algorithms","sample complexity","regret bounds","general function approximation","optimistic exploration","rare-switching","hybrid reinforcement learning","Bellman eluder dimension"],"falsifier":"Run NORA on an MDP with a function class $\\mathcal{F}$ that contains $Q^*$ but is not closed under Bellman backups, and log the pointwise optimism check $f^{(t)}_h(s,a) \\ge (T f^{(t)}_{h+1})(s,a)$ on every visited state-action pair at every update; a single violation on a reachable pair, or a number of critic updates growing linearly in $T$ instead of $O(dH\\log T)$, would contradict Lemma 14 and hence Theorem 2.","tokens_in":56575,"feed_emoji":"🤖","tokens_out":7231,"duration_ms":66558,"temperature":0.7,"pith_summary":"The paper claims to resolve an open problem in reinforcement learning: no actor-critic algorithm with general function approximation was previously known to find an $\\epsilon$-optimal policy with $O(1/\\epsilon^2)$ sampled trajectories when the agent must explore strategically. It introduces NORA, an optimistic actor-critic that learns an off-policy critic targeting the optimal value function $Q^*$, updates the critic only rarely, and resets the actor policy after each critic update. Under standard realizability and completeness assumptions and a bounded Bellman eluder dimension, NORA achieves $O(\\sqrt{dH^5T\\log T\\log|\\mathcal{A}|} + \\sqrt{\\beta H^4T \\,\\mathrm{SEC}(\\mathcal{F},\\Pi,T)})$ regret, which translates into the desired $1/\\epsilon^2$ sample complexity. The paper further shows that adding offline data yields a non-optimistic hybrid actor-critic with $\\sqrt{T}$ regret when the offline dataset satisfies a single-policy concentrability condition. If correct, these results constitute the first optimal-rate guarantee for policy-based methods in this regime.","feed_headline":"NORA attains optimal actor-critic sample efficiency","feed_subtitle":"Rare-switching critics targeting Q*, plus policy resets, close an open problem in policy-based RL.","key_machinery":"The load-bearing mechanism is the switch from a critic that targets the current policy $\\pi^{(t)}$ to one that targets the optimal value $Q^*$, combined with a rare-switching schedule. This makes the Bellman operator time-invariant, so the auxiliary class needed for completeness shrinks from $(T\\Pi)^T\\mathcal{F}$ to $\\mathcal{T}\\mathcal{F}$, and the log-covering number no longer grows with the number of actor updates. The number of critic updates is controlled by the squared distributional Bellman eluder dimension, the largest $d$ such that a sequence of Bellman errors can be extrapolated from past data; the paper shows at most $O(dH\\log T)$ updates occur. Policy resets to uniform after each update compensate for the actor lagging behind the changing greedy policy, and the higher learning rate absorbs the extra reset cost. The mirror-ascent update $\\pi^{(t+1)}_h(\\cdot|s)\\propto \\pi^{(t)}_h(\\cdot|s)\\exp(\\eta f^{(t)}_h(s,\\cdot))$ is what converts the critic values into a tractable tracking-error bound.","core_discovery":"On its own terms, the paper's central claim is that strategic exploration in actor-critic methods with general function approximation can be made statistically optimal by having the critic target $Q^*$ rather than the value of the current policy. NORA maintains a confidence set of critics whose squared temporal-difference error is close to minimal, plays the optimistic upper envelope $f^{(t)}_h(s,a)=\\sup_{f\\in\\mathcal{F}^{(t_{\\mathrm{last}})}} f_h(s,a)$, and updates the policy by multiplicative-weights mirror ascent. Because the Bellman backup of any $\\mathcal{F}$-function under the greedy operator lies in the auxiliary class $\\mathcal{T}\\mathcal{F}$, the confidence set admits $T^\\pi_h f^{(t)}_{h+1}$, so Lemma 14 gives optimism $f^{(t)}_h \\ge T^\\pi_h f^{(t)}_{h+1}$ for every $\\pi$; the negative Bellman error term in the regret decomposition is then nonpositive. Rare-switching keeps the number of critic updates at $O(dH\\log T)$, and policy resets plus an enlarged learning rate control the tracking error of the actor relative to the greedy policy $\\pi_{f^{(t)}}$. The result is the regret bound in Theorem 2 and sample complexity $N\\ge \\Omega(dH^5\\log T\\log|\\mathcal{A}|/\\epsilon^2 + H^4\\beta\\,\\mathrm{SEC}(\\mathcal{F},\\Pi,T)/\\epsilon^2)$.","pith_inferences":["If the rare-switching insight transfers to practice, deep actor-critic implementations should update the critic only when the temporal-difference error moves a confidence bound, and reset or reinitialize the policy after large critic changes; this could reconcile the success of delayed-target tricks in DDPG and TD3 with theory.","The dependence on $\\mathcal{T}\\mathcal{F}$ completeness suggests that expressive, closed-under-Bellman-backup function classes, such as sufficiently wide networks or classes with built-in value-iteration layers, may be needed to realize the rate in practice; otherwise the optimism step can fail silently.","A direct testable prediction of the theory is that NORA's regret should scale as the square root of the Bellman eluder dimension times the horizon and $T$, and that removing any one ingredient—optimism, rare switching, or policy resets—should degrade the bound.","In the hybrid setting, the theory predicts a smooth trade-off: as more offline data accumulates, the required size of the online exploration region shrinks, so the same total regret can be achieved with fewer online samples; this is a concrete prescription for offline-to-online fine-tuning schedules."],"forward_implications":["Actor-critic algorithms with general function approximation can reach $\\tilde{O}(\\sqrt{T})$ regret and $1/\\epsilon^2$ sample complexity without reachability or coverage assumptions, matching the best rates previously known only in tabular or linear settings.","Targeting $Q^*$ instead of $Q^{\\pi^{(t)}}$ keeps optimism valid under rare critic updates, so delayed or slowly updated critics do not destroy the exploration guarantee.","The policy-reset trick limits the cost of reacting to rare critic updates to $O(dH\\log T)$, which is dominated by the main $\\sqrt{T}$ regret term.","With offline data satisfying a single-policy concentrability bound, optimism can be dropped entirely while retaining $\\sqrt{T}$ regret, provided $N_{\\mathrm{off}}\\ge c^*_{\\mathrm{off}}dH^4/\\epsilon^2$.","Hybrid data can be partitioned into offline and online regions, and the regret bound improves when offline coverage is good, giving a formal sense in which offline pretraining accelerates online actor-critic fine-tuning."],"supporting_citations":[{"why":"Supplies the GOLF confidence-set algorithm, the Bellman eluder dimension, and the optimism machinery that NORA adapts to actor-critics.","marker":"Jin et al. (2021a)"},{"why":"Supplies the sequential extrapolation coefficient and the change-of-measure argument used to bound Bellman error under the actor's occupancy.","marker":"Xie et al. (2022)"},{"why":"Supplies the rare-switching framework and the switching-cost bound that limits NORA to $O(dH\\log T)$ critic updates.","marker":"Xiong et al. (2023)"},{"why":"Supplies the covering-number lemma for the policy class under mirror-ascent updates, the quantity that DOUHUA controls and NORA avoids.","marker":"Zhong and Zhang (2023)"},{"why":"Supplies the optimistic-policy-optimization regret decomposition and mirror-ascent tracking-error analysis used in both algorithms.","marker":"Cai et al. (2024)"},{"why":"Establishes the $1/\\epsilon^3$ sample-complexity baseline for optimistic natural policy gradient that Theorem 2 improves to $1/\\epsilon^2$.","marker":"Liu et al. (2023b)"},{"why":"The linear-MDP rate-optimal policy-optimization result that independently uses policy resets and motivates the rare-switching design.","marker":"Cassel and Rosenberg (2024)"},{"why":"Supplies the partial all-policy concentrability coefficient and the offline-online partition argument used in Theorem 5.","marker":"Tan and Xu (2024)"},{"why":"The hybrid policy-gradient baseline requiring $1/\\epsilon^6$ samples; the paper contrasts its regret model with the standard one-sample-per-round setting.","marker":"Zhou et al. (2023)"}],"fun_headline_variants":["Actor-critic achieves optimal sample efficiency","Rare-switching actor-critic solves open problem","Optimal actor-critic via Q-star targeting","Actor-critic hits O(1/ϵ²) sample complexity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument's load-bearing premise is generalized completeness: the critic's function class must be rich enough that every one-step look-ahead value computed from any critic it contains is again representable in the auxiliary class; if even one such look-ahead value falls outside the class, the optimism inequality that makes the negative Bellman error vanish can fail.","fun_headline_variants_meta":{"raw":{"variants":["Actor-critic achieves optimal sample efficiency","Rare-switching actor-critic solves open problem","Optimal actor-critic via Q-star targeting","Actor-critic hits O(1/ϵ²) sample complexity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000577,"raw_usage":{"total_tokens":2842,"prompt_tokens":1187,"completion_tokens":1655,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":803,"completion_tokens_details":{"reasoning_tokens":1593}},"tokens_in":803,"tokens_out":1655,"duration_ms":13348,"temperature":1.0,"reasoning_tokens":1593,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:46:15.436808+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run NORA on an MDP with a function class $\\mathcal{F}$ that contains $Q^*$ but is not closed under Bellman backups, and log the pointwise optimism check $f^{(t)}_h(s,a) \\ge (T f^{(t)}_{h+1})(s,a)$ on every visited state-action pair at every update; a single violation on a reachable pair, or a number of critic updates growing linearly in $T$ instead of $O(dH\\log T)$, would contradict Lemma 14 and hence Theorem 2.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the rare-switching framework and the switching-cost bound that limits NORA to $O(dH\\log T)$ critic updates."},{"cited_title":"and Zhang, T","cited_arxiv_id":null,"evidence_quote":"Supplies the covering-number lemma for the policy class under mirror-ascent updates, the quantity that DOUHUA controls and NORA avoids."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the optimistic-policy-optimization regret decomposition and mirror-ascent tracking-error analysis used in both algorithms."},{"cited_title":"and Rosenberg, A","cited_arxiv_id":null,"evidence_quote":"The linear-MDP rate-optimal policy-optimization result that independently uses policy resets and motivates the rare-switching design."}],"review_version":1}