Theory Lunch Seminar - Keegan Harris

— 1:00pm

Location:
In Person - Reddy Conference Room, Gates Hillman 4405

Speaker:
KEEGAN HARRIS, Ph.D. Student, Machine Learning Department, Carnegie Mellon University
https://keeganharris.github.io/

Regret Minimization in Stackelberg Games with Side Information

Algorithms for playing in Stackelberg games have been deployed in real-world domains including airport security, anti-poaching efforts, and cyber-crime prevention. However, these algorithms often fail to take into consideration the additional information available to each player (e.g. traffic patterns, weather conditions, network congestion), which may significantly affect both players’ optimal strategies. We formalize such settings as Stackelberg games with side information, in which both players observe an external context before playing. The leader commits to a (context-dependent) strategy, and the follower best-responds to both the leader’s strategy and the context. We focus on the online setting in which a sequence of followers arrive over time, and the context may change from round-to-round. 

In sharp contrast to the non-contextual version, we show that it is impossible for the leader to achieve no-regret in the full adversarial setting. Motivated by this result, we show that no-regret learning is possible in two natural relaxations: the setting in which the sequence of followers is chosen stochastically and the sequence of contexts is adversarial, and the setting in which contexts are stochastic and follower types are adversarial.   

This talk is based on the paper of the same name, to appear at NeurIPS 2024.

Event Website:
https://www.cs.cmu.edu/~theorylunch/

Add event to Google
Add event to iCal