Regret Minimization with Performative Feedback
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 only bandit feedback about the reward. Our main contribution is an algorithm that achieves regret bounds scaling only with the complexity of the distribution shifts and not that of the reward function. The algorithm only relies on smoothness of the shifts and does not assume convexity. Moreover, its final iterate is guaranteed to be near-optimal. 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. More broadly, our work establishes a conceptual approach for leveraging tools from the bandits literature for the purpose of regret minimization with performative feedback.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Parameter-Free Algorithms for Performative Regret Minimization under Decision-Dependent Distributions
This paper studies performative risk minimization, a formulation of stochastic optimization under decision-dependent distributions. We consider the general case where the performative risk can be non-convex, for which we…
Stochastic OptimizationPerformative Prediction with Bandit Feedback: Learning through Reparameterization
Performative prediction, as introduced by Perdomo et al, is a framework for studying social prediction in which the data distribution itself changes in response to the deployment of a model. Existing work in this field u…
PredictionRecommendation SystemsPerformative Prediction
When predictions support decisions they may influence the outcome they aim to predict. We call such predictions performative; the prediction influences the target. Performativity is a well-studied phenomenon in policy-ma…
PredictionThe Stability of Online Algorithms in Performative Prediction
The use of algorithmic predictions in decision-making leads to a feedback loop where the models we deploy actively influence the data distributions we see, and later use to retrain on. This dynamic was formalized by Perd…
Online Stackelberg Optimization via Nonlinear Control
In repeated interaction problems with adaptive agents, our objective often requires anticipating and optimizing over the space of possible agent responses. We show that many problems of this form can be cast as instances…