Doubly robust off-policy evaluation with shrinkage

1. Introduction

• The framework optimizes a sharp mean squared error bound to shrink importance weights, using predictor-agnostic pessimistic or predictor-quality-aware optimistic bounds.The authors seek systematic shrinkage strategies that adapt to reward-predictor quality without requiring strong assumptions about it.Source: §1 · p. 1
• The analysis shows that standard weight clipping corresponds to pessimistic shrinkage, providing a theoretical justification for the practice.Earlier approaches motivated shrinkage as a bias–variance heuristic but did not explain when or how to use different methods.Source: §1 · p. 1
• Optimistic shrinkage yields new estimators for atomic and combinatorial actions, including settings where a policy recommends a list of articles.The paper cites list recommendation as an example of combinatorial actions.Source: §1 · pp. 1–2
• Across 108 conditions from 9 real-world data sets and a combinatorial learning-to-rank data set, the authors report efficacy in all instances and identify a robust configuration through ablations.The atomic-action conditions vary data-set size, feature dimensions, policy overlap, and reward-estimator quality; the combinatorial evaluation varies reward-estimator quality.Source: §1 · p. 2
• Unlike kernel optimal matching, which relies on reward-function assumptions and runs super-linearly in data-set size, this approach uses essentially no modeling assumptions and a single data pass.The comparison is with KOM as described by Kallus (2017; 2018).Source: §1 · p. 2
• The authors investigate how weight shrinkage and reward-predictor training interact, reporting that MRDR performs poorly when combined with shrinkage.They note that different estimators may require different reward predictors.Source: §1 · p. 2

2. Setup

• Off-policy evaluation estimates a target policy’s average reward from context-action-reward data gathered by a logging policy.The estimator’s quality is measured by mean squared error, decomposed into bias and variance.Source: §2 · p. 2
• Direct modeling imputes rewards with a predictor, while inverse propensity scoring reweights observed rewards; DR combines these approaches.DM can have low variance but be biased by predictor approximation error, whereas IPS is unbiased under the stated overlap condition but can have high variance.Source: §2 · pp. 2–3
• The logging policy must assign positive probability wherever the target policy does, and the reward predictor is not assumed to be high quality.The predictor is fit on separate data; the analysis allows approximation error and does not assume its function class contains a good reward approximation.Source: §2 · pp. 2–3
• DR adds an importance-weighted residual correction to imputed rewards, preserving unbiasedness and attaining asymptotic optimality under weaker assumptions than other methods.Its variance can nevertheless be high when importance weights are large.Source: §2 · p. 3

3. Our Approach: DR with Shrinkage

• DR with shrinkage replaces standard DR weights with weights selected by optimizing sharp upper bounds on mean squared error, separately bounding bias and variance.The framework considers optimistic and pessimistic bounds; shrinkage weights are constrained not to exceed the original importance weights.Source: §3 · p. 3

3.1. DR with Optimistic Shrinkage

• Optimistic shrinkage uses a bound that adapts to reward-predictor quality and is expected to be tighter when the predictor is more accurate.Its parameterized weights recover DM at λ = 0 and standard DR as λ →∞.Source: §3.1 · pp. 3–4

3.2. DR with Pessimistic Shrinkage

• Pessimistic shrinkage assumes only that predictions lie in [0, 1] and recovers existing weight-clipping approaches.As with optimistic shrinkage, λ = 0 gives DM and λ →∞ gives DR.Source: §3.2 · p. 4

• Standard DR and IPS variance can scale linearly with the number of actions, which is typically exponential in dimension.Source: §4 · p. 4
• Under linear expected rewards, the pseudo-inverse DR estimator uses vector-valued importance weights, which the combinatorial shrinkage method scales by factors in [0, 1].Source: §4 · p. 5
• The first weight-shrinkage estimator for contextual combinatorial bandits applies to slate actions such as ranked lists.Source: §4 · pp. 4–5
• The combinatorial variance proxy is established assuming the logging policy is supported on a linearly independent action set and the shrunk weights preserve action-wise shrinkage.Source: §4 · p. 5
• The proxy’s norm term depends on the support set, not logging probabilities; an approximate barycentric spanner gives ∥vπ,x∥1 = O(d), while the non-combinatorial case recovers Proposition 1.Source: §4 · p. 5

• The procedure selects hyperparameters by minimizing the squared data-dependent bias upper bound plus estimated variance.Source: §5 · p. 5
• It compares favorably with all included unbiased estimators up to O(n^-3/2), and is asymptotically optimal when the candidate set includes standard DR.Source: §5 · p. 5
• The bias bounds used in experiments approximate three bias expressions with sample averages, and adjusted variants add twice the standard error.Source: §5 · p. 5
• Unlike MAGIC, the procedure selects one hyperparameter rather than aggregating several; it also uses different bias and variance estimates.Source: §5 · p. 6
• The procedure uses the SWITCH pessimistic bias bound, adds two empirically helpful bounding strategies, and gives an oracle-inequality justification.Source: §5 · p. 6

6.1. Non-combinatorial Setting

• The evaluation spans 108 conditions from nine UCI datasets, while combinatorial evaluation uses a learning-to-rank dataset; predictors, policies, and reward settings vary across experiments.Evaluation uses all available bandit data except for learning curves; each dataset has six logging policies and deterministic or stochastic rewards.Source: §6.1.1 · p. 6, §6.1 · p. 6, §6 · p. 6

6.1.1. OFF-POLICY EVALUATION

• With shrinkage, z = w^2 emerges as the best reward-predictor choice for DRs, whereas z ≡ 1 and z = w are top choices for DR.MRDR is dominated by other predictors in the experiments, except for the zero reward predictor.Source: §6.1.1 · pp. 6–7
• Both optimistic and pessimistic shrinkage matter for robust performance across conditions when paired with a fixed reward predictor.The comparison uses oracle tuning for λ.Source: §6.1.1 · p. 7
• DRs-direct has strong aggregate performance for both reward types, while DRs-upper leads by a large margin for deterministic rewards but degrades with stochastic rewards.The authors advocate DRs-direct as their final method because of its more robust performance.Source: §6.1.1 · p. 7

6.1.2. OFF-POLICY LEARNING

• DRs-direct outperforms DM, DR, and IPS on three of four UCI datasets; on optdigits, all methods perform similarly.Figure 3 reports average learned-policy value normalized by IPS across 10 replicates; DM and DR use hindsight-optimal hyperparameters, while DRs uses model selection.Source: §6.1.2 · p. 7, Figure 3 · p. 8

6.2. Combinatorial Setting

• DRs-PI outperforms DR by a factor of 1.5 or more across combinatorial conditions, while oracle-tuned DRs-PI indicates further potential from improved model selection.The reported MSE is on a log scale and averages 20 replicates.Source: Figure 2 · p. 8, §6.2 · p. 9

7. Conclusion

• The optimization-based framework derives shrinkage-based doubly robust estimators, recovers prior weight clipping, and yields novel optimistic estimators for atomic and combinatorial settings.Experiments demonstrate estimator efficacy and highlight model selection's role in performance; closing the gap with oracle tuning is identified as future work.Source: §7 · p. 9

• For each eligible context-action pair, the minimization is strongly convex and has a unique minimizer.Source: A. Derivation of Shrinkage Estimators… · p. 11
• When w>λ, the pessimistic solution sets ˆw=λ; when 0≤w≤λ, it leaves ˆw=w, yielding the clipped estimator.Source: A. Derivation of Shrinkage Estimators… · p. 11
• The optimistic estimator does not depend on the weighting function z or on how the regression model is trained.Source: A. Derivation of Shrinkage Estimators… · p. 11

B. Derivation of the Shrinkage Estimator for Combinatorial Setting

• Under a linear reward-model assumption and bounded predictions, the combinatorial derivation obtains an optimistic weight formula that matches the non-combinatorial solution.Source: B. Derivation of the Shrinkage… · pp. 11–12

C.1. Proof of Proposition 1

• The derivation bounds bias using the reward-model loss and bounds variance assuming predictions and rewards lie in [0, 1] and shrunk weights do not exceed original weights in magnitude.Source: B. Derivation of the Shrinkage… · p. 12

C.2. Proof of Proposition 2

• For the variance argument, the proof uses a basis-action pseudoinverse and bounds separate terms using the linear basis representation and bounded predictions and rewards.Source: §C.2 · pp. 13–14

C.3. Proof of Theorem 3

• The proof’s main technical step is a deviation inequality for sample variance, with a variance-estimation lemma for bounded iid variables.Source: §C.3 · p. 15

C.4. Construction of Upper Bounds on Bias

• Empirically, using the estimators alone rather than the bias upper bounds led to better performance.Source: §C.4 · p. 16
• Direct bias estimation approximates the expectation with a sample average and inflates it to obtain a high-probability upper bound.Source: §C.4 · p. 17
• The pessimistic bias estimate analytically averages over actions after eliminating reward dependence, which the authors say leads to lower variance.Source: §C.4 · p. 17
• The optimistic bias bound estimates a regressor-related term and an importance-weight term, with the two estimates described as fairly low variance.Source: §C.4 · p. 17

• The shrinkage and SWITCH coefficients are selected from a grid of 30 geometrically spaced values, with ranges defined using importance-weight quantiles.Source: §D.1 · p. 18
• For deterministic targets, both estimator types matter, while z=1 and z=w are more favorable reward-predictor weights than z=w², likely because z=w² has high training variance.Source: §D.1 · p. 18, Table 5 · p. 19
• Dir-all and Up-all are most frequently statistically indistinguishable from the best across model-selection comparisons, suggesting robustness of the pointwise-minimum bias estimate.Source: §D.1 · p. 18
• The additional comparisons cover friendly, adversarial, and uniform logging, plus an aggregated small-sample setting of 200 bandit samples across 108 conditions.Source: §D.1 · p. 18
• DRs-upper is most often in the top group and the unique winner across reward-predictor choices; DRs-direct also outperforms snIPS, snDR, and SWITCH.Source: §D.1 · p. 18

Hyperparameter grid

• The shrinkage parameter λ is selected from 15 geometrically spaced values based on the 0.05 and 0.95 quantiles of logged-data weights, with boundary values for DM and DR-PI.The grid endpoints are 0.01 × (w0.05)^2 and 100 × (w0.95)^2; the added boundary values are λ = 10^-50 and λ = 10^30.Source: §D.2 · p. 19

Basis construction

• The logging distribution is supported on a linearly independent action basis constructed using Algorithm 1, whose size is 1 + ℓ(m − 1) for lists of length ℓ from m items.Source: §D.2 · p. 19

Experimental comparisons

• Figures 4–6 show normalized-MSE CDFs across conditions for friendly and adversary scenarios, uniform logging and small-data regimes, and robustness tests of DRs-direct and DRs-upper.The robustness figure includes versions selecting reward predictors from all listed options, including MRDR.Source: Figure 4 · p. 20, Figure 5 · p. 20, Figure 6 · p. 21
• Tables 7–11 report, across all conditions, counts of when each estimator is statistically indistinguishable from the best and uniquely best, under specified reward-predictor choices.Table 6 compares model-selection methods across reward-predictor sets and shrinkage types. Its columns are indexed by model-selection methods, while its rows are indexed by reward predictors and shrinkage type.Source: Table 6 · p. 20, Table 7 · p. 21, Table 8 · p. 21

D.2. Experimental Details for Combinatorial Actions

• Satimage configurations use the π2 logging base with α = 0.3, β = 0.2 and α = 0.95, β = 0.1; the latter is tested with deterministic and stochastic rewards.Source: §D.2 · p. 24
• Vehicle experiments include π1 and π2 logging bases with α values of 0.3, 0.5, 0.7, and 0.95, plus π0 with α = 1/k; reward variants are deterministic or stochastic.The listed settings use β = 0.2 for α values 0.3, 0.5, and 0.7; β = 0.1 for α = 0.95; and β = 0 for π0 with α = 1/k.Source: §D.2 · p. 25
• Page-blocks experiments use π1 and π2 logging bases with α = 0.3, 0.5, 0.7, or 0.95, and π0 with α = 1/k, under deterministic or stochastic rewards.The listed β settings are 0.2 for α values 0.3, 0.5, and 0.7; 0.1 for α = 0.95; and 0 for π0 with α = 1/k.Source: §D.2 · p. 25