# State Dependent Performative Prediction with Stochastic Approximation

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Oct 2021.

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

- [Multiplayer Performative Prediction: Learning in Decision-Dependent Games](https://mlsanity.com/paper/2201.03398/) (2022)
- [Performative Power](https://mlsanity.com/paper/2203.17232/) (2022)
- [Regret Minimization with Performative Feedback](https://mlsanity.com/paper/2202.00628/) (2022)
- [Performative Prediction with Neural Networks](https://mlsanity.com/paper/2304.06879/) (2023)
- [How to Learn when Data Gradually Reacts to Your Model](https://mlsanity.com/paper/2112.07042/) (2021)
- [Plug-in Performative Optimization](https://mlsanity.com/paper/2305.18728/) (2023)
- [Performative Federated Learning: A Solution to Model-Dependent and Heterogeneous Distribution Shifts](https://mlsanity.com/paper/2305.05090/) (2023)
- [Performative Reinforcement Learning in Gradually Shifting Environments](https://mlsanity.com/paper/2402.09838/) (2024)
- [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)
- [Performative Reinforcement Learning with Linear Markov Decision Process](https://mlsanity.com/paper/2411.05234/) (2024)
- [Performative Validity of Recourse Explanations](https://mlsanity.com/paper/2506.15366/) (2025)
- [Online covariance estimation for stochastic gradient descent under Markovian sampling](https://mlsanity.com/paper/2308.01481/) (2023)
- [Distributionally Robust Performative Prediction](https://mlsanity.com/paper/2412.04346/) (2024)
- [Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data](https://mlsanity.com/paper/2206.11346/) (2022)
- [A Market for Accuracy: Classification under Competition](https://mlsanity.com/paper/2502.18052/) (2025)
- [Decision-Dependent Stochastic Optimization: The Role of Distribution Dynamics](https://mlsanity.com/paper/2503.07324/) (2025)
- [On Corruption-Robustness in Performative Reinforcement Learning](https://mlsanity.com/paper/2505.05609/) (2025)
- [Performative Policy Gradient: Optimality in Performative Reinforcement Learning](https://mlsanity.com/paper/2512.20576/) (2025)
- [Optimizing the Performative Risk under Weak Convexity Assumptions](https://mlsanity.com/paper/2209.00771/) (2022)
- [Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation](https://mlsanity.com/paper/2402.02857/) (2024)
- [Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies](https://mlsanity.com/paper/2404.10995/) (2024)
- [Independent Learning in Performative Markov Potential Games](https://mlsanity.com/paper/2504.20593/) (2025)
- [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)
- [Identifying Predictions That Influence the Future: Detecting Performative Concept Drift in Data Streams](https://mlsanity.com/paper/2412.10545/) (2024)
- [Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks](https://mlsanity.com/paper/2401.09665/) (2024)
- [Parameter-Free Algorithms for Performative Regret Minimization under Decision-Dependent Distributions](https://mlsanity.com/paper/2402.15188/) (2024)
- [Stochastic Gradient Descent with Adaptive Data](https://mlsanity.com/paper/2410.01195/) (2024)

## Abstract (arXiv)

This paper studies the performative prediction problem which optimizes a stochastic loss function with data distribution that depends on the decision variable. We consider a setting where the agent(s) provides samples adapted to the learner's and agent's previous states. The said samples are used by the learner to optimize a loss function. This closed loop algorithm is studied as a state-dependent stochastic approximation (SA) algorithm, where we show that it finds a fixed point known as the performative stable solution. Our setting models the unforgetful nature and the reliance on past experiences of agent(s). Our contributions are three-fold. First, we demonstrate that the SA algorithm can be modeled with biased stochastic gradients driven by a controlled Markov chain (MC) whose transition probability is adapted to the learner's state. Second, we present a novel finite-time performance analysis of the state-dependent SA algorithm. We show that the expected squared distance to the performative stable solution decreases as cal O(1/k), where k is the iteration number. Third, numerical experiments are conducted to verify our findings.