# Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 66 references that are in the map.
- First posted on arXiv 3 Jun 2021.

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

- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [OpenML Benchmarking Suites](https://mlsanity.com/paper/1708.03731/) (2017)
- [Doubly Robust Policy Evaluation and Optimization](https://mlsanity.com/paper/1503.02834/) (2015)
- [Orthogonal Statistical Learning](https://mlsanity.com/paper/1901.09036/) (2019)
- [More Robust Doubly Robust Off-policy Evaluation](https://mlsanity.com/paper/1802.03493/) (2018)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Confidence Intervals for Policy Evaluation in Adaptive Experiments](https://mlsanity.com/paper/1911.02768/) (2019)
- [Fast Rates for Contextual Linear Optimization](https://mlsanity.com/paper/2011.03030/) (2020)
- [Dynamic Pricing with Demand Covariates](https://mlsanity.com/paper/1604.07463/) (2016)
- [Optimal Off-Policy Evaluation from Multiple Logging Policies](https://mlsanity.com/paper/2010.11002/) (2020)
- [Intrinsically Efficient, Stable, and Bounded Off-Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1906.03735/) (2019)
- [Fast Rates for the Regret of Offline Reinforcement Learning](https://mlsanity.com/paper/2102.00479/) (2021)
- [Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes](https://mlsanity.com/paper/1909.02553/) (2019)
- [Estimation Considerations in Contextual Bandits](https://mlsanity.com/paper/1711.07077/) (2017)
- [Dynamic Assortment Personalization in High Dimensions](https://mlsanity.com/paper/1610.05604/) (2016)
- [Contextual bandits with surrogate losses: Margin bounds and efficient algorithms](https://mlsanity.com/paper/1806.10745/) (2018)
- [Generalized Policy Elimination: an efficient algorithm for Nonparametric Contextual Bandits](https://mlsanity.com/paper/2003.02873/) (2020)

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

- [Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequality](https://mlsanity.com/paper/2212.09900/) (2022)
- [Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR](https://mlsanity.com/paper/2302.03201/) (2023)
- [Near-Optimal Non-Parametric Sequential Tests and Confidence Sequences with Possibly Dependent Observations](https://mlsanity.com/paper/2212.14411/) (2022)
- [Sequential Counterfactual Risk Minimization](https://mlsanity.com/paper/2302.12120/) (2023)
- [Positivity-free Policy Learning with Observational Data](https://mlsanity.com/paper/2310.06969/) (2023)
- [Distributionally Robust Policy Learning under Concept Drifts](https://mlsanity.com/paper/2412.14297/) (2024)
- [Demistifying Inference after Adaptive Experiments](https://mlsanity.com/paper/2405.01281/) (2024)
- [Sequential Off-Policy Learning with Logarithmic Smoothing](https://mlsanity.com/paper/2506.10664/) (2025)
- [Fast Best-in-Class Regret for Contextual Bandits](https://mlsanity.com/paper/2510.15483/) (2025)
- [Wasserstein Policy Learning for Distributional Outcomes](https://mlsanity.com/paper/2606.19117/) (2026)

## Abstract (arXiv)

Empirical risk minimization (ERM) is the workhorse of machine learning, whether for classification and regression or for off-policy policy learning, but its model-agnostic guarantees can fail when we use adaptively collected data, such as the result of running a contextual bandit algorithm. We study a generic importance sampling weighted ERM algorithm for using adaptively collected data to minimize the average of a loss function over a hypothesis class and provide first-of-their-kind generalization guarantees and fast convergence rates. Our results are based on a new maximal inequality that carefully leverages the importance sampling structure to obtain rates with the right dependence on the exploration rate in the data. For regression, we provide fast rates that leverage the strong convexity of squared-error loss. For policy learning, we provide rate-optimal regret guarantees that close an open gap in the existing literature whenever exploration decays to zero, as is the case for bandit-collected data. An empirical investigation validates our theory.