Low-Rank Structures for Reinforcement Learning

QC 20261016

Abstract

Reinforcement learning has achieved remarkable empirical success, yet scaling algorithms to high-dimensional state-action spaces remains a fundamental computational and statistical challenge. While real-world environments often possess rich, low-dimensional latent structure, establishing provable sample efficiency and robust generalization without relying on known feature representations remains an open question. This thesis investigates how exploiting low-rank structure in sequential decision making problems can address these challenges, bridging ideas from spectral matrix estimation, representation learning, and reinforcement learning.

The contributions of this thesis span three increasingly complex settings. The first investigates low-rank bandits, where latent structure in reward functions can be exploited to improve statistical efficiency. We develop refined spectral estimation techniques that move beyond traditional global error measures and establish entry-wise and singular subspace recovery guarantees. These results enable efficient algorithms for matrix bandits and contextual low-rank bandits, achieving improved guarantees for policy evaluation, best policy identification, and regret minimization.

The second investigates how low-rank structure can be exploited in reinforcement learning, where the learned representations must ultimately support decision making. We study low-rank transition models, value functions, and successor measures, showing that the estimation guarantees required for control are substantially stronger than those typically considered in matrix estimation. By developing spectral methods with fine-grained error control, we establish sample-efficient algorithms for reward-free model-based reinforcement learning and model-free learning with low-rank value functions. Furthermore, we study when low-rank successor representations emerge naturally from the environment dynamics and identify conditions under which shifted successor measures admit accurate low-rank approximations.

The third investigates how low-rank successor representations can enable transfer and generalization across tasks. We introduce switching successor measures, a framework that extends successor representations to hierarchical decision making by allowing policies to temporarily switch before returning to the original behavior. Based on this framework, we develop a hierarchical zero-shot reinforcement learning algorithm that derives both high-level planning and low-level control from a shared successor representation, enabling generalization to previously unseen reward functions.

Together, the contributions of this thesis demonstrate how spectral geometry and structural assumptions can mitigate the statistical and computational challenges of sequential decision making. By connecting low-rank estimation theory with reinforcement learning representations, this work provides both rigorous guarantees and new perspectives on how intelligent agents can learn compact, reusable abstractions from complex environments.

Link to DiVA