mlsanityData to 14 Oct 2026

Compositional Behavioral Semantics for State Abstraction in Reinforcement Learning

arXiv 2606.25357 ↗First posted 24 Jun 2026cs.LG cs.AI math.CTcited by 0

On the map: Deep reinforcement learning methods → Interpretable and logic-guided RL

Abstract (arXiv)

State abstraction plays a key role in scaling reinforcement learning to complex but structured systems. In studying such systems, a wide range of behavioral structures have been studied in reinforcement learning, including value functions, invariants, bisimulation relations, and behavioral metrics. However, a general principle for determining what structures are provably preserved under state abstraction is still lacking. In this paper, we present a unified framework for defining and analyzing behavioral structures in reinforcement learning. Our framework provides a compositional way to specify behavioral semantics based on local, one-step descriptions of system dynamics. Using this framework, we establish results showing how behavioral structures can be safely transferred between abstract and concrete systems. We further show how to construct quantitative metrics from logical behavioral semantics with soundness guarantees. Together, these results provide a principled foundation for reasoning about behaviors under state abstraction in reinforcement learning and offer reusable definition and proof principles for a broad class of behavioral structures in reinforcement learning.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Interpretable and logic-guided RL, one of 15 directions in Deep reinforcement learning methods. Builds on 45 of its 92 references that are in the map. First posted on arXiv 24 Jun 2026.

Builds on

45 of 92 references.

References · 45

  1. 2017Safe Reinforcement Learning via Shieldingcited by 449
  2. 2020Learning Invariant Representations for Reinforcement Learning without Reconstructioncited by 436
  3. 2016Successor Features for Transfer in Reinforcement Learningcited by 340
  4. 2020Data-Efficient Reinforcement Learning with Self-Predictive Representationscited by 318
  5. 2019DeepMDP: Learning Continuous Latent Space Models for Representation Learningcited by 207
  6. 2020Reward Machines: Exploiting Reward Function Structure in Reinforcement Learningcited by 191
  7. 2024Deep Reinforcement Learning for Robotics: A Survey of Real-World Successescited by 176
  8. 2020MDP Homomorphic Networks: Group Symmetries in Reinforcement Learningcited by 142
  9. 2019Scalable methods for computing state similarity in deterministic Markov Decision Processescited by 133
  10. 2023A Definition of Continual Reinforcement Learningcited by 101
  11. 2020The Value Equivalence Principle for Model-Based Reinforcement Learningcited by 94
  12. 2020Approximate information state for approximate planning and reinforcement learning in partially observed systemscited by 70
33 more
  1. 2017Near Optimal Behavior via Approximate State Abstractioncited by 66
  2. 2020Plannable Approximations to MDP Homomorphisms: Equivariance under Actionscited by 61
  3. 2022Reachability Constrained Reinforcement Learningcited by 59
  4. 2019A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statisticscited by 56
  5. 2021Temporal Abstraction in Reinforcement Learning with the Successor Representationcited by 54
  6. 2024Bridging State and History Representations: Understanding Self-Predictive RLcited by 54
  7. 2021Safety and Liveness Guarantees through Reach-Avoid Reinforcement Learningcited by 49
  8. 2024A Survey of Constraint Formulations in Safe Reinforcement Learningcited by 44
  9. 2018Combined Reinforcement Learning via Abstract Representationscited by 37
  10. 2018Learning Finite State Representations of Recurrent Policy Networkscited by 37
  11. 2020Can Increasing Input Dimensionality Improve Deep Reinforcement Learning?cited by 37
  12. 2022A Theory of Abstraction in Reinforcement Learningcited by 27
  13. 2022Continuous MDP Homomorphisms and Homomorphic Policy Gradientcited by 27
  14. 2025Discovering Temporal Structure: An Overview of Hierarchical Reinforcement Learningcited by 22
  15. 2013Learning Finite-State Controllers for Partially Observable Environmentscited by 19
  16. 2024A Distributional Analogue to the Successor Representationcited by 17
  17. 2025A Survey of State Representation Learning for Deep Reinforcement Learningcited by 17
  18. 2023Structure in Deep Reinforcement Learning: A Survey and Open Problemscited by 16
  19. 2023Dynamic Datasets and Market Environments for Financial Reinforcement Learningcited by 15
  20. 2024When does Self-Prediction help? Understanding Auxiliary Tasks in Reinforcement Learningcited by 14
  21. 2024Three Dogmas of Reinforcement Learningcited by 14
  22. 2025Plasticity as the Mirror of Empowermentcited by 12
  23. 2023Policy Gradient Methods in the Presence of Symmetries and State Abstractionscited by 9
  24. 2024Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficientlycited by 6
  25. 2025When Can Model-Free Reinforcement Learning be Enough for Thinking?cited by 6
  26. 2022Categorical semantics of compositional reinforcement learningcited by 5
  27. 2025A Generalized Bisimulation Metric of State Similarity between Markov Decision Processes: From Theoretical Propositions to Applicationscited by 4
  28. 2025From monoliths to modules: Decomposing transducers for efficient world modellingcited by 4
  29. 2025AI in a vat: Fundamental limits of efficient world modelling for agent sandboxing and interpretabilitycited by 3
  30. 2025Understanding Behavioral Metric Learning: A Large-Scale Study on Distracting Reinforcement Learning Environmentscited by 3
  31. 2013Generalizing determinization from automata to coalgebrascited by 2
  32. 2023Enriching Disentanglement: From Logical Definitions to Quantitative Metricscited by 2
  33. 2014Behavioral Metrics via Functor Liftingcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026A Goal-Set Characterization of Task Composition in the Boolean Task Algebra
  2. 2024Reduce, Reuse, Recycle: Categories for Compositional Reinforcement Learning
  3. 2026A Contractive Feedback Semantics for Reinforcement Learning
  4. 2024Symbolic State Partitioning for Reinforcement Learning
  5. 2026Auditability Is Not One Property: Rule Overlap, Behavioural Agreement, and Composition in Reinforcement Learning
  6. 2025Context-Sensitive Abstractions for Reinforcement Learning with Parameterized Actions
  7. 2025Automating the Refinement of Reinforcement Learning Specifications
  8. 2026Abstraction for Offline Goal-Conditioned Reinforcement Learning