I am reading this paper on linear stochastic bandits :


All the results are stated in a high-probability setting, that is $\delta$ is a parameter to the algorithm , the regret at time $T$ is such that ,

\begin{align*} \mathbb{P}(R_T > f(T) ) \geq 1 - \delta \end{align*}

Is there any resource where the bounds are obtained in the form $\mathbb{E}[R_T] \leq f(T) $ ?

Trivially replacing $\delta = \frac{1}{T}$, does not give an anytime algorithm, that is the bounds don't hold for all $t > 0$.


Using the "doubling trick," you can turn your favorite high probability algorithm (e.g. LinUCB) to be an anytime algorithm with expected regret as a function of $T$, usually giving a $\tilde{O}(\sqrt{T})$ dependence without knowing $T$ in advance.

This turns out to be tight, i.e. in Chu et al. (2011), we give lower bounds on expected regret of $\Theta(\sqrt{dT})$ for the $d$-dimensional linear stochastic bandit problem. Hence, the expected regret, in the worst case, will indeed still be a function of $T$.

| cite | improve this answer | |
  • $\begingroup$ Hi Lev, Thanks for the answer. I am still trying to understand this, as i am new to this field. $\endgroup$ – rajatsen91 Dec 1 '15 at 16:58
  • $\begingroup$ I had one more question. If the set of arms are finite (say $K$) does the regret scale something like $ O(d \log ^2 t)$ where $d$ is the dimension of the feature vectors ? $\endgroup$ – rajatsen91 Dec 2 '15 at 1:46
  • 1
    $\begingroup$ These models have many intricate details. In many versions of the linear bandit problem, the number of arms is hidden in $d$, since the feature vector can encode "arm features" for each arm. Regarding the dependence on $T$, most bandit problems have two types of bounds in the stochastic case, a "problem dependent bound" that scales polylog($T$) and a minimax bound that scales approximately as $\sqrt{T}$. For the adversarial version of the problem, the bounds usually scale approximately as $\sqrt{T}$. This can even be seen in the basic bandit problem when comparing EXP3 vs UCB regret bounds. $\endgroup$ – Lev Reyzin Dec 2 '15 at 4:07
  • $\begingroup$ Thanks a lot. I think I understand it. Whenever there is a gap $\Delta$ between the optimal choice and the sub-optimal ones you can achieve problem dependent bounds which are polylog. $\endgroup$ – rajatsen91 Dec 2 '15 at 22:18
  • 1
    $\begingroup$ You can always achieve the problem-dependent bounds, but the gap appears in them. When the gap is "worst-case," i.e. a particular function of $T$, then those bounds also degrade to $\approx T^{1/2}$. $\endgroup$ – Lev Reyzin Dec 2 '15 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.