1
$\begingroup$

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

$\endgroup$

1 Answer 1

3
$\begingroup$

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

$\endgroup$
5
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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