The Epoch-Greedy Algorithm for Multi-armed Bandits with Side Information

By J. Langford, Tong Zhang. 2007

711 citations recorded by the source corpus.

Subfields: Reinforcement Learning, Algorithms & Complexity

How researchers see this paper

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

In Reinforcement Learning

In Algorithms & Complexity

Citations in the corpus

Counterfactual reasoning and learning systems: the example of computational advertising (2012, background): “Under simplified assumptions, multiarmed bandits theory (Robbins, 1952; Auer et al., 2002; Langford and Zhang, 2008) and reinforcement learning (Sutton and Barto, 1998) describe the exploration/exploitation dilemma associated with the training feedback loop.”
Learning from Logged Implicit Exploration Data (2010, methodology): “An instance of the contextual bandit problem is specified by a distribution D over tuples (x,~r) where x ∈ X is an input and ~r ∈ [0, 1]k is a vector of rewards (Langford & Zhang, 2008).”
Off-policy Bandits with Deficient Support (2020, background): “, voice assistants, recommender systems) can be modeled as contextual bandit problems [15].”
Off-policy evaluation for slate recommendation (2016, methodology): “We frame the slate recommendation problem as a combinatorial generalization of contextual bandits [3, 23, 13].”
Mapping Instructions and Visual Observations to Actions with Reinforcement Learning (2017, background): “The primary theoretical advantage of a contextual bandit setting is much tighter sample complexity bounds when comparing upper bounds for contextual bandits (Langford and Zhang, 2007) to lower bounds (Krishnamurthy et al.”
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation (2013, background): “At this stage, the deﬁnition above may appear quite abstract, so let us consider a few speciﬁc examples: • b -memory online protocols: Consider any algorithm which goes over examples one-by-one, and incrementally updates a state vector W t of bounded size b .”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, methodology): “In this paper, a context is most similar to state features in the RL literature and is a natural generalization of the notion of context as in the contextual bandit literature [Langford and Zhang, 2008].”
Horizon: Facebook's Open Source Applied Reinforcement Learning Platform (2018, background): “The first three estimators were originally designed to evaluate polices in contextual bandit problems [3, 28], the special cases of RL problems where the horizon of episodes is one.”
BlockDrop: Dynamic Inference Paths in Residual Networks (2017, background): “1It can also be seen as contextual bandits [29] although we do not operate in an online setting which has an objective of minimizing the regret.”
On Oracle-Efficient PAC RL with Rich Observations (2018, methodology): “As further motivation, the CSC oracle has been used in practically effective algorithms for contextual bandits [35, 19], imitation learning [20], and structured prediction [21].”
Hidden Technical Debt in Machine Learning Systems (2015, background): “The problem here is that bandit algorithms (such as contextual bandits [9]) do not necessarily scale well to the size of action spaces typically required for real-world problems.”
Learning by Asking Questions (2017, background): “Contextual multi-armed bandits [9, 30, 32] are another class of reinforcement learning algorithms that more closely resemble LBA.”
A Comprehensive Survey on Graph Anomaly Detection With Deep Learning (2021, methodology): “Their proposed algorithm, GraphUCB, models both attribute information and structural information, and inherits the merits of the contextual multi-armed bandit technology [101] to output potential anomalies.”
Multi-Task Learning for Contextual Bandits (2017, background): “The contextual bandit problem is an extension of the MAB problem where there is some side information, called the context, associated to each arm [12].”
Coactive Learning (2015, methodology): “Our model allows contextual information like in contextual bandits (Langford & Zhang, 2007), however, the arms in our problem are structured objects such as rankings.”