Draft:Best arm identification

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 ${\displaystyle \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 ${\displaystyle T}$ is fixed, and the goal is to find the best arm with the highest possible confidence in ${\displaystyle T}$ turns.

Math formalisation

We have one player and ${\displaystyle K}$ actions (arms). Behind each arm ${\displaystyle k\in \{1,\ldots ,K\}}$ lies an unknown distribution ${\displaystyle \nu _{k}}$ with mean ${\displaystyle \mu _{k}}$. Each distribution ${\displaystyle \nu _{k}}$ belongs to a known family ${\displaystyle {\mathcal {D}}}$ (such as the set of Gaussian distributions or Bernoulli distributions). At each timestep ${\displaystyle t}$, the player selects an arm ${\displaystyle a_{t}}$ and observes an independent sample ${\displaystyle X_{t}\sim \nu _{a_{t}}}$ from the corresponding distribution.

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

In best arm identification (BAI) the objective is to identify an optimal arm.^[3]

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 ${\displaystyle \delta \in (0,1)}$ is specified at the beginning. The algorithm must stop at some finite stopping time ${\displaystyle \tau _{\delta }<+\infty }$ and return an arm ${\displaystyle {\hat {a}}_{\tau _{\delta }}}$ such that the probability of error is bounded: ${\displaystyle \mathbb {P} ({\hat {a}}_{\tau _{\delta }}\neq a^{*})\leq \delta }$. The objective is to minimize the expected sample complexity ${\displaystyle \mathbb {E} [\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 ${\displaystyle \delta =1-0.95=0.05}$).

• Fixed horizon: In this setting, the number of samples ${\displaystyle T}$ is fixed in advance. The goal is to design an algorithm that minimizes the probability of misidentifying the optimal arm: ${\displaystyle \mathbb {P} ({\hat {a}}_{T}\neq 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 ${\displaystyle 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 ${\displaystyle \mu _{k}}$, which means that each distribution is a Bernoulli distribution, so ${\displaystyle {\mathcal {D}}}$ is the set of Bernoulli distributions. We can use a BAI algorithm to minimize ${\displaystyle \mathbb {E} [\tau _{0.05}]}$, the number of patients required to find the best treatment with probability 95%.

Algorithm structure

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

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

Lower bound

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

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

For any algorithm satisfying the ${\displaystyle \delta }$-correctness constraint, the expected sample complexity satisfies $${\displaystyle \mathbb {E} [\tau _{\delta }]\geq C^{\star }\,\operatorname {kl} (\delta ,1-\delta )}$$ where the problem-dependent constant ${\displaystyle C^{\star }}$ only depends on ${\displaystyle \nu }$

More information , between distributions ...

More technical details of the lower bound

Notation: Define the following quantities: ${\displaystyle \operatorname {KL} (\nu ,\nu ')}$: the Kullback–Leibler divergence between distributions ${\displaystyle \nu }$ and ${\displaystyle \nu '}$; ${\displaystyle {\mathcal {K}}_{\inf }^{+}(\nu ,x,{\mathcal {D}}):=\inf {\Bigl \{}\operatorname {KL} (\nu ,\nu '):\nu '\in {\mathcal {D}},\ \mu '>x{\Bigr \}}}$: the minimal ${\displaystyle \operatorname {KL} }$-divergence between ${\displaystyle \nu }$ and a distribution in ${\displaystyle {\mathcal {D}}}$ with mean strictly greater than ${\displaystyle x}$; ${\displaystyle {\mathcal {K}}_{\inf }^{-}(\nu ,x,{\mathcal {D}}):=\inf {\Bigl \{}\operatorname {KL} (\nu ,\nu '):\nu '\in {\mathcal {D}},\ \mu '<x{\Bigr \}}}$: the minimal ${\displaystyle \operatorname {KL} }$-divergence between ${\displaystyle \nu }$ and a distribution in ${\displaystyle {\mathcal {D}}}$ with mean strictly less than ${\displaystyle x}$; ${\displaystyle C^{\star }}$ is defined through its inverse: $${\displaystyle (C^{\star })^{-1}:=\sup _{\omega \in \mathbf {\Delta } _{K}}\min _{a\neq a^{\star }}\inf _{x\in [\mu _{a},\mu ^{\star }]}\left\{\omega _{a^{\star }}\,{\mathcal {K}}_{\inf }^{-}(\nu _{a^{\star }},x,{\mathcal {D}})+\omega _{a}\,{\mathcal {K}}_{\inf }^{+}(\nu _{a},x,{\mathcal {D}})\right\}}$$ where ${\displaystyle \mathbf {\Delta } _{K}:=\{(\omega _{1},\dots ,\omega _{K})\in [0,1]^{K}\mid \sum _{k}\omega _{k}=1\}}$ is the simplex of sampling proportions.[6] Interpretation: Optimal proportions: The supremum over ${\displaystyle \omega \in \mathbf {\Delta } _{K}}$ characterizes the existence of an optimal allocation strategy that specifies how samples should be distributed among arms. This optimal proportion ${\displaystyle \omega ^{\star }}$ is independent of the confidence level ${\displaystyle \delta }$, it only depends on ${\displaystyle \nu }$. Most confusing instance: For each suboptimal arm ${\displaystyle a\neq a^{\star }}$, the inner optimization identifies the "closest" alternative problem instance where arm ${\displaystyle a}$ becomes optimal. Specifically, for a given threshold ${\displaystyle x\in [\mu _{a},\mu ^{\star }]}$, consider an alternative instance ${\displaystyle {\tilde {\nu }}(x)}$ where: (1) arms ${\displaystyle k\notin \{a,a^{\star }\}}$ remain unchanged: ${\displaystyle {\tilde {\nu }}_{k}(x)=\nu _{k}}$, and (2) arms ${\displaystyle a}$ and ${\displaystyle a^{\star }}$ are modified to have equal means at ${\displaystyle x}$: ${\displaystyle {\tilde {\mu }}_{a}(x)={\tilde {\mu }}_{a^{\star }}(x)=x}$. The infimum over ${\displaystyle 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.[6]

Close

Asymptotically optimal algorithms

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

The first algorithm proposed to achieve asymptotic optimality is the Track-and-Stop algorithm^[6], which consists of tracking the constant ${\displaystyle C^{*}}$ in lower bound by using the empirical distribution and adding some minimal exploration to be sure that the estimated lower bound ${\displaystyle {\hat {C}}^{*}}$ is close enough to the real lower bound ${\displaystyle C^{*}}$.

More information The algorithm attempts to estimate the optimal sampling proportions ...

More technical details of the algorithm Track-and-Stop

Sampling rule: The algorithm attempts to estimate the optimal sampling proportions ${\displaystyle \omega ^{\star }}$ using the current empirical distributions ${\displaystyle {\hat {\nu }}(t)}$ at round ${\displaystyle t}$. Arms are then sampled to ensure that the empirical proportions ${\displaystyle N_{a}(t)/t}$ track the estimated optimal proportions ${\displaystyle {\hat {\omega }}^{\star }(t)}$. Forced exploration is incorporated to prevent premature convergence and ensure that ${\displaystyle {\hat {\omega }}^{\star }(t)}$ remains close to the true ${\displaystyle \omega ^{\star }}$.[6] Stopping rule: Let ${\displaystyle {\hat {a}}^{\star }}$ denote the empirical best arm (i.e., the arm with highest empirical mean) given the current sample counts ${\displaystyle (N_{1}(t),\dots ,N_{K}(t))}$. Define the stopping statistic: $${\displaystyle W_{t}:=\min _{a\neq {\hat {a}}^{\star }}\inf _{x\in [{\hat {\mu }}_{a},{\hat {\mu }}^{\star }]}\left\{N_{{\hat {a}}^{\star }}(t)\,{\mathcal {K}}_{\inf }^{-}({\hat {\nu }}_{{\hat {a}}^{\star }}(t),x,{\mathcal {D}})+N_{a}(t)\,{\mathcal {K}}_{\inf }^{+}({\hat {\nu }}_{a}(t),x,{\mathcal {D}})\right\},}$$ which can be interpreted as a sample-complexity-weighted estimate of the separation between the current empirical best arm and its closest competitor. The algorithm stops at $${\displaystyle \tau _{\delta }:=\inf\{t\mid W_{t}\geq c(\delta ,t)\},}$$ where the threshold ${\displaystyle c(\delta ,t)}$ is chosen to ensure time-uniform concentration inequality. Specifically, ${\displaystyle c(\delta ,t)}$ must satisfy $${\displaystyle \mathbb {P} {\Bigl (}\exists (N_{1},\dots ,N_{K})\in \mathbb {N} ^{K}:\max _{b\in \{1,\dots ,K\}}\min _{a\neq b}\inf _{x\in [{\hat {\mu }}_{a},{\hat {\mu }}_{b}]}\{N_{b}\,{\mathcal {K}}_{\inf }^{-}({\hat {\nu }}_{b},x,{\mathcal {D}})+N_{a}\,{\mathcal {K}}_{\inf }^{+}({\hat {\nu }}_{a},x,{\mathcal {D}})\}\geq c{\bigl (}\delta ,\sum _{k=1}^{K}N_{k}{\bigr )}{\Bigr )}\leq \delta .}$$ Intuitively, the algorithm stops when there is sufficient statistical evidence (at confidence level ${\displaystyle 1-\delta }$) that the current empirical best arm is indeed optimal. For distributions with support in ${\displaystyle [0,1]}$, one valid threshold is $${\displaystyle c(\delta ,t):=\ln(1/\delta )+2\ln(1+t/2)+2+\ln(K-1).}$$ While the constants can be refined, this threshold captures the leading-order term ${\displaystyle \ln(1/\delta )}$ and ensures the desired confidence guarantee.[7]

Close

Algorithm structure

A typical fixed-horizon BAI algorithm proceeds as follows:

Input: Distribution family ${\displaystyle {\mathcal {D}}}$, horizon ${\displaystyle T}$
Initialize: 
    For each arm ${\displaystyle i}$: pull once and set ${\displaystyle N_{i}\leftarrow 1}$, ${\displaystyle {\hat {\nu }}_{i}\leftarrow }$ initial empirical distribution
for ${\displaystyle t}$ from ${\displaystyle K+1}$ to ${\displaystyle T}$ do:
    ${\displaystyle a_{t}\leftarrow }$ Sampling_rule(${\displaystyle {\mathcal {D}}}$, ${\displaystyle T}$, ${\displaystyle N}$, ${\displaystyle {\hat {\nu }}}$)
    Observe reward ${\displaystyle X_{t}\sim \nu _{a_{t}}}$
    Update: ${\displaystyle N_{a_{t}}\leftarrow N_{a_{t}}+1}$
    Update empirical distribution ${\displaystyle {\hat {\nu }}_{a_{t}}}$
return ${\displaystyle {\hat {a}}_{T}^{\star }\leftarrow \arg \max _{a}{\hat {\mu }}_{a}}$

Unlike the fixed-confidence setting, there is no stopping rule because we stop at time ${\displaystyle 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 ${\displaystyle T}$. It is expressed as an asymptotic result when ${\displaystyle T}$ is large.

Lower bound theorem: For any algorithm, for any instance ${\displaystyle \nu }$, there exists a constant ${\displaystyle H(\nu )}$ that depends only on ${\displaystyle \nu }$ such that the probability of error satisfies $${\displaystyle \lim _{T\to +\infty }\mathbb {P} ({\hat {a}}_{T}\notin {\mathcal {A}}^{\star })\geq \exp \left(-TH(\nu )\right)}$$^[8]

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

Simple regret

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

While ${\displaystyle \mathbb {P} ({\hat {a}}_{T}^{*}\neq a^{\star })}$ treats all mistakes with the same cost, the simple regret ${\displaystyle r_{T}}$ accounts for the gap between the optimal mean ${\displaystyle \mu ^{*}}$ and the mean of the arm considered as the optimal arm by the algorithm ${\displaystyle \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.^[9]