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.
100,544 characters · 24 sections · 53 citation commands
Policy Learning with Adaptively Collected Data
The growing availability of user-specific data has welcomed the exciting era of personalized decision making, a paradigm that exploits the heterogeneity in a given population so as to provide individualized service decisions that lead to improved outcomes. This paradigm has found applications in a wide variety of operations management domains. For instance, in healthcare, using electronic medical records, doctors can better prescribe heterogeneous treatments---different types of drugs/therapies or different dosage levels of the same drug---to different patients based on their medical characteristics murphy2003optimal,kim2011battle,bertsimas2017personalized,fukuoka2018objectively. In advertising charles2013counterfactual,kallus2016dynamic,schnabel2016recommendations,farias2019learning,bastani2021predicting, using the recorded clientele information, the retailer can send more targeted product promotions---either in mail or online---to different existing and potential customers. In news recommendation li2010contextual,li2011unbiased,zeng2016online,karimi2018news,schnabel2019shaping,lee2020news,schnabel2020impact, the content provider may stream different news articles and/or media content to users with different digital footprints and perceived interests. In online education mandel2014offline,lan2016contextual,hoiles2016bounded,bassen2020reinforcement, an institution may want to offer different education plans to different students based on their varied learning styles (visual learner v.s. aural learner v.s. verbal learner, etc.).
A key problem in achieving intelligent personalization through data lies in learning an effective policy (which maps individual characteristics to treatments/actions) in a sample-efficient manner (i.e., making the fullest use of a given dataset so as to learn---to the extent possible---a policy that yields the highest rewards and hence leading to the best outcome for each individual). Particular challenges arise for off-policy evaluation due to missing counterfactual outcomes. Researchers from a variety of fields---including operations research, statistics and machine learning---have devoted extensive efforts to this problem in recent years dudik2011doubly,zhang2012estimating,zhao2015doubly,swaminathan2015batch,swaminathan2015counterfactual,swaminathan2015self,swaminathan2016off,kitagawa2018should,levine2020offline,kallus2018confounding,zhou2022offline,joachims2018deep,chernozhukov2019semi,su2019cab,bennett2020efficient,sachdeva2020off,jin2020pessimism,athey2021policy and satisfactorily addressed (discussed in more detail in Section (ref)) various aspects of the policy learning problem when the underlying historical data has been collected with a fixed exploration policy, which results in independent and identically distributed (i.i.d.) data over time. This is an important setting that includes several data-collection mechanisms: A/B testing, randomized control trials, and deploying a fixed operational policy that has built-in randomization.
However, much less is known on this problem when data is collected adaptively, that is, where the policy used to select actions evolves over time in response to observed outcomes rather than stays fixed. The following two broad categories of adaptive data collection are common in practice:
Policy learning using adaptively collected data is much more difficult, since there are complex intertemporal dependencies. To see this, suppose we have observational data $\{(X_t, W_t, Y_t)\}_{t=1}^T$ collected sequentially, where $X_t\stackrel{\textnormal{\textbf{i.i.d.}}}{\sim}P_X$ is the context, $W_t\in\operatorname{\mathcal{W}}=\{1,\dots, K\}$ is the selected action, and $Y_t=\mu(X_t;W_t)+\epsilon_t$ is the outcome, with $\{\epsilon_t\}_{t=1}^T$ being i.i.d. zero-mean random variables. Importantly, the samples $\{(X_t, W_t, Y_t)\}_{t=1}^T$ are not i.i.d. since $W_t$ is sampled according to probabilities $\big(e_t(X_t; 1), \dots, e_t(X_t; K)\big)$---also known as propensity scores---that are time-varying and dependent on past observations $\{(X_s, W_s, Y_s)\}_{s=1}^{t-1}$. Note that $e_t$ is the (randomized) policy used at $t$ while data was being collected. In practice, these $e_t$ functions may be derived from complicated functions with a large number of parameters (e.g., neural networks) and are quickly and constantly updated (e.g., ads serving engines), hence making it cumbersome to record those policies in their entirety. Consequently, in reflecting this constraint, we assume that only $e_t(X_t, W_t)$---the probability of sampling the chosen action $W_t$ at $t$---is recorded for each $t$, but not the entire function $e_t(\cdot\,;\, \cdot)$\footnote{Nevertheless, in our proposal we require the knowledge of $e_t(X_t, W_t)$ instead of estimating it from the data, which may be difficult in adaptive experiments since $e_t$ can be time-varying.}.
With a dataset of the form described above, the goal of policy learning is to select a good policy from a given policy class. A policy $\pi$---mapping from contexts to actions---can be evaluated by its policy value $Q(\pi)=\mathbb{E} \big[\mu(X, \pi(X))\big]$, where the expectation is taken with respect to the randomness in $X$ over the target population. To perform effective policy learning, one needs to select a policy with as large value as possible, or equivalently, as small regret as possible, where regret is defined to be the policy value loss relative to the best value in the policy class. An effective policy learning algorithm should achieve a small regret as a function of a given finite $T$, the quantitative measure of the algorithm's sample complexity. However, a moment of thought reveals that this is a challenging desideratum for the following three reasons.
First, unlike in fixed policy data collection where the propensities $e(\cdot \, ;\, \cdot)$ do not change over time (corresponding to a constant exploration bandwidth), a distinct feature in adaptive collection (when carried out by popular algorithms used in practice) is that $e_t(\cdot \,;\, \cdot)$ shrinks and goes to $0$ over time for certain actions (and contexts). This means that exploration is gradually reduced, thereby resulting in vanishing probabilities of selecting certain (poorly performing) actions. This crucial benefit of adaptive experiments---that poor arms can be dropped, while good arms are more likely to be pulled---creates difficulty for offline policy learning, a purely exploitation task. This is because the data not only have selection bias (as is already present in the fixed policy setting), but also become increasingly more so overtime, thereby producing skewed data that makes it difficult to compare the quality (i.e., the outcome) of alternative actions under a given context.
Second, although one might be tempted to think that smaller propensities (particularly towards the end of data-collection) indicate that certain actions are “clearly bad" as a result of their vanishing probabilities being selected, it is important to keep in mind that the policy learner does not have access to the propensity functions $e_t(\cdot\,;\, \cdot)$ and hence cannot perform this “action elimination" type of policy learning. Consequently, when observing that $e_T(X_T; W_T)$ is small on the last timestep $T$ and---assuming that we are confident that the adaptive data collection process is well-designed and can hence conclude that the action $W_T$ is indeed the wrong action for $X_T$---we would still not be able to know what other actions are wrong for $X_T$, nor what other contexts are bad for $W_T$. Further, since we only observe a single data point $e_t(X_t, W_t)$ for the propensity function $e_t(\cdot\,;\,\cdot)$, there is no hope to learn these evolving $e_t(\cdot \,;\, \cdot)$'s, a clear distinction from the fixed policy setting where one can learn the fixed propensity function $e(\cdot \,;\, \cdot)$ using the entire training dataset that it has generated.
Third, an adaptive data collection mechanism may itself be “poorly" designed and hence result in wrong propensities: $e_t(x,w)$ is small when $w$ is in fact the best action for context $x$. This “poor" design can arise for different reasons; for instance, it could be that an ineffective adaptive exploration scheme is used, \textcolor{black}{resulting in over-exploiting certain actions and under-exploring others}. Since contextual bandits rely on learning a complex outcome surface $\mu(\cdot,w)$ for each action $w$, most commonly used algorithms rely on specifying and estimating a parametric model for $\mu$, making misspecification a real possibility. Alternatively, it could be that the data were collected to answer a specific inferential question and hence the data-collection process was steered towards a particular direction. Regardless of the cause, when this occurs, the policy learner will see very few samples on the good actions but many samples on the bad actions, in effect reducing the overall useful samples and yielding larger uncertainty about which action is actually good for which context. This is a risk that the policy learner should address, because it has no control over what the data-collector does in collecting the data.\footnote{If the policy learner also plays the role of collecting data, it should instead focus on adaptive experimental design or online adaptive learning, rather than offline policy learning, although there are scenarios where the data-collector has multiple objectives and thus does not optimize for policy learning during the experiment.} Hence, policy learning methods should be robust to a wide class of adaptive data-collection mechanisms, good or bad from the policy learner's own perspective.
Situated in this challenging and under-explored landscape, we aim to make initial progress into confronting these challenges and focus on developing finite-sample regret bounds that shed light on the design and implementation of efficient policy learning using adaptively collected data.
Our contributions are twofold. First, we study the fundamental difficulty of this problem by characterizing a lower bound for policy learning. In particular, let $\{g_t\}_{t=1}^T$ be any positive lower-bound sequence of propensities $e_t(\cdot \,;\, \cdot)$ (i.e., $e_t(\cdot\,;\,\cdot)$ is lower bounded by $g_t$ for each $t$).\footnote{The assumption that $g_t > 0$ ensures that each action is sampled with positive probability regardless of the contexts.} Then, \textcolor{black}{for a worst-case distribution satisfying the propensity lower bound $\{g_t\}_{t=1}^T$}, any policy learning algorithm will incur at least an expected regret of $\Omega\big(\sqrt{{\textnormal{Ndim}(\Pi)}/{\sum_{t=1}^T g_t}}\big)$, where $\textnormal{Ndim}(\Pi)$ refers to the Natarajan dimension of the (multi-action) policy class $\Pi$---this is a generalization of the VC-dimension for the multi-action policy classes, and in particular $\textnormal{VC}(\Pi) = \textnormal{Ndim}(\Pi)$ in settings of binary actions (i.e. only two actions are available). Consider an example where $g_t$ decays at a rate with $g_t = t^{-\alpha}$ and $\alpha \in [0,1)$, then the worst-case expected regret is lower bounded by $\Omega(\sqrt{\textnormal{Ndim}(\Pi)}\cdot T^{(\alpha - 1)/2})$. This regret lower bound highlights a necessary boundary for the feasibility of policy learning with adaptively collected data: if the adaptive data collection process is overly aggressive in exploitation, leading to an exploration rate that decreases faster than $\Theta(t^{-1})$, then the regret will be $\Omega(1)$---there is thus no hope of ever learning a near-optimal policy in the worst cases, no matter how large $T$ is. On the other hand, when $\alpha = 0$, our regret bound recovers the $\Omega(T^{-{1}/{2}})$ lower bound for the non-adaptive setting where the data is collected by a fixed policy kitagawa2018should.
Second, building on the recent adaptive inference literature, we propose a policy learning algorithm and \textcolor{black}{establish its expected regret bound, which is minimax optimal when the assignment probability lower bound $g_t$ is known to the policy learner.} Our algorithm follows a two-step procedure: 1) construct a policy value estimator $\widehat{Q}(\pi)$ for any fixed $\pi\in\Pi$ using the collected data; 2) output the policy in $\Pi$ that maximizes the estimated value: $\widehat{\pi}=\textnormal{argmax}_{\pi\in\Pi}\widehat{Q}(\pi)$. The specific estimator we use is a variant of the family of generalized augmented inverse propensity weights (AIPW) estimators considered in luedtke2016statistical, hadad2021confidence,zhan2021off, which takes the following form:
Above, $\widehat{\mu}_t$ is the nuisance estimator of the expected outcome, $\widehat{\Gamma}_t(\pi)$ is the AIPW score robins1994estimation, and $h_t$ is the pre-specified deterministic weight that remains the same for all $\pi\in\Pi$. The purpose of $h_t$ is to offset the (potentially) large worst-case variance caused by vanishing assignment probabilities $e_t(X_t; \pi(X_t))$. Depending on whether $g_t$ is known or not, $h_t$ would be chosen differently, which results in different regret bounds (to be elaborated shortly in subsequent paragraphs). These specific choices of $h_t$ are simple and different from those variants adopted in luedtke2016statistical, hadad2021confidence,zhan2021off, which are concerned with devising $h_t$ to evaluate a specific target policy and achieve asymptotic normality for inference, while instead here we aim for controlling worst-case estimation variance and constructing finite-sample regret bounds.
\textcolor{black}{With the weights $\{h_t\}_{t=1}^T$ plugged into the generalized AIPW estimator, we show that our algorithm has an expected regret upper bound of $\tilde{O}\big(\kappa(\Pi)\cdot \frac{\sqrt{\sum_{t=1}^Th_t^2/g_t} }{\sum_{t=1}^T h_t} + \frac{\sum^T_{t=1}h_t^4/g_t^3}{(\sum^T_{t=1}h_t^2/g_t)^2}\big)$ \footnote{We use $\tilde{O}(\cdot)$ to show rates after omitting logarithm factors.}, and $\kappa(\Pi)$ is the entropy integral of a policy class $\Pi$ based on the Hamming distance. Since the data are no longer i.i.d., existing techniques in most policy learning literature no longer apply. Our analysis instead leverages the framework of sequential uniform concentration rakhlin2015sequential. When $\widehat{\mu}_t$ is fitted with observations up to time $t-1$, the AIPW score $\widehat{\Gamma}_t$ is unbiased conditional on the past observations, so we can write $\widehat{Q}_T(\pi) - Q(\pi)$ as the sum of a martingale difference sequence. The supremum of the sum of this martingale difference sequence cannot be bounded with the standard notion of the Rademader complexity used in existing policy learning literature kallus2018balanced,zhou2022offline. We instead consider an analog of the Rademacher process in the adaptive data setting---the tree Radamecher process---and connect the martingale difference sequence with a tree Radamechar process, thereby developing a bound for $\max_{\pi\in\Pi}|\widehat{Q}(\pi)-Q(\pi)|$. However the uniform concentration results in rakhlin2015sequential are not directly applicable here, since here martingale difference terms are not bounded (as required in rakhlin2015sequential) with risk that $\widehat{\Gamma}_t$ may diverge due to vanishing propensities. To address this issue, we introduce a high probability event on which the quadratic variation of the martingale difference sequence is regularized; then we bound the supremum of the tree Radamechar process via a covering of the policy class on the event, by refining and sharpening a chaining technique in zhou2022offline. }
\textcolor{black}{The choice of weight $h_t$ largely decides the regret bound provided by our algorithm. We show that the optimal weight $h^*_t$ is proportional to the assignment probability lower bound $g_t$, which yields the expected regret bound $\tilde{O}(\kappa(\Pi)/\sqrt{\sum_{t=1}^T g_t})$. Note that $\kappa(\Pi) = O\big(\sqrt{\log{p}\cdot\textnormal{Ndim}(\Pi)}\big)$, where $p$ denotes the dimension of the context; in the binary-action case, $\kappa(\Pi) \le 2.5 \sqrt{\textnormal{VC}(\Pi)}$ jin2022upper. This implies that our upper bound with optimal weight $h^*_t$ is tight with respect to (abbreviated as w.r.t. hereafter) the sample size and the complexity of the policy class up to logarithmic factors, and is thus minimax optimal. In cases where $g_t$ is not disclosed to the policy learner, we recommend using uniform weights, that is, estimating policy values with standard AIPW estimator. This choice yields an expected regret bound $\tilde{O}\big(\kappa(\Pi) \cdot \frac{\sqrt{\sum_{t=1}^T g_t^{-1}}}{T} + \frac{\sum^T_{t=1} 1/g_t^3}{(\sum^T_{t=1} 1/g_t)^2}\big)$ that is in general looser than the minimax regret but performs reasonably well in many cases. In particular, for the same example above in which $g_t=t^{-\alpha}$, using uniform weighting also achieves the minimax optimal regret bound $\tilde{O}(\kappa(\Pi)\cdot T^{(\alpha-1)/2})$, which---by setting $\alpha$ to 0---recovers the minimax optimal regret bound for policy learning under i.i.d. data collection established in zhou2022offline.}
\textcolor{black}{After we posted a version of this paper online, bibaut2021risk made remarkable progress on this policy learning problem with adaptive data. They show that their algorithm (which amounts to a variant of our algorithm that by using uniform weighting $h_t=1$ and setting nuisance component $\hat{\mu}_t=0$) meets our established lower bound in settings where $g_t=t^{-\alpha}$ (though their algorithm does not guarantee minimax optimality beyond those special cases). Encouraged by this positive result, we tighten the upper bound of our algorithm and show that it achieves minimax optimal regret guarantee with optimal weighting $h_t^*=g_t$ in general cases (that is, even when $g_t$ is not of the form $t^{-\alpha}$). Besides, the nuisance component $\widehat{\mu}_t$ in our algorithm (which is set to zero in bibaut2021risk) would reduce variance in policy value estimation even with misspecification, which in turn improves the value of learned policy. We defer detailed empirical comparison to Appendix (ref).}
Finally, leveraging a publicly available piece of software, we consider the policy class of (fixed-depth) decision trees and evaluate the algorithm on both synthetic data and public benchmark datasets. The empirical results show two important strengths of our policy learning algorithm. First, when $g_t$ is unknown, our algorithm narrowly trails and has the same regret decay rate as the setting where $g_t$ is known (and hence the optimal weights $h_t^*$ can be computed exactly). This suggests that although it would be helpful to know $g_t$ and hence leverage it to achieve even better performance, our algorithm would still be functional even when such information is not available. Second, since online learning algorithms (e.g., Thompson sampling) often directly use outcome regression, they are prone to model misspecification, where they allocate small propensities to good actions, incurring large performance gap as the process goes on. Despite this, our offline learning algorithm can still find the ($\epsilon$-)optimal policy, demonstrating its effectiveness and robustness.
Policy learning with observational data is a growing field that has received increasing attention from different communities. As already mentioned, the existing literature in offline policy learning has primarily focused on data collected by a fixed policy, where they collectively proposed several statistical efficient and/or computationally efficient policy learning algorithms that achieve the minimax optimal regret bounds of $\Theta(T^{-{1}/{2}})$ on the expected regret. A sequence of refinements zhang2012estimating,zhao2015doubly,kitagawa2018should,athey2021policy addressed this challenge in the settings of binary actions; and particularly kitagawa2018should established the tight regret bound with the knowledge of propensities, which was relaxed later in athey2021policy that established the optimal dependency with estimated propensities. Extension to multi-action schemes has been successively investigated by swaminathan2015batch,zhou2017residual,kallus2018balanced,zhou2022offline; zhou2022offline established the minimax regret bound using doubly robust AIPW estimator when the propensities are unknown. An important distinction when using AIPW estimator on adaptive data is that one often assumes the knowledge of propensities luedtke2016statistical,hadad2021confidence,zhan2021off, as is the case in this paper, since they are typically time-varying and are difficult to approximate with limited batch size.
Another strongly related area is offline policy evaluation with adaptively collected data. Estimating policy values on adaptively collected data is much more challenging compared to that on i.i.d. data. For instance, direct methods that fit regression models will be biased nie2018adaptively,shin2019sample, while unbiased estimators such as inverse propensity weighted (IPW) estimator can suffer from huge variability horvitz1952generalization,imbens2004nonparametric. Note that IPW estimators already suffer from large variance with i.i.d. data (where the propensity has a fixed lower bound that does not change), and the problem becomes more acute in the adaptive data collection setting because the propensities are vanishing. The AIPW estimator robins1994estimation,dudik2011doubly combines the outcome modelling and IPW approaches, gaining efficiency and “double robustness” properties with i.i.d. data. In particular, the AIPW estimator is consistent if either the propensity model or the outcome model is consistently estimated. However, AIPW still has challenges when the data is adaptively collected, since vanishing propensities will yield exploding variance and de-stablize the estimator. To deal with this, the literature has seen two approaches for adapting AIPW estimators to offline policy evaluation with adaptively collected data. The first incorporates weight clipping into AIPW bembom2008data, charles2013counterfactual,wang2017optimal,su2020doubly, where one controls variance by shrinking the weights at the cost of introducing a small bias. The second approach, described above, is to locally stabilize the elements of the AIPW estimator luedtke2016statistical, hadad2021confidence,zhan2021off. Our policy learning algorithm uses an estimator that falls into this second approach, where the weights $h_t$ are chosen with the consideration of the worst-case variance in order to be robust.
Finally, there is also an extensive literature on online contextual bandits dani2008stochastic,besbes2009dynamic,rigollet2010nonparametric,abbasi2011improved,chu2011contextual,bubeck2012regret,abbasi2013online,agrawal2013thompson,goldenshluger2013linear,russo2014learning,li2017provably,dimakopoulou2017estimation,bastani2020online, the online counterpart of policy learning. The literature focuses on analyzing bounds on the regret experienced by alternative algorithms. This problem is distinct from ours and from offline policy learning in general; in the online learning literature, the focus is on the adaptive algorithms and how to assign treatment to units in order to balance the exploration-exploitation trade-off. We close by pointing out that no “online-to-batch" conversion is feasible here: online learning algorithms cannot be directly converted to offline learning algorithms because the offline policy learner does not have the opportunity to choose a particular action. The counterfactual outcomes from alternative actions for a particular unit are unobserved.
Let $T$ be the time horizon, $\operatorname{\mathcal{X}}$ the covariate space, and $\operatorname{\mathcal{W}}$ the action space with $K$ actions. At time $t \in [T] \stackrel{\Delta}{=}\{1,\ldots, T\}$, the experimenter observes a covariate $X_t \in \operatorname{\mathcal{X}}$ with $X_t\stackrel{\textnormal{\textbf{i.i.d.}}}{\sim}P_X$; then the experimenter takes an action $W_t \in \operatorname{\mathcal{W}}$ sampled from a multinomial distribution with probability $\big(e_t(X_t; 1), \dots, e_t(X_t; K)\big)$; next she receives a response $Y_t$ from the chosen action generated via:
where $\{\varepsilon_t\}_{t=1}^T$ is a sequence of i.i.d. zero-mean and $\sigma^2$-variance random variables. We assume that the assignment probability $e_t(x,w)$ is updated for all $(x,w) \in \operatorname{\mathcal{X}} \times \operatorname{\mathcal{W}}$ using observations up to time $t-1$. We use $\operatorname{\mathcal{H}}_{t}=\{(X_s, W_s, Y_s)\}_{s=1}^{t}$ to denote samples up to time $t$. Throughout, we make the following assumptions on the data generating process.
Assumption (ref)(b) requires the experimenters to record data $(X_t, W_t, Y_t, e_t(X_t;W_t))$ at each time instead of the standard $(X_t, W_t, Y_t)$, which is feasible in many applications since practitioners often have access to the algorithm used to collect data, and hence have the knowledge of the assignment probability. \textcolor{black}{The requirement of a lower bound on assignment probabilities for all arms is a bit more restrictive---for instance standard Thompson sampling may not fall into this category since the sampling probability on a clearly sub-optimal arm may decay to zero too fast as $T$ goes to infinity---but we note that this is already a generalization of the previous settings with i.i.d. data.} In parallel, previous work on offline policy learning with i.i.d. data (e.g., athey2021policy,zhou2022offline) often assumes the “overlap” condition: the assignment probability $e_t(x;w)$ is lower bounded by a positive constant for all $(x,w)\in\operatorname{\mathcal{X}} \times \operatorname{\mathcal{W}}$ and all $t\in[T]$. This is in fact a special case of our condition by setting $g_{t}$ to be a positive constant.
\textcolor{black}{A policy $\pi$ is a mapping from the covariate space to the action space, i.e., $\pi: \operatorname{\mathcal{X}} \mapsto \operatorname{\mathcal{W}}$.} Given a policy $\pi$, we are interested in its policy value defined as the expected reward incurred by taking actions according to $\pi$:
where $\operatorname{\mathbb{E}}_X[\cdot]$ denotes taking expectation w.r.t. $P_X$. For a class of policies $\Pi$, we wish to learn the optimal policy $\pi^*$ within $\Pi$:
The {\em regret} of a policy $\pi \in \Pi$ is the policy value difference between the optimal policy and itself:
Conceptually, we would like to learn a policy whose regret is as small as possible (so that its policy value is close to that of the optimal policy). To do this, we shall 1) construct a policy value estimator for each $\pi \in \Pi$, and 2) choose the policy $\hat{\pi}$ that maximizes the estimated policy value over the class $\Pi$. Note that here $\hat{\pi}$ is data-driven, and thus itself and $R(\hat{\pi})$ are both random variables. Our strategy of deriving an upper bound for $R(\hat{\pi})$ is to establish that our policy value estimator is close to the true value uniformly across the policy class. For the rest of the paper, \textcolor{black}{when we say a regret bound for $\hat{\pi}$, we refer to upper bound of the expected regret.}
Policy class is a central element in the discussion of policy learning. The complexity of a policy class presents a trade-off: a richer policy class means that the corresponding optimal policy has a larger value, while the increasing complexity of the class makes the optimal policy learning intrinsically harder. Ideally we would like to consider a policy class with the appropriate complexity such that the optimal policy has a reasonably high value, and meanwhile it is feasible to learn the optimal policy efficiently. Our first step towards this goal is to characterize the complexity of a policy class based on the Hamming distance.
The entropy integral is the key quantity characterizing the complexity of a policy class. We will show in Section (ref) that the regret of our estimator can be upper bounded by a function of the entropy integral, and in Section (ref) we provide a tree-based policy class with finite entropy integral.
To characterize the fundamental limit of the offline policy learning problem, we establish a lower bound for the worst-case expected regret in this section. The lower bound is stated in terms of the Natarajan dimension of a multi-action policy class, the definition of which is as follows.
\textcolor{black}{Returning to our problem, we let $\textnormal{Ndim}(\Pi)$ denote the Natarajan dimension of $\Pi$, $\operatorname{\mathcal{Z}}_T = \{(X_t,W_t,Y_t)\}_{t=1}^T$ represent the collected offline data and $\operatorname{\mathbb{P}}$ be the joint distribution of $\operatorname{\mathcal{Z}}_T$. The following theorem shows that, there exists a $\operatorname{\mathbb{P}}$ satisfying Assumption (ref), such that for any policy $\hat{\pi}$ that is learned from $\operatorname{\mathcal{Z}}_T\sim \operatorname{\mathbb{P}}$, the expected regret is lower bounded by $\Omega\Big(\min\big(1, \sqrt{\textnormal{Ndim}(\Pi)\big/\sum^T_{t=1} g_t}\big)\Big)$.}
\textcolor{black}{
}
\textcolor{black}{As is self-explained in Theorem (ref), when $\textnormal{Ndim}(\Pi) > \frac{1}{9}\sum_{t=1} g_t$, the expected regret in the worst case is lower bounded by a constant, which makes the problem of learning optimal policies infeasible. Hence in this paper, we shall focus on the settings where $\textnormal{Ndim}(\Pi) \leq \frac{1}{9}\sum_{t=1} g_t$ and write the lower bound as $O\big(\sqrt{\textnormal{Ndim}(\Pi)/\sum_{t=1}^T g_t}\big)$ elsewhere when no confusion arises.}
Consider $K$ arms indexed by $[K]$, and write $d = \textnormal{Ndim}(\Pi)$. By the definition of the Natarajan dimension, there exists a set of $d$ points $\{x_1,x_2,\ldots,x_d\} \subset \operatorname{\mathcal{X}}$ that is shattered by $\Pi$, i.e., there exist two functions $f_{-1}$, $f_1: \{x_1,x_2,\ldots,x_d\} \mapsto [K]$, such that $f_{-1}(x_j) \neq f_1(x_j)$ for any $j\in[d]$, and for any ${\bm \sigma} \in \{\pm 1\}^d$, there exists a policy $\pi \in \Pi$ such that $\pi(x_j) = f_{\sigma_j}(x_j)$.
To establish the lower bound, we construct $2^d$ distributions for $\operatorname{\mathcal{Z}}_T$, where each ${\bm \sigma} \in \{\pm 1\}^d$ induces a joint distribution of $\operatorname{\mathcal{Z}}_T$. Fix a ${\bm \sigma} \in \{\pm 1\}^d$. For each $t\in [T]$, let $X_t$ be independently and uniformly generated from $\{x_1,x_2,\ldots,x_d\}$; conditional on $X_t = x_j$, $W_t$ is chosen to be $f_{1}(x_j)$ with probability (w.p.) $g_t$ and other arms w.p. $\big(1-g_t\big)/(K-1)$ (thus the distribution of $X_t$ and $W_t$ does not depend on ${\bm \sigma}$). We now proceed to specify the set of reward distributions for the $K$ arms that depend on ${\bm \sigma}$. For any $j\in[d]$ and some (small) $\Delta > 0$ to be specified later, conditional on $X_t = x_j$,
where $\textnormal{Bern}(q)$ denotes the Bernoulli distribution with parameter $q$. By construction, conditional on $X_t = x_j$, the optimal arm is $f_{\sigma_j}(x_j)$; since $\{x_1,\ldots,x_d\}$ is shattered by $\Pi$, there exists a policy $\pi^{{\bm \sigma},*}\in\Pi$ that selects the optimal arm for any $x_j\in\{x_1,\ldots,x_d\}$. It can be easily verified that the distributions constructed satisfy Assumption (ref). Let $\operatorname{\mathbb{P}}_{{\bm \sigma}}(\cdot)$ and $\mathbb{E}_{{\bm \sigma}}[\cdot]$ refer to the distribution and expectation taken under the joint distribution induced by ${\bm \sigma}$, and let $\operatorname{\mathbb{P}}$ be the mixture distribution uniformly drawn from $\{\operatorname{\mathbb{P}}_{{\bm \sigma}}\}_{{\bm \sigma} \in \{\pm 1\}^d}$. For any policy $\hat{\pi}$ learned from $\mathcal{Z}_T\sim \operatorname{\mathbb{P}}$,
Above, step (i) uses the tower property; in step (ii), the optimal policy is in $\Pi$ since $\{x_1,\ldots,x_d\}$ is shattered by $\Pi$. For a fixed ${\bm \sigma}\in\{\pm 1\}^d$, let $M_j({\bm \sigma})\in \{\pm 1\}^d$ be the vector that differs from ${\bm \sigma}$ only in element $j$: $[M_j({\bm \sigma})]_j = -{\bm \sigma}_j$ and $[M_j({\bm \sigma})]_i = {\bm \sigma}_i$ for all $i \neq j$. Equipped with the notation, we have
where $\textsf{TV}(P,Q)$ denotes the total variation distance between two distributions $P$ and $Q$, and $\textnormal{D}_{\textnormal{KL}}(P\,\|\,Q)$ is the KL-divergence between $P$ and $Q$; step (i) is because $f_1(x_j) \neq f_{-1}(x_j)$, and $\{\hat{\pi}(x_j) = f_{-1}(x_j)\}\subset \{\hat{\pi}(x_j) \neq f_1(x_j)\}$; step (ii) follows from the definition of the total variation distance and step (iii) is a result of Lemma (ref) stated below.
The KL-divergence between $\operatorname{\mathbb{P}}_{{\bm \sigma}}$ and $\operatorname{\mathbb{P}}_{M_j({\bm \sigma})}$ can be directly computed as,
where step (i) uses the linearity and the tower property of expectation; step (ii) is because $\operatorname{\mathbb{P}}_{{\bm \sigma}}$ differs from $\operatorname{\mathbb{P}}_{M_j({\bm \sigma})}$ only when $X = x_j$; \textcolor{black}{step (iii) follows from that $x\log(\frac{1+x}{1-x})\le 3x^2$ for $x \in [0,\frac{1}{3}]$}; step (iv) is by design of the sampling mechanism of $\{W_t\}_{t=1}^T$. Combining (ref) and (ref), we have that \textcolor{black}{
} \textcolor{black}{If $d\leq \frac{1}{9}\sum_{t=1}^T g_t$, letting $\Delta = \sqrt{d\big/\big(\sum_{t=1}^T g_t\big)}$ yields the desired lower bound. Otherwise, choose $\Delta=1/3$, and we have
} which concludes the proof.
A direct consequence of Theorem (ref) is the following corollary. \textcolor{black}{
} The proof is completed by noticing that $\sum_{t=1}^T g_t \leq {T^{1-\alpha}}/{(1-\alpha)}$.
In this section, we introduce our offline policy learning algorithm based on the generalized AIPW estimator, followed by a regret analysis of the algorithm and a discussion on the choice of weights.
Our proposed algorithm consists of two steps. First, it estimates the value of a policy $\pi$ via reweighting the AIPW scores, where the \textcolor{black}{AIPW score} for $t\in[T]$ is defined as follows
Above, $\widehat{\mu}_t(x;w)$ is an estimator of the expectation $\mu(x;w)$ using $\operatorname{\mathcal{H}}_{t-1}$, and $e_t(X_t;w)$ is the assignment probability that is also computed based on $\operatorname{\mathcal{H}}_{t-1}$ and is known to the algorithm by Assumption (ref). The algorithm then outputs the policy maximizing the estimated policy value.
We start from some properties of the AIPW scores that will be useful later.
A direct consequence of Proposition (ref)(a) is that any weighted average of $\widehat{\Gamma}_t(\pi)$ is also unbiased; Proposition (ref)(b) reveals that the conditional variance of the AIPW score $\widehat{\Gamma}_t(\pi)$ scales with $\mathbb{E}\big[e_t(X_t; \pi(X_t))^{-1}\mid \operatorname{\mathcal{H}}_{t-1}\big]$. As is often the case in adaptive experiments, $e_t(X_t;w)$ goes to zero for some suboptimal action $w$ as $t$ increases; consequently, the term $e_t(X_t; \pi(X_t))^{-1}$ may go to infinity, and the variance of $\hat{\Gamma}_t(\pi)$ may explode. To offset the potentially large variance of $\widehat{\Gamma}_t$, we further introduce a weight $h_t$ (the choice of which will be discussed soon) to balance the variance of these AIPW scores. This gives our generalized AIPW estimator:
Our algorithm then selects the policy that maximizes the above estimator:
\textcolor{black}{Below we state the main condition on our weighting scheme.
This assumption specifies a regularity condition on the weights, which controls the higher moments of the estimator $\widehat{Q}_T(\pi)$ in (ref) in the worst cases and thus enables us to introduce martingale concentration results to prove the uniform convergence of $\widehat{Q}_T(\pi)$. An analogous assumption is also required for weighting schemes used in policy inference with adaptive data hadad2021confidence,zhan2021off. We now present the bound on the expected regret for the policy obtained via (ref).}
\textcolor{black}{
}
Here, we only discuss the proof of Theorem (ref) at a high level and defer the details to Section (ref). The main idea is to bound the regret of $\hat{\pi}$ by the worst-case estimation error of $\widehat{Q}_T$ over $\Pi$:
where the inequality uses the fact that $\hat{\pi}$ maximizes $\widehat{Q}_T(\pi)$. It thus suffices to bounding the quantity $\max_{\pi \in \Pi} |Q(\pi) - \widehat{Q}_T(\pi)|$. With $h_t$ being independent of policy $\pi$ and data realization, we have
Define the $\sigma$-field $\mathcal{F}_t \stackrel{\Delta}{=} \sigma(\operatorname{\mathcal{H}}_{t}, X_{t+1})$. Then by Proposition (ref)(a) the term $\sum_{t=1}^T h_t (\widehat{\Gamma}_t(\pi)-Q(X_t,\pi))$ is a martingale difference sequence w.r.t. the filtration $\{\mathcal{F}_t\}_{t \ge 1}$; the term $\sum_{t=1}^T h_t( Q(X_t,\pi)-Q(\pi))$ is an empirical process with i.i.d. random variables. We shall establish uniform concentration results for these two terms in Section (ref) separately.
We proceed to discuss how to choose weights $h_t$ to satisfy Assumption (ref) and sharpen the regret bound established in Theorem (ref). Two scenarios are considered: one with assignment probability lower bound $g_t$ disclosed and the other without; we summarize the procedure in Algorithm (ref).
\textcolor{black}{With the knowledge of $g_t$, our goal is to analytically solve the optimal weight $h^*_t$ that minimizes the regret bound presented in Theorem (ref), which we shall soon show to be $h_t^*\propto g_t$. When $h_t \propto g_t$, Assumption (ref) reduces to that $\sum_{t=1}^T g_t \rightarrow + \infty$, which is naturally satisfied when the learning problem is “feasible” (note that when $\lim\!\sup_{T\rightarrow +\infty} \sum^T_{t=1} g_t < +\infty$, by the lower bound no learning algorithm can do better than a constant error in the worst case). Further, the policy $\hat{\pi}$ obtained with $h^*_t$ is minimax optimal---the expected regret upper bound is $\tilde{O}\big(\kappa(\Pi)\cdot (\sum_{t=1}^T g_t)^{-1/2}\big)$, matching the exact lower bound in Theorem (ref) up to logarithmic factors.}
\textcolor{black}{To solve for $h_t^*$, we firstly minimize the term $(\sum_{t=1}^Th_t^2/g_t)/(\sum_{t=1}^T h_t)^2$ in (ref); as we shall soon see, this minimizer also minimizes the term $L_T(h,g)$ in (ref). Let $\tilde{h}_t=h_t/(\sum_{s=1}^T h_s)$ be normalized weights. We rewrite the original problem into the following convex optimization problem:
The above problem has a unique minimizer $\tilde{h}^*_t=g_t/\big(\sum_{s=1}^T g_s\big)$ (see Appendix (ref) for details). Plugging $\tilde{h}^*$ into $L_T(h,g)$, we have
where the inquality is by Cauchy-Schwartz inequality. This choice of $\tilde{h}^*$ yields a minimax optimal regret bound summarized in the corollary below.}
\textcolor{black}{
The corollary is proven by letting $h_t = g_t$ in Theorem (ref) and noting that $L_T(h,g) = (\sum^T_{t-1}g_t)^{-1} \le (\sum^T_{t=1} g_t)^{-1/2}$.}
In practice, one may not have access to the assignment probability lower bound $g_t$. We claim in such settings, uniform weighting with $h_t=1$ can also be effective. \textcolor{black}{In this case, Assumption (ref) reduces to that
which holds in many cases such as $g_t = t^{-\alpha}$ for some $\alpha \in [0,1)$. The following corollary characterizes the regret incurred by our estimator with uniform weights.}
\textcolor{black}{
}
\textcolor{black}{In general, the regret bound $\tilde{O}\big(\kappa(\Pi)\cdot\frac{\sqrt{\sum_{t=1}^T g_t^{-1}}}{T} + \frac{\sum^T_{t=1}1/g_t^3}{(\sum^T_{t=1}1/g_t)^2}\big)$ yielded by uniform weighting is looser than the minimax regret $\tilde{O}\big(\kappa(\Pi)\cdot(\sum_{t=1}^Tg_t)^{-1/2}\big)$ yielded by optimal weighting, which can be verified by noticing that $\frac{\sqrt{\sum_{t=1}^T g_t^{-1}}}{T}\geq(\sum_{t=1}^Tg_t)^{-1/2}$ as a result of Cauchy-Schwarz inequality. However, in some cases, these two achieve the same regret decay rate---both are minimax optimal, as illustrated in the following example.}
\textcolor{black}{To provide intuition, consider a special case where the assignment probability lower bound decays polynomially, and in specific we let $g_t = t^{-\alpha}$ for some $\alpha\in[0,1)$. We consider weights $h_t=t^{-\beta}$ for some nonnegative $\beta$ and study how $\beta$ affects the regret of $\hat{\pi}$ obtained via (ref). Theorem (ref) shows that the expected regret (in terms of $T$) is lower bounded by $\Omega(T^{(\alpha-1)/2})$. Assumption (ref) holds for any $\beta < \frac{\alpha+1}{2}$; then with Theorem (ref), the expected regret upper bound with $h_t = t^{-\beta}$ for $\beta\in(0, \frac{\alpha+1}{2})$ is $\tilde{O}(\kappa(\Pi)\cdot T^{(\alpha-1)/2}+ T^{4\beta-2\alpha-2})$. In particular, when $\beta\leq \frac{5\alpha+3}{8}$, our algorithm achieves expected regret bounds of $\tilde{O}(\kappa(\Pi)\cdot T^{(\alpha-1)/2})$, which matches the exact lower bound and is thus minimax optimal. Notably, uniform weighting (which does not require $g_t$ known) achieves the minimax optimal regret upper bound, and this bound inflates the one obtained by optimal weights (which needs $g_t$ to be disclosed) by a factor of $(1-\alpha^2)^{-1/2}$. In this regard, when the assignment probability lower bound does not decay too fast in the sense that $g_t=t^{-\alpha}$ for some $\alpha\in[0,1)$, the minimax optimality of our algorithm is agnostic to the knowledge of $g_t$.}
We now establish the regret bound given in Theorem (ref). The problem has been decoupled to showing two uniform concentration results for: (i) the martingale difference sequence $\sum_{t=1}^T h_t \big(\widehat{\Gamma}_t(\pi) - Q(X_t, \pi)\big)$, where we condition on an event that the quadratic variation of AIPW scores $\widehat{\Gamma}_t$ is well regularized across the policy class, which happens with high probability under Assumption (ref); and (ii) the sum of independent variable sequence $\sum_{t=1}^T h_t\big(Q(X_t, \pi)-Q(\pi)\big)$, where we apply standard techniques in analyzing empirical processes with i.i.d. data.
Define $\operatorname{\mathbb{M}}_T(\pi) \stackrel{\Delta}{=} \sum^T_{t=1} h_t \big(\widehat{\Gamma}_t(\pi) - Q(X_t, \pi)\big)$. Our goal is to show that with high probability, $\max_{\pi\in\Pi}|\operatorname{\mathbb{M}}_T(\pi)|$ is small. \textcolor{black}{Particularly, we shall restrict our analysis on the event below:
In the following, we write $C_T({h,g}) \stackrel{\Delta}{=} 10KM^2 \cdot \sum^T_{t=1} h_t^2/g_t$ for notation convenience. On the event $\operatorname{\mathcal{B}}_T$, the quadratic variation of $\operatorname{\mathbb{M}}_T(\pi)$ is controlled, which is critical in showing a fast uniform concentration rate of $\operatorname{\mathbb{M}}_T$. The following lemma quantifies the probability of the event $\operatorname{\mathcal{B}}_T$.
The proof is deferred to Appendix (ref). Lemma (ref) immediately implies that under Assumption (ref), event $\operatorname{\mathcal{B}}_T$ happens with high probability. Moving on, we shall show that $\operatorname{\mathbb{M}}_T$ concentrates uniformly at a fast rate when $\operatorname{\mathcal{B}}_T$ happens.}
The traditional symmetrization technique is useful for proving uniform concentration results with i.i.d. data, but is not directly applicable given the adaptive nature of our data. Motivated by rakhlin2015sequential, we leverage a sequential analog of the symmetrization technique to obtain the uniform concentration for martingale empirical process. Note that results in rakhlin2015sequential, which require difference elements to be bounded, cannot be directly invoked in our setting where each element may diverge. \textcolor{black}{To still allow for sequential uniform concentration, we take a different route and condition on event $\operatorname{\mathcal{B}}_T$, such that the sum of quadratic terms is under control.}
We present the proof of uniform concentration of $\operatorname{\mathbb{M}}_T(\pi)$ in two steps. First, we connect the martingale empirical process with a tree Rademacher process (defined shortly afterwards), and next we connect the tree Rademacher process with the entropy integral of the policy class $\kappa(\Pi)$.
\paragraph{Step 1: Connecting the Martingale Empirical Process with a Tree Rademacher Process.} We start by defining the notion of a tree, following rakhlin2015sequential.
A tree $\operatorname{\mathbf{z}}$ is identified with a sequence of labeling functions $(\operatorname{\mathbf{z}}_1,\ldots, \operatorname{\mathbf{z}}_T)$, where $\operatorname{\mathbf{z}}_i:\{\pm 1\}^{i-1} \mapsto \operatorname{\mathcal{Z}}$ labels the nodes on the $i$-th level. To be more speficic, $\operatorname{\mathbf{z}}_1$ refers to the root node; $\operatorname{\mathbf{z}}_i$ for $i>1$ refers to the node on the $i$-th level of the tree with the following rule: for a $\{\pm 1\}$-valued sequence of length $i-1$, $\operatorname{\mathbf{z}}_i$ maps the sequence to a node by following a path on the tree, with $-1$ referring to “left” and $+1$ to “right”. As an example, Figure (ref) plots a tree of depth $3$, where $\operatorname{\mathbf{z}}_3(-1,-1)$ corresponds to the blue node, and $\operatorname{\mathbf{z}}_3(1,-1)$ is the red node.
We proceed to state the definition of a tree Rademacher process:
\textcolor{black}{Defining $Z_t \stackrel{\Delta}{=} (W_t,Y_t,\{e_t(X_t;w)\}_{w\in\operatorname{\mathcal{W}}}, \{\hat{\mu}_t(X_t;w)\}_{w\in\operatorname{\mathcal{W}}})$, we write $f(h_t,X_t,Z_t;\pi) = h_t\cdot\hat{\Gamma}_t(\pi)$.} Let $\mathcal{Z}$ be the space $Z_t$ lives in and $\operatorname{\mathbf{z}}$ be a $\operatorname{\mathcal{Z}}$-valued binary tree. For notational simplicity, we write $\operatorname{\mathbf{x}}=\{x_{1}, \dots, x_T\}$ to denote realized values of the covariates and $z_t(\epsilon) = \operatorname{\mathbf{z}}_t(\epsilon_1,\ldots,\epsilon_{t-1})$ to denote a node at depth $t$. Following rakhlin2015sequential, we introduce a decoupled tangent sequence (which is similar to the symmetrized sequence in the i.i.d. case and is defined in Definition (ref)) with respect to the data sequence $(Z_1,\ldots,Z_T)$. \textcolor{black}{Similar to analyzing the martingale empirical process on event $\operatorname{\mathcal{B}}_T$, we also restrict our analysis of the tree Rademacher process on the event $\operatorname{\mathcal{B}}_T(\operatorname{\mathbf{x}},\operatorname{\mathbf{z}})$, which is defined with respect to a realization of covariates $\operatorname{\mathbf{x}}$ and a tree $\operatorname{\mathbf{z}}$ as follows:
Lemma (ref) shows that the tail of $\sup_{\pi\in\Pi} |\operatorname{\mathbb{M}}_T(\pi)|$ on the event $\operatorname{\mathcal{B}}_T$ is bounded by the tail of the supremum of tree Rademacher process on the event $\operatorname{\mathcal{B}}_T(\operatorname{\mathbf{x}},\operatorname{\mathbf{z}})$.
} The proof is deferred to Appendix (ref).
\paragraph{Step 2: Connecting the Tree Rademacher Process with Policy Class Complexity.} We now proceed to connect the tail bound of the supremum of tree Rademacher process with the complexity of the policy class. Note that this Rademacher process is defined on a tree, and the Hamming distance in Definition (ref) cannot be directly applied here to characterize Rademacher complexity. Alternatively we adopt the notion of distance between policies on the tree process defined in rakhlin2015sequential and modify it slightly for notational convenience in the proof.
The Hamming distance is connected with the $\ell_2$ distance as follows.
The proof of Lemma (ref) is provided in Appendix (ref). We are now ready to bound the tail of supremum of tree Rademacher process using the entropy integral defined under Hamming distance.
\textcolor{black}{
}
We refer readers to Appendix (ref) for the complete proof of Lemma (ref). We here present the three key parts in our proof to provide some intuition.
\endproof
We now establish concentration results for $\sum_{t=1}^T h_t\big(Q(X_t,\pi)-Q(\pi)\big)$. We note that covariates $X_{1:T}$ are exogenous; thus $\{Q(X_t, \pi)\}_{t=1}^T$ are bounded i.i.d. random variables. We shall apply the standard toolkit for the uniform concentration of i.i.d. data.
The proof is deferred to Appendix (ref) for details. At a high level, we shall decompose $\sum_{t=1}^T h_t\big(Q(X_t,\pi)-Q(\pi)\big)$ via a sequence of policy approximation operators, and bound each difference with standard uniform concentration techniques for i.i.d. data.
\textcolor{black}{We are now ready to put the pieces together and prove Theorem (ref). Suppose that Assumptions (ref) and (ref) hold. Consider a $T$ such that $L_T(h,g) \le 1/8$.
where the last inequality is a result of Lemma (ref). Next, using the decomposition introduced earlier,
For the first expectation, letting $\bar{\zeta} = 24 \sqrt{C_T({h,g})} \cdot (2\sqrt{2} + 2\sqrt{2} \kappa(\Pi) + \sqrt{\log \Big(\frac{2M \sum^T_{t=1}h_t/g_t}{ \sqrt{C_T({h,g})}}\Big)} + 1/\sqrt{T} )$, we have
where in the last step we apply Lemma (ref) and Lemma (ref) with $\eta = 4\bar{\zeta} / T$ and $\delta = \frac{1}{M} \frac{\sqrt{C_T({h,g})}}{\sum^T_{t=1} h_t/g_t}$ (it can be checked that $\eta > \sqrt{8C_T({h,g}) / (KT^2)}$).}
\textcolor{black}{For the second expectation, we take $\delta = \sqrt{C_T({h,g})}/(M\sum^T_{t=1}h_t)$ in Lemma (ref) and get
}
\textcolor{black}{Summing the two terms up, we have
}
\textcolor{black}{The proof is hence completed.}
\endproof
In this section, we provide experimental evidence on the effectiveness of Algorithm (ref), using both synthetic datasets and classification datasets from OpenML OpenML2013. We investigate 1) how offline learning compares with its online counterpart when there is model misspecification; and 2) how different choices of weights $h_t$ influences the regret of offline-learned policy. Throughout the experiments, we use linear models to fit the nuisance estimator $\mu_t$ on data $\operatorname{\mathcal{H}}_{t-1}$.\footnote{Reproduction code can be found at \url{https://github.com/gsbDBI/PolicyLearning}.}
\paragraph{Policy Class.} \textcolor{black}{Exact policy learning via maximizing policy value estimation generally leads to a nonconvex optimazation problem and can be infeasible for arbitrary policy classes. We hereby focus on a policy class of decision trees with fixed depth, which has a finite entropy integral zhou2022offline. To learn the policy that maximizes generalized AIPW estimator, we apply a publicly available solver PolicyTree that finds the global optimum in polynomial runtime via an exhaustive and unconstrained tree search sverdrup2020policytree.} Algorithm (ref) adapts the software to our problem setting with customized inputs, so that weights $h_t$ are incorporated in the value estimator.
\paragraph{Data-Collection Agent.} At each time, the experimenter first computes each arm's preliminary assignment probabilities $\{\bar{e}_t(X_t;w)\}_{w\in\operatorname{\mathcal{W}}}$ based on past observations via a Linear Thompson sampling agent agrawal2013thompson; then a lower bound $g_t=t^{-\alpha}/K$ (with $\alpha=0.5$) is imposed: arms with $\bar{e}_t(X_t;w)<g_t$ have assignment probability $e_t(X_t;w)=g_t$; others will be shrunk by setting $e_t(X_t;w)=g_t+c(\bar{e}_t(X_t;w)-g_t)$, where $c$ ensures $\sum_{w\in\operatorname{\mathcal{W}}}e_t(X_t;w)=1$. \textcolor{black}{This type of flooring scheme is a generalization of commonly-enforced overlap practice in randomized controlled trials and has been increasingly used in adaptive experimentation. The floor allows for diminishing exploration on suboptimal arms, but imposes a positive probability of sampling each arm to facilitate post-experiment analyses (which often require non-zero assignment probabilities everywhere when using methods based on inverse probability weighting) offer2021optimal.}
We consider a contextual bandit problem with two arms. At each time, the experimenter observes a covariate $X_t\in \mathbb{R}^3$ that is i.i.d. sampled from Uniform$[-2,2]^3$. The outcome model only depends on the first coordinate of the covariate: given $x=(x_1, x_2, x_3)$, arm $1$ has conditional mean $\mu_1(x)=x_1^2$, and arm $2$ has conditional mean $\mu_2(x)=2-x_1^2$; see the left panel in Figure (ref) for illustration. The observed response is perturbed by i.i.d. standard Gaussian noise.
To evaluate learned policies, we in addition sample $100,000$ observations (covariates and potential outcomes) from the same underlying distribution as test data to calculate the regret. The right panel in Figure (ref) demonstrates that given each sample size, the out-of-sample regrets (on the test data) of the current data-collection agent (note that this agent updates its policy with growing sample size) and of the policies obtained via Algorithm (ref) with different choices of $h_t$.
We first compare online learning with offline learning when there is model misspecification. Both the data-collection agent and the nuisance component $\hat{\mu}_t$ in the AIPW scores assume a linear outcome model, while the true $\mu$ is quadratic. The data-collection agent thus fails to learn the optimal policy; in fact, as shown in Figure (ref), its out-of-sample regret decays much slower than the regret of any policy learned via Algorithm (ref).
\textcolor{black}{Figure (ref) also demonstrates that performances of different choices of weights are consistent with our analysis in Section (ref), where the optimal weight $h^*_t=t^{-\alpha}$ (which minimizes the theoretical regret bound in Theorem (ref)) achieves the smallest regret. Besides, weights $h_t=t^{-\beta}$ with $\beta<\frac{5\alpha+3}{8}$ yield the same regret decay rate as $h_t^*$; this rate is faster than the regret obtained by setting $\beta= 2\alpha$, which choice of weights does not satisfy Assumption (ref) and thus does not have guaranteed regret decay in Theorem (ref). These findings are aligned with our recommendation of weights in Algorithm (ref)---when the assignment probability lower bound $g_t$ is unknown, one can choose $h_t=1$ to achieve a reasonable regret decay rate, which is minimax optimal when $g_t$ decays slower than $\Theta(t^{-1})$.}
We adapt $82$ multi-class classification datasets from OpenML OpenML2013 into contextual bandit problems of sequential classification, following literature dudik2011doubly,dimakopoulou2017estimation,su2020doubly. Specifically, each class represents an arm, and each feature vector denotes a covariate that is sampled uniformly from the data; the counterfactual outcomes of different arms correspond to the one-hot encoding of the associated label. That is, we set the expected potential outcome for a given “arm” (a possible label) to one if the arm is the same as the label, and zero otherwise. The observed outcome is perturbed with a standard Gaussian noise. We can simulate an online learning algorithm with this artificial definition of arms and outcomes. In the experiment, we again use a floored Thompson sampling agent to collect data. See Appendix (ref) for the list of datasets. Table (ref) summarizes the statistics of the datasets.
Figure (ref) demonstrates regret of policies learned with different choices of weights $h_t$ on various datasets. Particularly, we use uniform weights $h_t=1$ as a baseline, and compare it with other choices of weights $h_t=t^{-\beta}$ with $\beta=\{\alpha/2, \alpha, 2\alpha\}$. Each point represents a dataset, and its $x,y$ coordinates are normalized regrets using the uniform weights $h_t=1$ and the weights $h_t=t^{-\beta}$, with the normalization term being the largest regret among all datasets. One can see that the best performance is achieved at optimal weights $h_t=t^{-\alpha}$, while the worst one is given by weights $h_t=t^{-2\alpha}$. We also observe that in the first two panels of Figure (ref), setting $h_t=\{t^{-\alpha/2},t^{-\alpha}\}$ yields smaller regret than uniform weighting $h_t=1$ in most datasets (most points are in orange in these two panels), but the improvement is mild. \textcolor{black}{This again agrees with our analysis in Section (ref), which shows these three choices of weighting $h_t=\{1,t^{-\alpha/2},t^{-\alpha}\}$ have the same minimax regret decay rate $O(T^{(\alpha-1)/{2}})$.} As such, we again recommend using uniform weighting when the assignment probability lower bound $g_t$ is unknown, as presented in Algorithm (ref).
We further provide auxiliary summary statistics in Table (ref), where for each weighting scheme, we list the average and median of regrets over all datasets; we also compute the number of datasets on which each weighting scheme achieves the smallest regret. Again, we find that optimal weighting with $h_t=t^{-\alpha}$ has the best performance.
In this paper, we propose an approach to policy learning with adaptively collected data. Our main result is that, in the regime where assignment probabilities are bounded below by a nonincreasing positive sequence, one can leverage generalized AIPW estimators to approximate policy value, and the policy that maximizes the estimates within a pre-specified class is asymptotically optimal. Our approach is built upon the semiparametric literature and does not require knowledge of outcome model. \textcolor{black}{Particularly, when equipped with the knowledge of lower bound on assignment probabilities, our algorithm achieves rate-optimal guarantees for minimax regret.}
A number of interesting research directions remain open. A natural extension is to adapt weights $h_t$ to a smaller subset of policy classes, or further, the policy currently being evaluated. Here we choose $h_t$ to offset the worst-case variance in the value estimation (and thus constant over the policy class and for any data realization); as a result, the effective sample size may not grow as fast as the actual sample size. However, if one can adaptively choose $h_t$ with respect to the evaluated policy and the data collected, as proposed in hadad2021confidence, it may result in better empirical performance with improved effective sample size. Another potential line of research is to accommodate our offline learning framework to batch learning in the online setting. Most of the online learning literature that has established regret bounds is built upon functional form assumptions about the outcome model, while the generalized AIPW estimator does not require such knowledge, suggesting its potential to innovate the design of adaptive experiments.
The authors would like to thank Vitor Hadad, David A. Hirshberg, Stefan Wager, and Ruoxuan Xiong for helpful discussions. The authors are also grateful for the generous support provided by Golub Capital Social Impact Lab. S.A. acknowledges generous support from the Office of Naval Research grant N00014-19-1-2468. R.Z. acknowledges generous support from the PayPal Innovation Fellowship.