💻 computer science

A Framework for Coalgebraic Reward-Sensitive Bisimulation (Extended Version)

This paper presents a unified coalgebraic framework using fibrational and gluing techniques to model reward-sensitive bisimulations that seamlessly integrate qualitative and quantitative aspects, thereby generalizing various existing notions such as relation-based and metric-based bisimulations.

Original authors: Pedro H. Azevedo de Amorim, Mayuko Kori, Koko Muroya

Published 2026-04-02

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Pedro H. Azevedo de Amorim, Mayuko Kori, Koko Muroya

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a video game with a friend. You both are navigating a maze, collecting coins, and trying to reach the exit.

The Old Way (Traditional Bisimulation):
In the past, computer scientists had a way to check if two characters in a game were "basically the same." They asked: "If I take a step left, can you take a step left? If I hit a wall, do you hit a wall?"
This is called bisimulation. It's like a mirror check. If your friend copies your every move perfectly, you are "bisimilar." It's great for checking if two paths lead to the same destination, but it ignores the score. It doesn't care if you collected 100 coins and your friend only collected 1, as long as you both reached the exit.

The New Problem (Reward-Sensitive Bisimulation):
But what if the game is about efficiency? What if you want to know: "Can my friend reach the exit with at least 90% of the coins I collected?" or "Is the difference in our scores always less than 5 points?"
Traditional mirrors can't measure that. They only say "Yes, you are the same" or "No, you are different." They can't handle the quantitative part (the numbers, the rewards, the costs).

The Paper's Solution: The "Graded Mirror"
This paper introduces a new framework called Coalgebraic Reward-Sensitive Bisimulation. Think of it as upgrading the mirror to a Graded Mirror.

Here is how the authors explain it using simple concepts:

1. The Two Types of Mirrors

The authors propose using two interacting mirrors at the same time:

The Ungraded Mirror (The "Yes/No" Mirror): This is the old-school mirror. It just checks if the moves match. "Did you go left? Yes? Good." It ignores the score.
The Graded Mirror (The "Scorekeeper" Mirror): This is the new mirror. It doesn't just check if you moved left; it checks how much it cost you to move left. It says, "You moved left and lost 2 coins. I moved left and lost 5 coins. The difference is 3. That's okay, because our tolerance is 5."

2. The "Glue" (Categorical Gluing)

The hardest part of this paper is the math behind how these two mirrors talk to each other. The authors use a technique called Categorical Gluing.

The Analogy: Imagine you have two different maps of the same city.

Map A shows only the streets (qualitative).
Map B shows the streets and the traffic jams (quantitative/rewards).

Usually, these maps are separate. You can't easily compare them. The authors invented a special "glue" (a mathematical tool called a comma object) that sticks these two maps together into one super-map.

This super-map allows you to see the street and the traffic jam simultaneously.
It proves that if you have a perfect match on the "Traffic Map" (Graded), you automatically have a match on the "Street Map" (Ungraded).
It creates a bridge where the "Scorekeeper" logic can be simplified down to the "Yes/No" logic if you don't care about the score anymore.

3. Why This Matters (The "Tolerance" Concept)

The paper introduces the idea of Grading.

Imagine a "Grade 0" relationship: You and your friend must have the exact same score.
Imagine a "Grade 5" relationship: You and your friend can have a score difference of up to 5.
Imagine a "Grade 10" relationship: You can be off by 10 points.

The framework allows computers to reason about these different "grades" of similarity. It answers questions like: "Are these two AI agents similar enough to be considered the same, even if one is slightly more efficient than the other?"

4. Real-World Examples

The authors show this works for many things:

Automated Cars: Checking if two self-driving cars follow the same rules, even if one uses slightly more fuel (reward/cost) than the other.
Probabilistic Systems: Checking if two random number generators behave similarly, even if one is slightly more likely to produce a "win" than the other.
Approximate Matching: In systems where things aren't perfect (like measuring distance), this helps define how "close" is close enough.

Summary

In short, this paper builds a universal translator between "Qualitative" (Yes/No) and "Quantitative" (How much?) thinking.

Old Way: "Are you the same?" (Yes/No).
New Way: "Are you the same, and if not, how close are your scores?" (Yes, within a tolerance of X).

By using a clever mathematical "glue," the authors created a system that can handle complex, real-world scenarios where things aren't just black and white, but exist on a spectrum of rewards and costs. This helps engineers build better, more robust software that understands not just what happens, but how much it costs to make it happen.

1. Problem Statement

Traditional bisimulation relations are effective for reasoning about qualitative properties of transition systems (e.g., whether two states accept the same language). However, they fail to capture quantitative aspects, such as accumulated rewards, costs, or distances between states.

While various quantitative refinements exist (e.g., behavioral metrics, amortized bisimulations, approximate bisimulations), there is a lack of a unified categorical/coalgebraic theory that:

Systematically models graded bisimulations (where the "grade" represents a tolerance or bound on reward differences).
Relates these graded notions to standard ungraded bisimulations.
Explains how a graded bisimulation acts as a refinement of an ungraded one (i.e., how the ungraded notion is the "collapse" of the graded one).

2. Methodology

The authors employ a coalgebraic and fibration-based approach, building on the work of Hermida and Jacobs. The core methodology involves:

Fibrational Framework: They utilize CLat $\sqcap$ -fibrations (fibrations where fibers are complete lattices and reindexing preserves meets) to model relations and quantitative structures.
Graded Relations: They introduce graded relations using a pullback construction along a diagonal functor. This allows relations to be indexed by a monoid (e.g., natural numbers for rewards, $[0,1]$ for metrics).
Categorical Gluing: The central technical innovation is the application of categorical gluing (specifically, comma objects) to combine two distinct coalgebraic models:
- An ungraded model (standard relations).
- A graded model (reward-sensitive relations).
Adjoint Gluing Doctrine: They define a specific axiomatization called an adjoint gluing doctrine. This consists of:
- Two fibrations ( $p: E \to C$ for ungraded, $p_g: E_g \to C$ for graded).
- A fibred adjunction ( $\exists_g \dashv \Delta$ ) between them, where $\Delta$ embeds ungraded relations as constant graded relations, and $\exists_g$ maps graded relations to ungraded ones by taking the union over all grades.
- Functor liftings ( $\hat{F}$ and $\hat{F}_g$ ) that respect this structure.

3. Key Contributions

A. The Adjoint Gluing Doctrine

The paper formalizes the interaction between graded and ungraded systems via a tuple $(F, p, p_g, \hat{F}, \hat{F}_g, \exists_g, \Delta, \alpha)$ . This framework provides a common language to define:

Ungraded Simulations: Coalgebras in $E$ over $c: S \to FS$ .
Graded Simulations: Coalgebras in $E_g$ over $c$ .
Glued Simulations: Coalgebras in a "glued" category (a comma category) that simultaneously tracks both the graded relation and its ungraded projection.

B. The Glued Fibration Construction

The authors construct a comma category (the "glued model") that combines the graded and ungraded fibrations.

Objects in this category are triples $(A, R, f)$ , where $A$ is a graded relation, $R$ is an ungraded relation, and $f: \exists_g(A) \to R$ is a morphism witnessing that the union of the graded relation is contained in the ungraded one.
This construction allows for a canonical lifting of the system functor that operates on both levels simultaneously.

C. Abstract Soundness Theorem

A major theoretical result is the Soundness Theorem (Theorem 3):

If $A$ is a graded simulation on a coalgebra $c$ , then $\exists_g(A)$ (the union of the graded relations) is an ungraded simulation on $c$ .

This formally proves that graded bisimulations are indeed refinements of ungraded ones. The proof relies on the universal properties of the comma object and the natural transformation $\alpha: (\exists_g \circ \hat{F}_g) \Rightarrow (\hat{F} \circ \exists_g)$ .

D. Characterization of Final Coalgebras

The paper characterizes the final coalgebra in the glued model. It shows that the carrier of the final coalgebra for the glued functor consists of the pair of final coalgebras from the graded and ungraded components ( $\nu \hat{F}_g$ and $\nu \hat{F}$ ). This provides a coinductive principle for reasoning about systems with both qualitative and quantitative properties.

4. Results and Examples

The framework is demonstrated to be versatile by instantiating it on several distinct systems:

Deterministic Automata with Rewards (DAwR):
- A new notion of graded simulation is defined where the grade $n$ bounds the difference in accumulated rewards.
- The framework proves that the union of these graded relations yields the standard language inclusion simulation.
Amortized Bisimulations (Labelled Transition Systems):
- Generalizes Kiehn and Arun-Kumar's work on amortized bisimulations.
- Rewards are assigned locally to transitions. The graded relation tracks the "debt" or accumulated reward difference, showing it refines standard LTS bisimulation.
Probabilistic Systems (Markov Decision Processes - MDPs):
- Models MDPs with expected rewards.
- Defines graded simulations over the monoid of positive real numbers ( $\mathbb{R}^+$ ), capturing reward-sensitive refinements of probabilistic simulations.
Labelled Markov Processes (LMPs) and Metrics:
- Connects pseudometric-based bisimulations (using Lévy-Prokhorov metrics) with relation-based graded bisimulations.
- Uses the unit interval $[0,1]$ as a grading quantale.
- Proves that for finite state spaces, a metric-based bisimulation induces a relation-based graded bisimulation and vice versa, unifying the metric and relational viewpoints.

5. Significance

Unification: The paper provides the first unified coalgebraic framework that treats graded (quantitative) and ungraded (qualitative) bisimulations as interacting components of a single structure, rather than isolated concepts.
Formal Rigor: It moves beyond ad-hoc definitions of reward-sensitive bisimulations by grounding them in categorical logic (gluing, fibrations, adjunctions).
Modularity: The "Adjoint Gluing Doctrine" is a reusable pattern. It allows researchers to define new quantitative systems by simply specifying the grading monoid and the fibration, while automatically inheriting the soundness and structural properties (like final coalgebras) of the framework.
Bridging Gaps: It successfully bridges the gap between relation-based reasoning (common in verification) and metric-based reasoning (common in probabilistic and approximate systems), showing they are two sides of the same categorical coin.

In summary, the paper establishes a robust theoretical foundation for reward-sensitive bisimulation, proving that quantitative refinements are not just ad-hoc extensions but are structurally inherent refinements of standard bisimulations, accessible through the machinery of categorical gluing.