On the Problem of Best Arm Retention

Abstract

This paper presents a comprehensive study on the problem of Best Arm Retention (BAR), which requires retaining m arms with the best arm included from n after some trials, in stochastic multi-armed bandit settings. We explore many perspectives of the problem.

• We begin by revisiting the lower bound for the $(\varepsilon ,\delta )$-PAC algorithm for Best Arm Identification (BAI), where we remove the previously imposed restriction of $\delta <0.5$ in the lower bound found in the literature.

• By refining the technique above, we obtain optimal bounds for $(\varepsilon ,\delta )$-PAC algorithms for BAR.

• We further study another variant of the problem, called r-BAR, which has recently found applications in streaming algorithms for multi-armed bandits. The goal of the r-BAR problem is to ensure the expected gap between the best arm and the optimal arm retained is less than r. We prove tight sample complexity for the problem.

• We explore the regret minimization problem for r-BAR and develop algorithm beyond pure exploration. We also propose a conjecture regarding the optimal regret in this setting.

Appendices

A Proof of Lemma 1

Let $T_i(s)$ denote the index of the s-th pull of arm i for $s\le T_i$. Define the log-likelihood , abbreviated as $L_T$ when the context is clear. By applying the chain rule to $L_T$, we have

where the second equality follows from and that $r_t$ is independent of $\mathcal {F}_{t-1}$ conditioned on $a_t$. With , we apply Wald’s Lemma (see e.g. [28]) to to obtain:

(1)

The remaining task is to prove for any event $\mathcal {E}\in \mathcal {F}_T$, we reformulate the definition of $L_T$ as

Summing over all $\omega \in \mathcal {E}$, we obtain

(2)

Continuing to lower bound Eq. (2), we have

where the inequality follows from the Jensen inequality. Rearranging, we get . Similarly, . Hence, we conclude

which completes our proof in conjunction with Eq. (1).

B Bounds of KL Divergence

We will utilize the following inequalities from [31] to bound the KL divergence.

Fact 2

The following inequalities hold.

• (a) $\log (1+x)\ge \frac{x}{1+x}, \forall x>-1$;

• (b) $\log (1+x)\ge \frac{x}{1+x}(1+\frac{x}{2+x})=\frac{2x}{2+x}, \forall x>0$;

• (c) $\log (1+x)\ge \frac{x}{1+x}\frac{2+x}{2}, \text { if } -1<x\le 0$.

Lemma 6

(Restate 2). $\mathfrak {d}(\frac{1-\delta }{2}+\frac{1}{2n},1-\delta )=\varOmega \left( \frac{1-\delta }{2}-\frac{1}{2n}\right)$ if $1-\delta =\frac{1+\varOmega (1)}{n}$.

Proof

By definition,

where the inequality follows from (a) & (b) of Fact 2.

Lemma 7

(Restate Lemma 3). For any $x_1,x_2\dots ,x_n \in [0,1]$ with average $a:=\frac{\sum _{i}x_i}{n}< b\in [0,1]$, then $\sum _{i:x_i<b}\mathfrak {d}(x_i,b)\ge n\cdot \mathfrak {d}(a,b).$

Proof

Recall that $\mathfrak {d}(\cdot ,y)$ is convex for any fixed y in Fact 1. Let $S=\left\{ \,i:x_i<b\,\right\}$ and $k=\left\| S\right\|$. By the convexity of $\mathfrak {d}(\cdot ,b)$, we have $\frac{1}{k}\sum _{i\in S}\mathfrak {d}(x_i,b)\ge \mathfrak {d}\left( \frac{\sum _{i\in S}x_i}{k},b\right) .$ Since $\mathfrak {d}(x,b)>\mathfrak {d}(y,b)$ if $x<y<b$ in Fact 1,

$$\sum _{i\in S}\mathfrak {d}(x_i,b)\ge k\cdot \mathfrak {d}\left( \frac{\sum _{i\in S}x_i}{k},b\right) \ge k\cdot \mathfrak {d}\left( \frac{an-(n-k)b}{k},b\right) .$$

Using the convexity of $\mathfrak {d}(\cdot ,b)$ again, we get

$$\frac{k}{n}\cdot \mathfrak {d}\left( \frac{an-(n-k)b}{k},b\right) +\frac{n-k}{n}\cdot \mathfrak {d}(b,b)\ge \mathfrak {d}(a,b),$$

which implies $k\cdot \mathfrak {d}\left( \frac{an-(n-k)b}{k},b\right) \ge n\cdot \mathfrak {d}(a,b)$ since $\mathfrak {d}(b,b)=0$.

Lemma 8

(Restate Lemma 4). For any $0<a<b<1$, if $\frac{b-a}{a}={\Omega }(1)$, then $\mathfrak {d}(b,a)={\Omega }\left( b\cdot \log \frac{b}{a}\right) .$

Proof

By definition of the KL divergence, $\mathfrak {d}(b,a)=b\log \frac{b}{a}+(1-b)\log \frac{1-b}{1-a}.$

By Fact 2 (b) & (c),

$$b\log \frac{b}{a}=b\log \left( 1+\frac{b-a}{a}\right) \ge (b-a)\left( 1+\frac{(b-a)/a}{2+(b-a)/a}\right) $$

and

$$(1-b)\log \frac{1-b}{1-a}=(1-b)\log \left( 1+\frac{a-b}{1-a}\right) \ge -(b-a)\left( 1-\frac{b-a}{2(1-a)}\right) . $$

Therefore if $r:=\frac{b-a}{a}={\Omega }(1)$,

$$\begin{aligned} \mathfrak {d}(b,a) &= \left( 1-\frac{1}{1+r/(2+r)}\right) b\log \frac{b}{a}+\frac{1}{1+r/(2+r)}b\log \frac{b}{a}+(1-b)\log \frac{1-b}{1-a}\\ &\ge \left( 1-\frac{1}{1+r/(2+r)}\right) b\log \frac{b}{a} +(b-a)-(b-a)\left( 1-\frac{b-a}{2(1-a)}\right) \\ &\ge \left( 1-\frac{1}{1+r/(2+r)}\right) b\log \frac{b}{a}. \end{aligned}$$

C Details of the OSMD Algorithm Corresponding to Proposition 1

For completeness, we provide a description of the OSMD algorithm used in Algorithm 1. For more detailed information, please refer to the work of [21].

Let $\varDelta _{(n-1)}$ denote the probability simplex with $n-1$ dimensions, defined as $\varDelta _{(n-1)}=\left\{ \,\textbf{q}\in \mathbb R_{\ge 0}: \sum _{i=1}^n \textbf{q}(i)=1\,\right\}$. Here, $\textbf{q}(i)$ represents the value at the i-th position of vector $\textbf{q}$. Consider a function $F:\mathbb R^n\rightarrow \mathbb R\cup \left\{ \,\infty \,\right\}$. The Bregman divergence with respect to F is defined as $B_F(\textbf{q},\textbf{p}) = F(\textbf{q})-F(\textbf{p}) - \langle \nabla F(\textbf{p}),\textbf{q}-\textbf{p}\rangle$ for any $\textbf{q},\textbf{p}\in \mathbb R^n$.

The algorithm proposed in [21] is designed for loss cases, where each pull results in a loss associated with the corresponding arm instead of a reward. To adapt their algorithm to our setting, we can perform a simple reduction by constructing the loss of each arm $\ell _t(i)$ as $1-r_t(i)$, where $r_t(i)$ is the reward of arm ${arm}_i$. It is straightforward to verify that the results in [21] also hold for the reward setting. Let $\eta$ be the learning rate and $F:\mathbb R^{\left\| S\right\| }\rightarrow \mathbb R\cup \left\{ \,\infty \,\right\}$ be the potential function, where S is the arm set. Without loss of generality, we index the arms in S by $[\left\| S\right\| ]$.

By choosing $\eta = \sqrt{\frac{8}{L}}$ and $F(\textbf{q}) = -2\sum _{i=1}^{\left\| S\right\| } \sqrt{\textbf{q}(i)}$, the conclusion in Proposition 1 can be directly derived from Theorem 11 in [21].

D Details of the MedianElimination Algorithm Corresponding to Proposition 2

For completeness, we present the description of the MedianElimination algorithm we used in Algorithm 1. For more detailed information, please refer to Theorem 10 of [9].