Lai–Robbins lower bound

Intuitive example

Suppose a farmer must choose, each year, one of ${\displaystyle K}$ seed varieties to plant. Each variety ${\displaystyle k}$ has an unknown average yield ${\displaystyle \mu _{k}}$. If the farmer knew the best variety (with mean ${\displaystyle \mu ^{*}}$) he would plant it every year; in reality he must try varieties to learn which is best. The cumulative regret after ${\displaystyle T}$ years measures the total expected loss in yield due to imperfect knowledge.

Remarks

1. The model above is the stochastic MAB; there also exist adversarial variants.^[3]
2. One may consider a fixed-horizon setting (known ${\displaystyle T}$) or an anytime setting (unknown ${\displaystyle T}$).

Consistency (uniformly good algorithms)

Let ${\displaystyle {\mathcal {D}}}$ be a class of probability distributions and consider ${\displaystyle K}$ arms with reward distributions ${\displaystyle \nu =(\nu _{1},\dots ,\nu _{K})\in {\mathcal {D}}^{K}}$. An algorithm is said to be consistent (also called uniformly good) on ${\displaystyle {\mathcal {D}}^{K}}$ if, for every instance ${\displaystyle \nu \in {\mathcal {D}}^{K}}$, the expected regret ${\displaystyle R_{T}(\nu )}$ grows subpolynomially:

${\displaystyle \forall \alpha >0,\qquad R_{T}(\nu )=o(T^{\alpha })\quad {\text{as }}T\to \infty }$

This assumption excludes algorithms that perform well on some instances but incur linear regret on others.

Formal lower bound

For any suboptimal arm ${\displaystyle a}$. For a distribution ${\displaystyle \nu _{a}\in {\mathcal {D}}}$ and a threshold ${\displaystyle x}$, define

${\displaystyle {\mathcal {K}}_{\inf }(\nu _{a},x,{\mathcal {D}}):=\inf {\Bigl \{}\operatorname {KL} (\nu _{a},\nu '):\nu '\in {\mathcal {D}},\ \mu '>x{\Bigr \}}}$

where ${\displaystyle \operatorname {KL} (\cdot ,\cdot )}$ denotes the Kullback-Leibler divergence.

Then, for any algorithm consistent on ${\displaystyle {\mathcal {D}}^{K}}$ and for every instance ${\displaystyle \nu \in {\mathcal {D}}^{K}}$, every suboptimal arm ${\displaystyle a}$ satisfies

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

Consequently, the regret satisfies

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

The original 1985 paper^[1] established this result for exponential families; later work showed that the bound holds under much weaker assumptions on ${\displaystyle {\mathcal {D}}}$.

Intuition

Consistency imposes that, for every ${\displaystyle \nu }$, the number of pulls of an optimal arm must be large. This means that ${\displaystyle \mu ^{*}}$ is estimated very accurately. The goal is to determine, for a suboptimal arm ${\displaystyle k}$, how many samples are needed to be confident, with the appropriate level of confidence, that ${\displaystyle \mu _{k}<\mu ^{*}}$. To do so, we use what is called the most confusing instance: an instance close to ${\displaystyle \nu }$ such that arm ${\displaystyle k}$ is optimal. We define it as ${\displaystyle {\tilde {\nu }}}$ such that, for all ${\displaystyle a\neq k}$, ${\displaystyle {\tilde {\nu }}_{a}=\nu _{a}}$, and ${\displaystyle {\tilde {\nu }}_{k}}$ is chosen so that ${\displaystyle {\tilde {\mu }}_{k}>\mu ^{*}}$. The objective is to determine how many samples of arm ${\displaystyle k}$ are required to distinguish whether we are in the instance with ${\displaystyle \nu _{k}}$ or with ${\displaystyle {\tilde {\nu }}_{k}}$ in terms of ${\displaystyle \operatorname {KL} }$ distance.

Structured bandit

A more complexe is structured bandit where we know that the mean of each arm is in a set with some restriction. In this case we can prove a smaller lower bound that use the knowledge of this set.^[14][15]

Best arm identification (BAI)

A similar result has been proved for best arm identification, which is the same game except that, instead of minimizing the regret, the goal is to identify the best arm with probability ${\displaystyle 1-\delta }$ using as few rounds as possible.^[16]

Reinforcement Learning (RL)

Similar results have been proved for regret minimization in average-reward reinforcement learning. The order is also ${\displaystyle \ln T}$, with a constant that depends on the problem.^[17]