Abstract
Third-person imitation learning (TPIL) addresses the challenge of an agent learning to mimic an expert operating in a different but structurally related environment. This work provides a theoretical treatment of TPIL by modeling the relationship between environments as an isomorphism between Markov Decision Processes (MDPs). We analyze two distinct observation regimes: an offline setting where expert trajectories are observed in the target domain, and an online setting where the agent interacts with the target domain. Our findings reveal a fundamental asymmetry in difficulty: offline TPIL is provably efficient using spectral alignment techniques, whereas online TPIL is susceptible to deception by environmental symmetries, leading to exponential sample complexity.
Introduction
Standard imitation learning assumes the expert and the agent operate in the exact same environment, sharing the same state and action spaces. However, real-world applications often require an agent to learn from an expert in a sensorially different domain—for instance, a robot learning from a human video where camera angles or lighting differ. This problem, known as third-person imitation, is often ill-defined in general domain adaptation contexts.
This paper restricts the problem to a more tractable setup: transferring policies between isomorphic MDPs. In this framework, the underlying transition rules are identical, but the state representations are scrambled via a hidden one-to-one mapping (a bijection). The central question is whether an agent can efficiently learn this mapping and the corresponding expert policy by observing states alone, without access to the expert's actions.
Problem Formulation
The problem is framed as transferring policies between two isomorphic MDPs, $\mathcal{M}$ and $\hat{\mathcal{M}}$. While the dynamics are structurally identical, the state spaces are related by a hidden bijection $\pi_*$. The agent's goal is to recover this mapping to enable the imitation of the expert's policy in the target domain.
Two primary observation regimes are explored:
- Offline Observation: The agent observes trajectories of the expert policy as they appear in the target domain. This provides a direct look at the expert's state distribution in the new environment.
- Online Observation: The agent actively interacts with the target domain, executing its own policies and observing the resulting state transitions to infer the underlying alignment.
Methodology: Spectral Alignment and Thresholding
The authors propose a novel algorithm for the offline setting that frames the problem as aligning the Markov chains induced by the expert's policy in both domains. The core idea relies on the concept of "friendly" matrices from graph isomorphism literature. A Markov chain is considered friendly if its rescaled transition matrix possesses distinct singular values, which mathematically guarantees a unique alignment between the two domains.
To handle the practical challenges of finite sampling and state occupancy, the paper introduces a critical thresholding technique:
- Empirical Estimation: The agent estimates the stationary distribution of states from the observed trajectories.
- State Truncation: "Low-occupancy" states—those visited rarely by the expert—are discarded. This prevents the algorithm from requiring an impractical number of samples to estimate rare transitions.
- Spectral Decomposition: A rescaled transition matrix is computed for the remaining high-occupancy states.
- Optimization: Singular Value Decomposition (SVD) combined with the Hungarian algorithm is used to find the optimal state-to-state bijection within this truncated space.
Theoretical Results
The paper establishes rigorous bounds for both the offline and online settings, highlighting a significant gap in their learnability.
Offline Upper Bound
The proposed Permuted Policy Learning algorithm is shown to be highly efficient. The authors prove that the imitation loss is bounded by $O(t|S| / (1-\gamma)^2)$, where $t$ is the occupancy threshold, $|S|$ is the number of states, and $\gamma$ is the discount factor. Most importantly, the sample complexity required to achieve this bound scales only logarithmically with the total number of states, making it feasible for large environments.
Online Lower Bound
In contrast, the online setting is proven to be fundamentally harder. By constructing a bandit-like MDP counterexample, the authors show that any online algorithm requires $\Omega(1/\epsilon^2 \log(1/\delta))$ samples to achieve low imitation loss, where $\epsilon$ represents the degree of near-symmetry in the environment. This suggests that without the expert's guidance on the correct state distribution, an agent can be easily deceived by structural symmetries.
Discussion and Conclusion
This work provides the first theoretical foundations for third-person imitation learning in isomorphic environments. A key insight is that perfect alignment of the entire state space is unnecessary; by focusing on states the expert frequently visits, agents can achieve near-optimal imitation with manageable sample complexity.
However, the assumption of strict isomorphism remains a significant limitation for real-world robotics where domains may have differing dynamics or non-bijective state mappings. Future research may involve relaxing these assumptions by incorporating observable features (like visual cues) to guide the alignment process and exploring how natural environmental asymmetries can be exploited to improve deep imitation learning algorithms.
Summary updated