betaFeedback

WorksMathematics

Adaptive Budgeted Data Acquisition for Robust Off-Policy Evaluation from Multiple Loggers

Abstract

We consider off-policy evaluation when additional data can be purchased from several existing logging policies (or loggers) with heterogeneous costs per observation. While existing work on multiple loggers presumes a fixed number of observations from each logger, we study how to allocate a limited budget across them sequentially to evaluate a finite class of target policies. We propose Adaptive Greedy, an algorithm that purchases observations sequentially from the affordable logger that has the most cost-normalized variance reduction across the target policies. It turns out that each such purchase is an 'approximate conditional-gradient step' for the corresponding design problem. Under mild assumptions, we establish that the empirical allocation converges almost surely to the optimal design at an explicit rate. We also derive the asymptotic normality of the final pooled estimator and show that it attains the semiparametric efficiency bound. Simulations and a semi-synthetic application based on the AIDS Clinical Trials Group Study 175 show that Adaptive Greedy outperforms standard allocation strategies, remains accurate if stopped early, and matches the final accuracy of repeated integer programming at a fraction of its computational cost.

Introduction

Contextual bandits are widely used in applications where an action must be chosen after observing information about the current user or environment, including recommendation systems, online content selection, and personalized interventions [39] (Li et al. 2010). In such applications a new policy usually cannot be deployed simply to learn how well it performs, since online experimentation is costly, risky, and slow. Off-policy evaluation avoids this by estimating the value of a target policy from data collected under a different behavior policy [11, 41].

In practice, the available data need not come from a single behavior policy. Deployed systems are updated over time, several experiments may run in parallel, and different loggers may use different decision rules. Methods for combining observations from several loggers generally take the logger sample sizes as given [1, 28] (He et al. 2019). In many applications, however, more data can still be collected, but only from loggers that already exist, and these loggers differ both in the actions they tend to take and in their per-observation prices. An inexpensive logger may concentrate on a few actions, while a more costly logger may provide the coverage that a target policy needs. The practical question is where the remaining observations should be purchased when the reward distribution is not yet known. We study a fixed set of logging policies μ1,…,μK\mu_1,\ldots,\mu_K with known costs c1,…,cKc_1,\ldots,c_K. The policies cannot be redesigned, and acquisition chooses only which logger to sample from next, subject to a finite budget.

This problem differs from behavior-policy design, in which the logging or augmentation policy is itself chosen to reduce the variance of a downstream estimator [23, 40, 35]. When the loggers are fixed, an allocation is a count vector N=(N1,…,NK)∈Z+KN=(N_1,\ldots,N_K)\in\mathbb{Z}_{+}^{K} with cTN≤Bc^{\mathsf{T}}N\le B, where NkN_k is the number of observations purchased from logger kk and BB is the total budget. Each purchase increments one coordinate of NN and bears the corresponding logger cost.

A second feature is that several target policies may have to be evaluated from the same sample. We consider a finite target class Π={π1,…,πM}\Pi=\{\pi_1,\ldots,\pi_M\} and seek a design that controls the largest target-specific uncertainty over that class. The criterion retains each policy’s target-specific efficient variance and minimizes its maximum, so the objective can change as the target attaining that maximum changes. Prior work on evaluating multiple policies jointly provides related motivation, although it studies different sampling settings and objectives [9, 5].

The criterion depends on the conditional reward mean and variance, which are unknown at the outset and must be estimated from the observations acquired along the way. We propose a sequential rule, which we call Adaptive Greedy, that re-estimates the criterion as data accrue and at each step purchases from the affordable logger with the largest estimated reduction in the worst-target criterion per unit of cost. An additional feature is that the rule does not plan toward a declared final budget. The budget enters only through which loggers remain affordable and when acquisition stops. This is useful if the available budget is unexpectedly reduced or the process must stop early, since the data already collected were chosen to improve the current design rather than to follow a plan optimized for a larger final budget. Planners that repeatedly solve for count vectors at a declared final budget behave differently, since their early purchases are chosen with that budget in mind.

For a fixed logger composition, weighting each observation by the overall mixture of the logging policies has no larger asymptotic variance than weighting it only by the logger that generated it. We therefore combine all acquired observations using this pooled estimator. Under adaptive data collection, however, the final logger composition depends on the rewards observed along the way, so the pooled denominator is itself random. We show that as the design converges, this random denominator can be replaced at first order by its deterministic limiting value. As a result, the pooled estimator remains asymptotically normal and its large-sample variance is determined by the allocation reached by the algorithm.

Our contributions are threefold. First, we formulate budgeted off-policy evaluation as a sequential allocation problem among loggers with heterogeneous costs and propose the Adaptive Greedy algorithm. Second, assuming overlap only for the pooled behavior distribution at the optimal design, rather than for every logger, we show that the resulting design converges almost surely to the continuous minimax design. Under stronger conditions on the plug-in estimates, we also derive an explicit polynomial rate. Third, we establish joint asymptotic normality and consistent covariance estimation for the pooled estimator, even though the logger choices depend on previously observed rewards. The variance advantage of pooled over logger-specific weighting is known for fixed designs [1, 28]. Our result shows that pooled inference remains valid after adaptive data collection under the stated conditions.

Related Work

Off-policy evaluation from several loggers has so far been studied with the logger sample sizes given in advance. Agarwal et al. [1] observe that weighting each observation by the pooled behavior distribution never increases variance relative to weighting it by the logger that generated it. He et al. (2019) study off-policy learning from data collected by multiple loggers, and Lai et al. [29] choose variance-minimizing weights for combining estimators computed from several behavior policies. Kallus et al. [28] characterize the semiparametric efficiency bound for the fixed-stratified multi-logger model and construct an estimator that attains it. This pooled bound, viewed as a function of the logger composition, is the population objective of our design problem.

Related mixture-design problems have also been studied in importance sampling. He and Owen (2014) establish convexity of variance objectives for mixtures of fixed proposal distributions and discuss minimizing the maximum variance when estimating multiple integrals from shared samples. Our setting instead concerns sequential purchases from fixed contextual-bandit loggers with heterogeneous costs, where allocation decisions depend on the observations acquired so far.

A second line of work designs or learns the data-collection policy itself for downstream evaluation. Examples include behavior-policy search ([23, 31]), experimental design in linear heteroscedastic bandits ([35]), safe or robust data-collection designs ([46, 34, 32, 4]), and the optimization of logging probabilities ([10]). In contextual bandits, Tucker and Joachims [40] design an augmentation logging policy for an existing dataset and evaluate with a balanced estimator that divides by the pooled behavior distribution of the original and augmentation data. In all of these works the behavior or augmentation policy is a design variable, whereas in our setting the loggers are fixed and only the number of purchases from each can be chosen.

Evaluating several target policies from shared data is a closely related problem. Dann et al. [9] study high-confidence evaluation of multiple policies in episodic reinforcement learning, Jain et al. [27] adaptively learn a behavior policy for evaluating several general value functions, and Chen et al. [5] optimize an offline sampling distribution for several policies in an episodic MDP. Liu et al. [32] and Russo and Pacchiano [38] also study data collection when there are several evaluation targets. These works motivate designing for a finite target class jointly, which in our setting takes the form of a minimax criterion over the target-specific pooled efficiency bounds.

Inference from data collected by outcome-adaptive rules has been developed for batched bandits, adaptive experiments, and off-policy evaluation from contextual bandits ([45, 19, 44, 3, 42]). In these works the weights and normalizations entering the estimator are predictable, meaning that they are known when each observation is collected, and martingale arguments apply to the resulting estimating equations. The pooled estimator studied here divides by the final logger composition, which depends on rewards observed along the acquisition path and is known only after acquisition ends. Design convergence allows us to replace this random final mixture by its deterministic limit.

The cost-normalized feasible set and the minimax variance criterion connect the problem to classical optimal design ([14, 37]). The sequential update has a conditional-gradient interpretation related to the Fedorov–Wynn design algorithms ([43, 6]), with vertices fixed by the available loggers and a step size set by the cost of the logger purchased. § 4.1 develops this connection.

Preliminaries

Problem Setup

Let X\mathcal{X} be a measurable context space and let A\mathcal{A} be a finite action space. There are KK existing logging policies (or loggers) μ1(a∣x),…,μK(a∣x)\mu_1(a \mid x), \ldots, \mu_K(a \mid x), and acquiring one observation from logger kk costs ck>0c_k > 0. If an observation is purchased from logger kk, it is generated as

X∼PX,A∼μk(⋅∣X),R∼PR(⋅∣X,A).(1)X \sim P_X,\qquad A \sim\mu_k(\cdot\mid X),\qquad R \sim P_R(\cdot\mid X,A). \tag*{(1)}

The context distribution PXP_X and conditional reward distribution PRP_R are common across loggers. Write q(x,a)=E(R∣X=x,A=a)q(x,a) = \mathbb{E}(R \mid X = x, A = a) and σ2(x,a)=Var⁡(R∣X=x,A=a)\sigma^2(x,a) = \operatorname{Var}(R \mid X = x, A = a) for the conditional reward mean and variance. Let Π={π1,…,πM}\Pi= \{\pi_1,\ldots,\pi_M\} be the finite target policy class. Our estimand is the vector of policy values J=(J1,…,JM)⊤J = (J_1,\ldots,J_M)^\top, which we estimate after acquisition is complete, where Jj=EX{qj(X)}J_j = \mathbb{E}_X\{q_j(X)\} and qj(x)=∑a∈Aπj(a∣x)q(x,a)q_j(x) = \sum_{a \in\mathcal{A}} \pi_j(a \mid x)q(x,a). Only context-action pairs used by some target policy affect the policy values. Let S={(x,a):πj(a∣x)>0 for some j}\mathcal{S} = \{(x,a) : \pi_j(a \mid x) > 0 \text{ for some } j\} be the union of the target-policy supports. For a function ff of (x,a)(x,a), we write ess inf⁡Sf\operatorname{ess\,inf}_{\mathcal{S}} f for the infimum of f(x,a)f(x,a) over (x,a)∈S(x,a) \in\mathcal{S}, after removing a PXP_X-null set of contexts.

Data are acquired sequentially, and each logger is chosen using only the data observed before that choice. For observation ii, let Ki∈{1,…,K}K_i \in\{1,\ldots,K\} denote the selected logger, and AiA_i for the contextual-bandit action generated by that logger. Let

Fi=σ{K1,X1,A1,R1,…,Ki,Xi,Ai,Ri},\mathcal{F}_i = \sigma\{K_1, X_1, A_1, R_1,\ldots,K_i, X_i, A_i, R_i\},

with F0\mathcal{F}_0 trivial, be the history till time ii. If external randomization is used to select a logger (e.g., to break a tie between two or more potential loggers), the filtration is assumed to include that randomization before the corresponding logger choice. Thus KiK_i is Fi−1\mathcal{F}_{i-1}-measurable. Conditional on Fi−1\mathcal{F}_{i-1} and Ki=kK_i = k, the observation (Xi,Ai,Ri)(X_i,A_i,R_i) is generated according to (1). We impose the following structural assumption, which is standard in off-policy evaluation with multiple loggers; see Dudík et al. [11] and Kallus et al. [28].

Assumption 1. The logging probabilities μ1,…,μK\mu_1,\ldots,\mu_K and the costs c1,…,cKc_1,\ldots,c_K are known, 0<cmin⁡=min⁡kck≤max⁡kck=cmax⁡<∞0 < c_{\min} = \min_k c_k \le\max_k c_k = c_{\max} < \infty, and ∣R∣≤Rmax⁡<∞|R| \le R_{\max} < \infty almost surely.

With total budget BB, acquisition continues until no logger remains affordable. Let Nt,k=∑i=1t1{Ki=k}N_{t,k} = \sum_{i=1}^{t} 1\{K_i = k\} count the number of observations acquired from logger kk. Let Ct=∑k=1KckNt,kC_t = \sum_{k=1}^{K} c_kN_{t,k} denote the expenditure after tt observations. Write Nt=(Nt,1,…,Nt,K)⊤N_t = (N_{t,1},\ldots,N_{t,K})^\top, so that ∑kNt,k=t\sum_k N_{t,k} = t. Acquisition stops at

TB=min⁡{t≥0:cmin⁡>B−Ct},T_B = \min\{t \ge0 : c_{\min} > B - C_t\},

which is a stopping time with respect to (Ft)(\mathcal{F}_t). It is easy to see that TBT_B is bounded between ⌊(B−cmin⁡)/cmax⁡⌋\lfloor(B-c_{\min})/c_{\max}\rfloor and ⌈B/cmin⁡⌉\lceil B/c_{\min}\rceil, and in particular TB→∞T_B \to\infty as B→∞B \to\infty.

Fixed Logger Sizes

The purpose of this subsection is to obtain the variance criterion that we will later use for acquisition. Here we fix the sample size tt and the sequence of loggers k1,…,ktk_1,\ldots,k_t with ki∈{1,…,K}k_i \in\{1,\ldots,K\}. Let Nk=Nt,kN_k = N_{t,k} be the resulting number of observations from logger kk, and N=(N1,…,NK)⊤N = (N_1,\ldots,N_K)^\top. Thus ∑kNk=t\sum_k N_k = t, the counts are deterministic, and no acquisition decision depends on the observed data. This is the fixed-stratified setting studied by Kallus et al. [28].

Since all loggers share PXP_X and PRP_R, we can weight every observation by the mixture of the logging policies, as if the combined sample came from that mixture. This weighting never gives a larger variance than weighting each observation by the logger that generated it (Agarwal et al., 2017; [28]). The mixture is the pooled behavior distribution

μˉN(a∣x)=1t∑k=1KNkμk(a∣x).(2)\bar{\mu}_{N}(a \mid x) = \frac{1}{t}\sum_{k=1}^{K} N_k\mu_k(a \mid x). \tag*{(2)}

We define the pooled augmented inverse propensity weighted (AIPW) estimator of JjJ_j as

References

  1. [1]Agarwal, A., Basu, S., Schnabel, T., and Joachims, T. (2017), “Effective Evaluation Using Logged Bandit Feedback from Multiple Loggers,” in Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, pp. 687–696.DOI
  2. [2]Antos, A., Grover, V., and Szepesvári, C. (2010), “Active Learning in Heteroscedastic Noise,” Theoretical Computer Science, 411, 2712–2728.DOI
  3. [3]Bibaut, A., Dimakopoulou, M., Kallus, N., Chambaz, A., and van der Laan, M. (2021), “Post-Contextual-Bandit Inference,” in Advances in Neural Information Processing Systems, vol. 34, pp. 28548–28559.arxiv.org/abs/2106.00418
  4. [4]Chen, C., Liu, S. D., Luo, L., Chandra, R., Jiang, N., and Zhang, S. (2026), “Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluation,” arXiv preprint arXiv:2608.24146.arxiv.org/abs/2608.24146
  5. [5]Chen, Y., Pacchiano, A., and Paschalidis, I. (2025), “Multiple-Policy Evaluation via Density Estimation,” in Proceedings of the 42nd International Conference on Machine Learning, PMLR, vol. 267 of Proceedings of Machine Learning Research, pp. 8794–8820.arxiv.org/abs/2404.00195
  6. [6]Chernoff, H. (1959), “Sequential Design of Experiments,” The Annals of Mathematical Statistics, 30, 755–770.
  7. [7]Chernozhukov, V., Chetverikov, D., Demirer, M., Duflo, E., Hansen, C., Newey, W., and Robins, J. (2018), “Double/Debiased Machine Learning for Treatment and Structural Parameters,” The Econometrics Journal, 21, C1–C68.
  8. [8]Dai, J., Gradu, P., and Harshaw, C. (2023), “CLIP-OGD: An Experimental Design for Adaptive Neyman Allocation in Sequential Experiments,” in Advances in Neural Information Processing Systems, vol. 36.arxiv.org/abs/2305.17187
  9. [9]Dann, C., Ghavamzadeh, M., and Marinov, T. V. (2023), “Multiple-Policy High-Confidence Policy Evaluation,” in Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, PMLR, vol. 206 of Proceedings of Machine Learning Research, pp. 9470–9487.
  10. [10]Douglas, C., Persson, J., and Provost, F. (2026), “Logging Policy Design for Off-Policy Evaluation,” arXiv preprint arXiv:2605.15108.arxiv.org/abs/2605.15108
  11. [11]Dudík, M., Erhan, D., Langford, J., and Li, L. (2014), “Doubly Robust Policy Evaluation and Optimization,” Statistical Science, 29, 485–511.
  12. [12]Étoré, P. and Jourdain, B. (2010), “Adaptive Optimal Allocation in Stratified Sampling Methods,” Methodology and Computing in Applied Probability, 12, 335–360.
  13. [13]Fan, C., Lu, W., Song, R., and Zhou, Y. (2017), “Concordance-Assisted Learning for Estimating Optimal Individualized Treatment Regimes,” Journal of the Royal Statistical Society: Series B (Statistical Methodology), 79, 1565–1582.DOI
  14. [14]Fedorov, V. V. (1972), Theory of Optimal Experiments, New York: Academic Press.
  15. [15]Frank, M. and Wolfe, P. (1956), “An algorithm for quadratic programming,” Naval Research Logistics Quarterly, 3, 95–110.DOI
  16. [16]G.-Tóth, B., Casado, L. G., Hendrix, E. M. T., and Messine, F. (2021), “On New Methods to Construct Lower Bounds in Simplicial Branch and Bound Based on Interval Arithmetic,” Journal of Global Optimization, 80, 779–804.
  17. [17]Gao, G., Ju, S., Sanz-Ausin, M., and Chi, M. (2023), “HOPE: Human-Centric Off-Policy Evaluation for E-Learning and Healthcare,” in Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS).arxiv.org/abs/2302.09212
  18. [18]Garivier, A. and Kaufmann, E. (2016), “Optimal Best Arm Identification with Fixed Confidence,” in Proceedings of the 29th Annual Conference on Learning Theory, PMLR, vol. 49 of Proceedings of Machine Learning Research, pp. 998–1027.
  19. [19]Hadad, V., Hirshberg, D. A., Zhan, R., Wager, S., and Athey, S. (2021), “Confidence Intervals for Policy Evaluation in Adaptive Experiments,” Proceedings of the National Academy of Sciences, 118, e2014602118.DOI
  20. [20]Hall, P. and Heyde, C. C. (1980), Martingale Limit Theory and Its Application, New York: Academic Press.
  21. [21]Hammer, S. M., Katzenstein, D. A., Hughes, M. D., Gundacker, H., Schooley, R. T., Haubrich, R. H., Henry, W. K., Lederman, M. M., Phair, J. P., Niu, M., Hirsch, M. S., and Merigan, T. C. (1996a), “AIDS Clinical Trials Group Study 175,” UCI Machine Learning Repository.DOI
  22. [23]Hanna, J. P., Chandak, Y., Thomas, P. S., White, M., Stone, P., and Niekum, S. (2024), “Data-Efficient Policy Evaluation Through Behavior Policy Search,” Journal of Machine Learning Research, 25, 1–58.
  23. [26]Jaggi, M. (2013), “Revisiting Frank–Wolfe: Projection-free sparse convex optimization,” in Proceedings of the 30th International Conference on Machine Learning (ICML), PMLR, vol. 28, pp. 427–435.
  24. [27]Jain, A., Hanna, J. P., and Precup, D. (2024), “Adaptive Exploration for Data-Efficient General Value Function Evaluations,” in Advances in Neural Information Processing Systems, vol. 37, pp. 18783–18814.arxiv.org/abs/2405.07838
  25. [28]Kallus, N., Saito, Y., and Uehara, M. (2021), “Optimal Off-Policy Evaluation from Multiple Logging Policies,” in Proceedings of the 38th International Conference on Machine Learning, PMLR, vol. 139 of Proceedings of Machine Learning Research, pp. 5247–5256.arxiv.org/abs/2010.11002
  26. [29]Lai, J., Zou, L., and Song, J. (2020), “Optimal Mixture Weights for Off-Policy Evaluation with Multiple Behavior Policies,” arXiv preprint arXiv:2011.14359.arxiv.org/abs/2011.14359
  27. [31]Liu, S. and Zhang, S. (2024), “Efficient Policy Evaluation with Offline Data Informed Behavior Policy Design,” in Proceedings of the 41st International Conference on Machine Learning, PMLR, vol. 235 of Proceedings of Machine Learning Research, pp. 32345–32368.arxiv.org/abs/2301.13734
  28. [32]Liu, S. D., Chen, C., and Zhang, S. (2025a), “Efficient Multi-Policy Evaluation for Reinforcement Learning,” Proceedings of the AAAI Conference on Artificial Intelligence, 39, 18951–18959.arxiv.org/abs/2408.08706
  29. [34]Mukherjee, S., Hanna, J. P., and Nowak, R. D. (2024a), “SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDP,” in Proceedings of the 41st International Conference on Machine Learning, PMLR, vol. 235 of Proceedings of Machine Learning Research, pp. 36531–36576.arxiv.org/abs/2406.02165
  30. [35]Mukherjee, S., Xie, Q., Hanna, J. P., and Nowak, R. (2024b), “SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Bandits,” in Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, PMLR, vol. 238 of Proceedings of Machine Learning Research, pp. 2962–2970.arxiv.org/abs/2301.12357
  31. [36]Nesterov, Y. (2005), “Smooth Minimization of Non-Smooth Functions,” Mathematical Programming, 103, 127–152.
  32. [37]Pukelsheim, F. (2006), Optimal Design of Experiments, vol. 50 of Classics in Applied Mathematics, Philadelphia, PA: Society for Industrial and Applied Mathematics.
  33. [38]Russo, A. and Pacchiano, A. (2025), “Adaptive Exploration for Multi-Reward Multi-Policy Evaluation,” in Proceedings of the 42nd International Conference on Machine Learning, PMLR, vol. 267 of Proceedings of Machine Learning Research, pp. 48931–48956.arxiv.org/abs/2502.02516
  34. [39]Tewari, A. and Murphy, S. A. (2017), “From Ads to Interventions: Contextual Bandits in Mobile Health,” in Mobile Health: Sensors, Analytic Methods, and Applications, eds. Rehg, J. M., Murphy, S. A., and Kumar, S., Springer, pp. 495–517.DOI
  35. [40]Tucker, A. D. and Joachims, T. (2023), “Variance-Minimizing Augmentation Logging for Counterfactual Evaluation in Contextual Bandits,” in Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, ACM, pp. 967–975.DOI
  36. [41]Wang, Y.-X., Agarwal, A., and Dudík, M. (2017), “Optimal and Adaptive Off-Policy Evaluation in Contextual Bandits,” in Proceedings of the 34th International Conference on Machine Learning, PMLR, vol. 70 of Proceedings of Machine Learning Research, pp. 3589–3597.arxiv.org/abs/1612.01205
  37. [42]Waudby-Smith, I., Wu, L., Ramdas, A., Karampatziakis, N., and Mineiro, P. (2024), “Anytime-Valid Off-Policy Inference for Contextual Bandits,” ACM/IMS Journal of Data Science, 1, 1–36.
  38. [43]Wynn, H. P. (1970), “The Sequential Generation of D-Optimum Experimental Designs,” The Annals of Mathematical Statistics, 41, 1655–1664.DOI
  39. [44]Zhan, R., Hadad, V., Hirshberg, D. A., and Athey, S. (2021), “Off-Policy Evaluation via Adaptive Weighting with Data from Contextual Bandits,” in Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2125–2135.
  40. [45]Zhang, K. W., Janson, L., and Murphy, S. A. (2020), “Inference for Batched Bandits,” Advances in Neural Information Processing Systems, 33, 9818–9829.arxiv.org/abs/2002.03217
  41. [46]Zhu, R. and Kveton, B. (2022), “Safe Optimal Design with Applications in Off-Policy Learning,” in Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, PMLR, vol. 151 of Proceedings of Machine Learning Research, pp. 2436–2447.

Paper details

vlnc:W_egktaarv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents