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

• URL: http://arxiv.org/abs/2501.14928v1
• Date: Fri, 24 Jan 2025 21:31:50 GMT
• Title: Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy
• Authors: Fan Chen, Alexander Rakhlin,
• Abstract summary: 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 provides an complexity between the complexity and adversarial settings of decision making.
• Score: 59.64384863882473
• License:
• 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 (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.

Related papers

• Hierarchical Upper Confidence Bounds for Constrained Online Learning [4.8951183832371]
  We introduce the hierarchical constrained bandits (HCB) framework, which extends the contextual bandit problem to incorporate hierarchical decision structures and multi-level constraints. Our theoretical analysis establishes sublinear regret bounds for HC-UCB and provides high-probability guarantees for constraint satisfaction at all hierarchical levels.
  arXiv  Detail & Related papers  (2024-10-22T17:41:14Z)
• Making Large Language Models Better Planners with Reasoning-Decision Alignment [70.5381163219608]
  We motivate an end-to-end decision-making model based on multimodality-augmented LLM. We propose a reasoning-decision alignment constraint between the paired CoTs and planning results. We dub our proposed large language planners with reasoning-decision alignment as RDA-Driver.
  arXiv  Detail & Related papers  (2024-08-25T16:43:47Z)
• Sequential three-way group decision-making for double hierarchy hesitant fuzzy linguistic term set [8.081831444300489]
  Group decision-making (GDM) characterized by complexity and uncertainty is an essential part of various life scenarios. To address this issue, a novel multi-level sequential three-way decision for group decision-making (S3W-GDM) method is constructed from the perspective of granular computing.
  arXiv  Detail & Related papers  (2024-06-27T04:33:26Z)
• Differentiable Distributionally Robust Optimization Layers [10.667165962654996]
  We develop differentiable DRO layers for generic mixed-integer DRO problems with parameterized second-order conic ambiguity sets. We propose a novel dual-view methodology by handling continuous and discrete parts of decisions via different principles. Specifically, we construct a differentiable energy-based surrogate to implement the dual-view methodology and use importance sampling to estimate its gradient.
  arXiv  Detail & Related papers  (2024-06-24T12:09:19Z)
• Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient [51.37720227675476]
  We introduce a new variant of the Decision-Estimation Coefficient, and use it to derive new lower bounds that improve upon prior work on three fronts. We provide upper bounds on regret that scale with the same quantity, thereby closing all but one of the gaps between upper and lower bounds in Foster et al. Our results apply to both the regret framework and PAC framework, and make use of several new analysis and algorithm design techniques that we anticipate will find broader use.
  arXiv  Detail & Related papers  (2023-01-19T18:24:08Z)
• RISE: Robust Individualized Decision Learning with Sensitive Variables [1.5293427903448025]
  A naive baseline is to ignore sensitive variables in learning decision rules, leading to significant uncertainty and bias. We propose a decision learning framework to incorporate sensitive variables during offline training but not include them in the input of the learned decision rule during model deployment.
  arXiv  Detail & Related papers  (2022-11-12T04:31:38Z)
• On the Complexity of Adversarial Decision Making [101.14158787665252]
  We show that the Decision-Estimation Coefficient is necessary and sufficient to obtain low regret for adversarial decision making. We provide new structural results that connect the Decision-Estimation Coefficient to variants of other well-known complexity measures.
  arXiv  Detail & Related papers  (2022-06-27T06:20:37Z)
• Reinforcement Learning with a Terminator [80.34572413850186]
  We learn the parameters of the TerMDP and leverage the structure of the estimation problem to provide state-wise confidence bounds. We use these to construct a provably-efficient algorithm, which accounts for termination, and bound its regret.
  arXiv  Detail & Related papers  (2022-05-30T18:40:28Z)
• The Statistical Complexity of Interactive Decision Making [126.04974881555094]
  We provide a complexity measure, the Decision-Estimation Coefficient, that is proven to be both necessary and sufficient for sample-efficient interactive learning. A unified algorithm design principle, Estimation-to-Decisions (E2D), transforms any algorithm for supervised estimation into an online algorithm for decision making.
  arXiv  Detail & Related papers  (2021-12-27T02:53:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.