Kullback–Leibler Upper Confidence Bound

Short description: Asymptotically optimal algorithm for a decision theory problem

Behaviour of an UCB algorithm on a bandit run

In multi-armed bandit problems, KL-UCB (for Kullback–Leibler Upper Confidence Bound) 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.

Multi-armed bandit problem

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

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

Regret minimization

The goal is to minimize the regret at time $T$ that is defined as

$R_T:=\sum _{a=1}^K{\mathrm{\Delta }}_a\mathbb{𝔼}[N_a(T)]$

where

• ${\mu }_a:=\mathbb{𝔼}[{\nu }_a]$ is the mean of arm $a$
• ${\mu }^{*}:=\underset{a}{\max }{\mu }_a$ is the highest mean
• ${\mathrm{\Delta }}_a:={\mu }^{*}-{\mu }_a$
• $N_a(t)$ is the number of pulls of arm $a$ up to turn $t$
  

The player has to find an algorithm that chooses at each turn $t$ which arm to pull based on the previous actions and observations $(a_s,X_s{)}_{s<t}$ to minimize the regret $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.

Applications

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

Algorithm KL-UCB

The algorithm is a UCB-type algorithm based on optimism, which means that at each turn $t$ we compute an upper confidence bound (UCB) for the mean of each arm $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 to make the upper confidence bound.

History

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

Formal algorithm

The index of an arm a at turn t for KL UCB

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

$U_a(t):=\max \{\mu |N_a(t){{𝒦}}_{inf}({\hat{\nu }}_a(t),\mu ,{𝒟})\le {\delta }_t\}$

where

• ${{𝒦}}_{inf}(\nu ,\mu ,{𝒟}):=\inf \{\mathrm{K}\mathrm{L}(\nu ,\tilde{\nu })|\tilde{\nu }\in {𝒟},\mathbb{𝔼}[\tilde{\nu }]>\mu \}$
• $\mathrm{K}\mathrm{L}$ is the Kullback–Leibler divergence
• ${\hat{\nu }}_a(t)$ is the empirical distribution of arm $a$ at turn $t$
• ${\delta }_t$ is a well-chosen sequence of positive numbers, often equal to $\ln t+c\ln \ln t$ with $c>0$.

Then we choose the arm $a_t$ with the highest index:

$a_t:=\arg \underset{a}{\max }{U}_a(t)$

We note that the algorithm does not require knowledge of $T$.

Example

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

$U_a(t)={\hat{\mu }}_a(t)+\sqrt{\frac{2{\sigma }^2{\delta }_t}{N_a(t)}}$

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

Pseudocode

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)

Theoretical results

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

Lai–Robbins lower bound

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

It states that for every consistent algorithm on the set ${𝒟}$ — that is, an algorithm for which, for every $({\nu }_1,\dots ,{\nu }_K)\in {{𝒟}}^K$, the regret $R_T$ is subpolynomial (i.e. $R_T=o_{T\to +\mathrm{\infty }}(T^{\alpha })$ for all $\alpha >0$) — we have:

$R_T\ge \left(\sum _{a:{\mu }_a<{\mu }^{*}}\frac{{\mathrm{\Delta }}_a}{{{𝒦}}_{\inf }({\nu }_a,{\mu }^{*},{𝒟})}\right)\ln T+o_{T\to +\mathrm{\infty }}(\ln T).$

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

Regret bound for KL-UCB

The algorithm matches the Lai–Robbins lower bound for one-dimensional exponential-family distributions and for distributions bounded in $[0,1]$.

One-dimensional exponential family

For ${𝒟}$ being the set of one-dimensional exponential families, with ${\delta }_t:=\ln t+3\ln \ln t$ we have the following upper bound on the regret of KL-UCB:

$R_T\le \left(\sum _{a:{\mu }_a<{\mu }^{*}}\frac{{\mathrm{\Delta }}_a}{{{𝒦}}_{\inf }({\nu }_a,{\mu }^{*},{𝒟})}\right)\ln T+O_T(\sqrt{\ln T}).$

Bounded distributions in [0,1]

For ${𝒟}={𝒫}([0,1])$ (the set of distributions supported on $[0,1]$), and for ${\delta }_t:=\ln t+\ln \ln t$, we have the following upper bound on the regret of KL-UCB:

$R_T\le \left(\sum _{a:{\mu }_a<{\mu }^{*}}\frac{{\mathrm{\Delta }}_a}{{{𝒦}}_{\inf }({\nu }_a,{\mu }^{*},{𝒟})}\right)\ln T+O_T((\ln T{)}^{4/5}\ln \ln T).$

Runtime

For ${𝒟}={𝒫}([0,1])$, the runtime needed per step and for an arm $k$ with $n$ observations is ${𝒪}(n(\ln n{)}^2)$. This is higher than that of other optimal algorithms, such as NPTS with ${𝒪}(n)$. MED with ${𝒪}(n\ln n)$. and IMED with ${𝒪}(n\ln n)$.

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

See also

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