Mostly Exploration-Free Algorithms for Contextual Bandits
Top Cited Papers
- 1 March 2021
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Management Science
- Vol. 67 (3) , 1329-1349
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 suboptimal 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. This paper was accepted by J. George Shanthikumar, big data analytics.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Simultaneously Learning and Optimizing Using Controlled Variance PricingManagement Science, 2014
- The BATTLE Trial: Personalizing Therapy for Lung CancerCancer Discovery, 2011
- Woodroofe’s one-armed bandit problem revisitedThe Annals of Applied Probability, 2009
- Arbitrary side observations in bandit problemsAdvances in Applied Mathematics, 2005
- Strong consistency of maximum quasi-likelihood estimators in generalized linear models with fixed and adaptive designsThe Annals of Statistics, 1999
- One-Armed Bandit Problems with CovariatesThe Annals of Statistics, 1991
- Persistent excitation in adaptive systemsInternational Journal of Control, 1987
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985
- A One-Armed Bandit Problem with a Concomitant VariableJournal of the American Statistical Association, 1979
- ON THE LIKELIHOOD THAT ONE UNKNOWN PROBABILITY EXCEEDS ANOTHER IN VIEW OF THE EVIDENCE OF TWO SAMPLESBiometrika, 1933