English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the trade-off between expectation and tail risk for regretdistribution in the stochastic multi-armed bandit problem. We fullycharacterize the interplay among three desired properties for policy design:worst-case optimality, instance-dependent consistency, and light-tailed risk.We show how the order of expected regret exactly affects the decaying rate ofthe regret tail probability for both the worst-case and instance-dependentscenario. A novel policy is proposed to characterize the optimal regret tailprobability for any regret threshold. Concretely, for any given $\alpha\in[1/2,1)$ and $\beta\in[0, \alpha]$, our policy achieves a worst-case expected regretof $\tilde O(T^\alpha)$ (we call it $\alpha$-optimal) and an instance-dependentexpected regret of $\tilde O(T^\beta)$ (we call it $\beta$-consistent), whileenjoys a probability of incurring an $\tilde O(T^\delta)$ regret($\delta\geq\alpha$ in the worst-case scenario and $\delta\geq\beta$ in theinstance-dependent scenario) that decays exponentially with a polynomial $T$term. Such decaying rate is proved to be best achievable. Moreover, we discoveran intrinsic gap of the optimal tail rate under the instance-dependent scenariobetween whether the time horizon $T$ is known a priori or not. Interestingly,when it comes to the worst-case scenario, this gap disappears. Finally, weextend our proposed policy design to (1) a stochastic multi-armed banditsetting with non-stationary baseline rewards, and (2) a stochastic linearbandit setting. Our results reveal insights on the trade-off between regretexpectation and regret tail risk for both worst-case and instance-dependentscenarios, indicating that more sub-optimality and inconsistency leave spacefor more light-tailed risk of incurring a large regret, and that knowing theplanning horizon in advance can make a difference on alleviating tail risks.

Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Risk