Abstract
This paper investigates the challenge of expected loss minimization when the underlying data distribution is influenced by the decision-maker's actions and evolves dynamically over time. Unlike traditional models that assume instantaneous distribution shifts, this work models the environment as a geometrically decaying process. We introduce novel epoch-based algorithms for both first-order (gradient-based) and zeroth-order (loss-only) settings. By holding decisions constant over specific intervals, these algorithms allow the environment to equilibrate, achieving iteration complexities that match standard stochastic gradient methods. The framework is validated using a semi-synthetic study of the SFpark dynamic pricing pilot, demonstrating improved target occupancy and reduced parking rates.
Introduction
In many modern machine learning applications—such as credit scoring, insurance pricing, and predictive policing—the deployment of a model influences the behavior of the subjects it aims to predict. This phenomenon, known as performative prediction, breaks the fundamental assumption of supervised learning: that training and testing distributions are static and independent of the model.
While existing literature often assumes that the environment reacts instantaneously to new decisions, real-world systems typically possess "memory." For instance, if a city adjusts parking prices, it takes time for commuters to change their habits. This paper addresses the problem of finding performatively optimal decisions in dynamic environments where the distribution evolves gradually toward a new steady state following a decision change.
Problem Formulation: Dynamic Performative Environments
The authors model the environment's evolution as a geometrically decaying process. At any time $t+1$, the data distribution is a weighted average of the current distribution and the "target" distribution induced by the decision $x$. This captures the lag or inertia inherent in human and physical systems.
Mathematically, the goal is to find a decision $x$ that minimizes the performative risk: $$PR(x) = \mathbb{E}_{z \sim \mathcal{D}(x)} [\ell(x, z)]$$ where $\mathcal{D}(x)$ is the steady-state distribution resulting from a long-term deployment of decision $x$. The challenge lies in the fact that the decision-maker never observes $\mathcal{D}(x)$ directly, but rather a sequence of distributions $\mathcal{D}_t$ that are converging toward it.
The Epoch-Based Framework
To navigate this dynamic landscape, the paper proposes a "Slow Down to Go Fast" strategy. Rather than updating the model at every time step—which can lead the system toward sub-optimal stable points—the authors introduce an Epoch-Based framework:
- Query-Mix Phase: The decision-maker deploys a fixed decision $x$ for a duration $n$ (the epoch length). This allows the lagging environment to "mix" and approach the steady-state distribution $\mathcal{D}(x)$.
- Update Phase: Once the environment has sufficiently stabilized, the decision-maker queries an oracle (either a gradient or a loss value) and updates the decision using a stochastic step.
Algorithms
- Algorithm 1 (Zeroth-Order): Designed for "bandit feedback" settings where only the loss value is observable. It utilizes a one-point gradient estimate by sampling from a unit sphere.
- Algorithm 2 (First-Order): Designed for settings where a first-order gradient oracle is available, providing more direct guidance toward the optimum.
The core technical contribution is proving that the bias introduced by the environment's memory can be bounded and effectively managed by choosing an appropriate epoch length $n$ relative to the decay rate of the environment.
Key Results and Insights
Theoretical Convergence
Despite the added complexity of a shifting, lagging environment, the authors demonstrate that their algorithms match the iteration complexity of standard stochastic gradient methods up to logarithmic factors:
- First-Order Complexity: $\tilde{O}(1/\epsilon)$
- Zeroth-Order Complexity: $\tilde{O}(d^2/\epsilon^2)$
Empirical Validation: SFpark
The framework was tested using data from the SFpark dynamic pricing pilot in San Francisco. The study simulated how parking occupancy reacts to price changes over time. The results showed that the proposed epoch-based algorithms reached the target occupancy (70%) more effectively than the heuristics actually used in the pilot study. Notably, the algorithms achieved these institutional goals while resulting in lower average parking rates for users, suggesting that accounting for dynamic performativity can lead to more efficient and equitable outcomes.
Strategic Robustness
In experiments using the "Give Me Some Credit" dataset, the authors demonstrated that standard retraining methods (Repeated Risk Minimization) often fail to reach the performative optimum when agents are strategic and the environment has memory. In contrast, the epoch-based approach successfully converged to the optimal decision by accounting for the long-term equilibrium of the system.
Conclusion and Future Work
This research provides a robust theoretical foundation for decision-making in adaptive environments. By recognizing that environments have memory, the epoch-based approach bridges the gap between theoretical performative prediction and real-world dynamic systems.
Future research directions include addressing environments with periodic dynamics (e.g., seasonality), developing adaptive epoch lengths that do not require prior knowledge of the decay rate, and exploring non-linear memory processes where the rate of adaptation might itself depend on the decision being made.
Summary updated