arXiv:2605.15108v1 [stat.ML] 14 May 2026
Logging Policy Design for Off-Policy Evaluation Connor Douglas
Joel Persson
Foster Provost
New York University
Spotify
New York University
May 2026
Abstract Off-policy evaluation (OPE) estimates the value of a target treatment policy (e.g., a recommender system) using data collected by a different logging policy. It enables high-stakes experimentation without live deployment, yet in practice accuracy depends heavily on the logging policy used to collect data for computing the estimate. We study how to design logging policies that minimize OPE error for given target policies. We characterize a fundamental reward–coverage tradeoff: concentrating probability mass on high-reward actions reduces variance but risks missing signal on actions the target policy may take. We propose a unifying framework for logging policy design and derive optimal policies in canonical informational regimes where the target policy and reward distribution are (i) known, (ii) unknown, and (iii) partially known through priors or noisy estimates at logging time. Our results provide actionable guidance for firms choosing among multiple candidate recommendation systems. We demonstrate the importance of treatment selection when gathering data for OPE, and describe theoretically optimal approaches when this is a firm’s primary objective. We also distill practical design principles for selecting logging policies when operational constraints prevent implementing the theoretical optimum.
1
Introduction
Off-policy evaluation (OPE) is a key tool when implementing data-driven decision-making systems (policies), such as recommender and content-selection systems. The aim of OPE is to evaluate the value of some “target” policy using data collected under some other “logging” policy (Uehara Acknowledgments. This material is based upon work supported by the Fubon Center of Technology, Business and Innovation at NYU Stern and the National Science Foundation Graduate Research Fellowship under Grant No. DGE-2234660. We would like to thank Kyle Kretchsman for supporting this research at Spotify. We would also like to thank Todd Wasson for helpful discussions on practical problems and solution approaches.
1
et al., 2022).0 OPE is a crucial first step to improve decision-making systems in many settings, as it enables data-informed exploration of candidate treatment policies without deployment. This step in development is especially important in areas such as medicine (Murphy et al., 2001), digital advertising (Thomas et al., 2017), and recommendation systems (M. Chen et al., 2019), where online experimentation can be costly or unethical and also can degrade the experience or welfare of individuals. As a simplified example illustration, consider a content recommendation platform. A key feature of the platform is the user’s home page, which displays a prominent recommendation each time the user visits the page. The recommendation might be a playlist, podcast, audiobook, etc. The firm continually iterates on its recommendation systems to improve the user experience and account for new technical developments, dynamic content catalogs, evolving user preferences, and broader platform priorities (Fernández-Lorı́a et al., 2022). Before live (“in vivo”) testing, candidate recommendation policies are evaluated offline via OPE on logged, historical data. The logging policy is the policy that served recommendations to users during the logging period, generating the historical data. Previous research and platforms companies have indicated that OPE accuracy can vary dramatically with the choice of logging policy, and that some logging policies require vastly more data to achieve a given level of estimation precision Wan2022Safe; Persson (2024), Tucker and Joachims (2023), and Zhu and Kveton (2022). Yet little is known about how to best design logging policies to support reliable and efficient OPE. This paper aims to address that gap. We offer a theoretical explanation for the sensitivity of OPE to the logging policy and show how logging policies should be designed to support statistically reliable and efficient OPE. Specifically, we optimize the action propensities during data collection to minimize the mean-squared error (MSE) of an IPW estimate of a target policy’s value, which is the expected mean reward accrued under that policy. We focus on the IPW estimator because it is unbiased and completely determined by the action propensities of the logging policy and the target policy. Therefore, our design isolates the effect of the logging policy on our OPE estimate. Practical considerations complicate the design problem. The action space—the possible recommendations for a user—may be very large, and rewards may be very sparse and heterogeneous across users (e.g., users may click on certain recommendations infrequently even if they are good recommendations). This sparsity problem poses statistical challenges for OPE, yet is precisely 0
In the literature, target policies are also called evaluation policies and logging policies are called behavior policies or learning policies.
2
what the value of personalization hinges on. Furthermore, the firm may or may not know the exact candidate policies it will want to evaluate with the logged data before it has been collected. This means the logging policy may need to cover a broad range of actions, since the target policy to be evaluated may not be known in advance. Finally, since the logging policy is actually deployed to serve recommendations, a firm typically wants the user experience during the logging policy to be good. In economic terms, the firm wants to avoid the cost of excessively random action selection, if possible. Informed by this, we study logging policy design under varying degrees of knowledge of the target policy and of reward probabilities, and analyze the reward accrual (value produced) under resulting logging policies. The design of logging policies for OPE is the subject of a small but emerging body of research. Much of this work has focused on the design of “safe” logging policies, which aims to attain acceptable performance outcomes during the logging period while still ensuring reliable and efficient OPE. This problem is related to, but distinct from, the problem of bandit learning or other standard adaptive experimentation settings. In the bandit literature, a typical objective is to design adaptive policies that maximize cumulative reward by balancing exploration of action-reward distributions against exploitation of accumulated knowledge (Sutton & Barto, 1998). The aim of logging policy design for OPE is different. It is not to adaptively maximize reward, nor to identify the best policy in as few samples as possible. Instead, logging policy design for OPE aims to sample actions so that the value of one or more (potentially unknown) target policies can be estimated offline from the accrued data, with as low statistical error as possible. In addition, firms will generally want to maintain acceptable recommendation performance during the logging period. For a content streaming platform such as Netflix or Spotify, this means that the reward metric of interest (e.g., average streaming rate across users among impressed items) during the deployment of a logging policy should not be much lower than that of the status-quo production policy that delivers the personalized experience per user. There is substantial literature on how to construct unbiased and efficient statistical estimators for OPE. This work typically treats the data as fixed and generated according to some existing and potentially unknown logging policy. Key estimators from this stream of work include the direct method, inverse propensity weighting (IPW) (Chesnaye et al., 2022) and doubly-robust (DR) approaches (Dudı́k et al., 2014). In the sample limit, these estimators enjoy strong statistical guarantees, including asymptotic unbiasedness and bounded variance. These hold as long as the data and models involved in the estimation satisfy standard causal inference assumptions and 3
regularity conditions (see e.g., Uehara et al., 2022, for an overview and technical treatment). In finite sample sizes, however, the choice of logging policy has a dramatic effect on the bias and variance of OPE estimates. Since all practical settings have finite samples, this motivates studying how the logging policy’s action probabilities should be chosen to minimize bias and variance of the OPE estimator. Summary of contributions. We present a unified framework for logging policy design with the objective of minimizing the mean squared error (MSE) of an IPW estimate of a target policy’s value. Our framework organizes the design problem along two dimensions: knowledge of the target policy and knowledge of the reward distribution. This organization reflects the informational constraints faced in practice and yields a clean space of design problems with tractable optimal solutions. Section 2 demonstrates the importance of logging policy choice for OPE. Section 3 then sets up the challenges for the design problem. We derive the bias-variance decomposition of the IPW estimator as a function of the logging policy, and show that a “good” logging policy must balance a fundamental reward-coverage tradeoff: concentrating probability mass on high-reward actions reduces variance from reward realization, but coverage across actions the target policy may take is needed to control both bias and variance. Balancing this tradeoff is the central design challenge and connects logging policy design to classical problems in optimal experimental design (Kiefer, 1959; Wald, 1943) and importance sampling. In Section 4, we derive optimal logging policies at the extrema of our space of informational settings. We show that when neither the target policy nor the reward distribution is known, uniform randomization is minimax optimal. This reflects the classical intuition that an uninformative prior is optimal when one assumes nothing about the estimand and wants to control worst-case error. We then consider the ideal case where both the target policy and reward function are known. We show the optimal logging policy takes the form of a Neyman allocation (Neyman, 1934) directed toward the target policy, weighting action probabilities by the product of target policy mass and the square root of the reward probability. This solution minimizes IPW variance subject to overlap, and yields two notable byproducts: the resulting OPE estimate based on IPW has lower MSE than the empirical on-policy estimate one would obtain by running the target policy directly, and the logging policy accrues higher expected reward than the target policy during the logging period.
4
This confirms that OPE with an optimized logging policy can jointly attain higher policy value and estimation precision than on-policy evaluation (e.g., an A/B test). In Section 5, we extend our analysis to intermediate informational settings that may better reflect practical applications. We present and prove the optimal solution for cases where only the distribution over target policies is known. Examlpes of such cases include when the firm plans to evaluate several candidate systems from a single logged dataset. For this case, the optimal logging policy should not allocate sampling mass towards any given target policy, but instead towards a second-moment pseudo-target. We provide a simple plug-in construction that instantiates this idea. We then consider the case that instead the reward distribution is only partially known. This occurs in practice when rewards are estimated, for instance by fitting a machine learning model on historically logged data. We show that using noisy reward predictions directly to in logging policy design inevitably inflates the variance of the downstream IPW estimate. As a solution, we propose the use of posterior shrinkage of reward estimates toward a per-context, across-action mean, and provide the optimal amount of shrinkage under a Gaussian hierarchical prior and noise. This prior can in turn be estimated from data, leading to an “empirical Bayes” (Efron & Morris, 1973; Robbins, 1956) interpretation of the logging policy design solution. In Section 6, we provide practical guidance for settings where the theoretically optimal logging policy cannot be deployed. This analysis is motivated by organizational constraints. Fully personalized action propensities for actions may not be available at serving time, and deploying an optimized logging policy per target policy can carry excessive engineering costs. Irrespective of the reason, we highlight that even when the theoretically best logging policies cannot be implemented, simple “soft-greedy” logging policies that weight action propensities toward current, in-production estimates can greatly improve the reliability and efficiency of OPE. We describe three suitable policy classes (top-k, softmax, and power-normalized), each indexed by a single greediness parameter that smoothly interpolates between uniform randomization and deterministic greedy selection. By this construction, these policy classes balance the reward-coverage tradeoff through a single decision variable. We show through simulation that well-tuned policies in these classes can approach the MSE of the theoretical optimum, and provide guidance on how the greediness parameter should be chosen relative to sample size and action space.
5
2
Setting
We frame the setting similarly to a contextual bandit problem: a Markov Decision Process without transition dynamics, and where rewards from actions given contexts are realized immediately. This directly maps to our example of a content platform selecting one piece of content at a time to recommend to a particular user through its prominent home page slot. The reward of interest is some binary preference signal, which in our example could be whether a user chooses to stream the recommended content or not. This framing is standard in the literature and enables scalable deployment (Xie et al., 2018). Let X denote the space of contexts and A the set of available actions. Here, context refers to a user and the circumstances under which they are being served an action (for example, time of day, day of week, etc.). In our example, actions would refer to the items of content to recommend. Contexts arrive according to a stationary distribution pX , which may be unknown. Given a realized context x ∈ X , the system selects an action a ∈ A according to a policy π(· | x). We then observe a reward R drawn from a conditional distribution pR|X,A . We take rewards to be binary variables R | (A, X) ∼ Bernoulli(µ(A, X)) where µ(a, x) := E[R | A = a, X = x] denotes the conditional mean reward, or, equivalently, the success probability Pr(R = 1 | A = a, X = x). In our running example, µ can be thought of as the chance that a given user streams a content item after being recommended it, given their context. Any policy, including the πl , produces some average reward across contexts and the actions it selects. This expected reward is the policy’s value V . Formally, the value of a policy V (π) = E[R], with this expectation taken across context X from pX , actions A drawn from π(·|X), and the Bernoulli reward R drawn from pR|A,X . The aim of off-policy evaluation is to construct an accurate and precise estimate of the policy value, V̂ , for some “target” policy, using data collected by the logging policy πl . We treat the action probability (propensity score) π(a | x) as known for each a ∈ A and x ∈ X . This is not restrictive, since the task of logging policy design is precisely to determine these probabilities. Our setup satisfies the standard assumptions of consistency and unconfoundedness by construction. These assumptions are central in the causal inference literature (e.g., Hernán & Robins, 2020; Imbens & Rubin, 2015) and off-policy evaluation (Uehara et al., 2022, Section 2). Consistency means that the realized reward for a given context depends only on the action assigned in that context. This is reasonable in our motivating example of a homepage content recommender 6
with a single recommendation slot and no cross-user interactions. It may be violated in settings such as multi-slot feeds or social platforms with network effects. Unconfoundedness requires that potential rewards are independent of action assignment conditional on the observed context. This holds by construction in our setting, since actions are randomized according to a logging policy chosen and implemented by the logging policy designer.
2.1
Inverse Propensity Score Weighting (IPW)
A key class of estimators of a target policy’s value is derived via inverse propensity weighting (IPW). Formally, the IPW estimator of a target policy’s value is defined as N
1 X πt (Ai |Xi ) Ri , V̂IPW (πt |πl ) = N i=1 πl (Ai |Xi )
(1)
i.i.d.
which is computed over the sample {Xi , Ai , Ri }N i=1 ∼ pX (x)πl (a|x)pR|X,A (r | x, a) generated by deploying the logging policy πl , and the sample size N can be interpreted as the finite experimentation budget. In this paper, we examine how to construct logging policies for off-policy evaluation using the IPW estimator. Our use of the IPW estimator is motivated by two features. First, most popular OPE estimators build on the IPW estimator, including the self-normalized IPW and doubly robust variants (Dudı́k et al., 2014)). Second, the IPW estimator is completely design-based : it requires only observed rewards and action propensities. This is a benefit in applications since the designer controls the sampling of actions but not why and how users respond to them. Thus, by considering the IPW estimator, we design logging policy precisely to maximize the accuracy of our OPE estimates. As we will see, however, designing an effective logging policy will depend crucially on assumptions about rewards and the target policy. This is inevitable if the logged data is to be most informative for off-policy evaluation. An aim of our work is to make design considerations and their trade-offs explicit. The problem of logging policy design is based on the observation that even with the IPW estimator held fixed, the choice of logging policy has a dramatic effect on the accuracy of offpolicy evaluation. Figure 1 shows the sampling distributions of IPW estimates under two logging policies, personalized and uniform, across repeated simulated datasets and two sample sizes. Here, a personalized logging policy assigns equal probability to the 10 actions with the highest noisy 7
reward estimates; the uniform policy samples assigns equal probability across all 10,000 actions. Both policies are used to gather data for evaluation a target policy, which places mass uniformly across the 10 actions with the highest (noiseless) reward probabilities, with the IPW estimator. A logging policy that samples more frequently from high-reward items produces estimates whose sampling distribution is more tightly concentrated around the true target policy value. This effect is particularly pronounced in the small-sample regime, where sampling variability of the estimate is inevitably greater. Here, uniform logging can produce highly inaccurate off-policy estimates, often resulting in extremely small or extremely large estimates (see the spikes at zero and one for the small-sample regime for the uniform policy). Collecting more informative data substantially reduces this error. As the figure shows, 1,000 observations under the personalized logging policy match the accuracy of 100,000 observations under uniform logging. This example illustrates the practical importance of logging policy design for off-policy evaluation. Because the logging phase represents a finite experimentation period prior to deployment, an effective logging policy can attain a desired level of evaluation accuracy with fewer observations, or equivalently, achieve greater accuracy for a fixed experimentation budget. In recommender systems, this is particularly important because prolonged experimentation can delay product innovations, expose users to suboptimal recommendations, and incur opportunity costs relative to deploying the target policy. Histogram of IPW Estimates
Count
102
Target Policy Value Uniform (n = 100, 000) Uniform (n = 1, 000) Personalized (n = 100, 000) Personalized (n = 1, 000)
101
100 0.000 0.025 0.050 0.075 0.100 0.125 0.150 0.175 0.200
0.95
1.00
Estimate (VIPW)
Figure 1: Dependence of IPW estimates on logging policy . Histogram of V̂IPW based on uniform and personalized logging policies, in small sample (n = 1, 000) and large sample (n = 100, 000) regimes. Uniform logging yields far worse estimates, especially in the small sample regime. Full simulation details are in Online Appendix D
8
2.2
Objective: Minimize MSE in Informational Settings
The previous section illustrates that the sampling distribution of the IPW estimator depends critically on the logging policy. To compare logging policies, we therefore require a metric that evaluates the accuracy of the estimator V̂IPW (πt | πl ) relative to the true target policy value V (πt ), taking into account both systematic bias and sampling variability. A natural choice is the mean squared error (MSE), as it decomposes into bias and variance, represents the convex underlying cost structure of errors, and is a standard measure of “risk” in OPE and statistical decision theory. We therefore study logging policy design with the objective of minimizing the MSE of the IPW estimator, given by h i h 2 i MSE V̂IPW (πt | πl ) = E V̂IPW (πt |πl ) − V (πt ) .
(2)
where the expectation is taken over the joint distribution pX (x)πl (a|x)pR|X,A (r | x, a) of the logged data under πl , that is, across arriving context, actions selected by the logging policy, and resultant rewards. Our focus on the MSE is also motivated by its differentiability and the generally convex nature of underlying costs to the designer with respect to errors in OPE estimates. Throughout the paper, we use the term error as shorthand for MSE when convenient, and denote by πl∗ a minimizer within some feasible class Π of logging policies. With this objective in mind, we study logging policy design under the different informational settings a designer may face when choosing the logging policy. Applications reside in a space characterized by two dimensions: knowledge of the target policy πt and knowledge of the reward distribution µ, as illustrated in Figure 2. Because the data generated by the logging policy are not yet realized at the design stage, the designer must reason beforehand about estimation error, leading to objectives based on worst-case or average error, according to the information available a priori. In Section 4, we analyze logging policies in the extreme cases of full information and no information about these quantities, and in Section 5 we extend the analysis to intermediate settings.
3
MSE Decomposition and the Reward–Coverage Tradeoff
To analyze the accuracy of OPE estimates under different logging policies, we need to understand the sources of error in the off-policy estimates. The MSE—or the risk, as it is known in statistical decision theory—of V̂IPW can be decomposed into bias and variance. This decomposition is useful 9
Figure 2: Informational settings for logging policy design . The two dimensions of information available to the logging policy designer: knowledge of the target policy πt (vertical axis), and knowledge of the reward distribution µ (horizontal axis) because the two sources call for different design strategies. Throughout, we treat context arrivals as exogenous and average over them, as they are outside the control of the logging policy designer.
3.1
Bias-Variance Tradeoff
Let Ax := {a ∈ A, πl (a|x) > 0} denote the support of πl for context x. Following the standard decomposition (see Online Appendix B), we have that !2 Bias2 :=
X
Pr(x)
x∈X
X
1 X Pr(x) Var := N x∈X X
,
a∈A / x
"
−
πt (a | x)µ(a, x)
X πt (a | x)2 a∈Ax
πl (a | x) !2
πt (a | x)µ(a, x)
! µ(a, x)
,
a∈Ax
MSE V̂IPW (πt | πl ) = Bias2 + Var. In words, a logging policy will induce bias in V̂ when it assigns zero probability to actions with non-zero expected reward that the target policy πt may select. Variance, in turn, captures error in the target policy’s IPW value estimate due to random sampling, both in terms of sampling actions and the sampling of rewards from actions. Definition 1 (Weak Overlap (Uehara et al., 2022)). A logging policy πl is said to have weak 10
overlap with respect to a target policy πt if πl (a|x) > 0
∀a ∈ A, x ∈ X where πt (a|x) > 0.
Weak overlap ensures that V (πt ) is point-identified from the data collected under πl , and is required for the IPW estimator to be unbiased. The assumption is called “weak” to distinguish it from the standard (strong) overlap assumption, which instead invokes that πl (a|x) > 0 for all a ∈ A (Uehara et al., 2022, Section 2). Strong overlap ensures unbiased evaluation of any target policy from the same logged data. Since the goal of logging policy designs is to collect data for a specific target policy, weak overlap with respect to that target is sufficient to ensure an unbiased estimate of V (πt ). Since we will be working in this setting, we henceforth refer to weak overlap simply as overlap. While overlap eliminates bias, it does not necessarily minimize MSE. When overlap fails, the IPW estimator instead targets the value of the target policy restricted to the logging support Ax , inducing bias relative to V (πt ). As shown in Online Appendix C, in small-sample or large-action settings, the increase in bias induced by this truncation can be more than offset by a substantial reduction in variance, yielding lower MSE with respect to the true policy value. More generally, when a context arrives infrequently and the action space is large, the designer may reduce MSE by excluding certain actions from the logging support. This is because the MSE can explode as πl (a|x) approaches 0, whereas bias is bounded. This implies that if the designer is concerned with minimizing MSE of the IPW estimator for a target policy’s value, they may prefer logging policies that induce bias. There are practical concerns with leaving out actions and incurring this bias, however. Leaving actions out of the support of the logging policy eliminates any signal on certain context-action pairs the logging policy designer may wish to estimate. Since variance decreases with sample size while bias does not, the optimal set of actions to sample depends on sample size, among other factors that may be outside the designer’s control..
3.2
Choice of Action Set
Having established that a biased estimator may, in certain cases, yield a lower MSE, we now provide a sufficiency condition on when to include an action in the logging support. This condition takes the form of a lower bound on the probability of the logging policy recommending an action to a given user. If an action is sampled with at least this probability, then the MSE will be lower than if the action were left unsampled (i.e. πl (a|x) = 0). 11
Proposition 1 (Sufficiency for sampling). A sufficient condition guaranteeing that the inclusion of a in Ax for some context x decreases MSE relative to a logging policy that assigns zero probability to action a at context x is if πl (a|x) > µ(a,x)(n1Pr(x)+1) . Proof. See Online Appendix A.1. This requirement serves as a guide guaranteeing that an item should be sampled. However, this is not a necessary condition. If the logging probability falls below this threshold, removing the action from the support does not necessarily improve MSE. These cases call for an exact analysis of the logging policy and the current bias and variance it induces. For our derivation of optimal solutions, we place an overlap requirement on the logging policy to avoid the complex analyses induced by these edge cases. Beyond the complexity in calculating a solution to these cases, these solutions are themselves uninformative: when a logging policy is designed so that errors are concentrated in the bias term, it effectively foregoes actually gathering any signal about the quality of the target policy. For instance, if a logging policy only collects data on actions that πt would never sample, the resulting IPW estimator produces an estimate of zero. This incurs bias but achieves zero variance by ignoring all collected data. In the smallsample or large-action regimes that are most interesting for applications, such a logging policy can yield a lower MSE than one that produces an unbiased but high-variance estimate due to small logging propensities, simply because variance then dominates the MSE. However, this type of trivial “optimization” misses the aim of off-policy evaluation which is to use data collected under one policy to estimate the value of another. Since these solutions do not provide signal on the quality of a target policy to OPE, we will focus our theoretical analyses on the problem of variance minimization, placing appropriate constraints on our claims. Specifically, in our theoretical analyses, we restrict the search space of logging policies to those satisfying overlap. We relax this restriction in Section 6.1, where we examine logging policy classes that may intentionally truncate the action support.
3.3
Reward-Coverage Tradeoff
In addition to the standard bias-variance tradeoff, there is another fundamental tradeoff that must be balanced when deciding how to allocate probability mass across actions. From the derivation in Section 3.1, we see that increasing mass on context-action pairs in πt reduces MSE, as Variance ∝ πt2 (a|x) , while adding coverage (support) to previously unsupported pairs can ensure bias reduction πl (a|x)
12
as well. This incentivizes coverage across pairs on which πt places mass. However, we also have that , so there is an incentive to place more mass on high reward pairs in µ. When πt Variance ∝ πµ(a,x) l (a|x) and µ are misaligned, this creates a tradeoff that must be managed when assigning mass in πl . As πt and µ become more aligned, this tension diminishes. To illustrate this tradeoff, consider the following example. Let there be a simple, one context (X = {x1 }), two action (A = {a1 , a2 }) setting, with the logging policy defined via a scalar value as πl := πl (a1 |x1 ). In this setting, suppose reward probabilities across items for the given user follow µ(a1 , x1 ) = .9, µ(a2 , x1 ) = .1. So using our running content platform example, in this case there is only one user (or one type of user), and two different possible streaming recommendations. One recommendation is very likely to be streamed, while the other is unlikely. Continuing, the designer aims to devise a logging policy to evaluate one of two potential target recommendation policies offline from the collected data. In the first scenario, the target policy is aligned with rewards: πt (a1 |x1 ) = .9, πt (a2 |x1 ) = .1; in other words, it is more likely to recommend the content that is more likely to be streamed, as illustrated in Figure 3(a). In this case, we see from the figure that the optimal logging policy πl∗ places nearly all its mass on a1 , yielding πl∗ ≈ .96. In the second scenario, as illustrated in Figure 3(b), the target policy is misaligned with rewards, πt (a1 |x1 ) = .1, πt (a2 |x1 ) = .9. Therefore, the logging designer must balance placing mass on those high-reward actions with placing mass on the actions likely to be selected by the target policy. For this setting, we see that the optimal logging policy sets πl∗ = .25. Note that in neither case is the optimal logging policy the same as the target policy. Therefore, even if the firm could run the target policy in vivo via an A/B test, doing so would not be the optimal strategy for evaluating its performance. This example demonstrates the need to balance two competing objectives: allocating mass on high-reward actions (reward ) and on actions the target policy may take (coverage). Matching the target policy’s distribution minimizes variance due to action sampling, making it a natural objective. However, error also arises from variance in reward realization. Rewards are stochastic, and positive outcomes may be rare. For observations with zero-valued rewards (ri = 0), the absolute error for observation i is simply πt (ai , xi )µ(ai , xi ). If positive rewards (ri = 1), the error depends inversely (ai ,xi ) on πl , and equals ππtl (a − πt (ai , xi )µ(ai , xi ). A large value of µ(ai , xi ) makes ri = 1 a more likely i ,xi )
event, so small it is much more likely to produce ri = 1, yielding an error which explodes in small πl (ai , xi ) causes this error contribution to explode. This reward-coverage tradeoff is the central challenge in logging policy design. 13
(a) Aligned setting
(b) Misaligned setting
Figure 3: Illustration of error across logging policy choices in aligned and misaligned target policies. . Panel (a) shows the MSE in the aligned setting V̂IP W (πt |πl,µ̃ ) across πl := πl (a1 |x1 ) with µ(a1 , x1 ) = .9, µ(a2 , x1 ) = .1 and πt (a1 |x1 ) = .9, πt (a2 |x1 ) = .1.The MSE-minimizing πl∗ is denoted as a star (πl∗ ≈ .96). Panel (b) shows the MSE in the misaligned setting V̂IP W (πt |πl,µ̃ ) across πl := πl (a1 |x1 ) with µ(a1 , x1 ) = .9, µ(a2 , x1 ) = .1 and πt (a1 |x1 ) = .1, πt (a2 |x1 ) = .9. The MSE-minimizing πl∗ is denoted as a star (πl∗ = .25).
4
Logging Policy Design at Informational Extrema
Based on these general considerations for logging policy design, we now examine optimal logging policies in informational extrema (see Figure 2). We restrict attention to logging policies that induce an unbiased IPW estimator V̂IPW (πt | πl ), both to keep the analysis theoretically meaningful and to reflect the practical objective of collecting data to estimate V (πt ). For these no-knowledge settings, either µ, πt , or both are unknown. In light of this, we treat the design problem as an adversarial game: the logging policy designer aims to choose πl to minimize MSE with respect to πt , while nature selects µ and πt to maximize MSE. This minimax formulation is standard in statistical decision theory and yields logging policies that are worst-case optimal. We first analyze the case where the target policy is unknown, then turn to the case where reward information is unavailable.
4.1
Unknown πt
Under a completely unknown πt , the only way to ensure overlap is to require full support across actions. With this requirement, we describe optimal logging policy design under unknown and known reward estimates.
14
4.1.1
Unknown µ
Under settings where the designer has no information about πt and no information about µ, the designer is only aware of the set of users on their platform and the set of items they can recommend. In this setting, the designer will minimize the MSE of their worst possible estimate by uniformly sampling across items. This is described below in Proposition 2. Proposition 2. For an unconstrained target policy class Π, and a logging policy requiring full support, πl∗ = πU is the designer’s solution to min
max
πl ∈Π µ∈M,πt ∈Π
MSE[V̂IPW (πt |πl )].
Proof. See Online Appendix A.2. Here, we recover the intuition from statistical inference that uniform random sampling is the best way to collect data when we have no knowledge of the estimand of interest. In that sense, uniform random sampling of actions can be seen as optimal under an uninformative prior over the target policy. Unfortunately, this approach can yield very high MSE and cause undesirable actions to be selected during logging. In our running example, this would mean selecting content for users uniformly at random, regardless of their preferences or the target policy to be evaluated. Under even modest content diversity, this approach will recommend items users are unlikely to want and that a personalized target policy will take. As a result, the logging policy may be poorly aligned with both the reward distribution and the target policy, leading to high variance in OPE estimates. Furthermore, by recommending content uniformly at random, the platform could incur a significantly degraded user experience. Of course, that is not what platforms would (or should) do in practice. This error can be mitigated as the logging policy designer will generally have an implicit or explicit prior arising from information about rewards in the sampling process. As soon as this information is known, uniform randomization ceases to be the optimal logging policy. 4.1.2
Known µ
As the designer learns more about their setting, they can design a solution that improves on uniform sampling. Consider the case where the designer knows the probabilities of reward for each useritem pair. In this case, the designer should recommend higher-reward items more often, designing a logging policy that is increasing in µ(·, x). Online Appendix A presents this worst-case analysis 15
formally and shows how under known reward distribution µ, a πl (ensuring overlap) that allocates µ mass proportional to c+µ 2 minimizes the worst-case MSE, proving the following proposition.
Proposition 3. For an unconstrained target policy class Π, and a logging policy requiring full P µ(a,x) µ(a,x) support, πl∗ (a|x) = c+µ 2 (a,x) with 1 = a∈Ax c+µ2 (a,x) is the designer’s solution to the problem min max MSE[V̂IPW (πt |πl )].
πl ∈Π πt ∈Π
Proof. See Online Appendix A.3. In this solution, c is a normalizing constant, ensuring πl∗ (·|x) comprises a valid probability distribution. Unfortunately, this constant cannot be solved for analytically, instead requiring numerical estimation. While it may not be immediately clear, this policy preserves the ordering of actions by µ(·|x) in πl∗ (·|x). In our running example, another important implication is that such a policy would be “safer” that the uniform policy, as it would be less likely to recommend content that the user would not like. Corollary 1 (Preservation of Ordering). For all a, a′ ∈ A
s.t.
µ(a, x) > µ(a′ , x),
πl∗ (a|x) >
πl∗ (a′ |x). Proof. See Online Appendix A.5. This claim builds the intuition that higher-reward actions should be sampled more. We now proceed from the logging policy designer having no knowledge of πt to having complete knowledge of the target policy.
4.2
Known πt
In practice, it is common for the set of target policies (to be evaluated) to be constrained. At the extreme, there is one target policy to evaluate and the logging policy designer knows it. In this case our results have the cleanest interpretation. At first, designing a logging policy for this setting may seem unnecessary: if there is a single, known target recommendation policy, why not just run this policy in vivo? FWhy not conduct a live A/B test of the target policy and evaluate it on-policy? Answering this question is not straightforward: as Figure 3 shows, the optimal logging policy may or may not be the target policy itself. To provide definite answers, we organize our analysis by whether the reward function is known. 16
4.2.1
Unknown µ
In the setting where the designer has no knowledge of µ, but full knowledge of πt , the designer will indeed minimize worst-case MSE by collecting data under πt itself. Proposition 4. For a policy class Π requiring full support on the support of πt , πl∗ = πt is the designer’s solution to min max MSE[V̂IPW (πt |πl )]. πl ∈Π µ∈M
Proof. See Online Appendix A.4. While the guarantee of optimality of this result is useful in these cases, it is not wholly surprising. However, in many applicable cases, this policy can be improved upon. 4.2.2
Known µ
In practice, the reward function µ is rarely entirely unknown at the time of deciding on a logging policy. Consider the case where µ is fully observed: the designer knows the probabilities that users will like each item. Using πt to log data will generally yield a sub-optimal solution. The optimal solution is presented in Proposition 5. Proposition 5. For known πt and µ and a logging policy requiring full support on the support of √ πt (a|x) µ(a,x) ∗ √ ′ minimizes MSE[V̂IPW (πt |πl )]. πt , setting πl (a|x) = P ′ a′ ∈A πt (a |x)
µ(a ,x)
Proof. See Online Appendix A.6. This result aligns with the optimality of Neyman allocation1 in stratified sampling and optimal proposal selection in importance sampling, but the connection to optimal design for OPE via IPW has not yet been shown in the literature. It is worth noting that, in the case of a deterministic πt , we do recover that the optimal logging policy for MSE-minimization in the policy value estimate is πt , meaning that on-policy evaluation is the optimal approach to data collection. In our running example, a deterministic policy would always recommend the same streaming content to a user in a particular context. Such “degenerate” policies are rarely used in practice as they are counter to standard recommendation system design principles encouraging exploration across items and diversity of recommendations. Nonetheless, this result fleshes out the design space, and is given formally in Corollary 2. 1
The Neyman allocation describes strata size selection in stratified sampling according to outcome variance and population size (Neyman, 1934).
17
Corollary 2. When πt is deterministic, setting πl := πt will minimize variance. Proof. See Online Appendix A.7. However, when πt is not degenerate, the optimal logging policy for minimizing worst-case MSE is not πt itself. Corollary 3. Denote the empirical on-policy estimator as V̂emp (πt ) = N1
PN
i=1 ri with actions
drawn according to πt . Then MSE[V̂IPW (πt |πl∗ )] ≤ MSE[V̂emp (πt )]. Proof. See Online Appendix A.8. The optimal design πl∗ in Proposition 5 has a notable side-benefit: it also weakly improves live reward accrual during the logging period, relative to running πt directly. Corollary 4. The policy value (expected accrued reward) under the optimal logging policy V (πl∗ ) ≥ V (πt ) for all valid πt and for all µ(a, x) ∈ [0, 1]. With knowledge of πt and µ, Corollaries 3 and 4 form an important joint result: This general logging policy attain a (weakly) greater value than the target policy it is derived from, and produces a more precise estimate of that target policy’s true value than running it. While emerging research on on-policy evaluation in bandit-adaptive designs highlights a tradeoff between statistical inference and regret minimization (Duan et al., 2024; Qin & Russo, 2024; Simchi-Levi & Wang, 2023), our result here demonstrates that it is possible, in certain settings, to jointly improve statistical precision and accrued regret under non-adaptive designs for off-policy evaluation. The implication for the designer of the logging policy is clear. To evaluate a single target policy, the designer should collect data under this modified solution πl∗ and perform OPE of πt on this data, rather than live testing πt .
5
Logging Policy Design in Intermediate Information Settings
In practice, the designer may not know the exact target policy they will be evaluating at logging time. A firm may anticipate evaluating several candidate policies without knowing in advance which will ultimately be deployed. For instance, it is likely the case that the currently deployed 18
(“incumbent”, “production”) policy is already quite good, and that candidate policies will therefore be derived from it. This effectively constrains the class of target policies. Such a constraint may take the form of a lower bound on policy value, membership in a given policy class, or an organizational requirement such as a maximum deviation from the incumbent policy. In this case, the target policy can be characterized as a draw from a distribution. Furthermore, the reward function µ may be only partially known. In applications, we only have an estimate of µ, for example from a machine learning model. This estimate carries uncertainty, which affects the ability to efficiently allocate sampling mass towards what to evaluate (cf. Propositions 3 and 5). Here the designer faces an intermediate information setting. For analysis, we characterize these settings by two main features. The first is that a distribution over the target policies Πt is known. This framing reflects a setting where the designer does not know the exact target policy, but has prior knowledge about the class of policies that might be evaluated. The second feature is that a noisy estimate of µ, the conditional expectation of rewards, is available at the design stage. For example, the designer has access to estimates of reward probabilities for the available items based on item features and user contexts. In recommendation systems, such an estimate is generally available from prior logged data, either via empirical frequencies after a cold-start period, or from a statistical model that generalizes over contexts. For the simulation results below, we make the further assumption that Πt is restricted to some class of “reasonable” policies.
5.1
Known Pr(πt )
We start with the case where the designer does not know the exact target policy but can formulate a prior distribution over the policy class. In this setting, a firm may wish to derive a single logging policy for the evaluation of multiple known target policies, linearly weighting the MSE of each in the overall objective. Let Πt be the distribution that πt can assume.2 Without a single πt , we now have multiple possible objectives to minimize when designing a logging policy. Our objective is to minimize expected MSE, averaging over the distribution of target policies Πt . Formally, the objective is: min Eπt ∼Πt [MSE(πt |πl )]. πl
2
This is a minor overloading of Πt , so as not to introduce too many symbols.
19
From this, we can solve for the optimal logging policy. p Proposition 6. With known Pr(πt ), define π̃t (a|x) := E[πt (a|x)2 ]. Under the overlap assumption, √ π̃t (a|x) µ(a,x) √ ′ satisfies minπt Eπt ∼Πt [MSE(πt |πl )]. πl∗ = P a′ ∈A π̃t (a|x)
µ(a ,x)
This result follows directly from the structure of the expected MSE and allows for the simple construction of a plug-in pseudo-target policy in the logging policies introduced above. Intuitively, uncertainty over the target policy is summarized by π̃t (a|x), which can be treated as a pseudo target when allocating action probabilities at logging time. We next derive a corresponding plug-in construction for µ in settings where reward estimates are noisy.
5.2
Noisy µ
For applications like recommender systems, the logging policy designer may only have partial knowledge of the reward function µ. In these cases, the designer will typically have a model-based estimate µ̂l learned from data previously collected. For instance, one may use a machine learning model that predicts the probability of a user streaming a recommendation conditional on it being impressed and given contextual features of items and the user. Even if the training dataset is large and has broad coverage, µ̂l will still tend to deviate from the true µ. Likewise, the target policy will often be derived from noisy (but potentially different) model estimates µ̂t . In Figure 4, we show how using µ̂l as a surrogate for µ can affect the resulting MSE for OPE. We simulate the performance of logging policies under uncertainty in the reward function µ by computing the MSE of target policy value estimates across a range of noise levels in reward predictions. In the simulations, we draw µ according to a geometric decay in reward probabilities across actions, as described in Online Appendix D. We produce noisy reward predictions as µ̂l (a, x) = ϵ(a, x)µ(a, x), where ϵ(a, x) ∼ N (1, σ) adds multiplicative noise and heteroskedasticity in the reward predictor. To generate a target policy πt , we analogously construct µ̂t (a, x) = ϵ(a, x) µ(a, x).3 We then define the target policy to evaluate, πt , to place equal probability mass on the top 30 actions ranked by µ̂t (· | x) for each context x. This target policy reflects the usual desire in recommendation systems of balancing immediate reward accrual with exploration and diversity of recommendations, and is in the spirit of the top-k policy we consider in the next subsection. Note that a fully greedy 3
The standard deviation of this noise is chosen empirically to be .25 to ensure a “good” (see the figure) but not perfect target policy.
20
(top-1) target policy would instead coincide with the optimal logging policy, as discussed earlier. Full simulation details are provided in Online Appendix D. Figure 4 shows the MSE for estimating the value of πt from various logging policies, as a function of the level of noise σ in the reward predictor µ̂l . We observe that the MSE of offpolicy evaluation under this logging policy varies with the precision of µ̂l , and may be lower, equal to, or higher than that of on-policy evaluation. Still, some excess error relative to on-policy evaluation is generally tolerable, as off-policy evaluation is often preferred or necessary due to practical constraints. Nonetheless, we show in the next subsection that the designer can mitigate this risk of off-policy evaluation by shrinking the reward predictions toward a per-context mean, reducing the effective noise in the off-policy evaluations from optimized logging policy designs compared to plugging-in reward estimates directly.
Figure 4: MSE as a function of the level of noise in the reward estimates µ̂. . The (red) dashed line shows the MSE of on-policy estimation. Estimation with the “optimal” logging policy can be either better or worse than on-policy estimation, depending on how noisy the reward estimates are, with a convex shape of the expected error in the noise in reward estimates.
5.3
Posterior Shrinkage
When the reward function µ is not known exactly, it is often suboptimal to use µ̂l as a plug-in estimator for designing logging policies. Intuitively, the uncertainty in µ increases as the error in µ̂l grows. In the extreme where noise dominates variation in estimates, µ̂l carries little information about µ. Allocating probability mass toward such estimates could produce logging policies that perform worse than uniform randomization. 21
This observation motivates using some degree of posterior shrinkage: we want our reward predictor to shrink towards a per-context average the more uncertain its reward prediction is for a given context-action pair. This form of shrinkage is closely related to empirical Bayes estimators under hierarchical models, where noisy conditional point estimates are pulled to a common mean to reduce the MSE of an estimator (Efron & Morris, 1973; Robbins, 1956). We now derive a practical procedure for implementing posterior shrinkage in logging policy designs for off-policy evaluation via the IPW estimator. This enables the designer to regularize noisy reward estimates toward more stable logging policies. Theoretical derivation of shrinkage weight Optimal shrinkage varies in how reward probabilities are distributed per context and how noise is distributed in reward estimates. We make standard assumptions on each to make this problem tractable. To arrive at a simple and interpretable shrinkage rule, we adopt the following hierarchical Gaussian prior. First, we assume that the reward predictor is Gaussian distributed about the underlying reward function with fixed variance ε2 representing noise: µ̂(a, x) ∼ N µ(a, x), ε2 . We then assume that the reward function µ(a, x) itself is normally distributed about the per-context, across-action mean reward m(x) with variance σ 2 : µ(a, x) ∼ N m(x), σ 2 . This yields the posterior
µ(a, x)|µ̂(a, x) ∼ N
µ̂(a,x) + m(x) 1 ε2 σ2 , 1 1 1 + σ2 + σ12 ε2 ε2
! .
Rewriting, we get the posterior mean σ 2 µ̂(a, x) + ε2 m(x) E[µ(a, x)|µ̂(a, x)] = . ε2 + σ 2 Hence, given the reward predictor, the expected value of the underlying reward function is a linear combination of the predictor µ̂ and the true per-context expectation m(x). 22
Letting µ̃ := E[µ(a, x)|µ̂(a, x)], we have the form µ̃(a, x) = (1 − w)µ̂(a, x) + wm(x) for some shrinkage weight w ∈ [0, 1] based on the ratio of the estimation variance ε2 and cross-action variability σ 2 ; that is, w = ε2 /(ε2 + σ 2 ). Figure 5a illustrates the effect of using the posterior shrinkage predictor µ̃ for different values of the shrinkage weight w. We see that when noise is present in µ̂, moderate shrinkage toward the per-context mean reward reduces MSE for estimating the target policy value, and may even produce estimates of the target policy’s value that are more accruate than running the target policy and calculating empirical reward (i.e., on-policy evaluation) .4 As the shrinkage weight approaches 1, the shrinkage effect cancels out across actions and the correction toward the mean reward disappears. However, the shrinkage weight of the policy must be applied ex ante, prior to data collection under the logging policy. As a result, empirical grid search over values of w is infeasible in practice. We therefore require a principled method for selecting the shrinkage weight based on information available at the time of logging policy design. We now discuss how to do so using evaluation-set level metrics on µ̂. With full information about µ and µ̂, the optimal shrinkage can be solved analytically. In practice, however, we observe only the realized reward r for context-action pairs in prior data, which affects our accuracy of µ̂ and knowledge of µ across all action-context pairs. This reflects the bandit feedback setting and the fundamental problem of causal inference. To that end, we use proxies m(x) ≈ µ̄(x) and ε2 +σ 2 ≈ Var(µ̂(· | x)) to establish the expectation of the prior of µ the the total variance of µ̂. We now use logged data to estimate the quality of the estimate function µ̂ with metrics that serve directly as plug-in estimators for computing w∗ . To estimate σ 2 directly, we can use observed rewards from any previously collected data, sampled under any logging policy, for which we also have the reward predictions on the same context-action pairs. We then use the following identity, which holds exactly under the mean-zero noise assumption on µ̂, to approximate the variance of µ: Cov(µ̂(X, A), R) = E[µ̂(X, A) · R] − E[µ̂(X, A)]E[R]. 4
Simulation parameters are presented in Online Appendix D.
23
Using the decomposition, E[µ̂(X, A) · R] = E[E{µ̂(X, A) · R | µ(X, A)}]
(3)
= E[E{µ̂(X, A) | µ(X, A)}] · E[R | µ(X, A)]
(4)
= E[µ(X, A) · µ(X, A)]
(5)
= E[µ(X, A)2 ],
(6)
we arrive at the form Cov(µ̂(X, A), R) = E[µ(X, A)2 ] − E[µ̂(X, A)]E[R]. By the mean-zero noise assumption on µ̂ and with R drawn from i.i.d. Bernoulli trials, we then have Cov(µ̂(X, A), R) = E[µ(X, A)2 ] − E[µ(X, A)]2
(7)
= Var[µ(X, A)]
(8)
= σ2.
(9)
Specifically, we leverage an auxiliary dataset {(xi , ai , ri )}M i=1 of realized context, action, reward triples, over which µ̂(xi , ai ) is defined for all i ∈ {1, . . . , M }. So, we can approximate the optimal shrinkage weight w∗ empirically as w∗ = 1 − ≈1−
Cov[µ̂(X, A), R] Var[µ̂(X, A)] d M [µ̂(xi , ai ), ri ] Cov
(10) (11)
d M [µ̂(xi , ai ) Var where the hat and sample size subscripts denote that these are the empirical covariance and variance. This yields the posterior-shrinkage predictor of rewards as µ̃∗ (a|x) = (1 − w∗ )µ̂(a|x) + w∗ µ̄(x). The data used for computing Equation (10) should be held out from the data used to train µ̂ to avoid optimistic bias in the estimate of w∗ . Otherwise, the fit of µ̂ will inflate the empirical 24
covariance in the numerator, biasing w∗ downward. Figure 5b demonstrates the efficacy of this approach through simulation, using simulation parameters similar to those described above, which are described in detail in Online Appendix D. We see in that even when the underlying distribution of µ and µ̂ is not Gaussian, this weight selection rule is still effective and can still yield MSE that is better than on-policy evaluation.
(a) MSE as a function of shrinkage weight
(b) MSE and policy value under shrinkage
Figure 5: Effect of posterior shrinkage and reward prediction noise on MSE and policy value . A ∗ ∗ ∗ demonstration of MSE(πt |πl,µ̃ ) and V (πl,µ̃ )) with πl,µ̃ constructed according to various shrinkage values and noise values in estimates. Shrinkage weights w∗ are constructed according to our approximate solution. Panel (a) plots the expected MSE of the IPW estimator for estimating V (πt ) as a function of the shrinkage weight w, across different noise levels in the reward predictor µ̂. Stars represent the shrinkage weight computed according to the derived shrinkage rule and associated MSE of the derived optimal policy across each of 30 trials. “Target Policy Error” represents the MSE of on-policy value estimator, obtained as the sample average observed reward on data from the target policy. Panel (b) reports the MSE of V̂IPW (πt | πl,µ̃ ) and the logging policy value V (πl,µ̃ ) when using the reward predictor µ̃∗ constructed according to the empirically optimal shrinkage weight w∗ , compared to on-policy evaluation of πt , and across noise in the estimates of µ̂ (30 trials per noise level). Even across levels of noise, the optimal logging policy yields greater expected reward during the logging period and lower MSE in estimating the target policy value than on-policy evaluation, both as byproducts of the MSE-minimizing design. Simulation details are provided in Online Appendix D.
6
Discussion
In some settings, designers may have limited ability to specify policy classes. We now provide highlevel guidance on how a designer can choose which logging policy to implement, viewed through the lens of the reward-coverage tradeoff described in Section 3.3.
25
6.1
Restrictions on Πl
In practical settings, there may be organizational or technical reasons why the designer is not able to deploy or justify deploying the exact optimal logging policy for minimizing MSE. For example, a fully greedy optimal logging policy may not be deployable due to the firm’s desire to maintain diversity in recommendations. Alternatively, a logging policy that strays far from known highreward actions may be deemed risky. To capture such constraints, we consider logging policies indexed by a single “greediness’ parameter that trades off mass on high-reward actions against broader coverage of actions the target policy may take. We next demonstrate how MSE varies with this greediness parameter across two logging policy classes. These classes describe mappings from reward estimates to policies. Importantly, these classes can be used to define target policies in addition to logging policies. Their use as target policies describe some simple model of production recommendations with a dial balancing exploration and exploitation that could be made by the downstream, target policy designer. However, our analysis focuses on the efficacy of these classes for logging policy design. We define a (fully) greedy policy to be one that deterministically selects the action per context x with highest predicted reward; that is A = arg maxa∈A µ̂t (a, x) for all x ∈ X . We begin by examining how the MSE from off-policy evaluation with the IPW estimator varies as a logging policy shifts from fully greedy to uniformly random. We refer to policies at intermediate values of this parameter as soft-greedy. To assign this level of greediness to a scalar value, we define three related policy classes: top-k, power-normalized and softmax. top-k Policy Class n
o The top-k policy space ΠT K (µ̂) := πk : k ∈ 1, . . . , |A| , is the set of policies πk that assign equal weight to the k ≤ |A| actions with the highest values of µ̂(A, X) for each context X = x. Thus, πk=1 is the fully greedy policy and πk=|A| is the fully uniform policy. Softmax Policy Class n αµ̂(a,x) := The softmax policy space smoothly adjusts for greediness: ΠSM (µ̂) πα , πα (a|x) = P ′ e eαµ̂(a′ ,x) : ∀α ∈ a ∈A o [0, ∞) . Here, α = 0 corresponds to the uniform policy while α = ∞ equates to a greedy policy. Because this class of logging policies places probability mass on all actions for α ∈ [0, ∞), softmax policies ensure the IPW estimator V̂ (πt | πl ) is unbiased for any target policy V (πt ) even if this 26
mass is very small. This policy is directly related to Boltzmann sampling. Power-normalized Policy Class The power-normalized policy space also smoothly adjusts for greediness. The class is defined as n o d ΠP N (µ̂) := πd , πd (a|x) = P ′ µ̂ (a,x) : ∀ d ∈ [0, ∞)] . Here, d = 0 corresponds to the uniform µ̂d (a′ ,x) a ∈A
policy while d = ∞ equates to a greedy policy. This policy also enjoys the same property of ensuring weak overlap with any target policy, as long as reward estimates are bounded away from 0.
6.2
Simulations Across Logging Policy Classes
We simulate how the choice of greediness affects the MSE of IPW estimates using a simulated environment, detailed in Online Appendix D . Here, πt is defined to be the top-200 policy based on µ̂t . Figure 6 shows the results for small (N = 1000) and large (N = 100, 000) sample-size settings, where the target policy πt is a top-200 policy based on µ̂t and a large action space of |A| = 100, 000. We see that even these substantially constrained logging policy classes can achieve strong performance, approaching the MSE of the theoretical optimum, and in some cases matching or improving upon on-policy evaluation as a natural benchmark when the greediness parameter is chosen appropriately. In both the small-sample and large-sample settings, well-tuned top-k policies substantially outperform softmax policies, with optimal values of k around 200. This result demonstrates that narrowing the logging support toward high-reward actions—intentionally incurring some bias—can reduce overall MSE relative to policies that enforce overlap (i.e., softmax and power-normalized ). As the sample size increases, the policies that enforce overlap perform relatively better. This is driven by the fact that bias does not shrink in sample size, but variance does. This phenomenon is also what leads the optimal k value to be larger in the large sample-size setting. Likewise, powernormalized policies also perform well in the large-sample regime. With appropriate tuning, they approach the performance of top-k while controlling worst-case MSE over a reasonable range d. Yet, for any finite sample size, as d and α approach ∞ (i.e. approaching greedy), MSE approaches infinity. The strong performance of top-k policies and bounded error near greedy suggest that truncating support can improve MSE when logging propensities are small relative to sample size. This findings is consistent with the sufficiency condition in Proposition 1.
27
More generally, these results show that simple soft-greedy approaches to logging policy design can yield substantial improvements in off-policy evaluation relative to uniform logging, although their performance benefit depends heavily on the choice of greediness parameter. Moreover, the inability for the biased top-k policy to reduce error relative to the variance-optimal policy described in Proposition 5 suggests that restricting the optimal policy derivation to variance minimization does not sacrifice the performance gains available from intentionally incurring bias. We examine further heuristic variants in Online Appendix D. MSE1 of Soft-Greedy Policies Across Uniformity Parameters (|A| = 100000; N = 1000) 10
Softmax ( * = 71.46, w/ MSE = 1.94e 03) Top-k (k * = 181, w/ MSE = 3.93e 05) Power-normalized (d * = 0.91, w/ MSE = 5.04e 05)
MSE of Soft-Greedy Policies Across Uniformity Parameters (|A| = 100000; N = 1000000)
Target (MSE=4.14e-05) Optimal (MSE=3.81e-05) Uniform (MSE=2.16e-02)
10 2
Target (MSE=4.14e-08) Optimal (MSE=3.81e-08) Uniform (MSE=2.16e-05)
10 4
MSE
MSE
Softmax ( * = 66.34, w/ MSE = 2.49e 06) Top-k (k * = 249, w/ MSE = 5.20e 08) Power-normalized (d * = 0.91, w/ MSE = 5.21e 08)
10 3
10 3
10 5
10 6
10 4 10 7
120
108
96
84
36
24
12
0
120
108
96
84
36
24
12
0
6.0
5.4
4.8
4.2 3.6 3.0 2.4 1.8 Power-normalized Uniformity (d)
1.2
0.6
0.0
6.0
5.4
4.8
4.2 3.6 3.0 2.4 1.8 Power-normalized Uniformity (d)
1.2
0.6
0.0
101
102 103 Top-k Uniformity (k, log scale)
104
105
100
101
102 103 Top-k Uniformity (k, log scale)
104
100
72 60 48 Softmax Uniformity ( )
(a) Small action space |A| = 1, 000.
72 60 48 Softmax Uniformity ( )
105
(b) Large action space |A| = 100, 000.
Figure 6: MSE of IPW estimator for soft-greedy logging policy classes top-k and softmax. . Simulation evidence of the MSE of the IPW estimator as a function of the greediness parameter for the top-k, softmax, and power-normalized logging policy classes. The left edge of the x axis of each panel corresponds to (near) greedy logging, while the right edge corresponds to uniform random logging. The MSE is measured with respect to the value (expected reward) of a top-k (k = 200) target policy based µ. ”Target” shows the MSE of running the target policy, if it were known. Panel (a) shows that the MSE-minimizing top-k logging policy occurs at k ∗ = 181, yielding MSE = 3.93 × 10−5 ; the MSE-minimizing softmax parameter is α∗ = 71.46, yielding MSE = 1.94 × 10−3 ; and the SEminimizing power-normalized degree is d∗ = .91, yielding MSE = 5.04 × 10−5 . Panel (b) shows analogous results for the large sample-size setting, with MSE-minimizing top-k being k ∗ = 249 for the top-k logging policy, yielding MSE = 5.20 × 10−8 ; the MSE-minimizing α value for softmax is α∗ = 66.34, yielding MSE = 2.49 × 10−6 ; and the MSE-minimizing degree d for softmax is d∗ = .91, yielding MSE = 5.21 × 10−8 . Full simulation details are in Online Appendix D Selecting the greediness parameter in practice can be guided by the simulation results above. When the target policy class is known, k can be initialized at the target policy’s approximate support size, as the MSE-minimizing k closely tracks this quantity across both sample-size regimes. For power-normalized policies, d can be tuned analogously via held-out MSE evaluation. For soft28
max policies, α lacks a direct analytical interpretation and should be selected via held-out MSE evaluation; however, given the consistently weaker performance of softmax relative to top-k and power-normalized across our simulations, the latter two classes are generally preferable when the action space is large. When the target policy is unknown, a moderately soft-greedy policy is preferable to a fully greedy one, since bias from support truncation does not diminish in sample size. In all of these settings, a natural approach is to treat the parameter as a hyperparameter and select it by computing IPW estimates of a reference policy’s value on historically collected data, choosing the value that minimizes the resulting MSE. This requires only prior logged data and reward predictions — both available before the logging period begins.
7
Related work
The closest body of related work is the nascent stream examining the design of safe logging policies. In the most closely related work, Wan2022Safe<empty citation> describe the design of safe logging policies to evaluate bandit policies offline. Here, safety is defined as the value of the logging policy (average reward accrual) being no less than some fixed proportion of the value of a baseline policy. The authors highlight standard approaches, involving a mixture between some given policy and a uniform exploration logging policy. Under hard safety and sample budget constraints, the authors derive optimal logging policies for various bandit agents to best study the difference in policy values relative to some baseline policy. Other works study the augmentation of logging policies for better OPE. Tucker and Joachims (2023) is most similar in scope to ours, but describes a method for adding observations. The resultant method confirms the intuition behind our solution to the fully observable problem. Demonstrating the sub-optimality of an ϵ-mixing approach, Zhu and Kveton (2022) cast logging policy design as an optimal experimental design problem. These authors design an optimal solution derived from G-optimal design which describes the quality of a logging policy in terms of information gain. Their optimal policy follows a “water-filling” method, ensuring the minimal action-context pairs have equal propensity scores. However, this derived policy is tailored to off-policy learning, not to off-policy evaluation. T. Li et al. (2023) study optimal treatment allocation for OPE in sequential decision-making problems. The authors here propose allocating more samples to actions where IPW estimates would 29
be noisy, due to the target policy or due to reward variance. Our approach follows a similar thread, where we highlight that a reward-coverage tradeoff needs to be balanced in designing a logging policy; however, we note that mass needs to be allocated explicitly toward high-reward items, not high-variance-in-reward items. An emerging literature focuses on developing estimators for use in experimental data under various assumptions. Sakhi et al. (2025) describe a more efficient estimator of the ATE of treatment policies when run via A/B tests. This estimator leverages overlap in the treatment policies being tested, a key factor we consider when designing logging policies. L. Li et al. (2015) consider the worst case estimation error in a similar setup to one of our “informational settings.” Their results focus on describing bounds on minimax squared error across several estimators; we focus on the optimal design of logging policies to achieve minimal squared error. Ma et al. (2022) study minimax optimality in a similar setting but propose a switch estimator to achieve an optimal competitive ratio on this risk. Their work looks at this risk under varying levels of knowledge about the logging policy, whereas our work designs the logging policy under varying levels of knowledge about the setting. Another part of this literature focuses on how to conduct statistical inference on data that has been adaptively collected via a bandit algorithm (Bibaut & Kallus, 2025; Bibaut et al., 2021; H. Chen et al., 2021; Shen et al., 2024; Zhang et al., 2020, 2021). A closely related stream of work focuses specifically on how to conduct OPE in contextual bandits (Wang et al., 2017; Zhan et al., 2021). Our work differs in that we focus on how to collect data for a given OPE estimator. Because the logging policy is non-adaptive, the OPE estimator can be applied as usual while retaining its properties for statistical inference. Other recent research focuses on the online problem of simultaneous regret minimization and statistical inference on treatment arms, and the trade-off between the two objectives (Duan et al., 2024; Simchi-Levi & Wang, 2023). We do not focus on regret minimization or online inference. Nonetheless, our result that uniform logging is worst-case optimal for OPE (yet can accrue arbitrarily poor rewards) hints at a broader trade-off between data collection performance and what can be learned from it. Taken together, the above literature emphasizes either safety constraints, designing efficient estimators, or a trade-off between regret minimization and statistical inference. Our contribution instead centers on the design of logging policies to minimize policy-value estimation error under informational constraints. This design perspective connects our problem to two foundational liter30
atures. The general problem of choosing assignment probabilities to improve estimator precision traces back to optimal experimental design, beginning with Wald (1943) and developed through geometric and information-based criteria (Elfving, 1952; Kiefer, 1959). For recent surveys through an optimization lens, see Xiong (2025, Sections 1 and 2) and Zhao (2024). In this classical literature, treatment probabilities are selected to minimize the variance of an estimator of the average treatment effect, typically under a parametric outcome model. In contrast, our work considers the design of logging policies for off-policy evaluation, with the objective of minimizing MSE of a policy value estimate based on inverse propensity weighting. As such, we do not aim to maximize precision of an average contrast in potential outcomes, but rather minimize the estimation error of the average potential outcome under a counterfactual treatment assignment mechanism. Our logging policy solutions can be viewed as contextual analogs of unequal-probability sampling for the Horvitz–Thompson estimator (Horvitz & Thompson, 1952), where action probabilities are chosen to control MSE. From an importance-sampling perspective, our results reflect the trade-off between variance inflation due to small proposal probabilities and bias from truncating the support of the proposal distribution (e.g., Ionides, 2008). A second connection is to empirical Bayes methods for statistical decision problems, initiated by Robbins (1956, 1964). In the empirical Bayes framework, parameters are treated as draws from an unknown prior, estimated from data and then substituted into the Bayes decision rule. Under an MSE criterion, optimal solutions to this problem formulation yield shrinkage estimators that reduce risk relative to naive plug-in estimation (see, e.g., Efron & Morris, 1973). In our setting, direct plug-in estimators inflate the variance of induced inverse propensity weights when reward parameters are estimated with noise, but this can be mitigated via posterior shrinkage applied to the reward model’s estimates. As such, our solution admits an empirical Bayes interpretation that reduces MSE of the IPW estimator while improving reward accrual during logging.
8
Conclusion and Future Work
This paper presents a unified framework for the optimal design of logging policies for off-policy evaluation. The central insight is that the logging policy is not merely a data collection mechanism. Instead, it is a design choice with direct consequences for the statistical quality of downstream policy evaluation. To this end, we frame logging policy design as the problem of minimizing the MSE of 31
the IPW estimator, which is a simple and model-free estimator. Our analysis shows how firms can make principled, theoretically grounded choices about how to collect data for OPE, rather than relying on ad hoc heuristics, safety-only constraints, or uniform randomization as a conservative fallback. Beyond this takeaway for practice, our work makes several contributions to the literature. First, it provides a clean sufficiency condition on when an action should be covered by the logging policy, while noting that there is no simple closed-form expression for when an action should be included. We describe a fundamental reward-coverage tradeoff that needs to be balanced when designing a logging policy for use in OPE. We then provide optimal solutions to the problem of minimizing MSE of off-policy evaluation with the IPW estimator in settings of informational extremes. As part of our results, we note an important byproduct of the optimal logging policy: in certain settings, the optimal logging policy accrues higher expected reward than the target policy during the logging period, and yields an IPW estimate with lower MSE than the empirical on-policy estimator. The paper extends these findings in informational extremes to intermediate settings, and describes the construction of tractable logging policies for settings where reward probabilities are not exactly known. Finally, the paper provides more general insights into balancing the rewardcoverage tradeoff when the theoretically optimal logging policy cannot be deployed. In particular, we provide approximate, soft-greedy methods for balancing these considerations and demonstrate that these can attain strong performance by balancing logging mass between high-reward items and coverage across items the target policy is likely to sample. Taken together, our results provide a principled basis for logging policy design. The framework clarifies when and why different logging strategies are appropriate, and gives firms concrete tools for improving offline experimentation efforts within their operational and organizational constraints. Limitations. The results of this paper rely on several assumptions. The first assumption is that the IPW estimator is used for the off-policy evaluation. By being free of a reward model, this estimator decouples the design stage from the estimation stage. For model-based estimators such as the direct method or doubly robust, complications may arise when the outcome model used in estimation is correlated with the reward model used to design the logging policy. Extending our framework to such estimators is left for future work. Another limitation is that our theoretical results rely on weak overlap, leading our MSE minimization to reduce to variance minimization. In the sample limit, variance dominates bias, so the derived policies minimize MSE. In small-sample 32
regimes, however, inducing bias can improve MSE relative to the variance-optimal policy, as we demonstrate through counterexample. Future work. There are several dimensions to explore further in future work. The first is a generalization of these results to arbitrary real-valued rewards. Similar extensions could expand on more sophisticated recommendation settings, such as slate-based or sequential recommendations. A second direction is optimal parameter selection for common soft-greedy policies. Finally, exploring logging policy design experimentally could yield insights into the practical performance of our theoretically derived policies.
References Bibaut, A., Dimakopoulou, M., Kallus, N., Chambaz, A., & van Der Laan, M. (2021). Postcontextual-bandit inference. Advances in Neural Information Processing Systems, 34, 28548– 28559. Bibaut, A., & Kallus, N. (2025). Demystifying inference after adaptive experiments. Annual Review of Statistics and its Application, 12 (1), 407–423. Chen, H., Lu, W., & Song, R. (2021). Statistical inference for online decision making: In a contextual bandit setting. Journal of the American Statistical Association, 116 (533), 240–255. Chen, M., Beutel, A., Covington, P., Jain, S., Belletti, F., & Chi, E. H. (2019). Top-k off-policy correction for a reinforce recommender system. Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, 456–464. https://doi.org/10.1145/3289600. 3290999 Chesnaye, N. C., Stel, V. S., Tripepi, G., Dekker, F. W., Fu, E. L., Zoccali, C., & Jager, K. J. (2022). An introduction to inverse probability of treatment weighting in observational research. Clinical Kidney Journal, 15 (1), 14–20. Duan, C., Ma, W., Jiang, J., & Xia, D. (2024). Regret minimization and statistical inference in online decision making with high-dimensional covariates. arXiv preprint arXiv:2411.06329. Dudı́k, M., Erhan, D., Langford, J., & Li, L. (2014). Doubly robust policy evaluation and optimization. Statistical Science, 29 (4), 485–511. Efron, B., & Morris, C. (1973). Stein’s estimation rule and its competitors—an empirical Bayes approach. Journal of the American Statistical Association, 68 (341), 117–130. 33
Elfving, G. (1952). Optimum allocation in linear regression theory. The Annals of Mathematical Statistics, 255–262. Fernández-Lorı́a, C., Provost, F., Anderton, J., Carterette, B., & Chandar, P. (2022). A comparison of methods for treatment assignment with an application to playlist generation. Information Systems Research, 33 (3), 786–803. https://doi.org/10.1287/isre.2022.1149 Hernán, M. A., & Robins, J. M. (2020). Causal inference: What if. Horvitz, D. G., & Thompson, D. J. (1952). A generalization of sampling without replacement from a finite universe. Journal of the American Statistical Association, 47 (260), 663–685. Imbens, G. W., & Rubin, D. B. (2015). Causal Inference in Statistics, Social, and Biomedical Sciences. Cambridge University Press. Ionides, E. L. (2008). Truncated importance sampling. Journal of Computational and Graphical Statistics, 17 (2), 295–311. Kiefer, J. (1959). Optimum experimental designs. Journal of the Royal Statistical Society: Series B (Methodological), 21 (2), 272–304. Li, L., Munos, R., & Szepesvari, C. (2015, September). Toward minimax off-policy value estimation. In G. Lebanon & S. V. N. Vishwanathan (Eds.), Proceedings of the eighteenth international conference on artificial intelligence and statistics (pp. 608–616, Vol. 38). PMLR. https : //proceedings.mlr.press/v38/li15b.html Li, T., Shi, C., Wang, J., Zhou, F., & Zhu, H. (2023). Optimal treatment allocation for efficient policy evaluation in sequential decision making. Advances in Neural Information Processing Systems 36 (NeurIPS). Ma, C., Zhu, B., Jiao, J., & Wainwright, M. J. (2022). Minimax off-policy evaluation for multiarmed bandits. IEEE Transactions on Information Theory, 68 (8), 5314–5339. https://doi. org/10.1109/TIT.2022.3162335 Murphy, S. A., van der Laan, M. J., Robins, J. M., & Group, C. P. P. R. (2001). Marginal mean models for dynamic regimes. Journal of the American Statistical Association, 96 (456), 1410– 1423. Neyman, J. (1934). On the two different aspects of the representative method: The method of stratified sampling and the method of purposive selection. Journal of the Royal Statistical Society, 97 (4), 558–606. https://doi.org/10.1111/j.2397-2335.1934.tb04184.x
34
Persson, J. (2024). Causal ML in Recommender Systems: On Contextual Bandits, Off-Policy Evaluation, and Bias (NABE TEC 2024 Presentation). Retrieved January 14, 2026, from https: //www.youtube.com/watch?v=Hi4EThF2d3U&t=19245s Qin, C., & Russo, D. (2024). Optimizing adaptive experiments: A unified approach to regret minimization and best-arm identification. arXiv preprint arXiv:2402.10592. Robbins, H. (1956). An empirical bayes approach to statistics. Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, 3, 157–164. Robbins, H. (1964). The empirical Bayes approach to statistical decision problems. The Annals of Mathematical Statistics, 35 (1), 1–20. Sakhi, O., Gilotte, A., & Rohde, D. (2025). Practical improvements of a/b testing with off-policy estimation. https://doi.org/10.48550/arXiv.2506.10677 Shen, Y., Cai, H., & Song, R. (2024). Doubly robust interval estimation for optimal policy evaluation in online learning. Journal of the American Statistical Association, 119 (548), 2811–2821. Simchi-Levi, D., & Wang, C. (2023). Multi-armed bandit experimental design: Online decisionmaking and adaptive inference. International Conference on Artificial Intelligence and Statistics, 3086–3097. Sutton, R. S., & Barto, A. G. (1998). Reinforcement learning: An introduction (Vol. 1). MIT Press Cambridge. Thomas, P., Theocharous, G., Ghavamzadeh, M., Durugkar, I., & Brunskill, E. (2017). Predictive off-policy policy evaluation for nonstationary decision problems, with applications to digital marketing. Proceedings of the AAAI Conference on Artificial Intelligence, 31 (2), 4740–4745. https://doi.org/10.1609/aaai.v31i2.19104 Tucker, A. D., & Joachims, T. (2023). Variance-minimizing augmentation logging for counterfactual evaluation in contextual bandits. Proceedings of The Web Conference (WWW). Uehara, M., Shi, C., & Kallus, N. (2022). A review of off-policy evaluation in reinforcement learning. arXiv preprint arXiv:2212.06355. Wald, A. (1943). On the efficient design of statistical investigations. The Annals of Mathematical Statistics, 14 (2), 134–140. Wang, Y.-X., Agarwal, A., & Dudık, M. (2017). Optimal and adaptive off-policy evaluation in contextual bandits. International Conference on Machine Learning, 3589–3597.
35
Xie, Y., Feng, Y., & Li, L. (2018). Off-policy evaluation and learning from logged bandit feedback. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 1505–1513. Xiong, R. (2025). Automated experimental design with optimization from historical data simulations. Available at SSRN 5126080. Zhan, R., Hadad, V., Hirshberg, D. A., & Athey, S. (2021). Off-policy evaluation via adaptive weighting with data from contextual bandits. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2125–2135. Zhang, K., Janson, L., & Murphy, S. (2020). Inference for batched bandits. Advances in Neural Information Processing Systems, 33, 9818–9829. Zhang, K., Janson, L., & Murphy, S. (2021). Statistical inference with m-estimators on adaptively collected data. Advances in Neural Information Processing Systems, 34, 7460–7471. Zhao, J. (2024). Experimental design for causal inference through an optimization lens. In Tutorials in operations research: Smarter decisions for a better world (pp. 146–188). INFORMS. Zhu, R., & Kveton, B. (2022). Safe optimal design with applications in off-policy learning. International Conference on Artificial Intelligence and Statistics, 2436–2447.
36
Online Appendix
A
Additional Proofs
A.1
Proof of Proposition 1
Proof. Fix a context x and set of actions Ax which receive support by πl (·|x). Now, we show that the addition of some action a′ ∈ / Ax to Ax will reduce MSE if πl (a′ |x) > µ(a′ ,x)(n1Pr(x′ )+1) . If mass were placed on a′ meeting this criteria, we have the following derivation: πl (a′ |x) >
1 µ(a′ , x′ )(n Pr(x′ ) + 1)
1 πl (a′ |x′ ) πt (a′ |x′ )2 µ(a′ , x′ ) ⇐⇒ (N Pr(x′ ) + 1)πt (a′ |x′ )2 µ(a′ |′ x)2 > ′ ′ πl (a |x ) πt (a′ |x′ )2 ⇐⇒ N Pr(x′ )πt (a′ |x′ )2 µ(a′ , x′ )2 > µ(a′ , x′ ) − πt (a′ |x′ )2 µ(a′ , x′ )2 πl (a′ |x′ ) πt (a′ |x′ )2 1 ′ ′ ′ ′ 2 ′ ′ 2 ′ ′ 2 ′ ′ 2 µ(a , x ) − πt (a |x ) µ(a , x ) . ⇐⇒ πt (a |x ) µ(a , x ) > N Pr(x′ ) πl (a′ |x′ ) Pr(x′ ) πt (a′ |x′ )2 ′ ′ ′ ′ 2 ′ ′ 2 ′ 2 ′ 2 ′ ′ 2 µ(a , x ) − πt (a |x ) µ(a , x ) . ⇐⇒ Pr(x ) πt (a |x) µ(a , x ) > N πl (a′ |x′ ) ⇐⇒ (N Pr(x′ ) + 1)µ(a′ , x′ ) >
We now manipulate the RHS to show that this quantity is at least the increase in the variance from sampling action a′ with probability πl > µ(a′ ,x′ )(n1Pr(x′ )+1) . For notational simplicity, let V (X \ 2 P P P 2 π (a|x) t ′ ′ {x′ }) := N1 x∈X \{x′ } Pr(x) denote the variance a∈Ax πl (a|x) µ(a, x ) − a∈Ax′ πt (a|x)µ(a, x ) term contributed by all contexts other than x′ which are added linearly. The RHS of the above
38
inequality is then
πt (a′ |x′ )2 Pr(x ) X πt (a|x′ )2 ′ µ(a, x ) + µ(a′ , x′ ) ′) ′ |x′ ) N π (a|x π (a l l a∈Ax′ 2 X − πt (a|x′ )µ(a, x′ ) + πt (a′ |x′ )µ(a′ , x′ ) + V (X \ {x′ }) ′
∆Variance :=
a∈Ax′
|
{z
−
}
Variance of setting πl (a′ |x′ )>0 ′
X πt (a|x′ )2
Pr(x ) N a∈A
x′
πl (a|x′ )
2
µ(a, x′ ) −
X
πt (a|x′ )µ(a, x′ ) + V (X \ {x′ })
a∈Ax′
|
{z
}
Variance of setting πl (a′ |x′ )=0
′
′
2
′ 2
Pr(x ) πt (a |x ) µ(a′ , x′ ) − πt (a|x′ )µ(a, x′ ) + πt (a′ |x′ )µ(a′ , x′ ) ′ ′ N πl (a |x ) a∈Ax′ 2 X + πt (a|x′ )µ(a, x′ ) X
=
a∈Ax′
Pr(x′ ) πt (a′ |x′ )2 ′ ′ ′ ′ 2 ′ ′ 2 µ(a , x ) − πt (a |x ) µ(a , x ) ≤ N πl (a′ |x′ ) Likewise, we now manipulate the LHS to show that this term is no more than the increase in bias squared—that is, the other component of the MSE decomposition—from not sampling action a′ . Similarly, let B(X \ {x′ }) correspond to the bias contributed by all contexts other than x′ , with P P B(X \ {x′ }) := x∈X \{x′ } Pr(x) a∈A / x πt (a|x)µ(a, x). The LHS of the inequality is then !2 B(X \ {x′ }) + Pr(x′ )
∆Bias2 :=
X
πt (a|x)µ(a, x) + Pr(x′ )πt (a′ |x)µ(a′ , x)
a∈A / x
|
{z
Bias2 of setting πl (a′ |x)=0
!2 ′
′
− B(X \ {x }) + Pr(x )
X
πt (a|x)µ(a, x)
a∈A / x
|
{z
Bias2 of setting πl (a′ |x)>0
≥ Pr(x′ )2 πt (a′ |x)2 µ(a′ , x)2
39
}
}
Now, we sandwich these inequalities to arrive at the per-context conclusion: Pr(x) πt (a′ |x)2 ′ ′ 2 ′ 2 µ(a , x) − πt (a |x) µ(a , x) ≥ ∆Variance ∆Bias ≥ Pr(x ) πt (a |x) µ(a , x) > N πl (a′ |x) 2
′ 2
′
2
′
2
⇒ ∆Bias2 > ∆Variance.
A.2
Proof of Proposition 2
Proof. Denote π ∗ to be the logging policy solution to min
max
πl ∈Π µ∈M,πt ∈Π
MSE[V̂IPW (πt |πl )]. We first
demonstrate that for any context x, π ∗ (·|x) = πU (·|x) minimizes the maximum MSE the target policy can induce. To begin, we define functions describing conditional error, that is, the MSE conditional on context, which constitutes one “instance” of the estimation problem. With this assumption that the logging policy has full support, we have no conditional bias. Let v(πt , πl | x) denote the contribution of context x to the variance of V̂IPW (πt | πl ). Under full support, this equals the conditional variance given X = x. We have X πt (a | x)2
(Conditional IPW Variance) v(πt , πl | x) :=
a∈Ax
πl (a | x)
!2
! µ(a, x)
−
X
πt (a | x)µ(a, x)
.
a∈Ax
We now consider the support of πl on context x, Ax , to be fixed. We show that with this fixed support, the maximum variance term v is minimized for the designer by spreading probability equally across Ax . Lemma 1 (Conditional uniform across support). Fix support Ax . πl∗ (·|x) = |A1x | ∀a ∈ Ax minimizes max
µ∈M,πt ∈Π
v(πt , πl |x).
Proof of Lemma 1. Observe that vIP W (πt , πl |x) is convex in πt . Thus, a deterministic πt (·|x) will maximize vIP W (πt , πl |x), treating πl as fixed. Let πt∗ be this deterministic policy with all its mass placed on action a∗ . We now have the function g that the designer needs to minimize, with µ(a∗ |x) ∗ 2 − µ(a |x) . g(πl |Ax ) = max a∗ ∈Ax πl (a∗ |x)
40
(12)
∗
µ(a |x) Because µ is not determined by the designer, solving πl∗ (·|x) reduces to minimizing max . πl (a∗ |x) ∗ ′
µ(a ,x) While, it follows that setting πl∗ (·|x) s.t. πµ(a,x) ∗ (a|x) = π ∗ (a′ |x) l
l
a ∈Ax
∀ a, a′ ∈ Ax , without knowledge of µ,
all actions must be treated as having constant reward averages. Thus, πl∗ (a|x) = |A1x | minimizes
max
µ∈M,πt ∈Π
∀ a ∈ Ax
vIP W (πt , πl |x).
Extending this argument to the aggregate level, we have in this setting with full support that
2
X πt (a | x) 1 X Pr(x) µ(a, x) N x∈X π l (a | x) a∈Ax " # 1 X Pr(x)vIPW (πt , πl | x) . = N x∈X
MSE[V̂IPW (πt |πl )] =
!2
! −
X
πt (a | x)µ(a, x)
a∈Ax
1 Because Pr(x) and n are treated as fixed and vIPW (·|x) are combined linearly, πl (a|x) = |A| minimizes
max
µ∈M,πt ∈Π
A.3
MSE[V̂IPW (πt |πl )].
Proof of Proposition 3
Proof. This proof follows a very similar structure to the proof of Proposition 1. We begin with showing the solution minimizing the conditional variance v. µ(a,x) Lemma 2 (Instance Level Uniform across support). Fix support Ax . Then πl∗ (a|x) = c+µ 2 (a|x) with P µ(a,x) 1 = a∈Ax c+µ 2 (a|x) minimizes max vIP W (πt , πl |x). πt ∈Π
Proof of Lemma 2. As in Lemma 1, observe that vIP W (πt , πl |x) is convex in πt . Thus, a deterministic πt (·|x) will maximize v(πt , πl |x), treating πl as fixed. Let πt∗ be this deterministic policy with all its mass placed on action a∗ . Let f (a|πl ) := πµ(a,x) −µ(a, x)2 . We now have the function g that the designer needs to minimize, l (a|x) with g(πl |Ax ) = max f (a∗ |πl ). ∗ a ∈Ax
(13)
We have that f is decreasing and convex in πl , so g(πl |Ax ) is minimized when f (a|πl ) = f (a′ |πl ) ∀ a, a′ ∈ P µ(a,x) µ(a,x) Ax . By setting f (a|πl ) = c ∀ a ∈ A, we have πl∗ (a|x) = c+µ 2 (a|x) with 1 = a∈Ax c+µ2 (a|x) , noting here that µ(a, x) ≤ 1, πl (a|x) ≤ 1 ∀ a ∈ A =⇒ c ≥ 0.
41
We now prove the proposition simply by extending this argument to the population-level marginal over contexts. For this setting with full support, we have that
X πt (a | x)2
!2
!
1 Pr(x) µ(a, x) N x∈X πl (a | x) a∈Ax " # 1 X = Pr(x)vIPW (πt , πl |x) . N x∈X
MSE[V̂IPW (πt |πl )] =
X
−
X
πt (a | x)µ(a, x)
a∈Ax
µ(a,x) Because Pr(x) and n are treated as fixed and vIPW (·|x) are combined linearly, πl∗ (a|x) = c+µ 2 (a|x)
minimizes max MSE[V̂IPW (πt |πl )]. πt ∈Π
A.4
Proof of Proposition 4
Proof. We examine the conditional variance by fixing x and then extend this result to the populaP tion. We denote the value (mean reward) of πt on a given instance x as v(x) := a∈A πt (a|x)µ(a, x). We examine the worst-case MSE in cases where (1) πl ̸= πt , and (2) πl = πt . We begin by defining and proving a useful intermediate lemma. Lemma 3 (Minimum sum). Let C(πl |x) :=
P
πt (a|x)2 a∈A πl (a|x) .
Then, C(πl ) = 1 iff πl (·|x) = πt (·|x),
otherwise C(πl |x) > 1. Proof of Lemma 3. Let m ⃗ a := √πt (a|x) and ⃗na :=
p
πl (a|x)
πl (a|x). Because πl (·|x) is a valid probability
distribution, we have ||⃗n|| = 1, and we have ||m|| ⃗ := C(πl ). By the Cauchy-Schwarz inequality that ||m|| ⃗ ||⃗n|| ≥ |m ⃗ · m| ⃗ = 1, with equality holding iff m ⃗ a = c⃗na ∀a ∈ A. Because πl (·|x) and πt (·|x) both comprise valid probability distributions, this equality can only hold when πl (·|x) = πt (·|x). Now, we examine each case. Case (1): πl ̸= πt . Denote the set of µ values constrained to a single value across actions as MC := {µ(a) = t, ∀ a ∈ A : t ∈ [0, 1]}. We have that unconstrained supremum will be greater than or equal to the supremum attained on the constrained optimization when all actions have the same value in µ; that is, supµ∈M vIPW (πt , πl |x) ≥ supµ∈MC vIPW (πt , πl |x). We now solve this constrained problem. With µ ∈ MC , we have m(x) = t and vIP W (πt , πl |x) = tC(πl |x)−t2 for some t ∈ [0, 1]. By Lemma 3, we have that C(πl |x) > 1.
42
This leads to maxt∈[0,1] tC(πl |x) − t2 > 14 . Therefore, we have that 1 sup vIPW (πt , πl | x) > . 4 µ∈M Case (2): πl = πt . With πl = πt , we have
P
πt (a|x)2 a∈A πl (a|x) = v(x). This gives conditional variance of
vIPW = v(x) − v(x)2 , which is maximized at v(x) = 12 . This yields 1 sup vIPW (πt , πl |x) = . 4 µ∈M With the variance term of MSE[V̂IPW (πt |πl )] as a linear combination of vIPW (πt , πl |x), we have πl∗ = πt as the unique minimizer to max min MSE[V̂IPW (πt |πl )]. µ∈M πl ∈Π
A.5
Proof of Corollary 1
Proof. We begin by bounding the value of c which will be used to prove that the original inequality holds. Lemma 4 (Constraint lower bound). The normalizing constant meets the constraint c ≥ µ(a, x)µ(a′ , x) A, x ∈ X . Proof of Lemma 4. Let ai denote the ith highest average reward for a context, such that µ(a1 |x) ≥ µ(a2 |x) ≥ .... Now, let c0 := µ(a1 |x)µ(a2 |x). We have that µ(a1 |x) µ(a2 |x) µ(a1 |x) µ(a2 |x) + = + 2 2 2 c0 + µ(a1 |x) c0 + µ(a2 |x) µ(a1 |x)µ(a2 |x) + µ(a1 |x) µ(a1 |x)µ(a2 |x) + µ(a2 |x)2 1 1 = + µ(a2 |x) + µ(a1 |x) µ(a1 |x) + µ(a2 |x) 2 = µ(a2 |x) + µ(a1 |x) ≥1
(14) (15) (16) (17)
43
∀
a,
as µ(a, x). Let g(c) :=
P
µ(a,x) a∈A c+µ(a,x)2 . Thus, we have
g(c0 ) = =
µ(a, x) c + µ(a, x)2 a∈A
X
(18)
2 + µ(a2 |x) + µ(a1 |x)
X a∈A\{a1 ,a2 }
µ(a, x) c + µ(a, x)2
≥ 1.
(19) (20)
Observe that g is decreasing in its argument, so our normalizing constant must meet c ≥ c0 to attain g(c) = 1. Thus, c ≥ c0 ≥ µ(a1 |x)µ(a2 |x) ≥ µ(a)µ(a′ ) ∀ a, a′ ∈ A. We use this bound on c to prove the monotonicity argument. Let µ(a, x) > µ(a′ , x). Now, we use simple algebraic manipulation to arrive at our claim: c[µ(a, x) − µ(a′ , x)] > [µ(a, x)µ(a′ , x)][µ(a, x) − µ(a′ , x)] (21) ⇐⇒ c[µ(a, x) − µ(a′ , x)] + [µ(a, x)µ(a′ , x)][µ(a′ , x) − µ(a, x)] > 0
(22)
⇐⇒ µ(a, x)[c + µ(a′ , x)2 ] − µ(a′ , x)[c + µ(a, x)2 ] > 0
(23) ′
⇐⇒
A.6
µ(a , x) µ(a, x) > . c + µ(a, x)2 c + µ(a′ , x)2
(24)
Proof of Proposition 5
Proof. Consider, again, the single-instance variance v. As
P
a∈A πt (a)µ(a) is fixed, we have the
constrained optimization problem: minimize
X πt (a | x)2 a∈A
s.t.
X
πl (a | x)
µ(a, x)
πl (a|x) = 1.
a∈A
First, let c(a) := πt2 (a|x)µ(a, x). Define the Lagrangian
44
L(πl , λ) =
X c(a) − λ( πl (a|x) − 1). πl (a | x) a∈A a∈A
X
(25)
Now, we set the KKT conditions. For every action a, ∂L ca = 0 =⇒ − ∗ + λ = 0 =⇒ πl∗ (a|x) = 2 ∂πl (a|x) πl (a|x) We now impose
r
ca . λ
(26)
∗ a∈A πl (a|x) = 1 to identify the Lagrange multiplier:
P
X√ √ ca =⇒ λ = ca′ . λ a′ ∈A
(27)
p √ c π (a|x) µ(a, x) a t p πl∗ (a|x) = P = P . √ ′ ′ ca′ a′ ∈Ax a′ ∈A πt (a |x) µ(a , x)
(28)
1=
X
πl∗ (a|x) =
X
a∈A
a∈A
r
i
Substituting λ back, we have
Given that this solution minimizes conditional variance, it minimizes the weighted sum of these √ πt (a|x) µ(a,x) ∗ √ ′ minimizes MSE[V̂IPW (πt |πl )]. conditional variance terms. Therefore, πl (a|x) = P ′ a′ ∈A πt (a |x)
A.7
µ(a ,x)
Proof of Corollary 2
Proof. This result follows from Proposition 5. With deterministic πt , we have that X
πt (a′ |x)
p
µ(a′ , x) =
p µ(a∗ |x)
a′ ∈A
with a∗ being the action deterministically selected by πt . Then, p πt (a|x) µ(a, x) p πl (a|x) = . µ(a, x) So, πl (a∗ |x) = 1 and πl (a′ |x) = 0 ∀a′ ̸= a.
45
A.8
Proof of Corollary 3
Proof. Observe that πl∗ induces an unbiased estimate V̂IPW (πt |πl∗ ). We have conditional MSE capp P tured entirely by the conditional variance vIPW (πt , πl∗ |x), defined earlier. Let Z := a∈Ax πt (a|x) µ(a, x) P and µ̄ := a∈Ax πt (a | x)µ(a, x). Then vIPW (πt , πl∗ |x) =
X πt (a | x)2 a∈Ax
=
=
πl∗ (a | x)
!2
! µ(a, x)
X
−
πt (a | x)µ(a, x)
! p ′ ′ , x) µ(a π (a |x) t x p µ(a, x) − µ̄2 π (a | x) µ(a, x) t a∈Ax ! X p Z πt (a | x) µ(a, x) − µ̄2 X πt (a | x)2
(29)
a∈Ax
P
a′ ∈A
(30)
(31)
a∈Ax
= Z 2 − µ̄2 Letting u :=
p πt (a|x)
and v = a∈Ax
(32) p p πt (a|x) µ(a, x)
, we have by Cauchy-Schwartz a∈Ax
|⟨u, v⟩|2 ≤ ⟨u, u⟩ · ⟨v, v⟩ X X Z2 ≤ πt (a|x) πt (a|x)µ(a, x). a∈Ax
a∈Ax
Recall, that πt (·|x) comprises a probability distribution, so this simplifies to Z2 ≤ 1 ·
X
πt (a|x)µ(a, x)
(33)
a∈Ax
Z 2 ≤ µ̄.
(34)
46
Now, let vemp (x) be the conditional variance in reward given X = x. This is defined as vemp (x) := Var[R | X = x] = E [Var(R | X = x)] + Var (E[R | X = x]) !2 X
=
πt (a|x)µ(a, x) (1 − µ(a, x)) +
a∈Ax
X
πt (a|x)µ(a, x)2 −
a∈Ax
X
πt (a|x) µ(a, x)
a∈Ax
!2 X
=
πt (a|x)µ(a, x) −
X
πt (a|x) µ(a, x)
a
a∈Ax
= µ̄ − µ̄ 2 . Using these on (9), we have vIPW (πt , πl∗ |x) = Z 2 − µ̄2
(35)
≤ µ̄ − µ̄2 = vemp (x).
(36)
This inequality extends to the aggregate level as the inequality holds across exogenous context arrivals, which linearly combines v(x), and sample sizes, divides both by n. Therefore, MSE[V̂IPW (πt |πl∗ )] ≤ MSE[V̂emp (πt )].
A.9
Proof of Corollary 4
Proof. We have the target and logging policy values #
" V (πt ) =
X
X
Pr(x)
x∈X
πt (a|x)µ(a, x)
a∈A
"
# p πt (a|x) µ(a, x) p Pr(x) µ(a, x) P ′ ′ a′ ∈A πt (a |x) µ(a , x) x∈X a∈A "P # 3/2 X π (a|x)µ(a, x) t = Pr(x) Pa∈A 1/2 a∈A πt (a|x)µ(a, x) x∈X
V (πl∗ ) =
X
X
47
To simplify notation, define Y (x) assume the value V (πt ) =
X
p µ(a, x) w.p. πt (a|x). Then we have
Pr(x)E[Y (x)2 ]
x∈X
V (πl∗ ) =
X
Pr(x)
x∈X
E[Y (x)3 ] . E[Y (x)]
Now, let’s examine the conditional value. We will show this conditional value is at least as great for a given context x. Comparing the differences in these conditional values, we have E[Y (x)3 ] E[Y (x)3 ] − E[Y (x)2 ]E[Y (x)] − E[Y (x)2 ] = E[Y (x)] E[Y (x)] Cov(Y (x), Y (x)2 ) = . E[Y (x)]
(37) (38)
Because µ assumes only non-negative values, Cov(Y (x), Y (x)2 ) ≥ 0, and E[Y (x)] ≥ 0 . Therefore, we have V (πl∗ ) − V (πt ) =
X
Pr(x)
x∈X
Cov(Y (x), Y (x)2 ) E[Y (x)]
≥ 0. If we make the assumption that the support of Y (x) is non-zero for at least one x, this inequality becomes strict.
A.10
Proof of Proposition 6
Proof. argminπl Eπt ∼Πt MSE[V̂IPW (πt |πl )] = argminπl Variance(πt |πl ) X X X πt (a|x)2 = argminπl Pr(πt ) Pr(x) µ(a, x) π l (a|x) πt ∈Πt x∈X a∈A P X X π ∈Π Pr(πt )πt (a|x)2 t t = argminπl Pr(x) µ(a, x) πl (a|x) x∈X a∈A Following similar steps to the proof of the optimal πl under known πt , let c(a) :=
48
(39) (40) (41)
2 πt ∈Πt Pr(πt )πt (a|x) µ(a, x).
P
Define the Lagrangian L(πl , λ) =
X c(a) − λ( πl (a|x) − 1). πl (a | x) a∈A a∈A
X
(42)
Set the KKT conditions. For every action a, ∂L c(a) = 0 =⇒ − ∗ + λ = 0 =⇒ πl∗ (a|x) = ∂πl (a|x) πl (a|x)2 We now impose
r
c(a) . λ
(43)
∗ a∈A πl (a|x) = 1 to identify the Lagrange multiplier:
P
r 1=
X
πl∗ (a|x) =
a∈A
X a∈A
Xp √ c(a) =⇒ λ = c(a′ ). λ a′ ∈A
(44)
i
Substituting λ back, we have p c(a) ∗ p πl (a|x) = P = P c(a) a′ ∈Ai ′
qP
a ∈A
2 πt ∈Πt Pr(πt )πt (a|x) µ(a, x)
qP
.
(45)
′ 2 ′ πt ∈Πt Pr(πt )πt (a |x) µ(a , x)
Which can be alternatively rewritten as p E[πt (a|x)2 ]µ(a, x) p πl∗ (a|x) = P . E[πt (a′ |x)2 ]µ(a′ , x) a′ ∈A
49
(46)
B
Derivation of MSE(V̂IP W )
We have that MSE[V̂ (πt |πl )] = (V (πt ) − V̂ (πt |πl ))2 . We can decompose this in accordance to the bias-variance decomposition to arrive at the MSE. Define Ax to be the set of actions for x where ∀a ∈ Ax , πl (a, x) > 0, then we have: 2 Bias = V (πt ) − E[V̂IPW (πt |πl )] 2
=
=
!!2 πt (a | x) µ(a, x) Pr(x) πt (a | x)µ(a, x) − πl (a|x) π l (a|x) x∈X a∈A a∈Ax !2 X X Pr(x) πt (a | xi )µ(a, x) X
X
x∈X
a∈A / x
X
X
X
!2 =
Pr(x)
x∈X
πt (a | x)µ(a, x)
a∈A / x
(A|x) R with randomness due to action selection and Bernoulli For notational compactness, let Zx := ππtl (A|x)
draws. With the independence of Z terms in variance, we can decompose this term in the following way: Variance = E
2 E[V̂ (πt |πl )] − V̂ (πt |πl )
1 X Pr(x)Var(Zx ) N x∈X 1 X = Pr(x)(E[Zx2 ] − E[Zx ]2 ) N x∈X =
Because we have E[Zx ] =
P πt (a|x) a∈Ax πℓ (a | x) πℓ (a|x) µ(a, x) = a∈Ax πt (a | x) µ(a, x).
P
50
Now,
Variance =
1 X N x∈X
! Pr(x) E[Zx2 ] −
=
N x∈X
πt (a | x)µ(a, x)
a
1 X
X
Pr(x)
X πt (a|x)2 a∈Ai
πl (a|x)
!2
! µ(a, x)
X
−
πt (a|xi )µ(a, x)
a∈Ai
This leads to a final, closed-form expression of MSE.
2
MSE[V̂ (πt |πl )] =
+
X
Pr(x)
X
x∈X
a∈A / i
1 Pr(x) N x∈X X
πt (a | x)µ(a, x) X πt (a | x)2 a∈Ax
πl (a | x)
51
!2
! µ(a, x)
−
X a∈Ax
πt (a | x)µ(a, x)
.
C
Example of Bias Improving Estimate
There are cases, however, where worst-case MSE can be minimized by not sampling actions that might be sampled by the target policy, inducing a biased estimate. Proposition 7. For an unconstrained target policy class Π, a logging policy with full support does not always minimize
max
µ∈M,πt ∈Π
MSE[V̂IPW (πt |πl )].
Proof. Let |A| = 10 and |X | = 1 and n = 1. Consider a deviation from πU to the degenerate policy π ′ (a1 |x1 ) = 1. For πU we have: " max
µ∈M,πt ∈Π
MSE[V̂IPW (πt |πU )] =
max
µ∈M,πt ∈Π
−
X
|A|πt2 (a|x1 )µ(a, x1 )
a∈A
!2 X
πt (a|x1 )µ(a, x1 )
a∈A
= 9. However, for πl′ , we have: max
µ∈M,πt ∈Π
MSE[V̂IPW (πt |πl′ )] =
max
µ∈M,πt ∈Π
X
πt (a|x1 )µ(a, x1 )
a̸=a1
+ πt2 (a1 |x1 )µ(a1 |x1 ) − (πt (a1 |x1 )µ(a1 |x1 ))2
= 1. So, there exists conditions under which the minimax MSE is minimized via a biased policy.
52
D
Simulations
D.1
Additional Simulations
D.1.1
Other Policy Mappings
We briefly extend the results of Figure 6 to other policy classes, motivated by the performance of top-k policies with a well chosen k. Specifically, we use top-k to truncate logging propensities. Then, rather than sample uniformly across these actions, we sample in accordance to the estimated reward probability. Thus, we end up with two parameters of greediness for the following classes: Power-normalized across top-k (Top-k PN). We defined this class to be ΠT KP N (µ̂) := n o πk,d ; ∀d ∈ [0, ∞), k ∈ 1...|A|] , where πk,d is the power-normalization function using degree d described in Section 6, however where normalization only happens over the top-k items. n Softmax across top-k (Top-k SM). We defined this class to be ΠT KSM (µ̂) := πk,α ; ∀α ∈ o [0, ∞), k ∈ 1...|A|] , where πk,α is the softmax function using parameter α described in Section 6, where sampling only happens over the top-k items. In Figure 7, we compare these policies to those in Figure 6. We plot these additional classes at several different d or α parameters respectively across all k values. In general, these classes seem to improve performance as k grows large, suggesting these can limit the downside of selecting a support which is too large. Specifically, we note that for the given simulation parameters, sampling across the top-k proportional to raw reward estimates (d = 1) can yield comparable upside MSE when k is tuned well but limit MSE loss as k grows too large.
D.2
Environment Description
In constructing the simulation environment, we set the number of users |X | and the number of actions |A|. Then, for each x ∈ X , we assign some arrival probability Pr(x). We then generate reward probabilities µ(a, x) as follows. For each user context x, randomly permute A to generate A′ . Then, for i ∈ 1...|A|, assign µ(A′i , x) = αγ i , where α is a scale parameter and γ ∈ [0, 1] is the decay rate. Model estimates µ̂ are generated from µ by multiplying each underlying probability by noise N (1, σ 2 ). At simulation time, the dataset is constructed as follows. For each instance, a user is drawn from x ∼ Pr(x) with replacement, an action is taken according to the logging policy
53
10 1
MSE of Soft-Greedy Policies Across Uniformity Parameters (|A| = 100000; N = 1000) Softmax Top-k Power-normalized Top-k PN (d = 12 ) Top-k PN (d = 1) Top-k PN (d = 2)
MSE of Soft-Greedy Policies Across Uniformity Parameters (|A| = 100000; N = 1000000)
Top-k SM ( = 5) Top-k SM ( = 50) Target (MSE=4.14e-05) Optimal (MSE=3.81e-05) Uniform (MSE=2.16e-02)
Softmax Top-k Power-normalized Top-k PN (d = 12 ) Top-k PN (d = 1) Top-k PN (d = 2)
10 3
Top-k SM ( = 5) Top-k SM ( = 50) Target (MSE=4.14e-08) Optimal (MSE=3.81e-08) Uniform (MSE=2.16e-05)
10 4
MSE
MSE
10 2
10 5
10 3 10 6
10 4 10 7
120
108
96
84
72 60 48 Softmax Uniformity ( )
36
24
12
0
120
108
96
84
72 60 48 Softmax Uniformity ( )
36
24
12
0
6.0
5.4
4.8
4.2
3.6 3.0 2.4 Power-normalized Uniformity (d)
1.8
1.2
0.6
0.0
6.0
5.4
4.8
4.2
3.6 3.0 2.4 Power-normalized Uniformity (d)
1.8
1.2
0.6
0.0
105
100
100
101
102
103
Top-k Uniformity (k, log scale)
104
(a) Small action space |A| = 1, 000.
101
102
103
Top-k Uniformity (k, log scale)
104
105
(b) Large action space |A| = 100, 000.
Figure 7: MSE of IPW estimator for soft-greedy logging policy classes top-k and softmax. . Simulation evidence of the MSE of the IPW estimator as a function of the greediness parameter for the top-k, softmax, and power-normalized logging policy classes, in addition to top-k PN and top-k SM. Full simulation details are in Appendix D, under the same parameters as Figure 6. a ∼ πl (·|x), and a reward is drawn from the underlying distribution r ∼ Bernoulli(µ(a, x)). This is then repeated n times to form a dataset. Simulation generating Figure 1 Simulation parameters are: |A| = 10, 000 for a single context, with scaled geometric reward pref1 ). The target policy is a top-k policy (k = 10) on 0-noise estimates of µ. erences (γ = .99, α = 10
The personalized logging policy is a top-k policy (k = 10) on µ̂ with multiplicative Gaussian noise of σ 2 = .25. Simulation generating Figure 4 Simulation parameters are: |A| = 1, 000 a single context (|X | = 1), with scaled geometric reward 1 preferences (γ = .99, α = 10 ). There are 100 samples drawn for all logging policies to generate the
MSE. Noises in µ̂l are placed equally spaced on [0, .25], with 1, 000 trials at each noise. The target policy is generated for each trial based on a top-k policy (k = 30) on noisy estimates of µ with (ϵ = .25). The optimal logging policy is derived for this target policy for each trial.
54
Simulation generating Figure 5 Simulation parameters are: |A| = 1, 000, |X | = 1, 000 with µ(a, x) distributed by randomly permuting A then assigning a linearly decreasing µ(a, x) on the equally spaced lattice from .4 to 0. Here, 50, 000 samples are drawn for each trial. The target policy is a top-k policy (k = 100) based on estimates generated with standard multiplicative noise with σ 2 = .05. Both MSE and observed outcomes used to derive w∗ are based on a sample size of 50, 000. Simulation generating Figure 6 Simulation parameters are: |A| = 1, 000 for the small action space setting and |A| = 100, 000 for the large action space setting for a single context, with scaled geometric reward preferences (γ = .99, 1 α = 10 ), with. 1, 000 samples are drawn for all logging policies. The target policy is a top-k policy
(k = 200) on 0-noise estimates of µ.
55