Bayesian Inference of Contextual Bandit Policies via Empirical Likelihood

AI summary

Overview

Research area: Off-policy evaluation and statistical inference for contextual bandits (stat.ML / statistics methodology).

Technical level: Advanced. The paper builds on empirical likelihood theory, Lagrange duality, and Bayesian posterior computation, and assumes familiarity with importance sampling estimators.

Scope: The paper develops a Bayesian empirical likelihood method for jointly evaluating and comparing multiple contextual bandit policies in finite-sample regimes, and applies it to simulated bandit experiments and an adolescent body mass index data set.

What This Paper Is About

Contextual bandit policies decide which action to take given context information, and practitioners often want to know how well a policy would have performed using only data collected by a different ("behavior") policy. The standard tool for this, off-policy evaluation, gives point estimates, but reliable uncertainty quantification remains hard because the distribution of the importance weights is unknown and standard chi-squared approximations are badly calibrated when samples are small. This paper replaces that frequentist chi-squared calibration with a Bayesian treatment of the empirical likelihood, so that policy values, policy differences, and comparisons among multiple correlated policies all come with well-calibrated uncertainty.

Key Contributions

1. A joint empirical likelihood for multiple policies. The authors define an empirical likelihood for the value vector v of ℓ policies at once, built on the estimating equation v = E[w_a r_a] plus an additional constraint E[w_a] = 1. This extra constraint bounds the likelihood's support to the true support [0,1]^ℓ and makes the likelihood invariant to whether policies are measured by value or by regret. Including the constraint makes the maximum empirical likelihood estimator correspond to the self-normalized importance sampling (SNIS) estimator; omitting it corresponds to the plain importance sampling (IS) estimator.

2. Bayesian inference with empirical likelihood instead of a chi-squared approximation. Rather than relying on Wilks' theorem (which only behaves like a chi-squared distribution at large sample sizes), the authors place a prior — uninformative or informative — on the policy value and derive a joint posterior distribution. This yields credible regions and supports arbitrary probability statements about policies, such as P(v_new > v_baseline + δ), P(v_new > (1+δ)v_baseline), or P(g(v_new, v_baseline) ≥ 0).

3. A dedicated empirical likelihood for the policy value difference. For the comparison d = v_new − v_baseline, the authors project v onto a one-dimensional interval and define a separate log-empirical likelihood for d, which is more directly aligned with policy comparison and cheaper to compute than the full joint posterior.

4. A practical computational scheme. Because each empirical likelihood evaluation requires solving an optimization problem, the authors approximate posteriors on a fine grid over an adaptive sub-support {v_j | L(v) ≥ c⁻¹L*}, where L* is the maximum empirical likelihood over the full support. This avoids wasting computation on regions where the likelihood is effectively zero and can be parallelized.

Main Findings

• The proposed empirical likelihood may not have a unique maximizer. Because the formulation optimizes over all probability measures on the hyperrectangular support S rather than a fixed set of points, the empirical likelihood can be flat over some region. The authors state that this non-uniqueness does not affect the subsequent Bayesian inference.

• HPD intervals are more robust than Wilks' intervals in finite samples. In simulation with 10,000 replicates at nominal levels of 90% and 95%, both interval types converge to nominal coverage as sample size grows, but at small sample sizes the HPD (Bayesian) intervals are better calibrated. For the baseline policy, both intervals overcover, with Wilks' intervals showing stronger overcoverage. For the new policy, Wilks' coverage probabilities "deviate significantly" from nominal levels when the sample size is small.

• Wilks' intervals are wider and more variable. At small sample sizes, Wilks' intervals are approximately 10% wider than HPD intervals on average, and this margin quickly drops to zero as sample size increases. In the undercoverage case, Wilks' interval widths spread over a larger range, with a significant proportion of intervals being too narrow — which the authors identify as the explanation for the undercoverage.

• Correlated policies require joint treatment. In the policy comparison experiment at sample size 100, the joint posterior shows that v_baseline and v_new are not independent, which the authors say demonstrates the necessity of joint inference using either the policy value vector v or the value difference d.

• Joint and univariate posteriors give similar comparison probabilities. The probability P(d > δ) from the one-dimensional posterior is not strictly identical to the corresponding probability from the joint posterior, but the authors report that the two share similar values.

• Simulation setup specifics. The simulated bandit has K = 10 arms, common context x_c ∈ ℝ^12 drawn from Dirichlet(1, …, 1), arm-specific context x_a ∈ ℝ^12 drawn from N(0, I_d), Bernoulli rewards with β₀ = 0 and β₁ = 3, and a completely randomized behavior policy. The baseline policy (sample size 256, m = 1, s = 2, K′ = 3) has a true value of 0.75, the new policy (sample size 1024, m = 1, s = 1, K′ = 1) has a true value of 0.83, and the oracle policy that always picks the best arm has a true value of 0.84. True values were computed by Monte Carlo integration with one million random points.

• The BMI application. The abstract and introduction state that the method is applied to an adolescent body mass index data set; the specific results of that application are not included in the available content of the paper.

Methodology in Plain English

The authors start from the standard off-policy evaluation identity: the value of a target policy equals the average of rewards reweighted by the ratio of the target policy's action probability to the behavior policy's action probability. That ratio is the importance weight. Rather than plugging these weights into a fixed formula, the authors treat the policy value as the unknown parameter of an empirical likelihood — a nonparametric likelihood that assigns probabilities to observed data points so as to satisfy the estimating equations exactly. They extend this from one policy to several, tracking a vector of importance weights and a vector of policy values simultaneously, and adding the constraint that the importance weights average to one.

Solving the resulting constrained optimization through its Lagrange dual turns the problem into a minimax expression that can be evaluated numerically. Because the empirical likelihood is not an ordinary likelihood, the authors lean on prior work (Lazar 2003; Grendár and Judge 2009) that justifies using it as a posterior in the Bayesian sense. They place a prior on the policy value — a flat prior throughout the experiments — and compute the posterior by evaluating the likelihood on a fine grid. To keep the grid useful as sample sizes grow (the likelihood concentrates on a tiny region), they first identify a shrunken adaptive support by finding where the likelihood exceeds a small fraction of its maximum, then place the grid inside it. Posterior probabilities and highest posterior density intervals are obtained by summing over the grid; the computation is embarrassingly parallel because each grid point is an independent optimization.

For the policy comparison experiments, the authors use a heuristic policy-learning procedure: fit a logistic regression per arm, form an upper confidence bound on each arm's success probability using a confidence-level parameter m, convert the bounds into action probabilities with a sharpness parameter s, and optionally restrict play to the top K′ arms.

Why This Matters

Impact on research. The paper addresses a real gap in off-policy evaluation: point estimators for bandit policies are well developed (IS, SNIS, doubly robust), but uncertainty quantification in small samples is unreliable. By moving empirical likelihood into a Bayesian framework, the work connects nonparametric likelihood methods to sequential decision-making and provides a principled way to make probability statements about policy differences and about multiple correlated policies — something the authors note is infeasible for existing single-policy methods.

Real-world applications (as cited in the paper):

• News article recommendation (Li et al., 2010)
• Personalized medicine (Tewari and Murphy, 2017)
• Design of clinical trials (Villar and Rosenberger, 2018)
• Advertisement optimization (Narita et al., 2019)
• Public-health analysis of adolescent body mass index

Industry relevance. Any organization running a recommender, ad-placement, or personalization system accumulates logged data collected by an older deployed policy and wants to know whether a new policy would be better before shipping it. This method lets practitioners report calibrated credible intervals and direct probabilities of improvement (for example, P(v_new > v_baseline + δ)) rather than only point estimates, which is directly useful for go/no-go decisions, and it does so without requiring the new policy to be run live.

Future Directions

• Scaling to higher-dimensional policy comparisons. The authors explicitly recommend reducing the dimension of v to a small number of policy value comparisons in high-dimensional cases; developing inference that scales to many simultaneously compared policies remains open.
• Understanding and exploiting the non-uniqueness of the maximum empirical likelihood estimator. Appendix B is said to discuss when the likelihood is flat, but the consequences for estimation (as opposed to Bayesian inference) are left unresolved.
• Choice and tuning of the adaptive support threshold c. The paper defers details on how c is chosen to Appendix D; principled, automatic selection of c across sample sizes is an evident next step.
• Extending beyond the simulation and the single BMI application. Broader empirical validation — larger numbers of arms, continuous or non-Bernoulli rewards, and estimated rather than known behavior policies — would test the method's practical reach. The paper assumes the behavior policy is known or well estimated.

Target Audience

Statisticians and machine learning researchers working on off-policy evaluation, contextual bandits, and reinforcement learning evaluation; methodologists interested in Bayesian empirical likelihood; and quantitatively trained practitioners in online experimentation, recommender systems, advertising, or clinical trial design who need trustworthy uncertainty statements about policy performance from logged data. Readers need comfort with importance sampling, likelihood-based inference, and basic duality arguments to follow the derivations.

Authors’ abstract

Policy inference plays an essential role in the contextual bandit problem. In this paper, we use empirical likelihood to develop a Bayesian inference method for the joint analysis of multiple contextual bandit policies in finite sample regimes. The proposed inference method is robust to small sample sizes and is able to provide accurate uncertainty measurements for policy value evaluation. In addition, it allows for flexible inferences on policy comparison with full uncertainty quantification. We demonstrate the effectiveness of the proposed inference method using Monte Carlo simulations and its application to an adolescent body mass index data set.