Formalizing Task-Space Complexity for Zero-Shot Generalization
Provides a formal framework and practical certificates for building generalizable control policies with minimal source contexts, benefiting reinforcement learning and control applications.
The paper introduces a performance-based task dissimilarity measure, the signed divergence, that bounds the zero-shot generalization gap in contextual dynamical systems. Using this measure, they define task-space complexity as the minimum number of source contexts needed to cover all targets within a given gap, and show that greedy source selection achieves better coverage with fewer policies than baselines on LQR and CartPole systems.
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.