Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy

Fan Chen, Alexander Rakhlin
Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:983-985, 2025.

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 this Paper

BibTeX
@InProceedings{pmlr-v291-chen25b, 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}, pages = {983--985}, year = {2025}, editor = {Haghtalab, Nika and Moitra, Ankur}, volume = {291}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--04 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v291/main/assets/chen25b/chen25b.pdf}, url = {https://proceedings.mlr.press/v291/chen25b.html}, 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. } }
Endnote
%0 Conference Paper %T Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy %A Fan Chen %A Alexander Rakhlin %B Proceedings of Thirty Eighth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Nika Haghtalab %E Ankur Moitra %F pmlr-v291-chen25b %I PMLR %P 983--985 %U https://proceedings.mlr.press/v291/chen25b.html %V 291 %X 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.
APA
Chen, F. & Rakhlin, A.. (2025). Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy. Proceedings of Thirty Eighth Conference on Learning Theory, in Proceedings of Machine Learning Research 291:983-985 Available from https://proceedings.mlr.press/v291/chen25b.html.

Related Material