Beyond Open Loop Algorithm Design: Learning from Decision-Dependent Data
Lillian Ratliff (University of Washington)
Calvin Lab Auditorium
Learning algorithms are increasingly being deployed in a variety of real world systems. A central tenet of present day machine learning is that when it is arduous to model a phenomenon, observations thereof are representative samples from some, perhaps unknown, static or otherwise independent distribution. In the context of systems such as civil infrastructure and online marketplaces, at least one challenge calls into question the efficacy of this tenet. Data used to either train the algorithms offline or as an input to an online decision-making algorithm may be generated by strategic data sources such as human users. Indeed, such data depends on how the algorithm impacts a user’s individual objectives or (perceived) quality of service. This leads to an interesting feedback mechanism wherein the underlying data distribution depends on the output of the algorithm. This begs the question of how learning algorithms can and should be designed taking into consideration this closed-loop interaction with the environment. In this talk, I will provide one perspective on designing and analyzing algorithms by modeling the underlying learning task in the language of game theory and control, and using tools from these domains to provide performance guarantees on the convergence of algorithms. Recent, promising results in this direction including those on modeling competition between learning algorithms in presence of strategic behavior will be highlighted. Time permitting, open questions will be posed towards the end of the talk.