Algorithm IMED

In multi-armed bandit problems, IMED (for Indexed Minimum Empirical Divergence) is an algorithm developed in 2015 by Junya Honda and Akimichi Takemura. It is the first algorithm proved to be asymptotically optimal respect to the problem-dependant Lai–Robbins lower bound^[1] for distributions in ${\displaystyle (-\infty ,1]}$^[2].

The Multi-armed bandit problem is a sequential game where one player has to choose at each turn between ${\displaystyle K}$ actions (arms). Behind every arm ${\displaystyle a}$ there is an unknown distribution ${\displaystyle \nu _{a}}$ that lies in a set ${\displaystyle {\mathcal {D}}}$ known by the player (for example, ${\displaystyle {\mathcal {D}}}$ can be the set of Gaussian distributions or Bernoulli distributions).

At each turn ${\displaystyle t}$ the player chooses (pulls) an arm ${\displaystyle a_{t}}$, he then gets an observation ${\displaystyle X_{t}}$ of the distribution ${\displaystyle \nu _{a_{t}}}$.

The goal is to minimize the regret at time ${\displaystyle T}$ that is defined as

${\displaystyle R_{T}:=\sum _{a=1}^{K}\Delta _{a}\mathbb {E} [N_{a}(T)]}$

where

• ${\displaystyle \mu _{a}:=\mathbb {E} [\nu _{a}]}$ is the mean of arm ${\displaystyle a}$
• ${\displaystyle \mu ^{*}:=\max _{a}\mu _{a}}$ is the highest mean
• ${\displaystyle \Delta _{a}:=\mu ^{*}-\mu _{a}}$
• ${\displaystyle N_{a}(t)}$ is the number of pulls of arm ${\displaystyle a}$ up to turn ${\displaystyle t}$
  

The player has to find an algorithm that chooses at each turn ${\displaystyle t}$ which arm to pull based on the previous actions and observations ${\displaystyle (a_{s},X_{s})_{s<t}}$ to minimize the regret ${\displaystyle R_{T}}$.

This is a trade-off problem between exploration to find the best arm (the arm with the highest mean) and exploitation to play as much as possible the arm that we think is the best arm.^[3]

Multi-armed bandit algorithms are used in a variety of fields; for example, they have applications in clinical trials, recommender systems, telecommunications^[4], and agriculture.^[5]

The algorithm compute an index at each turn for each arm. Then it pull the arm with the smallest index.^[2]

The index is the sum of two terms. The first is the cost of to transport the empirical distribution to a distribution such that the arm is optimal. The second is the cost of behing pulled to much.

Formally, the index ${\displaystyle I_{a}(t)}$ of an arm ${\displaystyle a}$ at turn ${\displaystyle t}$ is defined as follow:

${\displaystyle I_{a}(t):=N_{a}(t)K_{inf}({\hat {\nu }}_{a}(t),{\hat {\mu }}^{*}(t))+\ln(N_{a}(t))}$

where

• ${\displaystyle {\mathcal {K}}_{inf}(\nu ,\mu ,{\mathcal {D}}):=\inf \left\{\mathrm {KL} (\nu ,{\tilde {\nu }})\ |\ {\tilde {\nu }}\in {\mathcal {P}}([-\infty ,1]),\ \mathbb {E} [{\tilde {\nu }}]>\mu \right\}}$
• ${\displaystyle \mathrm {KL} }$ is the Kullback–Leibler divergence
• ${\displaystyle {\mathcal {P}}([-\infty ,1])}$ is the set of distribution in ${\displaystyle [-\infty ,1]}$
• ${\displaystyle {\hat {\nu }}_{a}(t)}$ is the empirical distribution of arm ${\displaystyle a}$ at turn ${\displaystyle t}$
• ${\displaystyle {\hat {\mu }}^{*}(t)}$ is the highest empirical mean of turn ${\displaystyle t}$

Remark : For arms ${\displaystyle a}$ that verify ${\displaystyle {\hat {\mu }}_{a}(t)={\hat {\mu }}^{*}(t)}$ we have ${\displaystyle K_{inf}({\hat {\nu }}_{a}(t),{\hat {\mu }}^{*}(t))=0}$. Then there index is equal to ${\displaystyle \ln(N_{a}(t))}$

for each arm i do:
    n[i] ← 1; nu[i] ← None; mu[i] ← None
for t from 1 to K do:
    select arm t
    observe reward r
    n[t] ← n[t] + 1
    nu[t] ← update empirical distribution
    mu[t] ← update empirical mean
for t from K+1 to T do:
    mu* ← highest mu
    for each arm i do:
        scoreK[i] ← n[i] K_inf(nu[i],mu*)
        scoreN[i] ← ln(n[i])
        index[i] ← scoreK[i] + scoreN[i]
    select arm a with smallest index[a]
    observe reward r
    n[a] ← n[a] + 1
    nu[a] ← update empirical distribution
    mu[a] ← update empirical mean

In the multi-armed bandit problem we have the asymptotic Lai–Robbins lower bound^[1] asymptotic lower bound on regret. The algorithm IMED is the first algorithm that matches this lower bound for distribution in ${\displaystyle (-\infty ,1]}$ in the first order. If the distribution are also bounded then it also match the second order. It is the first algorithm that match the second under of this lower bound.^[2]

In 1985 Lai and Robbins proved an asymptotic, problem-dependent lower bound on regret^[1]. In 2018, Aurelien Garivier, Pierre Menard and Gilles Stoltz proved a refined lower bound that gives the second order ^[6]

It states that for every consistent algorithm on the set ${\displaystyle {\mathcal {P}}([-\infty ,1])}$ — that is, an algorithm for which, for every ${\displaystyle (\nu _{1},\dots ,\nu _{K})\in {\mathcal {P}}([-\infty ,1])^{K}}$, the regret ${\displaystyle R_{T}}$ is subpolynomial (i.e. ${\displaystyle R_{T}=o_{T\to +\infty }(T^{\alpha })}$ for all ${\displaystyle \alpha >0}$) — we have:

${\displaystyle R_{T}\geq \left(\sum _{a:\mu _{a}<\mu ^{*}}{\frac {\Delta _{a}}{{\mathcal {K}}_{\inf }(\nu _{a},\mu ^{*})}}\right)\ln T-\Omega _{T\to +\infty }(\ln \ln T).}$

This bound is asymptotic (as ${\displaystyle T\to +\infty }$) and gives a first-order lower bound of order ${\displaystyle \ln T}$ with the optimal constant in front of it and the second order in ${\displaystyle -\Omega (\ln \ln T)}$.

If the distribution of every arm ${\displaystyle a}$ is ${\displaystyle (-\infty ,1]}$ ( i.e. ${\displaystyle \nu _{a}\in {\mathcal {P}}([-\infty ,1]))}$ then the regret of the algorithm IMED verify

${\displaystyle R_{T}\leq \left(\sum _{a:\mu _{a}<\mu ^{*}}{\frac {\Delta _{a}}{{\mathcal {K}}_{\inf }(\nu _{a},\mu ^{*})}}\right)\ln T+O(1)}$^[2]

If all the distribution ${\displaystyle \nu _{a}}$ are bounded then it exists a constant ${\displaystyle C>0}$ such that for ${\displaystyle T}$ large enough the regret of IMED is upper bounded by

${\displaystyle R_{T}\leq \left(\sum _{a:\mu _{a}<\mu ^{*}}{\frac {\Delta _{a}}{{\mathcal {K}}_{\inf }(\nu _{a},\mu ^{*})}}\right)\ln T-C\ln \ln T}$^[2]

The algorithm only requiere to compute the ${\displaystyle K_{inf}}$ for suboptimal arms who are pulled ${\displaystyle O(\ln T)}$ times, which make it a lot faster than KL-UCB. A faster version of IMED was developed in 2023 to make it even faster, using a Taylor development of the ${\displaystyle K_{inf}}$ in the first order ^[7].

• Multi-armed bandit
• Kullback–Leibler Upper Confidence Bound
• Confidence interval