Improved Algorithms for Linear Stochastic Bandits

By Yasin Abbasi-Yadkori, Dávid Pál, Csaba Szepesvari. 2011

2,065 citations recorded by the source corpus.

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

Citations in the corpus

On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization (2012, background): “Keywords: Stochastic Convex Optimization; Derivative-Free Optimization; Bandit Convex Optimization; Regret”
Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “10 of Abbasi-Yadkori et al. (2011) in the final step of the proof of Lem.”
Surprising Negative Results for Generative Adversarial Tree Search (2018, background): “Bias-Variance Trade-Off: Consider an MDP M = 〈X ,A, T, R, γ〉, with state space X , action space A, transition kernel T , reward distribution R with [0, 1]-bounded mean, and discount factor 0 ≤ γ < 1.”
Balanced Linear Contextual Bandits (2018, background): “In general, UCB based algorithms ((Auer 2003; Chu et al. 2011; Bubeck and Cesa-Bianchi 2012; Abbasi-Yadkori, P´al, and Szepesv´ari 2011)) tend to have better (and sometimes near-optimal) theoretical regret bounds.”
Estimation Considerations in Contextual Bandits (2017, background): “In general, UCB based algorithms ([11, 23, 21, 1]) tend to have better (and sometimes near-optimal) theoretical regret bounds.”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “More complex algorithms for various extensions of the stochastic multi-armed bandit problem are also based on the same idea which, along with the exponential weighting scheme presented in Section 3, is an algorithmic cornerstone of regret analysis in bandits.”
Learning to Optimize via Posterior Sampling (2013, methodology): “[2] and [3], which apply to linear models, the analysis of Filippi et al.”
Fair Algorithms for Infinite and Contextual Bandits (2016, methodology): “The top of page 15 of of [Abbasi-Yadkori et al., 2011] notes that log det(V̄t) ≤ d log(γ + t/d), and we combine this with the fact that ∑T t=1 ||xt,i||2V̄t ≤ 2 log det(V̄ T )− 2 log det(V ) (proven as part of Lemma 11 in [Abbasi-Yadkori et al.”
Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization (2012, methodology): “Various methods of introducing dependence include bandits with linear (Dani et al., 2008; Abernethy et al., 2008; Abbasi-Yadkori et al., 2011) or Lipschitzcontinuous payoffs (Kleinberg et al.”
Efficient Exploration Through Bayesian Deep Q-Networks (2018, methodology): “The main body of the following analyses on concentration of measure are based on the contextual linear bandit analyses (Abbasi-Yadkori et al., 2011; Chu et al., 2011; Li et al., 2010; Rusmevichientong & Tsitsiklis, 2010; Dani et al., 2008; Russo & Van Roy, 2014a) and self normalized processes (de…”
A Tutorial on Thompson Sampling (2017, positive): “It follows from the above relation that existing analyses (Dani et al., 2008; Rusmevichientong and Tsitsiklis, 2010; Abbasi-Yadkori et al., 2011) of UCB algorithms imply that under TS”
Thompson Sampling for Contextual Bandits with Linear Payoffs (2012, methodology): “Abbasi-Yadkori et al. (2011) analyze a UCB-style algorithm and provide a regret upper bound of O(d log (T ) √ T+ √ dT log (T/δ)).”
Provable Optimal Algorithms for Generalized Linear Contextual Bandits (2017, methodology): “We instead use results on self-normalized martingales (Abbasi-Yadkori et al., 2011), together with a finitetime normality result like Theorem 1, to prove the next theorem.”
Online Decision Making with High-Dimensional Covariates (2020, methodology): “We evaluate the LASSO Bandit on a synthetically-generated dataset to address two questions: (1) How does the LASSO Bandit’s performance compare against existing algorithms empirically?; (2) Is the LASSO Bandit robust to the choice of input parameters? We compare the LASSO Bandit against (i) the UCB-”
Offline Multi-Action Policy Learning: Generalization and Optimization (2018, background): “(2011), Abbasi-Yadkori et al. (2011), Bubeck et al. (2012), Agrawal and Goyal (2013), Russo and Van Roy (2014), Bastani and Bayati (2015), Li et al.”
Online Clustering of Bandits (2014, methodology): “From (Abbasi-Yadkori et al., 2011) it follows that |u>i x−w>i,tx| ≤ TCBi,t(x) holds with probability at least 1− δ/2, uniformly over i ∈ V , t = 0, 1, 2, . . .. and x ∈ Rd.”
Exploiting the Natural Exploration In Contextual Bandits (2017, methodology): “Greedy-First can switch to any contextual bandit algorithm (e.g., OFUL by [AYPS11] or Thompson sampling by [AG13, RVR14a]) instead of the OLS Bandit.”
Model-based Reinforcement Learning and the Eluder Dimension (2014, background): “Papers here establigh regret bounds Õ( Ô T ) for linear quadratic control [16], but with constants that grow exponentially with dimension.”