{"id":"8dcd1641-7476-482c-b0ad-44e4ab70201a","arxiv_id":"2512.14617","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"QR-MAX reuses environment-transition counts across reward-automaton states, achieving a PAC bound for non-Markovian rewards with one less factor of automaton size than R-MAX.","lead":"The paper introduces QR-MAX, a model-based reinforcement learning algorithm for tasks whose rewards depend on the whole history rather than just the current state. It separates learning of the environment dynamics from learning of a history-tracking automaton, giving a provable sample-complexity improvement over standard methods.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Continuous Bucket-QR-MAX PAC guarantee rests on an unverified SimHash-diameter assumption (A.5/Remark A.7); discrete QR-MAX claim appears intact.","rationale":"The reader's central verdict is CONDITIONAL, and I agree with that recommendation. The discrete QR-MAX PAC bound is the paper's headline contribution; it is plausible and I could not isolate a decisive technical error. The weakest point I see is the continuous Bucket extension: the PAC theorem is conditional on Assumption A.5, and the paper's own Remark A.7 says the probability that SimHash satisfies that assumption is left for future work. That is a real, self-declared gap in the continuous guarantee. The q-observability assumption flagged by the reader is less compelling as a weakness: it is standard in reward-machine RL and the paper states it explicitly; if it fails, the model-based approach is not applicable, but that is a scope condition rather than an internal flaw. Therefore the load-bearing concern is the unverified SimHash-diameter assumption; it does not change the CONDITIONAL verdict, and the discrete claim remains supported.","tokens_in":22423,"tokens_out":27825,"duration_ms":646134,"concrete_test":"Analyze the SimHash partition empirically and theoretically: for the continuous Office-World inputs (or a worst-case L-Lipschitz MDP), fix hash parameters (L, d_h) and estimate the distribution of maximum bucket diameter over all visited buckets; compare with the required φ ≤ cε(1−γ)/L. If δ_LSH (frequency of A.5 violation) is non-negligible or if |B| grows super-polynomially with the horizon, the conditional PAC bound has no practical instantiation and BUCKET-QR-MAX should be presented as an empirical method rather than a PAC-guaranteed one. Alternatively, re-derive Theorem A.6 replacing Assumption A.5 with a concrete high-probability bound on SimHash collisions; if that derivation requires an extra factor in |B| or an unquantified δ_LSH, the continuous PAC claim is not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5 / Appendix Theorem A.6 gives a PAC-MDP bound for BUCKET-QR-MAX only under Assumption A.5: every SimHash bucket has diameter ≤ φ and the continuous MDP is L-Lipschitz. This assumption is not established for SimHash. Remark A.7 explicitly concedes that SimHash does not deterministically guarantee a given diameter and defers the analysis of δ_LSH—the probability that the induced partition violates A.5—to future work. Hence the continuous guarantee as stated is conditional on a property that the algorithm neither verifies nor controls. Moreover the sample bound depends on |B|, the number of buckets, which is data-dependent and can grow with the observation stream; without a bound on |B| and δ_LSH, the claimed polynomial sample complexity may not hold for the underlying continuous MDP. This is the load-bearing weakness of the paper's broader claims. For the discrete QR-MAX result, I do not find a similarly decisive flaw: the proof sketch is terse but follows the R-MAX template, and the observability of q is a standard, explicitly stated assumption in the reward-machine setting.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes QR-MAX, a model-based RL algorithm for discrete-action NMRDPs whose non-Markovian reward is specified by a deterministic finite automaton (reward machine). The key idea is to factorize the transition model into the environment component P(s'|s,a) and the automaton component P(q'|q,s'), learning them with separate counters and optimistic value iteration. The authors claim a PAC-MDP bound of O((|S||A|+|S||Q|)/(ε^3(1−γ)^3)) interactions, removing a factor of |Q| relative to running R-MAX on the product S×Q MDP. The paper also extends the approach to continuous state spaces via SimHash-based bucketization (Bucket-QR-MAX), for which a conditional PAC bound is stated under a bounded-discretization assumption. Experiments on gridworlds with reward machines report large sample-efficiency gains over R-MAX, QRM, UCBVI, PSRL, and OPSRL, with code released.","tokens_in":22733,"tokens_out":13231,"duration_ms":108376,"significance":"If the discrete QR-MAX PAC bound is correct, this is a meaningful structural contribution: it is, to my knowledge, the first model-based algorithm for discounted NMRDPs that explicitly decouples environment and automaton dynamics in the sample-complexity analysis, and the improvement — from |S||Q||A| to |S||A|+|S||Q| — is substantial and well motivated. The experimental comparison is extensive, uses a statistically principled stopping rule, and reports large margins over strong baselines. The continuous Bucket-QR-MAX variant is a useful practical heuristic with an honest conditional statement, but its formal guarantee is currently not established for the actual SimHash algorithm.","major_comments":[{"comment":"The PAC-MDP proof is incomplete in a load-bearing way. Lemma A.3 is justified in one sentence: it invokes optimism, a per-step model error bound β, and planning horizon T, but does not state or prove a simulation lemma showing that the greedy policy in the factorized optimistic model has true value within ε of V*. The proof of Theorem A.4 then asserts that non-ε-optimal steps occur only while visiting unknown pairs, but it never proves that every step taken when the current (s,q,a) is known is ε-optimal; it also mentions a 'last T-step value-iteration sweep' in §4.2, which is computation and not an environment interaction. The counting argument needs to be made precise, e.g., in the style of Strehl et al. (2009), with an explicit known-state decomposition and a proof that the induced known model is ε-optimistic.","section":"§4.2, Appendix §A.3–A.4"},{"comment":"The stated threshold m_E = ⌈8 R_max^2 β^{-2} ln(2|S||A|/δ)⌉ is insufficient for the transition-estimation bound used in Lemma A.2. The appendix's Weissman-based condition is (2|S|) exp(−m_E β^2/(2 R_max^2)) ≤ δ/(2N_E), which forces a term proportional to |S| ln 2 inside the logarithm. As written, the displayed m_E does not satisfy the condition for large |S|, so the theorem's concentration part does not follow. The asymptotic eO claim can be repaired by enlarging m_E with a log|S| factor, but the exact statement in §4.2 is wrong and must be corrected.","section":"§4.2, threshold m_E / Lemma A.2"},{"comment":"The continuous PAC-MDP guarantee for Bucket-QR-MAX is conditional on Assumption A.5, which requires every SimHash bucket to have diameter ≤ φ and the dynamics/rewards to be L-Lipschitz. Remark A.7 explicitly concedes that SimHash does not deterministically guarantee such a diameter and defers the analysis of δ_LSH to future work. The sample bound also depends on |B|, which is data-dependent and can grow with the observation stream. Consequently the theorem does not provide a PAC guarantee for the actual algorithm on the underlying continuous MDP; at best it bounds the induced bucket MDP under an assumption the algorithm neither verifies nor controls. The paper should either give a high-probability bound on the partition diameter and on |B|, or clearly frame Bucket-QR-MAX as a heuristic/conditional extension rather than a PAC-MDP algorithm.","section":"§5, Appendix Theorem A.6, Remark A.7"}],"minor_comments":[{"comment":"Theorem numbering is inconsistent: §4.2 refers to 'Theorem A.1' for the discrete PAC bound, but the appendix labels it Theorem A.3/A.4; §5 refers to 'Theorem A.1' for Bucket-QR-MAX, but the appendix has Theorem A.6. Please renumber for consistency.","section":"Theorems/Appendix"},{"comment":"The appendix says 'full proofs' but Lemma A.3 and Theorem A.4 are proof sketches. Either expand them to full proofs or label them as sketches; the current phrasing overstates the rigor.","section":"Appendix §A"},{"comment":"The choice t_E=30 is justified only by a 'rule of thumb' for Gaussian means. This is informal and not tied to the theoretical threshold in §4.2; the discrepancy should be acknowledged, and the sensitivity of the results to t_E should be discussed.","section":"§6 / footnote 4"},{"comment":"When done==True in an environment step, the transition counts for (s',q') are updated before the episode reset. Confirm whether terminal transitions are included in the known-state analysis; if not, clarify the pseudocode.","section":"Algorithm A.1"},{"comment":"The memory entry for QR-MAX is listed as O(|S|^2|A|+|S||Q|), which appears to be missing the automaton-count term |S||Q|^2 or a factor of |Q|. Please make the memory accounting consistent with the algorithm's counters.","section":"Table 5"}],"recommendation":"major_revision","confidential_remarks":"The discrete QR-MAX direction is worthwhile and the central sample-complexity claim is plausible, but the current proof skeleton is not yet at journal rigor. The Bucket-QR-MAX result is honestly labeled as conditional, but as it stands the continuous guarantee is really a bound for an idealized partition, not for SimHash; this should be stated prominently or supported with a concrete δ_LSH analysis. I would ask for a major revision focused on completing the discrete PAC proof and reframing or strengthening the continuous result."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The discrete part of this paper is the real story. QR-MAX factorizes the product-MDP transition into environment dynamics P(s'|s,a) and automaton dynamics P(q'|s',q), then runs an R-MAX-style optimistic count-based algorithm on two separate counters. That is a genuine structural observation, and it buys a sample-complexity bound of O((|S||A|+|S||Q|)/eps^3(1-gamma)^3) instead of R-MAX on the product MDP's O(|S||Q||A|/eps^3(1-gamma)^3). The discrete proof follows the standard R-MAX template: Hoeffding and Weissman inequalities, optimism, and a counting argument. The appendix proof sketches are terse, but the discrete argument is coherent and, as far as I can tell, correct. The experiments support the claimed sample-efficiency gains, and the code is public. This appears to be the first model-based PAC-MDP algorithm for discrete-action NMRDPs that explicitly reuses environment transitions across automaton states, and it deserves a serious referee.\n\nThe soft spot is the continuous extension. Bucket-QR-MAX's PAC guarantee (Theorem A.6) is conditional on Assumption A.5: every SimHash bucket has diameter at most phi and the MDP is L-Lipschitz. The authors concede in Remark A.7 that SimHash does not deterministically guarantee the diameter and that the probability of violating A.5 is not analyzed. So the stated continuous guarantee is not yet a theorem about the original continuous MDP; it is a theorem about the induced bucket MDP, conditional on a partition property that the algorithm neither verifies nor controls. The bound also depends on |B|, which can grow with the observation stream. This is not fatal for the discrete contribution, but it is load-bearing for the paper's broader claims. The authors should either provide an actual LSH analysis with a tractable delta_LSH, or they should restate the continuous result as a heuristic with a much more modest claim.\n\nA few minor points: the observability of q is stated explicitly, which is standard for reward machines. The experimental comparison appears honest, though the horizon choices for the finite-horizon baselines are favorable to those methods, and the t-test stopping rule is unusual. The paper's own limitation statements are at least acknowledged, which I appreciate.\n\nBottom line: the discrete QR-MAX result is sound enough and novel enough for peer review. The continuous Bucket-QR-MAX section needs major revision before its claims as stated can be accepted. I would send the paper to referees rather than desk-reject, with explicit instructions to focus on the SimHash assumption or the need to soften the continuous theorem. I would cite the discrete result in my own work.","headline":"The discrete QR-MAX result is real and worth refereeing; the continuous Bucket-QR-MAX guarantee rests on an unproved SimHash assumption and should be softened or fixed.","tokens_in":784,"tokens_out":1621,"would_cite":true,"duration_ms":26801,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"By separating environment dynamics from the reward automaton, QR-MAX is the first model-based RL algorithm for non-Markovian rewards with a PAC sample bound that drops a |Q| factor.","keywords":["model-based reinforcement learning","non-Markovian reward decision processes","reward machines","PAC-MDP","sample complexity","factorized dynamics","SimHash discretization","continuous state spaces"],"falsifier":"Run QR-MAX on an NMRDP where the reward automaton state is unobservable and the automaton is not known a priori, so the agent cannot maintain q internally; if the algorithm still achieves ε-optimality without ever recovering q, the paper's assumption would be violated. Alternatively, fix |S| and |A|, vary |Q| from 2 to a large value, and measure the number of interactions to reach an ε-optimal policy; a superlinear (or multiplicative |Q|) growth would contradict the stated O(|S||A|+|S||Q|) bound.","tokens_in":22326,"feed_emoji":"🤖","tokens_out":5168,"duration_ms":40187,"temperature":0.7,"pith_summary":"QR-MAX is a model-based reinforcement learning algorithm for tasks whose rewards depend on the whole history rather than just the current state. The paper's central claim is that by splitting the dynamics into a Markovian environment transition and a deterministic reward-automaton update, an agent can learn an ε-optimal policy with O((|S||A|+|S||Q|)/ε^3(1−γ)^3) interactions — one fewer factor of |Q| than the standard R-MAX approach that treats the joint state as opaque. This is argued to be the first PAC guarantee for model-based RL on discrete-action non-Markovian reward decision processes, and a variant extends the same decoupling to continuous state spaces using SimHash buckets. A sympathetic reader would care because many real tasks — delivery sequences, patrols, assembly steps — are naturally non-Markovian, and the improvement means sample-hungry exploration is reduced without needing to know the reward machine in advance.","feed_headline":"QR-MAX removes a |Q| factor from PAC sample complexity","feed_subtitle":"First PAC guarantee for model-based RL on non-Markovian rewards: up to |Q|-fold fewer interactions.","key_machinery":"The load-bearing identity is the factored transition kernel P(s′,q′|s,q,a)=P(s′|s,a)P(q′|s′,q), where the first factor is Markovian and the second is a deterministic finite-state automaton (the reward machine) update. QR-MAX maintains four separate accumulators — environment transition counts, environment rewards, automaton transition counts, automaton rewards — and labels a component known only after its own threshold (t_E for the environment, t_Q for the automaton). Value iteration on the optimistic model uses only known components, leaving unknown entries at R_max/(1−γ), which is what makes optimism under uncertainty work while reusing each environment sample across all automaton states.","core_discovery":"The paper establishes that an NMRDP's transition model factorizes as P(s′|s,a)P(q′|s′,q): the environment's next state depends only on the current environment state and action, while the automaton's next state depends only on the automaton state and the observed next environment state. QR-MAX exploits this by keeping separate visit counters and thresholds for environment pairs (s,a) and automaton pairs (q,s′), so each learned environment transition is reused across every automaton state. With thresholds m_E and m_Q chosen as functions of the desired accuracy ε and confidence δ, the paper proves the greedy policy in the optimistic factored model is ε-optimal after at most N(ε,δ)=2/(1−γ)ε (|S|","pith_inferences":["The decoupling idea is orthogonal to factored-MDP and existing structure-aware methods, so it could plausibly be combined with posterior sampling or regret-minimization objectives to yield regret bounds with the same |Q| reduction.","The paper's t_Q=1 observation suggests that when the reward machine is deterministic and known, automaton learning is nearly free; an immediate testable extension is to stochastic reward machines, where the same threshold logic applies with a larger t_Q.","Because SimHash does not deterministically guarantee bucket diameter, the practical guarantee for Bucket-QR-MAX is probabilistic and depends on the unanalyzed δ_LSH term; a concrete next step is to bound this term via the LSH collision probabilities.","The one-to-two order-of-magnitude empirical gap over QRM hints that model-free algorithms might also benefit from sharing environment transition statistics across automaton states — a direction the paper leaves implicit."],"forward_implications":["If the central claim holds, model-based RL for non-Markovian tasks no longer needs to explore the joint state space S×Q as if it were opaque; every environment sample contributes to all automaton states.","The improved bound removes one multiplicative |Q| factor, which yields up to |Q|-fold sample savings when the automaton is comparable in size to the state space, and a smaller constant-factor saving otherwise.","Since a deterministic automaton is known after t_Q=1 visit, learning the reward machine's dynamics is essentially free in QR-MAX, unlike methods that must estimate transitions on the full product MDP.","The continuous Bucket-QR-MAX variant means the factorization benefit carries over to real-valued state spaces without manual grid design or neural approximators, provided the SimHash buckets are small enough and the dynamics are Lipschitz.","The algorithm provides the first PAC-MDP guarantee for model-based RL in discrete-action NMRDPs, giving a formal sample-complexity baseline that future structure-aware algorithms can be measured against."],"fun_headline_variants":["QR-MAX: first PAC guarantee for model-based RL on non-Markovian rewards","First PAC-efficient model-based RL for non-Markovian rewards","QR-MAX factorizes transitions to cut PAC sample complexity","Model-based RL for non-Markovian rewards: first PAC efficiency","QR-MAX: PAC-optimal model-based RL without Markovian assumptions"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"For the discrete guarantee, the load-bearing premise is that the agent observes or maintains the current automaton state q at every step (as stated in Section 4); if q is hidden and cannot be reconstructed from history, the factorization collapses and QR-MAX loses its advantage. For the continuous guarantee, the load-bearing premise is Assumption A.5, that every SimHash bucket has diameter at most φ and the MDP is Lipschitz — which SimHash itself does not deterministically en","fun_headline_variants_meta":{"raw":{"variants":["QR-MAX: first PAC guarantee for model-based RL on non-Markovian rewards","First PAC-efficient model-based RL for non-Markovian rewards","QR-MAX factorizes transitions to cut PAC sample complexity","Model-based RL for non-Markovian rewards: first PAC efficiency","QR-MAX: PAC-optimal model-based RL without Markovian assumptions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001386,"raw_usage":{"total_tokens":5460,"prompt_tokens":770,"completion_tokens":4690,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":514,"completion_tokens_details":{"reasoning_tokens":4604}},"tokens_in":514,"tokens_out":4690,"duration_ms":27593,"temperature":1.0,"reasoning_tokens":4604,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T15:59:48.933525+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run QR-MAX on an NMRDP where the reward automaton state is unobservable and the automaton is not known a priori, so the agent cannot maintain q internally; if the algorithm still achieves ε-optimality without ever recovering q, the paper's assumption would be violated. Alternatively, fix |S| and |A|, vary |Q| from 2 to a large value, and measure the number of interactions to reach an ε-optimal policy; a superlinear (or multiplicative |Q|) growth would contradict the stated O(|S||A|+|S||Q|) bound.","supporting_citations":[],"review_version":1}