acceptodds
Under review as a conference paper at ICLR 2027

Learning Coarser Markov State Abstractions

10 views

Abstract

State abstractions in reinforcement learning create compact representations, and increase sample-efficiency, by keeping information in observations that is relevant for decision-making while discarding other regularities. Recently introduced Markov state abstractions (MSAs) define reward-free sufficient conditions under which the learned representation is Markov. However, current implementations of the MSA objectives satisfy a stronger (kinematic inseparability) condition, which results in over-refined abstractions that preserve all transition regularities in the observation. We show for the first time how to align the training objective with the original theoretical MSA conditions and thus build coarser abstractions. This objective drives the representation to satisfy sufficient Markov conditions, but does not, by itself, guarantee minimality. We therefore provide an additional heuristic to push the representation towards minimality. Our experiments in pixel-based domains show that the learned abstractions recover the underlying complexity of the problem, which improves downstream performance.

Primary area:
reinforcement learning
Keywords:
State abstraction, Reinforcement learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_e5iSOpenReview ↗
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 (s,s′)(s,s') and the corresponding abstract-state pair (z,z′)(z,z'). 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 ss. 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 zz. Averaging over ground states mapped to the same zz 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 ϕinv\phi_{\mathrm{inv}} 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 ϕ∗\phi^\ast. The accompanying corollary shows that, under any full-support state distribution, ϕ∗\phi^\ast 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 ϕinv\phi_{\mathrm{inv}}; 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:

Lenc=αLinv+βLmatch+λLrate.L_{\mathrm{enc}} = \alpha L_{\mathrm{inv}} + \beta L_{\mathrm{match}} + \lambda L_{\mathrm{rate}}.

The inverse loss LinvL_{\mathrm{inv}} trains a model to predict the action aa from two consecutive representations (z,z′)(z,z'). It encourages the representation to preserve distinctions needed to identify the agent’s actions and serves as an anti-collapse mechanism. The matching loss LmatchL_{\mathrm{match}} 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 (z,s′)(z,s'), while the other receives (z,z′)(z,z'). 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, LrateL_{\mathrm{rate}} is a KL divergence between the stochastic encoder qϕ(z∣s)q_\phi(z\mid s) and a learned prior rη(z)r_\eta(z). It provides a variational upper bound on I(S;Z)I(S;Z) 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 3×33\times3 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 3×33\times3 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 zt=ϕ(st)z_t=\phi(s_t), 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
  1. 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?

  2. What is the intended theoretical or practical advantage of restricting the representation to zt=ϕ(st)z_t=\phi(s_t), rather than allowing a recursively updated history representation?

  3. Can a history-dependent representation be strictly coarser or more useful than the ϕ∗\phi^\ast identified by Theorem 1? How should the theorem’s minimality claim be interpreted relative to such representations?

  4. Why are three stacked frames treated as the input state in the continuous-control experiments? Were other stack lengths or learned recurrent representations evaluated?

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

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)z_t=\phi(s_t) & 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’)I(a | s, s’)==I(a | z, z’)), the density condition ⇔\Leftrightarrow 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’)I(a | s, s’) would be equivalent to the policy output π(a∣s)\pi(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’)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,…,snz = {s_1, …, s_n}, and assume some actions are predictable. This abstraction is strictly coarser than ϕ∗\phi^\ast 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.

Reviewer_e5iSOpenReview ↗

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.

Reviewer_9ESQOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

It is data/compute expensive to learn and plan in large MDPs. State abstraction can be used to reduce the MDP size. They discuss one prior approach for finding a Markov state abstraction that involves ensuring two conditions: an inverse model condition and a density ratio. They then introduce a new criteria that maintains the inverse model condition but allows for a coarser representation than requiring the original density ratio criteria. This is used to derive a training objective.

Critical strengths

This is an interesting topic.

Critical weaknesses

Thm 1 and corollary do not seem to immediately imply that the resulting abstraction will preserve learning the optimal decision policy.

Section 4 only looks at the learned representations, but I am interested in the impact on RL. This comes in section 5, but I would like some illustrative toy domains to discuss when this will or won’t cause linear regret.

The experimental results did not compare to deep learning methods that try to compactly encode and learn the representation. For example, couldn’t some of Amy Zhang’s work be used on some of these domains?

Questions for authors

See above.

2 comments

Thank you for your comments.

Thm 1 and corollary do not imply learning the optimal decision policy and Linear Regret

We agree that Theorem 1 and its corollary do not imply preserving the optimal decision policy or sublinear regret, and that these representations are only useful if they improve the sample efficiency in downstream task performance. Theorem 1 proves the existence of a unique coarsest solution (not the coarsest among all Markov abstractions, but those that are refinements of ϕinv\phi_{inv}), and its corollary gives us a practical target for defining an objective for minimality.

We believe your concern can be summarized as “Do we lose performance by choosing to use the abstraction instead of ground states?” This question can be answered using approximate state abstractions (Abel et al., 2016; Jiang 2018) where we are interested in two errors: ∣R(s1,a)−R(s2,a)∣≤ϵr(how much the agent misrepresents the reward),|R(s1, a) - R(s2, a)| \leq \epsilon_r\quad\text{(how much the agent misrepresents the reward),}

∑z’∣T(z’∣a,s1)−T(z’∣a,s2)∣≤ϵt(how much the agent misrepresents the abstract transition function)\sum_z’ |T(z’ | a, s1) - T(z’ | a, s2)| \leq \epsilon_t \quad\text{(how much the agent misrepresents the abstract transition function)} where s1s_1 and s2s_2 are from the same abstract state, and this is for all z∈Zz \in Z, a∈Aa \in A. Then, the value difference between using the ground vs. abstract state is upper bounded by these errors:

∣V∗(s)−Vπϕ(s)∣≤2ϵr1−γ+γϵtRmax⁡(1−γ)2.|V^\ast(s) - V^{\pi_\phi}(s)| \leq \frac{2\epsilon_r}{1 - \gamma} + \frac{\gamma \epsilon_t \text{R}_{\max}}{(1 - \gamma)^2}.

When ϵr\epsilon_r and ϵt\epsilon_t are zero, it is possible to recover the optimal policy, and an agent learning on zz has sublinear regret over the abstract states. Otherwise, regret can be linear with slope at most the bound.

Let us give some examples by extending our scenario in Fig. 1. Consider that from state g, the agent jumps randomly into one of the sub-MDPs below, and there is a reset action that takes the agent back to g. If the same reward is defined for R2R_2 through RNR_N, then there will not be any approximation error—it does not really matter for the agent which copy it is in, since it cares about the position in the sub-MDP. On the other hand, if the rewarding state is only R4R_4, then ϵr\epsilon_r will be positive, and the optimal policy would not be preserved (or rather, the loss in value function will be upper bounded as above). There, the agent seeing the ground states can hit reset until it successfully jumps into sub-MDP_4, whereas the agent using weak abstractions cannot see which sub-MDP it is at. For ϵt\epsilon_t violation, suppose the sub-MDPs are one-directional and only sub-MDP_4 has a rewarding exit at its end. The weak abstraction still merges the LiL_i and MiM_i across copies, so the agent cannot tell whether it is heading to the exit until it gets there, whereas the agent seeing the ground states resets right after the jump.

In practice, we expect these cases to be uncommon: states that differ in reward usually also differ in how actions affect them (e.g., a goal state ends the episode, or an object has been picked up), and the weak conditions keep such states apart. Figure 2 shows this for two chains that differ only in their dynamics. In our DMC experiments, in the clean setting, MSA (weak) matches RAD and MSA (strong), which keep all the information in the observation, and outperforms them as distraction increases, so what it discards is not needed for the task.

Abel, D., Hershkowitz, D., & Littman, M. (2016). Near optimal behavior via approximate state abstraction. In ICML (pp. 2915-2923). PMLR.

Jiang, N. (2018). Notes on state abstractions. Lecture notes, University of Illinois at Urbana-Champaign. https://nanjiang.cs.illinois.edu/files/cs598/note4.pdf.

Comparison with other deep learning methods

We took Allen et al. (2021) as the main baseline since that work already established an advantage over other representation learning methods (DBC (Zhang et al., 2021), DeepMDP (Gelada et al., 2019), CPC (Oord et al., 2018), and CURL (Laskin et al., 2020)) in online continuous control tasks. Nevertheless, we took your recommendation into account and made experiments with DBC on our continuous control domains (Appendix F). On the DMC’s Cheetah setting (clean), DBC gets around 100 reward, whereas Weak MSA (our proposal), MSA (strong), and RAD (default baseline) get higher than 400 reward. We included these results in the updated manuscript.

Zhang et al. Learning invariant representations for reinforcement learning without reconstruction. In ICLR, 2021.

Gelada et al. Deepmdp: Learning continuous latent space models for representation learning. In ICML, pp. 2170–2179. PMLR, 2019.

Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv:1807.03748, 2018.

Michael Laskin, Aravind Srinivas, and Pieter Abbeel. Curl: Contrastive unsupervised representations for reinforcement learning. In ICML, pp. 5639–5650. PMLR, 2020.

Thank you again for your feedback. We hope our response clarified your questions. Please let us know if you have any further questions.

Reviewer_K3W2OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents a reasonable refinement to past work on learning reward-free state representations. The observation seems sound to me, and the proposed solutions seem reasonable.

I think learning reward-free representations can be useful, and can help learning even if we ultimately care about rewards. It would have been nice to see more results related to the motivations to do this specifically, e.g., on multi-task settings, but I don't view that as essential.

There is some disconnect between theory and practice. For instance, Eq. (2) conditions on the policy, but in the loss L_match (Eq. (3) and (4)) this conditioning is missing. Concretely, how should we train these classifiers? Should we, in general, do this in advance or online, during the RL? How much does either choice impact performance? Can things go wrong if you do this wrong? Can we learn abstractions early on that we can't recover from? I would have liked a deeper dive into these topics.

The new weak objective seems equivalent to p(z|s') = p(z|z'), i.e., the next abstract state tells us as much about the previous abstract state as the true next state does. Perhaps this could motivate a different loss. This is no criticism, just an observation.

The loss coefficients seems to differ by as much as an order of magnitude between experiments. I would have appreciated a sensitivity analysis on these. Also, what happens when λ = 0?

I appreciated the toy experiments that add clarity to the paper.

Critical strengths

The approach is clear, well-motivated, and the solutions are reasonable. Overall, I found this to be quite a clear paper, and I liked the toy experiments to highlight the issue and to understand the properties of different solution techniques.

Critical weaknesses

The policy dependency of Eq. (2) is silently dropped later on. Offline and online experiments are performed, but the role of the policy is not investigated very deeply.

The new hyper-parameters seem tuned over a pretty wide range (differing by an order of magnitude between experiments). A sensitivity analysis would be good to inform the reader how hard these are to tune.

Questions for authors
  • Have you tried other representation-learning techniques? I'm curious how much of the gains are due to the additional learning signal vs the learning direction.
  • Have you tried λ = 0 to check the impact of L_rate?
  • How hard was it to tune the new hyper-parameters?
  • The losses seem reasonable, but also don't seem to be the only way to formalize the objective. Have you tried other variations?
2 comments

Thank you for your comments.

Disconnect between theory and practice

We have missed the subscripts in Equations 3 and 4—they are policy (and time) dependent as well. Thank you for noticing this!

As for your comment about the gap between theory and practice, based on our experiments, objectives we defined in the paper are well-behaved across a wide parameter range. Our new ablation experiments on the coefficients provide evidence for this (more below).

As you also noticed, the learned abstractions are directly dependent on the policy that collects observations. Things can go wrong if, for instance, the exploration policy depends on the abstraction, and the abstraction converges prematurely. Our chain-walk experiments (Sec. 4) use the uniform policy to collect samples, and the RL experiments explore with an epsilon-greedy action selection for DDQN (Sec. 5.1), and use the standard deviation in SAC’s actor (Sec. 5.2) to encourage exploration regardless of the current abstraction to prevent this scenario. While learning abstractions and doing exploration based on them at the same time would be interesting, for the purpose of this paper, we consider them as two separate problems and focus on abstraction learning in isolation (by encouraging exploration with random action sampling).

Other representation learning techniques

We took Allen et al. (2021) as the main baseline, as we are proposing changes to their objectives, and their approach already performs better than autoencoders, DeepMDP, DBC, CURL, CPC, and RAD. In our experiments in Sec. 5, we used DQN and SAC-RAD to set a baseline for what we should expect—not necessarily to show the best-performing method. Our main motivation was systematically showing if we are getting the representation we are expecting with our proposed objectives, and whether that improves the task performance or not.

Are hyperparameters sensitive?

We have done extensive ablation analysis to provide evidence for the hyperparameter range (Appendices D and E). Regarding your question about the impact of L_rate, the inverse and the density match conditions are satisfied when the coarsest abstraction is found. However, they are also satisfied for finer abstractions. As such, when we set the rate coefficient to zero, although it is possible to find the coarsest representation, there is no guarantee that the learned representation would be minimal. For example, the ground MDP also minimizes L_inv and L_match, however, it is not minimal. Our new ablations show that even a small coefficient on L_rate drives representations toward minimality. When set to zero, we no longer favor coarser representations. When it is set to a high value such as 1, it overweighs and prevents other objectives from being minimized. In that sense, it is analogous to weight decay—a simple regularization that encourages simpler solutions. Our new ablations show that relatively small rate coefficients yield coarser abstractions in the chain-walk domain, and the return varied modestly across all coefficients in the continuous control task.

Other losses we have tried

We agree that there could be other ways to formalize these conditions into training objectives. One particular alternative that we have (extensively) tried was minimizing the difference between I(Z; S’) - I(Z; Z’) while maximizing them separately in alternating steps. The motivation was that I(Z; S’) is always greater than or equal to I(Z; Z’) (because of the data processing inequality—Z’ cannot give more information than S’ about Z), and we tried minimizing an upper bound for I(Z; S’) and maximizing a lower bound for I(Z; Z’). And this is very similar to the approach you proposed with p(z|s’) = p(z|z’). This approach also worked to some extent, but we had difficulties optimizing the bounds.

Thank you again for your feedback. We hope our response clarified your questions. Please let us know if you have any further questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.