Composing Value Functions for Zero Shot Generalization

57 concepts49 papers1 proposal

When humans learn to navigate to a red ball and pick up a blue cube, they do not need to undergo a new training regimen to "navigate to a red ball and pick up a blue cube." We naturally decompose tasks into modular primitives and recombine them instantly to satisfy novel goals.

Traditional Reinforcement Learning (RL) agents lack this capability. Standard deep RL algorithms treat tasks as monolithic entities, mapping raw states to actions or values for a single, fixed reward function. When the environment or the goal changes—even if the new objective is a simple logical combination of previously mastered skills—the agent's performance collapses, a limitation highlighted by benchmarks like Avalon (Joshua Albrecht et al.). To solve a new permutation of subtasks, a standard agent must typically relearn its policy from scratch.

The field of compositional reinforcement learning addresses this gap. Its core insight is that if we can structure an agent's representations and value functions correctly, we can bypass retraining entirely, mathematically fusing pre-learned skills to solve novel, complex tasks zero-shot.

Why Standard RL Fails to Compose

To understand why skills cannot be easily combined out of the box, we must look at the mathematical engine of standard RL: the Bellman optimality equation.

$$Q^*(s,a) = R(s,a) + \gamma \max_{a'} Q^*(s', a')$$

The presence of the $\max$ operator makes this equation fundamentally non-linear. Suppose an agent has learned the optimal action-value functions $Q^*_1$ and $Q^*_2$ for two distinct rewards, $R_1$ and $R_2$. If we present the agent with a new task whose reward is the sum of the two ($R_{\text{total}} = R_1 + R_2$), simply adding the value functions together ($Q^*_1 + Q^*_2$) will not yield the optimal value function for the combined task.

Because the $\max$ operator does not distribute over addition, the optimal policy for a compound goal is not a simple linear combination of the optimal policies for its parts (Andrew M Saxe et al.). This mathematical barrier forces traditional agents to treat every combination of objectives as a brand-new problem.

Linearizing the Bellman Equation

To make skills composable, we must change the underlying mechanics of the Markov Decision Process (MDP) to eliminate or smooth out this non-linearity. Researchers have converged on two primary frameworks to achieve this:

1. Linearly-Solvable MDPs (LMDPs)

Instead of forcing the agent to choose hard, discrete actions, LMDPs frame control as choosing a probability distribution over next states. The agent pays a penalty proportional to the KL-divergence between its chosen distribution and a passive, baseline dynamics distribution.

As demonstrated by Anders Jonsson et al. and Andrew M Saxe et al., this formulation transforms the non-linear Bellman equation into a system of linear equations. In this linearized space, the desirability of a state under a combination of goals becomes directly stackable, allowing optimal policies to be executed concurrently or hierarchically without further training.

2. Entropy-Regularized RL (Soft Q-Learning)

Another approach is to augment the standard reward function with a penalty that encourages policy entropy, preventing the agent from collapsing prematurely into a single deterministic action. The standard $\max$ operator is replaced by a smooth, differentiable $\text{log-sum-exp}$ (or "soft-max") operator.

Tuomas Haarnoja demonstrated that policies trained via maximum entropy possess unique composability properties, allowing independently learned skills (such as reaching and obstacle avoidance) to be merged into compound behaviors. Building on this mathematical foundation, Steven James proved that the optimal value function for a composite logical "OR" task can be computed directly as a weighted combination of individual value functions in the exponentiated space.

Logical Composition and Task Algebras

When value functions can be combined linearly in a transformed space, we can construct a formal Boolean algebra over tasks. This allows us to use logical operators (AND, OR, NOT) to synthesize new behaviors.

Geraud Nangue Tasse et al. formalized this framework for lifelong learning. If an agent has a library of value functions for basic tasks, it can instantly compute the exact value function for a complex instruction like "go to the room that has a key AND does NOT have an enemy" by applying algebraic operations directly to its pre-trained Q-functions.

[Task A: Find Key] --------> Q_A(s,a) \
                                        --> [Algebraic Fusion] --> Q_combined(s,a)
[Task B: Avoid Enemy] ------> Q_B(s,a) /

To make this practical across high-dimensional task spaces, Lucas N. Alegre et al. proposed the Option Keyboard Basis (OKB). Instead of learning an infinite number of separate policies, the agent learns a minimal set of "seed" policies that span the task space. A learned meta-policy can then dynamically combine these base behaviors to solve novel linear and non-linear task configurations instantly.

Factoring the World into Attributes

Mathematical compositionality at the policy level is only half the battle; it requires a corresponding modularity in how the agent perceives the world. If an agent views a scene as an unparsed block of pixels, it cannot isolate the components necessary to execute a composed value function.

To address this, researchers design world models that explicitly factor environments into independent attributes or objects:

  • Attribute Planning: Amy Zhang et al. introduced planners that operate over human-interpretable attributes (e.g., "block A is on block B"). By learning transitions between simple properties rather than full states, the agent can stitch these transitions together to achieve long-term goals it never saw during training.
  • Object-Centered Dynamics: Fan Feng et al. and Sungbin Mun et al. developed attribute-factored and 3D disentangled object representations. By breaking visual scenes into individual objects with distinct properties (color, shape, position), agents can successfully manipulate novel pairings of attributes that were never encountered together during training.
  • Disentangled Skill Discovery: If discovered skills are messy and "entangled," using one skill might inadvertently disrupt another state factor (e.g., a skill meant to steer a robot might accidentally alter its speed). Jiaheng Hu et al. demonstrated that explicitly regularizing unsupervised skill discovery to isolate specific state factors preserves behavioral modularity, ensuring that skills can be cleanly composed downstream.

Language as a Compositional Scaffold

How do we communicate these complex, composed goals to an agent? Natural language provides a highly structured, pre-existing combinatorial framework. Rather than treating text commands as monolithic strings, modern compositional RL frameworks leverage language as the "glue" for hierarchical decision-making.

Ekin Akyürek et al. demonstrated that pre-trained Large Language Models (LLMs) can serve as a sequential decision-making scaffold, translating complex environmental observations and goals into structured sub-goals and yielding massive gains in combinatorial generalization. To bridge the gap between language and control, Lajanugen Logeswaran et al. combined an attention-based subgoal predictor with an additive decomposition of action-value functions, enabling an agent to execute novel combinations of actions and objects (such as slicing a fruit it has only ever picked up) based purely on text instructions.

Taking this integration to its logical conclusion, Vanya Cohen developed CERLLA, a framework where an LLM parses natural language instructions directly into explicit Boolean expressions. These expressions map one-to-one onto the underlying logical composition of the agent's base behaviors, providing a direct pipeline from human speech to zero-shot algebraic policy fusion.

Key Foundational Work

Hierarchical Linearly-Solvable Markov Decision Problems (2016) — contributed 1 concept elements to this direction.
Reinforcement Learning with a Hierarchy of Abstract Models (1992) — contributed 1 concept elements to this direction.
Hierarchy through Composition with Linearly Solvable Markov Decision Processes (2016) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_compositional_generalization_task_compos_3c5b2ccc,
  title = {compositional generalization (task compositionality)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compositional-generalization-task-compositionality/rdr_3c5b2ccca3614442bf4cdfb4d741a7d1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_compositional_generalization_task_compos_3c5b2ccc_v1,
  title = {compositional generalization (task compositionality)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compositional-generalization-task-compositionality/rdr_3c5b2ccca3614442bf4cdfb4d741a7d1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake