Decision-Dependent Risk Minimization in Geometrically Decaying Dynamic Environments

Mitas Ray, Lillian J. Ratliff, Dmitriy Drusvyatskiy, Maryam Fazel

Abstract

This paper studies the problem of expected loss minimization given a data distribution that is dependent on the decision-maker's action and evolves dynamically in time according to a geometric decay process. Novel algorithms for both the information setting in which the decision-maker has a first order gradient oracle and the setting in which they have simply a loss function oracle are introduced. The algorithms operate on the same underlying principle: the decision-maker deploys a fixed decision repeatedly over the length of an epoch, thereby allowing the dynamically changing environment to sufficiently mix before updating the decision. The iteration complexity in each of the settings is shown to match existing rates for first and zero order stochastic gradient methods up to logarithmic factors. The algorithms are evaluated on a "semi-synthetic" example using real world data from the SFpark dynamic pricing pilot study; it is shown that the announced prices result in an improvement for the institution's objective (target occupancy), while achieving an overall reduction in parking rates.

Introduction

In traditional machine learning, data is often assumed to be drawn from a static, fixed distribution. However, many real-world applications—such as credit scoring, insurance pricing, or traffic routing—are "performative." In these settings, the model's decisions actively shift the underlying data distribution. While previous research often assumes these shifts occur instantaneously, real-world environments possess inertia or "memory." For instance, changing parking prices does not immediately result in a new equilibrium occupancy; it takes time for drivers to adjust their habits. This paper addresses the challenge of finding performatively optimal decisions in environments governed by a geometrically decaying dynamic process.

Modeling Dynamic Environments

The authors model the environment's state as a weighted mixture of its previous state and a target distribution induced by the current decision. This geometric decay captures the reality that systems do not reset instantly. The core difficulty lies in the fact that the decision-maker typically observes transient, shifting data rather than the steady-state distribution. To find the "performatively optimal" point—the best long-term decision—the decision-maker must account for these feedback loops.

Epoch-Based Algorithms

To solve this, the paper introduces a framework based on Epoch-Based Stochastic Gradient Descent. The central strategy is "timescale separation": a decision is held constant for a specific number of steps (an epoch). This allows the environment to "mix" and approach its fixed-point distribution before the next update is made.

Two primary algorithms are proposed:

  1. Epoch-Based First-Order Algorithm: Utilized when a gradient oracle is available, such as when the decision-maker has a parametric model of distribution shifts.
  2. Epoch-Based Zeroth-Order Algorithm: Designed for "bandit feedback" settings where only the resulting loss value is observable. It employs a one-point gradient estimate by sampling around the current decision.

The authors prove that by increasing the epoch length logarithmically relative to the desired accuracy, they can achieve convergence rates comparable to standard stochastic gradient methods in static environments: $O(1/\epsilon)$ for first-order and $O(d^2/\epsilon^2)$ for zeroth-order settings.

Empirical Evaluation: The SFpark Pilot

The algorithms were validated using a "semi-synthetic" dataset derived from the SFpark project, a dynamic pricing pilot for on-street parking in San Francisco. Real occupancy and pricing data were used to estimate parameters like price elasticity and geometric decay rates.

Summary of SFpark simulation results showing prices and occupancy across various street segments.

The simulation results demonstrate that the proposed algorithms successfully converged to the target occupancy range (60–80%) across multiple street blocks. Notably, the algorithms often achieved the city's 70% target occupancy while maintaining lower average prices than the original SFpark heuristics, representing a "win-win" for both the city and the public.

Key Results and Insights

The theoretical analysis shows that the epoch-based approach effectively manages the "bias" introduced by environmental dynamics. In practice, the Zeroth-Order algorithm proved highly functional despite requiring more iterations to settle due to the variance inherent in derivative-free estimation.

Convergence of price and occupancy over 125 weeks for Beach St 600, comparing First-Order (FO) and Zeroth-Order (ZO) methods.

As shown in the convergence plots, the choice of epoch parameters ($n, T$) significantly impacts the stability and speed of convergence. The "patience" inherent in the epoch approach prevents the model from overreacting to transient data that has not yet reflected the full impact of previous decisions.

Conclusion

This work highlights the importance of accounting for environmental memory in performative prediction. While the current framework assumes geometric decay and strong convexity, it provides a robust foundation for managing decision-dependent distributions. Future research may extend these methods to more complex dynamics, such as seasonal cycles or non-linear response patterns.

Summary updated

Abstract

This paper studies the problem of expected loss minimization given a data distribution that is dependent on the decision-maker's action and evolves dynamically in time according to a geometric decay process. Novel algorithms for both the information setting in which the decision-maker has a first order gradient oracle and the setting in which they have simply a loss function oracle are introduced. The algorithms operate on the same underlying principle: the decision-maker deploys a fixed decision repeatedly over the length of an epoch, thereby allowing the dynamically changing environment to sufficiently mix before updating the decision. The iteration complexity in each of the settings is shown to match existing rates for first and zero order stochastic gradient methods up to logarithmic factors. The algorithms are evaluated on a ``semi-synthetic" example using real world data from the SFpark dynamic pricing pilot study; it is shown that the announced prices result in an improvement for the institution's objective (target occupancy), while achieving an overall reduction in parking rates.
BibTeX
@inproceedings{ray2022decision,
  author = {Mitas Ray and Lillian J. Ratliff and Dmitriy Drusvyatskiy and Maryam Fazel},
  title = {{Decision-Dependent Risk Minimization in Geometrically Decaying Dynamic Environments}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=94DbRy65MV},
}
Figure