Decision-Dependent Stochastic Optimization: The Role of Distribution Dynamics
Distribution shifts have long been regarded as troublesome external forces that a decision-maker should either counteract or conform to. An intriguing feedback phenomenon termed decision dependence arises when the deployed decision affects the environment and alters the data-generating distribution. In the realm of performative prediction, this is encoded by distribution maps parameterized by decisions due to strategic behaviors. In contrast, we formalize an endogenous distribution shift as a feedback process featuring nonlinear dynamics that couple the evolving distribution with the decision. Stochastic optimization in this dynamic regime provides a fertile ground to examine the various roles played by dynamics in the composite problem structure. To this end, we develop an online algorithm that achieves optimal decision-making by both adapting to and shaping the dynamic distribution. Throughout the paper, we adopt a distributional perspective and demonstrate how this view facilitates characterizations of distribution dynamics and the optimality and generalization performance of the proposed algorithm. We showcase the theoretical results in an opinion dynamics context, where an opportunistic party maximizes the affinity of a dynamic polarized population, and in a recommender system scenario, featuring performance optimization with discrete distributions in the probability simplex.
Code (1)
Tasks
Recommendation SystemsStochastic OptimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Solving Decision-Dependent Games by Learning from Feedback
This paper tackles the problem of solving stochastic optimization problems with a decision-dependent distribution in the setting of stochastic strongly-monotone games and when the distributional dependence is unknown. A …
Stochastic OptimizationParameter-Free Algorithms for Performative Regret Minimization under Decision-Dependent Distributions
This paper studies performative risk minimization, a formulation of stochastic optimization under decision-dependent distributions. We consider the general case where the performative risk can be non-convex, for which we…
Stochastic OptimizationRole of Externally Provided Randomness in Stochastic Teams and Zero-sum Team Games
Stochastic team decision problem is extensively studied in literature and the existence of optimal solution is obtained in recent literature. The value of information in statistical problem and decision theory is classic…
Stochastic Optimization with Optimal Importance Sampling
Importance Sampling (IS) is a widely used variance reduction technique for enhancing the efficiency of Monte Carlo methods, particularly in rare-event simulation and related applications. Despite its power, the performan…
Stochastic OptimizationRockafellian Relaxation and Stochastic Optimization under Perturbations
In practice, optimization models are often prone to unavoidable inaccuracies due to dubious assumptions and corrupted data. Traditionally, this placed special emphasis on risk-based and robust formulations, and their foc…
Novel ConceptsStochastic Optimization