A Unified Theory of Compositionality, Modularity, and Interpretability in Markov Decision Processes

arXiv 2506.09499 ↗First posted 11 Jun 2025cs.LG cs.AIcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We introduce Option Kernel Bellman Equations (OKBEs) for a new reward-free Markov Decision Process. Rather than a value function, OKBEs directly construct and optimize a predictive map called a state-time option kernel (STOK) to maximize the probability of completing a goal while avoiding constraint violations. STOKs are compositional, modular, and interpretable initiation-to-termination transition kernels for policies in the Options Framework of Reinforcement Learning. This means: 1) STOKs can be composed using Chapman-Kolmogorov equations to make spatiotemporal predictions for multiple policies over long horizons, 2) high-dimensional STOKs can be represented and computed efficiently in a factorized and reconfigurable form, and 3) STOKs record the probabilities of semantically interpretable goal-success and constraint-violation events, needed for formal verification. Given a high-dimensional state-transition model for an intractable planning problem, we can decompose it with local STOKs and goal-conditioned policies that are aggregated into a factorized goal kernel, making it possible to forward-plan at the level of goals in high-dimensions to solve the problem. These properties lead to highly flexible agents that can rapidly synthesize meta-policies, reuse planning representations across many tasks, and justify goals using empowerment, an intrinsic motivation function. We argue that reward-maximization is in conflict with the properties of compositionality, modularity, and interpretability. Alternatively, OKBEs facilitate these properties to support verifiable long-horizon planning and intrinsic motivation that scales to dynamic high-dimensional world-models.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 16 of its 36 references that are in the map. First posted on arXiv 11 Jun 2025.

Builds on

16 of 36 references.

References · 16

2018Reinforcement Learning and Control as Probabilistic Inference: Tutorial and Reviewcited by 482
2020Reward Machines: Exploiting Reward Function Structure in Reinforcement Learningcited by 191
2018Verifiable Reinforcement Learning via Policy Extractioncited by 177
2018PDDLStream: Integrating Symbolic Planners and Blackbox Samplers via Optimistic Adaptive Planningcited by 150
2016Reinforcement Learning With Temporal Logic Rewardscited by 117
2021Temporal Abstraction in Reinforcement Learning with the Successor Representationcited by 54
2016Unifying task specification in reinforcement learningcited by 41
2019Certified Reinforcement Learning with Logic Guidancecited by 36
2020What can I do here? A Theory of Affordances in Reinforcement Learningcited by 35
2019Few-Shot Bayesian Imitation Learning with Logical Program Policiescited by 30
2021Verifiable and Compositional Reinforcement Learning Systemscited by 13
2023Combining Behaviors with the Successor Features Keyboardcited by 12

4 more

2021Temporally Abstract Partial Modelscited by 11
2023Composing Task Knowledge with Modular Successor Feature Approximatorscited by 7
2021Globally Optimal Hierarchical Reinforcement Learning for Linearly-Solvable Markov Decision Processescited by 6
2021Continuous Homeostatic Reinforcement Learning for Self-Regulated Autonomous Agentscited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way