Beyond IID: data-driven decision-making in heterogeneous environments

• URL: http://arxiv.org/abs/2206.09642v4
• Date: Wed, 19 Jun 2024 14:49:17 GMT
• Title: Beyond IID: data-driven decision-making in heterogeneous environments
• Authors: Omar Besbes, Will Ma, Omar Mouchtaki,
• Abstract summary: We study a data-driven decision-making framework in which historical samples are generated from unknown and different distributions. This work aims at analyzing the performance of central data-driven policies but also near-optimal ones.
• Score: 8.714718004930363
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: How should one leverage historical data when past observations are not perfectly indicative of the future, e.g., due to the presence of unobserved confounders which one cannot "correct" for? Motivated by this question, we study a data-driven decision-making framework in which historical samples are generated from unknown and different distributions assumed to lie in a heterogeneity ball with known radius and centered around the (also) unknown future (out-of-sample) distribution on which the performance of a decision will be evaluated. This work aims at analyzing the performance of central data-driven policies but also near-optimal ones in these heterogeneous environments and understanding key drivers of performance. We establish a first result which allows to upper bound the asymptotic worst-case regret of a broad class of policies. Leveraging this result, for any integral probability metric, we provide a general analysis of the performance achieved by Sample Average Approximation (SAA) as a function of the radius of the heterogeneity ball. This analysis is centered around the approximation parameter, a notion of complexity we introduce to capture how the interplay between the heterogeneity and the problem structure impacts the performance of SAA. In turn, we illustrate through several widely-studied problems -- e.g., newsvendor, pricing -- how this methodology can be applied and find that the performance of SAA varies considerably depending on the combinations of problem classes and heterogeneity. The failure of SAA for certain instances motivates the design of alternative policies to achieve rate-optimality. We derive problem-dependent policies achieving strong guarantees for the illustrative problems described above and provide initial results towards a principled approach for the design and analysis of general rate-optimal algorithms.

Related papers

• Stochastic Gradient Descent with Adaptive Data [4.119418481809095]
  gradient descent (SGD) is a powerful optimization technique that is particularly useful in online learning scenarios. Applying SGD to policy optimization problems in operations research involves a distinct challenge: the policy changes the environment and thereby affects the data used to update the policy. The influence of previous decisions on the data generated introduces bias in the gradient estimate, which presents a potential source of instability for online learning not present in the iid case. We show that the convergence speed of SGD with adaptive data is largely similar to the classical iid setting, as long as the mixing time of the policy-induced dynamics is factored in.
  arXiv  Detail & Related papers  (2024-10-02T02:58:32Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [61.580419063416734]
  A recent stream of structured learning approaches has improved the practical state of the art for a range of optimization problems. The key idea is to exploit the statistical distribution over instances instead of dealing with instances separately. In this article, we investigate methods that smooth the risk by perturbing the policy, which eases optimization and improves the generalization error.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• It's All in the Mix: Wasserstein Machine Learning with Mixed Features [5.739657897440173]
  We present a practically efficient algorithm to solve mixed-feature problems. We demonstrate that our approach can significantly outperform existing methods that are to the presence of discrete features.
  arXiv  Detail & Related papers  (2023-12-19T15:15:52Z)
• Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [59.758009422067]
  We consider the problem of quantifying uncertainty over expected cumulative rewards in model-based reinforcement learning. We propose a new uncertainty Bellman equation (UBE) whose solution converges to the true posterior variance over values. We introduce a general-purpose policy optimization algorithm, Q-Uncertainty Soft Actor-Critic (QU-SAC) that can be applied for either risk-seeking or risk-averse policy optimization.
  arXiv  Detail & Related papers  (2023-12-07T15:55:58Z)
• DRFLM: Distributionally Robust Federated Learning with Inter-client Noise via Local Mixup [58.894901088797376]
  federated learning has emerged as a promising approach for training a global model using data from multiple organizations without leaking their raw data. We propose a general framework to solve the above two challenges simultaneously. We provide comprehensive theoretical analysis including robustness analysis, convergence analysis, and generalization ability.
  arXiv  Detail & Related papers  (2022-04-16T08:08:29Z)
• Reinforcement Learning with Heterogeneous Data: Estimation and Inference [84.72174994749305]
  We introduce the K-Heterogeneous Markov Decision Process (K-Hetero MDP) to address sequential decision problems with population heterogeneity. We propose the Auto-Clustered Policy Evaluation (ACPE) for estimating the value of a given policy, and the Auto-Clustered Policy Iteration (ACPI) for estimating the optimal policy in a given policy class. We present simulations to support our theoretical findings, and we conduct an empirical study on the standard MIMIC-III dataset.
  arXiv  Detail & Related papers  (2022-01-31T20:58:47Z)
• Integrated Conditional Estimation-Optimization [6.037383467521294]
  Many real-world optimization problems uncertain parameters with probability can be estimated using contextual feature information. In contrast to the standard approach of estimating the distribution of uncertain parameters, we propose an integrated conditional estimation approach. We show that our ICEO approach is theally consistent under moderate conditions.
  arXiv  Detail & Related papers  (2021-10-24T04:49:35Z)
• Complexity-Free Generalization via Distributionally Robust Optimization [4.313143197674466]
  We present an alternate route to obtain generalization bounds on the solution from distributionally robust optimization (DRO) Our DRO bounds depend on the ambiguity set geometry and its compatibility with the true loss function. Notably, when using maximum mean discrepancy as a DRO distance metric, our analysis implies, to the best of our knowledge, the first generalization bound in the literature that depends solely on the true loss function.
  arXiv  Detail & Related papers  (2021-06-21T15:19:52Z)
• Accounting for Unobserved Confounding in Domain Generalization [107.0464488046289]
  This paper investigates the problem of learning robust, generalizable prediction models from a combination of datasets. Part of the challenge of learning robust models lies in the influence of unobserved confounders. We demonstrate the empirical performance of our approach on healthcare data from different modalities.
  arXiv  Detail & Related papers  (2020-07-21T08:18:06Z)
• Kidney Exchange with Inhomogeneous Edge Existence Uncertainty [33.17472228570093]
  We aim to maximize a matched cycle and chain packing problem, where we aim to identify structures in a directed graph to the edge of failure. Our approaches on data from the United for Sharing (SUNO) provides better performance with the same weights as as an SAA-based method.
  arXiv  Detail & Related papers  (2020-07-07T04:08:39Z)
• Learning Overlapping Representations for the Estimation of Individualized Treatment Effects [97.42686600929211]
  Estimating the likely outcome of alternatives from observational data is a challenging problem. We show that algorithms that learn domain-invariant representations of inputs are often inappropriate. We develop a deep kernel regression algorithm and posterior regularization framework that substantially outperforms the state-of-the-art on a variety of benchmarks data sets.
  arXiv  Detail & Related papers  (2020-01-14T12:56:29Z)

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.