Algorithm IMED

Regret minimization

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]

Pseudocode

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

Lai–Robbins lower bound

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)}$.

Regret bound for IMED

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]