Delays, cooperation and pairwise comparisons in sequential decision-making processes
File(s)
Author(s)
Howson, Benjamin
Type
Thesis
Abstract
This thesis presents novel algorithms for sequential decision-making in uncertain environments, focussing on the challenges introduced by complex feedback structures. Specifically, we study scenarios that frequently arise in real-world applications, including delayed feedback, cooperation in multi-agent systems, and learning from pairwise comparisons.
First, we study delayed feedback. Here, the decision-maker sequentially selects actions, but the corresponding feedback arrives later. For generalised linear bandits, we propose an algorithm and prove an upper bound on its regret. This guarantee shows that the delays cause a small additive penalty on top of what is possible with immediate feedback, substantially improving upon existing results. Subsequently, we extend the study of delayed feedback to episodic reinforcement learning and propose two approaches to handle the delays. For each approach, we provide regret bounds for numerous immediate feedback algorithms and prove that the price for delays is an additive penalty.
Second, we study problem settings where numerous cooperative decision-makers interact with the environment. For these problems, we propose a black-box algorithm that takes any single-agent algorithm as input and turns it into a cooperative multi-agent algorithm. Additionally, we prove that the black-box algorithm transfers the theoretical guarantees of any single-agent algorithm to the multi-agent setting. These guarantees are comparable to, or better than, existing works.
Finally, we study learning from pairwise comparisons, where the decision-maker selects two actions and receives the preferred action as their feedback. For this setting, we propose an algorithm that collects batches of preferences and uses this information to learn a policy that generates preferable actions. We prove that the cumulative sub-optimality of our algorithm grows sub-linearly without requiring strong assumptions on the preference structure.
Overall, this thesis provides practical algorithms with theoretical guarantees. These results make a step towards bridging the gap between idealised models for sequential decision-making and real-world challenges.
First, we study delayed feedback. Here, the decision-maker sequentially selects actions, but the corresponding feedback arrives later. For generalised linear bandits, we propose an algorithm and prove an upper bound on its regret. This guarantee shows that the delays cause a small additive penalty on top of what is possible with immediate feedback, substantially improving upon existing results. Subsequently, we extend the study of delayed feedback to episodic reinforcement learning and propose two approaches to handle the delays. For each approach, we provide regret bounds for numerous immediate feedback algorithms and prove that the price for delays is an additive penalty.
Second, we study problem settings where numerous cooperative decision-makers interact with the environment. For these problems, we propose a black-box algorithm that takes any single-agent algorithm as input and turns it into a cooperative multi-agent algorithm. Additionally, we prove that the black-box algorithm transfers the theoretical guarantees of any single-agent algorithm to the multi-agent setting. These guarantees are comparable to, or better than, existing works.
Finally, we study learning from pairwise comparisons, where the decision-maker selects two actions and receives the preferred action as their feedback. For this setting, we propose an algorithm that collects batches of preferences and uses this information to learn a policy that generates preferable actions. We prove that the cumulative sub-optimality of our algorithm grows sub-linearly without requiring strong assumptions on the preference structure.
Overall, this thesis provides practical algorithms with theoretical guarantees. These results make a step towards bridging the gap between idealised models for sequential decision-making and real-world challenges.
Version
Open Access
Date Issued
2025-04-04
Date Awarded
01/08/2025
License URL
Advisor
Pike-Burke, Ciara
Filippi, Sarah
Sponsor
Engineering and Physical Sciences Research Council
Grant Number
EP/S023151/1
Publisher Department
Department of Mathematics
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)