  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.
