This paper gives some high probability results for UCB algorithm of the form,

\begin{align} \mathbb{P}(R_{n} > r_0.x) \leq O(n^{-2\rho x + 1} + x^{-2 \rho + 1} ) \end{align}

where $\rho$ is a parameter of the algorithm, $R_{n}$ is the regret till time $n$, and $r_{0}$ is the bound for the expected regret that is of order $O(\log n)$.

Is it possible to get high-probability bounds on the regret between time $n_2$ and $n_1$, that is $R_{n_2} - R_{n_1}$ , where $n_2 - n_1 = o(n_1)$ ? I presume we can modify the arguments in the above paper to do so, but if there is any resource that directly gives such bounds, then that would be helpful.

| cite | improve this question | | | | |

Your Answer

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

Browse other questions tagged or ask your own question.