Timezone: »

 
Spotlight
Regret Minimization with Performative Feedback
Meena Jagadeesan · Tijana Zrnic · Celestine Mendler-Dünner

Thu Jul 21 01:00 PM -- 01:05 PM (PDT) @ Ballroom 3 & 4
in T: Online Learning and Bandits »

In performative prediction, the deployment of a predictive model triggers a shift in the data distribution. As these shifts are typically unknown ahead of time, the learner needs to deploy a model to get feedback about the distribution it induces. We study the problem of finding near-optimal models under performativity while maintaining low regret. On the surface, this problem might seem equivalent to a bandit problem. However, it exhibits a fundamentally richer feedback structure that we refer to as performative feedback: after every deployment, the learner receives samples from the shifted distribution rather than bandit feedback about the reward. Our main contribution is regret bounds that scale only with the complexity of the distribution shifts and not that of the reward function. The key algorithmic idea is careful exploration of the distribution shifts that informs a novel construction of confidence bounds on the risk of unexplored models. The construction only relies on smoothness of the shifts and does not assume convexity. More broadly, our work establishes a conceptual approach for leveraging tools from the bandits literature for the purpose of regret minimization with performative feedback.

Keywords: OPT: Global Optimization · T: Game Theory · T: Online Learning and Bandits · T: Social Aspects · MISC: Online Learning, Active Learning and Bandits

Author Information

Meena Jagadeesan (UC Berkeley)
Tijana Zrnic (University of California, Berkeley)
Celestine Mendler-Dünner (Max Planck Institute for Intelligent Systems)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors