Decision-Dependent Risk Minimization in Geometrically Decaying Dynamic Environments
This addresses decision-dependent risk minimization in dynamic environments, offering incremental algorithmic improvements with practical applications like dynamic pricing.
The paper tackles the problem of minimizing expected loss when the data distribution depends on the decision-maker's action and evolves dynamically with geometric decay, introducing novel algorithms for gradient and loss function oracle settings that deploy fixed decisions over epochs to allow environment mixing. The algorithms match existing stochastic gradient method rates up to logarithmic factors and, in a semi-synthetic evaluation using SFpark data, improve the institution's target occupancy while reducing parking rates.
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 repeatedly deploys a fixed decision 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.