Source-linked AI summary
Contextual Bandit Algorithms with Supervised Learning Guarantees
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, Robert E. Schapire
TL;DR
The paper asks how to learn contextual-bandit decisions when only chosen-action feedback is observed. It introduces Exp4.P and a VC-based extension, obtaining supervised-learning-style high-probability regret guarantees, while retaining an explicit-expert-weight computational limitation.
Problem
Contextual-bandit learners must explore while receiving feedback only for chosen actions, unlike full-label supervised learning.
Method
Exp4.P combines Exp4 and Exp3.P with a sharper martingale analysis, and a VC argument extends it to infinite finite-VC policy classes.
Results
Exp4.P obtains high-probability regret O(sqrt(KT ln(N/δ))) for N experts, while the VC-based result obtains O(sqrt(T(d ln(T) + ln(1/δ)))).
Takeaways & Limitations
The guarantees bring contextual-bandit exploration closer to supervised-learning guarantees, requiring only a factor of K more experience for matched accuracy and confidence.
Takeaways & Limitations
Exp4.P can become inefficient for very large N because it requires explicit weights over experts.
Abstract
from arXiv · showhide
We address the problem of learning in an online, bandit setting where the learner must repeatedly select among $K$ actions, but only receives partial feedback based on its choices. We establish two new facts: First, using a new algorithm called Exp4.P, we show that it is possible to compete with the best in a set of $N$ experts with probability $1-δ$ while incurring regret at most $O(\sqrt{KT\ln(N/δ)})$ over $T$ time steps. The new algorithm is tested empirically in a large-scale, real-world dataset. Second, we give a new algorithm called VE that competes with a possibly infinite set of policies of VC-dimension $d$ while incurring regret at most $O(\sqrt{T(d\ln(T) + \ln (1/δ))})$ with probability $1-δ$. These guarantees improve on those of all previous algorithms, whether in a stochastic or adversarial environment, and bring us closer to providing supervised learning type guarantees for the contextual bandit setting.
1 INTRODUCTION
The paper studies contextual bandits, where learners choose actions with partial feedback, and develops high-probability guarantees that approach supervised-learning performance. It introduces Exp4.P for finite expert classes and extends the approach to VC-dimension-bounded policy classes, while noting computational and stochastic-setting boundaries.
- Motivation: Contextual bandits require exploration because learners observe rewards only for chosen actions, with applications such as personalized content recommendation.Contexts can include search queries or geolocation.
- Main results: Exp4.P achieves high-probability regret O(sqrt(KT ln(N/δ))) when competing with a finite set of N experts.The guarantee applies in the adversarial contextual bandit setting and improves on the prior stochastic high-probability rate stated in the paper.
- Main results: The paper extends the approach to possibly infinite policy classes with finite VC-dimension d, obtaining regret O(sqrt(T(d ln(T) + ln(1/δ)))) under stochastic sampling.The VC-dimension result assumes contexts and rewards are drawn independently from a fixed, unknown distribution.
- Implication: The central claim is that contextual-bandit learning needs only a factor of K more experience than supervised learning for equal accuracy and confidence.The paper presents this as a supervised-learning-type guarantee for exploration problems.
- Limitation and evaluation: Exp4.P becomes inefficient when N is too large because it must maintain explicit weights over experts, although structured exponentially large classes may remain tractable.The paper reports an efficient implementation applied to a large-scale real-world problem.
- Method: Exp4.P combines Exp4 and Exp3.P and uses a sharper martingale analysis based on an exponential-moment argument.The paper derives a Freedman-style inequality for martingales to support the analysis.
2 PROBLEM SETTING AND NOTATION
The formal setting gives the learner contextual information, requires choosing one of K actions, and reveals only the chosen reward. Performance is measured by regret against the best policy or expert in the available class.
- Experts and policies: Each expert’s advice vector is a probability distribution over the K arms, with entry ξ_i,j(t) giving the probability of choosing arm j.For deterministic policies, the vector has one component equal to 1 and all others equal to 0.
- Experts and policies: A policy π induces an expert that predicts according to π(x_t), using the context only to generate its action recommendation.The notation distinguishes expert indices i from arm indices j.
- Interaction protocol: On each round, the learner observes context, receives expert recommendations, chooses one of K actions, and sees only that action’s reward.The world commits to the reward vector before recommendations and the learner’s choice.
- Performance measures: The learner’s cumulative return is the sum of rewards for its chosen actions, while each expert’s expected return is computed from its advice vector and reward vector.The paper denotes the learner’s return by G_A and the expert’s per-round expected reward by y_i(t).
- Performance measures: Regret is the difference between the cumulative reward of the best expert and the learner’s reward, and high-probability bounds are defined over algorithm and reward randomness.The best expert’s return is denoted G_max.
3 A GENERAL RESULT FOR MARTINGALES
The section develops a martingale concentration result in which variance is treated as a random variable, then uses it to obtain a Freedman-style high-probability bound.
- The variance is treated as a random variable rather than replaced only by an a priori variance bound.The result permits any fixed estimate of the variance, while the standard Freedman-style corollary uses an a priori upper bound.
- The theorem assumes Xt ≤ R and conditional mean Et[Xt] = 0 for every round.
- The bound holds with probability at least 1 − δ for the resulting martingale guarantee.
- The proof uses conditional expectations, exponential-moment arguments, and elementary inequalities to establish the result.
4 A HIGH PROBABILITY ALGORITHM
Exp4.P combines Exp4 and Exp3.P with confidence bounds to compete with a finite expert class under partial feedback and high-probability guarantees.
- Exp4.P is introduced as an algorithm with a formal performance guarantee.
- Theorem 2 assumes ln(N/δ) ≤ KT and includes an expert selecting an action uniformly at random each round.
- The algorithm initializes equal expert weights, computes action probabilities, samples one action, and observes only its reward.
- Its proof uses an upper confidence bound on each expert’s expected reward derived from an estimated reward.
- The analysis applies a martingale theorem to the estimation error, whose conditional mean is zero and whose values are bounded above by 1.
5 COMPETING WITH SETS OF FINITE VC DIMENSION
The paper extends Exp4.P to compete with possibly infinite policy classes of finite VC dimension by reducing them to finite expert sets using an initial exploration phase.
- Exp4.P applies to an infinite policy class with VC dimension d when contexts and rewards are sampled independently from a fixed unknown distribution.The section initially assumes two actions, with extensions to more actions through multiclass VC dimension and Sauer’s lemma.
- VE partitions policies by their advice on the first τ rounds, selects one representative per class, and runs Exp4.P on the resulting finite set.
- Theorem 5 gives a high-probability guarantee for every distribution over contexts and rewards and every policy set of VC dimension d.
- The proof bounds initial exploration, Exp4.P’s regret against the representative set, and the representative set’s regret against the original policy class.
- Sauer’s lemma bounds the number of policy behaviors on a fixed observation sequence, enabling the finite reduction.
- The argument transfers the fixed-sequence result to i.i.d. samples using exchangeability.
6 A PRACTICAL IMPROVEMENT TO EXP4.P
The section presents an alternative way to set action probabilities in Exp4.P that preserves the analysis requirements while reducing unnecessary probability mass on poorly performing actions.
- The probability-setting procedure must satisfy two required properties for the Exp4.P analysis.
- Each action probability pj(t) is constrained to be at least pmin.
- Uniform mixing is simple and achieves optimal regret up to a multiplicative constant, but can assign unnecessary mass to badly performing arms.
- Algorithm 2 enforces the minimum probability from the smallest to largest action probabilities and has per-round computational complexity O(K ln K).
- The alternate method preserves the proof with little modification and is used in the experiments.
7 EXPERIMENTS
The experiments evaluate Exp4.P for personalized Yahoo! front-page article recommendation using contextual expert policies and large-scale randomized traffic data. Exp4.P uses efficient implementation for structured experts and trades greater exploration for the highest deployment eCTR.
- Experimental setting: Exp4.P was evaluated on personalized Yahoo! front-page recommendation, where articles are arms and clicks define the payoff and CTR metric.The goal is to maximize total clicks on recommended articles from a changing pool of candidate news articles.
- Expert representation: The experiment used B = 5 user clusters, with experts mapping each cluster to an article through a vector a ∈{1, . . ., K}^B.Users were assigned cluster-membership features whose nonnegative components sum to 1.
- Efficient implementation: Exp4.P runs in time linear in K and B despite an exponentially large structured expert class.The implementation computes final arm-selection probabilities implicitly from maintained quantities rather than enumerating every expert.
- Dataset: The Yahoo! dataset contains over 41M user visits, 253 articles, and about 21 candidate articles per visit.Historical visits were collected under a uniformly random policy from May 1 to 9, 2009, enabling unbiased evaluation estimates.
- Results: Exp4.P achieved the highest deployment eCTR, while its more conservative exploration made its learning-bucket eCTR slightly worse than Exp4.The additional variance-control terms encourage further exploration; the deployment result implies a superior greedy policy relative to Exp4.
- Results: The ϵ-greedy variant had the highest learning-bucket eCTR but the lowest deployment-bucket eCTR among the three algorithms.This comparison is presented as evidence for the benefits of Exp4.P’s soft-max exploration scheme.
A PROOF OF LEMMA 4
The proof establishes bounds on estimated quantities under Lemma 4’s conditions and derives the result through a sequence of inequalities, logarithmic transformation, and summation over T rounds.
- Lemma 4: Under Theorem 2’s conditions, the estimated quantities satisfy ˆyi(t) ≤ 1/pmin and ˆvi(t) ≤ 1/pmin.These bounds are stated as Lemma 4’s result.
- Derivation: The derivation uses elementary exponential and quadratic inequalities, then takes logarithms, sums over T, and applies ln(1 + x) ≤ x.The proof states that Inequalities 1 through 3 support the subsequent steps and corollary.
- Proof setup: The proof introduces normalized weights ¯wi(t) = wi(t)/Wt and applies an exponential-weight expression involving ¯wi(t) exp (bˆyi(t) + cˆvi(t)).The normalized weights and exponential expression are used in the proof’s intermediate inequalities.