Mostly Exploration-Free Algorithms for Contextual Bandits
Preprint
Abstract
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 $\textit{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).
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Online Decision Making with High-Dimensional CovariatesOperations Research, 2020
- Learning to Optimize via Posterior SamplingMathematics of Operations Research, 2014
- Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit ProblemsFoundations and Trends in Machine Learning, 2012
- Dynamic Pricing Under a General Parametric Choice ModelOperations Research, 2012
- User-Friendly Tail Bounds for Matrix Martingales2011
- A contextual-bandit approach to personalized news article recommendation2010
- A Structured Multiarmed Bandit Problem and the Greedy PolicyIEEE Transactions on Automatic Control, 2009
- Woodroofe’s one-armed bandit problem revisitedThe Annals of Applied Probability, 2009
- Optimal aggregation of classifiers in statistical learningThe Annals of Statistics, 2004
- Strong consistency of maximum quasi-likelihood estimators in generalized linear models with fixed and adaptive designsThe Annals of Statistics, 1999