Best arm identification

Short description: Multi-armed bandit sequential game

Best arm identification (BAI) is a sequential one-player game where the player has to find the best action (arm) among a list of actions (arms) by collecting information in the most efficient way.

It is a multi-armed bandit game as a player only gets information about an arm by playing it. The most common objective in multi-armed bandit games is to minimize the regret (i.e., play the best action as much as possible), but in BAI, the goal is to find the best arm as efficiently as possible.

This problem naturally arises in scenarios such as adaptive clinical trials where the number of patients is limited and the quantification of the confidence in a treatment is important. It also arises in hyperparameter optimization where the goal is to find the optimal choice of hyperparameters for an algorithm with the smallest possible number of experiments, as it can be costly in terms of time, energy, or money.

Stochastic multi-armed bandit

The stochastic multi-armed bandit (MAB) is a sequential game with one player and $K$ actions (arms). Each arm has an unknown probability distribution associated with it.

At each turn, the player has to choose one action and receive an observation from the probability distribution associated with the arm. The more you play an arm, the more you get information on its probability distribution.

Best arm identification

In BAI the goal is to find the arm that has the probability distribution with the highest mean. BAI may be either fixed confidence or fixed horizon. In a fixed-confidence game, a confidence level $\delta$ is fixed at the beginning of the game and the goal is to find the best arm with this confidence level in as few turns as possible. In a fixed horizon game, the number of turns $T$ is fixed, and the goal is to find the best arm with the highest possible confidence in $T$ turns.

Math formalisation

We have one player and $K$ actions (arms). Behind each arm $k\in \{1,\dots ,K\}$ lies an unknown distribution ${\nu }_k$ with mean ${\mu }_k$. Each distribution ${\nu }_k$ belongs to a known family ${𝒟}$ (such as the set of Gaussian distributions or Bernoulli distributions). At each time step $t$, the player selects an arm $a_t$ and observes an independent sample $X_t\sim {\nu }_{a_t}$ from the corresponding distribution.

We will note ${\mu }^{*}:=\max {\mu }_a$ the highest mean. An arm $a$ that satisfies ${\mu }_a={\mu }^{*}$ is called an optimal arm; otherwise it is called suboptimal arm.

In best arm identification (BAI) the objective is to identify an optimal arm.

Two main settings for BAI appear in the literature:

• Fixed confidence: In this setting, one typically assumes that there exists a unique optimal arm. A confidence level $\delta \in (0,1)$ is specified at the beginning. The algorithm must stop at some finite stopping time ${\tau }_{\delta }<+\mathrm{\infty }$ and return an arm ${\hat{a}}_{{\tau }_{\delta }}$ such that the probability of error is bounded: $\mathbb{\mathbb{P}}({\hat{a}}_{{\tau }_{\delta }}\ne a^{*})\le \delta$. The objective is to minimize the expected sample complexity $\mathbb{𝔼}[{\tau }_{\delta }]$.

Such a setting appears, for example, when a constraint on the confidence is required (for example, if we require a confidence level of 95%, so $\delta =1-0.95=0.05$).

• Fixed horizon: In this setting, the number of samples $T$ is fixed in advance. The goal is to design an algorithm that minimizes the probability of misidentifying the optimal arm: $\mathbb{\mathbb{P}}({\hat{a}}_T\ne a^{*})$.

This setting appears when the number of experiments is limited (for drug tests, the number of patients can be fixed in advance).

Example of simple modelling

In the case where we have $K$ treatments and we want to be sure with a confidence level of 95% which treatment is the best to heal a specific disease. Each treatment heals or does not heal the disease with a probability ${\mu }_k$, which means that each distribution is a Bernoulli distribution, so ${𝒟}$ is the set of Bernoulli distributions. We can use a BAI algorithm to minimize $\mathbb{𝔼}[{\tau }_{0.05}]$, the number of patients required to find the best treatment with probability 95%.

Applications

Best arm identification naturally arises in several practical domains:

• Adaptive clinical trials: The objective is to identify the most effective treatment based on sequentially collected patient data. Each treatment can be modeled as having an underlying distribution of outcomes. The goal is to identify the treatment with the highest expected outcome with high confidence (fixed confidence setting $\delta$) while minimizing the number of drug test patients (minimise $\mathbb{𝔼}[{\tau }_{\delta }]$), as it costs to pay patients for this and we would like to use as little as possible less effective drugs.
• Hyperparameter tuning: Selecting the best configuration for machine learning models efficiently by treating each hyperparameter setting as an arm. The goal is to find the best hyperparameter with as few experiments possible as experiments are costly in time and in energy

Fixed confidence level

Typical run for a BAI algorithm with fixed confidence

In the fixed-confidence setting, the goal is to design an algorithm that identifies the best arm with a prescribed confidence level $\delta$ while minimizing the expected number of samples. Any such algorithm requires two key components:

• Stopping rule: A decision criterion that determines when to stop sampling. Formally, this defines a stopping time ${\tau }_{\delta }$ and returns an arm ${\hat{a}}_{{\tau }_{\delta }}$ such that $\mathbb{\mathbb{P}}({\hat{a}}_{{\tau }_{\delta }}\ne a^{\star })\le \delta$ and $\mathbb{\mathbb{P}}({\tau }_{\delta }<+\mathrm{\infty })=1$.
• Sampling rule: A policy $\pi$ that, at each round $t$, selects the next arm to sample $a_t$ based on all previous observations $(a_s,X_s{)}_{s<t}$.

Algorithm structure

The general structure of a fixed-confidence BAI algorithm can be described as follows:

Input: Distribution family ${𝒟}$, confidence level $\delta$
Initialize: 
    For each arm $i$: set $N_i\leftarrow 1$, ${\hat{\nu }}_i\leftarrow \text{None}$
    Set $\tau \leftarrow 0$, $\text{stop}\leftarrow \text{False}$
while $\text{stop}==\text{False}$ do:
    $a\leftarrow$ Sampling_rule(${𝒟}$, $\delta$, $N$, $\hat{\nu }$)
    Observe reward $X\sim {\nu }_a$
    Update: $N_a\leftarrow N_a+1$
    Update empirical distribution ${\hat{\nu }}_{a_{\tau }}$
    $\tau \leftarrow \tau +1$
    $\text{stop}$ ← Stopping_rule(${𝒟}$, $\delta$, $N$, $\hat{\nu }$)
return ${\hat{a}}_{\tau }^{\star }\leftarrow \arg \underset{a}{\max }{\hat{\mu }}_a$

Lower bound

$C^{*}$ when we have two Gaussian arms of variance 1 and means equal to $\mu$ and $\mu +x$

The minimal expected number of pulls to obtain the confidence level of $1-\delta$ was determined in 2016. For a given instance $\nu$ and a fixed $\delta$, it provides the minimum value of $\mathbb{𝔼}[{\tau }_{\delta }]$ possible.

To give the lower bound, we first need to define the function $\mathrm{kl}(\delta ,1-\delta )$, the Kullback–Leibler divergence between two Bernoulli distributions with means $\delta$ and $1-\delta$. This is equivalent to $\ln (1/\delta )$ when $\delta$ tend to $0$.

For any algorithm satisfying the $\delta$-correctness constraint, the expected sample complexity satisfies $$\mathbb{𝔼}[{\tau }_{\delta }]\ge C^{\star }\mathrm{kl}(\delta ,1-\delta )$$ where the problem-dependent constant $C^{\star }$ only depends on $\nu$. An optimal sampling rule ${\omega }^{*}$ is associated with this optimal constant.

More technical details of the lower bound

Notation: Define the following quantities:

• $\mathrm{KL}(\nu ,{\nu }^{\prime })$: the Kullback–Leibler divergence between distributions $\nu$ and ${\nu }^{\prime }$;
• ${{𝒦}}_{\inf }^{+}(\nu ,x,{𝒟}):=\inf \{\mathrm{KL}(\nu ,{\nu }^{\prime }):{\nu }^{\prime }\in {𝒟},{\mu }^{\prime }>x\}$: the minimal $\mathrm{KL}$-divergence between $\nu$ and a distribution in ${𝒟}$ with mean strictly greater than $x$;
• ${{𝒦}}_{\inf }^{-}(\nu ,x,{𝒟}):=\inf \{\mathrm{KL}(\nu ,{\nu }^{\prime }):{\nu }^{\prime }\in {𝒟},{\mu }^{\prime }<x\}$: the minimal $\mathrm{KL}$-divergence between $\nu$ and a distribution in ${𝒟}$ with mean strictly less than $x$;

$C^{\star }$ is defined through its inverse: $$(C^{\star }{)}^{-1}:=\underset{\omega \in {\mathrm{\Delta }}_K}{\sup }\underset{a\ne a^{\star }}{\min }\underset{x\in [{\mu }_a,{\mu }^{\star }]}{\inf }\{{\omega }_{a^{\star }}{{𝒦}}_{\inf }^{-}({\nu }_{a^{\star }},x,{𝒟})+{\omega }_a{{𝒦}}_{\inf }^{+}({\nu }_a,x,{𝒟})\}$$ where ${\mathrm{\Delta }}_K:=\{({\omega }_1,\dots ,{\omega }_K)\in [0,1{]}^K\mid \sum _k{\omega }_k=1\}$ is the simplex of sampling proportions.

Interpretation:

• Optimal sampling rule: The supremum over $\omega \in {\mathrm{\Delta }}_K$ characterizes the existence of an optimal allocation strategy that specifies how samples should be distributed among arms. This optimal proportion ${\omega }^{\star }$ is independent of the confidence level $\delta$, it only depends on $\nu$.
• Most confusing instance: For each suboptimal arm $a\ne a^{\star }$, the inner optimization identifies the "closest" alternative problem instance where arm $a$ becomes optimal. Specifically, for a given threshold $x\in [{\mu }_a,{\mu }^{\star }]$, consider an alternative instance $\tilde{\nu }(x)$ where: (1) arms $k\notin \{a,a^{\star }\}$ remain unchanged: ${\tilde{\nu }}_k(x)={\nu }_k$, and (2) arms $a$ and $a^{\star }$ are modified to have equal means at $x$: ${\tilde{\mu }}_a(x)={\tilde{\mu }}_{a^{\star }}(x)=x$. The infimum over $x$ then identifies the alternative instance that is hardest to distinguish from the original problem.

The proof technique follows a similar approach to the Lai–Robbins lower bound for regret minimization, using change-of-measure arguments and information-theoretic inequalities.

Asymptotically optimal algorithms

Since $\mathrm{kl}(\delta ,1-\delta )\sim \ln (1/\delta )$ as $\delta \to 0$, an algorithm is called asymptotically optimal if $$\underset{\delta \to 0}{\lim }\frac{\mathbb{𝔼}[{\tau }_{\delta }]}{\ln (1/\delta )}=C^{\star }.$$

The first algorithm proposed to achieve asymptotic optimality is the Track-and-Stop algorithm, which consists of tracking the optimal sampling rule ${\omega }^{*}$ in the lower bound by using the empirical distribution and choosing the next arm to play according to this estimated optimal sampling rule.

Fixed horizon

In the fixed-horizon setting, the total number of samples $T$ is specified in advance, contrasting with the fixed-confidence setting where sampling continues until a confidence criterion is met. The algorithm must select an arm at each round $t\in \{1,\dots ,T\}$, and at the end of the horizon, it returns a recommendation ${\hat{a}}_T$. The objective is to minimize the probability of error $\mathbb{\mathbb{P}}({\hat{a}}_T\ne a^{\star })$.

This setting is particularly relevant when computational or experimental resources are strictly limited, such as in clinical trials when we want to figure out which of $K$ is the best, and patient enrollment is fixed. Each arm corresponds to a choice of treatment given to one patient between $K$ which gives an observation of the distribution of the treatment, and each patient corresponds to a turn $t$. The total number of patients is the horizon $T$

Algorithm structure

A typical fixed-horizon BAI algorithm proceeds as follows:

Input: Distribution family ${𝒟}$, horizon $T$
Initialize: 
    For each arm $i$: pull once and set $N_i\leftarrow 1$, ${\hat{\nu }}_i\leftarrow$ initial empirical distribution
for $t$ from $K+1$ to $T$ do:
    $a_t\leftarrow$ Sampling_rule(${𝒟}$, $T$, $N$, $\hat{\nu }$)
    Observe reward $X_t\sim {\nu }_{a_t}$
    Update: $N_{a_t}\leftarrow N_{a_t}+1$
    Update empirical distribution ${\hat{\nu }}_{a_t}$
return ${\hat{a}}_T^{\star }\leftarrow \arg \underset{a}{\max }{\hat{\mu }}_a$

Unlike the fixed-confidence setting, there is no stopping rule because we stop at time $T$. The algorithm is only base on a sampling rule.

Lower bound

The lower bound in the fixed-horizon setting gives the best confidence level we can reach with a given number of turns $T$. It is expressed as an asymptotic result when $T$ is large.

Lower bound theorem: For any algorithm, for any instance $\nu$, there exists a constant $H(\nu )$ that depends only on $\nu$ such that the probability of error satisfies $$\underset{T\to +\mathrm{\infty }}{\lim }\mathbb{\mathbb{P}}({\hat{a}}_T\notin {{𝒜}}^{\star })\ge \exp (-TH(\nu ))$$

This result shows that the error probability decays exponentially with the number of turns $T$.

Simple regret

An alternative performance metric for fixed-horizon BAI is the simple regret, defined as $$r_T:=\mathbb{𝔼}[{\mu }^{\star }-{\mu }_{{\hat{a}}_T^{*}}],$$ which measures the expected suboptimality of the returned arm.

While $\mathbb{\mathbb{P}}({\hat{a}}_T^{*}\ne a^{\star })$ treats all mistakes with the same cost, the simple regret $r_T$ accounts for the gap between the optimal mean ${\mu }^{*}$ and the mean of the arm considered as the optimal arm by the algorithm ${\mu }_{{\hat{a}}_T^{*}}$. This distinction is important in applications where the cost of choosing a suboptimal arm depends on how far it is from optimal.

See also

• Multi-armed bandit
• Design of experiments
• Concentration inequality