Efficient Optimal Learning for Contextual Bandits

By Miroslav Dud'ik, Daniel J. Hsu, Satyen Kale, Nikos Karampatziakis, J. Langford, Lev Reyzin, Tong Zhang. 2011

325 citations recorded by the source corpus.

We address the problem of learning in an online setting where the learner repeatedly observes features, selects among a set of actions, and receives reward for the action taken. We provide the first efficient algorithm with an optimal regret. Our algorithm uses a cost sensitive classification learner as an oracle and has a running time polylog(N), where N is the number of classification rules among which the oracle might choose. This is exponentially faster than all previous algorithms that achieve optimal regret in this setting. Our formulation also enables us to create an algorithm with regret that is additive rather than multiplicative in feedback delay as in all previous work.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, 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 Electrical and Electronic Engineering

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).”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “An efficient algorithm for this model has been recently proposed in [74].”
Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits (2014, methodology): “This problem is very similar to the one in Dud´ık et al. (2011a), and our coordinate descent algorithm in Section 3.1 gives a constructive proof that the problem is feasible.”
Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization (2012, background): “Only recently, Dudik et al. (2011) demonstrated that it is possible to obtain regret bounds that only increase additively with the delay (i.e., the penalty becomes negligible for large numbers of decisions).”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, methodology): “Prior related work (for instance in contextual bandits [Dudik et al., 2011, Agarwal et al., 2014]) used supervised learning oracles for computationally eﬃcient approaches.”
Practical Evaluation and Optimization of Contextual Bandit Algorithms (2018, methodology): “Although some techniques (Dudik et al., 2011b) attempt to remove a dependence on encoding, in practice, and particularly in an online scenario, this is imperfect.”
PAC Reinforcement Learning with Rich Observations (2016, methodology): “The above model is closely related to several well-studied models in the literature, namely: Contextual Bandits: If H = 1, then our model reduces to stochastic contextual bandits [8, 16], a well-studied simplification of the general reinforcement learning problem.”
Asymptotic Convergence in Online Learning with Unbounded Delays (2016, background): “Thus, maxscoren(z) is bounded below by z − 1 (consider the case where j = 1 and m = 0) and bounded above by z − j −m+ relscoren(z, j, m).”
A Contextual Bandit Bake-off (2018, methodology): “The focal point of contextual bandit (henceforth CB) learning research is eﬃcient exploration algorithms (Abbasi-Yadkori et al., 2011; Agarwal et al., 2012, 2014; Agrawal and Goyal, 2013; Dudik et al., 2011a; Langford and Zhang, 2008; Russo et al., 2018).”
Dialog State Tracking with Reinforced Data Augmentation (2019, background): “The problem of high quality data generation is modeled as a contextual bandit (or one-step reinforcement learning ) (Dudik et al., 2011).”
A Neural Networks Committee for the Contextual Bandit Problem (2014, background): “Dudı́k et al [15] propose an algorithm of policies elimination.”
Interactive collaborative filtering (2013, methodology): “On the other hand, in the contextual bandit model with side information, the structure is modelled by positioning each arm into a feature space [13], while a more general linear setting is discussed in [14].”
Bandit Algorithms (2020, background): “An earlier attempt to address the problem of reducing contextual bandits to cost-sensitive ERM is by Dudik et al. [2011]. The adversarial case of static experts is considered by Syrgkanis et al.”
Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability (2021, methodology): “…to efficiently search over the class Π, and it leads to algorithms that can be implemented via a reduction to supervised learning as a primitive [Dudik et al., 2011; Agarwal et al., 2014; Krishnamurthy et al., 2015; Rakhlin and Sridharan, 2016; Syrgkanis et al., 2016a,b; Luo et al., 2018].”