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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We investigate the regret-minimisation problem in a multi-armed banditsetting with arbitrary corruptions. Similar to the classical setup, the agentreceives rewards generated independently from the distribution of the armchosen at each time. However, these rewards are not directly observed. Instead,with a fixed $\varepsilon\in (0,\frac{1}{2})$, the agent observes a sample fromthe chosen arm's distribution with probability $1-\varepsilon$, or from anarbitrary corruption distribution with probability $\varepsilon$. Importantly,we impose no assumptions on these corruption distributions, which can beunbounded. In this setting, accommodating potentially unbounded corruptions, weestablish a problem-dependent lower bound on regret for a given family of armdistributions. We introduce CRIMED, an asymptotically-optimal algorithm thatachieves the exact lower bound on regret for bandits with Gaussiandistributions with known variance. Additionally, we provide a finite-sampleanalysis of CRIMED's regret performance. Notably, CRIMED can effectively handlecorruptions with $\varepsilon$ values as high as $\frac{1}{2}$. Furthermore, wedevelop a tight concentration result for medians in the presence of arbitrarycorruptions, even with $\varepsilon$ values up to $\frac{1}{2}$, which may beof independent interest. We also discuss an extension of the algorithm forhandling misspecification in Gaussian model.

CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption