Structure and representation in statistical reinforcement learning

To what extent can advances in data-driven prediction be leveraged to improve data-driven decision-making? Reinforcement learning (RL) has been a promising approach for tackling automated sequential decision-making tasks, and in recent years has been instrumental for success in numerous impressive applications ranging from game-playing to recommendation systems to inventory management to the training of large generative models. These advances are largely powered by the merging of RL with modern function approximators (notably, neural networks). This thesis contributes to the statistical and algorithmic foundations of this framework. Our aim is to develop algorithms which leverage function approximation for scalability to large, complex sequential decision-making tasks. We seek methods with statistical complexities analogous to those obtained in simpler prediction tasks and algorithmically reduce to well-known primitives such as empirical risk minimization. Achieving this goal requires structural assumptions about the environment and/or representational assumptions about the function class. We investigate the nature of these assumptions in three parts. The first part of this thesis tackles the question of efficient RL with access to a simulator of the environment and linear features that satisfy only weak representational assumptions -- namely, which are only assumed to capture the optimal value function. In a series of three chapters, we establish that: 1) in general, sample-efficient RL is not possible under this minimal assumption, but that sample-efficiency is possible when 2) the action space is sufficiently small, or 3) a small amount of expert advice is available. The second part of this thesis examines the interaction between RL and function class misspecification. We demonstrate that, in RL, the error incurred by misspecification can be amplified due to the challenges of distribution shift and credit assignment. We study the optimal approximation factors incurred and develop algorithms which -- when possible -- mitigate this amplification. The third part of this thesis studies structural conditions which permit efficient online RL under general (possibly nonlinear) function approximation. We first leverage intimate connections between offline RL and online RL to derive algorithms that are statistically and computationally efficient under a general structural condition known as coverability. We then study the representation learning problem in settings where agents must make decisions from high-dimensional observations (such as images or sensor readings) that mask simpler underlying latent dynamics, with the goal of reducing problems to their latent complexity.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Amortila, Philip

Contributors dc:contributor

• Jiang, Nan
• Banerjee, Arindam
• Raginsky, Maxim
• Szepesvári, Csaba

• Artificial Intelligence
• Machine Learning
• Reinforcement Learning
• Statistics

Statement dc:rights

• Copyright 2025 Philip Amortila

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/129914

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F129914