Time-uniform confidence bands for the CDF under nonstationarity
This work addresses a gap in distribution estimation for non-i.i.d. data, relevant for decision-making in controlled experiments like A/B tests or contextual bandits.
The paper tackles the problem of estimating the complete distribution of a random variable under nonstationary, arbitrary data-dependent settings, presenting time-uniform and value-uniform confidence bands for the CDF with an instance-dependent convergence guarantee.
Estimation of the complete distribution of a random variable is a useful primitive for both manual and automated decision making. This problem has received extensive attention in the i.i.d. setting, but the arbitrary data dependent setting remains largely unaddressed. Consistent with known impossibility results, we present computationally felicitous time-uniform and value-uniform bounds on the CDF of the running averaged conditional distribution of a real-valued random variable which are always valid and sometimes trivial, along with an instance-dependent convergence guarantee. The importance-weighted extension is appropriate for estimating complete counterfactual distributions of rewards given controlled experimentation data exhaust, e.g., from an A/B test or a contextual bandit.