Source-linked AI summary
Nonparametric Bandits with Covariates
Philippe Rigollet, Assaf Zeevi
TL;DR
The paper studies sequential two-arm bandits with noisy rewards depending on observed covariates, where the goal is to maximize cumulative expected reward. It develops UCBograms by localizing covariate space into regressogram-based bandit problems and derives matching-order upper and lower regret bounds up to logarithmic terms. The approach is limited by excessive binning when α ≥ 1.
Problem
Traditional UCB results rely on homogeneous iid rewards, while covariate-dependent nonparametric bandits require response-function estimation and have less understood regret complexity.
Method
UCBograms combine regressogram estimates with upper-confidence-bound terms, treating covariate bins as localized standard bandit problems.
Results
The UCBogram policy has polynomial regret, and a lower bound shows that no admissible policy can improve its polynomial order under the paper’s assumptions.
Takeaways & Limitations
The results connect nonparametric regression and traditional bandit methods while identifying smoothness and margin conditions as determinants of problem complexity.
Takeaways & Limitations
For α ≥ 1, UCBogram bins the covariate space too finely because it requires sampling each arm in every bin, incurring regret at least of order M^d.
Abstract
from arXiv · showhide
We consider a bandit problem which involves sequential sampling from two populations (arms). Each arm produces a noisy reward realization which depends on an observable random covariate. The goal is to maximize cumulative expected reward. We derive general lower bounds on the performance of any admissible policy, and develop an algorithm whose performance achieves the order of said lower bound up to logarithmic terms. This is done by decomposing the global problem into suitably "localized" bandit problems. Proofs blend ideas from nonparametric statistics and traditional methods used in the bandit literature.
1 Introduction
The paper studies bandits where rewards depend on observable covariates, extending traditional homogeneous-population UCB analysis to nonparametric response functions. It introduces UCBograms, proves polynomial regret and a matching-order lower bound, and connects bandit methods with nonparametric statistics.
- Motivation: The paper targets sequential treatment or advertisement allocation when observed covariates permit customized decisions but rewards are not identically distributed within each arm.Motivating settings include clinical treatment allocation and web advertising based on noisy efficacy or click-through observations.
- Related problem: Unlike homogeneous two-armed bandits, covariate-dependent rewards require policies that estimate each arm’s response function and select actions conditional on the observed covariate.Traditional UCB policies achieve order log n regret under iid rewards, while the paper studies the more flexible nonparametric setting.
- Assumptions and gap: The analysis assumes smooth arm-response functions and a margin condition, with the latter identified as a complexity measure for nonparametric bandits.Prior nonparametric policies were consistent, but their refined regret optimality and connection to response-function complexity were unclear.
- Contributions: UCBograms combine regressogram estimates with upper-confidence bounds by decomposing covariate space into bins that index localized bandit problems.Within each bin, mean responses are estimated by averaging and a suitable UCB modification determines arm selection.
- Contributions: The paper proves that UCBogram regret is polynomial in the horizon n, rather than bounded or logarithmic, and establishes a lower bound showing that no admissible policy improves this polynomial order under the assumptions.The authors present the lower bound as matching the upper-bound order from Theorem 3.1.
- Contributions: The paper also highlights possible synergies and connections between traditional bandit theory and nonparametric statistics.This connection is reflected in the use of regression estimation alongside confidence-bound exploration.
2 Description of the problem
The model supplies sequential covariates and arm-specific rewards, benchmarks policies against a covariate-dependent oracle, and measures both regret and inferior sampling. Complexity is controlled through smoothness and margin conditions, whose interaction determines whether the oracle is trivial.
- 2.1 Machine and game: The machine generates iid covariates and arm-specific rewards whose conditional means are unknown functions f^(i)(x), while a non-anticipating policy chooses one arm using prior observations.The oracle knows both response functions and selects the arm with the larger expected reward at the current covariate.
- 2.1 Machine and game: Regret compares a policy with the covariate-dependent oracle, while the inferior sampling rate counts expected pulls of a strictly suboptimal arm.The suboptimal arm can vary with the covariate value x.
- 2.1 Machine and game: Without regularity assumptions, regret and inferior sampling can approach the horizon n, making the game arbitrarily difficult.The paper therefore imposes structural conditions on the response functions and their separation.
- 2.2 Smoothness and margin conditions: The smoothness condition requires each response function to satisfy |f^(i)(x) − f^(i)(x′)| ≤ L∥x − x′∥^β for β ∈ (0, 1] and L > 0.It also implies that the gap function Δ = |f^(1) − f^(2)| is smooth with parameters (β, 2L).
- 2.2 Smoothness and margin conditions: Smoothness limits how rapidly the gap departs from zero, while the margin condition requires separation from zero except on a small-probability set.Their opposing effects jointly determine the problem’s complexity.
- 2.2 Smoothness and margin conditions: The margin condition controls how much probability mass lies near zero gap, with larger α indicating stronger separation and α close to 0 allowing the arm responses to be nearly indistinguishable.This parameter is used to characterize the complexity of the nonparametric bandit problem.
- 2.2 Smoothness and margin conditions: When αβ > 1, the oracle pulls one arm almost surely, whereas for αβ ≤ 1 machines with nontrivial covariate-dependent oracle policies exist.Thus the product αβ determines whether the assumptions permit meaningful arm switching.
3 Policy and main result
The paper constructs UCBogram policies by binning covariates, estimating arm responses with regressograms, and applying confidence bounds to localized bandit problems. Under smoothness and margin conditions, the resulting policy has a regret bound and an associated inferior-sampling-rate bound.
- 3.1 Binning and regressograms: Regressograms estimate each arm’s mean response by averaging rewards observed in the current covariate bin.The estimators are piecewise constant over the partition.
- 3.1 Binning and regressograms: The policy partitions the covariate space into bins, decomposing the nonparametric problem into M^d traditional bandit machines.Each bin corresponds to a local problem without covariates.
- 3.2 The UCBogram: UCBogram replaces each local average reward with the corresponding regressogram value and adds an upper-confidence term for stochastic uncertainty.The policy selects arms using these confidence-adjusted estimates at the current covariate.
- 3.2 The UCBogram: Under equivalent covariate density, smoothness, and margin conditions, Theorem 3.1 gives UCBogram an expected cumulative-regret upper bound with M = floor((n/log n)^(1/(2β+d))).The stated theorem applies for β in (0,1] and α in (0,1].
- 3.2 The UCBogram: The proof separates poorly distinguished bins from well-separated bins, treating the latter conditionally as standard two-armed bandits and applying UCB analysis.The margin condition controls the contribution of bins where the arms are not sufficiently separated.
- 3.2 The UCBogram: For α ≥ 1, UCBogram can use too many fixed bins, causing at least order M^d regret and an additional log n factor when α = 1.The paper notes that adaptive larger bins could reduce this limitation, but developing such policies is outside its scope.
- 3.3 The inferior sampling rate: Theorem 3.1’s regret guarantee yields a corresponding upper bound on the inferior sampling rate through Lemma 3.1 and Corollary 3.1.The connection between regret and inferior sampling is more involved here than in traditional bandits.
4 Lower bound
The lower-bound construction shows that the polynomial regret and inferior-sampling rates achieved by the policy are minimax-optimal for a broad class of conditional reward distributions. The proof constructs smooth, margin-constrained reward functions and reduces distinguishing them to hypothesis testing using KL-divergence bounds.
- The polynomial rates in the upper bounds are minimax-optimal for a large class of conditional reward distributions.This establishes a lower bound applying to any non-anticipating policy.
- For fixed α, β, and L with αβ < 1, the lower-bound construction uses uniformly distributed covariates on [0, 1]^d and reward functions satisfying smoothness and margin conditions.The theorem assumes αβ < 1, uniform covariates, and a reward family obeying both regularity conditions.
- The lower-bound argument applies to both regret and inferior sampling rate, with the latter obtained through the theorem’s stated bound and positivity threshold.The theorem explicitly states bounds for regret and inferior sampling rate, and the proof identifies positivity when n exceeds 16κ^2M^(2β+d).
- The proof reduces the bandit lower bound to a hypothesis-testing problem and controls distinguishability through KL-divergence calculations.The argument applies a standard nonparametric testing approach and uses the KL chain rule across sequential observations.
- The constructed functions are assembled from localized smooth bumps on a regular grid, with sign choices generating a family of alternatives.The family uses m localized bins and binary vectors ω ∈ {−1, 1}^m, while remaining equal to 1/2 outside the selected bins.
- The resulting rates also occur in the full-information classification setting, but the paper develops a technique tailored to partial-information bandit policies.The distinction concerns the proof technique rather than the final rate.