Back

Improved Algorithms for Linear Stochastic Bandits

Yasin Abbasi-YadkoriDávid PálCsaba Szepesvari

article2011NeurIPS2,094 citations

Develops a novel self-normalized tail inequality for vector-valued martingales to construct tighter confidence sets for linear stochastic bandits, yielding improved regret bounds and substantial empirical performance gains over existing optimism-based algorithms.

Listen

In sequential decision-making systems—such as online recommendation engines, dynamic web advertising, and clinical trials—algorithms must balance exploring unknown options against exploiting the best currently known option. The linear stochastic bandit framework models this dilemma by assuming expected rewards depend linearly on chosen actions. Prior algorithms following the optimism-in-the-face-of-uncertainty principle suffered from overly conservative confidence estimates and high computational overhead, largely due to statistical dependencies created across sequential decisions.

The article establishes tighter theoretical confidence bounds and develops practical, high-performance algorithms for both multi-armed and linear stochastic bandits. It evaluates these methods mathematically and validates their performance through simulated empirical experiments.

The authors developed a novel self-normalized tail inequality for vector-valued martingales, which constructs valid confidence sets that hold uniformly across all time steps without requiring conservative union bounds over time. Using this theoretical foundation, they introduced the OFUL (Optimism in the Face of Uncertainty Linear bandit) algorithm along with a computationally efficient variant called Rarely Switching OFUL, which updates its optimization model only when empirical data volume changes by a set factor. The authors evaluated these algorithms across both problem-dependent and worst-case scenarios and benchmarked them against prior state-of-the-art methods in simulation trials.

The key findings are as follows:

  1. The new martingale tail inequality eliminates the need for standard union bounds across time horizons, significantly tightening the confidence sets surrounding unknown system parameters.
  2. In empirical linear bandit simulations, the OFUL algorithm achieved an order-of-magnitude reduction in cumulative regret compared to previous baseline algorithms.
  3. The Rarely Switching OFUL algorithm reduced required computations by approximately 350 times in test experiments while maintaining identical regret performance to the standard OFUL method.
  4. In standard multi-armed bandit settings, modifying the Upper Confidence Bound algorithm achieved constant regret with high probability, removing the explicit dependence on the total time horizon.

These findings indicate that linear bandit algorithms can be deployed effectively in production environments without the severe computational costs or conservative exploration penalties that hindered earlier approaches. By basing confidence sets on empirical rather than worst-case theoretical quantities, systems can converge significantly faster toward optimal decision strategies, cutting exploration costs and increasing cumulative payoffs.

For practical implementation, engineering and data science teams should adopt Rarely Switching OFUL for high-frequency or resource-constrained environments, tuning the switching threshold to balance runtime overhead against decision accuracy. Further real-world validation in live customer-facing systems is recommended before replacing legacy production models.

The conclusions are subject to standard mathematical assumptions, primarily that noise is sub-Gaussian and true expected rewards are linear. While analytical proofs provide high confidence under these modeled conditions, decision-makers should remain cautious in production contexts characterized by non-linear payoffs or severe non-stationary drift.

stochastic
Abbasi-Yadkori et al (2011).pdf
Cover for Improved Algorithms for Linear Stochastic Bandits

Abstract

We improve the theoretical analysis and empirical performance of algorithms for the stochastic multi-armed bandit problem and the linear stochastic multi-armed bandit problem. In particular, we show that a simple modification of Auer's UCB algorithm (Auer, 2002) achieves with high probability constant regret. More importantly, we modify and, consequently, improve the analysis of the algorithm for the for linear stochastic bandit problem studied by Auer (2002), Dani et al. (2008), Rusmevichientong and Tsitsiklis (2010), Li et al. (2010). Our modification improves the regret bound by a logarithmic factor, though experiments show a vast improvement. In both cases, the improvement stems from the construction of smaller confidence sets. For their construction we use a novel tail inequality for vector-valued martingales.

Topics

stochastic

Table of Contents

  • 1 Introduction
  • 1.1 Notation
  • 1.2 The Learning Model
  • 2 Optimism in the Face of Uncertainty
  • 3 Self-Normalized Tail Inequality for Vector-Valued Martingales
  • 4 Construction of Confidence Sets
  • 5 Regret Analysis of the OFUL ALGORITHM
  • 5.1 Saving Computation
  • 5.2 Problem Dependent Bound
  • 6 Multi-Armed Bandit Problem
  • 7 Conclusions
  • References
  • A Proof of Theorem 1
  • B Proof of Theorem 2
  • C Proof of Theorem 3
  • D Proof of Theorem 4
  • E Proof of Theorem 5
  • F Proof of Lemma 6
  • G Proof of Theorem 7

Knowls

  1. Knowl 1 — Self-Normalized Tail Inequality for Vector-Valued Martingales

    theoretical result

    Let (Ft)t=0∞(\mathcal{F}_t)_{t=0}^\infty be a filtration. Let (ηt)t=1∞(\eta_t)_{t=1}^\infty be a real-valued stochastic process such that each ηt\eta_t is Ft\mathcal{F}_t-measurable and conditionally RR-sub-Gaussian for a constant R≥0R \ge 0, meaning that for all λ∈R\lambda \in \mathbb{R}:

    E[exp⁡(ληt)∣Ft−1]≤exp⁡(λ2R22).\mathbb{E}\left[\exp(\lambda \eta_t) \mid \mathcal{F}_{t-1}\right] \le \exp\left(\frac{\lambda^2 R^2}{2}\right).

    Let (Xt)t=1∞(X_t)_{t=1}^\infty be an Rd\mathbb{R}^d-valued stochastic process such that each XtX_t is Ft−1\mathcal{F}_{t-1}-measurable. Let V∈Rd×dV \in \mathbb{R}^{d \times d} be a symmetric positive definite matrix. For any integer t≥0t \ge 0, define:

    Vt=V+∑s=1tXsXs⊤,St=∑s=1tηsXs.V_t = V + \sum_{s=1}^t X_s X_s^\top, \qquad S_t = \sum_{s=1}^t \eta_s X_s.

    Then, for any δ>0\delta > 0, with probability at least 1−δ1 - \delta, the self-normalized bound holds uniformly across all time steps t≥0t \ge 0 simultaneously:

    ∥St∥Vt−12≤2R2log⁡(det⁡(Vt)1/2det⁡(V)−1/2δ),\|S_t\|_{V_t^{-1}}^2 \le 2 R^2 \log \left( \frac{\det(V_t)^{1/2} \det(V)^{-1/2}}{\delta} \right),

    where ∥x∥A2=x⊤Ax\|x\|_{A}^2 = x^\top A x denotes the matrix-weighted Euclidean norm for a positive definite matrix AA.

  2. Knowl 2 — Uniform Confidence Ellipsoids for Linear Stochastic Bandits

    theoretical result

    In a linear stochastic bandit setting where actions Xt∈RdX_t \in \mathbb{R}^d yield scalar rewards Yt=⟨Xt,θ∗⟩+ηtY_t = \langle X_t, \theta_* \rangle + \eta_t with an unknown parameter θ∗∈Rd\theta_* \in \mathbb{R}^d satisfying ∥θ∗∥2≤S\|\theta_*\|_2 \le S and conditionally RR-sub-Gaussian noise ηt\eta_t, let θ^t\hat{\theta}_t be the ℓ2\ell_2-regularized least-squares estimate with regularization parameter λ>0\lambda > 0:

    θ^t=(X1:t⊤X1:t+λI)−1X1:t⊤Y1:t,\hat{\theta}_t = (X_{1:t}^\top X_{1:t} + \lambda I)^{-1} X_{1:t}^\top Y_{1:t},

    where X1:t∈Rt×dX_{1:t} \in \mathbb{R}^{t \times d} has rows X1⊤,…,Xt⊤X_1^\top, \dots, X_t^\top, Y1:t=(Y1,…,Yt)⊤∈RtY_{1:t} = (Y_1, \dots, Y_t)^\top \in \mathbb{R}^t, and Vt=λI+∑s=1tXsXs⊤V_t = \lambda I + \sum_{s=1}^t X_s X_s^\top.

    For any δ>0\delta > 0, with probability at least 1−δ1 - \delta, θ∗\theta_* lies inside the ellipsoid CtC_t uniformly for all t≥0t \ge 0:

    Ct={θ∈Rd:∥θ^t−θ∥Vt≤R2log⁡(det⁡(Vt)1/2det⁡(λI)−1/2δ)+λ1/2S}.C_t = \left\{ \theta \in \mathbb{R}^d : \|\hat{\theta}_t - \theta\|_{V_t} \le R \sqrt{2 \log\left( \frac{\det(V_t)^{1/2} \det(\lambda I)^{-1/2}}{\delta} \right)} + \lambda^{1/2} S \right\}.

    Furthermore, if ∥Xt∥2≤L\|X_t\|_2 \le L for all t≥1t \ge 1, then with probability at least 1−δ1 - \delta, θ∗\theta_* lies in the simpler confidence set Ct′C_t' uniformly for all t≥0t \ge 0:

    Ct′={θ∈Rd:∥θ^t−θ∥Vt≤Rdlog⁡(1+tL2/λδ)+λ1/2S}.C_t' = \left\{ \theta \in \mathbb{R}^d : \|\hat{\theta}_t - \theta\|_{V_t} \le R \sqrt{d \log\left( \frac{1 + t L^2 / \lambda}{\delta} \right)} + \lambda^{1/2} S \right\}.

  3. Knowl 3 — Optimism in the Face of Uncertainty Linear Bandit Algorithm

    algorithm

    The Optimism in the Face of Uncertainty Linear bandit algorithm (OFUL) sequentially chooses actions from time-varying decision sets Dt⊆RdD_t \subseteq \mathbb{R}^d to maximize cumulative linear reward ∑t=1n⟨Xt,θ∗⟩\sum_{t=1}^n \langle X_t, \theta_* \rangle. The algorithm maintains an ℓ2\ell_2-regularized least-squares estimate θ^t−1\hat{\theta}_{t-1} and a confidence ellipsoid Ct−1⊆RdC_{t-1} \subseteq \mathbb{R}^d centered at θ^t−1\hat{\theta}_{t-1}. In each round tt, it jointly chooses an optimistic parameter estimate θ~t∈Ct−1\tilde{\theta}_t \in C_{t-1} and an action Xt∈DtX_t \in D_t that maximize the predicted reward ⟨x,θ⟩\langle x, \theta \rangle.

    Input: Regularization parameter λ>0\lambda > 0, noise sub-Gaussian parameter R≥0R \ge 0, norm bound S≥∥θ∗∥2S \ge \|\theta_*\|_2, confidence failure probability δ∈(0,1)\delta \in (0, 1)
    Initialize V0=λI∈Rd×dV_0 = \lambda I \in \mathbb{R}^{d \times d}, b0=0∈Rdb_0 = 0 \in \mathbb{R}^d, C0={θ∈Rd:∥θ∥V0≤λ1/2S}C_0 = \{ \theta \in \mathbb{R}^d : \|\theta\|_{V_0} \le \lambda^{1/2} S \}
    for t=1,2,…t = 1, 2, \dots do
        Receive decision set Dt⊆RdD_t \subseteq \mathbb{R}^d
        (Xt,θ~t)=argmax⁡(x,θ)∈Dt×Ct−1⟨x,θ⟩(X_t, \tilde{\theta}_t) = \operatorname{argmax}_{(x, \theta) \in D_t \times C_{t-1}} \langle x, \theta \rangle
        Play action XtX_t and observe reward YtY_t
        Update Vt=Vt−1+XtXt⊤V_t = V_{t-1} + X_t X_t^\top
        Update bt=bt−1+YtXtb_t = b_{t-1} + Y_t X_t
        Compute θ^t=Vt−1bt\hat{\theta}_t = V_t^{-1} b_t
        Update Ct={θ∈Rd:∥θ^t−θ∥Vt≤R2log⁡(det⁡(Vt)1/2λ−d/2/δ)+λ1/2S}C_t = \{ \theta \in \mathbb{R}^d : \|\hat{\theta}_t - \theta\|_{V_t} \le R \sqrt{2 \log(\det(V_t)^{1/2} \lambda^{-d/2} / \delta)} + \lambda^{1/2} S \}
    end for

  4. Knowl 4 — Worst-Case Regret Bound for the OFUL Algorithm

    theoretical result

    Assume that for all rounds t≥1t \ge 1 and all available actions x∈Dtx \in D_t, ⟨x,θ∗⟩∈[−1,1]\langle x, \theta_* \rangle \in [-1, 1] and ∥x∥2≤L\|x\|_2 \le L. Let ∥θ∗∥2≤S\|\theta_*\|_2 \le S, the noise ηt\eta_t be conditionally RR-sub-Gaussian, and the regularization parameter satisfy λ≥1\lambda \ge 1.

    Then, with probability at least 1−δ1 - \delta, the cumulative pseudo-regret Rn=∑t=1n⟨xt∗−Xt,θ∗⟩R_n = \sum_{t=1}^n \langle x_t^* - X_t, \theta_* \rangle of the OFUL algorithm satisfies for all n≥0n \ge 0:

    Rn≤4ndlog⁡(λ+nLd)(λ1/2S+R2log⁡(1δ)+dlog⁡(1+nLλd)),R_n \le 4 \sqrt{n d \log\left(\lambda + \frac{n L}{d}\right)} \left( \lambda^{1/2} S + R \sqrt{2 \log\left(\frac{1}{\delta}\right) + d \log\left(1 + \frac{n L}{\lambda d}\right)} \right),

    where xt∗=argmax⁡x∈Dt⟨x,θ∗⟩x_t^* = \operatorname{argmax}_{x \in D_t} \langle x, \theta_* \rangle. Asymptotically, this bound is O(dnlog⁡n+dnlog⁡(n)log⁡(1/δ))\mathcal{O}\left(d \sqrt{n} \log n + \sqrt{d n \log(n) \log(1/\delta)}\right), improving over prior confidence-ball algorithms by a factor of log⁡n\sqrt{\log n}.

  5. Knowl 5 — Problem-Dependent Regret Bound for OFUL

    theoretical result

    Let Δt=max⁡x∈Dt⟨x,θ∗⟩−max⁡x∈Dt∖{xt∗}⟨x,θ∗⟩\Delta_t = \max_{x \in D_t} \langle x, \theta_* \rangle - \max_{x \in D_t \setminus \{x_t^*\}} \langle x, \theta_* \rangle be the reward gap between the optimal and second-best actions in decision set DtD_t at time tt, and let Δˉn=min⁡1≤t≤nΔt>0\bar{\Delta}_n = \min_{1 \le t \le n} \Delta_t > 0 be the minimum gap up to time nn. Assume λ≥1\lambda \ge 1, ∥θ∗∥2≤S\|\theta_*\|_2 \le S with S≥1S \ge 1, ∥x∥2≤L\|x\|_2 \le L for all x∈⋃tDtx \in \bigcup_t D_t, and noise conditionally RR-sub-Gaussian.

    With probability at least 1−δ1 - \delta, for all n≥1n \ge 1, the cumulative regret of OFUL satisfies:

    Rn≤16R2λS2Δˉn(log⁡(Ln)+(d−1)log⁡64R2λS2LΔˉn2+2(d−1)log⁡(dlog⁡dλ+nL2d+2log⁡1δ)+2log⁡1δ)2.R_n \le \frac{16 R^2 \lambda S^2}{\bar{\Delta}_n} \left( \log(L n) + (d - 1) \log \frac{64 R^2 \lambda S^2 L}{\bar{\Delta}_n^2} + 2 (d - 1) \log\left( d \log\frac{d \lambda + n L^2}{d} + 2 \log\frac{1}{\delta} \right) + 2 \log\frac{1}{\delta} \right)^2.

    For a constant minimum gap Δ=inf⁡nΔˉn>0\Delta = \inf_n \bar{\Delta}_n > 0, this bound scales as O(log⁡(1/δ)Δ(log⁡n+dlog⁡log⁡n)2)\mathcal{O}\left(\frac{\log(1/\delta)}{\Delta} (\log n + d \log\log n)^2\right), improving upon the prior O(d2Δlog⁡(n/δ)log⁡2n)\mathcal{O}\left(\frac{d^2}{\Delta} \log(n/\delta) \log^2 n\right) problem-dependent rate.

  6. Knowl 6 — Rarely Switching OFUL Algorithm

    algorithm

    The Rarely Switching OFUL algorithm decreases the computational overhead of standard OFUL by updating the optimistic parameter estimate θ~t\tilde{\theta}_t only when the determinant of the empirical design matrix Vt=λI+∑s=1tXsXs⊤V_t = \lambda I + \sum_{s=1}^t X_s X_s^\top grows by a factor greater than 1+C1 + C relative to the last update round τ\tau, where C>0C > 0 is a fixed constant. This restricts the number of costly confidence-set optimizations to O(dlog⁡n)\mathcal{O}(d \log n) over nn rounds.

    Input: Threshold constant C>0C > 0, regularization λ>0\lambda > 0, noise parameter R≥0R \ge 0, norm bound S≥∥θ∗∥2S \ge \|\theta_*\|_2, confidence δ∈(0,1)\delta \in (0, 1)
    Initialize τ=1\tau = 1, V0=λI∈Rd×dV_0 = \lambda I \in \mathbb{R}^{d \times d}, b0=0∈Rdb_0 = 0 \in \mathbb{R}^d, C0={θ∈Rd:∥θ∥V0≤λ1/2S}C_0 = \{ \theta \in \mathbb{R}^d : \|\theta\|_{V_0} \le \lambda^{1/2} S \}
    for t=1,2,…t = 1, 2, \dots do
        Receive decision set Dt⊆RdD_t \subseteq \mathbb{R}^d
        if det⁡(Vt−1)>(1+C)det⁡(Vτ)\det(V_{t-1}) > (1 + C) \det(V_\tau) or t=1t = 1 then
            (Xt,θ~t)=argmax⁡(x,θ)∈Dt×Ct−1⟨θ,x⟩(X_t, \tilde{\theta}_t) = \operatorname{argmax}_{(x, \theta) \in D_t \times C_{t-1}} \langle \theta, x \rangle
            τ=t\tau = t
        end if
        Xt=argmax⁡x∈Dt⟨θ~τ,x⟩X_t = \operatorname{argmax}_{x \in D_t} \langle \tilde{\theta}_\tau, x \rangle
        Play action XtX_t and observe reward YtY_t
        Update Vt=Vt−1+XtXt⊤V_t = V_{t-1} + X_t X_t^\top
        Update bt=bt−1+YtXtb_t = b_{t-1} + Y_t X_t
        Compute θ^t=Vt−1bt\hat{\theta}_t = V_t^{-1} b_t
        Update Ct={θ∈Rd:∥θ^t−θ∥Vt≤R2log⁡(det⁡(Vt)1/2λ−d/2/δ)+λ1/2S}C_t = \{ \theta \in \mathbb{R}^d : \|\hat{\theta}_t - \theta\|_{V_t} \le R \sqrt{2 \log(\det(V_t)^{1/2} \lambda^{-d/2} / \delta)} + \lambda^{1/2} S \}
    end for

  7. Knowl 7 — Regret Bound for Rarely Switching OFUL

    theoretical result

    Let C>0C > 0 be the determinant growth threshold in the Rarely Switching OFUL algorithm. Under the assumptions that ⟨x,θ∗⟩∈[−1,1]\langle x, \theta_* \rangle \in [-1, 1] and ∥x∥2≤L\|x\|_2 \le L for all x∈Dtx \in D_t, ∥θ∗∥2≤S\|\theta_*\|_2 \le S, λ≥1\lambda \ge 1, and conditionally RR-sub-Gaussian noise ηt\eta_t, the cumulative pseudo-regret RnR_n satisfies, with probability at least 1−δ1 - \delta, for all n≥0n \ge 0:

    Rn≤4(1+C)ndlog⁡(λ+nLd)(λS+Rdlog⁡(1+nLλd)+2log⁡1δ)+4dlog⁡nd.R_n \le 4 \sqrt{(1 + C) n d \log\left(\lambda + \frac{n L}{d}\right)} \left( \sqrt{\lambda} S + R \sqrt{d \log\left(1 + \frac{n L}{\lambda d}\right) + 2 \log\frac{1}{\delta}} \right) + 4 \sqrt{d \log\frac{n}{d}}.

    This bound matches the regret of standard OFUL up to a factor of 1+C\sqrt{1+C} and a lower-order additive term, demonstrating that running confidence set optimization only O(dlog⁡n)\mathcal{O}(d \log n) times preserves the theoretical regret guarantee.

  8. Knowl 8 — Uniform-in-Time Confidence Intervals for Multi-Armed Bandits

    theoretical result

    In a dd-armed stochastic bandit problem with arm expected rewards μ1,…,μd∈R\mu_1, \dots, \mu_d \in \mathbb{R} and conditionally 11-sub-Gaussian additive noise, let Ni,t=∑s=1tI{Is=i}N_{i,t} = \sum_{s=1}^t \mathbb{I}\{I_s = i\} be the number of times arm ii was pulled up to round tt, and let Xˉi,t=1Ni,t∑s=1tI{Is=i}Ys\bar{X}_{i,t} = \frac{1}{N_{i,t}} \sum_{s=1}^t \mathbb{I}\{I_s = i\} Y_s be the sample mean of arm ii.

    For any δ∈(0,1)\delta \in (0, 1), with probability at least 1−δ1 - \delta, the true expected rewards satisfy:

    ∣Xˉi,t−μi∣≤ci,tfor all i∈{1,…,d} and all t≥0,|\bar{X}_{i,t} - \mu_i| \le c_{i,t} \quad \text{for all } i \in \{1, \dots, d\} \text{ and all } t \ge 0,

    where

    ci,t=1+Ni,tNi,t2(1+2log⁡(d(1+Ni,t)1/2δ)).c_{i,t} = \sqrt{\frac{1 + N_{i,t}}{N_{i,t}^2} \left( 1 + 2 \log\left( \frac{d (1 + N_{i,t})^{1/2}}{\delta} \right) \right)}.

    Crucially, ci,tc_{i,t} depends only on the arm pull count Ni,tN_{i,t} and the confidence parameter δ\delta, and does not depend on the total elapsed rounds tt or the horizon nn.

  9. Knowl 9 — Constant High-Probability Regret for UCB(δ) in Multi-Armed Bandits

    theoretical result

    Let μ∗=max⁡1≤i≤dμi\mu^* = \max_{1 \le i \le d} \mu_i be the optimal arm expected reward and Δi=μ∗−μi\Delta_i = \mu^* - \mu_i be the suboptimality gap of arm ii. The UCB(δ\delta) algorithm chooses the arm It=argmax⁡i(Xˉi,t−1+ci,t−1)I_t = \operatorname{argmax}_i (\bar{X}_{i,t-1} + c_{i,t-1}) using confidence radius ci,t−1=1+Ni,t−1Ni,t−12(1+2log⁡(d(1+Ni,t−1)1/2/δ))c_{i,t-1} = \sqrt{\frac{1 + N_{i,t-1}}{N_{i,t-1}^2} (1 + 2 \log(d(1+N_{i,t-1})^{1/2}/\delta))}.

    Assuming conditionally 11-sub-Gaussian noise, with probability at least 1−δ1 - \delta, the total cumulative regret Rn=∑t=1n(μ∗−μIt)R_n = \sum_{t=1}^n (\mu^* - \mu_{I_t}) of UCB(δ\delta) is bounded by a constant independent of the time horizon nn:

    Rn≤∑i:Δi>0(3Δi+16Δilog⁡(2dΔiδ)).R_n \le \sum_{i : \Delta_i > 0} \left( 3 \Delta_i + \frac{16}{\Delta_i} \log\left( \frac{2 d}{\Delta_i \delta} \right) \right).

    When δ\delta is chosen as 1/n1/n, this bound yields the standard optimal expected regret bound O(∑i:Δi>0log⁡nΔi)\mathcal{O}\left(\sum_{i: \Delta_i > 0} \frac{\log n}{\Delta_i}\right).

  10. Knowl 10 — Empirical Performance and Computational Savings of OFUL Variants

    empirical result

    In synthetic 2-dimensional linear bandit simulations where the unknown parameter vector θ∗\theta_* and action sets DtD_t are drawn from the unit Euclidean ball with zero-mean Gaussian noise (σ=0.1,δ=10−4)(\sigma = 0.1, \delta = 10^{-4}) over 10,000 rounds:

    1. Regret Comparison: OFUL achieves cumulative regret between 200 and 300, outperforming the CONFIDENCEBALL algorithm of Dani et al. (2008), whose cumulative regret exceeds 2,000 under identical conditions.
    2. Computation vs Regret Trade-off: Rarely Switching OFUL achieves empirical regret virtually identical to standard OFUL while requiring approximately 350 times fewer confidence set recomputations.
    3. Computation Budget Scaling: Under a fixed constraint on the total number of allowed action updates, increasing the switching parameter CC allows Rarely Switching OFUL to run for more total steps, lowering the average regret per time step for a fixed computational budget.

Coverage note — Intermediate matrix perturbation bounds (such as Theorem 13 and Lemma 12) and intermediate determinant-trace lemmas (Lemmas 10 and 11) were omitted as standalone knowls because their primary contribution is supporting the proofs of the main regret and confidence theorems.

References

  1. 1.Yasin Abbasi-Yadkori, Andr%#225;s Antos, and Csaba Szepesv%#225;ri. Forced-exploration based algorithms for playing in stochastic linear bandits. In COLT Workshop on On-line Learning with Limited Feedback, 2009.
  2. 2.Naoki Abe, Alan W. Biermann, and Philip M. Long. Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica, 37:263293, 2003.
  3. 3.A. Antos, V. Grover, and Cs. Szepesv%#225;ri. Active learning in heteroscedastic noise. Theoretical Computer Science, 411(29-30):2712–2728, 2010.
  4. 4.J.-Y. Audibert, R. Munos, and Csaba Szepesv%#225;ri. Exploration-exploitation tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):1876–1902, 2009a.
  5. 5.Jean-Yves Audibert, R%#233;mi Munos, and Csaba Szepesv%#225;ri. Exploration-exploitation tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 19:1876–1902, 2009b.
  6. 6.P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3):235–256, 2002.
  7. 7.Peter Auer. Using upper confidence bounds for online learning. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS 2000), pages 270–279. IEEE, 2000.
  8. 8.Peter Auer. Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3:397–422, 2002.
  9. 9.S. Bubeck, R. Munos, G. Stoltz, and Cs. Szepesv%#225;ri. Online optimization in X-armed bandits. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, NIPS-21, pages 201–208, 2008.
  10. 10.Nicol%#242; Cesa-Bianchi and G%#225;bor Lugosi. Prediction, Learning, and Games. Cambridge University Press, New York, NY, USA, 2006.
  11. 11.Wei Chu, Lihong Li, Lev Reyzin, and Robert E. Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics (AISTATS 2011), 2011.
  12. 12.Pierre-Arnaud Coquelin and R%#233;mi Munos. Bandit algorithms for tree search. In UAI, 2007.
  13. 13.Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In Rocco Servedio and Tong Zhang, editors, Proceedings of the 21st Annual Conference on Learning Theory (COLT 2008), pages 355–366, 2008.
  14. 14.Victor H. de la Pe%#241;a, Michael J. Klass, and Tze Leung Lai. Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws. Annals of Probability, 32(3):1902–1933, 2004.
  15. 15.Victor H. de la Pe%#241;a, Tze Leung Lai, and Qi-Man Shao. Self-normalized processes: Limit theory and Statistical Applications. Springer, 2009.
  16. 16.Ofer Dekel, Claudio Gentile, and Karthik Sridharan. Robust selective sampling from single and multiple teachers. In Adam Tauman Kalai and Mehryar Mohri, editors, Proceedings of the 23rd Annual Conference on Learning Theory (COLT 2010), 2010.
  17. 17.David A. Freedman. On tail probabilities for martingales. The Annals of Probability, 3(1):100–118, 1975.
  18. 18.A Garivier and E Moulines. On upper-confidence bound policies for non-stationary bandit problems. Technical report, LTCI, Dec 2008.
  19. 19.Robert Kleinberg, Alexandru Niculescu-Mizil, and Yogeshwer Sharma. Regret bounds for sleeping experts and bandits. Machine learning, pages 1–28, 2008.
  20. 20.Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6:4–22, 1985.
  21. 21.Tze Leung Lai and Ching Zong Wei. Least squares estimates in stochastic regression models with applications to identification and control of dynamic systems. The Annals of Statistics, 10(1):154–166, 1982.
  22. 22.Tze Leung Lai, Herbert Robbins, and Ching Zong Wei. Strong consistency of least squares estimates in multiple regression. Proceedings of the National Academy of Sciences, 75(7):3034–3036, 1979.
  23. 23.Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web (WWW 2010), pages 661–670. ACM, 2010.
  24. 24.V. Mnih, Cs. Szepesv%#225;ri, and J.-Y. Audibert. Empirical Bernstein stopping. In W. W. Cohen, A. McCallum, and S. T. Roweis, editors, ICML 2008, pages 672–679. ACM, 2008. doi: http://doi.acm.org/10.1145/1390156.1390241.
  25. 25.Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58:527–535, 1952.
  26. 26.Paat Rusmevichientong and John N. Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395–411, 2010.
  27. 27.G.W. Stewart and Ji-guang Sun. Matrix Perturbation Theory. Academic Press, 1990.
  28. 28.Thomas J. Walsh, Istv%#225;n Szita, Carlso Diuk, and Michael L. Littman. Exploring compact reinforcement-learning representations with linear regression. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI 2009), pages 591–598. AUAI Press, 2009.

Citation

MLA
Abbasi-Yadkori, Y., et al. “Improved Algorithms for Linear Stochastic Bandits”. Neural Information Processing Systems, vol. 24, 2011, pp. 2312–20, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1030.3615.
APA
Abbasi-Yadkori, Y., Pál, D., & Szepesvári, C. (2011). Improved Algorithms for Linear Stochastic Bandits. Neural Information Processing Systems, 24, 2312–2320. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1030.3615
Chicago
Abbasi-Yadkori, Y., D. Pál, and C. Szepesvári. 2011. “Improved Algorithms for Linear Stochastic Bandits”. Neural Information Processing Systems 24: 2312–20. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1030.3615.
Harvard
Abbasi-Yadkori, Y., Pál, D. and Szepesvári, C. (2011) “Improved Algorithms for Linear Stochastic Bandits”, Neural Information Processing Systems, 24, pp. 2312–2320. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1030.3615.
Vancouver
1. Abbasi-Yadkori Y, Pál D, Szepesvári C (2011) Improved Algorithms for Linear Stochastic Bandits. Neural Information Processing Systems 24:2312–2320

BibTeX

@article{abbasiyadkori2011improved,
  title = {Improved Algorithms for Linear Stochastic Bandits},
  author = {Abbasi-Yadkori, Yasin and Pál, Dávid and Szepesvári, Csaba},
  year = {2011},
  journal = {Neural Information Processing Systems},
  volume = {24},
  pages = {2312-2320},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1030.3615}
}
Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors