Structure and representation in statistical reinforcement learning

Amortila, Philip

Permalink

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

Description

Title

Structure and representation in statistical reinforcement learning

Author(s)

Amortila, Philip

Issue Date

2025-07-02

Director of Research (if dissertation) or Advisor (if thesis)

Jiang, Nan

Doctoral Committee Chair(s)

Jiang, Nan

Committee Member(s)

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

Department of Study

Siebel School Comp & Data Sci

Discipline

Computer Science

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Artificial Intelligence
• Machine Learning
• Reinforcement Learning
• Statistics

Abstract

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.

Graduation Semester

2025-08

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

Copyright 2025 Philip Amortila

Owning Collections