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 investigate the fixed-budget best-arm identification (BAI) problem forlinear bandits in a potentially non-stationary environment. Given a finite armset $\mathcal{X}\subset\mathbb{R}^d$, a fixed budget $T$, and an unpredictablesequence of parameters $\left\lbrace\theta_t\right\rbrace_{t=1}^{T}$, analgorithm will aim to correctly identify the best arm $x^* :=\arg\max_{x\in\mathcal{X}}x^\top\sum_{t=1}^{T}\theta_t$ with probability ashigh as possible. Prior work has addressed the stationary setting where$\theta_t = \theta_1$ for all $t$ and demonstrated that the error probabilitydecreases as $\exp(-T /\rho^*)$ for a problem-dependent constant $\rho^*$. Butin many real-world $A/B/n$ multivariate testing scenarios that motivate ourwork, the environment is non-stationary and an algorithm expecting a stationarysetting can easily fail. For robust identification, it is well-known that ifarms are chosen randomly and non-adaptively from a G-optimal design over$\mathcal{X}$ at each time then the error probability decreases as$\exp(-T\Delta^2_{(1)}/d)$, where $\Delta_{(1)} = \min_{x \neq x^*} (x^* -x)^\top \frac{1}{T}\sum_{t=1}^T \theta_t$. As there exist environments where$\Delta_{(1)}^2/ d \ll 1/ \rho^*$, we are motivated to propose a novelalgorithm $\mathsf{P1}$-$\mathsf{RAGE}$ that aims to obtain the best of bothworlds: robustness to non-stationarity and fast rates of identification inbenign settings. We characterize the error probability of$\mathsf{P1}$-$\mathsf{RAGE}$ and demonstrate empirically that the algorithmindeed never performs worse than G-optimal design but compares favorably to thebest algorithms in the stationary setting.

A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationarity