Linearly Parameterized Bandits

By Paat Rusmevichientong, John N. Tsitsiklis. 2008

599 citations recorded by the source corpus.

We consider bandit problems involving a large (possibly infinite) collection of arms, in which the expected reward of each arm is a linear function of an r-dimensional random vector Z ∈ Rr, where r ≥ 2. The objective is to minimize the cumulative regret and Bayes risk. When the set of arms corresponds to the unit sphere, we prove that the regret and Bayes risk is of order Θ(r √T), by establishing a lower bound for an arbitrary policy, and showing that a matching upper bound is obtained through a policy that alternates between exploration and exploitation phases. The phase-based policy is also shown to be effective if the set of arms satisfies a strong convexity condition. For the case of a general set of arms, we describe a near-optimal policy whose regret and Bayes risk admit upper bounds of the form O(r √T log3/2T).

Subfields: Artificial Intelligence, Computer Networks and Communications, 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 Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Off-policy evaluation for slate recommendation (2016, methodology): “, 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.”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “Recent progress on this problem can be found in Rusmevichientong and Tsitsiklis [2010], Filippi et al. [2010], Abbasi-Yadkori et al. [2011].”
Randomized Prior Functions for Deep Reinforcement Learning (2018, neutral): “Consider a linear bandit with reward rt(xt) = xt ◊ú +‘t for some ◊ú œ Rd and ‘t ≥ N(0, 1) [56].”
Learning to Optimize via Posterior Sampling (2013, methodology): “In the “linear bandit” problem studied by [2, 3, 12, 21], reward functions are parameterized by a vector θ ∈ Θ ⊂ R, and there is a known feature mapping φ : A 7→ R such that fθ(a) = 〈φ(a), θ〉.”
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, background): “UCB algorithms have been proposed for a variety of problems, including bandit problems with independent arms [36, 53, 54, 55], bandit problems with linearly parameterized arms [30, 56], bandits with continuous action spaces and smooth reward functions [57, 58, 59], and exploration in reinforcement l”
Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting (2009, background): “L G ] 9 J un 2010 (also see Auer 2002; Dani et al. 2007; Abernethy et al. 2008; Rusmevichientong & Tsitsiklis 2008), explicitly dependent on the dimensionality.”
On Kernelized Multi-armed Bandits (2017, background): “Parametric bandits, especially linearly parameterized bandits (Rusmevichientong and Tsitsiklis, 2010), represent a well-studied class of structured decision making settings.”
Convex Optimization: Algorithms and Complexity (2015, unknown): “logarithmic terms, matches the order of the O ( d √ T ) lower bound for this problem [Rusmevichientong and Tsitsiklis, 2010].”
A Linear Response Bandit Problem (2013, background): “To further clarify, what we term as a “covariate” is exogenously given, while in Mersereau et al. (2009) and Rusmevichientong and Tsitsiklis (2010) this is the decision variable.”
Introduction to Multi-Armed Bandits (2019, background): “• for linear bandits (e.g., Dani et al., 2008; Rusmevichientong and Tsitsiklis, 2010; Shamir, 2015).”
Improved Algorithms for Linear Stochastic Bandits (2011, methodology): “Another variant, studied by Dani et al. (2008), Abbasi-Yadkori et al. (2009), Rusmevichientong and Tsitsiklis (2010), is the case when the set of available actions does not change between time steps but the set can be an almost arbitrary, even inﬁnite, bounded subset of a ﬁnite-dimensional vector…”
Bandit Algorithms (2020, background): “10 or the paper by Russo and Van Roy [2014a] for more details.”
Finite-Time Analysis of Kernelised Contextual Bandits (2013, methodology): “Another well known related family are the ConfidenceBall algorithms (Abbasi-Yadkori, Pal, & Szepesvari, 2011; Dani et al., 2008; Rusmevichientong & Tsitsiklis, 2010).”
Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint (2023, unknown): “Lemma G.4 (Elliptical Potential Lemma (Dani et al., 2008; Rusmevichientong & Tsitsiklis, 2010; Abbasi-Yadkori et al., 2011)) .”