Compositional Behavioral Semantics for State Abstraction in Reinforcement Learning

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.

Reinforcement learning systems often face too many possible situations to treat each one separately. Researchers therefore simplify the problem by grouping situations together, much like using a map that leaves out small details while keeping the routes that matter. But a simplification is only useful if it preserves the behavior we care about. For example, an agent learning to navigate a building might treat several rooms as the same kind of situation if they lead to the same choices and outcomes. This paper gives researchers a way to specify which behaviors matter, such as expected rewards, safety requirements, or ways of comparing two situations, and then prove whether those behaviors survive after situations are grouped together. The result is a general toolkit for reasoning about simplification in reinforcement learning. Rather than analyzing each notion of behavior from scratch, researchers can use one framework to define, compare, and transfer many of them across original and simplified systems. This can make future reinforcement learning methods easier to analyze and justify.