2024 Theses Doctoral
Learning in the Presence of Adaptive Behavior
Algorithms for repeated (or “online”) decision-making are predominantly studied under the assumption that feedback is either statistical (determined by fixed probability distributions) or adversarial (changing over time in a potentially worst-case manner). Both of these assumptions ignore a phenomenon commonly present in repeated interactions with other agents, in which the space of our possible future outcomes is shaped in a structured and potentially predictable manner by our history of prior decisions.
In this thesis, we consider online decision problems where the feedback model is adaptive rather than purely statistical or adversarial. One such example is a repeated game played against an opponent who uses a learning algorithm of their own; here, we give a characterization of possible outcome spaces which unifies disparate equilibrium notions, and serves as a basis for designing new algorithms. We then consider the task of providing recommendations to an agent whose preferences adapt based on the recommendation history, where we explore algorithmic tradeoffs in terms of the structure of this adaptivity pattern. We conclude by offering a general framework and algorithmic toolkit for approaching adaptive problems of this form.
Subjects
Files
- Brown_columbia_0054D_18389.pdf application/pdf 1.23 MB Download File
More About This Work
- Academic Units
- Computer Science
- Thesis Advisors
- Roughgarden, Tim
- Papadimitriou, Christos H.
- Degree
- Ph.D., Columbia University
- Published Here
- June 12, 2024