Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits

By Alekh Agarwal, Daniel J. Hsu, Satyen Kale, J. Langford, Lihong Li, Robert E. Schapire. 2014

564 citations recorded by the source corpus.

We present a new algorithm for the contextual bandit learning problem, where the learner repeatedly takes one of K actions in response to the observed context, and observes the reward only for that action. Our method assumes access to an oracle for solving fully supervised cost-sensitive classification problems and achieves the statistically optimal regret guarantee with only O(√KT) oracle calls across all T rounds. By doing so, we obtain the most practical contextual bandit learning algorithm amongst approaches that work for general policy classes. We conduct a proof-of-concept experiment which demonstrates the excellent computational and statistical performance of (an online variant of) our algorithm relative to several strong baselines.

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

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

Citations in the corpus

Contextual Dueling Bandits (2015, methodology): “To address this difficulty, we propose an approach used previously in other works on contextual bandits (Langford and Zhang, 2007; Dudı́k et al., 2011; Agarwal et al., 2014).”
Concrete Problems in AI Safety (2016, background): “In practice, real world RL projects can often avoid these issues by simply hard-coding an avoidance of catastrophic behaviors.”
Balanced Linear Contextual Bandits (2018, methodology): “2010), (Agrawal and Goyal 2013), (Agarwal et al. 2014), (Bastani and Bayati 2015).”
Estimation Considerations in Contextual Bandits (2017, methodology): “Apart from baselines that belong in the family of contextual bandits with linear realizability assumption and have strong theoretical guarantees, we also evaluate the policy-based ILOVETOCONBANDITS (ILTCB) from [4] that does not estimate a model, but instead it assumes access to an oracle for solvin”
Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling (2018, methodology): “We evaluated the algorithms (see Appendix A) on several bandit problems constructed from real-world datasets ([26, 27, 28] and Appendix B for details).”
Off-policy Bandits with Deficient Support (2020, methodology): “Specifically, unlike in online learning for contextual bandits [1, 29], batch learning from bandit feedback (BLBF) operates in the off-policy setting.”
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].”
Mapping Instructions and Visual Observations to Actions with Reinforcement Learning (2017, methodology): “We address the data efficiency problem by learning in a contextual bandit setting, which is known to be more tractable (Agarwal et al., 2014), and using reward shaping to increase exploration effec-”
A Study on Overfitting in Deep Reinforcement Learning (2018, background): “, 2002) and adversarial bandits (Auer, 2000; Bubeck & Cesa-Bianchi, 2012), for contextual bandits (Agarwal et al., 2014), contextual decision processes (Jiang et al.”
TOUCHDOWN: Natural Language Navigation and Spatial Reasoning in Visual Street Environments (2018, background): “The reward shaping term is F ( s, a, s (cid:48) ) = φ ( s (cid:48) ) − φ ( s ) , where the potential function φ ( s ) is the length of the shortest path from agent position at the state s to the goal state.”
Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning (2017, neutral): “PAC: [2, 3, 4, 5], (uniform) high-probability regret: [6, 7, 8]; expected regret: [9, 10, 11, 12]).”
On Oracle-Efficient PAC RL with Rich Observations (2018, methodology): “The oracle-based approach has produced practically effective algorithms for active learning [18], contextual bandits [19], structured prediction [20, 21], and multi-class classification [22], and here, we consider oracle-based algorithms for challenging RL settings.”
Deep Online Convex Optimization by Putting Forecaster to Sleep (2015, methodology): “ize the set of awake players. There are currently no oﬀ-the shelf methods for contextual partial monitoring. However, an eﬃcient contextual bandit algorithm for the stochastic setting is provided in (Agarwal et al., 2014). It is an interesting question whether eﬃcient methods speciﬁcally tailored to”
Online Decision Making with High-Dimensional Covariates (2020, methodology): “This setting is considered in the contextual multi-armed bandit literature, which extends the traditional multi-armed bandit model to include user-specific covariates (Auer 2003, Langford and Zhang 2008, Slivkins 2014, Agarwal et al. 2014, Goldenshluger et al. 2013).”
Causal Bandits: Learning Good Interventions via Causal Inference (2016, background): “A well-studied class of bandit problems with side information are “contextual bandits” Langford and Zhang (2008); Agarwal et al. (2014).”