{"id":"c069240b-849b-46ee-9293-bb089fd75705","arxiv_id":"2507.22854","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Improved classical and quantum regret bounds for reinforcement learning with a generative model, including a new expected-regret measure under which quantum algorithms achieve polylogarithmic regret for infinite-horizon tasks.","lead":"This paper gives new classical and quantum algorithms for learning Markov decision processes when the agent can periodically query a simulator without accruing regret. The quantum algorithms achieve logarithmic-in-time regret for finite-horizon tasks and, under a newly defined 'expected regret' measure, also for infinite-horizon average-reward tasks, improving on earlier quantum bounds.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Infinite-horizon poly(log T) claims require a 1-stage span-contraction assumption that the abstract and Results 4–5 omit; weak communicability alone does not imply it.","rationale":"The paper's genuine contributions are the quantum finite-horizon regret bounds (Theorem 26), which match or improve prior works while keeping poly(log T) in T within a well-specified hybrid model, and the detailed generative-model algorithms in Section 4. I did not find an internal algebraic error in the main proofs: the variance-reduction steps, the quantum-oracle failure analysis in Theorem 20, and the doubling-trick regret accounting all check out at the level of constant factors. The expected-regret measure is unusual but explicitly defined and worst-case over states, so it is not a hidden weakening; the real issue is scope. The reader's weakest_assumption — that the infinite-horizon results require a 1-stage ν-span contraction not implied by weak communicability — is exactly the load-bearing concern. The deterministic two-state cycle demonstrates that the abstract and Results 4–5 claim more than the theorems deliver. This does not invalidate the conditional contribution, but it reinforces the CONDITIONAL verdict and requires the authors either to state the stronger assumption in the abstract and results or to develop a J-stage-contraction version of Theorems 23–30. No change to the reader's verdict is needed.","tokens_in":61225,"tokens_out":12925,"duration_ms":159782,"concrete_test":"Construct the finite MDP with S={1,2}, A={1}, r(1)=1, r(2)=0, p(2|1)=1, p(1|2)=1, and verify it satisfies the advertised preliminaries: it is weakly communicating, has g*=1/2 and spp(h*)=0, so Λ=0. Then compute L: (Lu)(1)=1+u(2), (Lu)(2)=0+u(1); for any constant c, L(c)=c+(1/2)e, and on span-zero functions spp(Lu−Lv)=spp(u−v), so no ν<1 span contraction exists for L or any iterate. This single example settles that the abstract's and Results 4–5's ‘weakly communicating’ phrasing covers MDPs for which Theorems 23–30 do not apply, confirming the advertised infinite-horizon quantum advantage is narrower than stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The finite-horizon results are credible within the hybrid model, but the paper's central infinite-horizon contribution — poly(log T) regret under the new expected-regret measure (Theorem 30) — is gated by an assumption missing from the front-facing claims. Theorems 23, 24, 27, 28, 29, and 30 all begin with: “Assume the optimal Bellman operator L of M is a 1-stage ν-span contraction (Definition 9),” whereas Results 4–5 and the abstract advertise bounds for “weakly communicating MDPs with spp(h*) ≤ Λ.” Weak communicability (Section 2.3) does not imply any span contraction of L: a deterministic two-state cycle 1→2→1 with rewards 1 and 0 is weakly communicating, has spp(h*)=0, and yet satisfies spp(Lu−Lv)=spp(u−v) for span-zero perturbations, so no 1-stage ν-span contraction with ν<1 exists, and the same is true for every power L^J. The proofs of Lemma 21 and Theorem 22, which drive the stopping criterion in Algorithm 4/5, explicitly require the 1-stage contraction to control spp(u_t−h*); for periodic or multi-chain weakly communicating MDPs that control is unavailable. The paper cites Puterman Theorems 8.5.2 and 8.5.3, which give sufficient conditions for J-stage span contractions, not 1-stage, so the imposed assumption is not subsumed by the stated “weakly communicating” regime. This is a scoping overclaim rather than an internal inconsistency: the theorems state the assumption, but the abstract and Results 4–5 do not, so the advertised infinite-horizon exponential quantum speedup holds only for a strictly narrower subclass.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a hybrid exploration-generative reinforcement learning model in which the agent alternates between classical regret-accumulating exploration phases and free generative phases where a simulator oracle can be queried. It supplies classical and quantum generative-model algorithms for finite-horizon backward induction and for infinite-horizon average-reward value iteration, and then embeds these in online algorithms with a doubling schedule. The headline results are an O~(√(HSAT)) classical and an O~(S min{HA, H^2√A} log T) quantum finite-horizon regret, and, for average-reward MDPs, a new expected-regret measure under which the quantum algorithm attains polylog T regret. The finite-horizon proofs are detailed, internally consistent, and the query counts in Theorems 17–20 and 25–26 match the stated policy accuracies and regret sums.","tokens_in":61593,"tokens_out":9892,"duration_ms":121621,"significance":"If the infinite-horizon results are read with their stated span-contraction assumption, the paper is a substantial contribution: it extends the polylog-T quantum regret regime of Zhong et al. and Ganguly et al. to finite-horizon MDPs with improved state- and action-space factors, and it proposes a new expected-regret criterion that sidesteps the Azuma-Hoeffding √T term in infinite-horizon settings. The manuscript is unusually careful: the oracle models are explicit, the supporting lemmas are proved in place, and the comparison to the concurrent work of Luo et al. is honest. The central weakness is a scope mismatch: the advertised infinite-horizon results are stated for weakly communicating MDPs with bounded bias span, but Theorems 23–30 require a 1-stage span-contraction assumption that weak communicability does not imply.","major_comments":[{"comment":"Results 4 and 5 and the abstract advertise regret bounds for 'weakly communicating MDPs with spp(h*) ≤ Λ', but Theorems 23, 24, 27, 28, 29, and 30 each require the additional assumption that the optimal Bellman operator L is a 1-stage ν-span contraction (Definition 9). This assumption is load-bearing: Lemma 21 and Theorem 22 use it to control spp(u_t − h*) and to justify the stopping criterion of Algorithms 4 and 5. Weak communicability does not imply any J-stage span contraction; for example, the deterministic two-state cycle with reward 1 in both states is weakly communicating with spp(h*) = 0, yet satisfies spp(Lu − Lv) = spp(u − v) for all u, v, so no power of L is a contraction. The cited Puterman theorems (8.5.2 and 8.5.3) give sufficient conditions for J-stage contractions under additional aperiodicity and unichain assumptions, not a consequence of weak communicability. The theorem statements themselves are internally consistent, but the front-facing claims in the abstract and Results 4–5 overstate the scope; please restate those claims with the span-contraction assumption and add a discussion of the restriction.","section":"§1.1, Results 4–5; Theorems 23–30"}],"minor_comments":[{"comment":"The abstract as provided to me states that an 'infinite-horizon discounted regret bound' is brand new, but the main text treats only finite-horizon and infinite-horizon undiscounted average-reward MDPs; please align the abstract with the actual content.","section":"Abstract"},{"comment":"The claim that the quantum expected regret is 'exponentially better compared to classical algorithms' is a comparison to the classical algorithm of this paper (Theorem 29), since no lower bound for Regret^E_∞ in the same model is proved; please qualify the comparison target explicitly.","section":"Result 5 and §1.1.2"},{"comment":"The pseudocode has duplicated line numbers (two lines labelled '3:') and the quantum branch does not specify in the input block whether Algorithm 2 or Algorithm 3 is invoked; please fix the pseudocode and state the oracle used.","section":"Algorithm 6"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is in scope for a serious ML/quantum algorithms journal, and the finite-horizon part appears sound. The main fix is scoping the infinite-horizon claims: the span-contraction assumption should appear in the abstract and in Results 4–5, or the paper should explicitly discuss the narrower class of MDPs for which the assumption holds. I would also ask the authors to state clearly that the expected-regret separation is an algorithm-to-algorithm comparison in the absence of a lower bound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take after reading it through. The finite-horizon half is the strong part: the quantum backward induction algorithms (Algorithms 2 and 3) give query complexity min{H^2 S A/ε, H^3 S√A/ε} under a generative model, which beats the classical bound and matches the concurrent work by Luo et al. that they acknowledge. The online regret bound S min{HA, H^2√A} poly-log T is a genuine improvement over prior quantum results. The proofs are complete, self-contained, and the parameter tracking checks out; I did not find a hidden circularity.\n\nInfinite horizon is where I agree with the skeptic. Theorems 23–30 all start by assuming the optimal Bellman operator is a 1-stage ν-span contraction, but Results 4–5 and the abstract advertise 'weakly communicating' MDPs with spp(h*) ≤ Λ. Weak communicability does not imply that contraction, as the two-state cycle example shows: it's weakly communicating with zero bias span, but L is not a contraction in span for any power. So the advertised poly(log T) expected regret applies to a strictly narrower class. The theorems themselves are honest; the scoping in the summary is not. That is a fixable overclaim, not a fatal flaw.\n\nThe expected regret measure is a mixed bag. It removes the random-walk √T term by comparing to min_x g^{d_t^∞}(x), which is a defensible way to separate policy quality from path noise, but it is a different benchmark, so the 'exponential advantage' is partly built into the definition. The abstract's mention of 'discounted regret' looks like a leftover from an earlier draft; the body is entirely average-reward. Minor, but should be cleaned up.\n\nBottom line: this deserves a serious referee. The finite-horizon results are publishable as is; the infinite-horizon claims need re-scoping and the regret measure should be argued on its own terms. I would send it to review.","headline":"Solid finite-horizon quantum RL results; the infinite-horizon poly(log T) speedup is real but conditional on a span-contraction assumption the front matter omits.","tokens_in":62147,"tokens_out":3634,"would_cite":true,"duration_ms":41223,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","90C40","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Splitting online RL into exploration and free generative phases makes quantum regret polylogarithmic in the horizon.","keywords":["reinforcement learning","Markov decision processes","quantum algorithms","regret bounds","generative model","average reward","value iteration","quantum mean estimation"],"falsifier":"Take a weakly communicating infinite-horizon MDP with bias span $\\operatorname{spp}(h^*)\\le\\Lambda$ whose optimal Bellman operator is not a one-stage span contraction, and run the quantum expected-regret version of Algorithm 7; if the regret is no longer polylogarithmic in $T$ but reverts to a $\\sqrt{T}$-scale, that identifies exactly which assumption carries the advertised infinite-horizon advantage. For the finite-horizon claim, give the online agent free generative calls and record the oracle query count; the bound predicts a near-optimal policy after $\\tilde{O}(\\min\\{H^2SA/\\varepsilon, H^3S\\sqrt{A}/\\varepsilon\\})$ queries, and failing to reach $\\varepsilon$-optimality on an instance with Hölder-continuous transitions would refute the planner guarantee.","tokens_in":60994,"feed_emoji":"🎲","tokens_out":9442,"duration_ms":100614,"temperature":0.7,"pith_summary":"The paper tries to establish that giving an online reinforcement-learning agent occasional free access to a simulator, in what it calls a hybrid exploration-generative model, changes the regret landscape. The agent alternates ordinary exploration, during which regret is incurred, with generative phases in which it may query the true transition probabilities at no regret cost. The authors show that in this model both classical and quantum agents can compute near-optimal policies directly instead of building confidence sets, and they prove regret bounds for finite- and infinite-horizon Markov decision processes. The headline results are quantum: finite-horizon regret that is polylogarithmic in the time horizon $T$, breaking the classical $\\tilde{O}(\\sqrt{T})$ barrier, and, under a newly introduced expected-regret measure, infinite-horizon average-reward regret that is also polylogarithmic in $T$. If correct, the paper identifies simulator access as the resource that turns the usual exploration-exploitation trade-off into a much cheaper bookkeeping problem.","feed_headline":"Quantum RL regret drops to logarithmic when a simulator is nearby","feed_subtitle":"Pausing real play to query a simulator beats the sqrt(T) classical regret barrier for RL agents.","key_machinery":"The load-bearing object is the hybrid exploration-generative learning model of Section 3. During an exploration phase the agent acts classically and accumulates regret; during a generative phase it may use a classical sampling oracle $C_p$ or a quantum sampling oracle $O_p$ and its inverse at most a number of times proportional to the length of the preceding exploration phase. The paper's online algorithms are the generative-model planners run inside this loop: classical backward induction, quantum backward induction with multivariate quantum mean estimation, a simpler quantum backward induction using quantum max-finding, and classical and quantum value iteration for infinite-horizon MDPs. Convergence for the infinite-horizon case rests on the one-stage $\\nu$-span contraction property of the optimal Bellman operator, which lets robust value iteration be stopped once the span of successive iterates is small. The new expected regret replaces the observed path's reward by the average reward of the current decision rule, filtering out the $\\sqrt{T}$ fluctuation term that otherwise enters through concentration inequalities.","core_discovery":"The central claim, stated on the paper's own terms, is that the standard online RL paradigm can be replaced by a two-phase scheme: explore in real time to earn the right to use a generative model, then use quantum mean estimation and quantum max-finding on oracle access $O_p$ to compute an approximately optimal policy that will be used until the next update. For finite-horizon MDPs (Theorem 26) the resulting quantum regret is $\\tilde{O}(S \\min\\{HA, H^2\\sqrt{A}\\log(HS)\\} \\log(T/H) \\log(HSA))$, where $S$ is the number of states, $A$ the number of actions, and $H$ the horizon; this is logarithmic in $T$ and improves the prior quantum logarithmic-regret bounds in $S,A,H$. For infinite-horizon average-reward MDPs (Theorem 30), the paper defines expected regret $R^E_\\infty(T)$ by comparing each employed decision rule's average reward to the optimal gain, and proves $\\tilde{O}(\\Lambda S\\sqrt{A}\\log^2 T \\log(SAT) \\log(ST))$, again polylogarithmic in $T$, while classical in-path regret in the same model remains $\\tilde{O}(\\Lambda\\sqrt{SAT})$. The infinite-horizon results require the optimal Bellman operator to be a one-stage span contraction, an assumption stronger than weak communicability.","pith_inferences":["The hybrid model places the entire quantum advantage in the generative phase; a natural test is to charge a positive cost per simulator query and re-derive the regret, since the polylog $T$ bound may then translate into a large hidden simulator budget.","The new expected-regret measure could be applied retroactively to classical algorithms; if their $\\sqrt{T}$ term also shrinks under this measure, part of the classical horizon dependence is a concentration artifact rather than an information-theoretic cost.","The span-contraction assumption is the narrow neck of the infinite-horizon result; finding natural classes of weakly communicating MDPs that satisfy it, or proving the bound without it, would settle how much of the advertised advantage survives outside that class.","The near-matching lower bound for finite-horizon generative planning that the authors mention leaves a concrete open question: close the gap between the $\\Omega(H^{1.5}S\\sqrt{A}/\\varepsilon)$ lower bound and the $\\tilde{O}(\\min\\{H^2SA/\\varepsilon, H^3S\\sqrt{A}/\\varepsilon\\})$ upper bound."],"forward_implications":["Finite-horizon quantum regret becomes polylogarithmic in $T$ with the stated $S,A,H$ factors, exponentially better in $T$ than the classical $\\tilde{O}(\\sqrt{HSAT})$ bound under the same model.","For infinite-horizon average-reward MDPs, the new expected regret separates policy suboptimality from path randomness: a quantum agent can have expected regret polylogarithmic in $T$ while in-path regret still carries a $\\sqrt{T}$ term.","The classical version of the hybrid model also beats or matches prior classical regret bounds, improving for example the infinite-horizon finite-state bound from $\\tilde{O}(\\Lambda\\sqrt{S^2AT})$ to $\\tilde{O}(\\Lambda\\sqrt{SAT})$.","Because the online algorithms never estimate transition probabilities or maintain confidence sets, the entire optimism-in-the-face-of-uncertainty machinery can be removed whenever generative access is available.","Compact state spaces are handled by discretization into $1/n$-nets under Hölder continuity, so the regret bounds extend to continuous settings at the price of factors like $T^{D/(D+\\alpha)}$."],"supporting_citations":[{"why":"Supplies the classical near-optimal generative backward induction whose variance-reduction structure the quantum finite-horizon algorithms quantize.","marker":"[SWW`18]"},{"why":"Shows how to quantize value iteration with quantum mean estimation for discounted MDPs; the paper adapts this template to finite-horizon and average-reward MDPs.","marker":"[WSK`21]"},{"why":"Prior quantum RL with logarithmic regret in a similar hybrid generative model; the paper's finite-horizon bound improves its S,A,H factors.","marker":"[ZHX`24]"},{"why":"Other prior quantum episodic RL work with logarithmic regret that serves as a baseline comparison.","marker":"[GWW A23]"},{"why":"Classical regret bound for weakly communicating MDPs that the infinite-horizon results improve in the finite-state case.","marker":"[BT09]"},{"why":"Source of MDP theory used throughout: optimality equations, span seminorm, span contraction, and weak communicability.","marker":"[Put14]"},{"why":"Quantum mean estimation subroutine used to estimate Bellman expectations with fewer queries.","marker":"[KO23]"},{"why":"Multivariate quantum mean estimation used to estimate all H mean values in one pass, improving the horizon dependence.","marker":"[CHJ22]"},{"why":"Improved multivariate quantum mean estimator used in the quantum finite-horizon algorithm.","marker":"[Tan25]"}],"fun_headline_variants":["Simulator access lets quantum RL beat the sqrt(T) regret limit","Quantum RL breaks sqrt(T) barrier with occasional simulator queries","A little simulator access buys quantum RL a polylog T regret","Quantum RL with a simulator achieves polylog T regret"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the agent can, from time to time, query the true environment for free through a simulator during generative phases; for the infinite-horizon expected-regret result this is joined by the assumption that the optimal Bellman operator is a one-stage span contraction, which is stricter than the weakly communicating condition.","fun_headline_variants_meta":{"raw":{"variants":["Simulator access lets quantum RL beat the sqrt(T) regret limit","Quantum RL breaks sqrt(T) barrier with occasional simulator queries","A little simulator access buys quantum RL a polylog T regret","Quantum RL with a simulator achieves polylog T regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001165,"raw_usage":{"total_tokens":4874,"prompt_tokens":1051,"completion_tokens":3823,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":667,"completion_tokens_details":{"reasoning_tokens":3752}},"tokens_in":667,"tokens_out":3823,"duration_ms":29888,"temperature":1.0,"reasoning_tokens":3752,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T11:13:46.512256+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a weakly communicating infinite-horizon MDP with bias span $\\operatorname{spp}(h^*)\\le\\Lambda$ whose optimal Bellman operator is not a one-stage span contraction, and run the quantum expected-regret version of Algorithm 7; if the regret is no longer polylogarithmic in $T$ but reverts to a $\\sqrt{T}$-scale, that identifies exactly which assumption carries the advertised infinite-horizon advantage. For the finite-horizon claim, give the online agent free generative calls and record the oracle query count; the bound predicts a near-optimal policy after $\\tilde{O}(\\min\\{H^2SA/\\varepsilon, H^3S\\sqrt{A}/\\varepsilon\\})$ queries, and failing to reach $\\varepsilon$-optimality on an instance with Hölder-continuous transitions would refute the planner guarantee.","supporting_citations":[],"review_version":1}