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

arXiv: https://arxiv.org/abs/2206.09642 · HTML: https://mlsanity.com/paper/2206.09642/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 77 references that are in the map.
- First posted on arXiv 20 Jun 2022.

## Builds on (most cited first, 22 of 22)

- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Corruption-robust exploration in episodic reinforcement learning](https://mlsanity.com/paper/1911.08689/) (2019)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [Hedging the Drift: Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1903.01461/) (2019)
- [Robust Sample Average Approximation](https://mlsanity.com/paper/1408.4445/) (2014)
- [Learning Whenever Learning is Possible: Universal Learning under General Stochastic Processes](https://mlsanity.com/paper/1706.01418/) (2017)
- [Multi-Item Mechanisms without Item-Independence: Learnability via Robustness](https://mlsanity.com/paper/1911.02146/) (2019)
- [Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries](https://mlsanity.com/paper/2202.08549/) (2022)
- [Learning Multi-item Auctions with (or without) Samples](https://mlsanity.com/paper/1709.00228/) (2017)
- [Making the Most of Your Samples](https://mlsanity.com/paper/1407.2479/) (2014)
- [On the power of adaptivity in statistical adversaries](https://mlsanity.com/paper/2111.10352/) (2021)
- [Universal Online Learning: an Optimistically Universal Learning Rule](https://mlsanity.com/paper/2201.05947/) (2022)
- [How Big Should Your Data Really Be? Data-Driven Newsvendor: Learning One Sample at a Time](https://mlsanity.com/paper/2107.02742/) (2021)
- [Relaxing the I.I.D. Assumption: Adaptively Minimax Optimal Regret via Root-Entropic Regularization](https://mlsanity.com/paper/2007.06552/) (2020)
- [Randomization beats Second Price as a Prior-Independent Auction](https://mlsanity.com/paper/1507.08042/) (2015)
- [Are Two (Samples) Really Better Than One? On the Non-Asymptotic Performance of Empirical Revenue Maximization](https://mlsanity.com/paper/1802.08037/) (2018)
- [Robust Learning of Optimal Auctions](https://mlsanity.com/paper/2107.06259/) (2021)

## Built on by (most cited first, 9 of 9)

- [Binary Search with Distributional Predictions](https://mlsanity.com/paper/2411.16030/) (2024)
- [Online Algorithms with Uncertainty-Quantified Predictions](https://mlsanity.com/paper/2310.11558/) (2023)
- [Best Arm Identification with Possibly Biased Offline Data](https://mlsanity.com/paper/2505.23165/) (2025)
- [Contextual Optimization under Covariate Shift: A Robust Approach by Intersecting Wasserstein Balls](https://mlsanity.com/paper/2406.02426/) (2024)
- [Practical Performative Policy Learning with Strategic Agents](https://mlsanity.com/paper/2412.01344/) (2024)
- [Ski Rental with Distributional Predictions of Unknown Quality](https://mlsanity.com/paper/2602.21104/) (2026)
- [Survey of Data-driven Newsvendor: Unified Analysis and Spectrum of Achievable Regrets](https://mlsanity.com/paper/2409.03505/) (2024)
- [From Stream to Pool: Pricing Under the Law of Diminishing Marginal Utility](https://mlsanity.com/paper/2310.19220/) (2023)
- [Robust and Consistent Ski Rental with Distributional Advice](https://mlsanity.com/paper/2603.29233/) (2026)

## Abstract (arXiv)

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.