Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy
Abstract
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 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.
Cite
Text
Chen and Rakhlin. "Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy." Proceedings of Thirty Eighth Conference on Learning Theory, 2025.Markdown
[Chen and Rakhlin. "Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy." Proceedings of Thirty Eighth Conference on Learning Theory, 2025.](https://mlanthology.org/colt/2025/chen2025colt-decision/)BibTeX
@inproceedings{chen2025colt-decision,
title = {{Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy}},
author = {Chen, Fan and Rakhlin, Alexander},
booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory},
year = {2025},
pages = {983-985},
volume = {291},
url = {https://mlanthology.org/colt/2025/chen2025colt-decision/}
}