Sample mean based index policies by O(log n) regret for the multi-armed bandit problem

By Rajeev Agrawal. 1995

How researchers see this paper

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

Citations in the corpus

A contextual-bandit approach to personalized news article recommendation (2010, neutral): “In contrast to the unguided exploration strategy adopted by greedy, another class of algorithms generally known as upper confidence bound algorithms [4, 7, 17] use a smarter way to balance exploration and exploitation.”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, positive): “While the theoretical behavior of Thompson sampling has remained elusive for a long time, we have now a fairly good understanding of its theoretical properties: in Agrawal and Goyal [2012] the first logarithmic regret bound was proved, and in Kaufmann et al. [2012b] it was showed that in fact Thomps”
PAC Bounds for Discounted MDPs (2012, background): “It also gives insight into the workings of the proof in the next two sections. s0 r = 1 s1 r = 0 1− p p 1− q q Consider the mdp on the right with two states and one action where rewards are shown inside the states and transition probabilities on the edges.”
Distributed Algorithms for Learning and Cognitive Medium Access with Logarithmic Regret (2010, methodology): “This in turn, can be analyzed by manipulating the classical results on multiarmed bandits [10], [11].”
Linearly Parameterized Bandits (2008, background): “Subsequent papers along this line include Agrawal et al. (1989), Agrawal (1995), and Auer et al. (2002). There has been relatively little research, however, on policies that exploit the dependence among the arms. In what is widely regarded as the original paper on the multiarmed bandit problem, Thom”
Tuning Bandit Algorithms in Stochastic Environments (2007, background): “Agrawal has shown how to construct such optimal policies starting from the sample-means of the arms [1].”
An Asymptotically Optimal Multi-Armed Bandit Algorithm and Hyperparameter Optimization (2020, methodology): “Agrawal (1995) modified the UCB policy without knowing the total sample size.”
A modern Bayesian look at the multi-armed bandit (2010, unknown): “Agrawal [19] and Auer et al.”
The Multi-fidelity Multi-armed Bandit (2016, background): “Related Work The K-armed bandit has been studied extensively in the past [1, 9, 11].”
The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond (2011, methodology): “ptimistic", as the agent acts as if, at each instant, the expected rewards were equal to the highest possible values that are compatible with her past observations. Auer et al. (2002), following Agrawal (1995), proposed and analyzed two variants, UCB1 (usually called simply UCB in latter works)”
Customer Acquisition via Display Advertising Using Multi-Armed Bandit Experiments (2017, background): “This policy is optimal in the sense that it minimizes finite-time regret (Agrawal 1995; Auer 2002; Lai 1987).”
Exploration-exploitation tradeoff using variance estimates in multi-armed bandits (2009, background): “Agrawal [1] has shown how to construct upper confidence bound algorithms that use the sample-means of the arms.”