Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processes

T0 review · 3 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2512.14617 v2 pith:CWSZBWRV submitted 2025-12-16 cs.LG cs.AI

Alessandro Trapasso , Luca Iocchi , Fabio Patrizi This is my paper · ORCID
classification cs.LGcs.AI
keywords model-basedreinforcementlearningnon-MarkovianrewarddecisionprocessesmachinesPAC-MDPsamplecomplexityfactorizeddynamicsSimHashdiscretizationcontinuousstatespaces
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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|

Load-bearing premise

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

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [§4.2, Appendix §A.3–A.4] 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.
  2. [§4.2, threshold m_E / Lemma A.2] 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.
  3. [§5, Appendix Theorem A.6, Remark A.7] 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.
minor comments (5)
  1. [Theorems/Appendix] 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.
  2. [Appendix §A] 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.
  3. [§6 / footnote 4] 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.
  4. [Algorithm A.1] 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.
  5. [Table 5] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: QR-MAX's PAC bound is a direct counting argument; the continuous guarantee is conditional, not circular.

full rationale

The discrete QR-MAX derivation is self-contained. Section 4.2 and Appendix A.2/A.3 set thresholds m_E and m_Q from Hoeffding/Weissman concentration inequalities and then count visits to still-unknown (s,a) and (q,s') pairs; the resulting N(ε,δ)=2/((1−γ)ε)(|S||A|m_E+|S||Q|m_Q) is the bookkeeping of the algorithm's own counters, not a fitted value or a renamed input. Lemma A.1's accuracy claim is an independent probabilistic statement over empirical estimates; Lemma A.2 is the standard optimism argument. The self-cited product-MDP reduction (Brafman, De Giacomo, and Patrizi 2018) is only background motivation for the baseline R-MAX on S×Q and is not used to prove QR-MAX's factorization; Equations (1)–(2) are derived from the Markov property and determinism of the automaton. The continuous BUCKET-QR-MAX theorem is explicitly conditional on Assumption A.5 (bounded bucket diameter + Lipschitz MDP), and Remark A.7 concedes that SimHash does not deterministically guarantee the diameter and defers δ_LSH. That is an unverified assumption / verification gap, not a circular derivation: the theorem does not assume its own conclusion, it simply states a conditional guarantee whose antecedent is not established. No equation in the paper reduces to a fitted quantity or to the paper's own prior claims, so there is no significant circularity.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The core PAC bound is not fitted: thresholds are derived from ε, δ, and R_max. The hand-set experimental thresholds (t_E=30, t_Q=1) and unreported SimHash parameters are the main free choices. Assumption A.5 is an ad hoc regularity condition for the continuous extension. No new physical or conceptual entities are introduced.

free parameters (3)
  • t_E = 30
    Environment-visit threshold in experiments; set by rule of thumb, not from the PAC formula. Determines how many samples are needed to mark an (s,a) pair known.
  • t_Q = 1
    Automaton-visit threshold; 1 suffices because reward machines used in experiments are deterministic.
  • SimHash granularity (L, d_h) = not reported
    Number of SimHash functions and projections controls bucket diameter φ in Assumption A.5; exact values and tuning are not given in the main text.
assumptions (4)
  • domain assumption The agent observes the current automaton state q (or maintains it exactly from a known DFA).
    Stated in Section 4: 'we assume that the agent observes the current automaton state q'. Without this, the factorized counters n_E and n_Q cannot be updated and QR-MAX is inapplicable.
  • domain assumption Rewards are bounded and fit the Hoeffding range [0, R_max].
    Lemma A.1's Hoeffding bound uses range R_max; the experiments include negative rewards (-100), so the theoretical error bound does not strictly cover the empirical setting.
  • ad hoc to paper Assumption A.5: SimHash buckets have diameter at most φ and rewards/transitions are L-Lipschitz.
    This is the only bridge from BUCKET-QR-MAX's abstract bucket MDP to the true continuous MDP. Remark A.7 concedes SimHash does not deterministically guarantee the diameter condition and defers δ_LSH analysis to future work.
  • standard math Standard PAC-MDP concentration arguments apply to adaptively sampled transitions.
    Lemma A.1 uses Hoeffding and Weissman inequalities on counts collected under a changing policy; the appendix does not address the non-i.i.d. dependence, which standard R-MAX proofs handle with a more careful stopping-time argument.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processes." pith.science (2026). https://pith.science/paper/CWSZBWRV

@misc{pith2026251214617,
  author       = {Pith},
  title        = {Pith review of: Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CWSZBWRV}},
  note         = {Machine review of arXiv:2512.14617}
}
abstract

Many practical decision-making problems involve tasks whose success depends on the entire system history, rather than on achieving a state with desired properties. Markovian Reinforcement Learning (RL) approaches are not suitable for such tasks, while RL with non-Markovian reward decision processes (NMRDPs) enables agents to tackle temporal-dependency tasks. This approach has long been known to lack formal guarantees on both (near-)optimality and sample efficiency. We contribute to solving both issues with QR-MAX, a novel model-based algorithm for discrete NMRDPs that factorizes Markovian transition learning from non-Markovian reward handling via reward machines. To the best of our knowledge, this is the first model-based RL algorithm for discrete-action NMRDPs that exploits this factorization to obtain PAC convergence to $\varepsilon$-optimal policies with polynomial sample complexity. We then extend QR-MAX to continuous state spaces with Bucket-QR-MAX, a SimHash-based discretiser that preserves the same factorized structure and achieves fast and stable learning without manual gridding or function approximation. We experimentally compare our method with modern state-of-the-art model-based RL approaches on environments of increasing complexity, showing a significant improvement in sample efficiency and increased robustness in finding optimal policies.

Figures

Figures reproduced from arXiv: 2512.14617 by the authors.

Figure 1
Figure 1. Results for the three experimental configurations (mean over 10 random seeds with shaded bands showing [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Map4 (15x15) - Office World [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Map0 - task 0 (10x10) B.2 Environment map0. We build on the grid–world map0 introduced by Tiapkin et al. (2022), a 10×10 grid. For UCBVI, PSRL, and OPSRL the planning horizon is fixed at H = 50; the two Bayesian methods use eight Thompson samples per episode, follow￾ing the authors’ default. Non-Markovian extension. The original one-shot objective is replaced by a four-stage mission that forces the agent to remember… view at source ↗
Figures from the paper (15 more)
Figure 4
Figure 4. Figure 4: Map4 - task 6 (15x15) - Office World MAX and QR-MAX, respectively, by propagating knowledge to unseen states as in QRM. The algorithms QL, R-MAX, QR-MAX, R-MAXRM and QR-MAXRM use the discount factor γ = 0.9. All the vari￾ants of UCBVI and PSRL/OPSRL use the discount fa…
Figure 5
Figure 5. Figure 5: Scalability with respect to task complexity. Training steps needed to achieve the goal in 15 different tasks. [PITH_FULL_IMAGE:figures/full_fig_p014_5.png]
Figure 6
Figure 6. Figure 6: Office World - 15 tasks with 95 % confidence in [PITH_FULL_IMAGE:figures/full_fig_p014_6.png]
Figure 7
Figure 7. Figure 7: Map1 (12x9) - Office World [PITH_FULL_IMAGE:figures/full_fig_p015_7.png]
Figure 8
Figure 8. Figure 8: Map2 (12x12) - Office World substantially (up to 156.46 steps on Map3 exp5) and the VI success rate falls below 10%, reflecting harder coordina￾tion challenges. Nevertheless, QR-MAXRM still completes training in 1.47 × 104 steps on Map3 exp5, compared to 1.29 × 105 for…
Figure 11
Figure 11. Figure 11: Reward Machine of Experiment 2 - Office World [PITH_FULL_IMAGE:figures/full_fig_p016_11.png]
Figure 18
Figure 18. Figure 18: Map1 Exp3 - Office World [PITH_FULL_IMAGE:figures/full_fig_p016_18.png]
Figure 19
Figure 19. Figure 19: Map1 Exp4 - Office World [PITH_FULL_IMAGE:figures/full_fig_p016_19.png]
Figure 20
Figure 20. Figure 20: Map1 Exp5 - Office World [PITH_FULL_IMAGE:figures/full_fig_p017_20.png]
Figure 25
Figure 25. Figure 25: Map2 Exp5 - Office World [PITH_FULL_IMAGE:figures/full_fig_p018_25.png]
Figure 26
Figure 26. Figure 26: Map3 Exp1 - Office World [PITH_FULL_IMAGE:figures/full_fig_p018_26.png]
Figure 27
Figure 27. Figure 27: Map3 Exp2 - Office World [PITH_FULL_IMAGE:figures/full_fig_p018_27.png]
Figure 28
Figure 28. Figure 28: Map3 Exp3 - Office World [PITH_FULL_IMAGE:figures/full_fig_p019_28.png]
Figure 29
Figure 29. Figure 29: Map3 Exp4 - Office World [PITH_FULL_IMAGE:figures/full_fig_p019_29.png]
Figure 30
Figure 30. Figure 30: Map3 Exp5 - Office World [PITH_FULL_IMAGE:figures/full_fig_p019_30.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Theoretical Foundations of $\max$@$k$ Reinforcement Learning

    cs.LG 2026-07 conditional novelty 7.0 of 10

    For max@k (best-of-K) finite-horizon MDPs, Markovian policies are suboptimal, a compact (previous-best, current-cumulative) state augmentation restores optimality, exact planning is NP-hard but an FPTAS exists, and th...

Reference graph

Works this paper leans on

6 extracted references · 1 linked inside Pith · cited by 1 Pith paper

  1. [1]

    simulation-lemma

    Discretisation error and abstract MDPLetMbe the true continuous-state MDP and let ¯Mbe theabstract MDP whose states are the bucket–automaton pairs(b, q)∈ B ×Q, with transitions and rewards given by the bucket- averaged quantities. Under Assumption A.5, any two states s, s′ mapped to the same bucketbsatisfy∥s−s ′∥ ≤ϕ. Lip- schitz continuity then implies th...

  2. [2]

    Estimation error in the bucket MDPWithin the ab- stract MDP ¯Mon(b, q), BUCKET-QRMAX behaves ex- actly as QR-MAX on a discrete MDP with state space S′ =B ×Q. The thresholdsm ET , mER , mQT , mQR are chosen so that, once a triple(b, a, q)is markedknown, the corresponding empirical estimates bPE, bRE, bPQ, bRQ areβ- accurate for ¯Mwith high probability. Mor...

  3. [3]

    error + V πt ¯M (b, q)−V ∗ ¯M (b, q) | {z } est

    Combining the two sources of errorFor any states with bucketb=h(s), we can now decompose the gap be- tween the value of the learned policy inMand the optimal value inMinto three terms: V πt M (s)−V ∗ M (s) ≤ V πt M (s)−V πt ¯M (b, q) | {z } disc. error + V πt ¯M (b, q)−V ∗ ¯M (b, q) | {z } est. error + V ∗ ¯M (b, q)−V ∗ M (s) | {z } disc. error . By step ...

    2022

  4. [2003]

    Journal of Artificial Intelligence Research, 19: 399–468

    Efficient Solution Algorithms for Factored MDPs. Journal of Artificial Intelligence Research, 19: 399–468. Gupta, G.; Yin, C.; Deshmukh, J. V .; and Bogdan, P. 2021. Non-Markovian Reinforcement Learning using Fractional Dynamics. InProc. CDC, 1542–1547. Icarte, R. T.; Klassen, T. Q.; Valenzano, R. A.; and McIlraith, S. A. 2022. Reward Machines: Exploiting...

    arXiv 2021

  5. [2020]

    InProc, ICAPS, volume 34, 13659–13662

    Restraining bolts for Reinforcement Learning agents. InProc, ICAPS, volume 34, 13659–13662. De Giacomo, G.; and Vardi, M. Y . 2013. Linear Temporal Logic and Linear Dynamic Logic on Finite Traces. InProc, IJCAI, 854–860. Gaon, M.; and Brafman, R. I. 2020. Reinforcement Learning with Non-Markovian Rewards. InProc. AAAI, 3980–3987. Guestrin, C.; Koller, D.;...

    2013

  6. [2023]

    InInternational Conference on Artificial Intelligence and Statistics (AISTATS), 4114–4146

    Exploration in Reward Machines with Low Regret. InInternational Conference on Artificial Intelligence and Statistics (AISTATS), 4114–4146. Brafman, R.; De Giacomo, G.; and Patrizi, F. 2018. LTLf/LDLf Non-Markovian Rewards. InProc. AAAI, 1771– 1778. Brafman, R. I.; and Tennenholtz, M. 2003. R-max - a general polynomial time algorithm for near-optimal reinf...

    2018

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.