FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs

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

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 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.

Introduction

Reinforcement Learning (RL) in real-world environments often faces the "curse of dimensionality," where massive state spaces make traditional tabular methods intractable. To address this, practitioners typically rely on low-dimensional features to compress environmental complexity. However, a fundamental "chicken-and-egg" problem persists: efficient exploration requires good features to distinguish novel states, yet learning these features requires a diverse dataset obtained through exploration.

This paper introduces FLAMBE (Feature Learning And Model-Based Exploration), the first algorithm to provably learn both representations and environment dynamics in Low-Rank Markov Decision Processes (MDPs) with both statistical and computational efficiency.

Structural Complexity: Low-Rank MDPs

Most theoretical RL research assumes either a small state space or pre-provided features. FLAMBE instead operates on Low-Rank MDPs, where the transition probability $P(x' | x, a)$ factors into an inner product of two low-dimensional functions: $\langle \phi(x, a), \mu(x') \rangle$. This framework is significantly more expressive than "Block MDPs," where states are simply clustered into discrete latent states.

Structural hierarchy of MDP models, showing how Low-Rank MDPs generalize Block MDPs from discrete latent states to general features.

By treating representation learning as a non-linear matrix decomposition problem, the authors show that Low-Rank MDPs can model complex, continuous-feeling environments that previous frameworks could not capture.

The FLAMBE Algorithm

FLAMBE solves the circular dependency between exploration and representation learning through an iterative three-step process:

  1. Model Learning (MLE): The agent uses a Maximum Likelihood Estimation (MLE) oracle to find the best transition model (features $\phi$ and $\mu$) within a given function class (e.g., a neural network architecture) based on all collected data.
  2. Exploration Planning: Using the current model, FLAMBE employs an Elliptical Planner. Inspired by linear bandits, this planner identifies "novel" directions in the learned feature space that have not been sufficiently explored.
  3. Data Collection: The agent executes the resulting exploratory policy in the real environment, feeding new transitions back into the MLE step.

FLAMBE is oracle-efficient, meaning it reduces the complex RL problem to standard optimization tasks like MLE training, which are well-supported by modern deep learning tools.

Key Results and Comparison

The primary contribution of this work is proving that Low-Rank MDPs are fundamentally solvable in polynomial time. As shown in the comparison below, FLAMBE is the first algorithm to achieve both "Low Rank MDP" generality and "Oracle efficiency."

Comparison of FLAMBE with existing algorithms. FLAMBE is the first to provide an oracle-efficient solution for the general Low-Rank MDP setting.

The authors provide a rigorous proof (Theorem 2) that the sample complexity scales polynomially with the horizon ($H$), action space ($K$), feature dimension ($d$), and accuracy ($\epsilon$). Specifically, FLAMBE achieves "system identification," learning a uniformly accurate model of the environment that allows for "reward-free" exploration—once the model is learned, any reward function can be optimized without further data collection.

Limitations and Future Directions

While FLAMBE establishes a theoretical breakthrough, the current sample complexity bounds (e.g., $H^{22}$) are high, suggesting that the "vanilla" version may be slow for immediate practical application. Future research is needed to tighten these bounds and relax the assumption that MLE oracles always reach global optima. Additionally, extending these representation learning principles to model-free RL remains a significant open challenge.

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 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.
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