Decision-Dependent Risk Minimization in Geometrically Decaying Dynamic Environments

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

[AAAI-22] Main Track
Abstract: This paper considers 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. Motivated by practice, empirical information settings are considered: namely, the decision-maker either has oracle access, for a fixed batch size, to the empirical gradient of the loss (first order setting), or the empirical loss function (zero order setting). Novel algorithms for each of these settings are introduced, both of which operate on the same underlying principle: the decision-maker repeatedly deploys a fixed decision over a fixed length epoch, thereby allowing the dynamically changing environment to sufficiently mix before updating the decision. The proposed algorithms are shown to converge to the optimal point. Specifically, high-probability sample complexity guarantees are given, which depend exponentially on the epoch length and logarithmically on the batch size. 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 Video

Sessions where this paper appears

  • Poster Session 4

    Blue 3

  • Poster Session 9

    Blue 3