PaperlayerView exact revision on arXiv

Source-linked AI summary

Mostly Exploration-Free Algorithms for Contextual Bandits

Hamsa Bastani, Mohsen Bayati, Khashayar Khosravi

arXiv:1704.09011v8stat.MLcs.LG

TL;DR

Contextual bandits traditionally rely on exploration, which may be costly or unethical, while greedy algorithms can fail to learn optimal policies. This paper analyzes when greedy learning is sufficient and introduces Greedy-First, which begins greedily and explores only after detecting failure. The authors show that Greedy-First is rate optimal without covariate-diversity or arm-number assumptions, while reducing exploration when greedy learning succeeds.

  • Problem

    Exploration-based contextual bandit methods can be costly or unethical, while greedy algorithms may fail to learn optimal policies and incur linear regret.

  • Method

    The paper analyzes greedy algorithms and introduces Greedy-First, which follows a greedy policy initially and switches to exploration when needed.

  • Results

    Greedy-First achieves rate-optimal regret without covariate-diversity or arm-number assumptions, remains exploration-free under covariate diversity, and can reduce exploration otherwise.

  • Takeaways & Limitations

    Greedy exploration may be unnecessary in some contextual bandit instances, while Greedy-First provides a compromise between avoiding exploration and learning the true policy.

  • Takeaways & Limitations

    A pure greedy algorithm can achieve linear regret on average when it fails to converge, including in instances without covariate diversity.

Abstract

from arXiv · show

The contextual bandit literature has traditionally focused on algorithms that address the exploration-exploitation tradeoff. In particular, greedy algorithms that exploit current estimates without any exploration may be sub-optimal in general. However, exploration-free greedy algorithms are desirable in practical settings where exploration may be costly or unethical (e.g., clinical trials). Surprisingly, we find that a simple greedy algorithm can be rate optimal (achieves asymptotically optimal regret) if there is sufficient randomness in the observed contexts (covariates). We prove that this is always the case for a two-armed bandit under a general class of context distributions that satisfy a condition we term covariate diversity. Furthermore, even absent this condition, we show that a greedy algorithm can be rate optimal with positive probability. Thus, standard bandit algorithms may unnecessarily explore. Motivated by these results, we introduce Greedy-First, a new algorithm that uses only observed contexts and rewards to determine whether to follow a greedy algorithm or to explore. We prove that this algorithm is rate optimal without any additional assumptions on the context distribution or the number of arms. Extensive simulations demonstrate that Greedy-First successfully reduces exploration and outperforms existing (exploration-based) contextual bandit algorithms such as Thompson sampling or upper confidence bound (UCB).

1. Introduction

Contextual bandits personalize decisions by learning arm-specific rewards from individual contexts, but exploration can be costly or unethical. The paper shows that greedy methods can sometimes achieve optimal regret and introduces Greedy-First to reduce exploration while retaining rate-optimal guarantees.

  • Problem setting: Contextual bandits choose among K arms using individual context vectors to learn unknown parameters predicting rewards over T individuals.The setting includes linear and generalized linear reward models.
  • Motivation: Exploration improves future decisions but can be costly, infeasible, unethical, or damaging in applications such as medicine and marketing.Insufficient exploration can prevent learning the true arm parameters and yield poor performance.
  • Greedy algorithms: A simple greedy algorithm can achieve state-of-the-art asymptotic performance when observed contexts provide sufficient randomness through covariate diversity.For two arms, the result applies to linear rewards and extends to generalized linear models.
  • Greedy algorithms: Even without covariate diversity, greedy methods converge to the optimal policy with positive probability, although they may incur linear regret when they fail.The success probability depends on problem parameters.
  • Greedy-First: Greedy-First begins greedily and switches to a standard exploration-based algorithm when it detects that the greedy approach has failed.It uses observed contexts and rewards to determine when exploration is needed.
  • Greedy-First: Greedy-First achieves rate-optimal regret without covariate-diversity or arm-number restrictions while reducing exploration and outperforming standard bandit algorithms in simulations.It remains purely greedy with high probability when covariate diversity holds and reduces expected forced exploration otherwise.

2. Problem Formulation

The paper formulates contextual bandits as sequential learning with unknown arm parameters and context-dependent stochastic rewards, evaluated by cumulative expected regret. It then states margin, boundedness, and covariate-diversity assumptions used to analyze greedy policies and gives distributional examples satisfying them.

  • 2. Problem Formulation: A K-armed contextual bandit presents i.i.d. individual contexts, unknown arm parameters, and stochastic rewards observed only for the selected arm.The policy learns arm parameters sequentially while receiving no counterfactual feedback from unchosen arms.
  • 2. Problem Formulation: Performance is measured by cumulative expected regret against an oracle that knows the arm parameters and chooses the best expected arm for each context.Instantaneous regret is the expected reward difference between the oracle’s choice and the selected arm.
  • 2.1. Assumptions: The model assumes bounded contexts and arm parameters, with context norms at most xmax and parameter norms at most bmax.These bounds constrain the context support and parameter set used in the analysis.
  • 2.1. Assumptions: The α-margin condition controls context probability near the decision boundary, with higher α imposing stronger assumptions on the context density.The paper uses α = 1 for simplicity but states that its results extend to general α, including greedy convergence.
  • 2.1. Assumptions: Covariate diversity requires context-weighted covariance to remain positive definite on every half space, ensuring sufficient randomness for each arm to receive informative contexts.The condition is used to prove that the greedy algorithm converges to the optimal policy and to ensure persistent excitation for each arm.
  • 2.2. Examples of Distributions Satisfying Assumptions 1-3: Covariate diversity holds for distributions including bounded-support densities positive near the origin, uniform and truncated Gaussian distributions, and binary Rademacher contexts.The paper also notes that discrete and product distributions can satisfy the relevant assumptions.
  • 2.1. Assumptions: Without exploration, a greedy policy may drop an arm and fail to provide the persistent excitation needed for arm-parameter estimates to converge.Covariate diversity instead guarantees excitation for every arm regardless of the bandit algorithm’s sample path.
  • 2.2. Examples of Distributions Satisfying Assumptions 1-3: A sufficient distributional criterion uses a symmetric set around the origin, comparable densities at paired points, and a third stated condition; then Assumption 3 follows.Lemma 1 provides these easier-to-check conditions, while the discrete case replaces integrals with sums.

3. Greedy Bandit

The Greedy Bandit selects the arm with the highest estimated contextual reward and updates only the chosen arm’s parameter estimate. Under covariate diversity, it achieves logarithmic regret and can remain rate optimal more generally with positive probability.

  • Estimation: Arm parameters are estimated by ordinary least squares using the design matrix and outcomes collected when each arm was played.The estimator equals (X⊤X)^−1X⊤Y when the design covariance is invertible.
  • Algorithm: The algorithm plays the arm with the highest estimated reward for each observed context, breaking ties randomly.It updates only the selected arm’s estimate using observations assigned to that arm.
  • Performance: For two arms satisfying the stated assumptions, the Greedy Bandit has logarithmic cumulative regret and is rate optimal.The paper combines its upper bound with an O(log T) lower bound for two-armed contextual bandits.
  • Covariate diversity: Under covariate diversity, the expected covariance matrix for each arm grows linearly, providing sufficient observations and enabling parameter convergence.The resulting guarantees extend to generalized linear rewards and yield logarithmic regret for two arms.
  • Scope and comparison: The analysis extends beyond two arms and general margin conditions, although the Greedy Bandit bound can scale worse in dimension than the OLS Bandit bound.For standard covariate-diverse distributions, the stated bound is O(d^3(log d)^(3/2) log T), versus O(d^2(log d)^(3/2) log T) for OLS Bandit.
  • Without covariate diversity: Without covariate diversity, the greedy algorithm still converges to the correct policy and achieves rate-optimal performance with problem-specific positive probability.The success probability improves with less noise, fewer arms, more initialization samples, and larger arm gaps.

4. Greedy-First Algorithm

Greedy-First begins with greedy decisions and monitors covariance growth and parameter convergence. It switches to a forced-exploration contextual bandit when the diagnostic condition fails, preserving logarithmic regret without covariate-diversity or arm-count restrictions.

  • Design: Greedy-First uses observed contexts and rewards to follow a greedy policy when parameter estimates appear to converge, avoiding forced exploration when possible.Its guarantee does not require the additional covariate-diversity or two-arm assumptions needed for the basic greedy analysis.
  • Switching rule: The algorithm monitors the minimum eigenvalue of each arm’s sample covariance matrix against the threshold λ0t/4.If the condition is not met, Greedy-First switches to a standard bandit algorithm with forced exploration.
  • Practical tuning: The input choices λ0 and t0 affect empirical performance and the probability that Greedy-First remains exploration-free.The paper advises choosing t0 much larger than Kd because a small initialization period may trigger an incorrect switch.
  • Guarantees: Greedy-First always achieves O(log T) cumulative regret, including when it switches to the OLS Bandit.The bound combines an initialization cost with logarithmic regret before and after the switch.
  • Purely greedy operation: When two arms satisfy covariate diversity, Greedy-First remains purely greedy with probability at least 1 − δ.Here δ decreases exponentially with t0, so increasing the initialization period can make the switching probability arbitrarily small.
  • General settings: With arbitrary arm count and without covariate diversity, Greedy-First can still switch with probability one when some arms’ covariance matrices fail to grow sufficiently fast.This behavior can allow the decision-maker to drop such arms while retaining logarithmic regret guarantees.

5. Simulations

Simulations on synthetic and real healthcare data show that Greedy-First adapts exploration to whether greedy learning succeeds, achieving robust regret performance across favorable and unfavorable settings.

  • Synthetic Data: Greedy-First matches Greedy Bandit when covariate diversity holds because it never switches to OLS Bandit.
  • Synthetic Data: When covariate diversity fails, Greedy Bandit incurs linear regret, whereas Greedy-First is the clear frontrunner.Greedy-First benefits because greedy learning succeeds on some instances but fails on others.
  • Synthetic Data: Greedy-First explores only after detecting likely greedy failure, avoiding unnecessary exploration while learning the true policy.
  • Logistic Reward: In logistic-reward simulations, Greedy Bandit far outperforms GLM-UCB, whose performance severely degrades as xmax increases.The paper attributes this degradation to a conservative confidence-bound term that is exponentially large in xmax.
  • Real Datasets: On real healthcare datasets, Greedy-First is a robust frontrunner: it matches or outperforms competing algorithms depending on whether exploration is necessary.It performs best when greedy learning gets stuck, but can underperform Greedy Bandit when exploration hurts short-horizon performance.
  • Real Datasets: In one healthcare dataset, Greedy Bandit performs best because a rarely optimal high-dose arm is better dropped over the short horizon.Greedy-First explores that under-sampled arm and consequently performs worse than Greedy Bandit.
  • Overall Results: Across the reported results, Greedy-First matches Greedy Bandit when exploration is unnecessary and matches or outperforms competing bandit algorithms when exploration is necessary.

6. Conclusions and Discussions

The paper argues that greedy contextual-bandit algorithms can achieve strong regret guarantees without deliberate exploration, while Greedy-First selectively explores when the data indicate it is necessary.

  • Main conclusions: Greedy algorithms can be rate optimal in cumulative regret for two-armed contextual bandits when contexts satisfy covariate diversity.Covariate diversity requires positive-definite context covariance conditioned on any half space.
  • Main conclusions: Even without covariate diversity, greedy algorithms can converge to the optimal policy with some probability.This creates a risk of under-exploration when the problem instance is not known to be amenable to greediness.
  • Greedy-First: Greedy-First begins with a greedy policy and explores only when observed data indicate exploration is necessary.The method is intended for settings where decision-makers want guaranteed convergence without always exploring.
  • Greedy-First: Greedy-First is rate optimal without covariate diversity or restrictions on the number of arms.It remains exploration-free when covariate diversity holds and may reduce exploration when it does not.
  • Empirical implications: Empirical results suggest Greedy-First outperforms standard contextual-bandit algorithms while balancing reduced exploration with convergence to the correct policy.The comparison includes UCB, Thompson sampling, and epsilon-greedy methods.

Appendix B: Useful Concentration Results

This appendix collects concentration results used in the paper’s analysis, including a matrix concentration theorem for adapted positive-semidefinite sequences.

  • Concentration results: It also applies a theorem from Wainwright (2019) by setting b_k = 0 and ν_k = σ_k.These substitutions specialize the cited theorem for the paper’s proof.
  • Concentration results: The appendix invokes a concentration result for finite sequences of positive-semidefinite matrices adapted to a filtration.The cited result is identified as Theorem 3.1 of Tropp (2011).

Appendix C: Proof of Theorem 1

The proof of Theorem 1 bounds Greedy Bandit’s instantaneous regret by partitioning context regions, controlling estimation errors, and summing the resulting bounds over time.

  • Proof strategy: The proof first establishes a lemma for Greedy Bandit’s instantaneous regret using a peeling argument.The analysis conditions on context regions and uses concentration bounds for estimated arm parameters.
  • Proof strategy: Regret is decomposed across arms and regions where one arm is superior to another.The decomposition also accounts for random tie-breaking and nonnegative regret.
  • Probability control: The proof controls wrong-arm selection through conditional probability bounds, independence, union bounds, and Cauchy-Schwarz inequalities.These steps combine concentration events with the margin condition.
  • Final bound: Theorem 1 follows by summing instantaneous expected regret through time T and applying the preceding lemmas.The proof explicitly uses K = 2 and bounds the initial regret term by 2x_maxb_max.

D.1. Proof of Corollary 1

The proof of Corollary 1 adapts the instantaneous-regret analysis to a general margin parameter α, yielding asymptotic bounds after controlling the resulting summation.

  • Proof adaptation: The corollary modifies the bound on the probability that contexts fall in each region using an α-margin condition.The remaining arguments from Lemma 6 continue to apply.
  • Summation bound: The proof shows that the relevant summation is bounded by a quantity depending only on d and α.This isolates the time dependence in the term δ^(1+α).
  • Summation bound: For sufficiently large peeling indices, exponential decay controls the terms, while finitely many smaller indices are bounded directly.The threshold depends on the dimension d and the margin parameter α.
  • Final step: The proof completes the result by summing instantaneous regret over t = 1,2,...,T and applying the two-arm setting.The desired asymptotic bound follows from the resulting integral estimate.

D.2. Proof of Proposition 1

The proof establishes uniqueness and estimation control for generalized linear models, then uses these properties to bound Greedy Bandit’s regret. It also describes the forced-sampling and greedy decision structure used in the analysis.

  • Proof of Proposition 1: Positive definiteness of X⊤X ensures that the maximum-likelihood equation has a unique solution.The argument uses strict positivity of µ′ and injectivity of the associated mapping.
  • Proof of Proposition 1: The estimation analysis bounds parameter error when the design matrix is positive definite and the transformed noise term is sufficiently small.The bound is derived using mθ, the minimum derivative of the link function over a bounded interval.
  • Proof of Proposition 1: Greedy Bandit’s generalized-linear-model analysis converts parameter concentration into an upper bound on instantaneous expected regret.The bound depends on d, σ, xmax, link-function regularity, and constants from the assumptions and earlier proposition.
  • Proof of Proposition 1: The algorithm combines forced sampling with estimates from forced and all observed samples to eliminate clearly sub-optimal arms before greedy selection.Forced samples are taken regardless of the observed covariates; remaining decisions use the highest estimated reward among surviving arms.

Appendix F: Missing Proofs of §3.5 and §4.3

The appendix derives monotonicity properties for the greedy-success probability and analyzes limiting behavior through the auxiliary function L. The results compare effects of model parameters such as m, h, and σ.

  • Monotonicity results: The proofs establish monotonicity by differentiating auxiliary functions and taking infima over the admissible parameter space.The argument repeatedly uses decreasing behavior of functions such as f or g on the relevant regime.
  • Monotonicity results: Sgb(m1,K,σ,xmax,λ1,h) = Sgb(m2,K,σ,xmax,λ1,h) under the stated reparameterization relating m1 and m2.The equality follows by shifting the optimization variable p and comparing the corresponding L functions.
  • Monotonicity results: Sgb(m,K,σ,xmax,λ1,h1) ≤ Sgb(m,K,σ,xmax,λ1,h2) when h1 < h2.The proof uses the fact that the h-dependent exponential terms in L decrease as h increases.
  • Limiting behavior: The appendix studies limits as σ approaches zero by selecting σ-dependent values of γ, δ, and p and evaluating L or L′.The derivations bound the resulting expressions using constants independent of σ.

F.1. Proofs of Theorems 2 and 4

The proofs of Theorems 2 and 4 show how initial random sampling supports covariance growth and accurate estimates, allowing greedy decisions to retain optimal arms and reject sub-optimal ones. These properties yield probability guarantees for greedy success and logarithmic regret.

  • F.1. Proofs of Theorems 2 and 4: If arm estimates remain within radius θ1 of their true parameters, covariance matrices for optimal arms grow linearly while sub-optimal arms are not selected by Greedy Bandit.The result combines parameter accuracy with the separation condition for sub-optimal arms.
  • F.1. Proofs of Theorems 2 and 4: A sufficiently large covariance-matrix minimum eigenvalue implies that an arm’s estimate is close to its true parameter with high probability.This concentration property is used to control the event that all arm estimates remain accurate.
  • F.1. Proofs of Theorems 2 and 4: During the first Km periods, each arm receives m random samples from the context distribution, providing the initial covariance structure.These samples are independent across arms because they come from the random-sampling phase.
  • F.1. Proofs of Theorems 2 and 4: Under the required accuracy events, Greedy Bandit succeeds with a lower-bounded probability and achieves logarithmic regret.The proof combines the event bounds with the fact that optimal arms continue receiving informative samples while sub-optimal arms remain unplayed.
  • F.1. Proofs of Theorems 2 and 4: Greedy-First does not switch to the exploratory algorithm when the stated minimum-eigenvalue conditions hold for all relevant arms and times.This identifies a sufficient event under which the algorithm remains greedy after the initial phase.

Appendix G: Additional Simulations

The additional simulations examine Greedy Bandit as the number of arms and context dimension vary, while also studying Greedy-First’s switching and input parameters. Figure 5 focuses on five arms and shows a sharp performance change as d increases.

  • Appendix G: Additional Simulations: The simulations vary K and d for Greedy Bandit and examine t0, h, and q for Greedy-First.Greedy Bandit is described as parameter-free, whereas Greedy-First’s switching and post-switch behavior depend on these inputs.
  • Appendix G: Additional Simulations: Figure 5 shows a sharp change in Greedy Bandit’s performance for K = 5 arms as d increases.The figure is presented as a performance-versus-d comparison for the five-arm setting.

G.1. More than Two Arms (K > 2)

For K > 2 arms, Greedy-First performs competitively across dimensions and avoids the poor low-dimensional behavior observed for Greedy Bandit. The simulations suggest that higher dimension benefits greedy approaches, while Greedy Bandit's performance worsens as the number of arms increases.

  • The simulations vary d = 2,3,...,10 with K = 5 arms while scaling noise variance by d to keep the signal-to-noise ratio fixed.
  • Greedy Bandit's performance improves dramatically with dimension but degrades as the number of arms increases.The simulations attribute the degradation to the greater chance of dropping an arm after an early poor parameter estimate.
  • When dimension is small relative to the number of arms, Greedy Bandit may drop an arm and incur linear regret.The authors conjecture that the turning point occurs when d ≥K −1.
  • At d = 3, Greedy Bandit performs poorly, while Greedy-First performs nearly as well as the best algorithms.

G.2. Sensitivity to parameters

The sensitivity analysis examines how Greedy-First responds to its input parameters h, q, and t0. Its performance is reported to be quite robust to the choice of these inputs.

  • Greedy-First's sensitivity analysis varies the input parameters h, q, and t0.The analysis uses the same problem parameters as Figure 2 when covariate diversity does not hold.
  • Greedy Bandit is entirely parameter-free, unlike Greedy-First.
  • Greedy-First performs quite robustly across choices of its input parameters.
Loading 1704.09011v8…