Abstract
This work investigates whether inverse models—predicting actions from state transitions—contain sufficient information to reconstruct the full forward dynamics of an environment. We demonstrate that while 1-step inverse models are generally under-determined when the number of actions is less than the number of states, 2-step models typically provide enough constraints for uniqueness. We further analyze the computational complexity of this reconstruction, proving NP-hardness in the general case while providing an efficient linear relaxation for practical scenarios.
Introduction
In reinforcement learning (RL), agents typically interact with environments through forward models: predicting the next state $s'$ given a current state $s$ and action $a$. However, "inverse models"—which infer the action $a$ that caused a transition from $s$ to $s'$—have gained popularity due to their potential for abstraction. For instance, an inverse model can ignore complex environmental dynamics (like leaves blowing in the wind) that are irrelevant to the agent's own actions.
The fundamental question addressed by Marcus Hutter and Steven Hansen is: To what extent do inverse models (combined with a known policy) determine the full dynamics of the system? If the world cannot be uniquely reconstructed from these models, agents relying solely on them may be fundamentally limited in their understanding of the environment.
The Dimensionality Gap
The authors formalize the problem by comparing the degrees of freedom in a transition matrix $M$ against the constraints provided by an inverse model $p(a|s, s')$.
A key finding is the $k < d$ problem: if an environment has fewer actions ($k$) than states ($d$), a 1-step inverse model is mathematically under-determined. In such cases, multiple distinct forward models can produce the exact same 1-step inverse observations. This confirms the intuition that inverse models provide a "compressed" view of the world, potentially losing information about the environment's full transition structure.
The Power of Multi-Step Models
While 1-step models are often insufficient, the authors show that a 2-step inverse model $p(a, a'|s, s'')$—which predicts a sequence of two actions given a start and end state—provides significantly more information. These models introduce quadratic constraints that usually "lock in" a unique forward model.
Theoretical analysis suggests that for most "natural" or random environments, the 2-step model is sufficient for uniqueness. However, the authors also identify "degenerate" cases (e.g., those involving specific cyclic groups or permutations) where even multi-step models remain ambiguous. This highlights a subtle boundary between environments that are fully identifiable and those that are not.
Computational Complexity and Algorithms
Reconstructing the forward model from inverse observations is non-trivial. The relationship between 1-step and 2-step models is quadratic, making the direct solution difficult.
- NP-Hardness: The authors prove that finding a consistent MDP from inverse models is NP-hard in the general case, using a reduction from 1-in-3SAT. This suggests that while a solution may exist and be unique, finding it can be computationally prohibitive in the worst case.
- Linear Relaxation: To address this, they propose a polynomial-time algorithm that "linearizes" the quadratic system by introducing auxiliary variables. This allows the problem to be solved using standard linear algebra techniques, making the reconstruction practical for many real-world scenarios.
Empirical Validation
The theory was tested across several environments to validate the "Random $M$" hypothesis and the algorithm's performance:
- Grid-worlds: In a "four-rooms" environment and random grids ($d=24, k=5$), the linear relaxation algorithm successfully recovered the true transition matrices ($M^+$) from inverse models.
- Augmented Half-Cheetah: By adding uncontrollable background video to a standard RL benchmark, the authors demonstrated that inverse models effectively filter out irrelevant dynamics while still capturing the core transition logic necessary for the agent.
- Robustness: Experiments showed that the reconstruction remains stable even when noise is injected into the inverse model data, with low KL-divergence between the true and recovered models across several orders of magnitude of noise.
Conclusion and Future Work
This research establishes a theoretical foundation for understanding inverse models in RL. While 1-step models are often insufficient to describe the world, 2-step models usually suffice, albeit at the cost of high computational complexity in the worst case.
Several open challenges remain:
- Scaling to Deep Learning: The current work focuses on tabular MDPs. Extending these proofs and algorithms to continuous state spaces or neural network representations is a major next step.
- Sparse Dynamics: In environments with many zero-probability transitions (the "0/0 problem"), the inference becomes significantly more complex.
- Massive State Spaces: The requirement that the number of action sequences ($k^i$) exceeds the number of states ($d$) may be difficult to satisfy in environments with extremely large state spaces.
Summary updated