Adaptive Budgeted Data Acquisition for Robust Off-Policy Evaluation from Multiple Loggers
Organizations: Department of Statistics, University of Illinois at Urbana-Champaign
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.
Figures & tables
| Method | Environment A | Environment B | Environment C |
|---|---|---|---|
| Adaptive Greedy | 5.30 (0.25) | 5.73 (0.27) | 4.31 (0.28) |
| Reoptimized plug-in | 5.37 (0.25) | 5.72 (0.27) | 4.29 (0.28) |
| Estimated static | 6.38 (0.30) | 7.35 (0.37) | 4.35 (0.25) |
| Equal expenditure | 6.69 (0.29) | 6.71 (0.28) | 5.24 (0.34) |
| Cheapest only | 9.17 (0.48) | 9.97 (0.45) | 8.83 (0.59) |
| Oracle static | 5.31 (0.24) | 5.62 (0.25) | 4.33 (0.29) |
| Method | ||||
|---|---|---|---|---|
| Adaptive Greedy | 113 (6.2) | 58.4 (2.6) | 28.3 (1.4) | 18.8 (0.85) |
| Reoptimized plug-in | 125 (9.7) | 56.1 (2.4) | 28.2 (1.4) | 18.6 (0.87) |
| Estimated static | 134 (9.2) | 65.5 (7.2) | 31.0 (1.5) | 21.9 (1.6) |
| Equal expenditure | 119 (5.7) | 63.1 (3.1) | 31.2 (1.5) | 22.8 (1.2) |
| Cheapest only | 125 (7.2) | 60.9 (2.9) | 30.4 (1.5) | 21.2 (0.96) |
| Oracle static | 121 (11) | 56.7 (2.6) | 27.9 (1.4) | 18.6 (0.84) |
Appendix figures & tables15 assets
Supplementary material from the paper’s appendix.
Appendix
| Symbol | Meaning |
|---|---|
| Numbers of loggers and target policies. | |
| Logger and target policy . | |
| Value of target , and the conditional mean and variance of the reward. | |
| Cost of logger , and the set of loggers affordable at step . | |
| Counts and money spent after purchases, the budget, and the number of purchases when the budget is spent. | |
| Probability simplex, and the sample fractions in it. |
| Experiment | Replications |
|---|---|
| Environments A and B | 200 |
| Environment C | 100 |
| Misleading initialization | 100 per initialization |
| Misspecified reward model | 100 |
| Weak overlap | 100 |
| Sensitivity to and | 50 per setting |
| Environment | ||
|---|---|---|
| A | ||
| B | ||
| C |
| Environment | Budget | Target | Empirical SD | Mean SE | SE/SD | Coverage | MCSE |
|---|---|---|---|---|---|---|---|
| A | 6000 | 1 | 0.008227 | 0.008401 | 1.021 | 0.964 | 0.0083 |
| A | 6000 | 2 | 0.008563 | 0.008610 | 1.005 | 0.944 | 0.0103 |
| A | 6000 | 3 | 0.010898 | 0.011053 | 1.014 | 0.948 | 0.0099 |
| A | 6000 | 4 | 0.010511 | 0.010655 | 1.014 | 0.952 | 0.0096 |
| A | 24000 | 1 | 0.004153 | 0.004251 | 1.023 | 0.944 | 0.0103 |
| A | 24000 | 2 | 0.004227 | 0.004403 | 1.042 | 0.958 | 0.0090 |
| Environment | Budget | Coverage | MCSE |
|---|---|---|---|
| A | 6000 | 0.956 | 0.0092 |
| A | 24000 | 0.950 | 0.0097 |
| B | 6000 | 0.960 | 0.0088 |
| B | 24000 | 0.958 | 0.0090 |
| Budget | Final estimator | Block-split estimator |
|---|---|---|
| 1500 | 0.02218 | 0.03898 |
| 6000 | 0.01076 | 0.01353 |
| Intermediate budget | ||
|---|---|---|
| 200 | 1.538371 | 0.464505 |
| 500 | 1.179021 | 0.142007 |
| 700 | 1.138549 | 0.125322 |
| 1000 | 1.092325 | 0.101177 |
| 2000 | 1.036573 | 0.062111 |
| 3000 | 1.023061 | 0.048914 |
| Intermediate budget | Adaptive Greedy trajectory | Adaptive Greedy separate run | Reoptimized trajectory | Reoptimized separate run |
|---|---|---|---|---|
| 500 | 1.179021 | 1.187451 | 1.414239 | 1.186214 |
| 1000 | 1.092325 | 1.090244 | 1.722523 | 1.105435 |
| 3000 | 1.023061 | 1.022266 | 1.285166 | 1.023932 |
| Intermediate budget | Plan for intermediate budget | Mean purchased counts | Mean | Mean |
| Original costs | ||||
| 500 | 1.414 | 0.169 | ||
| 700 | 1.556 | 0.205 | ||
| 1000 | 1.723 | 0.225 | ||
| 2000 | 1.593 | 0.216 | ||
| 3000 | 1.285 | 0.144 | ||
| 500 | 0.7957 | 0.0408 | 0.0130 | 0.1390 | 0.0115 | 1.11505 | 0.10277 |
|---|---|---|---|---|---|---|---|
| 1500 | 0.7883 | 0.0269 | 0.0081 | 0.1729 | 0.0038 | 1.04539 | 0.06461 |
| 6000 | 0.8046 | 0.0107 | 0.0169 | 0.1669 | 0.0009 | 1.01680 | 0.03043 |
| 12000 | 0.8086 | 0.0057 | 0.0218 | 0.1634 | 0.0005 | 1.01045 | 0.01994 |
Off-Policy Evaluation
Off-policy evaluation estimates a policy’s value from data collected by another policy, using weighting, models, and uncertainty-aware methods.
See all 81 papers