Skip to content

Bandit Algorithms

Primary menu

Category: Lower bound

The variance of Exp3

Posted onFebruary 16, 2019March 17, 2019Leave a comment

In an earlier post we analyzed an algorithm called Exp3 for $k$-armed adversarial bandits for which the expected regret is bounded by \begin{align*} R_n = \max_{a \in [k]} \E\left[\sum_{t=1}^n y_{tA_t} – y_{ta}\right] \leq \sqrt{2n k \log(k)}\,. \end{align*} The setting of Continue Reading

CategoriesAdversarial bandits, Bandits, Lower bound

Adversarial linear bandits and the curious case of the unit ball

Posted onNovember 25, 2016March 17, 2019Leave a comment

According to the main result of the previous post, given any finite action set $\cA$ with $K$ actions $a_1,\dots,a_K\in \R^d$, no matter how an adversary selects the loss vectors $y_1,\dots,y_n\in \R^d$, as long as the action losses $\ip{a_k,y_t}$ are in Continue Reading

CategoriesAdversarial bandits, Bandits, Lower bound

Lower Bounds for Stochastic Linear Bandits

Posted onOctober 20, 2016March 17, 20192 Comments

Lower bounds for linear bandits turn out to be more nuanced than the finite-armed case. The big difference is that for linear bandits the shape of the action-set plays a role in the form of the regret, not just the Continue Reading

CategoriesBandits, Lower bound

Instance dependent lower bounds

Posted onSeptember 30, 20166 Comments

In the last post we showed that under mild assumptions ($n = \Omega(K)$ and Gaussian noise), the regret in the worst case is at least $\Omega(\sqrt{Kn})$. More precisely, we showed that for every policy $\pi$ and $n\ge K-1$ there exists Continue Reading

CategoriesBandits, Finite-armed bandits, Lower bound

More information theory and minimax lower bounds

Posted onSeptember 28, 201617 Comments

Continuing the previous post, we prove the claimed minimax lower bound. We start with a useful result that quantifies the difficulty of identifying whether or not an observation is drawn from similar distributions $P$ and $Q$ defined over the same Continue Reading

CategoriesBandits, Finite-armed bandits, Lower bound

  • About
  • Download book

Recent Posts

  • Bayesian/minimax duality for adversarial bandits
  • The variance of Exp3
  • First order bounds for k-armed adversarial bandits
  • Bandit Algorithms Book
  • Bandit tutorial slides and update on book

Recent Comments

  • Tor Lattimore on Ellipsoidal Confidence Sets for Least-Squares Estimators
  • Zeyad on Ellipsoidal Confidence Sets for Least-Squares Estimators
  • Tiancheng Yu on Bayesian/minimax duality for adversarial bandits
  • Claire on Ellipsoidal Confidence Sets for Least-Squares Estimators
  • Tor Lattimore on Ellipsoidal Confidence Sets for Least-Squares Estimators

Archives

  • March 2019
  • February 2019
  • July 2018
  • February 2018
  • November 2016
  • October 2016
  • September 2016
  • August 2016

Categories

  • Adversarial bandits
  • Bandits
  • Bayesian bandits
  • Finite-armed bandits
  • Game theory
  • Lower bound
  • Probability

Meta

  • Log in
  • Entries RSS
  • Comments RSS
  • WordPress.org
Copyright © 2025 Bandit Algorithms. All Rights Reserved.
Clean Education by Catch Themes
Scroll Up
Bitnami