Abstract
In deep reinforcement learning (RL), representational transfer—pre-training on source tasks to learn a feature map for a target task—is a widely used heuristic. However, theoretical guarantees for its success have remained elusive, particularly when tasks exhibit significant distribution shifts. This paper introduces REPTRANSFER, an algorithm that leverages generative access to source tasks to learn a shared representation. We prove that under a flexible "point-wise linear span" assumption, representational transfer can achieve sample complexity in a target task nearly identical to that of an agent with prior knowledge of the ground-truth features.
Introduction
The success of modern deep RL often hinges on the ability to transfer knowledge across tasks. A common paradigm involves training a neural network on a suite of source tasks to extract a robust representation, which is then "frozen" and utilized for a novel target task. Despite its empirical success, the theoretical underpinnings of this process are poorly understood. The primary obstacle is distribution shift: because an agent's data collection depends on its policy, different tasks naturally lead the agent to explore different regions of the state space. Existing theories often rely on restrictive assumptions, such as tasks sharing identical state distributions, which are rarely satisfied in practice. This work addresses whether transfer learning can be provably beneficial even when tasks appear superficially distinct, provided they share an underlying structural representation.
Theoretical Framework: Low-rank MDPs
The authors model the environment using Low-rank MDPs. In this framework, the transition dynamics $P(s'|s, a)$ are factored into a low-dimensional feature map $\phi(s, a)$ and a task-specific embedding $\mu(s')$. This structure implies that while the state-action space may be vast, the underlying transitions are governed by a small number of latent features.
A key innovation of this paper is the Point-wise Linear Span Assumption. Unlike previous models that assume the target task is a fixed linear combination of source tasks, this assumption allows the combination coefficients $\alpha_i(s')$ to vary with the next state $s'$. This provides a much more flexible and realistic definition of task relatedness, accommodating scenarios where different source tasks inform different aspects of the target task's dynamics.
The REPTRANSFER Algorithm
The proposed algorithm, REPTRANSFER, operates in three distinct phases:
- Pre-training: The agent explores multiple source tasks to identify "exploratory policies" that sufficiently cover the latent feature space.
- Cross-Sampling: To mitigate distribution shift, the algorithm utilizes generative access (a simulator). By "teleporting" the agent from a state reached in one task to the same state in another task, the algorithm can directly compare transition dynamics. This "cross-referencing" is critical for aligning representations across tasks.
- Deployment: A shared representation $\phi$ is learned via Maximum Likelihood Estimation (MLE) and subsequently integrated into a standard linear RL algorithm, such as LSVI-UCB, to solve the target task.
Theoretical Contributions and Comparisons
The paper's theoretical results significantly advance the state of the art by relaxing assumptions required in previous works.
As shown in the table above, this work (Theorems 3.1 and 4.2) eliminates the need for the "Generalization (assumption)" found in prior literature like Lu et al. (2021) and Cheng et al. (2022). Furthermore, Theorem 4.1 establishes a fundamental lower bound: without generative access, representational transfer is impossible under these flexible assumptions. This highlights the necessity of "cross-sampling" to resolve representational ambiguities that arise from online-only exploration.
Empirical Validation
The theory was tested using the Rich Observation Combination Lock (comblock) environment, a challenging "needle in a haystack" problem requiring strategic exploration. In a variant called Comblock-PO (Partitioned Observations), where source tasks have disjoint observation spaces, REPTRANSFER demonstrated remarkable efficiency:
- Sample Efficiency: REPTRANSFER solved the target task in approximately 8,000 episodes.
- Baseline Comparison: The state-of-the-art algorithm starting from scratch (BRIEE) required over 180,000 episodes—a 20x improvement.
- Ablation: An online-only version (O-REPTRANSFER) failed in the partitioned setting, empirically validating the theoretical necessity of generative access.
Conclusion
This research provides the first rigorous "proof of work" for representational transfer in RL under realistic conditions. By identifying generative access and cross-sampling as key enablers, the authors bridge the gap between empirical practice and theoretical understanding. Future work will focus on relaxing the requirement for generative access, perhaps by identifying specific environmental properties that allow for "online-only" alignment of representations.
Summary updated