Contextual Bandit Algorithms with Supervised Learning Guarantees

By Alina Beygelzimer, J. Langford, Lihong Li, Lev Reyzin, Robert E. Schapire. 2010

356 citations recorded by the source corpus.

We address the problem of competing with any large set of N policies in the nonstochastic bandit setting, where the learner must repeatedly select among K actions but observes only the reward of the chosen action.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Evaluation & Benchmarks

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

In Evaluation & Benchmarks

Citations in the corpus

Contextual Dueling Bandits (2015, methodology): “Beygelzimer et al. (2011) prove that, with probability at least 1− δ, Exp4.”
Doubly Robust Policy Evaluation and Optimization (2014, background): “The following is a corollary of Theorem 1 of Beygelzimer et al. (2011).”
Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms (2010, methodology): “The EXP4 algorithm and its variants [6, 8] use the exponential weighting technique to achieve an ˜ O ( √ T ) regret in expectation, where ˜ O ( x ) def = O ( x ln x ), even if the sequence of contexts and payoﬀs are chosen by an adversarial world, but the computational complexity may be exponential…”
Fairness in Learning: Classic and Contextual Bandits (2016, background): “…– the stochastic multi-armed bandit problem is a special case of every contextual bandit problem, and for general contextual bandit problems, it is also known how to get non-trivial regret after only T = O ( k ) many rounds [Agarwal et al., 2014, Beygelzimer et al., 2011, Chu et al., 2011].”
Learning Representations for Counterfactual Inference (2016, background): “This setup comes up in diverse areas, for example off-policy evaluation in reinforcement learning (Sutton & Barto, 1998), learning from “logged implicit exploration data” (Strehl et al., 2010) or “logged bandit feedback” (Swaminathan & Joachims, 2015), and in understanding and designing complex…”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “Note that, from a theoretical point of view UCT was proved to perform poorly by Coquelin and Munos [2007], and a strategy based on a similar idea, but with improved theoretical performance, was proposed by Bubeck and Munos [2010]. Other applications in related directions have also been explored, see”
Learning to Optimize via Posterior Sampling (2013, neutral): “Following that, we review prior results and their relation to results of this paper.”
Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits (2014, methodology): “The following form of Freedman’s inequality for martingales is from Beygelzimer et al. (2011).”
Reinforcement and Imitation Learning via Interactive No-Regret Learning (2014, background): “The problem may be cast as a contextual bandit problem [2, 6] where features of the current state deﬁne the context of exploration.”
Provable Optimal Algorithms for Generalized Linear Contextual Bandits (2017, background): “With the development of modern technologies, contextual bandit problems have more applications, especially in web-based recommendation, advertising and search (Agarwal et al., 2009; Li et al., 2010; 2012).”
Equal Opportunity in Online Classification with Partial Feedback (2019, methodology): “The learner ﬁrst predicts +1 for roughly T 2 ↵ rounds, then uses the collected data to deﬁne a set of fair policies according to the observed empirical distribution, and lastly runs the EXP4 algorithm [3, 6] over the set of fair policies.”
PAC-Bayes-Bernstein Inequality for Martingales and its Application to Multiarmed Bandits (2011, background): “The existing theoretical analysis of the exploration-exploitation trade-off in problems that go beyond multiarmed bandits is mainly focused on the worst-case scenarios (Strehl et al., 2009; Jaksch et al., 2010; Beygelzimer et al., 2011, 2009).”
Neural Contextual Bandits with UCB-based Exploration (2019, background): “One line of work is the family of expert learning algorithms (Auer et al., 2002; Beygelzimer et al., 2011) that typically have a time complexity linear in the number of experts (which in many cases can be exponential in the number of parameters).”
Introduction to Multi-Armed Bandits (2019, background): “applied, achieving regret bound OPT E[REW] O~(T=B) p KTlogj j: This regret rate matches (10.15) when OPT > (T), and is optimal in the regime B> (T). The “primal” algorithm ALG 1 is Exp4:P from Beygelzimer et al. (2011), the high-probability version of algorithm Exp4 from Section 6.4. Like Exp4”
Risk and parameter convergence of logistic regression (2018, background): “The key observation is that the Lipschitz continuity of ` allows a sharp control on the conditional variance, by which the martingale Bernstein bound (e.g., Theorem 1 in Beygelzimer et al. (2011)) gives Lemma 2.5.”
Budgeted Learning for Developing Personalized Treatment (2014, background): “subgroups or biomarker profiles) have been studied under the name of contexual bandits or bandit with covariates, [8], [9].”