mlsanityData to 14 Oct 2026

Adaptive state-action abstractions via rate-distortion

arXiv 2606.06123 ↗First posted 4 Jun 2026cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

When learning to walk, infants seem to address a coarse version of the problem first - stay upright, reach the caregiver - and refine it only when further practice at that resolution stops paying off. Reinforcement learning offers multiple techniques for building simple versions of complex tasks, but lacks general principles for how to dynamically adjust the granularity of these abstractions during learning. This paper proposes one such principle: refine the abstraction as soon as the learning error within it becomes comparable to the error induced by the abstraction itself. Here, we investigate one way of formalising this principle via a performance certificate that decomposes value error into two terms: a learning error bound captured by a Bellman residual, and an abstraction error bound given by a bisimulation metric. The resulting switching strategy is implemented by soft state-action abstractions built from rate-distortion principles, whose resolution along state and action axes can be continuously adjusted. We validate this construction in a range of tabular settings, showing that near-optimal performance can be achieved under substantial lossy compression of state and action information.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 26 of its 68 references that are in the map. First posted on arXiv 4 Jun 2026.

Builds on

26 of 68 references.

References · 26

  1. 2016The Option-Critic Architecturecited by 448
  2. 2020Learning Invariant Representations for Reinforcement Learning without Reconstructioncited by 436
  3. 2023Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Taskscited by 327
  4. 2019DeepMDP: Learning Continuous Latent Space Models for Representation Learningcited by 207
  5. 2018Deep learning generalizes because the parameter-function map is biased towards simple functionscited by 183
  6. 2021The Low-Rank Simplicity Bias in Deep Networkscited by 154
  7. 2020MDP Homomorphic Networks: Group Symmetries in Reinforcement Learningcited by 142
  8. 2019Scalable methods for computing state similarity in deterministic Markov Decision Processescited by 133
  9. 2021Contrastive Behavioral Similarity Embeddings for Generalization in Reinforcement Learningcited by 123
  10. 2019Generalization in Reinforcement Learning with Selective Noise Injection and Information Bottleneckcited by 101
  11. 2019InfoBot: Transfer and Exploration via the Information Bottleneckcited by 78
  12. 2017Near Optimal Behavior via Approximate State Abstractioncited by 66
14 more
  1. 2021Towards Robust Bisimulation Metric Learningcited by 49
  2. 2021MICo: Improved representations via sampling-based state similarity for Markov decision processescited by 43
  3. 2022Continuous MDP Homomorphisms and Homomorphic Policy Gradientcited by 27
  4. 2021Deciding What to Learn: A Rate-Distortion Approachcited by 23
  5. 2022Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learningcited by 19
  6. 2021The Value of Information When Deciding What to Learncited by 15
  7. 2013Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processescited by 10
  8. 2020Learning Discrete State Abstractions With Deep Variational Inferencecited by 10
  9. 2023Understanding and Addressing the Pitfalls of Bisimulation-based Representations in Offline Reinforcement Learningcited by 10
  10. 2021Distillation of RL Policies with Formal Guarantees via Variational Abstraction of Markov Decision Processes (Technical Report)cited by 9
  11. 2023Policy Gradient Methods in the Presence of Symmetries and State Abstractionscited by 9
  12. 2022On Rate-Distortion Theory in Capacity-Limited Cognition & Reinforcement Learningcited by 6
  13. 2022Between Rate-Distortion Theory & Value Equivalence in Model-Based Reinforcement Learningcited by 2
  14. 2025Existence and Synthesis of Multi-Resolution Approximate Bisimulations for Continuous-State Dynamical Systemscited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Context-Sensitive Abstractions for Reinforcement Learning with Parameterized Actions
  2. 2026Measuring the Stability Assumption Behind Action Chunking
  3. 2025Memento 2: Learning by Stateful Reflective Memory
  4. 2025Dynamic Action Interpolation: A Universal Approach for Accelerating Reinforcement Learning with Expert Guidance
  5. 2025The Pitfalls of Imitation Learning when Actions are Continuous
  6. 2024Building Minimal and Reusable Causal State Abstractions for Reinforcement Learning
  7. 2026Performance-Driven Environment Abstraction with Multi-Timescale Learning
  8. 2026Tape: A Cellular Automata Benchmark for Evaluating Rule-Shift Generalization in Reinforcement Learning