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:
- 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.
- 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