# Regret Minimization with Performative Feedback

arXiv: https://arxiv.org/abs/2202.00628 · HTML: https://mlsanity.com/paper/2202.00628/

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 44 references that are in the map.
- First posted on arXiv 1 Feb 2022.

## Builds on (most cited first, 22 of 22)

- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [Parseval Networks: Improving Robustness to Adversarial Examples](https://mlsanity.com/paper/1704.08847/) (2017)
- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation](https://mlsanity.com/paper/1705.08475/) (2017)
- [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017)
- [Outside the Echo Chamber: Optimizing the Performative Risk](https://mlsanity.com/paper/2102.08570/) (2021)
- [Stochastic Optimization for Performative Prediction](https://mlsanity.com/paper/2006.06887/) (2020)
- [Performative Prediction in a Stateful World](https://mlsanity.com/paper/2011.03885/) (2020)
- [How to Learn when Data Reacts to Your Model: Performative Gradient Descent](https://mlsanity.com/paper/2102.07698/) (2021)
- [Stochastic optimization with decision-dependent distributions](https://mlsanity.com/paper/2011.11173/) (2020)
- [Conservative Bandits](https://mlsanity.com/paper/1602.04282/) (2016)
- [Conservative Contextual Linear Bandits](https://mlsanity.com/paper/1611.06426/) (2016)
- [Who Leads and Who Follows in Strategic Classification?](https://mlsanity.com/paper/2106.12529/) (2021)
- [Safe Exploration for Interactive Machine Learning](https://mlsanity.com/paper/1910.13726/) (2019)
- [Alternative Microfoundations for Strategic Classification](https://mlsanity.com/paper/2106.12705/) (2021)
- [State Dependent Performative Prediction with Stochastic Approximation](https://mlsanity.com/paper/2110.00800/) (2021)
- [Online Learning with Feedback Graphs Without the Graphs](https://mlsanity.com/paper/1605.07018/) (2016)
- [Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization](https://mlsanity.com/paper/2106.09082/) (2021)
- [Online Learning with Gaussian Payoffs and Side Observations](https://mlsanity.com/paper/1510.08108/) (2015)
- [Approximate Regions of Attraction in Learning with Decision-Dependent Distributions](https://mlsanity.com/paper/2107.00055/) (2021)
- [Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning](https://mlsanity.com/paper/2006.12367/) (2020)

## Built on by (most cited first, 30 of 40)

- [Performative Prediction: Past and Future](https://mlsanity.com/paper/2310.16608/) (2023)
- [Performative Power](https://mlsanity.com/paper/2203.17232/) (2022)
- [Anticipating Performativity by Predicting from Predictions](https://mlsanity.com/paper/2208.07331/) (2022)
- [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022)
- [Performative Prediction with Neural Networks](https://mlsanity.com/paper/2304.06879/) (2023)
- [Making Decisions under Outcome Performativity](https://mlsanity.com/paper/2210.01745/) (2022)
- [Plug-in Performative Optimization](https://mlsanity.com/paper/2305.18728/) (2023)
- [Human Expertise in Algorithmic Prediction](https://mlsanity.com/paper/2402.00793/) (2024)
- [Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimality](https://mlsanity.com/paper/2207.04173/) (2022)
- [Performative Prediction with Bandit Feedback: Learning through Reparameterization](https://mlsanity.com/paper/2305.01094/) (2023)
- [Zero-Regret Performative Prediction Under Inequality Constraints](https://mlsanity.com/paper/2309.12618/) (2023)
- [Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instruments](https://mlsanity.com/paper/2208.11040/) (2022)
- [Diversified Recommendations for Agents with Adaptive Preferences](https://mlsanity.com/paper/2210.07773/) (2022)
- [Incentivizing honest performative predictions with proper scoring rules](https://mlsanity.com/paper/2305.17601/) (2023)
- [Online Learning in a Creator Economy](https://mlsanity.com/paper/2305.11381/) (2023)
- [Performative Validity of Recourse Explanations](https://mlsanity.com/paper/2506.15366/) (2025)
- [Online Convex Optimization with Unbounded Memory](https://mlsanity.com/paper/2210.09903/) (2022)
- [Decision-Dependent Stochastic Optimization: The Role of Distribution Dynamics](https://mlsanity.com/paper/2503.07324/) (2025)
- [Optimizing the Performative Risk under Weak Convexity Assumptions](https://mlsanity.com/paper/2209.00771/) (2022)
- [Independent Learning in Performative Markov Potential Games](https://mlsanity.com/paper/2504.20593/) (2025)
- [The Limitations of Model Retraining in the Face of Performativity](https://mlsanity.com/paper/2408.08499/) (2024)
- [Tight Lower Bounds and Improved Convergence in Performative Prediction](https://mlsanity.com/paper/2412.03671/) (2024)
- [The Stability of Online Algorithms in Performative Prediction](https://mlsanity.com/paper/2602.24207/) (2026)
- [Integrating Expert Judgment and Algorithmic Decision Making: An Indistinguishability Framework](https://mlsanity.com/paper/2410.08783/) (2024)
- [Practical Performative Policy Learning with Strategic Agents](https://mlsanity.com/paper/2412.01344/) (2024)
- [On the Impact of Performative Risk Minimization for Binary Random Variables](https://mlsanity.com/paper/2502.02331/) (2025)
- [Parameter-Free Algorithms for Performative Regret Minimization under Decision-Dependent Distributions](https://mlsanity.com/paper/2402.15188/) (2024)
- [Dissecting Performative Prediction: A Comprehensive Survey](https://mlsanity.com/paper/2602.10176/) (2026)
- [Partially Performative Prediction](https://mlsanity.com/paper/2606.07890/) (2026)
- [On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimization](https://mlsanity.com/paper/2401.12508/) (2024)

## Abstract (arXiv)

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.