In multi-armed bandit problems, KL-UCB (for Kullback–Leibler Upper Confidence Bound) is a UCB-type algorithm that is asymptotically optimal, in the sense that its regret matches the problem-dependent Lai-Robbins lower bound.
Multi-armed bandit problem The Multi-armed bandit problem is a sequential game where one player has to choose at each turn between K {\displaystyle K} actions (arms). Behind every arm a {\displaystyle a} there is an unknown distribution ν a {\displaystyle \nu _{a}} that lies in a set D {\displaystyle {\mathcal {D}}} known by the player (for example, D {\displaystyle {\mathcal {D}}} can be the set of Gaussian distributions or Bernoulli distributions). At each turn t {\displaystyle t} the player chooses (pulls) an arm a t {\displaystyle a_{t}} , he then gets an observation X t {\displaystyle X_{t}} of the distribution ν a t {\displaystyle \nu _{a_{t}}} .
Regret minimization The goal is to minimize the regret at time T {\displaystyle T} that is defined as
R T := ∑ a = 1 K Δ a E [ N a ( T ) ] {\displaystyle R_{T}:=\sum _{a=1}^{K}\Delta _{a}\mathbb {E} [N_{a}(T)]}
where
μ a := E [ ν a ] {\displaystyle \mu _{a}:=\mathbb {E} [\nu _{a}]} is the mean of arm a {\displaystyle a}
μ ∗ := max a μ a {\displaystyle \mu ^{*}:=\max _{a}\mu _{a}} is the highest mean
Δ a := μ ∗ − μ a {\displaystyle \Delta _{a}:=\mu ^{*}-\mu _{a}}
N a ( t ) {\displaystyle N_{a}(t)} is the number of pulls of arm a {\displaystyle a} up to turn t {\displaystyle t}
The player has to find an algorithm that chooses at each turn t {\displaystyle t} which arm to pull based on the previous actions and observations ( a s , X s ) s < t {\displaystyle (a_{s},X_{s})_{s<t}} to minimize the regret R T {\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.
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 {\displaystyle t} we compute an upper confidence bound (UCB) for the mean of each arm a {\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 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
At first, the algorithm pulls all the arms once. Then, for each turn t ≥ K + 1 {\displaystyle t\geq K+1} , for each arm a {\displaystyle a} , we compute:
… excerpt ends here. Continue reading the full article.
