Lai-Robbins lower bound

The Lai-Robbins lower bound gives an asymptotic lower bound on the regret that any uniformly good algorithm must incur in the stochastic multi-armed bandit problem. The original result was proved by Tze Leung Lai and Herbert Robbins in 1985 for parametric exponential families. Later work extended the statement to more general classes of distributions.

Multi-armed bandit problem

The multi-armed bandit problem (MAB) is a sequential game in which the player must trade off exploration (to learn) and exploitation (to earn).

The player chooses among $K$ actions (arms) with unknown distributions $\nu =({\nu }_1,\dots ,{\nu }_K)$. The player is assumed to know a class of distributions ${𝒟}$ such that for every $k$ one has ${\nu }_k\in {𝒟}$ (for example, ${𝒟}$ may be the family of Gaussian or Bernoulli distributions).

At each round $t=1,\dots ,T$ the player selects (pulls) an arm $a_t$ and observes a reward $X_t\sim {\nu }_{a_t}$.

We denote

• $N_a(t):=\sum _{s=1}^t{\mathbf{𝟏}}_{\{a_s=a\}}$ the number of times arm $a$ has been pulled in the first $t$ rounds,
• $\mu (\nu ):=({\mu }_1,\dots ,{\mu }_K)$ the vector of arm means, where ${\mu }_k={\mathbb{𝔼}}_{X\sim {\nu }_k}[X]$,
• ${\mu }^{*}:=\underset{a}{\max }{\mu }_a$ the highest mean
• ${\mathrm{\Delta }}_a:={\mu }^{*}-{\mu }_a\ge 0$ the gap of arm $a$.

An arm $a$ with ${\mu }_a={\mu }^{*}$ is called an optimal arm; otherwise it is a suboptimal arm.

The goal is to minimize the regret at horizon $T$, defined by

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

Intuitively, the regret is the (expected) total loss compared to always playing an optimal arm:

$\text{regret}=\sum _a(\text{cost of playing }a)\times (\text{times }a\text{ is played}).$

An MAB algorithm is a (possibly randomized) policy $\pi$ that, at each round $t$, maps the history $(a_s,X_s{)}_{s<t}$ to a distribution over the next action $a_t$.

Intuitive example

Suppose a farmer must choose, each year, one of $K$ seed varieties to plant. Each variety $k$ has an unknown average yield ${\mu }_k$. If the farmer knew the best variety (with mean ${\mu }^{*}$) he would plant it every year; in reality he must try varieties to learn which is best. The cumulative regret after $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.
2. One may consider a fixed-horizon setting (known $T$) or an anytime setting (unknown $T$).

Lai-Robbins lower bound

The theorem gives the right amount of time we should pull a suboptimal arm $k$ to distinguish whether we are in the instance with ${\nu }_k$ or with ${\tilde{\nu }}_k$ where ${\tilde{\nu }}_k$ is such that ${\tilde{\mu }}_k>{\mu }^{*}$.

Knowning a lower bound on the number of pull of every suboptimal arm gives a lower bound on the regret as only suboptimal arms contribute to the regret.

Before stating the formal theorem we need to define what is a consistent algorithm.

Consistency (uniformly good algorithms)

Let ${𝒟}$ be a class of probability distributions and consider $K$ arms with reward distributions $\nu =({\nu }_1,\dots ,{\nu }_K)\in {{𝒟}}^K$. An algorithm $\pi$ is said to be consistent (also called uniformly good) on ${{𝒟}}^K$ if, for every instance $\nu \in {{𝒟}}^K$, the expected regret $R_T(\nu )$ grows subpolynomially:

$\mathrm{\forall }\alpha >0,R_T(\nu )=o(T^{\alpha })\text{as }T\to \mathrm{\infty }$

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

Formal lower bound

Regret divided by ln of 3 algorithms : IMED, KL-UCB, DMED

For any suboptimal arm $a$. For a distribution ${\nu }_a\in {𝒟}$ and a threshold $x$, define

${{𝒦}}_{\inf }({\nu }_a,x,{𝒟}):=\inf \{\mathrm{KL}({\nu }_a,{\nu }^{\prime }):{\nu }^{\prime }\in {𝒟},{\mu }^{\prime }>x\}$

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

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

${\mathbb{𝔼}}_{\nu }[N_a(T)]\ge \frac{\ln T}{{{𝒦}}_{\inf }({\nu }_a,{\mu }^{*},{𝒟})}+o(\ln T)$

Consequently, the regret satisfies

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

The original 1985 paper established this result for exponential families; later work showed that the bound holds under much weaker assumptions on ${𝒟}$.

Intuition

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

Sketch of proof

The proof relies on a change-of-measure argument. Fix a suboptimal arm $k$ and consider an alternative instance $\tilde{\nu }$ that coincides with $\nu$ on all arms except $k$, and such that arm $k$ becomes optimal under $\tilde{\nu }$. If the algorithm does not sample arm $k$ sufficiently often, then the observation processes induced by $\nu$ and $\tilde{\nu }$ are statistically hard to distinguish, although the algorithm must behave differently in the two instances because of consistency combined with having different optimal arms. Using information-theoretic equalities, one can show that $\mathrm{KL}({\mathbb{\mathbb{P}}}_{\nu }^{I_T},{\mathbb{\mathbb{P}}}_{\tilde{\nu }}^{I_T})=\sum _{a=1}^K{\mathbb{𝔼}}_{\nu }[N_a(T)]\mathrm{KL}({\nu }_a,{\tilde{\nu }}_a)$ where $I_T:=(A_1,X_1,\dots ,A_T,X_T)$ denotes the sequence of actions and observations up to time $T$. Since $\nu$ and $\tilde{\nu }$ differ only on arm $k$, this reduces to ${\mathbb{𝔼}}_{\nu }[N_k(T)]\mathrm{KL}({\nu }_k,{\tilde{\nu }}_k)$ On the other hand, using information-theoretic inequalities one can show $\mathrm{KL}({\mathbb{\mathbb{P}}}_{\nu }^{I_T},{\mathbb{\mathbb{P}}}_{\tilde{\nu }}^{I_T})\ge \mathrm{KL}(\mathrm{Ber}\left(\frac{E_{\nu }[N_k(T)]}{T}\right),\mathrm{Ber}\left(\frac{E_{\tilde{\nu }}[N_k(T)]}{T}\right))$ As $k$ is not optimal under $\nu$, consistency implies that for all $\alpha >0$, $\frac{E_{\nu }[N_k(T)]}{T}=o(T^{\alpha -1})$, while $\frac{E_{\tilde{\nu }}[N_k(T)]}{T}\to 1$ since $k$ is optimal for $\tilde{\nu }$. Letting $\alpha \to 0$ yields $\mathrm{KL}(\mathrm{Ber}\left(\frac{E_{\nu }[N_k(T)]}{T}\right),\mathrm{Ber}\left(\frac{E_{\tilde{\nu }}[N_k(T)]}{T}\right))\simeq \ln T$ Combining this inequality with the previous equality gives ${\mathbb{𝔼}}_{\nu }[N_k(T)]\mathrm{KL}({\nu }_k,{\tilde{\nu }}_k)\gtrsim \ln T$ Minimizing over all alternatives ${\tilde{\nu }}_k$ such that ${\tilde{\mu }}_k>{\mu }^{*}$ yields the lower bound in terms of ${{𝒦}}_{\inf }({\nu }_k,{\mu }^{*},{𝒟})$.

Algorithms achieving the Lai-Robbins lower bound

Several algorithms are known to achieve the Lai-Robbins asymptotic lower bound under specific assumptions on the reward distribution class ${𝒟}$. The following list summarizes a non-exhaustive list of algorithms mathing the lower bound.

Non-exhaustive list of algorithms achieving the lower bound under various distributional assumptions

Distribution class ${𝒟}$	Algorithms
Gaussian rewards (known variance)	KL-UCB, TS, AdaUCB, KL-UCB-switch, RB-SDA
Gaussian rewards	CHK
One-dimensional exponential families	KL-UCB
Bounded rewards ${𝒫}([0,1])$	KL-UCB, IMED, Fast-IMED, DMED, NPTS

Extension to structured families

In structured bandit problems, the vector of means $\mu =({\mu }_1,\dots ,{\mu }_K)$ is known to belong to a given set ${𝒮}\subset {\mathbb{ℝ}}^K$. Define the set of admissible instances

$G_{{𝒟},{𝒮}}:=\{\nu \in {{𝒟}}^K:\mu (\nu )\in {𝒮}\}$

For an instance $\nu \in G_{{𝒟},{𝒮}}$, let

$a^{*}(\nu ):=\arg \underset{a}{\max }{\mu }_a(\nu )$

denote the set of optimal arms.

Define the set of alternative instances

$B_{{𝒟},{𝒮}}(\nu ):=\{\tilde{\nu }\in G_{{𝒟},{𝒮}}:a^{*}(\tilde{\nu })\cap a^{*}(\nu )=\varnothing \text{ and }\mathrm{\forall }a\in a^{*}(\nu ),{\tilde{\nu }}_a={\nu }_a\}$

Then, for any algorithm consistent on $G_{{𝒟},{𝒮}}$, the regret satisfies, for every $\nu \in G_{{𝒟},{𝒮}}$,

$R_T(\nu )\ge C_{{𝒟},{𝒮}}^{*}(\nu )\ln T+o(\ln T)$

where $C_{{𝒟},{𝒮}}^{*}(\nu )$ is defined as the solution of

$\begin{array}{l}{C}_{{𝒟},{𝒮}}^{*}(\nu ):=\underset{(c_a{)}_{a\notin a^{*}(\nu )}}{\min }\sum _{a\notin a^{*}(\nu )}{\mathrm{\Delta }}_a{c}_a\\ \text{s.t.}{c}_a\ge 0\mathrm{\forall }a\notin a^{*}(\nu ),\\ \mathrm{\forall }\tilde{\nu }\in B_{{𝒟},{𝒮}}(\nu ),\sum _{a\notin a^{*}(\nu )}{c}_a\mathrm{KL}({\nu }_a,{\tilde{\nu }}_a)\ge 1.\end{array}$

Extension to other problems

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 $1-\delta$ using as few rounds as possible.

Reinforcement Learning (RL)

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

See also

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

References

This article "Lai-Robbins lower bound" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Lai-Robbins lower bound. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---