# Formalizing Task-Space Complexity for Zero-Shot Generalization

arXiv: https://arxiv.org/abs/2606.20967 · HTML: https://mlsanity.com/paper/2606.20967/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 37 references that are in the map.
- First posted on arXiv 18 Jun 2026.

## Builds on (most cited first, 23 of 23)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Domain Randomization for Transferring Deep Neural Networks from Simulation to the Real World](https://mlsanity.com/paper/1703.06907/) (2017)
- [A Survey on Multi-Task Learning](https://mlsanity.com/paper/1707.08114/) (2017)
- [Taskonomy: Disentangling Task Transfer Learning](https://mlsanity.com/paper/1804.08328/) (2018)
- [Which Tasks Should Be Learned Together in Multi-task Learning?](https://mlsanity.com/paper/1905.07553/) (2019)
- [Contextual Markov Decision Processes](https://mlsanity.com/paper/1502.02259/) (2015)
- [Actor-Mimic: Deep Multitask and Transfer Reinforcement Learning](https://mlsanity.com/paper/1511.06342/) (2015)
- [A Survey of Zero-shot Generalisation in Deep Reinforcement Learning](https://mlsanity.com/paper/2111.09794/) (2021)
- [Scalable methods for computing state similarity in deterministic Markov Decision Processes](https://mlsanity.com/paper/1911.09291/) (2019)
- [Contrastive Behavioral Similarity Embeddings for Generalization in Reinforcement Learning](https://mlsanity.com/paper/2101.05265/) (2021)
- [Markov Decision Processes with Continuous Side Information](https://mlsanity.com/paper/1711.05726/) (2017)
- [Multi-Task Reinforcement Learning with Mixture of Orthogonal Experts](https://mlsanity.com/paper/2311.11385/) (2023)
- [Contextualize Me -- The Case for Context in Reinforcement Learning](https://mlsanity.com/paper/2202.04500/) (2022)
- [When Is Generalizable Reinforcement Learning Tractable?](https://mlsanity.com/paper/2101.00300/) (2021)
- [Know When to Explore: Difficulty-Aware Certainty as a Guide for LLM Reinforcement Learning](https://mlsanity.com/paper/2509.00125/) (2025)
- [Statistical Context Detection for Deep Lifelong Reinforcement Learning](https://mlsanity.com/paper/2405.19047/) (2024)
- [Model-Based Transfer Learning for Contextual Reinforcement Learning](https://mlsanity.com/paper/2408.04498/) (2024)
- [Temporal Transfer Learning for Traffic Optimization with Coarse-grained Advisory Autonomy](https://mlsanity.com/paper/2312.09436/) (2023)
- [Synergistic Scheduling of Learning and Allocation of Tasks in Human-Robot Teams](https://mlsanity.com/paper/2203.07478/) (2022)
- [Provable Zero-Shot Generalization in Offline Reinforcement Learning](https://mlsanity.com/paper/2503.07988/) (2025)
- [Pessimism Principle Can Be Effective: Towards a Framework for Zero-Shot Transfer Reinforcement Learning](https://mlsanity.com/paper/2505.18447/) (2025)
- [Suboptimal coverings for continuous spaces of control tasks](https://mlsanity.com/paper/2104.11865/) (2021)

## Abstract (arXiv)

Policies must operate across diverse conditions, yet a single policy is often conservative while fully adaptive schemes can be complex. We study zero-shot generalization in contextual dynamical systems and introduce a performance-centric, directional task dissimilarity--the signed divergence--that upper bounds the generalization gap from a source context to a target context. The signed divergence induces varepsilon-tolerance sets that certify when a source policy class generalizes, and it yields a concrete notion of task-space complexity: the minimum number of source contexts needed so that every target context incurs at most varepsilon generalization gap. Under a mild local smoothness assumption on performance, the induced tolerance sets admit certified inner/outer balls and instance-dependent volume bounds on task-space complexity. In the finite-oracle setting, source selection reduces to set cover; a greedy strategy inherits the standard H(n) approximation guarantee. Using a Mass-Spring-Damper system with linear-quadratic regulator (LQR) controllers and a nonlinear CartPole system with deep reinforcement learning controllers, we show that greedy selection achieves the same varepsilon-coverage with fewer policies than uniform or random baselines. Our approach delivers a performance-based task similarity measure and practical certificates for building generalizable control with simple policies.