# Average Regret Bounds for Linear Stochastic Bandits

I am reading this paper on linear stochastic bandits :

http://papers.nips.cc/paper/4417-improved-algorithms-for-linear-stochastic-bandits.pdf

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$.
• 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 ? – rajatsen91 Dec 2 '15 at 1:46
• 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. – Lev Reyzin Dec 2 '15 at 4:07
• 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. – rajatsen91 Dec 2 '15 at 22:18
• 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}$. – Lev Reyzin Dec 2 '15 at 22:21