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

arXiv: https://arxiv.org/abs/2506.09499 · HTML: https://mlsanity.com/paper/2506.09499/

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

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 16 of 16)

- [Reinforcement Learning and Control as Probabilistic Inference: Tutorial and Review](https://mlsanity.com/paper/1805.00909/) (2018)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [Verifiable Reinforcement Learning via Policy Extraction](https://mlsanity.com/paper/1805.08328/) (2018)
- [PDDLStream: Integrating Symbolic Planners and Blackbox Samplers via Optimistic Adaptive Planning](https://mlsanity.com/paper/1802.08705/) (2018)
- [Reinforcement Learning With Temporal Logic Rewards](https://mlsanity.com/paper/1612.03471/) (2016)
- [Temporal Abstraction in Reinforcement Learning with the Successor Representation](https://mlsanity.com/paper/2110.05740/) (2021)
- [Unifying task specification in reinforcement learning](https://mlsanity.com/paper/1609.01995/) (2016)
- [Certified Reinforcement Learning with Logic Guidance](https://mlsanity.com/paper/1902.00778/) (2019)
- [What can I do here? A Theory of Affordances in Reinforcement Learning](https://mlsanity.com/paper/2006.15085/) (2020)
- [Few-Shot Bayesian Imitation Learning with Logical Program Policies](https://mlsanity.com/paper/1904.06317/) (2019)
- [Verifiable and Compositional Reinforcement Learning Systems](https://mlsanity.com/paper/2106.05864/) (2021)
- [Combining Behaviors with the Successor Features Keyboard](https://mlsanity.com/paper/2310.15940/) (2023)
- [Temporally Abstract Partial Models](https://mlsanity.com/paper/2108.03213/) (2021)
- [Composing Task Knowledge with Modular Successor Feature Approximators](https://mlsanity.com/paper/2301.12305/) (2023)
- [Globally Optimal Hierarchical Reinforcement Learning for Linearly-Solvable Markov Decision Processes](https://mlsanity.com/paper/2106.15380/) (2021)
- [Continuous Homeostatic Reinforcement Learning for Self-Regulated Autonomous Agents](https://mlsanity.com/paper/2109.06580/) (2021)

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