Kullback–Leibler Upper Confidence Bound

In multi-armed bandit problems, KL-UCB (for Kullback–Leibler Upper Confidence Bound)^[1] is a type of UCB-type algorithm that is asymptotically optimal, in the sense that its regret matches the problem-dependent lower bound derived by Lai and Robbins.^[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 precision agriculture.^[5]

The algorithm is a UCB-type algorithm based on optimism, which means that at each turn ${\displaystyle t}$ we compute an upper confidence bound (UCB) for the mean of each arm ${\displaystyle a}$; we then pull the arm with the highest UCB.

The difference with KL-UCB is that it uses an estimation of the lower bound of Lai–Robbins^[2] to make the upper confidence bound.^[1]

The algorithm was first introduced in 2011 for Bernoulli distribution.^[1] It was then extended to one-dimensional exponential families and bounded distributions in 2013.^[6] An adaptation called KL-UCB-Switch, which uses a mix of MOSS^[7] and KL-UCB, was developed to obtain both the problem-dependent and problem-independent asymptotic lower bounds in 2022.^[8] The algorithm was also extended to Lipschitz bandits in 2014.^[9]

At first, the algorithm pulls all the arms once. Then, for each turn ${\displaystyle t\geq K+1}$, for each arm ${\displaystyle a}$, we compute:

${\displaystyle U_{a}(t):=\max \left\{\mu \ |\ N_{a}(t){\mathcal {K}}_{inf}({\hat {\nu }}_{a}(t),\mu ,{\mathcal {D}})\leq \delta _{t}\right\}}$

where

• ${\displaystyle {\mathcal {K}}_{inf}(\nu ,\mu ,{\mathcal {D}}):=\inf \left\{\mathrm {KL} (\nu ,{\tilde {\nu }})\ |\ {\tilde {\nu }}\in {\mathcal {D}},\ \mathbb {E} [{\tilde {\nu }}]>\mu \right\}}$
• ${\displaystyle \mathrm {KL} }$ is the Kullback–Leibler divergence
• ${\displaystyle {\hat {\nu }}_{a}(t)}$ is the empirical distribution of arm ${\displaystyle a}$ at turn ${\displaystyle t}$
• ${\displaystyle \delta _{t}}$ is a well-chosen sequence of positive numbers, often equal to ${\displaystyle \ln t+c\ln \ln t}$ with ${\displaystyle c>0}$.^[6]

Then we choose the arm ${\displaystyle a_{t}}$ with the highest index:

${\displaystyle a_{t}:=\arg \max _{a}U_{a}(t)}$

We note that the algorithm does not require knowledge of ${\displaystyle T}$.

In the special case of Gaussian distribution with fixed variance ${\displaystyle \sigma ^{2}}$, we have:

${\displaystyle U_{a}(t)={\hat {\mu }}_{a}(t)+{\sqrt {\frac {2\sigma ^{2}\delta _{t}}{N_{a}(t)}}}}$

with ${\displaystyle {\hat {\mu }}_{a}(t)}$ being the empirical mean of arm ${\displaystyle a}$ at turn ${\displaystyle t}$.

The player gets the set D
for each arm i do:
    n[i] ← 1; nu[i] ← None; d ← ln(K)
for t from 1 to K do:
    select arm t
    observe reward r
    n[t] ← n[t] + 1
    nu[t] ← update empirical distribution
for t from K+1 to T do:
    for each arm i do:
        index[i] ← compute_index(n[i], nu[i], D, d)
    select arm a with highest index[a]
    observe reward r
    n[a] ← n[a] + 1
    nu[a] ← update empirical distribution
    d ← ln(t+1)

In the multi-armed bandit problem we have the Lai–Robbins^[2] asymptotic lower bound on regret. The algorithm KL-UCB matches this lower bound for one-dimensional exponential families with ${\displaystyle \delta _{t}:=\ln t+3\ln \ln t}$ and for distributions bounded in ${\displaystyle [0,1]}$ with ${\displaystyle \delta _{t}:=\ln t+\ln \ln t}$.^[6]

In 1952 Lai and Robbins proved an asymptotic, problem-dependent lower bound on regret.

It states that for every consistent algorithm on the set ${\displaystyle {\mathcal {D}}}$ — that is, an algorithm for which, for every ${\displaystyle (\nu _{1},\dots ,\nu _{K})\in {\mathcal {D}}^{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 ^{*},{\mathcal {D}})}}\right)\ln T+o_{T\to +\infty }(\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.

The algorithm matches the Lai–Robbins^[2] lower bound for one-dimensional exponential-family distributions and for distributions bounded in ${\displaystyle [0,1]}$.^[6]

For ${\displaystyle {\mathcal {D}}}$ being the set of one-dimensional exponential families, with ${\displaystyle \delta _{t}:=\ln t+3\ln \ln t}$ we have the following upper bound on the regret of KL-UCB:^[6]

${\displaystyle R_{T}\leq \left(\sum _{a:\mu _{a}<\mu ^{*}}{\frac {\Delta _{a}}{{\mathcal {K}}_{\inf }(\nu _{a},\mu ^{*},{\mathcal {D}})}}\right)\ln T+O_{T}({\sqrt {\ln T}}).}$

For ${\displaystyle {\mathcal {D}}={\mathcal {P}}([0,1])}$ (the set of distributions supported on ${\displaystyle [0,1]}$), and for ${\displaystyle \delta _{t}:=\ln t+\ln \ln t}$, we have the following upper bound on the regret of KL-UCB:^[6]

${\displaystyle R_{T}\leq \left(\sum _{a:\mu _{a}<\mu ^{*}}{\frac {\Delta _{a}}{{\mathcal {K}}_{\inf }(\nu _{a},\mu ^{*},{\mathcal {D}})}}\right)\ln T+O_{T}{\big (}(\ln T)^{4/5}\ln \ln T{\big )}.}$

For ${\displaystyle {\mathcal {D}}={\mathcal {P}}([0,1])}$, the runtime needed per step and for an arm ${\displaystyle k}$ with ${\displaystyle n}$ observations is ${\displaystyle {\mathcal {O}}{\big (}n(\ln n)^{2}{\big )}}$.^[10] This is higher than that of other optimal algorithms, such as NPTS^[11] with ${\displaystyle {\mathcal {O}}(n)}$.^[10] MED^[12] with ${\displaystyle {\mathcal {O}}(n\ln n)}$.^[10] and IMED^[13] with ${\displaystyle {\mathcal {O}}(n\ln n)}$.^[10]

The high runtime of KL-UCB is due to a two-level optimisation: for each arm and candidate mean ${\displaystyle \mu }$, the algorithm evaluates ${\displaystyle {\mathcal {K}}_{\inf }({\hat {\nu }}_{a}(t),\mu ,{\mathcal {D}})}$ and then maximises ${\displaystyle \mu }$ subject to ${\displaystyle N_{a}(t)\,{\mathcal {K}}_{\inf }({\hat {\nu }}_{a}(t),\mu ,{\mathcal {D}})\leq \delta _{t}}$. For distributions bounded in ${\displaystyle [0,1]}$ the inner problem has no closed form and must be solved numerically, which increases the per-step cost.^[12][6]

• Multi-armed bandit
• Upper Confidence Bound
• Confidence interval