FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs

Alekh Agarwal, Sham M. Kakade, Akshay Krishnamurthy, Wen Sun

In modern reinforcement learning (RL), agents frequently grapple with high-dimensional inputs like raw pixels. To overcome this "curse of dimensionality," researchers typically assume the environment can be compressed into a low-dimensional feature space. However, learning these features presents a classic "chicken-and-egg" problem: acquiring a good representation requires diverse data from the environment, but exploring the environment effectively to gather that data requires a good representation.

This paper introduces FLAMBE (Feature Learning And Model-Based Exploration), a theoretical framework and algorithm that tackles simultaneous representation learning and exploration in Low-Rank MDPs.

Moving Beyond Block MDPs

Historically, theoretical work on representation learning in RL has relied heavily on the "Block MDP" structure. In a Block MDP, states are partitioned into discrete, non-overlapping latent clusters. While mathematically convenient, this is a highly restrictive assumption that rarely maps to complex, real-world environments.

The authors prove that Low-Rank MDPs are significantly more expressive than Block MDPs. Low-Rank MDPs assume the transition dynamics can be factored into a matrix product of unknown features, allowing for "soft" features and even negative values in the underlying matrix decomposition.

Comparison of latent variable models showing how general Low-Rank MDPs encompass Block MDPs and Simplex features.

By framing the environment as a Low-Rank MDP, the authors provide a robust theoretical foundation for representation learning that generalizes prior formulations and is far more applicable to realistic scenarios.

The FLAMBE Algorithm

FLAMBE operates in a continuous, iterative loop designed to systematically uncover the environment's dynamics. Crucially, FLAMBE is reward-free. It focuses purely on "system identification"—learning the environment's dynamics so thoroughly that once a specific task (reward function) is introduced, the agent can solve it immediately using the learned features without further exploration.

The algorithm consists of three main phases:

  1. Representation Learning via MLE: The agent uses a Maximum Likelihood Estimation (MLE) oracle to learn embedding functions from its current dataset of transitions. It seeks the model that best explains the observed "next-state" distributions.
  2. Elliptical Planning: Drawing inspiration from linear bandit theory, FLAMBE employs an "Elliptical Planner." It identifies "new directions" in the learned feature space—areas where the agent's model is currently highly uncertain—and synthesizes a policy to reach those areas.
  3. Data Collection: The agent executes these exploratory policies in the environment, collects new transition data, and appends it to its dataset to refine the MLE model in the subsequent iteration.

Key Theoretical Results

As a theoretical paper, the authors focus on provable complexity bounds rather than empirical benchmarks (like Atari or MuJoCo). A major milestone of this work is proving that FLAMBE learns a "uniformly accurate" model of the environment using a total number of trajectories that is polynomial in the embedding dimension ($d$), the number of actions ($K$), and the horizon ($H$).

Comparison of FLAMBE's sample complexity and computational efficiency against prior algorithms.
  • Sample Complexity: For a general low-rank MDP, the sample complexity is roughly $\tilde{O}\left(\frac{H^{22}K^9d^7}{\epsilon^{10}}\right)$. If the environment can be factored using "simplex features" (where features are probability distributions), this bound improves significantly to $\tilde{O}\left(\frac{H^{11}K^5d_{LV}^5}{\epsilon^3}\right)$.
  • Eliminating "Reachability": Previous representation learning algorithms often required a strict "reachability" assumption—dictating that every latent state must be reachable with some minimum probability. FLAMBE successfully eliminates this requirement, proving that a globally useful model can still be learned even if some parts of the state space are exceptionally difficult to reach.

Limitations and Future Work

While proving polynomial sample complexity is a significant theoretical achievement, the high exponents (e.g., $H^{22}$, $\epsilon^{-10}$) indicate that FLAMBE is currently a theoretical blueprint rather than a practical algorithm ready for immediate deployment.

Furthermore, the theory relies on a "realizability" assumption, meaning it assumes the true environment's features exist within the function classes the agent is searching through. Future research could explore "agnostic" settings where the model class is slightly mismatched with reality. Finally, because FLAMBE is a model-based approach, developing model-free extensions of this representation learning framework remains a promising next step for the field.

Summary updated

Abstract

In order to deal with the curse of dimensionality in reinforcement learning (RL), it is common practice to make parametric assumptions where values or policies are functions of some low dimensional feature space. This work focuses on the representation learning question: how can we learn such features? Under the assumption that the underlying (unknown) dynamics correspond to a low rank transition matrix, we show how the representation learning question is related to a particular non-linear matrix decomposition problem. Structurally, we make precise connections between these low rank MDPs and latent variable models, showing how they significantly generalize prior formulations, such as block MDPs, for representation learning in RL. Algorithmically, we develop FLAMBE, which engages in exploration and representation learning for provably efficient RL in low rank transition models. On a technical level, our analysis eliminates reachability assumptions that appear in prior results on the simpler block MDP model and may be of independent interest.
BibTeX
@inproceedings{agarwal2020flambe,
  author = {Alekh Agarwal and Sham M. Kakade and Akshay Krishnamurthy and Wen Sun},
  title = {{FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=33bpIhlbLx},
}
Figure