Perturbed-History Exploration in Stochastic Multi-Armed Bandits

1 Introduction

A multi-armed bandit [Lai and Robbins, 1985; Auer et al., 2002; Lattimore and Szepesvari, 2019] is an online learning problem where actions of the learning agent are represented by arms. After the arm is pulled, the agent receives its stochastic reward. The objective of the agent is to maximize its expected cumulative reward. The agent does not know the mean rewards of the arms in advance and faces the so-called exploration-exploitation dilemma: explore, and learn more about the arm; or exploit, and pull the arm with the highest average reward thus far. The arm may be a treatment in a clinical trial and its reward is the outcome of that treatment on some patient population.

Thompson sampling (TS) [Thompson, 1933; Russo et al., 2018] and optimism in the face of uncertainty (OFU) [Auer et al., 2002; Dani et al., 2008; Abbasi-Yadkori et al., 2011] are the most celebrated and studied exploration strategies in stochastic multi-armed bandits. These strategies are near optimal in multi-armed [Garivier and Cappe, 2011; Agrawal and Goyal, 2013a] and linear [Abbasi-Yadkori et al., 2011; Agrawal and Goyal, 2013b] bandits. However, they typically do not generalize easily to complex problems. For instance, in generalized linear bandits [Filippi et al., 2010], we only know how to construct approximate high-probability confidence sets and posterior distributions. These approximations affect the statistical efficiency of bandit algorithms [Filippi et al., 2010; Zhang et al., 2016; Abeille and Lazaric, 2017; Jun et al., 2017; Li et al., 2017]. In online learning to rank [Radlinski et al., 2008], we only have statistically efficient algorithms for simple user interaction models, such as the cascade model [Kveton et al., 2015; Katariya et al., 2016]. If the model was a general graphical model with latent variables [Chapelle and Zhang, 2009], we would not know how to design a bandit algorithm with regret guarantees. In general, efficient approximations to high-probability confidence sets and posterior distributions are hard to design [Gopalan et al., 2014; Kawale et al., 2015; Lu and Van Roy, 2017; Riquelme et al., 2018; Lipton et al., 2018; Liu et al., 2018].

In this work, we propose a novel exploration strategy that is conceptually straightforward and has the potential to easily generalize to complex problems. In round t, the learning agent adds O(t) i.i.d. pseudo-rewards to its history and treats them as if they were generated by actual arm pulls. Then the agent pulls the arm with the highest average reward in this perturbed history and observes the reward of the pulled arm. The pseudo-rewards are drawn from the same family of distributions as actual rewards, but generate maximum variance randomized data.

Our algorithm, perturbed-history exploration (PHE), is inherently optimistic. To see this, note that the lack of "optimism" regarding arm i in round t, that its estimated mean reward is below the actual mean, is due to a specific history of past O(t) rewards. These rewards are independent noisy realizations of the mean reward of arm i. Therefore, the lack of optimism can be offset by adding O(t) i.i.d. pseudo-rewards to the history of arm i, so that the estimated mean reward of arm i in its perturbed history is above the mean with a high probability. This design is conceptually simple and appealing, because maximum variance rewards can be easily generated for any reward generalization model.

We make the following contributions in this paper. First, we propose PHE, a multi-armed bandit algorithm where the mean rewards of arms are estimated using a mixture of actual rewards and i.i.d. pseudo-rewards. Second, we analyze PHE in a K-armed bandit with [0, 1] rewards, and prove both O(K∆-1 logn) and O(√Kn logn) bounds on its n-round regret, where ∆ is the minimum gap between the mean rewards of the optimal and suboptimal arms. The key to our analysis is a novel argument that shows that randomized Bernoulli rewards lead to optimism. Finally, we empirically compare PHE to several baselines and show that it is competitive with the best of them.

2 Setting

We use the following notation. The set {1, . . . , n} is denoted by [n]. We define Ber(x; p) = px (1 - p)1-x and let Ber(p) be the corresponding Bernoulli distribution. We also define B(x; n, p) = (nx)px (1 - p)n-x and let B(n, p) be the corresponding binomial distribution. For any event E, 1{E} = 1 if and only if event E occurs, and is zero otherwise.

We study the problem of cumulative regret minimization in a stochastic multi-armed bandit. Formally, a stochastic multiarmed bandit [Lai and Robbins, 1985; Auer et al., 2002; Lattimore and Szepesvari, 2019] is an online learning problem where the learning agent sequentially pulls K arms in n rounds. In round t ∈ [n], the agent pulls arm It ∈ [K] and receives its reward. The reward of arm i ∈ [K] in round t, Yi,t, is drawn i.i.d. from a distribution of arm i, Pi, with mean µi and support [0, 1]. The goal of the agent is to maximize its expected cumulative reward in n rounds. The agent does not know the mean rewards of the arms in advance and learns them by pulling the arms.

Without loss of generality, we assume that the first arm is optimal, that is µ1 > maxi>1 µi. Let ∆i = µ1 - µi denote the gap of arm i. Maximization of the expected cumulative reward in n rounds is equivalent to minimizing the expected n-round regret, which we define as

3 Perturbed-History Exploration

Our new algorithm, perturbed-history exploration (PHE), is presented in Algorithm 1. PHE pulls the arm with the highest average reward in its perturbed history, which is estimated as follows. Let Ti,t = ∑tℓ=1 1{Iℓ = i} denote the number of pulls of arm i in the first t rounds and s = Ti,t-1. Then the estimated reward of arm i in round t, ˆµi,t, is the average of its past s rewards and as i.i.d. pseudo-rewards (Zℓ)as ℓ=1 , for some tunable integer a > 0. In line 9, ˆµi,t is computed from the sum of the rewards of arm i after s pulls, Vi,s, and the sum of its pseudo-rewards, Ui,s. After the arm is pulled, the cumulative reward of that arm is updated with its reward in round t (line 17). All arms are initially pulled once (line 11).

PHE can be implemented computationally efficiently, such that its computational cost in round t does not depend on t. The key observation is that the sum of as Bernoulli random variables with mean 1/2 is a sample from a binomial distribution with mean as/2. Therefore, Ui,s ∼ B(as, 1/2).

The perturbation scale a is the only tunable parameter of PHE (line 1), which dictates the number of pseudo-rewards that are added to the perturbed history. Therefore, a controls the trade-off between exploration and exploitation. In particular, higher values of a lead to more exploration. We argue informally below that any a > 1 suffices for sublinear regret. We prove in Section 4 that any a > 2 guarantees it.

Now we examine how exploration emerges within our algorithm. Fix arm i and the number of its pulls s. Let Vi,s be Algorithm 1 Perturbed-history exploration in a multi-armed bandit with [0, 1] rewards

• 1: Inputs: Perturbation scale a

the cumulative reward of arm i after s pulls. Let (Zℓ)as ℓ=1 ∼ Ber(1/2) be as i.i.d. pseudo-rewards and Ui,s = ∑as ℓ=1 Zℓ denote their sum. Then the mean reward of arm i (line 9) is estimated as

This estimator has two key properties that allow us to bound the regret of PHE in Section 4. First, it concentrates at the scaled and shifted mean reward of arm i. More precisely, let ¯Ui,s = E [Ui,s] and ¯ Vi,s = E [Vi,s]. Then we have

where σ2max is the maximum variance of any random variable on [0, 1]. By Popoviciu's inequality on variances [Popoviciu, 1935], we have σ2max = 1/4, which is precisely the variance of Z ∼ Ber(1/2).

Second, ˆµ is sufficiently optimistic in the following sense. Let E = { ¯ Vi,s/s -Vi,s/s = ε} be the event that the estimated mean reward of arm i is below the mean by ε > 0. We say that ˆµ is optimistic if

for any ε > 0 such that P (E) > 0. That is, for any deviation ε > 0, the conditional probability that the randomized mean reward ˆµ is at least as high as E [ˆµ] is higher than the probability of that deviation. Under this condition, PHE explores enough and can escape potentially harmful deviations.

Now we argue informally that (4) holds for a > 1 in PHE. Fix any ε > 0. First, note that

and

The last equality holds because Ui,s - ¯Ui,s is independent of past rewards. Based on the above two inequalities, (4) holds whenP

Finally, if both Vi,s/s and Ui,s/s were normally distributed, (5) would hold if the variance of Vi,s/s was lower than that of Ui,s/s. This is indeed true, since

and a > 1 from our assumption. This concludes our informal argument. We evaluate PHE with a > 1 in Section 5.

4 Analysis

PHE is an instance of general randomized exploration in Section 3 of Kveton et al. [2019b]. So, the regret of PHE can be bounded using their Theorem 1, which we restate below.

Theorem 1. For any (τi)Ki=2 ∈ RK-1 , the expected n-round regret of Algorithm 1 in Kveton et al. [2019b] can be bounded from above as R(n) ≤ ∑Ki=2 ∆i(ai + bi), where

For any arm i and the number of its pulls s ∈ [n] ∪ {0},

is the tail probability that the estimated mean reward of arm i, ˆµ, is at least τ conditioned on the history of the arm after s pulls, Hi,s; where p is the sampling distribution of ˆµ and τ is a tunable parameter. In PHE, the history Hi,s is Vi,s and ˆµ is defined in (1). Following Kveton et al. [2019b], we set τi in Theorem 1 to the average of the scaled and shifted mean rewards of arms 1 and i,

which are defined in (2). This setting leads to the following gap-dependent regret bound.

Theorem 2. For any a > 2, the expected n-round regret of PHE is bounded as

where

Proof. The proof has two parts. In Section 4.2, we prove an upper bound on bi in Theorem 1. In Section 4.3, we prove an upper bound on ai in Theorem 1. Finally, we add these upper bounds for all arms i > 0.

A standard reduction yields a gap-free regret bound.

Theorem 3. For any a > 2, the expected n-round regret of PHE is bounded as

where c is defined in Theorem 2.

Proof. Let A = {i ∈ [K] : ∆i ≥ ε} be the set of arms whose gaps are at least ε > 0. Then by the same argument as in the proof of Theorem 2 and from the definition of A, we have

Now we choose ε = √ 8a(2c + 1)K log n n , which completes the proof.

4.1 Discussion

We derive two regret bounds. The gap-dependent bound in Theorem 2 is O(K∆-1 log n), where ∆ = mini>1 ∆i is the minimum gap, K is the number of arms, and n is the number of rounds. This scaling is considered near optimal in stochastic multi-armed bandits. The gap-free bound in Theorem 3 is O(√Kn logn). This scaling is again near optimal, up to the factor of √log n, in stochastic multi-armed bandits.

A potentially large factor in our bounds is exp[16/(a-2)] in (6). It arises in the lower bound on the probability of a binomial tail (Appendix A) and is likely to be loose. Nevertheless, it is constant in K, ∆, and n; and decreases significantly even for small a. For instance, it is only e4 at a = 6.

4.2 Upper Bound on bi in Theorem 1

Fix arm i > 1. Based on our choices of Hi,s, ˆµ, and τi, we have for s > 0 that

We set Qi,0(τi) = 1, because of the optimistic initialization in line 11 of PHE. We abbreviate Qi,s(τi) as Qi,s.

Fix the number of pulls s and let m = 8a∆-2 i logn. If s ≤ m, we bound P(Qi,s > 1/n) trivially by 1. If s > m, we split our proof based on the event that Vi,s is not much larger than its expectation,

On event E,

where the first inequality is by the definition of event E, the second is by Hoeffding's inequality, and the last is from s > m. On the other hand, event ¯E is unlikely because

where the first inequality is from Hoeffding's inequality, the second is from a > 1, and the last is from s > m. Now we apply the last two inequalities and get

Finally, we chain our upper bounds for all s and get

This completes our proof.

4.3 Upper Bound on ai in Theorem 1

Fix arm i > 1. Based on our choices of H1,s, ˆµ, and τi, we have for s > 0 that

We set Q1,0(τi) = 1, because of the optimistic initialization in line 11 of PHE. We abbreviate Q1,s(τi) as Q1,s, and define Fs = 1/Q1,s - 1.

Fix the number of pulls s and let m = 16a∆-2 i logn. If s = 0, Q1,s = 1 and we obtain E [min {Fs, n}] = 0. Now consider the case of s > 0. If s ≤ m, we apply the upper bound in Theorem 4 in Appendix A and get

where c is defined in (6). Note that a in Theorem 4 plays the role of a/2 in this claim.

If s > m, we split our argument based on the event that V1,s is not much smaller than its expectation,

On event E,

where the first inequality is by the definition of event E, the second is by Hoeffding's inequality, and the last is from s > m. This lower bound yields

for n ≥ 2. On the other hand, event ¯E is unlikely because

where the first inequality is from Hoeffding's inequality, the second is from a > 1, and the last is from s > m. Now we apply the last two inequalities and get

Finally, we chain our upper bounds for all s and get

This completes our proof.

5 Experiments

We compare PHE to five baselines: UCB1 [Auer et al., 2002], KL-UCB [Garivier and Cappe, 2011], Bernoulli TS [Agrawal and Goyal, 2013a] with a Beta(1, 1) prior, Giro [Kveton et al., 2019b], and FPL [Neu and Bartok, 2013]. The baselines are chosen for the following reasons. KL-UCB and TS are statistically near-optimal in Bernoulli bandits. We implement them with [0, 1] rewards as follows. For any observed reward Yi,t ∈ [0, 1], we draw ˆ Yi,t ∼ Ber(Yi,t) and then use it instead of Yi,t [Agrawal and Goyal, 2013a]. Giro is chosen because it explores similarly to PHE, by adding pseudo-rewards to its history (Section 6). We implement it with a = 1, as analyzed in Kveton et al. [2019b]. FPL is chosen because it perturbs the estimates of mean rewards similarly to PHE (Section 6). We implement it with geometric resampling and exponential noise, as described in Neu and Bartok [2013].

We experiment with three settings of perturbation scales a in PHE: 2.1, 1.1, and 0.5. The first value is greater than 2 and is formally justified in Section 4. The second value is greater than 1 and is informally justified in Section 3. The last value is used to illustrate that the regret of PHE can be linear when PHE is not parameterized properly.

To run PHE with a non-integer perturbation scale a, we replace as in PHE with ⌈as⌉. The analysis of PHE in Section 4 can be extended to this setting. We also experimented with a = 1 and a = 2. We do not report these results because they are similar to those at a = 1.1 and a = 2.1.

5.1 Comparison to Baselines

In the first experiment, we evaluate PHE on two classes of the bandit problems in Kveton et al. [2019b]. The first class is a Bernoulli bandit where Pi = Ber(µi). The second class is a beta bandit where Pi = Beta(vµi, v(1 - µi)) and v = 4. We experiment with 100 randomly chosen problems in each class. Each problem has K = 10 arms and the mean rewards of these arms are chosen uniformly at random from interval [0.25, 0.75]. The horizon is n = 10000 rounds.

Our results are reported in Figures 1a and 1b. We observe that PHE with a > 1 outperforms four of our baselines: UCB1, KL-UCB, Giro, and FPL. This is unexpected, since the design of PHE is conceptually simple; and neither requires nor uses confidence intervals or posteriors. PHE becomes competitive with TS at a = 1.1. Note that the regret of PHE is linear in the Bernoulli bandit at a = 0.5. This shows that our suggestions for setting the perturbation scale a are reasonably tight.

5.2 Computational Cost

In the second experiment, we compare the run times of three randomized algorithms: TS, which samples from a beta posterior; Giro, which bootstraps from a history with pseudorewards; and PHE, which samples pseudo-rewards from a binomial distribution. The number of arms is between 5 and 20, and the horizon is up to n = 10000 rounds.

Our results are reported in Figure 1c. In all settings, the run time of PHE is comparable to that of TS. The run time of Giro is an order of magnitude higher. The reason is that the computational cost of bootstrapping grows linearly with the number of past observations.

6 RelatedWork

Our algorithm design bears a similarity to three existing designs, which we discuss in detail below.

Giro is a bandit algorithm where the mean reward of the arm is estimated by its average reward in a bootstrap sample of its history with pseudo-rewards [Kveton et al., 2019b]. The algorithm has a provably sublinear regret in a Bernoulli bandit. PHE improves over Giro in three respects. First, its design is simpler, because PHE merely adds random pseudorewards and does not bootstrap. Second, PHE has a sublinear regret in any K-armed bandit with [0, 1] rewards. Third, PHE is computationally efficient beyond a Bernoulli bandit. We discuss this in Section 3.

Our work is also closely related to posterior sampling. In particular, let µ ∼ N(µ0, σ2 ) and (Yℓ)sℓ=1 ∼ N(µ, σ2 ) be s i.i.d. noisy observations of µ. Then the posterior distribution of µ conditioned on (Yℓ)sℓ=1 is

A sample from this distribution can be also drawn as follows. First, draw s + 1 i.i.d. samples (Zℓ)sℓ=0 ∼ N(0, σ2 ). Then

is a sample from (7). Unfortunately, the above equivalence holds only for normal random variables. Therefore, it cannot justify PHE as a form of Thompson sampling. Nevertheless, the scale of the perturbation is similar to (1), which suggests that PHE is sound.

Follow the perturbed leader (FPL) [Hannan, 1957; Kalai and Vempala, 2005] is an algorithm design where the learning agent pulls the arm with the lowest perturbed cumulative cost. In our notation, It = argmin i∈[K] ˜ Vi,t-1 + ˜Ui,t, where ˜ Vi,t-1 is the cumulative cost of arm i in the first t - 1 rounds and ˜Ui,t is the perturbation of arm i in round t. PHE differs from FPL in three respects. First, ˜Ui,t = O(√n) in FPL. In PHE, the noise in round t adapts to the number of arm pulls, because Ui,Ti,t-1 = O(Ti,t-1). Second, FPL has been traditionally studied in the non-stochastic full-information setting. In comparison, PHE is designed for the stochastic bandit setting. Neu and Bartok [2013] extended FPL to the bandit setting using geometric resampling and we compare to their algorithm in Section 5. Finally, all existing FPL analyses derive gap-free regret bounds. We derive a gap-dependent regret bound.

7 Conclusions

We propose a new online algorithm, PHE, for cumulative regret minimization in stochastic multi-armed bandits. The key idea in PHE is to add O(t) i.i.d. pseudo-rewards to the history in round t and then pull the arm with the highest average reward in this perturbed history. The pseudo-rewards are drawn from the maximum variance distribution. We derive O(K∆-1 log n) and O(√Kn log n) bounds on the n-round regret of PHE, where K is the number of arms and ∆ is the minimum gap between the mean rewards of the optimal and suboptimal arms. This result is unexpected, since the design of PHE is conceptually simple. We empirically compare PHE to several baselines and show that it is competitive with the best of them.

PHE can be easily adapted to any reward distributions with a bounded support. If Yi,t ∈ [m,M], Yi,t in line 17 of PHE should be replaced with (Yi,t - m)/(M - m).

PHE can be applied to structured problems, such as generalized linear bandits [Filippi et al., 2010], as follows. Let xi be the feature vector of arm i. Then ((xIℓ , YIℓ,ℓ))t-1 ℓ=1 is the history in round t and a natural choice for the pseudo-history is ((xIℓ , Zj,ℓ))j∈[a], ℓ∈[t-1], where Zj,ℓ ∼ Ber(1/2) are i.i.d. random variables. In round t, the learning agent fits a reward generalization model to a mixture of both histories and pulls the arm with the highest estimated reward in that model. We leave the analysis and empirical evaluation of this algorithm for future work. The algorithm was analyzed in a linear bandit in Kveton et al. [2019a].

We believe that PHE can be extended to other perturbation schemes. For instance, since var [Vi,s] ≤ s/4, it is plausible that any s i.i.d. pseudo-rewards with a comparable variance, such as (Zℓ)sℓ=1 ∼ N(0, 1/4), would lead to optimism. We leave the analyses of such designs for future work.

A Technical Lemmas

Fix arm i and the number of its pulls n. Let X be the cumulative reward of arm i after n pulls and Y = ∑2an ℓ=1 Zℓ be the sum of 2an i.i.d. pseudo-rewards (Zℓ)2an ℓ=1 ∼ Ber(1/2). Note that both X and Y are random variables. Let ¯X = E [X] and ¯ Y = E [Y ]. Our main theorem is stated and proved below.

Theorem 4. For any a > 1,

Proof. Let W = E [1/P (Y ≥ ¯X -X + ¯ Y ∣∣X)]. Note that W can be rewritten as W = E [f(X)], where

and m = 2an. This follows from the definition of Y and that ¯ Y = an.

Note that f(X) decreases in X, as required by Lemma 1, because the probability of observing at least ⌈ ¯X -X + an⌉ ones increases with X and f(X) is its reciprocal. So we can apply Lemma 1 and get

where i0 is the smallest integer such that (i0 + 1)√n ≥ ¯X, as defined in Lemma 1.

Now we bound the sums in the reciprocals from below using Lemma 2. For δ = (i + 1)√n,

where the last inequality is from the definition of i0. Then we chain the above three inequalities and get

Now note that

It follows that

This concludes our proof.

Lemma 1. Let f(X) be a non-negative decreasing function of random variable X in Theorem 4 and i0 be the smallest integer such that (i0 + 1)√n ≥ ¯X. Then

Proof. Let

for i ∈ [i0]∪{0}. Then {Pi}i0 i=0 is a partition of [0, n]. Based on this observation,

where the inequality holds because f(x) is a decreasing function of x. Now fix i > 0. Then from the definition of Pi and Hoeffding's inequality, we have

Trivially, P (X ∈ P0) ≤ 1 = exp[-2 · 02 ]. Finally, we chain all inequalities and get our claim.

Lemma 2. Let m = 2an. Then for any δ ∈ [0, an],

Proof. By Lemma 4 in Appendix of Kveton et al. [2019b],

Also note that

for any y ∈ [0,m]. Now we combine the above two inequalities and get

Finally, we note the following. First, the above lower bound decreases in y for y ≥ an + δ, since δ ≥ 0. Second, by the pigeonhole principle, there are at least ⌊√n⌋ integers between an + δ and an + δ + √n, starting with ⌈an + δ⌉. This leads to the following lower bound

The last inequality is by ⌊√n⌋ /√n ≥ 1/2, which holds for n ≥ 1. This concludes our proof.