22 problems

An experimental procedure is any procedure for comparing recommendation algorithms in an A/B experiment, and preserving the sign means preserving the sign of the comparison between…

In an $epsilon$-global differentially private stochastic bandit, an algorithm is said to forget when it discards past rewards between independent episodes. Forgetting-necessity con…

Consider a $K$-armed bandit model. For arm $k$, let $N_{k,T}$ be the number of pulls by time $T$, let $\bar\mu_{k,T}$ be its empirical mean reward, and let $I(\cdot)$ be the index…

Stopping-time mutual-information tightness conjecture. The achievability result for $I_{t,\mathrm{E}}^\star$ is tight; equivalently, its lower bound cannot be improved in general.…

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…

Exponential-dependence conjecture. Some exponential dependence on $M$ is unavoidable in the sample complexity of learning latent multi-armed bandits.

Let $\epsilon$ denote the experimentation parameter in the paper's multi-armed bandit model, and let $\Pi^{I}_{\beta,c}$ denote the policymaker's discounted payoff, with discount f…

Let $M$ clients play a multi-armed bandit for $T$ time slots. For client $m$, let $k'_{*,m}$ denote its optimal arm, let $X'_{k,m}$ denote the reward distribution of arm $k$ for cl…

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 $M>2$ and let $N$ be the number of channels. For a problem instance $(M,N,\boldsymbol\mu)$, consider all possible permutations of arms in the set $\mathcal{S}(M)$ and the round…

Let $A$ be the set of arms, let $A_f$ be the set of feasible arms, and let $\Pi$ denote the set of deterministic algorithms for the constrained multi-armed bandit problem. An algor…

Consider the finite-horizon Bayesian two-armed bandit and the deterministic dynamic-programming design, denoted by $\operatorname{DP}$. Let $t\ll T$ denote epochs with a large numb…

Let the two arms have success probabilities from the known set $\{\theta_C,\theta_D\}$, where $\theta_C+\theta_D\neq 1$, with the assignment of probabilities to arms unknown. A des…

Let $N$ be the total number of Monte Carlo samples, and consider the instance-wise upper bound on $\mathbb{E}[N\mid\{P_i^{\mathrm{fMC}}\}=\{p_i\}]$ given for the confidence bounds…

Let $\mathcal{A}$ be a generic bandit algorithm, and let $\mathcal{A}'$ be its non-restarting doubling-trick version, which reinitializes the algorithm at successive horizons while…

Let an anytime algorithm be constructed from a non-anytime algorithm by applying a doubling trick. A geometric doubling sequence is known not to preserve the relevant problem-depen…

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…

The Gittins index strategy is compared with OCUCB, Thompson sampling, and UCB in Gaussian-noise bandit experiments. The Gittins strategy is a Bayesian strategy whose performance is…

Let the virtual arm have mean $(\mu_{1,1}+\mu_{2,1})/2$, where the arms in the first action are denoted by $\mathcal{P}_1$ and the remaining arms are the other arms. Virtual-arm re…

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

Optimal-regret conjecture. The optimal regret might satisfy

Impossibility conjecture. There is no algorithm that does not need to know the time horizon and whose regret has a tail distribution satisfying