TL;DR
This paper introduces the first provably sample-efficient offline policy learning algorithms designed to maximize quantiles of reward distributions (such as the median or lower percentiles) under unmeasured confounding and partial data coverage. By reformulating quantile estimation into nonlinear conditional moment restrictions using instrumental variables or negative controls, the authors establish a pessimistic minimax framework achieving near-optimal $\tilde{O}(n^{-1/2})$ regret.
What Problem Does This Paper Address?
In high-stakes offline decision-making—such as healthcare or social welfare programs—practitioners often care about distributional outcomes (e.g., boosting the 20th percentile of wages or lowering extreme hospital readmission times) rather than simply maximizing expected returns. However, learning quantile-optimal policies offline is notoriously hard due to three compounding obstacles:
- Unmeasured Confounding: Hidden factors simultaneously influence historical actions and outcomes, biasing standard quantile regressions.
- Nonlinear Functionals: Quantile objectives depend nonlinearly on the outcome distribution, ruling out standard linear Bellman or regression formulations.
- Insufficient Coverage: The offline dataset rarely covers all possible policies. Suboptimal, underexplored actions can induce high estimator variance, leading naive greedy policies to fail catastrophically.
Methods
The authors address confounding and partial coverage through a unified causal inference and pessimism framework:
- Causal Identification via Moment Restrictions:
- Instrumental Variables (IV): Structural quantiles are identified using conditional moment restrictions $\mathbb{E}[1\{Y \le h(A,X)\} - \alpha \mid X, Z] = 0$.
- Negative Controls (NC): The authors introduce the first conditional moment restrictions for structural quantiles using negative control exposure-outcome pairs $(E, V)$, solved via two simultaneous bridge equations and data augmentation.
- Minimax Estimation via Fenchel Duality: Direct estimation of squared conditional expectations introduces severe sample variance bias. Using Fenchel duality, the authors formulate a saddle-point empirical loss $\mathcal{L}_n(h)$ against a rich test function class $\Theta$.
- Pessimistic Policy Optimization:
- Solution Set (SS) Algorithm: Constructs an uncertainty set $\mathcal{S}(e_n)$ of candidate quantile functions and selects the policy maximizing the worst-case estimated performance: $$\hat{\pi} = \arg\max_\pi \inf_{h \in \mathcal{S}(e_n)} v(h, \pi)$$
- Regularized Algorithm: To bypass the computationally heavy data-dependent constraint, they formulate an augmented Lagrangian variant adding a penalty $\lambda_n \mathcal{E}_n(h)$, making the inner optimization solvable via gradient descent and linear programming.
Datasets
- Synthetic Confounded ODCP Benchmark: Evaluated on synthetic offline contextual bandit data with $X, Z \sim \mathcal{N}(0, 1)$, binary action $A$, confounder-induced error $\epsilon \sim \mathcal{N}(-\Phi^{-1}(\alpha), 1)$, and reward $Y = X + 3XA + \epsilon$.
- Contamination Stress-Testing: Offline datasets were deliberately corrupted with $p \in \{20\%, 50\%, 70\%\}$ pure noise actions to explicitly test algorithm robustness against poor coverage and spurious correlations across sample sizes $n \in \{50, 100, \dots, 6400\}$.
- Real-world benchmark datasets: None evaluated empirically (though motivating applications from job training programs and electronic health records are formally framed).
Key Insights and Ideas
- Fast Rates Without Global Coverage: The pessimism principle ensures that coverage is only required over the optimal policy’s trajectory (via a mild change-of-measure condition), ignoring unexplored regions of the action space.
- No Efficiency Loss Despite Nonlinearity: By conducting a local Taylor expansion of the nonlinear operator around the true structural quantile and bounding empirical process deviations via bracketing numbers, the authors prove an $\tilde{O}(n^{-1/2})$ regret rate. This matches the fast statistical rate achieved in standard mean-reward offline policy learning.
- Regularization vs. Constraint Trade-off: The regularized algorithm trades off an infinitesimal factor $\epsilon_{\lambda_n}$ in convergence rate—achieving $\tilde{O}(n^{-1/2(1 - \epsilon_{\lambda_n})})$—in exchange for a computationally benign unconstrained objective.
Key Results
- Theoretical Guarantees:
- The Solution Set policy achieves $\text{Regret}(\hat{\pi}) \le \tilde{O}(n^{-1/2})$ under both IV and Negative Control identification setups.
- The Regularized policy achieves $\text{Regret}(\hat{\pi}_R) \le \tilde{O}(n^{-1/2(1 - \epsilon_{\lambda_n})})$ when setting $\lambda_n = \eta_n^{-(1 + \epsilon_{\lambda_n})}$, outperforming prior offline regularized rates (e.g., $\tilde{O}(n^{-1/3})$).
- Empirical Performance: In synthetic experiments, the regularized pessimistic policy’s regret decays steadily toward zero as sample size grows. Remarkably, even when 70% of the actions in the offline dataset consist of random noise, the algorithm converges reliably, demonstrating resilience to heavy data contamination.
Limitations and Future Work
- Continuous Outcome Restriction: The theoretical analysis requires the outcome $Y$ to have a smooth, bounded conditional density so that pathwise derivatives exist; discrete rewards are not directly supported without smoothing (e.g., Gaussian convolution).
- Stronger Assumptions for Negative Controls: The Negative Control setup demands an $L_\infty$ bounded change-of-measure condition (unlike $L_2$ for IV), implying uniform support over covariates and control outcomes.
- Non-smoothness in Practice: Because the quantile indicator $1\{Y \le h\}$ is non-differentiable, implementation requires surrogate smoothing (e.g., sigmoid approximations), which introduces a practical optimization gap not fully reflected in the asymptotic theory.
Summary updated