Contextual Bandits with Linear Payoff Functions

By Wei Chu, Lihong Li, Lev Reyzin, Robert E. Schapire. 2011

1,222 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.

Citations in the corpus

Balanced Linear Contextual Bandits (2018, background): “√ The lower bound Ω( dT ) is established in (Chu et al. 2011) for linear contextual bandits (again in the context of a single parameter θ for all K arms).”
Estimation Considerations in Contextual Bandits (2017, background): “The rest of the proof adopts a similar structure as in [23].”
Off-policy evaluation for slate recommendation (2016, background): “, linear) models relating the metrics to the features describing a slate [2, 31, 15, 10, 29]; this can lead to bias if the model is inaccurate (e.”
Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms (2010, background): “…of an arm is linear in its features (namely, E D [ r t,a | x t,a ] = w ⊤ x t , a for some coeﬃcient vector w ), both LinRel [4] and LinUCB [19, 10, 11] are essentially UCB-type approaches generalized to linear payoﬀ functions, and their variants have a regret of ˜ O ( √ T ), a signiﬁcant…”
Fairness in Learning: Classic and Contextual Bandits (2016, background): “…– the stochastic multi-armed bandit problem is a special case of every contextual bandit problem, and for general contextual bandit problems, it is also known how to get non-trivial regret after only T = O ( k ) many rounds [Agarwal et al., 2014, Beygelzimer et al., 2011, Chu et al., 2011].”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “The case of deterministic covariates (fixed design), finitely many arms, and a linear stochastic dependence between covariates and rewards has been studied in [22, 66] — see also [2].”
Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits (2014, methodology): “In our experiments, we compare to a strong baseline algorithm that uses this approach (Chu et al., 2011).”
Efficient Exploration Through Bayesian Deep Q-Networks (2018, methodology): “[21] Chu, W.”
Thompson Sampling for Contextual Bandits with Linear Payoffs (2012, methodology): “This realizability assumption is standard in the existing literature on contextual multi-armed bandits, e.g. (Auer, 2002; Filippi et al., 2010; Chu et al., 2011; Abbasi-Yadkori et al., 2011).”
Automatic Bridge Bidding Using Deep Reinforcement Learning (2016, methodology): “UCB algorithms [21] are some of the most popular contextual bandit algorithms.”
Online Decision Making with High-Dimensional Covariates (2020, unknown): “Thus, we focus on the case where the arm rewards are linear functions of the covariates; this setting was first introduced by Auer (2003) and was subsequently improved by UCB-type algorithms by Dani et al. (2008), Rusmevichientong and Tsitsiklis (2010), Chu et al.”
Provably Efficient Exploration in Policy Optimization (2019, background): “A line of recent work (Fazel et al., 2018; Yang et al., 2019a; Abbasi-Yadkori et al., 2019a,b; Bhandari and Russo, 2019; Liu et al., 2019; Agarwal et al., 2019; Wang et al., 2019) answers the computational question aﬃrmatively by proving that a wide variety of policy optimization algorithms, such as”
Introduction to Multi-Armed Bandits (2019, unknown): “(2010), and analyzed in (Chu et al., 2011; Abbasi-Yadkori et al., 2011).”
Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound (2019, methodology): “There is a line of works on linear bandit problems and their regret analysis (Dani et al., 2008; Rusmevichientong and Tsitsiklis, 2010; Li et al., 2010; Abbasi-Yadkori et al., 2011; Chu et al., 2011).”
Provably Optimal Algorithms for Generalized Linear Contextual Bandits (2017, methodology): “its with probability at least 1−δ. With δ = 1/T, we obtain E[RT ] = O (logT)1.5 p dT logK . The theoremdemonstratesan O˜( √ dT logK) regretbound for the algorithm SupCB-GLM. It has been proved in Chu et al. (2011, Theorem 2) that √ dT is the minimax lowerboundoftheexpectedregretforK-armedlinearban”
Explore-exploit in top-N recommender systems via Gaussian processes (2014, methodology): “In a special case of CGP RANK , we can recover the exact algorithms presented presented in [4] and [18] by choosing appropriate linear kernels.”
Finite-Time Analysis of Kernelised Contextual Bandits (2013, methodology): “For a general discussion of the advantages of approaches directly taking advantage of structure in contextual bandit problems over the EXP4 family we refer to (Chu et al., 2011).”