Stochastic Linear Optimization under Bandit Feedback

By Varsha Dani, T. Hayes, Sham M. Kakade. 2008

969 citations recorded by the source corpus.

Subfields: Reinforcement Learning, Optimization & Training

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 Optimization & Training

Citations in the corpus

On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization (2012, background): “For linear functions over general domains, informationtheoretic Ω( √ d2/T ) lower bounds on the regret has been proven in [9, 10].”
Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (2016, background): “A similar observation to this problem of optimistic optimization has been shown in the setting of linear bandits (Dani et al., 2008; Russo & Van Roy, 2014).”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “[72].”
Fair Algorithms for Infinite and Contextual Bandits (2016, background): “We therefore obtain a clear separation between fair learning and the unconstrained case Dani et al. [2008], and show that an instance-dependent upper bound like the one in Section 4 is unavoidable.”
Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization (2012, background): “Only recently, Dudik et al. (2011) demonstrated that it is possible to obtain regret bounds that only increase additively with the delay (i.e., the penalty becomes negligible for large numbers of decisions). However, the approach of Dudik et al. only applies to contextual bandit problems with finite”
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 literature [1, 21, 41, 55, 22, 57] and self normalized processes [23, 53].”
A Tutorial on Thompson Sampling (2017, methodology): “This phenomenon and its impact on regret aligns with theoretical results of [30].”
Thompson Sampling for Contextual Bandits with Linear Payoffs (2012, methodology): “…(Woodroofe, 1979; Sarkar, 1991), associative reinforcement learning (Kaelbling, 1994), associative bandit problems (Auer, 2002; Strehl et al., 2006), bandit problems with expert advice (Auer et al., 2002), and linear bandits (Dani et al., 2008; Abbasi-Yadkori et al., 2011; Bubeck et al., 2012).”
A Survey of Preference-Based Online Learning with Bandit Algorithms (2014, neutral): “[19].”
Provably Efficient Exploration in Policy Optimization (2019, background): “…of uncertainty”, as ι kh ( x, a ) ≤ 0 or equivalently As a result, it only remains to upper bound the cumulative sum which allows us to apply the elliptical potential lemma (Dani et al., 2008; Rusmevichientong and Tsitsiklis, 2010; Chu et al., 2011; Abbasi-Yadkori et al., 2011; Jin et al., 2019).”
Multi-fidelity Gaussian Process Bandit Optimisation (2016, methodology): “UCB strategies have also been used in bandit tasks with linear (Dani et al., 2008) and GP (Srinivas et al.”
Finite-Time Analysis of Kernelised Contextual Bandits (2013, methodology): “For continuous action space linear bandits the attainable lower bound for the regret is Ω(d √ T ) (Dani et al., 2008), whereas for finite action space linear contextual bandits the attainable lower bound on regret is Ω( √ dT ) (Chu et al.”
Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle (2019, neutral): “See, e.g., [1, 8].”
Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint (2023, positive): “Lemma G.4 (Elliptical Potential Lemma (Dani et al., 2008; Rusmevichientong & Tsitsiklis, 2010; Abbasi-Yadkori et al., 2011)) .”
Reducing Dueling Bandits to Cardinal Bandits (2014, methodology): “Lemma 2.4 (Dani et al. 2008) .”
Exploiting the Natural Exploration In Contextual Bandits (2017, methodology): “√ [DHK08, AYPS11] provide O ( d T ) regret bounds when contexts can be generated by an adversary.”
From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning (2014, methodology): “Several optimistic algorithms have been introduced and analyzed, such as the confidence ball algorithms in [51], as well as refined variants in [104, 2].”
Combinatorial Network Optimization with Unknown Variables: Multi-Armed Bandits with Linear Rewards (2010, methodology): “This algorithm is shown to achieve a regret upper bound of O ( √ N √ n log ( n | )) . the Dani et al. [15] develop another randomized policy for case of a compact set of arms, and show the regret is upper bounded by O ( N √ n log 3 / 2 n ) for sufﬁciently large n with high probability, and lower…”