Abstract
Domain adaptation in imitation learning represents an essential step towards improving generalizability. However, even in the restricted setting of third-person imitation where transfer is between isomorphic Markov Decision Processes, there are no strong guarantees on the performance of transferred policies. We present problem-dependent, statistical learning guarantees for third-person imitation from observation in an offline setting, and a lower bound on performance in the online setting.
Introduction
Standard imitation learning typically assumes that the agent and the expert operate within the same environment. However, real-world applications often require "third-person" imitation, where an agent (e.g., a robot) must learn by observing an expert (e.g., a human) in a different but structurally related environment. This paper addresses the challenge of imitation between isomorphic Markov Decision Processes (MDPs)—environments that share identical underlying dynamics but differ in state representations or labels.
The primary hurdle in this setting is alignment: identifying the bijective mapping between the source domain (expert) and the target domain (agent) without access to the expert's actions, relying solely on state observations.
Methodology: Permuted Policy Learning
The authors introduce Algorithm 1: Permuted Policy Learning, which leverages spectral analysis to solve the alignment problem through the following steps:
- Markov Chain Alignment: Expert trajectories are treated as a Markov chain. The algorithm attempts to match the expert's transition matrix with the target environment's dynamics.
- Spectral Matching: By applying Singular Value Decomposition (SVD) to the transition matrices, the algorithm extracts unique "fingerprints" for each state. This is effective in "friendly" environments where dynamics are sufficiently asymmetric.
- Linear Assignment: The Hungarian algorithm is used to pair states between domains based on these spectral features, effectively solving the permutation problem.
- Robustness: A thresholding mechanism ensures alignment is only attempted for frequently visited states (high occupancy), mitigating noise from rare transitions.
Key Insights
A significant finding is that actions are not strictly necessary for imitation if the environment's physics are known; the sequence of states alone can be sufficient to recover the underlying mapping. The paper also formalizes the concept of "friendliness"—the degree of asymmetry required to distinguish states based on their dynamic signatures.
Furthermore, the study reveals a surprising gap between offline and online learning. In the offline setting, the expert's specific trajectory helps break environmental symmetries, making imitation more efficient. Conversely, in the online setting, an agent without expert guidance can be misled by near-symmetries, leading to an exponential increase in sample complexity.
Results and Empirical Validation
The theoretical analysis provides an upper bound for offline imitation that depends only logarithmically on the number of states $|S|$, suggesting strong scalability. In contrast, a lower bound (Theorem 5.1) proves that online imitation is fundamentally difficult in symmetric MDPs, requiring significantly more samples.
Empirical tests on Garnet MDPs and Planted MDPs (specifically constructed to be "friendly") validate these findings. As shown in the table below, the algorithm achieves near-zero imitation loss on Planted MDPs as the sample size $m$ increases.
Conclusion
This work provides the first provable guarantees for third-person imitation. While it currently assumes strict isomorphism and faces computational bottlenecks in very large state spaces ($O(|S|^3)$), it lays the groundwork for future research into more complex, non-isomorphic domain adaptations and the development of robust similarity measures between MDPs.
Summary updated