🤖 machine learning

Universal Decision Learners

This paper proposes a universal categorical framework called Universal Decision Learners (UDL) that unifies diverse decision-making theories—such as planning, reinforcement learning, and game theory—by characterizing them as canonical extensions of local behavioral data to globally coherent behavior via left and right Kan extensions.

Original authors: Sridhar Mahadevan

Published 2026-06-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sridhar Mahadevan

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 trying to teach a robot how to make good decisions. Usually, we teach it by showing it specific examples: "If you see a red light, stop." "If you see a green light, go." But the real world is full of situations the robot has never seen before. How does it figure out what to do in a brand-new scenario?

This paper proposes a new way to think about that problem. It suggests that all the different ways we teach machines to decide—whether it's planning a route, learning from rewards, or figuring out game strategies—are actually just different versions of the same mathematical trick. The author calls this a Universal Decision Learner (UDL).

Here is the core idea, broken down with simple analogies:

The Two-Step Recipe for Decision Making

The paper argues that learning to decide is a two-step process. Think of it like baking a cake, but instead of flour and eggs, you are using Local Data (what you've seen) and Global Rules (what makes sense everywhere).

Step 1: The "Rollout" (Left Kan Extension)

The Metaphor: Imagine you are a travel agent who has only seen a few short trips. You want to plan a massive, cross-country journey.

What you do: You take all the small, known trip segments you have and stitch them together to imagine every possible way to get to your destination. You are "rolling out" possibilities.
In the paper: This is called a Left Kan Extension. It takes local information (like a single step in a game or a short path) and aggregates it to generate candidates for new, larger situations. It answers the question: "Based on what I know, what are all the possible ways to get there?"

Step 2: The "Consistency Check" (Right Kan Extension)

The Metaphor: Now that you have a list of possible cross-country routes, you need to check if they actually work. Maybe a bridge is out, or a train schedule doesn't match. You look at the end of the journey and work backward to see if the start makes sense.

What you do: You filter your list. You keep only the routes that are consistent with all the rules and constraints of the world. If a route leads to a dead end, you discard it.
In the paper: This is called a Right Kan Extension. It takes the "rolled out" possibilities and forces them to satisfy global rules. It answers the question: "Which of these possibilities actually makes sense when I look at the whole picture?"

The "Universal" Part

The paper's main claim is that almost every famous decision-making method in computer science is just a specific way of doing these two steps:

Planning: You roll out paths (Step 1) and pick the best one that fits the destination (Step 2).
Reinforcement Learning (Learning by rewards): You roll out future rewards (Step 1) and find the value that stays consistent no matter how many steps you take (Step 2). This is exactly what the famous "Bellman Equation" does.
Game Theory: You look at what your opponent might do (Step 1) and find a strategy that is consistent with everyone else's best moves (Step 2). This is how you find a "Nash Equilibrium."
Causal Inference: You look at how changing one thing affects another locally (Step 1) and ensure your conclusion holds up under all possible interventions (Step 2).

Why This Matters (The "Universal" Guarantee)

The paper doesn't just say "these things look similar." It uses advanced math (Category Theory) to prove that this two-step method is the only way to do it that is mathematically "fair" and "canonical."

Think of it like a universal translator. If you have a local rule (like "stop at red"), there are infinite ways to guess what happens at a new color (like "orange"). But this paper says there is one specific, mathematically perfect way to extend that rule that doesn't rely on arbitrary guesses. It's the "gold standard" extension.

Abstraction: Seeing the Forest, Not the Trees

The paper also talks about Abstraction. Sometimes, two different situations look different on the surface but are actually the same deep down.

Example: In a video game, a "red goblin" and a "blue goblin" might look different, but if they both drop the same gold and move the same way, they are effectively the same for the player.
The Paper's View: The math proves that you can safely ignore the differences between them if their "Universal Decision" outcome is the same. This helps simplify complex problems by grouping similar situations together without losing the ability to make good decisions.

Summary

In short, this paper says:

Decision making is about extending local knowledge to the unknown.
There are two universal moves to do this: First, imagine all possibilities (Rollout), then filter them for consistency (Check).
Everything fits: Whether it's planning a trip, playing chess, or learning from rewards, they are all just different flavors of this same two-step mathematical process.

The paper is a theoretical blueprint. It doesn't give you a new app or a new robot to buy; instead, it gives us a single, unified language to understand how any decision-making system works, proving that deep down, they are all solving the same fundamental puzzle.

Technical Summary: Universal Decision Learners

Problem Statement

The paper addresses the challenge of unifying diverse theories of decision making—including planning, reinforcement learning (RL), causal intervention, online learning, and game-theoretic equilibrium. While these fields appear distinct, they share a common structural problem: how to extend partial, local behavioral data (observed in specific contexts) into globally coherent decisions for new, unobserved contexts.

Traditional approaches based on function approximation over sets (e.g., metric or vector spaces) fail to provide an overarching theory because they lack a canonical solution to the extension problem. The paper posits that category theory, specifically through Kan extensions, offers the necessary canonical framework to formalize this extension process.

Methodology: The Universal Decision Learner (UDL)

The core methodology proposes the Universal Decision Learner (UDL) as a categorical construction that extends a partially specified decision functor.

1. Formal Setup

Contexts: Let $\mathcal{D}$ be a category of locally observed contexts and $\mathcal{C}$ be a larger category of contexts where decisions must be made.
Inclusion: A functor $J: \mathcal{D} \to \mathcal{C}$ encodes the inclusion of observed contexts into the global context.
Local Data: A functor $F: \mathcal{D} \to \mathcal{E}$ encodes local decision data, where $\mathcal{E}$ is a category of decision objects (e.g., utilities, probability distributions, policy spaces).
Goal: Construct a functor $\mathcal{C} \to \mathcal{E}$ that agrees with or is coherently related to $F$ .

2. The Two-Stage Construction

The UDL is defined as the composite of two Kan extensions:
$\text{UDL}_J(F) = \text{Ran}_J(\text{Lan}_J F)$

Stage 1: Left Kan Extension ( $\text{Lan}_J F$ )
- Function: Expresses rollout, aggregation, and candidate generation.
- Mechanism: It pushes local decision data forward into larger contexts. Pointwise, it aggregates all observed ways of reaching a context $c$ (via the colimit over the comma category $J \downarrow c$ ).
- Interpretation: In planning, this corresponds to finding the best accumulated reward among all paths to a state; in attention mechanisms, it aggregates relevant keys/memories.
Stage 2: Right Kan Extension ( $\text{Ran}_J$ )
- Function: Expresses consistency, constraint satisfaction, and fixed-point semantics.
- Mechanism: It assembles a decision from constraints imposed by continuations or observations. Pointwise, it computes the object compatible with all observed consequences of $c$ (via the limit over the comma category $c \downarrow J$ ).
- Interpretation: This captures backward consistency, Bellman-style fixed points, feasibility constraints, and coinductive semantics.

3. Reward-Enriched Form

For many decision problems, the category $\mathcal{E}$ is enriched over a semiring (e.g., max-plus for shortest paths, probability for standard RL). In this setting:

The Left Kan extension takes the form of a dynamic programming update: $(\text{Lan}_J F)(c) = \max_{Jd \to c} (F(d) + w(d \to c))$ .
The Right Kan extension represents the tightest value satisfying downstream inequalities induced by all continuations.

Key Contributions

Formal Definition: The paper defines Universal Decision Learners as Kan-extension semantics for partial decision data, providing a unified categorical language for decision making.
Decomposition of Learning: It decomposes decision learning into two distinct semantic operations:
- Rollout via Left Kan extension (expansion/aggregation).
- Consistency via Right Kan extension (filtering/gluing).
Universal Comparison Theorem: The paper proves that UDLs are canonical among all globally defined decision models compatible with local data. Specifically, any global model $G$ compatible with the local data admits a unique comparison map to the UDL. If this map is an isomorphism, $G$ computes the same semantics as the UDL.
Abstraction and Equivalence:
- Kan Invariance: Defines behavioral equivalence as invariance under universal extension.
- Minimal Abstractions: Proves the existence of a minimal Kan-invariant quotient that identifies exactly those contexts whose extended behaviors are indistinguishable. This turns abstraction into a semantic operation rather than a syntactic one.
- Homotopy Kan Invariance: Extends the concept to allow for approximate equivalence (e.g., in causal inference or approximate RL), where models are equivalent if their induced semantics can be deformed into one another without changing observable consequences.
Derivation of Special Cases: The paper demonstrates that Bellman equations, planning recursions, causal interventions, online regret minimization, and Nash equilibria are all special instances of the same UDL construction.

Results and Special Cases

The paper does not present empirical benchmarks but derives theoretical results showing how established formalisms instantiate the UDL:

Planning: Modeled as a Left Kan extension in a max-plus category, aggregating path fragments to find optimal plans.
Reinforcement Learning: Modeled primarily as a Right Kan extension. The value function is the globally consistent extension of local reward/transition data. The Bellman optimality equation is identified as the pointwise Right Kan consistency condition. RL algorithms (Value Iteration, Q-learning) are interpreted as stochastic approximations or metric coinductions toward this fixed point.
Game-Theoretic Equilibrium: Nash equilibrium is viewed as a global section of a strategic decision functor that survives all local best-response tests (a Right Kan fixed point).
Online Learning: Sublinear regret is interpreted as approximate Kan consistency over time, where the learner's strategy becomes asymptotically indistinguishable from the best comparator.
Causal Intervention: Identifiability is framed as the invariance of the Kan-extended global semantics under different local structural presentations.

Significance and Claims

The paper's primary claim is unification through semantics, not the introduction of new algorithms or empirical benchmarks.

Canonical Nature: The central thesis is that while specific decision problems may have different algorithms, they instantiate the same universal problem: canonically extending local behavioral data and characterizing the globally coherent extensions.
Semantic Clarity: By using Kan extensions, the paper provides a rigorous way to distinguish between the semantic solution (the universal extension) and its computational implementation (e.g., specific RL algorithms).
Abstraction: The framework offers a principled method for defining minimal abstractions in decision making, ensuring that abstraction preserves the universal extension that determines observable behavior.

The authors explicitly state that the paper is theoretical, aiming to identify a "unifying semantic structure" rather than to propose a new neural architecture or empirical benchmark. The supplementary material (referenced but not included in the main text) is noted to develop the reinforcement learning specialization in greater detail.