- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies how to learn compact, reward-free state representations that retain the Markov property while discarding predictable but control-irrelevant details of high-dimensional observations. It builds on the Markov state abstraction framework of Allen et al. (2021), which gives two one-step sufficient conditions for an abstraction to be Markov: an inverse-model condition and a density-ratio condition. The inverse-model condition requires that the action responsible for a transition be equally predictable from the ground-state pair and the corresponding abstract-state pair . The density-ratio condition ensures that the abstraction preserves the relevant statistical relationship between consecutive states.
The paper’s central observation is that the objective previously used to implement these conditions enforces a stronger requirement than the original theory. The stronger condition matches a density ratio conditioned on the complete current ground state . Because it is conditioned on the complete observation, it encourages the representation to preserve every feature that helps predict the next observation, including predictable background changes, lighting, or other environmental processes that do not affect the agent’s controllable dynamics. The authors refer to this as the “strong” MSA condition and associate it with kinematic inseparability. In contrast, the original, weaker condition conditions the ground successor distribution on the current abstract state . Averaging over ground states mapped to the same allows observations with different but dynamically irrelevant details to be merged. The paper’s objective is therefore to learn representations satisfying this weaker condition while retaining the inverse-model condition needed to prevent complete representation collapse.
The theoretical component considers a deterministic abstraction satisfying the inverse-model condition and the set of all Markov abstractions that refine it. Theorem 1 establishes that, for a finite state space, this set contains a unique coarsest abstraction . The accompanying corollary shows that, under any full-support state distribution, is the unique abstraction in this class minimizing the mutual information between the ground state and its representation. The result is specifically about deterministic, memoryless abstractions that are both Markov and refinements of ; it is not a minimality result over all possible Markov representations. The mutual-information characterization is used to motivate an explicit compression term in the practical learning objective.
The proposed encoder objective consists of three losses:
The inverse loss trains a model to predict the action from two consecutive representations . It encourages the representation to preserve distinctions needed to identify the agent’s actions and serves as an anti-collapse mechanism. The matching loss approximates the weak density-ratio condition. Two binary classifiers are trained to distinguish observed successor pairs from pairs formed using successors sampled from the empirical marginal. One classifier receives , while the other receives . At their Bayes-optimal solutions, the classifiers’ posterior odds estimate the corresponding ground-successor and abstract-successor density ratios. The encoder is trained to match their output distributions using a KL divergence. Finally, is a KL divergence between the stochastic encoder and a learned prior . It provides a variational upper bound on and encourages the encoder to discard information not required by the other two losses. Training alternates between fitting the classifiers, inverse model, and prior with the encoder fixed, and then updating the encoder while holding these estimators fixed.
The paper first examines the learned representation in a controlled visual chain environment. The underlying problem contains six relevant states, formed from three positions and two types of transition dynamics. Each state is rendered using an MNIST digit over one of four backgrounds whose evolution is predictable but independent of the agent’s actions. The desired representation should therefore retain the six position-dynamics combinations while discarding background identity. The learned weak-MSA representation increasingly clusters observations by the six underlying states while mixing the four backgrounds. Nearest-neighbor probes show that cell identity remains predictable while background prediction falls toward chance. In contrast, the strong-MSA representation preserves separate clusters for different backgrounds and permits nearly perfect background prediction.
The authors then evaluate whether this representational difference affects reinforcement learning. In a goal-conditioned visual maze, they create multiple visually distinct copies of the same underlying maze and add a predictable four-phase background-color cycle. Weak MSA, strong MSA, and a standard Double DQN share the same base architecture and interaction budget. Across one, eight, 32, and 64 maze copies, weak MSA maintains a high success rate, whereas strong MSA and DQN deteriorate as the number of visually distinct copies increases. These experiments use five random seeds and 100,000 interactions.
The final experiments use image-based Walker Walk and Cheetah Run tasks from the DeepMind Control Suite with increasingly strong color distractions. The base reinforcement-learning method is RAD, a Soft Actor-Critic agent using image augmentation, and the abstraction objectives are attached to the same underlying agent. The encoder receives a stack of three RGB frames. Across ten random seeds, all methods perform similarly in the clean environments, but weak MSA retains higher returns than strong MSA and the unmodified RAD agent as the strength of the color distraction increases.
Overall, the paper claims that directly targeting the weak MSA condition, together with inverse-action prediction and an information-rate penalty, produces representations that retain distinctions needed for Markov dynamics while discarding predictable visual variation. The experiments support the narrower claim that this objective learns coarser representations than the strong-MSA implementation and that the resulting difference can improve sample efficiency and robustness to visual distractions.
Critical strengths
1. The paper identifies a precise mismatch between the theoretical definition of a Markov state abstraction and the objective previously used to learn one, and proposes a principled correction.
The original implementation imposes a stronger constraint than the theory requires. Under this strong condition, the density ratio for an abstract transition is matched to a ground-state density ratio conditioned on the complete current observation. The representation must therefore retain any feature that helps predict the next observation, including lighting, background identity, and other predictable processes irrelevant to the agent’s controllable dynamics.
The weak condition instead conditions the ground-successor distribution on the current abstract state, allowing it to average over multiple ground observations assigned to the same representation. Visually distinct observations can therefore be merged when they have the same relevant abstract dynamics. This clarifies the difference between preserving the information required for a Markov abstraction and preserving every predictable regularity in the observation stream.
The paper translates this insight into a concrete learning objective with three complementary terms. The matching loss uses two classifiers to approximate the weak density-ratio condition. The inverse-action loss preserves enough transition information to identify the action and discourages trivial collapse, while the rate penalty removes information unnecessary for the other conditions.
The theory further motivates this construction. Among deterministic Markov abstractions that refine an abstraction satisfying the inverse-model condition, the paper proves the existence of a unique coarsest abstraction and shows that it uniquely minimizes mutual information with the ground state. This result provides a structural justification for the rate penalty rather than presenting the objective as an empirical combination of auxiliary losses.
Overall, the paper identifies a specific source of over-refinement in an existing reward-free abstraction framework and develops both a theoretical characterization and a trainable solution. The distinction is particularly relevant for high-dimensional visual observations containing predictable but control-irrelevant variation.
2. The experiments are carefully organized to demonstrate the proposed mechanism and connect it to downstream reinforcement-learning performance.
The visual chain experiment is especially informative because the desired abstraction is known in advance. The environment contains six relevant states—three positions under two transition regimes—rendered over four predictably evolving backgrounds. Representation visualizations and nearest-neighbor probes show that both strong and weak MSA preserve the relevant state distinctions. However, background identity remains almost perfectly recoverable under strong MSA and approaches chance under weak MSA. The experiment therefore directly demonstrates that weak MSA removes a predictable nuisance variable without discarding the underlying state.
The online maze experiment connects this invariance to sample efficiency. The authors increase the number of visually distinct copies of an otherwise identical navigation problem while holding the underlying dynamics, reward, architecture, and interaction budget fixed. Weak MSA maintains high success as the number of copies grows from one to 64, whereas strong MSA and the standard DQN deteriorate. This provides controlled evidence that the coarser representation supports learning under increasing irrelevant visual complexity.
The Walker Walk and Cheetah Run experiments extend the evaluation to continuous control. Using the same RAD-based Soft Actor-Critic agent, the methods perform similarly under clean observations, but weak MSA degrades more slowly as color distractions become stronger. These results suggest that the benefit extends beyond the small domains used to illustrate the theory.
Together, the experiments form a coherent validation chain: the visual chain verifies the intended invariance, the maze connects it to online learning, and the continuous-control tasks demonstrate its applicability to larger pixel-based problems.
Critical weaknesses
The paper does not sufficiently position or justify its memoryless weak-MSA formulation relative to established history-based approaches, making the significance and scope of its main contribution difficult to assess.
Although the paper demonstrates that its weak-MSA objective can produce a coarser representation than the strong-MSA objective used by Allen et al., the discussion largely treats these two objectives as the relevant alternatives for learning Markov state abstractions. This gives an incomplete picture of the literature. A substantial line of work addresses the same underlying problem—constructing a compact representation that preserves the information required for prediction and control—by learning maps of interaction history rather than maps of only the current state.
For example, Subramanian et al., Approximate Information State for Approximate Planning and Reinforcement Learning in Partially Observed Systems, develop recursively updated information states that preserve reward and predictive information. Patil et al., On Learning History-Based Policies for Controlling Markov Decision Processes, study this problem even when the original environment is an MDP: although the ground state is Markov, a compressed feature of that state may no longer be Markov, and information from history may be needed to obtain a sufficient representation. Earlier work by Hutter, including Feature Markov Decision Processes and Extreme State Aggregation Beyond MDPs, similarly formulates compact states as features of complete interaction histories. More recent work explicitly connects these perspectives: Ni et al., Bridging State and History Representations: Understanding Self-Predictive Reinforcement Learning, relates state abstractions, history representations, approximate information states, bisimulation, and self-predictive objectives, while Kirtland et al., Memory as State Abstraction Over History, formalizes learned memory as state abstraction over trajectory history. None of these works is discussed.
These omissions are important for more than scholarly completeness because the cited works expose a central design choice in the present paper. Suppose that two different ground states are mapped to the same representation, but the same action has different consequences in those states. The compressed representation is then not Markov, even though the original ground state was Markov. There are two broad ways to address this problem. One can prevent the two states from being merged and require the current representation alone to retain every distinction needed for Markovness. Alternatively, one can use previous observations and actions to maintain the information needed to disambiguate the current compressed observation. The present paper takes the first approach by learning , whereas the omitted literature develops the second approach through recursively updated history representations.
This distinction is directly relevant to understanding what the proposed loss learns. The present objective combines inverse-action prediction, weak density-ratio matching, and a rate penalty. It therefore seeks a compressed representation that preserves action-identifiable transition structure while remaining Markov without memory. Patil et al. instead combine reward prediction with forward prediction of the next ground state and also discuss prediction in representation space. Approximate information-state and self-predictive approaches similarly seek recursive representations that preserve reward and future-prediction information. These objectives impose different notions of which information is relevant. For example, reward prediction can preserve a task-relevant variable that does not help identify the action, whereas the inverse loss used here need not preserve such a variable. Conversely, full-state prediction can encourage retention of predictable nuisance information, whereas latent prediction may permit that information to be removed. The paper does not explain how its weak-MSA conditions relate to these alternatives, so it remains unclear whether the proposed objective provides a genuinely different representational capability, a reward-free version of an existing idea, or a solution specialized to the memoryless MSA class.
The brief discussion following Equation 1 does not resolve this issue. The authors observe that directly checking the Markov condition requires conditioning on arbitrarily many past abstract states and actions and is therefore impractical. This observation motivates replacing the direct test with sufficient conditions that can be evaluated using one-step transitions. However, the difficulty of explicitly conditioning on a complete history is not the same as the difficulty of learning a compact summary of that history. A recurrent representation of the form: $ z_t=f(z_{t-1},s_t,a_{t-1}) $
can maintain a fixed-dimensional summary without explicitly storing or repeatedly processing the entire history. The existing history-based literature therefore presents a practical alternative to the one-step memoryless construction rather than merely an intractable definition of Markovness.
Focusing on memoryless maps is a reasonable design choice, but the paper would benefit from explaining what is gained by making this choice. Possible advantages could include simpler optimization, reduced computation, improved stability, better sample efficiency, fewer assumptions, or easier reuse across reward functions. The reward-free nature of the objective may also be valuable in sparse-reward or multi-task settings. At present, however, the paper neither develops a theoretical comparison showing when a memoryless weak-MSA representation is preferable nor provides experimental evidence demonstrating any of these potential advantages relative to history-based alternatives.
This missing comparison also affects the interpretation of the theoretical result. Theorem 1 identifies a unique coarsest abstraction among deterministic Markov abstractions that refine an abstraction satisfying the inverse-model condition. Every candidate in this set is a memoryless function of the current ground state. A representation constructed recursively from history is outside the theorem’s comparison class. Thus, the result establishes a coarsest solution within the selected memoryless class, not a coarsest Markov representation available to the agent more generally. The theorem remains meaningful within its stated scope, but understanding the significance of that scope requires a discussion of how it relates to history-based information states and whether allowing history could yield a different or more useful representation.
The experiments also do not provide this missing comparison. In the visual chain experiment, the current image identifies the position and transition type; the history of previous observations is not needed to determine the underlying state. The visual maze is constructed similarly: the current observation provides the agent’s cell and goal information, while texture and color act as observable distractors. These experiments effectively ask whether the proposed objective can discard nuisance information already separable from the state information contained in the current image. They do not consider the case in which compression creates ambiguity that can only be resolved from previous observations and actions.
In continuous control, the method receives a stack of three RGB frames. Here, temporal information is manually selected and supplied before the memoryless encoder is applied. Frame stacking is a standard way of making motion information such as velocity inferable from images, but it does not establish that a learned history representation is unnecessary. The paper does not explain why three frames are sufficient to produce a Markov input, investigate how performance depends on the number of frames, or compare the fixed stack with a recurrent representation that learns which historical information to retain. Across the experiments, history is therefore either unnecessary by construction or supplied manually as part of the input.
A comprehensive paper need not experimentally compare against every work mentioned above. This concern could instead be addressed through theory that distinguishes the representations obtainable from memoryless weak MSA from those obtainable through history-based maps. Alternatively, a representative comparison in a small number of carefully selected domains could demonstrate that the proposed formulation is more sample-efficient, stable, transferable, or robust than a learned history representation. At minimum, the paper should acknowledge this parallel literature, explain that its contribution concerns the memoryless MSA class, and clarify what advantages are expected from that restriction.
As written, the paper convincingly establishes an improvement over the strong-MSA objective in settings with predictable visual distractors. However, the omitted literature, unexplained choice of representation class, restricted interpretation of the minimality result, and absence of a relevant empirical comparison collectively make it difficult to determine what broader capability or advantage the proposed objective provides. Since the main contribution is a new objective for learning Markov representations, this uncertainty is consequential to the assessment of the paper’s novelty and significance.
Questions for authors
-
How do the proposed weak-MSA conditions formally relate to approximate information states, Patil et al.’s history-based representations, feature MDPs, and self-predictive state representations?
-
What is the intended theoretical or practical advantage of restricting the representation to , rather than allowing a recursively updated history representation?
-
Can a history-dependent representation be strictly coarser or more useful than the identified by Theorem 1? How should the theorem’s minimality claim be interpreted relative to such representations?
-
Why are three stacked frames treated as the input state in the continuous-control experiments? Were other stack lengths or learned recurrent representations evaluated?
-
What theoretical or experimental evidence establishes an advantage over representative alternatives beyond strong MSA, particularly in the sparse-reward or multi-task settings used to motivate the method?
3 comments
Response to the rebuttal
I have reviewed the authors' comments. To clearly demonstrate the empirical gains of the proposed method for learning Markov abstractions, it is important to compare it against existing approaches in the literature; without these comparisons, the paper's claims are weakened. Understanding that these experiments require time to run, I have raised my score with the expectation that the authors will include these empirical comparisons in future revisions, and also compare their work with the other method in this line of research.
Thank you again for your feedback and reconsideration. We will add comparisons (history-based and otherwise) in the final copy.
Thank you for your comments.
History-based representations
We agree with you that we have not discussed alternative history-based representation learning approaches, and how they connect to this work. This might have unintentionally made it look like it is the only way. Allen et al. 's (2021) sufficient conditions are indeed one way of recovering the Markovness, and the other alternative is to learn an abstraction based on historical observations. It would be hard to prepare a new set of experiments while making sure we are doing the comparisons correctly. We extended our related work and discussed history-based abstraction methods, but an extensive comparison with history-based methods is beyond the scope of the paper.
Intended theoretical or practical advantage of zt=ϕ(st) & theoretical or experimental evidence over alternatives
Conditions in Allen et al. (2021) say given the inverse condition (I(a∣s,s’)==I(a∣z,z’)), the density condition ⇔ Markov abstraction. And the inverse condition is essentially about an agent understanding the parts of the world that it can manipulate (since otherwise, I(a∣s,s’) would be equivalent to the policy output π(a∣s), and the equality would be trivially satisfied). So, if we are assuming that “the agent should know how it controls its environment,” the density matching condition gives a definitive answer on recovering Markovness (since it is an if and only if statement), and Theorem 1 and its corollary imply the coarsest abstraction (under that class), and our objectives are a simple way to approximate that condition using single transitions instead of full trajectories. Therefore, the theoretical advantage is that it is provably the minimal unique solution (under that assumption above).
The practical advantage in the sparse-reward and multi-task setting is that our weak formulation recovers exactly the parts that the agent can control, and makes no preference over other exogenous dynamics if it does not affect the agent’s control. For instance, consider our example in Fig. 1 where there is a very large complex domain, say, chess in the real world, in which observations always change (e.g., different lighting, objects in the background etc). What do we rely on as a learning signal apart from reward (since we won’t have any reward with random exploration)? Our answer is to let the agent learn what it can control (I(a∣s,s’)=I(a∣z,z’)), and ensure that the representation is Markov (the density match condition). This way, it would at least understand how chess works, and this could be further useful in exploration (which is beyond the scope of this paper). Our experiments in chain-walk and maze domains are essentially a reflection of this scenario. There could be other representations—and history-based ones—that are Markov but do not tell what the agent can control.
Can a history-dependent representation be coarser than one found in Theorem 1?
Theorem 1’s claim is “among abstractions that are Markov and satisfy the inverse model.” As such, for any Markov abstraction, if it satisfies Condition 1, phi* identified by Theorem 1 is provably the coarsest one. However, there could be other Markov abstractions that are coarser. Consider the constant abstraction, z=s1,…,sn, and assume some actions are predictable. This abstraction is strictly coarser than ϕ∗ identified by Th. 1 (and actually the coarsest one), and Markov, but violates Condition 1. We had already emphasized this after Theorem 1 in the main text, but also now added this constant abstraction example to the proof. Other history-based schemes may have different guarantees, but a coarseness comparison only makes sense for the same guarantees.
Frame-stacking in continuous-control experiments
The frame stacking of 3 is inherited from the original MSA and RAD papers, which we use as baselines. The main motivation is to allow the network to approximate velocity and acceleration using differences between multiple frames.