Efficient bandit algorithms for online multiclass prediction

By Sham M. Kakade, Shai Shalev-Shwartz, Ambuj Tewari. 2008

216 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research

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

Citations in the corpus

The offset tree for learning with partial labels (2008, methodology): “The Banditron algorithm [4] deals with a similar setting but does not address several concerns that the Offset Tree addresses: (1) the Banditron requires an interactive setting; (2) it deals with a specialization of our setting where the reward for one choice is 1, and 0 for all other choices; (3) i”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “[109].”
Reinforcement Learning for Bandit Neural Machine Translation with Simulated Human Feedback (2017, background): “, 2015) is an extension of the contextual bandits problem (Kakade et al., 2008; Langford and Zhang, 2008) to structured prediction.”
Learning Cumulatively to Become More Knowledgeable (2016, background): “Online learning and incremental learning [1, 6, 10, 15, 20, 42] mainly aim at handling new instances of known classes.”
The multi-armed bandit problem with covariates (2011, background): “Minimum contrast type policies have already received some attention in the bandit literature with side information, aka contextual bandits, in the papers [15] and also [13].”
Contextual Bandit Algorithms with Supervised Learning Guarantees (2010, background): “This setting goes under different names, including the “partial-label problem” [11], the “associative bandit problem” [18], the “contextual bandit problem” [13] (which is the name we use here), the “k-armed (or multi-armed) bandit problem with expert advice” [2], and “associative reinforcement learn”
Random Forest for the Contextual Bandit Problem (2015, methodology): “On the three datasets, B ANDITRON (Kakade et al (2008)) is clearly outperformed by the other Type , where the number of strong features seems to be high.”
Online Decision Making with High-Dimensional Covariates (2020, background): “…algorithm whose regret scales with the complexity of the hypothesis class (consisting of mappings from the context space to arm space), Kakade et al. (2008) looks specifically at the setting where the hypothesis class consists of margin-based linear functions for…”
Multi-armed bandits with episode context (2011, background): “Perhaps in some alternative approach that avoids the training/test distinction, there could be a way to make do with more limited target information; this has been studied in other settings [22].”
A Neural Networks Committee for the Contextual Bandit Problem (2014, methodology): “They achieve a smaller cumulated regret than Banditron, LinUCB and CTS.”
Online Learning: A Comprehensive Survey (2018, unknown): “Banditron is the first bandit algorithm for online multiclass prediction (Kakade et al., 2008), which is a variant of the Perceptron.”
Bandit Algorithms (2020, methodology): “Like before we recommend Kallenberg [2002] for readers who want to refresh their memory and Billingsley [2008] for a more detailed account.”