Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy
This work addresses the challenge of decision making in dynamic environments for machine learning and AI, offering a unified theoretical framework that connects multiple areas, though it is incremental in building on existing concepts like the Decision-Estimation Coefficient.
The authors tackled the problem of interactive decision making in changing environments by proposing a hybrid framework that interpolates between stochastic and adversarial settings, enabling unified analysis of local differential privacy, query-based learning, and robustness, with new results for contextual bandits under LDP constraints.
We study the problem of interactive decision making in which the underlying environment changes over time subject to given constraints. We propose a framework, which we call \textit{hybrid Decision Making with Structured Observations} (hybrid DMSO), that provides an interpolation between the stochastic and adversarial settings of decision making. Within this framework, we can analyze local differentially private (LDP) decision making, query-based learning (in particular, SQ learning), and robust and smooth decision making under the same umbrella, deriving upper and lower bounds based on variants of the Decision-Estimation Coefficient (DEC). We further establish strong connections between the DEC's behavior, the SQ dimension, local minimax complexity, learnability, and joint differential privacy. To showcase the framework's power, we provide new results for contextual bandits under the LDP constraint.