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

Amitakshar Biswas, Ruoqing ZhuarXiv 2026 · arXiv

TL;DR

This paper introduces Adaptive Greedy, an algorithm for "buying" data from multiple sources (loggers) with different costs to evaluate a set of target policies. By sequentially selecting the logger that offers the best cost-normalized variance reduction, the method converges to an optimal experimental design and provides statistically valid, high-accuracy evaluations at a fraction of the computational cost of traditional optimization methods.

What Problem Does This Paper Address?

In many real-world scenarios—like clinical trials or recommendation systems—we want to know how a new "target" policy will perform without actually deploying it. This is called Off-Policy Evaluation (OPE).

Usually, researchers take whatever data they already have. However, this paper looks at a more active scenario: What if you have a limited budget and can choose to "purchase" more observations from several existing sources?

Each source (or "logger") has a different behavior and a different cost per observation. For example, a cheap logger might only explore a few safe actions, while an expensive one provides the broad coverage needed to evaluate a complex new policy. The challenge is to figure out the best way to spend your budget across these loggers to minimize the uncertainty (variance) of your evaluation, especially when you are trying to evaluate multiple target policies simultaneously and want to ensure the "worst-case" policy is still estimated accurately (a minimax objective).

Methods

The authors propose the Adaptive Greedy algorithm. Its core components include:

  • Sequential Selection: Instead of deciding an allocation upfront, the algorithm buys one observation at a time. It estimates the reward distribution on the fly and picks the logger that provides the largest estimated reduction in variance per unit of cost.
  • Minimax Smoothing: To handle multiple target policies, the algorithm aims to minimize the maximum variance among them. Since "the maximum" is a non-smooth function, they use a log-sum-exp approximation to make the optimization mathematically tractable.
  • Forced Sampling: To prevent the algorithm from ignoring certain loggers early on due to poor initial estimates, they include a "forced sampling" mechanism. This ensures enough coverage of the action space to maintain reliable estimates.
  • Pooled AIPW Estimator: Once data is collected, they use a "pooled" Augmented Inverse Propensity Weighted (AIPW) estimator. This technique combines data from all loggers into a single mixture, which is theoretically proven to be more efficient than treating each logger's data separately.
  • Theoretical Framework: The authors show that this greedy approach is essentially a "conditional-gradient" (Frank-Wolfe) step for the underlying experimental design problem.

Datasets

The researchers evaluated their approach using:

  1. Synthetic Environments (A, B, and C): These involved 5 loggers, 5 actions, and 4 target policies. The environments varied in cost structures and how much the target policies overlapped with the loggers' behaviors to test the algorithm's robustness.
  2. ACTG 175 (AIDS Clinical Trials Group Study 175): A semi-synthetic application based on a real-world randomized trial of HIV treatments. They used the real patient covariates and treatment outcomes to build a "ground truth" model, then simulated the budgeted acquisition process to see if Adaptive Greedy could efficiently evaluate different treatment regimes.

Key Insights and Ideas

  • Cost-Normalized Value: The "aha moment" is that the best logger isn't necessarily the one that provides the most information, nor the cheapest one—it’s the one with the best ratio of information-to-price.
  • Anytime Accuracy: Because the algorithm is greedy and doesn't "plan" for a specific final budget, it is robust to early stopping. If your budget is suddenly cut, the data you've collected so far is already organized into a near-optimal design for that smaller budget.
  • Statistical Validity of Adaptive Data: A major theoretical contribution is proving that even though the data was collected adaptively (where later choices depend on earlier rewards), the final pooled estimator is still asymptotically normal and attains the semiparametric efficiency bound.
  • Computational Efficiency: Traditional methods often require solving complex integer programs. Adaptive Greedy achieves similar accuracy by simply comparing $K$ (number of loggers) indices at each step.

Key Results

  • Superior Accuracy: In synthetic tests, Adaptive Greedy reduced the "worst-target" Root Mean Squared Error (RMSE) by 17% to 51% compared to standard strategies like "equal expenditure" or "cheapest only."
  • Speedup: In the ACTG 175 application, Adaptive Greedy was roughly 10 times faster than "Reoptimized Plug-in" methods (which solve a full optimization problem every few steps) while matching their accuracy.
  • Convergence: The authors proved, and empirically demonstrated, that the algorithm's logger allocation converges to the theoretically optimal "minimax" design as the budget increases.

Limitations and Future Work

  • Known Propensities: The current work assumes the logging policies (the probabilities with which the sources take actions) are known. If these must be estimated, it adds another layer of uncertainty.
  • Fixed Pricing: The model assumes the cost per observation is constant. In some markets, prices might fluctuate based on how much data you have already purchased (variable pricing).
  • Regression Assumptions: The inference results rely on the reward regression model being reasonably well-behaved (Assumption 5), which might be challenging with very complex, high-dimensional data without specific cross-fitting techniques.

Summary updated

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.
BibTeX
@misc{biswas2026adaptive,
  author = {Amitakshar Biswas and Ruoqing Zhu},
  title = {{Adaptive Budgeted Data Acquisition for Robust Off-Policy Evaluation from Multiple Loggers}},
  year = {2026},
  eprint = {2611.10095},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.10095},
}
Figure