Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
2,236,539 characters · 14 sections · 17 citation commands
Sequential Decision Problems with Missing Feedback
\addtocontents{toc}{\setcounter{tocdepth}{2}}
\thispagestyle{empty}
Keywords: sequential decision problems, double robustness, missing data
\onehalfspacing \setlength\abovedisplayskip{5pt} \setlength\belowdisplayskip{5pt} \setlength\parindent{0pt} {6pt}
\addtocontents{toc}{\setcounter{tocdepth}{0}}
In recent years, technological advancements and the proliferation of digital platforms have enabled the collection of real-time data describing the interaction between a policy and its targets. Such rich online datasets naturally give rise to sequential decision problems in which a decision-maker continuously re-optimizes the implemented policy as more information is gathered. Historically, these decision problems have been modeled as multi‐armed bandits \citep*{thompson1933LikelihoodThatOne, wald1947SequentialAnalysis, robbins1952AspectsSequentialDesign}, in which a decision-maker interactively learns the best policy (action) among a set of alternatives by trying out options and observing a signal (feedback or reward) from the environment.
Naturally, the success of these strategies requires the decision-maker to be able to observe some feedback following each action and, thus, to assess the extent to which the chosen action had the intended impact. However, in many real‐world settings, the environment’s response to a given policy might not always be observable, making it harder to gauge the true efficacy of an intervention. If this particular form of missing data is correlated with the outcome of interest, it introduces sampling bias \citep*{horvitz1952GeneralizationSamplingReplacement} and complicates the identification of optimal decision rules. Despite that, standard bandit algorithms typically rely on the assumption that rewards are always observed upon each action.
To make the problem more concrete, consider the case of a digital platform that experiments with user engagement strategies—such as personalized push notifications or in‐app promotions—and gauges satisfaction via voluntary review prompts. While some users may readily submit reviews, a non‐trivial fraction will opt out. Suppose the probability of response itself depends on satisfaction. In that case, reviews are observed only for a particular subpopulation, which may differ from the target one in many aspects, thus potentially inducing a suboptimal policy choice. Other real-life examples include a firm implementing different hiring strategies and a graduate admission committee experimenting with alternative types of offers.
In this paper, I first show that the popular $\mathsf{UCB}$ algorithm \citep*{auer2002FinitetimeAnalysisMultiarmed} maintains its optimal (up to logarithmic factor) worst-case regret rate of $\widetilde{O}(\mathpalette\DHLhksqrt{T})$ whenever the process that causes missing data is independent from rewards. Intuitively, in this case, rewards are missing completely at random \citep*{rubin1976InferenceMissingData}, hence reward-independent missingness only makes the learning process slower, without invalidating it. Nevertheless, this independence assumption is implausible in most practical scenarios where reward observability directly depends on the feedback itself. For example, customer satisfaction is typically surveyed only for extreme types, and different job postings attract different potential employees.
Whenever the process that causes missing data is reward-dependent, I show that the standard $\mathsf{UCB}$ algorithm may select suboptimal policies with probability approaching one as the number of trials grows. By explicitly modeling the dependence between rewards and the selection process through observable covariates, I develop a theoretically grounded, fully nonparametric procedure for sequential decision problems with missing feedback. The proposed algorithm achieves a worst-case regret rate of order $\widetilde{O}(\mathpalette\DHLhksqrt{T})$, which I show to coincide (up to logarithmic factors) with the rate of a novel lower bound on the minimax regret for the class of bandits with reward-dependent missingness. Additionally, the proposed method is doubly robust in the sense that only one among the conditional expectation of rewards and the conditional probability of missingness needs to be correctly specified for the algorithm to function properly. In this spirit, the algorithm's name is Doubly-Robust Upper Confidence Bound ($\mathsf{DR}$-$\mathsf{UCB}$).
Finally, to the best of my knowledge, this paper provides the first high-probability bounds for a doubly-robust estimator under very general conditions. Specifically, the high-probability bounds derived throughout rely on the theory for martingale difference sequences \citep*{freedman1975TailProbabilitiesMartingales}, and so allow for very general dependence structures in the data. This was necessary in this setting due to the technical challenges brought by the sequential nature of the problem.
Sequential decision-making problems under uncertainty have been extensively studied in economics, statistics, and computer science after the seminal work of wald1947SequentialAnalysis and have mostly focused on the design of optimal strategies and algorithms. Recent advances have particularly emphasized the role of adaptive algorithms that sequentially learn and adjust to uncertain environments, leading to a proliferation of approaches that efficiently balance exploration and exploitation; for a textbook introduction, see bubeck2012RegretAnalysisStochastic, lattimore2020BanditAlgorithms, and references therein.
This paper builds explicitly on the extensive literature studying the properties of the $\mathsf{UCB}$ algorithm. The idea of being optimistic in the face of uncertainty first appeared in lai1985AsymptoticallyEfficientAdaptive. lai1987AdaptiveTreatmentAllocation provided the first version of the $\mathsf{UCB}$ algorithm, whereas the $\mathsf{UCB}$ algorithm analyzed here is closer to the $\mathsf{UCB}1$ analyzed in auer2002FinitetimeAnalysisMultiarmed. UCB methods have been widely recognized for their effectiveness in handling exploration-exploitation trade-offs, providing provable performance guarantees and optimal regret bounds in multi-armed bandit frameworks.
The literature on multi-armed bandits with delayed feedback is also closely related to this project. Delayed feedback poses significant challenges for standard $\mathsf{UCB}$ algorithms, as the decision-maker is forced to take actions before she can receive any signal from the environment she is interacting with. The closest predecessor of this work is probably lancewicki2021StochasticMultiArmedBandits, where the authors provide problem-specific regret bounds for the Successive Elimination algorithm when rewards are bounded and delays are occasionally infinite and reward-dependent. Different from them, here I propose distribution-free worst-case regret bounds for a novel version of the $\mathsf{UCB}$ and allow rewards to be unbounded.
Finally, this paper intersects with the literature that relies on doubly-robust estimators for different goals, such as handling missing data \citep*{robins1994EstimationRegressionCoefficients, bang2005DoublyRobustEstimation}, estimating the causal impacts of policies \citep*{cattaneo2010EfficientSemiparametricEstimation, farrell2015RobustInferenceAverage, chernozhukov2018DoubleDebiasedMachine}, or to learn optimal policies in offline \citep*{athey2021PolicyLearningObservational} and online settings \citep*{kallus2022DoublyRobustDistributionally, shen2024DoublyRobustInterval}.
The paper is organized as follows. Section (ref) describes the problem and the algorithms used throughout. Section (ref) contains the main results and showcases the worst-case regret properties of the classical $\mathsf{UCB}$ algorithm and $\mathsf{DR}$-$\mathsf{UCB}$ in environments with reward-independent (Section (ref)) and reward-dependent (Section (ref)) missingness. Section (ref) illustrates some simulation evidence. Section (ref) concludes. The code replicating the simulation study is available at \url{https://github.com/filippopalomba/P_2025_banditMissing}.
For two positive sequences $\left\{a_n\right\}_n,\left\{b_n\right\}_n$, I write $a_n = O(b_n)$ if $\exists\,M\in\operatorname{\mathbb{R}}_{++}:a_n\leq M b_n$ for all large $n$, $a_n=o(b_n)$ if $\lim_{n\to\infty} a_n b_n^{-1} = 0$, $a_n=\widetilde{O}(b_n)$ if $\exists\, k\in\operatorname{\mathbb{N}},C\in\operatorname{\mathbb{R}}_{++}: a_n=O(b_n\ln^k(Cn))$ $a_n\lesssim b_n$ if there exists a constant $C\in\operatorname{\mathbb{R}}_{++}$ such that $a_n\leq C b_n$ for all large $n$, and $a_n \sim b_n$ if $a_n / b_n \rightarrow 1$ as $n \rightarrow \infty$. For two sequences of random variables $\left\{A_n\right\}_n,\left\{B_n\right\}_n$, I write $A_n=o_{\mathbb{P}}(B_n)$ if $\forall\,\varepsilon\in\operatorname{\mathbb{R}}_{++}, \lim_{n\to\infty} \mathbb{P}[|A_n B_n^{-1}|\geq \varepsilon]= 0$ and $A_n =O_{\mathbb{P}}(B_n)$ if $\forall\,\varepsilon\in\operatorname{\mathbb{R}}_{++}, \exists \,M,n_0\in\operatorname{\mathbb{R}}_{++} : \mathbb{P}[|A_nB_n^{-1}|>M]<\varepsilon,$ for $n>n_0$. I denote a (possibly multivariate) Gaussian random variable with $\mathsf{N}(\mathbf{a}, \mathbf{B}),$ where $\mathbf{a}$ denotes the mean and $\mathbf{B}$ the variance-covariance, with $\mathsf{Be}(p)$ a Bernoulli distribution with $p\in(0,1]$ denoting the success probability, with $\mathsf{sG}(\sigma)$ a sub-Gaussian random variable with proxy variance at most $\sigma>0$, and with $\mathcal{SG}(\sigma)$ the space of sub-Gaussian probability distribution with variance proxy at most $\sigma>0$. A random variable $X$ is sub-Gaussian with parameter $\sigma>0$ if $\forall\,\lambda\in\operatorname{\mathbb{R}},\operatorname{\mathbb{E}}[\exp(\lambda X)]\leq \exp(\lambda^2\sigma^2/2)$ and $\operatorname{\mathbb{E}}[X]=0$ \citep*[Definition 5.1 in][]{lattimore2020BanditAlgorithms}. If $\{X_t\}_{t=1}^\infty$ is an $\mathcal{F}$-adapted martingale difference sequence with respect to some filtration $\mathcal{F}=\{\mathcal{F}_t\}_{t=1}^\infty$, then it is understood that $X_t\sim \mathsf{sG}(\sigma^2)$ requires $\forall\,\lambda\in\operatorname{\mathbb{R}},\operatorname{\mathbb{E}}[\exp(\lambda X_t)\mid \mathcal{F}_t]\leq \exp(\lambda^2\sigma^2/2)$ and $\operatorname{\mathbb{E}}[X_t\mid\mathcal{F}_t]=0$. See also Table (ref) in the supplemental appendix for a summary of the project-specific notation.
I start by describing a generic instance of a stochastic multi-armed bandit (henceforth, MAB) with (possibly) missing rewards and the decision-maker that interacts with such an environment.
Setting. A decision-maker faces a sequential decision problem over $ T \in \operatorname{\mathbb{N}}$ rounds in a stochastic environment. At the beginning of each round $ t \in [T] $, using all the information available at that point, the decision-maker selects an action $ A_t \in \mathcal{A}:=\{1,\ldots,A\}$. Each action $ a \in \mathcal{A} $ is associated with a reward $ R_a \in\operatorname{\mathbb{R}}, R_a\sim \mathsf{sG}(\sigma_a), \sigma_a>0$, an indicator for not being missing $ C_a \in \{0,1\}$, and some covariates $\mathbf{X}_a \in\mathcal{X}\subseteq \operatorname{\mathbb{R}}^k,k\in\operatorname{\mathbb{N}}$. All random variables are independent across actions, i.e., $(R_{a},C_{a},\mathbf{X}_{a})\protect\mathpalette{\protect\independenT}{\perp} (R_{a'},C_{a'},\mathbf{X}_{a'})$ for $a\neq a', a, a'\in\mathcal{A}$. A stochastic MAB problem with missing rewards is defined as a collection of random variables $\{(R_{a,\ell},C_{a,\ell},\mathbf{X}_{a,\ell})\}_{a\in\mathcal{A},\ell\in[T]}$ where each $(R_{a,\ell},C_{a,\ell},\mathbf{X}_{a,\ell})$ is a random draw from $(R_{a},C_{a},\mathbf{X}_{a})$. The reward of action $a\in\mathcal{A}$ in round $t\in[T]$, denoted with $R_{a,t}$, is observed only if $C_{a,t}=1$. At this level of generality, the class of bandits considered is \[\mathcal{C}:=\left\{(\nu_a)_{a\in\mathcal{A}}: \nu^{[R]}_a \in \mathcal{SG}(\sigma_a), \: \nu_a^{[C]} = \mathsf{Be}(q_a), q_a\in(0,1] \right\},\] where $\nu^{[Y]}_a$ is the marginal distribution of $Y\in\{R,C\}$. Finally, I define $\bar{\sigma}:= \mathpalette\DHLhksqrt{\max_{a\in\mathcal{A}}\sigma_a^2}$ and $\underline{q} = \min_{a\in\mathcal{A}}q_a$.
\paragraph{Decision-maker.} Each decision-maker is characterized by a policy that maps \newline $\{(A_\ell, R_{A_\ell,\ell}, C_{A_\ell,\ell}, \mathbf{X}_{A_\ell,\ell}^\top)\}_{\ell\in[t-1]}$, the history up to the beginning of round $t$, to the space of probability distributions over actions $\Delta(\mathcal{A})$. Denote the space of policies as $$\Pi:=\left\{\pi: \pi = \{\pi_t\}_{t\in[T]}, \pi_t: (\mathcal{A} \times \operatorname{\mathbb{R}} \times \{0,1\}\times\mathcal{X})^{t-1} \to \Delta(\mathcal{A})\right\}.$$ I use interchangeably the words “decision-maker", “algorithm", and “policy" when referring to a generic element $\pi\in\Pi$. Protocol (ref) describes the interaction between a decision-maker and a MAB with (possibly) missing feedback.
\paragraph{Regret.} The pseudo-regret of a decision-maker following a policy $\pi$ in a MAB with missing rewards $\nu\in\mathcal{C}$ is \[\mathsf{Regret}_T(\pi; \nu) =\sum_{t=1}^T (\max_{a\in\mathcal{A}}\theta_a - \operatorname{\mathbb{E}}_\nu[R_{A_t,t}]) = T\overline{\theta} - \sum_{t=1}^T \theta_{A_t},\] which depends on $\nu$ via the average rewards and it is a random quantity because the $\{A_t\}_{t\in[T]}$ are random. Note that the latter is true even if the policies considered are deterministic. The reason is that $A_t$ depends on the history, which is random. Furthermore, the regret depends on $R_{A_t,t}$ independently of whether the rewards have been observed. In what follows, I omit the dependence of the regret on $\nu$ and simply write $\mathsf{Regret}_T(\pi)$.
\paragraph{Goal.} The decision-maker's goal is to find a policy $\pi$ with good worst-case regret properties. Formally, the decision-maker seeks to find a policy $\pi$ whose worst-case regret $\overline{\mathsf{Regret}_T}({\pi};\mathcal{C}):=\sup_{\nu\in{\mathcal{C}}} \mathsf{Regret}_T({\pi};\nu)$ has the nearly optimal rate $\widetilde{O}(\mathpalette\DHLhksqrt{T})$. In what follows next, I will not directly optimize the worst case regret over the space of policy $\Pi$ (see adusumilli2024RiskOptimalPolicies for an example of such an approach in a standard MAB). Rather, I first derive a lower bound for the minimax regret \[\mathsf{Regret}_T^\star(\mathcal{C}) := \inf_{\pi\in\Pi}\overline{\mathsf{Regret}_T}({\pi};\mathcal{C}).\] Then, I derive an upper bound for the worst-case regret $\overline{\mathsf{Regret}_T}(\widetilde{\pi};\mathcal{C})$ of some specific policy $\widetilde{\pi}$ and, finally, I check that the rates of the two bounds coincide. In what follows, I focus on the popular $\mathsf{UCB}$ algorithm \citep*{auer2002FinitetimeAnalysisMultiarmed} and a novel, doubly-robust modification of it as the algorithms used by the decision-maker to form her policy.
The $\mathsf{UCB}$ algorithm selects the action to be played by solving an exploitation-exploration trade-off. Indeed, the algorithm desires to explore new actions, but, since playing a sub-optimal action induces regret, it also wants to exploit what is already known about the environment. On the one hand, too little exploration might make a sub-optimal alternative look better than the optimal one because of random fluctuations. On the other hand, too much exploration prevents the algorithm from playing the optimal alternative often enough, which also results in a larger regret.
Let $\hat{\theta}_{a}(t)$ be an estimator for $\theta_a$ after $t-1$ rounds and denote with $b_{a,t}(\delta)$ a bonus term chosen so that $\theta_a \in [\hat{\theta}_{a}(t) - b_{a,t}(\delta), \hat{\theta}_{a}(t) + b_{a,t}(\delta)]$ with probability at least $1-\delta$. The $\mathsf{UCB}$ algorithm selects the action $a^\star$ at round $t$ that has the highest optimistic mean reward estimate, i.e. \[a^\star = \operatorname*{arg\,max}_{a\in\mathcal{A}}\hat{\theta}_{a}(t) + b_{a,t}(\delta).\] As such, an action $a\in\mathcal{A}$ can be chosen for two different reasons: because $b_{a,t}(\delta)$ is large, implying that the estimate $\hat{\theta}_{a}(t)$ is noisy (explorative choice); or because $\hat{\theta}_{a}(t)$ is large (exploitative choice). Since the bonus term $b_{a,t}(\delta)$ is constructed to shrink quickly each time alternative $a$ is selected, exploration becomes less frequent over time. When $b_{a,t}(\delta)$ is sufficiently small, the estimated value $\hat{\theta}_{a}(t)$ closely approximates the true parameter $\theta_a$, assuming that $\hat{\theta}_{a}(t)$ is a “good" estimator for $\theta_a$. Consequently, $\mathsf{UCB}$ naturally balances between exploration and exploitation.
Before describing in great detail the algorithms, let \[P_a(t) := \sum_{\ell=1}^{t-1}\mathbbm{1}[A_\ell=a], \quad\text{and}\quad N_a(t) := \sum_{\ell=1}^{t-1}\mathbbm{1}[A_\ell=a] C_{a,\ell}\] be the number of times an arm $a\in\mathcal{A}$ has been pulled and the number of times the reward $R_a$ has been observed at the beginning of round $t\in[T]$, respectively.
The (regularized) estimate for $\theta_a, a\in\mathcal{A}$ at the beginning of round $t\in[T]$ is
where $\lambda>0$ is a regularization parameter that prevents the estimator from being ill-defined whenever, after initialization, it occurs that $N_a(t)=0$ for some $a\in\mathcal{A}$ and $t\geq 1$ (see also Remark (ref)). The optimistic mean reward estimate of action $a\in\mathcal{A}$ after $t\in[T]$ rounds is \[\widetilde{R}^{\mathsf{UCB}}_a(t,\delta) = \widehat{R}^{\mathsf{UCB}}_a(t) + b^{\mathsf{UCB}}_{a,t}(\delta), \] where the “bonus" term $b^{\mathsf{UCB}}_{a,t}(\delta)$ is chosen to make sure that the optimistic mean reward estimate $\widetilde{R}^{\mathsf{UCB}}_a(t,\delta)$ upper bounds the true mean reward $\theta_a$ with high probability. In this specific case, I define \[b^{\mathsf{UCB}}_{a,t}(\delta) := \frac{\bar{\sigma}}{\underline{q}_\lambda}\mathpalette\DHLhksqrt{\frac{2\ln(2AT/\delta)}{ P_a(t) +\lambda}}+\frac{\lambda\overline{K}}{N_a(t)+\lambda},\] where $\overline{K}$ is some constant larger than $\overline{\theta}, \underline{q}_\lambda:=\inf_{a,t}\frac{N_a(t) + \lambda}{P_a(t) + \lambda}$, and $\delta\in(0,1)$. Intuitively, the first term in $b^{\mathsf{UCB}}_{a,t}(\delta)$ governs the probability with which the optimistic estimate overestimates the mean reward, whereas the second term takes into account the bias induced by the regularization term $\lambda > 0$. Under reward-independent missingness (Assumption (ref) below), Lemma (ref) in the supplemental appendix formally justifies the particular choice of $b^{\mathsf{UCB}}_{a,t}(\delta)$ described above by showing that \[\forall\,a\in\mathcal{A},t\in[T],\quad \theta_a \in \left[\widehat{R}^{\mathsf{UCB}}_a(t) - b^{\mathsf{UCB}}_{a,t}(\delta),\widehat{R}^{\mathsf{UCB}}_a(t) + b^{\mathsf{UCB}}_{a,t}(\delta)\right]\] holds with probability at least $1-\delta$.
The way the $\mathsf{UCB}$ algorithm works is straightforward: at round $t \in[T]$, it selects the arm $a$ that has the highest optimistic mean reward estimate. Algorithm (ref) below summarizes all the steps needed by the classic $\mathsf{UCB}$ algorithm.
Let the true conditional mean reward and probability of not being missing for arm $a\in\mathcal{A}$ as \[\theta_a(\mathbf{X}_a) := \operatorname{\mathbb{E}}_\nu[R_{a}\mid \mathbf{X}_a], \qquad q_a(\mathbf{X}_a) = \operatorname{\mathbb{E}}_\nu[C_a\mid \mathbf{X}_a]\in[\underline{q}, 1]\] almost surely, and denote with $\hat{\theta}_a(\cdot)$ and $\hat{q}_a(\cdot)$ their estimated counterparts. Throughout, I use interchangeably the terms “probability of rewards not being missing" and “probability of missingness". The doubly-robust estimator for mean rewards is defined as \[ \widehat{R}^{\mathsf{DR}}_a(t) := \frac{1}{P_a(t)} \sum_{\ell=1}^{t-1}\mathbbm{1}[A_\ell=a] \left(\frac{C_{a,\ell}(R_{a,\ell} - \hat{\theta}_a(\mathbf{X}_{a,\ell}))}{\hat{q}_a(\mathbf{X}_{a,\ell})} + \hat{\theta}_a(\mathbf{X}_{a,\ell})\right).\]
The optimistic mean reward estimator for $\mathsf{DR}$-$\mathsf{UCB}$ is defined as
where $K_{\mathsf{ODR}} := \frac{\bar{\sigma}}{\underline{q}} + \bar{\sigma}$ and $b_{a,t}^{\mathsf{res}}(\delta)$ is defined precisely in Section (ref) of the supplemental appendix. Under a reward-dependent process that causes missing data (Assumption (ref) below), Lemma (ref) in the supplemental appendix thoroughly justifies the choice of $b^{\mathsf{DR}}_{a,t}(\delta)$ as a bonus term and proves that \[\forall\,a\in\mathcal{A},t\in[T],\quad \theta_a \in \left[\widehat{R}^{\mathsf{DR}}_a(t) - b^{\mathsf{DR}}_{a,t}(\delta),\widehat{R}^{\mathsf{DR}}_a(t) + b^{\mathsf{DR}}_{a,t}(\delta)\right]\] holds with probability at least $1-\delta$.
Finally, Algorithm (ref) describes in greater detail how the $\mathsf{DR}$-$\mathsf{UCB}$ algorithm works.
In Section (ref), I begin by analyzing the performance of the $\mathsf{UCB}$ algorithm under the assumption that the process that causes missing data does not depend on rewards (Assumption (ref)). In Section (ref), I then show that, when the previous assumption is relaxed to allow for reward-dependent missingness (Assumption (ref)), the $\mathsf{UCB}$ algorithm can suffer from linear regret, whereas $\mathsf{DR}$-$\mathsf{UCB}$ achieves sub-linear worst-case regret. In Section (ref), I present a lower bound for the minimax regret. Finally, in Section (ref), I conclude by giving some practical advice on how to implement $\mathsf{DR}$-$\mathsf{UCB}$.
I begin by considering the scenario where rewards are missing at random, as formalized in Assumption (ref). Additionally, rewards are assumed to be sub-Gaussian, a common condition that constrains their tail behavior and enables the use of standard concentration inequalities; see vershynin2018HighDimensionalProbabilityIntroduction and wainwright2019HighDimensionalStatisticsNonAsymptotic for an introduction.
Under Assumption (ref), the class of bandits of interest is restricted to \[\mathcal{C}_1:=\left\{(\nu_a)_{a\in\mathcal{A}}: \nu^{[R]}_a\in\mathcal{SG}(\sigma_a), \:\:\nu_a^{[C]}= \mathsf{Be}(q_a), q_a\in(0,1],\:\: \nu_a = \nu^{[R]}_a\cdot \nu^{[C]}_a \right\}\subset \mathcal{C}.\]
The paper’s first main result establishes that the $\mathsf{UCB}$ algorithm achieves a near-optimal worst-case regret rate over the class of bandits $\mathcal{C}_1$. The proof of such a result follows using standard arguments. Namely, I consider a “good" event and show that it occurs with high probability in the setting considered throughout. In this spirit, define such an event as $$\mathcal{G}(\delta_1,\delta_2) = \overline{\mathcal{F}^{\mathsf{UCB}}(\delta_1)} \cap \overline{\mathcal{F}^{\mathsf{MIS}}(\delta_2)},$$ for some $\delta_1,\delta_2\in(0,1)$, where
where $\underline{T}_a:= 1+\frac{24\ln(T)}{q_a}$. Under the good event, which realizes with probability at least $1-\delta_1-\delta_2$, it holds that: (i) for each action, the optimistic reward estimator always covers the true mean; (ii) after a minimum amount of pulls $\underline{T}_a$, the missing data mechanism is not too extreme in terms of percentage deviation from its mean.
In the supplemental appendix, Lemma (ref) and Lemma (ref) show that $\mathcal{F}^\mathsf{UCB}(\delta_1)$ and $\mathcal{F}^\mathsf{MIS}(\delta_2)$ occur with arbitrarily small probability. Then, under the good event $\mathcal{G}(\delta_1,\delta_2)$, it is possible to bound the worst case regret of $\mathsf{UCB}$ uniformly over bandits in $\mathcal{C}_1$ and horizons $T\in\operatorname{\mathbb{N}}$. This result is presented formally in the next theorem and proven in the supplemental appendix.
The previous section showed that, under the assumption that the process that causes missing data does not depend on rewards, the $\mathsf{UCB}$ algorithm has nearly-optimal regret. However, this independence assumption is hard to defend in practical applications. Borrowing from the program evaluation literature, I relax Assumption (ref) and, instead, rely on a conditional ignorability assumption (CIA), which states that independence holds only conditional on the vector of covariates $\mathbf{X}_a$ \citep*{rosenbaum1983CentralRolePropensity}.\footnote{This is a standard assumption in the causal inference literature. I refer the interested reader to imbens2004NonparametricEstimationAverage and Chapter 21 in wooldridge2010EconometricAnalysisCross for thorough discussions of the plausibility of such an assumption in various contexts.} Put differently, the CIA imposes that knowledge of $\mathbf{X}_a$ is sufficient to break the dependence between rewards and the missing data mechanism in each arm.
The CIA can be expressed in two ways: by imposing some structure on the conditional expectation of $C_a$ (so-called design-based approach); by imposing some structure on the conditional expectation of $R_a$ (so-called model-based approach). Depending on the specific application, either version of the CIA might be more appealing. The next assumption formalizes this idea.
On top of the CIA, Assumption (ref) requires sub-Gaussianity of rewards only conditional on $\mathbf{X}_a$ and has two other mild requirements: (i) the conditional expectation of each $R_a$ is uniformly bounded over $\mathcal{X}$; (ii) the probability of observing rewards is non-zero ($q_a>0$). Hence, the class of bandits considered throughout is \[\mathcal{C}_2:=\left\{\nu=(\nu_a)_{a\in\mathcal{A}}: \nu_a^{[C]} = \mathsf{Be}(q_a), q_a\in(0,1], \text{ and Assumption \ref{assump: conditional ignorability main} holds} \right\}\subset \mathcal{C}.\]
In this framework, it is well-known that the mean-reward estimator defined in (ref) is not consistent anymore for $\theta_a$ \citep*{horvitz1952GeneralizationSamplingReplacement}. Even more worryingly, the estimators $\widehat{R}^{\mathsf{UCB}}_a(t), a\in\mathcal{A}$ might have probability limits $\widetilde{\theta}_a$ such that \[\operatorname*{arg\,max}_{a\in\mathcal{A}}\widetilde{\theta}_a \neq \operatorname*{arg\,max}_{a\in\mathcal{A}}{\theta}_a,\] so that even after a large number of rounds $T$, the $\mathsf{UCB}$ algorithm will not learn the best arm. Section (ref) of the supplemental appendix shows an example of a bandit in $\mathcal{C}_2$ such that this realizes.
Assumption (ref) ensures that $\theta_a$ can be identified from the data had the nuisance functions $\{\theta_a(\cdot),q_a(\cdot), a\in\mathcal{A}\}$ been known. However, in practice, these nuisances need to be estimated, and extra care is required in doing so. Before elucidating how nuisance estimation should be conducted, define the following $\ell_2$-estimation errors for each $a\in\mathcal{A}$
and
for some known $\widetilde{q}_a(\mathbf{x})$ and $\widetilde{\theta}_a(\mathbf{x})$.
Assumption (ref) precisely states all the requirements the nuisance estimators have to satisfy; see also Section (ref) for two examples of practical procedures that satisfy Assumption (ref).
First, Assumption (ref) requires one between the true conditional probability of missingness, $q_a(\cdot)$, and the true conditional expectation of rewards, $\theta_a(\cdot)$, to be the probability limit of one of the nuisance estimators, $\hat{\theta}_a(\cdot)$ and $\hat{q}_a(\cdot)$. In other words, it suffices to have well-specified only one of the two conditional expectations. Second, Assumption (ref) bounds the estimated probability of (not) being missing away from 0, a typical regularity condition in such problems. Third, to avoid over-fitting bias, Assumption (ref) asks the nuisance functions to be estimated in an independent (conditional on $\mathbf{X}_a$) sample. Fourth, (ref) controls the estimation error of the nuisance estimators in two ways: (i) the estimation error of each nuisance need to be shrinking in $P_a(t)$; (ii) the product of the estimation errors must decay faster than $1/\mathpalette\DHLhksqrt{P_a(t)}$. These conditions make the sampling error dominate the estimation error induced by the fact that $\{(\theta_a(\cdot),q_a(\cdot)),a\in\mathcal{A}\}$ are estimated.
Assumption (ref) is fundamental to make the term $b_{a,t}^{\mathsf{res}}(\delta)$ of higher order in the bonus term $b_{a,t}^\mathsf{DR}(\delta)$ defined in (ref). Formally, under such an assumption, it follows that $b_{a,t}^{\mathsf{res}}(\delta)=o_{\mathbb{P}}(1/\mathpalette\DHLhksqrt{P_a(t)})$ and the next lemma follows.
The above result shows that the bonus term for the $\mathsf{DR}$-$\mathsf{UCB}$ algorithm has been chosen appropriately in the sense that it controls the probability with which $\widehat{R}^{\mathsf{DR}}_a(t)$ deviates from $\theta_a$. This result is of independent interest as it is the first one that provides high-probability bounds for a doubly-robust estimator under mild assumptions; see Lemma (ref) in the supplemental appendix for a formal statement, a proof of the result, and some heuristics on the logic behind the strategy used in the proof.
To provide a bound on the worst-case regret over the class $\mathcal{C}_2$, a similar strategy to the one used in Section (ref) is adopted. Define the failure event \[\mathcal{F}^{\mathsf{DR}}(\delta) := \left\{\exists\,a\in\mathcal{A},t\in[T],\left| \widehat{R}^{\mathsf{DR}}_a(t) - \theta_a\right|\geq b_{a,t}^\mathsf{DR}(\delta)\right\}.\] When $\mathcal{F}^{\mathsf{DR}}(\delta)$ occurs the optimistic doubly-robust reward estimator $\widetilde{R}_a^{\mathsf{DR}}(t) = \widehat{R}_a^{\mathsf{DR}}(t) + b_{a,t}^{\mathsf{DR}}(t)$ does not cover the true mean reward $\theta_a$. Using Lemma (ref), it is immediate to see that $\mathbb{P}[\mathcal{F}^{\mathsf{DR}}(\delta)]\leq \delta$ for some $\delta\in(0,1)$. The next theorem shows that the regret of the $\mathsf{DR}$-$\mathsf{UCB}$ algorithm is nearly optimal (up to logarithmic factors) and provides an upper bound that holds with high probability uniformly over the horizon $T$ and the class of bandits $\mathcal{C}_2$.
Comparing Theorem (ref) with Theorem (ref), it is possible to see that the leading order terms of the worst case regret bound are identical. Indeed, Assumption (ref) is crucial in granting that the uncertainty due to the estimation of the nuisance functions is dominated by the one due to sampling error; see the supplemental appendix for a formal proof and additional heuristics to foster intuition for this result.
In this section, I show that the minimax regret \[\mathsf{Regret}_T^\star(\mathcal{C}_j) := \inf_{\pi\in\Pi}\sup_{\nu\in\mathcal{C}_j} \mathsf{Regret}_T(\pi;\nu), \:j\in\{1,2\}\] is lower bounded by a constant times a factor of $\mathpalette\DHLhksqrt{T}$.
The logic of the proof is similar to that behind classic lower bound results obtained via Le Cam's two-point lemma. In particular, a generic policy $\tilde{\pi}\in\Pi$ is considered and its regret on two particular instances $\nu,\nu'\in\mathcal{C}$ is lower-bounded, where $\mathcal{C}$ is some class of bandits. Then, it follows that \[\sup_{\tilde{\nu}\in\mathcal{C}}\mathsf{Regret}_T(\tilde{\pi};\tilde{\nu}) \geq \max\{\mathsf{Regret}_T(\tilde{\pi},\nu), \mathsf{Regret}_T(\tilde{\pi},\nu')\}\geq f(T),\] for some function $f(\cdot)$. Because the policy $\tilde{\pi}$ was generic, then the bound above holds for any policy in $\Pi$, hence \[\mathsf{Regret}_T^\star(\mathcal{C}) = \inf_{\pi\in\Pi}\sup_{{\nu}\in\mathcal{C}}\mathsf{Regret}_T({\pi};{\nu})\geq f(T).\]
In particular, to get a lower bound for the minimax regret over the classes of bandits $\mathcal{C}_1$ and $\mathcal{C}_2$, I derive a lower bound for the minimax regret for the classes of Gaussian bandits \[\mathcal{C}_1^{\mathtt{gau}} := \{(\nu_a)_{a\in\mathcal{A}}: \nu_a^{[R]}=\mathsf{N}(\theta_a, 1), \nu_a^{[C]}=\mathsf{Be}(q_a),q_a\in(0,1]\}\subset \mathcal{C}_1\] and
Because the “sup" of the minimax is taken over a smaller subset, the minimax bound for Gaussian bandits extends immediately to the classes of sub-Gaussian bandits $\mathcal{C}_1$ and $\mathcal{C}_2$. A textbook example can be found in lattimore2020BanditAlgorithms, Chapter 15, and the proof of Theorem (ref) is almost identical to that of Theorem 15.2 in $\mathsf{LS}$ and, indeed, the bound is identical.
The near-optimality of $\mathsf{DR}$-$\mathsf{UCB}$ hinges on having nuisance estimators $\hat{\theta}_a(\cdot)$ and $\hat{q}_a(\cdot)$ that satisfy Assumption (ref). In what follows, I give two examples of classes of estimators that satisfy the conditions in Assumption (ref) and give practical advice for implementation.
First, I start by highlighting a classical trade-off between Assumptions (ref) and (ref): relying on flexible nonparametric estimators makes Assumption (ref) more likely to be satisfied than when parametric estimators are used; however, nonparametric estimators typically have slower convergence rates than their parametric competitors, thus making (ref) harder to be satisfied. As an instance, machine learning methods --such as lasso, ridge, random forests, neural networks-- can be used to estimate the nuisances $\{(\theta_a(\cdot), q_a(\cdot)),a\in\mathcal{A}\}$, as long as their convergence rate (or $\ell_2$ error bounds) decay at a faster rate than $1/\mathpalette\DHLhksqrt{P_a(T)}$. For some real-life applications and discussions of the feasibility of these methods, see ahrens2025IntroductionDoubleDebiased.
I now turn to Assumption (ref), but before discussing it, it is necessary to introduce some notation. Define the main estimation dataset as \[\mathcal{D}_{\mathtt{main}}^T:=\left\{\mathbf{Z}_\ell, \ell \in[T]\right\},\qquad \mathbf{Z}_j:=(R_{A_j,j}, C_{A_j,j}, \mathbf{X}_{A_j,j}^\top)^\top.\] Appropriate nuisance estimators $\hat{\theta}_a$ and $\hat{q}_a$ that satisfy Assumption (ref) can be constructed in (at least) two ways:
As a final remark, I stress that in virtue of approaches such as M2, I should be writing $\hat{\theta}^{(\ell)}_a$ and $\hat{q}^{(\ell)}_a$ for each round $\ell\in[T]$. I avoid doing so to save notation, but it is maintained that the nuisance estimators are allowed to be updated with the rounds.
Third, the estimated conditional probability of missingness needs to be bounded between $\underline{q}$ and 1 to avoid dealing with “small denominators", i.e., when some of the $\hat{q}_a$'s are close to 0. Various alternatives exist in the literature: crump2009DealingLimitedOverlap proposes a data-driven trimming procedure that minimizes the variance of the estimator, and it is optimal under homoskedasticity (see khan2025DoublyRobustHeteroscedasticityaware for a recent extension to the heteroskedastic case); ma2020RobustInferenceUsing warn against ad hoc trimming and propose a data-driven procedure that minimizes the asymptotic mean squared error of the resulting estimator. I stress that, while these procedures have been extensively validated via simulations, they rely on asymptotic guarantees and should therefore be applied with caution in finite-sample settings such as the one analyzed here.
In this section, I present simulation results for the performance of the algorithms discussed. In the simulation, for each $a\in\mathcal{A}$, I model $X_{a,j} \overset{\mathrm{iid}}{\sim} \mathsf{N}(0,1), j=1,\ldots, d, u_{a,j}\overset{\mathrm{iid}}{\sim} \mathsf{N}(0,\sigma_j^2),j\in\{C,R\},$ and define \[C_a = \mathbbm{1}\left[\sum_{\ell=1}^dX_{a,\ell} \beta_\ell+u_{a,C}>\tau(q_a)\right], \quad R_a = \theta_a + \sum_{\ell=1}^d X_{a,\ell}\beta_\ell + u_{a,R},\] where $\boldsymbol{\beta}:=(\beta_1,\ldots,\beta_d)^\top\in\operatorname{\mathbb{R}}_{++}$ and $\tau(q_a): \mathbb{P}[\sum_{\ell=1}^dX_{a,\ell} \beta_\ell+u_{a,C}>\tau(q_a)] = q_a.$ Note that \[R_a\sim\mathsf{N}(\theta,d+\sigma_R^2), \qquad C_a\sim \mathsf{Be}(q_a),\qquad C_a\protect\mathpalette{\protect\independenT}{\perp} R_a \mid \mathbf{X}_a.\]
I then set $A=2, T=5000, d=1,$ and consider three different scenarios: no missing data; reward-independent missingness; and reward-dependent missingness. Table (ref) reports the most important characteristics of these scenarios, which are the true mean rewards $(\theta_1,\theta_2)$, the probability limit of the mean reward estimator that uses only observed rewards $(\widetilde{\theta}_1,\widetilde{\theta}_2)$, and the probability of missingness. More details about the simulation, estimation of nuisance functions, and parametrization can be found in the supplemental appendix Section (ref).
In the first two scenarios, there is no wedge between the probability limits $(\widetilde{\theta}_1,\widetilde{\theta}_2)$ and the true mean reward, suggesting that the $\mathsf{UCB}$ algorithm would work fine. This is exactly what can be deduced from Figure (ref) and Figure (ref).
The left panel of those figures shows the instance-specific regret of the $\mathsf{UCB}$ algorithm, which exhibits the classical logarithmic shape in the number of rounds. As a benchmark, the performance of $\mathsf{UCB}$ is compared with an oracle version of the algorithm, which does not rely on the optimistic mean reward estimator $\widetilde{R}^{\mathsf{UCB}}_a(t;\delta)$, but rather on a confidence interval constructed as if the data-generating process was known. The right panel of Figure (ref) and Figure (ref) portrays the probability with which each algorithm selects the optimal arm $a^\star=2$ and shows that it approaches one as the number of rounds grows large. Notably, there is not much of a difference between scenario 1 and scenario 2. The only exception is that $\mathsf{UCB}$ needs more rounds to discover the optimal arm, consistent with the fact that rewards are not observed at all rounds.