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

This paper considers two fundamental sequential decision-making problems: theproblem of prediction with expert advice and the multi-armed bandit problem. Wefocus on stochastic regimes in which an adversary may corrupt losses, and weinvestigate what level of robustness can be achieved against adversarialcorruptions. The main contribution of this paper is to show that optimalrobustness can be expressed by a square-root dependency on the amount ofcorruption. More precisely, we show that two classes of algorithms, anytimeHedge with decreasing learning rate and algorithms with second-order regretbounds, achieve $O( \frac{\log N}{\Delta} + \sqrt{ \frac{C \log N }{\Delta} })$-regret, where $N, \Delta$, and $C$ represent the number of experts, the gapparameter, and the corruption level, respectively. We further provide amatching lower bound, which means that this regret bound is tight up to aconstant factor. For the multi-armed bandit problem, we also provide a nearlytight lower bound up to a logarithmic factor.

On Optimal Robustness to Adversarial Corruption in Online Decision Problems