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.
| Identifer | oai:union.ndltd.org:columbia.edu/oai:academiccommons.columbia.edu:10.7916/j6zc-vj92 |
| Date | January 2024 |
| Creators | Brown, William |
| Source Sets | Columbia University |
| Language | English |
| Detected Language | English |
| Type | Theses |
Page generated in 0.0028 seconds