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

2025/06/11 by Thomas J. Ringstrom, Paul Schrater, Ringstrom, Thomas J. +1
Computer Science · Neuroscience · #AI-based Problem Solving and Planning #Artificial Intelligence (cs.AI) #Embodied and Extended Cognition #FOS: Computer and information sciences #Machine Learning (cs.LG) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2506.09499

openalex publication_date 2025/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Combining Behaviors with the Successor Features Keyboard
• Composing Task Knowledge with Modular Successor Feature Approximators
• Continuous Homeostatic Reinforcement Learning for Self-Regulated Autonomous Agents
• Temporally Abstract Partial Models
• Verifiable and Compositional Reinforcement Learning Systems
• What can I do here? A Theory of Affordances in Reinforcement Learning
• Few-Shot Bayesian Imitation Learning with Logical Program Policies
• Certified Reinforcement Learning with Logic Guidance
• Reinforcement Learning and Control as Probabilistic Inference: Tutorial and Review
• Verifiable Reinforcement Learning via Policy Extraction
• PDDLStream: Integrating Symbolic Planners and Blackbox Samplers via\n Optimistic Adaptive Planning
• Reinforcement Learning With Temporal Logic Rewards
• Unifying task specification in reinforcement learning
• Compositional Planning Using Optimal Option Models

Related

• Goal Kernel Planning: Linearly-Solvable Non-Markovian Policies for Logical Tasks with Goal-Conditioned Options
• On Reward Structures of Markov Decision Processes
• Reward is not Necessary: How to Create a Modular & Compositional Self-Preserving Agent for Life-Long Learning
• Average-Reward Learning and Planning with Options
• Goal-oriented inference of environment from redundant observations