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 &gt; 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 &gt; 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$.