Source-linked AI summary
Learning from Logged Implicit Exploration Data
Alex Strehl, John Langford, Sham Kakade, Lihong Li
TL;DR
The paper studies how to learn and evaluate contextual-bandit policies from historical data when only chosen-action rewards are observed and the logging policy is unknown or nonrandom. It estimates logging action frequencies, converts records into thresholded importance-weighted events, and applies offline contextual-bandit learning. Theoretical results establish soundness under the paper's assumptions, while experiments on Yahoo! ad data support the estimator's ability to distinguish learned from random policies and sounder from naive approaches.
Problem
The problem is to construct a high-reward contextual policy from logged data generated by an uncontrolled, unknown logging policy when rewards for unchosen actions are unavailable.
Method
The method regresses estimated action frequencies ˆπ(a|x), forms synthetic events with weight 1/max{ˆπ(a|x), τ}, and applies an offline contextual-bandit algorithm.
Results
The estimator is theoretically sound, and empirical results distinguish learned policies from random policies and sounder approaches from a theoretically unsound naive approach.
Takeaways & Limitations
The approach supports policy learning and evaluation from historical exploration data even when no randomization was recorded, within the stated assumptions.
Takeaways & Limitations
The estimator can be a very loose lower bound when the evaluated policy often selects actions with small probability under the logging policy.
Abstract
from arXiv · showhide
We provide a sound and consistent foundation for the use of \emph{nonrandom} exploration data in "contextual bandit" or "partially labeled" settings where only the value of a chosen action is learned. The primary challenge in a variety of settings is that the exploration policy, in which "offline" data is logged, is not explicitly known. Prior solutions here require either control of the actions during the learning process, recorded random exploration, or actions chosen obliviously in a repeated manner. The techniques reported here lift these restrictions, allowing the learning of a policy for choosing actions given features from historical data where no randomization occurred or was logged. We empirically verify our solution on two reasonably sized sets of real-world data obtained from Yahoo!.
1. The Problem
The paper addresses warm-start policy learning for contextual bandits from logged data when the logging policy is unknown, nonrandom, and potentially query-dependent. It proposes estimating action frequencies, constructing importance-weighted synthetic events, and applying offline contextual-bandit learning, with theoretical and empirical support.
- The Problem: The warm-start problem seeks a policy maximizing rewards from logged events generated by an uncontrolled logging policy.Only the chosen action's reward is observed, so the setting is not standard supervised learning.
- Approaches that fail: Supervised regression can fail because its argmax may select actions absent or poorly represented in the training data.The paper gives an example where an action observed 10^-4 as often receives inadequate estimation despite being selected by the argmax.
- Approaches that fail: Standard bandit methods can require data linear in X × A, wasting generalization across contexts and actions.This is identified as a curse of dimensionality when methods are applied separately conditioned on X.
- Approaches that fail: Existing contextual-bandit methods require interaction or knowledge of the logging probability, while exploration scavenging assumes logging actions are independent of the query.The proposed setting has unknown logging probabilities and query-dependent logging.
- Our Approach: The approach estimates ˆπ(a|x) by regression and assigns each logged event the importance weight 1/max{ˆπ(a|x), τ}.The threshold τ controls numerical stability, and the offline learner can restrict its argmax to actions with positive estimated probability while weighting actions equally.
- Our Approach: A sequence of deterministic policies can be treated as a stochastic policy over actions when events are IID, because time variation supplies effective randomization.The estimated action frequency ˆπ(a|x) represents the expected display frequency over the logged timespan.
- Our Approach: Errors in ˆπ(a|x) require greater accuracy for small τ, whereas larger τ tolerates less accurate estimates but introduces mild downward bias for rarely displayed actions.The paper also reports theoretical analysis of policy selection and empirical evaluation on real ad data.
2. Formal Problem Setup and Assumptions
The formal setup models logged contextual-bandit data as outcomes from a sequence of possibly deterministic policies whose identities are unknown to the learner. An estimated logging policy and threshold then define an offline value estimator.
- Formal Problem Setup and Assumptions: Each round draws an input and reward vector from D, then selects an action according to the round-specific policy πt.The learner observes a sample containing x, the selected action a, and its reward ra.
- Formal Problem Setup and Assumptions: The learner is not given prior knowledge of the logging policies πt.
- Offline policy estimator: Given logged tuples, the method forms a predictor ˆπ mapping each input-action pair to an estimated selection probability.
- Offline policy estimator: A threshold τ ∈ [0, 1] is combined with ˆπ to construct an offline estimator for the value of a new policy h.
- Offline policy estimator: The estimator uses an indicator function to retain the reward contribution when the evaluated policy selects the logged action.
- Offline policy estimator: The threshold τ upper-bounds individual terms in the estimator's sum.
3. Theoretical Results
The paper estimates an unknown logging policy from historical data, then uses that estimate to evaluate and optimize policies despite deterministic or nonidentical logging. Its guarantees characterize estimator bias, consistency, support requirements, and optimization error.
- 3. Theoretical Results: The approach estimates the unknown logging policy and then optimizes a policy using the estimated logging policy.Theoretical analysis separates policy-estimation error from policy-optimization error.
- 3. Theoretical Results: Deterministic logging policies can be handled under IID data by treating variation across policies as randomization supplied by the world.The sequence of policies is related to a stochastic policy that uniformly randomizes over the policies.
- 3. Theoretical Results: The estimator is expectation-equivalent to evaluation under a fixed stochastic policy formed by uniformly averaging the sequence of logging policies.The equivalence relies on identical draws over T rounds and policies that do not depend on evaluation data.
- 3.1. Policy Estimation: The estimator is consistent, while its error can scale unfavorably with low-support actions through dependence on 1/τ.An example gives expected estimation error ϵ/τ when the true action probability is τ + ϵ but the estimate is τ.
- 3.1. Policy Estimation: The estimator’s bias has two sources: error in the estimated logging probabilities and thresholding by τ.The analysis uses squared loss for estimating logging probabilities because suitable sample-complexity bounds are available.
- 3.1. Policy Estimation: With perfect logging-policy estimation, the estimator provides a guaranteed lower bound on a policy’s true value, but the bound can be loose when chosen actions have low logging probability.The threshold τ controls the support requirement, and low-support actions can produce substantial underestimation.
- 3.2. Policy Optimization: Policy optimization can compete with the best hypothesis in H whose chosen actions have probability greater than τ under the averaged logging policy.Theorem 3.2 provides a high-probability generalization bound for the empirically selected policy, with independent but nonidentically distributed observations from the policy sequence.
4. Empirical Evaluation
The evaluation uses large-scale Yahoo! advertising logs to train and assess policies that select feasible ads using estimated click probabilities. Results show the estimator can distinguish learned, random, and theoretically unsound policies while remaining conservatively biased.
- The dataset contains approximately 880,000 ads, 35 million training events, 19 million test events, and 3.4 million distinct web pages.
- Page and ad representations use sparse word-frequency features, with a linear regressor over the combined feature representation.Each ad has about 30 ad features and each page about 50 page features.
- Using all data to estimate logging frequencies can make policy evaluation pessimistic, while train-only or split-data alternatives introduce distinct coverage or bias problems.A two-day example shows the estimator can overestimate the logging policy and drastically underestimate a better policy when ad availability changes.
- The learned policy selects a feasible ad maximizing a regression score trained to estimate click probability.Feasible ads are those with positive estimated logging-policy frequency.
- A naive supervised-learning policy receives 0 reward, whereas sounder approaches choose among explored ads.The naive policy’s argmax makes implausible choices rather than reliably finding unexplored good ads.
- Decreasing τ from 0.05 to 0.01 improves the estimated values of both learned and random policies.
- The test-set click-through rate was 0.0213, but it is not directly comparable with the best learned-policy estimate because the estimator is a biased lower bound.The comparison also differs in the set of ads available to deployed policies.
- The empirical results consistently provide pessimistic policy-value estimates while distinguishing learned policies from random and naive policies.They also distinguish policies using smaller versus larger feasible-ad spaces.
5. Conclusion
The paper presents and evaluates a method for warm-start exploration from logged data with controlled bias and estimation. It broadens applicability beyond input-independent logging policies while identifying a remaining boundary for adaptive, input-dependent logging.
- The paper states, justifies, and empirically evaluates a first method for warm-start exploration from logged data with controlled bias and estimation.
- The approach may also apply to reinforcement-learning settings by removing the need to know the chosen-action probability explicitly.This could allow learning from external observations of other agents.
- Unlike Exploration Scavenging, the method handles logging policies dependent on the current input but assumes a sequence of fixed policies.The paper leaves open offline estimation when logging policies both adapt over time and depend on current input.