统一分析动态环境下的鲁棒决策、私密学习与查询学习，提出新框架并给出紧致边界。
Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy
- 构建混合观测决策框架，融合随机与对抗设定
- 在局部差分隐私下实现上下文老虎机的新最优率
- 适用于关注隐私保护与鲁棒性的算法研究者
我们研究随时间变化的交互式决策问题，其环境受给定约束影响。提出一种名为「结构化观测的混合决策」（hybrid DMSO）的框架，可在随机与对抗设定间插值。该框架统一分析局部差分隐私（LDP）决策、基于查询的学习（特别是SQ学习）、以及鲁棒平滑决策，并基于决策-估计系数（DEC）的变体推导出上下界。进一步揭示了DEC行为与SQ维度、局部极小极大复杂度、可学习性及联合差分隐私之间的深刻联系。为展示框架能力，我们给出了在局部差分隐私约束下上下文老虎机的新结果。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。