Submission declined on 26 December 2025 by Fermiboson (talk). This submission provides insufficient context for those unfamiliar with the subject matter. Please see the guide to writing better articles for information on how to better format your submission. If you would like to continue working on the submission, click on the "Edit" tab at the top of the window. If you have not resolved the issues listed above, your draft will be declined again and potentially deleted. If you need extra help, please ask us a question at the AfC Help Desk or get live help from experienced editors. Please do not remove reviewer comments or this notice until the submission is accepted. Where to get help If you need help editing or submitting your draft, please ask us a question at the AfC Help Desk or get live help from experienced editors. These venues are only for help with editing and the submission process, not to get reviews. If you need feedback on your draft, or if the review is taking a lot of time, you can try asking for help on the talk page of a relevant WikiProject. Some WikiProjects are more active than others so a speedy reply is not guaranteed. How to improve a draft Wikipedia:Contributing to Wikipedia – a basic overview on how to edit Wikipedia. Help:Wikitext – how to use the markup Help:Referencing for beginners – how to include references Wikipedia:Article development – how to develop your article Wikipedia:Writing better articles – how to improve your article Wikipedia:Verifiability – make sure your article includes reliable third-party sources You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Add tags to your draft Editor resources Easy tools: Citation bot (help) | Advanced: Fix bare URLs Declined by Fermiboson 32 hours ago. Last edited by Fermiboson 32 hours ago. Reviewer: Inform author. Resubmit Please note that if the issues are not fixed, the draft will be declined again.

• Comment: Ordinary spelling and grammar mistakes aside (please copyedit), it is unclear to me 1) what is the formulation of the problem the algorithm is trying to solve and 2) what is the final computed quantity of the algorithm. You might also want to spend some effort explaining what regret minimisation is, and as with all optimisation algorithms, give a full formulation in terms of the objective function, optimising variable and the form of any constraints. Also, the title of the draft should be the full name of the algorithm and not an acronym. Fermiboson (talk) 13:01, 26 December 2025 (UTC)

• Comment: In accordance with Wikipedia's Conflict of interest guideline, I disclose that I have a conflict of interest regarding the subject of this article. Adrien PREVOST (talk) 20:14, 25 December 2025 (UTC)

In Multi-armed bandit problems, KL-UCB (Kullback-Leiber divergence - Upper Confidence Bound)^[1] is an UCB-type algorithm that matches the asymptotic lower bound of Lai-Robbins^[2] that is a problem-dependent lower bound for regret minimization.

The algorithm was first introduced in 2011 for Bernoulli distribution^[1]. It was then extent for one-dimensional exponential families and bounded distributions in 2013 ^[3] . An adaptation called KL-UCB-Switch that uses a mix of MOSS and KL-UCB was made to obtain both the problem-dependent and problem-independent asymptotic lower bound in 2022. ^[4]. The algorithm was also extended to Lipschitz bandits in 2014 ^[5]

It is a UCB-type algorithm based on optimism, which means that we pull the arm with the highest Upper Confidence Bound (UCB). This algorithm compute the UCB using the Kullback-Leibler divergence.

In multi-armed bandit problem where each arm distributions ${\displaystyle \nu _{k}}$ are in a known set ${\displaystyle {\mathcal {D}}}$, we compute at each turn ${\displaystyle t}$, for each arm ${\displaystyle a}$ the index^[3]

${\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 N_{a}(t)}$ is the number of pulls of the arm ${\displaystyle a}$ up to turn ${\displaystyle t}$
• ${\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 {\hat {\nu }}_{a}(t)}$ is the empirical distribution of the 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}$.^[3]

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

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

${\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 the arm ${\displaystyle a}$ at turn ${\displaystyle t}$.

For ${\displaystyle {\mathcal {D}}}$ being a one-dimensional exponential family, with ${\displaystyle \delta _{t}:=\ln t+3\ln \ln t}$ we have for each sub-optimal arm ${\displaystyle a}$^[3]

${\displaystyle \mathbb {E} [N_{a}(T)]\leq {\frac {1}{{\mathcal {K}}_{\inf }(\nu _{a},\mu ^{*},{\mathcal {D}})}}\ln T+O({\sqrt {\ln T}})}$

where ${\displaystyle \mu ^{*}}$ is the highest mean. We can see that the algorithm matches the optimal problem-dependent lower bound of Lai-Robbins.^[2]

For ${\displaystyle {\mathcal {D}}:={\mathcal {P}}([0,1])}$ the distributions bounded in ${\displaystyle [0,1]}$, for ${\displaystyle \delta _{t}:=\ln t+\ln \ln t}$ we have for each sub-optimal arm ${\displaystyle a}$^[3]

${\displaystyle \mathbb {E} [N_{a}(T)]\leq {\frac {1}{{\mathcal {K}}_{\inf }(\nu _{a},\mu ^{*},{\mathcal {P}}([0,1]))}}\ln T+O((\ln T)^{4/5}\ln \ln T)}$

The algorithm also matches the problem-dependant lower bound.

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}}(n(\ln n)^{2})}$^[6], which is higher than that of other optimal algorithms, such as NPTS^[7] with ${\displaystyle {\mathcal {O}}(n)}$^[6], MED^[8] with ${\displaystyle {\mathcal {O}}(n\ln n)}$^[6], and IMED^[9] with ${\displaystyle {\mathcal {O}}(n\ln n)}$.^[6]

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