arXiv 25 Jul 2025 · Econometrics
arXiv:2507.19596 · PDF · Extracted main text
This paper investigates the challenges of optimal online policy learning under missing data. State-of-the-art algorithms implicitly assume that rewards are always observable. I show that when rewards are missing at random, the Upper Confidence Bound (UCB) algorithm maintains optimal regret bounds; however, it selects suboptimal policies with high probability as soon as this assumption is relaxed. To overcome this limitation, I introduce a fully nonparametric algorithm-Doubly-Robust Upper Confidence Bound (DR-UCB)-which explicitly models the form of missingness through observable covariates and achieves a nearly-optimal worst-case regret rate of $\widetilde{O}(\sqrt{T})$. To prove this result, I derive high-probability bounds for a class of doubly-robust estimators that hold under broad dependence structures. Simulation results closely match the theoretical predictions, validating the proposed framework.
appendix boundary found by none_found · 100% of the source is main text. Read the extracted text to check this.
The works this paper leans on most, across its whole bibliography — not restricted to papers in our corpus. Ranked by composite intensity, which combines how often a work is mentioned, how many sections mention it, and how much of that falls in the main text rather than the appendix.
| Reference | Intensity | Mentions | Sections | Main text | |
|---|---|---|---|---|---|
| 1 | Lattimore and Szepesvári (2020) | 1.000 | 7 | 4 | 100% |
| 2 | Auer, Cesa-Bianchi and Fischer (2002) Finite-Time Analysis of the Multiarmed Bandit Problem | 0.811 | 4 | 2 | 100% |
| 3 | Horvitz and Thompson (1952) A Generalization of Sampling Without Replacement from a Finite Universe | 0.644 | 2 | 2 | 100% |
| 4 | Vershynin (2018) | 0.644 | 2 | 2 | 100% |
| 5 | Wald (1947) | 0.511 | 2 | 1 | 100% |
| 6 | Adusumilli (2024) Risk and Optimal Policies in Bandit Experiments | 0.405 | 1 | 1 | 100% |
| 7 | Ahrens, Chernozhukov, Hansen, Kozbur, Schaffer and Wiemann (2025) An Introduction to Double/Debiased Machine Learning | 0.405 | 1 | 1 | 100% |
| 8 | Athey and Wager (2021) Policy Learning With Observational Data | 0.405 | 1 | 1 | 100% |
| 9 | Bang and Robins (2005) Doubly Robust Estimation in Missing Data and Causal Inference Models | 0.405 | 1 | 1 | 100% |
| boyd2004ConvexOptimization | unmatched citation key boyd2004ConvexOptimization | 0.405 | 1 | 1 | 100% |
Showing the top 10 of 31 scored citations. 1 of these could not be matched to a bibliography entry, so only the citation key is shown.