<p>Using the "<a href="https://books.google.com/books?id=i8hQhp1a62UC&amp;pg=766" rel="nofollow">doubling trick</a>," you can turn your favorite high probability algorithm (e.g. <a href="http://www.research.rutgers.edu/~lihong/pub/Li10Contextual.pdf" rel="nofollow">LinUCB</a>) 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.</p>

<p>This turns out to be tight, i.e. in <a href="http://www.levreyzin.com/papers/ChuLRS11.pdf" rel="nofollow">Chu et al. (2011)</a>, 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$.</p>

CC BY-SA 3.0
2015-12-01T16:58:20.077Z
Hi Lev, Thanks for the answer. I am still trying to understand this, as i am new to this field.
rajatsen91
CC BY-SA 3.0
2015-12-02T01:46:10.903Z
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
CC BY-SA 3.0
2015-12-02T04:07:57.820Z
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
CC BY-SA 3.0
2015-12-02T22:18:45.287Z
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
CC BY-SA 3.0
2015-12-02T22:21:55.763Z
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
CC BY-SA 3.0
2015-12-01T02:35:37.827Z
2015-12-01T05:00:00.267Z
2015-12-01T05:00:00.267Z
Lev Reyzin
<p>I am reading this paper on linear stochastic bandits : </p>

<p><a href="http://papers.nips.cc/paper/4417-improved-algorithms-for-linear-stochastic-bandits.pdf" rel="nofollow">http://papers.nips.cc/paper/4417-improved-algorithms-for-linear-stochastic-bandits.pdf</a></p>

<p>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 ,</p>

<p>\begin{align*}
\mathbb{P}(R_T &gt; f(T) ) \geq 1 - \delta
\end{align*}</p>

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

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

<pr.probability><lg.learning><online-learning>
Average Regret Bounds for Linear Stochastic Bandits
rajatsen91
# Average Regret Bounds for Linear Stochastic Bandits

(Asked by: username_0 on 2015-12-01)

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$.

**Tags:** pr.probability, lg.learning, online-learning


---

## 1 answers

### Answer by username_1 on 2015-12-01. Score: 3 | Accepted answer

Using the "[doubling trick](https://books.google.com/books?id=i8hQhp1a62UC&pg=766)," you can turn your favorite high probability algorithm (e.g. [LinUCB](http://www.research.rutgers.edu/~lihong/pub/Li10Contextual.pdf)) 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)](http://www.levreyzin.com/papers/ChuLRS11.pdf), 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$.

> **Comments:**
> **username_0**: Hi Lev, Thanks for the answer. I am still trying to understand this, as i am new to this field.  
> **username_0**: 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 ?  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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}$.  

---

