Theses Doctoral

Learning in the Presence of Adaptive Behavior

Brown, William

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.

Files

  • thumnail for Brown_columbia_0054D_18389.pdf 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