{"id":"4533d85c-2130-4dc1-b8a1-7a907d04add2","arxiv_id":"2506.24026","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"The authors define MDP and NMDP categories, claim their equivalence, and construct new NMDP benchmarks via reversible group-sum and convolution-based history aggregators.","lead":"This paper proposes a category-theoretic framework uniting Markov and non-Markovian decision processes, and introduces invertible history aggregators that turn any MDP into a non-Markovian one with controlled temporal dependencies. It is a methodological contribution for building RL benchmarks that test an agent's memory and history-decoding abilities.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Definition 11's morphism condition composes a probability distribution against a map in the wrong direction; for non-injective state maps the result is not a probability measure, so the MDP category is not well-defined and Theorem 1's equivalence is unsupported.","rationale":"The reader's weakest_assumption identifies exactly the load-bearing defect: Definitions 11 and 12 assume that a distribution on the codomain of a morphism can be transported back to the domain via an arbitrary measurable map, which is not generally a probability measure. My read of the manuscript confirms this: the morphism condition in Definition 11 is written in the wrong direction for a pushforward, and the preimage construction needed to interpret the composition is not countably additive for non-injective maps. The resulting category is therefore not well-defined for general morphisms, and Theorem 1's equivalence, which is presented as the central contribution in the abstract and introduction, is unsupported. The appendix proof does not repair this: it relies on undefined operators L^2 and L^{-2} and never exhibits the required natural isomorphisms. I do credit the HAS constructions and Theorems 2-6 as a potentially useful and more solid contribution, but the claimed categorical equivalence is the stated headline result, and it fails at the definitional level. This corroborates the reader's rejection without requiring any new objection. The recommended verdict therefore remains the reader's REJECT, reported here as UNCHANGED.","tokens_in":24469,"tokens_out":6237,"duration_ms":69890,"concrete_test":"Check whether Definition 11 admits a morphism for a simple non-injective case. Let S={0,1}, S'={0}, A={a}, R={r}; let M' have transition T'_0 with T'_0(0,a)=δ_{(0,r)} and initial distribution rho'_0=δ_0, and take phi_S constant, phi_A(a)=a, phi_R(r)=r. (i) Evaluate rho'_0∘phi_S: it assigns 1 to each s∈S, so it is not in ΔS. (ii) For the transition condition, set μ=δ_{(0,r)} and define the purported pullback ν(B)=μ((phi_S,phi_R)(B)) for B⊆S×R; for B_1={(0,r)} and B_2={(1,r)}, ν(B_1)=ν(B_2)=1 but ν(B_1∪B_2)=1, violating additivity. If no non-injective phi can satisfy both conditions, the category collapses and Theorem 1 cannot hold as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 1, the equivalence of the MDP category M and the NMDP category N via the functors M and N. This claim depends on Definitions 11 and 12 being genuine categories. In Definition 11, a morphism phi=(phi_S,phi_A,phi_R) from M=⟨rho0,S,A,{T_t}⟩ to M'=⟨rho'_0,S',A',{T'_t}⟩ uses phi_S:S→S' and requires rho0 = rho'_0 ∘ phi_S and T_t(s,a) = ((T'_t ∘ (phi_S,phi_A))(s,a)) ∘ (phi_S,phi_R). If S is discrete, rho'_0∘phi_S is a function on S whose total mass is Σ_s rho'_0(phi_S(s)); for a non-injective phi_S this mass exceeds 1, so it is not in ΔS. For the transition condition, μ=T'_t(phi_S(s),phi_A(a)) is a distribution on S'×R. To obtain a distribution on S×R by composing with (phi_S,phi_R):S×R→S'×R requires a pullback of μ along a non-injective map, which is not countably additive. For example, with S={0,1}, S'={0}, phi_S constant, and μ=δ_{(0,r)}, the induced set function assigns mass 1 to each of the disjoint singletons {(0,r)} and {(1,r)} but mass 1 to their union. Thus the category axioms are only satisfied in degenerate or bijective cases, and the claimed equivalence in Theorem 1 is built on an ill-defined construction. The appendix proof of Theorem 1 compounds the issue by introducing undefined operators L^2 and L^{-2} and asserting natural isomorphisms M∘N ≅ 1_M and N∘M ≅ 1_N without constructing them or verifying naturality. The HAS-based results (Theorems 2-6) are separate and appear more defensible, but they do not rescue the paper's headline categorical claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":24879,"tokens_out":6706,"duration_ms":80372,"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":[{"comment":"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.","section":"Definition 11"},{"comment":"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.","section":"Definitions 11 and 12"},{"comment":"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.","section":"Theorem 1, Appendix Section 5"},{"comment":"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.","section":"Theorem 1, object-level correspondence"}],"minor_comments":[{"comment":"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.","section":"Appendix Section 8"},{"comment":"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":"Appendix, proof of Theorem 3"},{"comment":"The text referencing experimental results says 'As shown in 1' where it should say 'As shown in Figure 1'.","section":"Section 5"},{"comment":"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":"Throughout"},{"comment":"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.","section":"Section 5"}],"recommendation":"reject","confidential_remarks":"The HAS construction and the dependency-structure theorems are the strongest part of this submission and could plausibly form the basis of a separate paper on benchmark construction for non-Markovian decision processes. My rejection is driven specifically by the invalid morphism definitions in Definitions 11 and 12 and by the incomplete proof of Theorem 1; these are load-bearing for the paper's stated central contribution. If the categorical framework is removed or thoroughly reworked, the remaining HAS material may be publishable on its own."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe useful core of this paper is the History Aggregator for State (HAS) idea. The group-sum and convolution constructions are simple, implementable, and come with crisp dependency-structure theorems (Theorems 3 and 6). Those results look essentially correct and could give RL researchers a flexible way to build benchmarks with known temporal dependencies. That part deserves real credit.\n\nThe problem is the category theory. The claimed equivalence between the MDP category and the NMDP category (Theorem 1) rests on Definitions 11 and 12, which compose a probability distribution on S'×R with a map (phi_S, phi_R): S×R → S'×R. That is a pullback, and for non-injective phi_S it is not countably additive; the resulting set function is not a probability distribution. Similarly, rho'_0 ∘ phi_S has total mass exceeding 1 when phi_S is not injective. So the morphisms in the MDP category are not even well-defined. The appendix proof of Theorem 1 does not help: it introduces undefined operators L^2 and L^{-2} and asserts natural isomorphisms without constructing them. This is not a minor gap; it is the load-bearing wall of the paper's headline claim. The stress-test note is right.\n\nThe good news is that the HAS part is separable and likely salvageable. An editor could ask the authors to drop or fix the categorical equivalence—maybe by restricting to injective morphisms or reframing the morphisms as stochastic relations—and resubmit. The experiments are illustrative only: no error bars, best-checkpoint selection, and the paper's own summary treats them as secondary. They should not carry much weight.\n\nWho is this for? Researchers building non-Markovian RL benchmarks, or working on temporal dependency structures in decision processes. They should read Section 4 and the appendix proofs for the constructions. The category section, as currently written, is a distraction.\n\nI would send this to peer review rather than desk reject, because the HAS methodology is novel and useful after a major revision. But tell the referee to focus on the constructions and not to spend too long on the categorical equivalence as stated.","headline":"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.","tokens_in":25424,"tokens_out":3348,"would_cite":false,"duration_ms":36193,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Markov and non-Markov decision processes are equivalent categories, so history can be treated as state.","keywords":["Non-Markov Decision Process","Markov Decision Process","Category Equivalence","History Aggregator","State Dependency Structure","Reinforcement Learning","Convolution Aggregator","Functor"],"falsifier":"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\\}$.","tokens_in":24189,"feed_emoji":"🔁","tokens_out":10133,"duration_ms":109036,"temperature":0.7,"pith_summary":"Non-Markovian dynamics are a known obstacle in reinforcement learning, yet benchmark environments for them are scattered and ad hoc. This paper tries to put the relationship between Markov decision processes (MDPs) and non-Markov decision processes (NMDPs) on a categorical footing, proving that the two categories are equivalent: every NMDP becomes an MDP once the full history is treated as the state, and every MDP embeds as an NMDP. That equivalence is then turned into a construction tool, the History Aggregator for State (HAS), which lifts an MDP to an NMDP with a controlled state-dependency structure. The intended upshot is a principled way to generate benchmarks that test an algorithm's ability to memorize and decode history rather than its luck on a special-purpose environment.","feed_headline":"Proof: every non-Markov decision process is an MDP","feed_subtitle":"A category-theoretic bridge turns history into state, yielding controlled non-Markov test environments for reinforcement learning.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the definitions of category, functor, and natural transformation that the MDP and NMDP categories and Theorem 1 rely on.","marker":"[Leinster, 2014]"},{"why":"Introduces non-Markov decision processes and motivates treating past observations as decision-relevant history.","marker":"[Whitehead and Lin, 1995]"},{"why":"Provides the open-quantum-systems example used to motivate why non-Markovian dynamics matter.","marker":"[de Vega and Alonso, 2017]"},{"why":"Earlier Markov abstraction work that the paper generalizes with its full-history Markov abstraction functor.","marker":"[Hutter, 2009]"},{"why":"A recent Markov abstraction treatment of non-Markov decision processes whose functor viewpoint the category framework subsumes.","marker":"[Ronca et al., 2022]"},{"why":"Defines the Gymnasium interface used by the environment wrappers so constructed NMDPs run with standard RL agents.","marker":"[Farama-Foundation, 2023]"},{"why":"Supplies the PPO implementation used in the experiments comparing agents on original versus aggregated-history environments.","marker":"[DLR-RM, 2024b]"}],"fun_headline_variants":["MDPs and non-Markov processes: categorically identical","History as state: a categorical proof for RL","Non-Markov RL environments via reversible history aggregators","From MDPs to non-Markov: a functorial construction","Category theory unifies Markov and non-Markov decision processes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["MDPs and non-Markov processes: categorically identical","History as state: a categorical proof for RL","Non-Markov RL environments via reversible history aggregators","From MDPs to non-Markov: a functorial construction","Category theory unifies Markov and non-Markov decision processes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000679,"raw_usage":{"total_tokens":3094,"prompt_tokens":964,"completion_tokens":2130,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":580,"completion_tokens_details":{"reasoning_tokens":2044}},"tokens_in":580,"tokens_out":2130,"duration_ms":20682,"temperature":1.0,"reasoning_tokens":2044,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:28:32.122251+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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\\}$.","supporting_citations":[{"cited_title":"Reinforcement learning of non-markov decision processes","cited_arxiv_id":null,"evidence_quote":"Introduces non-Markov decision processes and motivates treating past observations as decision-relevant history."},{"cited_title":"Dynamics of non-markovian open quantum systems","cited_arxiv_id":null,"evidence_quote":"Provides the open-quantum-systems example used to motivate why non-Markovian dynamics matter."},{"cited_title":"Feature reinforcement learning: Part i","cited_arxiv_id":null,"evidence_quote":"Earlier Markov abstraction work that the paper generalizes with its full-history Markov abstraction functor."},{"cited_title":"Markov Abstractions for PAC Reinforcement Learning in Non-Markov Decision Processes","cited_arxiv_id":"2205.01053","evidence_quote":"A recent Markov abstraction treatment of non-Markov decision processes whose functor viewpoint the category framework subsumes."},{"cited_title":"Gymnasium, 2023","cited_arxiv_id":null,"evidence_quote":"Defines the Gymnasium interface used by the environment wrappers so constructed NMDPs run with standard RL agents."}],"review_version":1}