REVIEW 4 major objections 5 minor 24 references
Constructing Non-Markovian Decision Process via History Aggregator
T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Markov and non-Markov decision processes are equivalent categories, so history can be treated as state.
desk verdict The HAS construction is a genuinely useful idea, but the paper's headline category equivalence is built on ill-defined measure compositions and should be removed or fixed before this is publishable. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the History Aggregator for State (HAS), a family of maps $A_{S,t}$ from time-$t$ histories to a target state set; it is reversible when a companion decoder $A^*_{S,t}$ recovers the original MDP's current state from the sequence of aggregated histories. Around it sits the categorical machinery: the Markov abstraction functor (history-as-state), the non-Markov embedding, and Theorem 1's natural isomorphisms, which are the formal content of equivalence. The two implemented aggregators are a group-operator prefix aggregation $B_{S,t}=\otimes_{\tau=0}^t s_\tau$, reversible when $(S,\otimes)$ is a group, and a convolution aggregation $W_{S,t}=\oplus_{\tau=0}^t w_\tau\cdot s_{t-\tau}$ over a left $R$-module, reversible when $w_0$ is invertible. The state dependency structure $D_h$, the set of time indices whose replacement changes the next-state distribution, is the bookkeeping device used to prove exactly which past states the constructed NMDP depends on.
What would settle it
Take a two-state deterministic MDP and write out the natural-isomorphism components between $\mathcal{M}\circ\mathcal{N}(M)$ and $M$ that Theorem 1 requires. Any explicit construction must define the maps the appendix calls $L^2$ and $L^{-2}$; if those maps cannot be produced without changing the transition kernel, or if the pullback of the transition distribution through the morphism is not a probability distribution, the claimed equivalence is unsupported. Separately, the convolution theorem can be checked directly: for a small ring and a fixed invertible $w_0$, decode $s_t$ from the aggregated histories and verify that the dependency set equals $\{t-\tau \mid (w^{-1})_{0,\tau}\neq 0\}$.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that the category of MDPs and the category of NMDPs are equivalent through the Markov abstraction functor, which maps an NMDP to the MDP whose states are the NMDP's full histories, and the non-Markov embedding functor, which maps each MDP to an NMDP with the same states, actions, and rewards but history-dependent transition functions. The proof is meant to formalize the intuition that 'the entire history can be regarded as a state.' The paper then makes the equivalence constructive: a reversible HAS plus its decoding map converts an MDP into an NMDP that preserves the original problem's difficulty, and two concrete families of reversible aggregators are given. The group-operator aggregator builds n-th order dependencies by repeated application; the convolution aggregator lets the state dependency structure be read off from the inverse of an upper-triangular coefficient matrix. The claim is that this yields an expressive, flexible way to construct non-Markovian decision problems for benchmarking decision algorithms.
Load-bearing premise
The load-bearing premise is that every morphism can push transition distributions backward through arbitrary state and reward maps—pulling a distribution back along a non-injective map need not stay a probability distribution—and the appendix's proof of the equivalence additionally relies on operators $L^2$ and $L^{-2}$ that are never defined.
Editorial extensions
If this is right
- Any non-Markovian decision problem can in principle be solved by Markovian methods after enlarging the state space to the full history; the categorical equivalence says this is a change of representation, not a loss of generality.
- A reversible-HAS transformation preserves the original MDP's optimal achievable return, so performance differences between the MDP and its NMDP variant measure an algorithm's history handling rather than the problem's intrinsic difficulty.
- Applying the group-operator aggregator $n$ times to a non-degenerate MDP yields an NMDP whose state dependency is exactly the previous $n+1$ states, giving a direct recipe for $n$-th order non-Markovian benchmarks.
- The convolution aggregator can realize a prespecified state dependency structure, including exponentially decaying weights, by choosing the inverse of an upper-triangular coefficient matrix.
- Because the constructed NMDP keeps the original MDP's interface, the same off-the-shelf reinforcement-learning algorithms can be run on both with no code changes.
Reading between the lines
- The authors do not go this far, but Theorem 1 also licenses a transfer of solution concepts: any construction or algorithm that is functorial on one category, such as a state abstraction scheme, can in principle be pulled back to the other.
- A natural testable extension is to fix a random invertible upper-triangular matrix over a ring, build the convolution-based NMDP, and check empirically that the learned policy's behavior changes only when the 'active' history positions predicted by the inverse matrix are perturbed.
- Releasing the reversibility condition, as the appendix suggests, turns HAS into a general partial-observability model; one could interpolate between MDP, NMDP, and POMDP by varying how much history the aggregator retains.
- The equivalence is representation-level: it does not by itself make non-Markovian problems computationally easier, and the paper's own experiments show performance degrading as history dependence strengthens.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a category-theoretic unification of Markov decision processes (MDPs) and non-Markov decision processes (NMDPs). It defines categories M and N in Definitions 11 and 12, introduces functors called Markov abstraction and non-Markov embedding, and claims in Theorem 1 that these categories are equivalent. The paper then introduces the History Aggregator for State (HAS), gives two concrete reversible constructions based on group operators and convolution with auxiliary sequences, proves that these constructions are reversible, analyzes the state dependency structure of the resulting NMDPs, and reports experiments with PPO and LSTM-PPO on wrapped Gymnasium environments. The HAS-based construction and dependency-structure theorems are developed independently of the categorical claim, but the paper presents the category equivalence as the central theoretical foundation.
Significance. If Theorem 1 were correct, it would provide a clean categorical formulation of the standard intuition that every non-Markov decision process can be regarded as Markovian by taking the full history as the state. That would be a useful organizing statement for a fragmented literature on non-Markovianity. The HAS framework is a more concrete contribution: Theorems 2, 3, 5, and 6 are derived directly from group and ring inverses rather than fitted parameters, and the construction gives explicit, controllable state-dependency structures for benchmark generation. The experimental wrapper implementation is also a practical asset. However, the central categorical claim is not established as written: the morphism conditions in Definitions 11 and 12 are not well-formed for arbitrary maps between state spaces, and the appendix proof of Theorem 1 relies on undefined operators and missing natural isomorphisms. Since the equivalence of M and N is the headline result and is used to motivate the whole framework, this is a load-bearing defect rather than a presentation issue.
major comments (4)
- [Definition 11] The initial-state morphism condition ρ0 = ρ'_0 ∘ ϕ_S is not well-defined for an arbitrary map ϕ_S : S → S'. Since ρ'_0 is a probability distribution on S' with total mass 1, the composite ρ'_0 ∘ ϕ_S is a nonnegative function on S whose total mass is Σ_{s∈S} ρ'_0(ϕ_S(s)). For a non-injective ϕ_S this sum counts multiple preimages of the same target state and generally exceeds 1, so the equality cannot hold as an equality of probability distributions unless ϕ_S is injective or the category is restricted in some other way. This makes Lemma 1 and the category M itself ill-defined in the general case.
- [Definitions 11 and 12] The transition morphism condition is also not a well-formed equation of distributions. The term T'_t((ϕ_S,ϕ_A)(s,a)) is an element of Δ(S' × R), and the notation ((T'_t ∘ (ϕ_S,ϕ_A))(s,a)) ∘ (ϕ_S,ϕ_R) attempts to turn it into an element of Δ(S × R) by composing with the map (ϕ_S,ϕ_R) : S × R → S' × R, which points in the wrong direction. Obtaining a measure on S × R from a measure on S' × R would require a pushforward along a map from S' × R to S × R; pulling a measure back along a non-injective measurable map is not countably additive and does not generally define a probability measure. The same defect appears in Definition 12 for NMDP morphisms and is carried into the appendix proofs of Lemmas 1 and 2.
- [Theorem 1, Appendix Section 5] The proof of Theorem 1 uses the operators L^2_S,t, L^{-2}_S,t, and L^{-1}_S,t in displayed equations that are claimed to show that M ∘ N and N ∘ M are naturally isomorphic to identity functors. None of these operators is defined anywhere in the paper. Moreover, the proof asserts natural isomorphisms without giving their component morphisms or verifying the naturality squares. Consequently, even if the category definitions were repaired, the proof would not establish the claimed equivalence.
- [Theorem 1, object-level correspondence] At the level of objects, M ∘ N applied to an MDP M yields an MDP whose state set is the history set H of the embedded NMDP, not the original state set S. An equivalence of categories can still hold when the composite functor is only naturally isomorphic to the identity, but the paper does not construct such a natural isomorphism. The assertion that the original transition function can be 'reconstructed without loss of information' is insufficient, because the missing isomorphism is precisely the information needed to compare the two categories.
minor comments (5)
- [Appendix Section 8] The heading for Theorem 4 in the appendix says 'Convolution Operator', but the statement and proof correspond to the correlation operator introduced in the main text, since the inversion uses a one-step difference that requires each w_t to be invertible. The heading should be corrected to avoid confusion.
- [Appendix, proof of Theorem 3] The proof first says it is sufficient to specify the group operator as multiplication in the free group, then states that the theorem also holds for (R^k, +). As written, it is not immediate that the free-group argument transfers to the commutative vector-space setting, and this step deserves an explicit explanation.
- [Section 5] The text referencing experimental results says 'As shown in 1' where it should say 'As shown in Figure 1'.
- [Throughout] There are numerous typographical artifacts, including 'F or' at the start of several headings and 'V enesset al.' in the references; the manuscript would benefit from a careful proofreading pass.
- [Section 5] The experiments report three training runs per condition but the figures do not show error bars or variance information, which makes the claimed 'generally declining trend' hard to evaluate beyond the plotted averages.
Circularity Check
No circularity found: the algebraic dependency theorems are independently derived, and the category-equivalence claim rests on explicit functor definitions rather than on fitting, self-citation, or target-as-input.
full rationale
The paper contains no fitted parameters and invokes no prior work of the present authors; citations are to standard category theory and external non-Markovian RL literature, and none is load-bearing in a self-referential way. Theorems 2-6 are derived by direct algebraic inversion: group inverses for the group-operator HAS (Theorems 2 and 3) and triangular-matrix inversion for the convolution-based HAS (Theorems 5 and 6), with dependency structures following from the resulting decoding formulas rather than being assumed. Theorem 1's category equivalence is a formalization of the paper's own stated intuition that taking the full history as state makes any non-Markovian process Markovian; the functors M and N are explicitly constructed so that M∘N and N∘M become identity-like, so the theorem is a structural consequence of the definitions. The appendix proof is incomplete (the operators L^2 and L^{-2} are never defined, and natural isomorphisms are not constructed), and Definitions 11/12 have a genuine well-definedness flaw because pulling a probability distribution back along a non-injective map is not generally countably additive. These are mathematical correctness issues, not circular reductions: no theorem's conclusion is used as a premise, and no quantity is fitted and then renamed as a prediction. Absence of circularity is therefore the appropriate finding.
Assumptions & free parameters
free parameters (1)
- lambda (decay rate in S_lambda and D_lambda) =
swept over {0, 0.2, 0.4, 0.6, 0.8, 1.0}
assumptions (4)
- ad hoc to paper The composition T'_t(...) composed with (phi_S, phi_R) of a transition distribution with the state and reward maps defines a probability distribution on S x R.
- standard math The state set S can be extended to a group (S', tensor) such as a free group so that the group operator is defined on aggregated states.
- domain assumption For the convolution-based HAS, the state set is a left R-module over a unital ring and the leading coefficient w0 is invertible.
- domain assumption The transition dynamics of the NMDP depend only on the state component of the history.
invented entities (1)
-
History Aggregator for State (HAS)
Cite this review
Pith. "Pith review of Constructing Non-Markovian Decision Process via History Aggregator." pith.science (2026). https://pith.science/paper/CU47OMCH
@misc{pith2026250624026,
author = {Pith},
title = {Pith review of: Constructing Non-Markovian Decision Process via History Aggregator},
year = {2026},
howpublished = {\url{https://pith.science/paper/CU47OMCH}},
note = {Machine review of arXiv:2506.24026}
}
read the original abstract
In the domain of algorithmic decision-making, non-Markovian dynamics manifest as a significant impediment, especially for paradigms such as Reinforcement Learning (RL), thereby exerting far-reaching consequences on the advancement and effectiveness of the associated systems. Nevertheless, the existing benchmarks are deficient in comprehensively assessing the capacity of decision algorithms to handle non-Markovian dynamics. To address this deficiency, we have devised a generalized methodology grounded in category theory. Notably, we established the category of Markov Decision Processes (MDP) and the category of non-Markovian Decision Processes (NMDP), and proved the equivalence relationship between them. This theoretical foundation provides a novel perspective for understanding and addressing non-Markovian dynamics. We further introduced non-Markovianity into decision-making problem settings via the History Aggregator for State (HAS). With HAS, we can precisely control the state dependency structure of decision-making problems in the time series. Our analysis demonstrates the effectiveness of our method in representing a broad range of non-Markovian dynamics. This approach facilitates a more rigorous and flexible evaluation of decision algorithms by testing them in problem settings where non-Markovian dynamics are explicitly constructed.
Figures
Reference graph
Works this paper leans on
-
[1]
Learning and solving regular decision processes
Eden Abadi and Ronen I Brafman. Learning and solving regular decision processes. arXiv preprint arXiv:2003.01008 , 2020
arXiv 2003
-
[2]
Regular decision processes: A model for non-markovian domains
Ronen I Brafman, Giuseppe De Giacomo, et al. Regular decision processes: A model for non-markovian domains. In IJCAI , pages 5516--5522, 2019
work page 2019
-
[3]
Ltl and beyond: Formal languages for reward function specification in reinforcement learning
Alberto Camacho, Rodrigo Toro Icarte, Toryn Q Klassen, Richard Anthony Valenzano, and Sheila A McIlraith. Ltl and beyond: Formal languages for reward function specification in reinforcement learning. In IJCAI , volume 19, pages 6065--6073, 2019
work page 2019
-
[4]
Reinforcement learning in non-markovian environments
Siddharth Chandak, Pratik Shah, Vivek S Borkar, and Parth Dodhia. Reinforcement learning in non-markovian environments. Systems & Control Letters , 185:105751, 2024
work page 2024
-
[5]
Dynamics of non-markovian open quantum systems
In\'es de Vega and Daniel Alonso. Dynamics of non-markovian open quantum systems. Rev. Mod. Phys. , 89:015001, Jan 2017
work page 2017
- [6]
- [7]
-
[8]
Inferring probabilistic reward machines from non-markovian reward signals for reinforcement learning
Taylor Dohmen, Noah Topper, George Atia, Andre Beckus, Ashutosh Trivedi, and Alvaro Velasquez. Inferring probabilistic reward machines from non-markovian reward signals for reinforcement learning. In Proceedings of the International Conference on Automated Planning and Scheduling , volume 32, pages 574--582, 2022
work page 2022
Show all 24 references
-
[9]
Gymnasium, 2023
Farama-Foundation. Gymnasium, 2023
2023
-
[10]
Reinforcement learning with non-markovian rewards
Maor Gaon and Ronen Brafman. Reinforcement learning with non-markovian rewards. In Proceedings of the AAAI conference on artificial intelligence , volume 34, pages 3980--3987, 2020
2020
-
[11]
Non-markovian reinforcement learning using fractional dynamics
Gaurav Gupta, Chenzhong Yin, Jyotirmoy V Deshmukh, and Paul Bogdan. Non-markovian reinforcement learning using fractional dynamics. In 2021 60th IEEE Conference on Decision and Control (CDC) , pages 1542--1547. IEEE, 2021
2021
-
[12]
Feature reinforcement learning: Part i
Marcus Hutter. Feature reinforcement learning: Part i. unstructured mdps. Journal of Artificial General Intelligence , 1(1):3, 2009
2009
-
[13]
The sample-complexity of general reinforcement learning
Tor Lattimore, Marcus Hutter, and Peter Sunehag. The sample-complexity of general reinforcement learning. In International Conference on Machine Learning , pages 28--36. PMLR, 2013
2013
-
[14]
Basic category theory , volume 143
Tom Leinster. Basic category theory , volume 143. Cambridge University Press, 2014
2014
-
[15]
Selecting the state-representation in reinforcement learning
Odalric-Ambrym Maillard, Daniil Ryabko, and R \'e mi Munos. Selecting the state-representation in reinforcement learning. Advances in Neural Information Processing Systems , 24, 2011
2011
-
[16]
On q-learning convergence for non-markov decision processes
Sultan Javed Majeed, Marcus Hutter, et al. On q-learning convergence for non-markov decision processes. In IJCAI , volume 18, pages 2546--2552, 2018
2018
-
[17]
Competing with an infinite set of models in reinforcement learning
Phuong Nguyen, Odalric-Ambrym Maillard, Daniil Ryabko, and Ronald Ortner. Competing with an infinite set of models in reinforcement learning. In Artificial Intelligence and Statistics , pages 463--471. PMLR, 2013
2013
-
[18]
Learning non-markovian decision-making from state-only sequences
Aoyang Qin, Feng Gao, Qing Li, Song-Chun Zhu, and Sirui Xie. Learning non-markovian decision-making from state-only sequences. Advances in Neural Information Processing Systems , 36, 2024
2024
-
[19]
Learning non-markovian reward models in mdps
Gavin Rens and Jean-Fran c ois Raskin. Learning non-markovian reward models in mdps. arXiv preprint arXiv:2001.09293 , 2020
2001 arXiv
-
[20]
Markov abstractions for pac reinforcement learning in non-markov decision processes
Alessandro Ronca, Gabriel Paludo Licks, and Giuseppe De Giacomo. Markov abstractions for pac reinforcement learning in non-markov decision processes. arXiv preprint arXiv:2205.01053 , 2022
2022 arXiv
-
[21]
Stable-baselines3-contrib, 2024
Stable-Baselines-Team. Stable-baselines3-contrib, 2024
2024
-
[22]
A monte-carlo aixi approximation
Joel Veness, Kee Siong Ng, Marcus Hutter, William Uther, and David Silver. A monte-carlo aixi approximation. Journal of Artificial Intelligence Research , 40:95--142, 2011
2011
-
[23]
Reinforcement learning of non-markov decision processes
Steven D Whitehead and Long-Ji Lin. Reinforcement learning of non-markov decision processes. Artificial intelligence , 73(1-2):271--306, 1995
1995
-
[24]
write newline
" write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence '...
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.