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.


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.