Gradient-based methods for optimal sequential decision-making in high-dimension
File(s)
Author(s)
Johnson, Emmeran
Type
Thesis
Abstract
Sequential decision-making encompasses fundamental problems in statistics, optimisation, and reinforcement learning where a learner repeatedly selects actions and receives feedback to improve future decisions. The success of modern large-scale instances of these problems stems largely from gradient-based methods applied in high-dimensional settings, yet the theoretical understanding of these approaches remains limited. This thesis explores gradient-based approaches for high-dimensional sequential decision-making problems across three complementary directions.
First, we establish fundamental separations between low and high dimensional problems, showing that high dimensional problems are intrinsically harder and require different methods. We focus here on online convex optimisation and reinforcement learning.
Second, we show that prohibitively high dimensionality does not always preclude strong guarantees in stochastic shortest path problems. When additional low-dimensional structure, such as sparsity is present, gradient-based methods can be designed to exploit it optimally, replacing dependence on the ambient dimension with dependence on a smaller effective dimension. Third, we analyse gradient-based reinforcement learning algorithms in simple yet revealing settings. We identify sharp thresholds for the regret of policy gradient methods for bandits and establish optimal, dimension-independent convergence rates for exact policy mirror descent in discounted Markov decision processes.
Across these settings, the thesis provides upper and lower bounds that characterise the limits of performance. Collectively, these results clarify the interplay between dimensionality and gradient-based optimisation, advancing the theoretical foundations of modern sequential decision-making algorithms.
First, we establish fundamental separations between low and high dimensional problems, showing that high dimensional problems are intrinsically harder and require different methods. We focus here on online convex optimisation and reinforcement learning.
Second, we show that prohibitively high dimensionality does not always preclude strong guarantees in stochastic shortest path problems. When additional low-dimensional structure, such as sparsity is present, gradient-based methods can be designed to exploit it optimally, replacing dependence on the ambient dimension with dependence on a smaller effective dimension. Third, we analyse gradient-based reinforcement learning algorithms in simple yet revealing settings. We identify sharp thresholds for the regret of policy gradient methods for bandits and establish optimal, dimension-independent convergence rates for exact policy mirror descent in discounted Markov decision processes.
Across these settings, the thesis provides upper and lower bounds that characterise the limits of performance. Collectively, these results clarify the interplay between dimensionality and gradient-based optimisation, advancing the theoretical foundations of modern sequential decision-making algorithms.
Version
Open Access
Date Issued
2026-02-09
Date Awarded
2026-06-01
Copyright Statement
Attribution-NonCommercial 4.0 International Licence (CC BY-NC)
License URL
Advisor
Pike-Burke, Ciara
Rebeschini, Patrick
Grant Number
EP/S023151/1
Publisher Department
Department of Mathematics
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)