16 problems

Localization-omission conjecture. The authors conjecture that their techniques may allow for a simpler and more direct analysis by omitting the localization, while obtaining almost…

Let $\adapttt{}$ be the modified adaptive algorithm for differentially private best-arm identification, and let $\delta$ denote the confidence level. Its modified transportation co…

Consider regret minimisation and best-arm identification (BAI) under differential privacy, at an arbitrary privacy level. Let an arm-level measure of distinguishability mean a quan…

Let $W^{G,\epsilon}_{a,b}$ be the transportation cost used to measure distinguishability between arms $a$ and $b$ in the Gaussian private best-arm identification setting, and let i…

Let $H(\boldsymbol{\nu},\epsilon)$ denote the instance-dependent complexity appearing in the analysis of the adaptive algorithm $\adaptt{}$, and let $\alpha>1$ be an algorithmic hy…

Sample-average asymptotic optimality conjecture. Replacing the AIPW estimator with the sample average estimator in the strategy should still yield an upper bound that matches the l…

In a multi-armed bandit experiment, suppose the strategy estimates the arms' variances during the experiment rather than assuming that they are known. Variance-estimation optimalit…

In fixed-confidence differentially private best-arm identification, let AdaP-TT denote the private tracking algorithm discussed above, and let TTUCB denote the corresponding non-pr…

Let $a\in[K]\backslash\{a^*_0\}$ and $d\in[K]\backslash\{a^*_0,a\}$. Let $L^a_T$ denote the loss for arm $a$ at time horizon $T$, and let the semiparametric efficient score functio…

Consider the proposed RS-AIPW strategy for fixed-budget best-arm identification in multi-armed bandits, together with the RS-DR and RS-SA strategies. RS-DR and RS-SA asymptotic opt…

The setting is a two-armed bandit problem using the RS-DR strategy, with allocation probability $w_{a,t}$ for arm $a$ at time $t$ and a re-estimated allocation probability used by…

Consider problems in which the globally optimal parameter belongs to a finite set, and suppose the problems admit notions of statistical heterogeneity and distributed sequential de…

Let $L$ denote the size of the ground set, and let $4\epsilon_C4$ denote the smallest optimality gap achievable in the corruption-tolerant best-arm identification setting. Conjectu…

Let $K$-armed bandit means satisfy $mu_1>mu_2$ and suppose that $mu_1$ and $mu_2$ are much larger than the other means. Worst-case ETC conjecture. In this regime, the regret of an…

Fixed-budget error exponent conjecture. In the fixed-budget setting,

Optimal-regret conjecture. The optimal regret might satisfy