Regret Bounds and Reinforcement Learning Exploration of EXP-based Algorithms
Authors: Mengfan Xu
Diego Klabjan
Venue:  (2021)

Abstract: EXP-based algorithms are often used for exploration in multi-armed bandit. We revisit the EXP3.P algorithm and establish both the lower and upper bounds of regret in the Gaussian multi-armed bandit setting, as well as a more general distribution option. The analyses do not require bounded rewards compared to classical regret assumptions. We also extend EXP4 from multi-armed bandit to reinforcement learning to incentivize exploration by multiple agents. The resulting algorithm has been tested on hard-to-explore games and it shows an improvement on exploration compared to state-of-the-art.

Under review as a conference paper at ICLR 2021
REGRET BOUNDS AND REINFORCEMENT LEARNING EXPLORATION OF EXP-BASED ALGORIHTMM
Anonymous authors Paper under double-bling review
ABSTRACT
EXP-based algorithms are often used for exploration in multi-armed bandit, We revisit the EXP3.P algorithm and establish both the lower and upper bounds of regret in the Gaussian multi-armed bandit setting, as well as a more general distribution option. The analyses do require bounded rewards compared classical regret assumptions. We also extend EXP4 from multi-armed bandit to reinforcement learning to incentivize exploration by multiple agents. The resulting algorithm has been tested on hard-to-exple to-el-loor games and it shows an improvement on exploration compared to state-of titte-of-thhrrtt..
INTRODUCTION
Multi-armed bandit (MAB) is to maximize cumulative reward of a player throughout a bandit game by choosing different arms each time step. It is also equivalent minimizing the regret defined as the difference between the best rewards that can be achieved and the actual reward gained by the player. Formally, given time horizon T. in time step S T the player choose one arm a, among K arms, receives rf, among rewards rf = rri,rs..... rk)) and maximizes the total reward Σi= ri. the
or minimizes the regret. Computationally efficient and with abundant theoretical analyses EXP-type MAB algorithms. In EXP3.P, each arm has trust coefficient (weight). The player samples each with probability being the sum of its normalized weights and bias term, receives reward of the sampled arm and exponentially updates the weights based on the corresponding reward estimates. It achieves the regret of the order O O(VT) in a high probability sense. In EXP4, there are any number of experts. Each has sample rule over actions and a weight. The player samples according the weighted average of experts' sample rules and updates the weights respectively.
Contextual bandit is a variant of MAB by adding context or state space S. At time step t, the player has context & E with 81:7 = (81, ..,...,.......................,. 8T) being independent. Rewards rd follow (()(s)) where F is any distribution and (u(s)) is the mean vector that depends on state 8t. Reinforcement Learning (RL) generalizes contextual bandit, where state and reward transitions follow a Markov Decision Process (MDP) represented by transition kernel P(st+1, r |a,, st). ). A key challenge in RL the trade-off between exploration and exploitation. Exploration is to encourage the player to try new arms in MAB or actions in RL understand the game better. It helps to plan for the future, but with the sacrifice of potentially lowering the current reward. Exploitation aims to exploit currently known states and arms maximize the current reward, but it potentially prevents the player to gain more information to increase local reward. To maximize the cumulative reward, the player needs to know the game by exploration, while guaranteeing current reward by exploitation.
How to incentivize exploration in RL has been main focus in RL. Since RL is built on MAB, is natural to extend MAB techniques to RL and UCB is such a success. UCB (Auer et al. 2002a) motivates count- based exploration (Strehl and Littman| 2008) RL and the subsequent Pseudo- Count exploration (Bellemare et al., 2016). New deep RL exploration algorithms have been recently proposed. Using deep neural networks to keep track of the Q-values by means of Q-networks in RL is called DQN (Mnih et al. (2013)). This combination of deep learning and RL has shown great success. e-greedy in Mnih et al. (2015) is a simple exploration technique using DQN. Besides e-greedy, intrinsic model exploration computes intrinsic rewards by focusing on experiences. Intrinsic rewards directly measure and incentivize exploration if added to extrinsic (actual) rewards of RL, e.g. DORA (Fox et al. 2018) and (Stadie et al. (015). Random Network Distillation (RND) (Burda et al.) 2018) is a more recent suggestion relying on a fixed target network. A drawback of RND is its local Tocus without global exploration.

---

Under review as a conference paper at ICLR 2021
In order to address weak points of these various exploration algorithms in the RL context, the notion of experts is natural and thus EXP-type MAB algorithms are appropriate. The allowance of arbitrary experts provides exploration for harder contextual bandits and hence providing exploration possibilities for RL. We develop an EXP4 exploration algorithm for RI. that relies on several general experts. This is the first RL algorithm using several exploration experts enabling global exploration. Focusing on DQN, in the computational study we focus on two agents consisting of RND and e-greedy DQN.
We implement the RL EXP4 algorithm on the hard-to-explore RL game Montezuma's 's Revenge and compare with the benchmark algorithm RND (Burda al. (2018)) The numerical results show that the algorithm gains more exploration than RND and it gais the ability of global exploration by not getting stuck in local maximums of RND. Its total reward also increases with training. Overall, our algorithm improves exploration and exploitation on the benchmark game and demonstrates learning process RL.
Reward in RL in many cases is unbounded which relates to unbounded MAB rewards. There are three major versions of MAB: Adversarial, Stochastic, and herein introduced Gaussian. For adversarial MAB, rewards of the K arms r' can be chosen arbitrarily by adversaries at step l. For stochastic MAB, the rewards at different steps are assumed to be i..d. and the rewards across arms are independent. It is assumed that 0 < rf < for any arm and step t. For Gaussian MAB, rewards r' follow multi-variate normal (14, Σ) with fa being the mean vector and Σ the covariance matrix of the K arms. Here the rewards are neither bounded, nor independent among the arms. For this reason the introduced Gaussian MAB reflects the RL setting and is the subject of our MAB analyses of EXP3.P.
EXP-type algorithms (Auer et al. (002bb) are optimal in the two classical MABs. Auer et al. (202b)) show lower and upper bounds on regret of the order O(V for adversarial MAB and of the order O(lg((T) for stochastic MAB. All of the proofs of these regret bounds by EXP-type algorithms are based on the bounded reward assumption, which does not hold for Gaussian MAB. Therefore, the regret bounds for Gaussian MAB with unbounded rewards studied herein are significantly different from prior works.
We show both lower and upper bounds on regret of Gaussian MAB under certain assumptions. Some analyses even hold for more generally distributed MAB. Upper bounds borrow some ideas from the analysis of the EXP3.P algorithm in Auur et al. (2002b) for bounded MAB to our unbounded MAB, while lower bounds are by our brand new construction of instances. Precisely, we derive lower bounds order Q(T)) for certain fixed T and upper bounds of order (vT) for T being large enough. The question of bounds for any value of T remains open.
The main contributions of this work are as follows. On the analytical side we introduce Gaussian MAB with the unique aspect and challenge of unbounded rewards. We provide the very first regret lower bound in such a case by constructing a novel family of Gaussian bandits and we are able to analyze the EXP3.P algorithm for Gaussian MAB. Unbounded reward poses non-trivial challenge in the analyses. We also provide the very first extension of EXP4 to RL exploration. We show its superior performance two hard-to-explore RL games.
literature review is provided in Section[] Then in Section we exhibit upper bounds for unbounded MAB of the EXP3.P algorithm and lower bounds, respectively. Section 4 discusses the EXP4 algorithm for RI. exploration. Finally, in Section 5 we present numerical results related to the proposed algorithm.
LITERATURE REVIEW
The importance of exploration in RL is well understood. Count-based exploration in RL relies on UCB. Strehl and Littman (008 develop Bellman value iteration V(s) max, R(s, a) (s') + (N, a)= 2, where ((s.a) is the number of visits to (s, a) for state and action a. Value ((ss, - is positively correlated with curiosity of (s, a) and encourages exploration. This method is limited to tableau model-based MDP for small state spaces, while Bellemare et al. (016))
introduce Eseudo-Count exploration for non-tableau MDP with density models.
In conjunction with DQN, e-greedy in Mnih et al. (2015) is simple exploration technique using DQN. Besides e-greedy, intrinsic model exploration computes intrinsic rewards by the accuracy of model trained experiences. Intrinsic rewards directly measure and incentivize exploration if
2

---

Under review as a conference paper at ICLR 2021
added to extrinsic (actual) rewards of RL, e.g. DORA in Fox et al. (2018) and Stadie al. (0155) Intrinsic rewards in Stadie et al. (2015) are defined as e(s, a) = | (o(a(s), a where M is a parametric model, s' is the next state and a is imput extraction. Intrinsic reward e(s, a) relies on stochastic transition from & to s' and brings noise to exploration. Random Network (istillation(RND) in Burda et al. (2018) addresses this by defining e(s, a) = [[f(s") f(s) where f is a parametric model and f is randomly initialized but fixed model. Here e(s, a), independent of the transition, only depends on state s' and drives RND to outperform other algorithms on Montezuma'ss 's Revenge. None of these algorithms use several experts which is a significant departure from our work.
In terms of MAB regret analyses focusing EXP-type algorithms, Auer et al. (2002b) first introduce EXP3.P for bounded adversarial MAB and EXP4 for contextual bandits. Under the EXP3. P algorithm. an upper bound on regret of the order O (VT)) is achieved, which has no gap with the lower bound and hence it establishes that EXP3.P is optimal. However these regret bounds are not applicable to Gaussian MAB since rewards can be infinite. Meanwhile for unbounded MAB, |Srinivss et al. (2010) MAB,[Srinivas ?T) for noisy Gaussian process bandits where reward observation contains noise. The information gain "I is not well-defined in a noiseless Gaussian setting. For noiseless Gaussian bandits. Grünewälder et al. (2010) show both the optimal lower and upper bounds on regret, but the regret definition is not consistent with the one used in Auer et al. (2002b). We establish lower bound of the order ((T)) for certain T and an upper bound of the order O (vT) asymptotically on regret of unbounded noiseless Gaussian MAB following standard definitions of regret.
demonstrate regret bound of order
REGRET BOUNDS FOR GAUSSIAN MAB
For Gaussian MAB with time horizon T, at step 0 < S T rewards r² follow multi-variate normal (1,, Σ) where f = (H1, 14, is the mean vector and Σ = (0:5)..sE(L.....) is the covariance matrix of the K arms. The player receives reward y/- r/, by pulling arm de. We use Ry = maxk 1As- >. Elys] to denote pseudo regret called simply regret. (Note that the alternative
definition of regret Rr = max; ΣJ r E Vt depends on realizations of rewards.)
3.1 LOWER BOUNDS ON REGRET In this section we derive lower bound for Gaussian and general MAB under an assumption. General MAB replaces Gaussian with a general distribution. The main technique is to construct instances or sub-classes that have certain regret, no matter what strategies are deployed. We need the following assumption or setting.
Assumption There are two types of arms with general K with one type being superior (S' is the set of superior arms) and the other being inferior (I is the set of inferior arms). Let 1 q, q be the proportions of the superior and inferior arms, respectively which is known to the adversary and clearly 0 S 9 S 1. The arms in S are indistinguishable and so are those in T. The first pull of the player has two steps. In the first step the player selects an inferior or superior set of arms based on P(S) = 1 q and P(T) = q and once is selected, the corresponding reward of arm from the selected set is received.
An interesting special case of Assumption is the case of two arms and q = 1/2. In this case, the player has no prior knowledge and in the first pull chooses an arm uniformly at random.
The lower bound defined as Rr (T) = inf sup RG, where, first, inf is taken among all the strategies and then sup is among all Gaussian MAB. All proofs are in the Appendix.
The following is the main result with respect to lower bounds and it is based on inferior arms being distributed as (0, 1) and superior N ((,,) 1) with μ O.
Theorem 1. In Gaussian MAB under Assumption I. any 2 1/3 we have RT 2 (q c) T-TT where μ has to satisfy G(g.
p)) < q with e and T determined by
G(q.
G(g.u) u) <E<9 q.
T
+2
(1 - 9) 1 c o c bو
22
and G(g. p) = max {s - (1- ---le- g)e
تجسح) dx, I (1 - (1-q)e- 22
4 -e-
dx
3

---

Under review as a conference paper at ICLR 2021
To prove Theorem 1 we construct a special subset of Gaussian MAB with equal variances and zero covariances. On these instances we find a unique way to explicitly represent any policy. This builds a connection between abstract policies and this concrete mathematical representation. Then we show that pseudo regret R2 must be greater than certain values no matter what policies are deployed, which indicates regret lower bound these subset of instances.
The feasibility of the aforementioned conditions is established in the following theorem.
Theorem 2. In Gaussian MAB under Assumption 1, for any q 2 1/3, there exist I and e, 6 < l such that (T) 2 (q 6) T.
The following result with two arms and equal probability the first pull deals /with general probabil- ities. Even in the case of Gaussian MAB is not special case of Theorem 2 since it is stronger.
Theorem 3. For general MAB under Assumption I with K 2, 1/2, have that R2(T) 2 f holds for any distributions for the arms in I and for the arms in S with J [S fol (possibly with unbounded support), for any p. and T satisfying T 2- 1.
The theorem establishes that for any fixed > 0 there is a finite set of horizons and instances of Gaussian MAB that algorithm achieve regret smaller than linear in T. Table T provides the values of the relationship between and largest I' in the Gaussian case where the inferior arms are distributed based on the standard normal and the superior arms have mean μ > and variance 1. For example, there is no way to attain regret lower than T 10-4///// /4 for any 1 < T S 2501. The function decreases very quickly.
Table 1: Upper bounds for T as a function of
10-5
10-4 4
10-3
10-2
10-1
Upper bound for
25001
2501
251
3.5
The established lower bound result (T) 2 S2(T)) is larger than known results of classical MAB. This is not surprising since the rewards classical MAB are assumed to be bounded, while rewards in our setting follow an unbounded Gaussian distribution, which apparently increases regret.
Besides the known result Q(vT)) of adversarial MAB and (llg 7') of stochastic MAB, for noisy Gaussian Process bandits, Srinivas et al. (2010) show RG (T) S Q(V YT). Our lower bound for Gaussian MAB is different from this lower bound. The information gain term Yrr in noisy Gaussian bandits not well-defined Gaussian MAB and thus the two bounds are not comparable.
3.2 UPPER BOUNDS ON REGRET
In this section, we establish upper bounds for regret of Gaussian MAB by means of the EXP3.P algorithm (see Algorithm I) from Auer al. (2002b). We stress that rewards can be infinite, without the bounded assumption present in stochastic and adversarial MAB. We only consider non-degenerate Gaussian MAB where variance of each arm strictly positive, i.e. min, as 0.
Algorithm 1: EXP3.P
Initialization: Weights w1(1) = exp (a)
( /T) (1,2,.... K} for a > 0 and d E (0, 1);
for 1..2....,. . do
for i 1,2...., K do
(c(1) =
wx(() E (1)
8
end
Choose i, randomly according to the distribution pt()). (f)....... (t): ())()...,Pp(()) Receive reward ri, (t);
for j = 1,..., K do
(t) (1) (1) 1 m
w0y(1 + 1) w)(()) exp 3K (1)(1) kTTT
end
end
4

---

Under review as a conference paper at ICLR 2021
provide analyses for upper bounds Ry with high probability, E|Rr] and on Ry-- In Aner et al. (2002b) EXP3.P studied to yield a bound on regret Ry with high probability in the bounded MAB setting. As part of our contributions, we show that EXP3.P regret is of the order ("(VT) in the unbounded Gaussian MAB in the case of Rr with high probability, E[Rr] and Ry- The results are summarized as follows. The density of (j, Σ) is denoted by f.
Formally,
Theorem 4. For Gaussian MAB. any time horizon T, for any r EXP3.P has regret
KT 5 RT - 4D(n) (V KTK log(
+ 4 KT log K + log( KT) with probability (1 8)- (1- n))
where ((n) is determined by S_.... ... J ( 2K dx ... dr =
In the proof of Theorem 4 we first perform truncation of the rewards of Gaussian MAB by dividing the rewards to bounded part and unbounded tail throughout the game. For the bounded part, we directly borrow the regret upper bound EXP3.P in Auer et al. (2002)) and conclude with the regret upper bound order O [((n)) (n) vT). Since a Gaussian distribution a light-tailed distribution we can control the probability of tail shrinking which leads to the overall result.
The dependence of the bound on A can be removed by considering large enough T as stated next.
Theorem 5. For Gaussian MAB, and any a > 2, 0 < 6 < 1, EXP3.P has regret
RT < 1og(1/8)0" (VT) with probability (1 - 8) )
The constant behind O depends on K, a, μ and
The above theorems deal with Ry but the aforementioned lower bounds with respect to pseudo regret. To complete the analysis of Gaussian MAB, it is desirable to have an upper bound on pseudo regret which is established next. It is easy verify by the Jensen's inequality that R2 < E(RT] and thus it suffices to obtain an upper bound on E [R
For adversarial and stochastic MAB, the upper bound for E RT] is of the same order as Ry which follows by a simple argument. For Gaussian MAB, establishing based on Rr requires more work. We show an upper bound on E[AT] by using select inequalities, limit theories, and Randemacher complexity. To this end, the main result reads as follows.
upper bound on E[RT] or Rt
Theorem 6. The regret of EXP3.PMn in Gaussian MAB satisfies
P2 < E [T)] S (VT)..
All these three theorems also hold for uub-Gaussian MAB, which is defined by replacing Gaussian with aub-Gaussian. This generalization is straightforward and it is directly shown in the proof of Gaussian MAB in Appendix. Optimal upper bounds for adversarial MAB and noisy Gaussian Process bandits are of the same order as our upper bound. Auer et al. (2002)) derive an upper bound of the same order O ((VT)&& as the lower bound for adversarial MAB. For noisy Gaussian Process bandits, there is also no gap between its upper and lower bounds.
Our upper bound of the order O (vT) is of the same order the one for bounded MAB. In our case the upper bound result O*(VT) holds for large enough T which is hidden behind O while the linear lower bounds is valid only for small values T. This illustrates the rationality of the lower bound of O(T) and the upper bound of order O* (VTT).
4 EXP4 ALGORITHM FOR RL
EXP4 has shown great success in contextual bandits. Therefore, in this section, extend EXP4 to RL and develop EXP4-RL illustrated in Algorithm 2
The player has experts that are represented by deep Q-networks trained by RL algorithms (there is one to one correspondence between the experts and Q-networks). Each expert also has a trust coefficient. Trust coefficients are also updated exponentially based on the reward estimates as in EXP4. At each step of one episode, the player samples an expert (Q-network) with probability that is proportional to the weighted average of expert's 's trust coefficients. Then e-greedy DQN is applied on the chosen Q-network. Here different from EXP4, the player needs store all the interaction tuples
5

---

Under review as a conference paper at ICLR 2021
in experience buffer since RL is MDP. After one episode, the player trains all Q Q-networks with the experience buffer and uses the trained networks as experts for the next episode.
Algorithm 2: EXP4-RL
Initialization: Trust coefficients wy 1 for any ls E (I...., E,....,,,,.... , number of experts
(Q-networks), K = number of actions, A, e, >> 0 and temperature 2, T > 0, n2 = -00 (an
upper bound on reward);
while True do
Initialize episode by setting so:
for i ., T(lenghh of episode) do
Observe state 8;:
Let probability of Qı-network be P (1 17)
+ c
Σt wk
Sample network io according {pk Ja;
For Q netwwrkk use e-greedy to sample an action
a" = argmara QE (8x, a),
Tj = (1-c)-
j=at j=a
6 itt
j (1,2,........
K-1
Sample action o; based ı, Interact with the environment to receive reward r; and next state 8141;
nl max ]r); Update the trust coefficient wy of each Qk-network as follows:
Ps e-greedy(Qu)) (Qx), 1 11 j=a
(n, (n, E,2, K.y E[brus, wx w
Paς
Store (ss; az Th 8;+1) in experience replay buffer B;
end
Update each expert's Qe-netwrrk from buffer B; end
The basic idea is the same as EXP4 by using the experts that give advice vectors with deep -networks. It is combination of deep neural networks with EXP4 updates. From different perspective, can also view it as an ensemble in classification (Xia et al. (2011), by treating Q-networks as ensembles RL, instead of classification algorithms. While Q -entwworks do not necessarily have to experts, ie.. other experts can be used, these natural in a DQN framework.
In our implementation and experiments we use two experts, thus E = 2 with two Q-networks. The first one based on RND (Burda al. (2018) while the second one is simple DQN. To this end, in the algorithm before storing to buffer, we also record of = [lf())) - f(+ the RND intrinsic reward in Burda et al. (2018). This value is then added to the 4-tuple pushed B. When updating Qı corresponding to RND at the end of an iteration in the algorithm, by using ry + of we modify
the Qe-newwrrk and by using of an update to f is executed. Network Q2 pertaining to e-greedy is updated directly by using ry-
Intuitively, Algorithm 2 circumvents this drawback with the total exploration guided by two experts with EXP4 updated trust coefficients. When the RND expert drives high exploration, its trust coefficient leads to high total exploration. When it has low exploration, the second expert DQN should have high one and it incentivizes the total exploration accordingly. Trust coefficients are updated by reward estimates iteratively as EXP4, so they keep track of the long-term performance of experts and then guide the total exploration globally. These dynamics of EXP4 combined with intrinsic rewards guarantees global exploration. The experimental results exhibited in the next section verify this intuition regarding exploration behind Algorithm 2
We point out that potentially more general RL algorithms based on Q-factors can be used, e.g., boostrapped DQN (Osband et al. (2016)), random prioritized DQN (Osband et al. (2018) or adaptive possibility. Furthermore, experts in EXP4 even be policy
e-greedy VDBE Tokicc 2010)) networks trained by PPO (Schulman et al. (2017) instead of DQN for exploration. These possibilities demonstrate the flexibility of the EXP4-RL algorithm.

---

Under review as a conference paper at ICLR 2021
5 COMPUTATIONAL STUDY
As a numerical demonstration of the superior performance and exploration incentive of Algorithm 2 we show the improvements on basclines two hard-to-explore RL games, Mountain Car and Montezuma's Revenge. More precisely, we present that the real reward on Mountain Car improves significantly by Algorithm in Section 5.1 Then implement Algorithm [ on Montezuma's Revenge and show the growing and remarkable improvement of exploration in Section 5.2
Intrinsic reward of = =I]((s)) - [+:)]] given by intrinsic model f represents the exploration of RND Burda et al. (2018) as introduced Sections 2 and 4 We use the same criterion for evaluating exploration performance of our algorithm and RND herein. RND incentivizes local exploration with the single step intrinsic reward but with the absence of global exploration.
5.1 MOUNTAIN CAR
In this part, we summarize the experimental results of Algorithm 2 on Mountain Car, classical control RL game. This game has very sparse positive rewards, which brings the necessity and hardness of exploration. Blog post (Rivlin (2019)) shows that RND based on DQN improves the performance of traditional DQN, since RND has intrinsic reward to incentivize exploration. We use RND DQN from Riiviin (2019) the baseline and show the real reward improvement of Algorithm 2 which supports the intuition and superiority of the algorithm.
The comparison between Algorithm 2 and RND is presented in Figure 1 Here the x-axis is the epoch number and the y-axis is the cumulative reward of that epoch. Figure [T shows the raw data comparison between EXP4-RL and RND. We observe that though first RND has several spikes exceeding those of EXP4-RL, EXP4-RL has much higher rewards than RND after 300 epochs. Overall, the relative difference of areas under the curve (AUC) 4.9% for EXP4-RL over RND, which indicates the significant improvement of our algorithm. This improvement is better illustrated in Figure [b] with the smoothed reward values. Here there is a notable difference between EXP4-RL and RND. Note that the maximum reward hit by EXP4-RL is -86 and the one by RND is - -118, which additionally demonstrates our improvement on RND.
DF4FL
DAL
200
-10
60
(a) original
(b) smooth
Figure 1: The performance of Algorithm and RND measured by the epoch-wiss wise reward on Mountain Car, with the left one being the original data and the right being the smoothed reward values.
We conclude that Algorithm 2 performs better than the RND baseline and that the improvement increases at the later training stage. Exploration brought by Algorithm 2 gains real reward on this hard-to-explore Mountain Car, compared to the RND counterpart (without the DQN expert). The power of our algorithm can be enhanced by adopting more complex experts, not limited to only DQN.
5.2 MONTEZUMA'S S REVENGE AND PURE EXPLORATION SETTING
In this section, we show the experimental details of Algorithm 2 on Montezuma's Revenge, another notoriously hard-to-explore RL game. The benchmark on Montezuma's 's Revenge is RND based on DON which achieves a reward of zero in our environment (the PPO algorithm reported in Burda et al.) (2018) has reward 8,000 with many more computing resources; we ran the PPO-based RND with 10 parallel environments and 800 epochs to observe that the reward also 0), which indicates that DQN has room for improvement regarding exploration.
To this end, we first implement the DQN-version RND (called simply RND hereafter) on Montezuma's Revenge our benchmark by replacing the PPO with DQN. Then we implement Algorithm 2 with two experts as aforementioned. Our computing environment allows at most 10 parallel environments. In subsequent figures the x-axis always corresponds the number of epochs. RND update probability is the proportion of experience that used for training the intrinsic model f (Burda et al. 2018).
7

---

Under review as a conference paper at ICLR 2021
A comparison between Algorithm (EXP4-RL) and RND without parallel environments (the update probability is 100% since it is a single environment) is shown in Figure 2 with the emphasis on exploration by means of the intrinsic reward. We use 3 different numbers of burn-in periods (58, 68, 167 burn-in epochs) to remove the initial training steps, which is common in Gibbs sampling. Overall EXP4-RL outperforms RND with many significant spikes in the intrinsic rewards. The larger the number of burn-in periods is, the more significant is the dominance of EXP4-RL over RND. EXP4-RL has much higher exploration than RND some epochs and stays close to RND at other epochs. At some epochs, EXP4-RL even has 6 times higher exploration. The relative difference in the areas under the curves are 6.9%, 17.0%, 146.0% respectively, which quantifies the much better performance of EXP4-RL.
20
10
10
(a) small
(b) medium
(c) large
Figure 2: The performance of Algorithm 2 and RND measured by intrinsic reward without parallel
environments with three different burn-in periods
2014
2013
(a) Q-network losses with 0.25 update
(b) Intrinsic reward after (c) Intrinsic reward after smoothing with 0.25 update smoothing with 0.125 update
Figure 3: The performance of Algorithm 2 and RND with 10 parallel environments and with RND update probability 0.25 and 025, measured by loss and intrinsic reward.
We next compare EXP4-RL and RND with 10 parallel environments and different RND update probabilities Figure 3
The experiences are generated by the 10 parallel environments.
Figure 3a shows that both experts in EXP4-RL are learning with decreasing losses of their Q-networks. The drop is steeper for the RND expert but it starts with higher loss. With RND update probability 0.25 in Figure 3b we observe that EX and RND are very close when RND exhibits high exploration. When RND are driven by sticking to local maxima and then training the model intensively at local maxima, typical of the RND local exploration behavior. EXP4-RI. improves on RND as training progresses, c.g. the improvement after 550 epochs is higher than the one between epochs 250 and 550. In terms for AUC, this is expressed by 1.6% and 3.5%, respectively. Overall, EXP4-RL improves RND local minima of exploration, keeps high exploration of RND and induces smoother global exploration.
its local minima, EXP4-RL outperforms Usually these local minima
With the update probability of 0.25 in Figure 3c EXP4-RL almost always outperforms RND with a notable difference. The improvement also increases with epochs and is dramatically larger RND's local minima. These local minima appear more frequently in training of RND, so our improvement is more significant well erucial. The relative AUC improvement is 49.4%. The excellent performance in Figure 3c additionally shows that EXP4-RL improves RND with global exploration by improving local minima of RND or not staying at local maxima.
Overall, with either 0.25 or 0. 125, EXP4-RL incentivizes global exploration on RND by not getting stuck in local exploration maxima and outperforms RND exploration aggressively. With 0.125 the improvement with respect to RND is more significant and steady. These experimental evidence verifies our intuition behind EXP4-RL and provides excellent support for it. With experts being more advanced RI. exploration algorithms, e.g. DORA, EXP4-RI. can bring additional possibilities.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Auer, N. Cesa-Bianchi and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-2555 2002a.
P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002b.
M. F. Balcan. 8803 machine learning theory.
lect1117. 2011.
M. Bellemare, Srinivasan, Ostrovski, Schaul, D. Saxton, and Munos. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems, pages 1471-1479, 2016.
Y. Burda, H. Edwards, A. Storkey, and O. Klimov. Exploration by random network distillation. In International Conference Learning Representations, 2018.
S. Chatterjee. Superconcentraation and related topics, volume 15. Cham: Springer, 2014.
Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. Imagenet: large-scale hierarchical image database. In 2009 IEEE conference on Computer Vision and Pattern Recognition, pages 248 255. IEEE, 2009.
L. Devroye, A. Mehrabian, and T. Reddad. The total variation distance between high-dimennional gaussians. arXiv preprint arXiv:1810.086993, 2018.
J. Duchi. Probability bounds. probability_boune bounds. pdf 2009.
L. Fox, L. Choshen, and Y. Loewenstein. Dora the explorer: directed outreaching reinforcement action-selection. In International Conference on Learning Representations, 2018.
Grünewälder, Audibert, M. Opper, and J. Shawe-Taylor. Regret bounds for gaussian process bandit problems. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pages 273-280, 2010.
A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, pages 1097-1105, 2012.
V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Ried- miller, K. Fidjeland, G. Ostrovski, and S. Petersen. Human-level control through deep rein- forcement learning. Nature, 518(7540):529-55 553,, 2015.
I. Osband, C. Blundell, A. Pritzel, and B. Van Roy. Deep exploration via bootstrapped dqn. In Advances in Neural Information Processing Systems, pages 4026-4034 2016.
I. Osband, J. Aslanides, and A. Cassirer. Randomized prior functions for deep reinforcement learning. In Advances in Neural Information Processing Systems, pages
2018.
O. Rivlin. Mountaincar_dqun rnd. http:////ggttto..oooooooo/////// RND 2019.
J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 17770:7777. 2017.
N. Srinivas, A. Krause, S. Kakade, and M. Seeger. Gaussian process optimization in the bandit.
setting: regret and experimental design. In Proceedings of the 27th International Conference Machine Learning, 2010.
B. C. Stadie, Levine, and Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. arXiv preprint arXiv: 150.0008 2015.

---

Under review as a conference paper at ICLR 2021
A. L. Strehl and M. L. Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):1339- 1331,,11111100, 2008.
M. Tokic. Adaptive s-greedy exploration in reinforcement learning based on value differences. In Annual Conference on Artificial Intelligence, pages 203-210. Springer, 2010.
R. Xia, Zong, and Li. Ensemble of feature sets and classification algorithms for sentiment classification. Information Sciences, (81 111111181111551 1152, 2011.
10

---

Under review as a conference paper at ICLR 2021
A DETAILS ABOUT NUMERICAL EXPERIMENTS
A.1 MOUNTAIN CAR
the Adam optimizer with the 20-4 learning rate. The batch size for updating models is 64 with the replay buffer size of 10,000. The remaining parameters follows: the discount factor for the Q-networks is 0.95, the temperature parameter T is 0.1, 7 is 0.05, and e is decaying exponentially with respect to the number of steps with maximum 0.9 and minimum 0.05. The length of one epoch is 200 steps. The target networks load the weights and biases of the trained networks every 400 steps. Since reward upper bound is known in advance, we use 74
For the Mountain Car experiment,
We next introduce the structure of neural networks that are used in the experiment. The neural networks of both experts are linear. For the RND expert, it has the input layer with 2 input neurons, followed by a hidden layer with 64 neurons, and then two-headed output layer. The first output layer represents the Q values with 64 hidden neurons as input and the number of actions output neurons, while the second output layer corresponds to the intrinsic values, with output neuron. For the DQN expert, the only difference lies in the absence of the second output layer.
A.2 MONTEZUMA'S REVENGE
For the Montezuma's Revenge experiment, we use the Adam optimizer with the 10 learning rate. The other parameters read: the mini batch size is 4, replay buffer size is 1,000, the discount factor for the Q-networks is 0.999 and the same valus is used for the intrinsic value head, the temperature parameter is 0.1, 17 is 0.05, and is increasing exponentially with minimum 0.05 and maximum 0.9. The length of one epoch is 100 steps. Target networks are updated every 300 steps. Pre-normalization is 50 epochs and the weights for intrinsic and extrinsic values in the first network are and 2, respectively. The upper bound on reward is set to be constant n, 11
For the structure of nerual networks, we use CNN architectures since we are dealing with videos. More precisely, for the Q-network of the DQN expert in EXP4-RL and the predictor network f for computing the intrinsic rewards, (Deng et al. (209)). ). The number of output neurons of the final layer is 18, the number of actions in Montezuma. For the RND baseline and RND expert in EXP4-RL, we customize the Q-network with different linear layers while keeping all the layers except the final layer of pretrained Alexnet. Here we have two final linear layers representing two value heads, the extrinsic value head and the intrinsic value head. The number of output neurons in the first value head is again 18, while the second value head is with output neuron.
Alexnet (Krizhevsky et al. (2012)) pretrained on ImageNet
More details about the setup of the experiment on Montezuma's 's Revenge are elaborated follows. The experiment of RND with PPO in Burda et al. (2018) uses many more resources, such as 1024 parallel environments and runs 30,000 epochs for each environment. Parallel environments generate experiences simultaneously and store them in the replay buffer. Our computing environment allows most 10 parallel environments. For the DON-version of RND (called simply RND hereafter), use the same settings as Burda et al. (2018), such as observation normalization, intrinsic reward normalization and random initialization. RND update probability the proportion of experience in the replay buffer that are used for training the intrinsic model f in RND (Burda et al. 2018). Here in our experiment, we compare the performance under O. 125 and 0.25 RND update probability.
B PROOF OF RESULTS IN SECTION 3.1
For brevity, we define T 1.
We start by showing the following proposition that is used in the proofs.
Proposition 1. Let G(g, p), and p be defined as in Theorem 7 Then for any 2 1/3, there exists a p that satisfies the constraint G(g, p) < 4.
11

---

Under review as a conference paper at ICLR 2021
Proof. Let us denote G1 llfo(()) (1- (1-1) G2 (1(1-9f0(xz) -ff(z)) dr. Then we have
(4) = / lafo(o) - (1 ())((()) dr
/ (9f0(1) - (1 ()){ (
+ / (-150()) + (1 - (x)) (1
/ (9f0(z) - - (z)( (
tx + / (-1f0())+(11))(((())) (1-g)f((zz) 1 L>>g())
((1)
qe 2 -1--q)e (w-
(-qe + q)e 1w- de
dr dr+ +
2tx
a(1))
(9())
polu)- -g(u)ta
e - (1-9)
e E=
2x
-g(u)
where 0(44= = 1/2 log( 22)
Similarly we get
p(()) (1 - 9)
/
e e -
palu)an
G2(9. 2m
a(1))
-buu++
is easy to establish continuity of Gi and G2(g, u) on [0, o0), as well as the continuity of G(q, ().. Indeed, have
4= 0 G(g. = [1 2gl
max((q, 1 -q) + Since 2 1. then |1 - 24l < From continuity of G(g, p), there exists μo > 0 such that 3.
G(q, q for any μ S μo.
Proof of Theorem 7 As in Assumption 1, let the inferior arm set be / and the superior one be S. respectively, P(T) g and P(S) = - q. Arms in / follow fo(z) WWO0, 1) and arms in S follow Assumption 1, at the first step the player pulls an arm from either or S and receives reward V1- At time step i > 1, the reward is and let b, represent policy of the player. We can always define b; as
f1()) = (N, 1) where μ > According
b, [1 if the chosen arm at step i is not in the same arm set as the initial arm, otherwise.
Let a, E {0, } be the actual arm played at step i. It suffices to only specify a, arm set (a; = 0) or S (a, 1) since the arms in I and S are identical. The connection between a; and b, is explicitly given by by = |a anl. By Assumption 1, it easy to argue that h; = (y V2,..,, 9i-1) for a set of functions S2 S ....... S Sh+1- We proceed with the following lemma.
Lemma 1. Let the rewards of the in set I follow any Ln distribution fo(2r) and in set S follow any Ly distribution Si (xx) where the means satisfy μ(J1) >> p(Jo)- Let B be the number of arms played in the game in set S. Let us assume the player meets Assumption Then no matter what strategy the player takes, we have
B (1+1)
Se
where e, T. for fr satisfy
Glg, f1) + () 1) f1(x)) Se
12

---

Under review as a conference paper at ICLR 2021
G(g, for fi) max {ʃ (4fu(()) (1 g)fi(=)) ()fo(z)) (f((()) dæ).
Proof. We have
E[B] / (01 a2 + ... + an-1) for (V1) faz (12) San (un) du dyz- dyn-
a1 0, then a; and
B 01 = =0] = / (0- - b2 (11:1) +... .. + bu+1 (Him)) fo (11) for (12) ... for (Un) dyp ... dyn.
af 1, then 1 - = b; and
E B = 1] 1| / (1 be (v1a) +... + but1 (yI:n) fi (v1) ... f1-bn (yn) dyr .. dyn.
This gives us
E|B q- EBBaa = 0] (1 4) [B/a
= (1 - (1n
/ (b2 +... bn+1) (q So (v1).. ... Son (un) (1 -5 (11) ... S--,. (yn)) dy dyz ... dyn-
By defining b = O, we have
B (1 4) (n + 1)+
/ (b2 + .... + b (g for (V1)... for (yn) - (1 - q) fi (v1) f1-0n (2n)) dys dyd dyn.
For any 1 1 m & n we also derive
for (16) II fi (1i) dy1dyz... dym
for (Wi) Ifom (Um) - f2 (yn)) dy1dyz- dym +
1=1
/
II fo, (v:)
II
fi-o, (wi)
fi-bm (2m) dy dyzz ... dym
E=1
$ [1((z)) fz(2)) do /
m
Sb. (vi)
m-
fi b-,,, (y:) II d=1
f1-b., (Um) dyn dym (1)
i=1
= / (10(0)) - -1)( do + /
m-11
Sb. (yi)
II Si 1.- (y1)
dy ... .ddmm-
22 / (L6(L) - f1(x)) + /
12
m-
II fo. (v:)
II fi (16) i
dyz .dymm22
$ m / [16((=) -(x))
13

---

Under review as a conference paper at ICLR 2021
This provides
B
(1 - q) (n
n +
/ q
fo. (y:) -(1 g) II fi-b. (wt) dyndyz ... dyn
i=1
7
fo. (3i) 1a fon (Hn) (1 10-9) q) fi-b- (Wn)) dyi ... dy
n-1 (1 9)
n-1
Jo. (wi) - -1 -1-4) II S1-b; (11) fi-ba (yn) dyidy/2 ... dyn
i=1
$ max { q fo(x) -11 ()) (2(.)())) dr, / [11 (11-9) 9)- fo(z)) - f1(x)) dr
n-1
n-1
(1 g) / II Sb, (vi)
II Si-b, (vi) dyidyz-... dyn-1 1=1
< <max { /11- fo(x) - (1- (f(x)) dr, / 1(1 (11-)) ()(()) f((x)) dx
/g-f((x))
f(()))de)
(1 ()-g) - (n- 1 -
where the last inequality follows from The statement of the lemma now follows.
According to Proposition there is such μ satisfying the constraint G(g, < q. Note that G(q, = G(g, for fi). Then we can choose to be any quantity such that G(g, M) < e < q. Finally, (-G(a.)) there is T satisfying T (-0))1166((---11-))))) + 2 that gives us
G(q +(1 (T - f) -((f(())((()))))))))))))())()(() Se.
By choosing e, T, as above, by Lemmal we have
[[
(1 9) .T
<C,
T
which is equivalent to E[B] < (1 9 + e) T. Therefore, regret RG satisfies, with A being the number of arm pulls from I, inequality
RT Σ max(px) ΣElvd
Elvil =Tp Σ Elvil Tμ (EEB E[A] 0)
2Tμ (1 + c)TT = = - -)TTT.
This yields R4 inf sup R (q - c) μ..
Theorem follows from Theorem D and Proposition
Proof of Theorem 3 The assumption here is the special case of Assumption I where there two arms and q = 1/2. Set follows fo and follows f1 where p(fo) < p(f1).
In the same in the proof of Theorem [we obtain
RT.(T) ! c) T
under the constraint that n/2- f [.fo - n/2 - fi) < e where TV stands for total variation. Here use m4 1122- TV(Jo, Setting 1/4 yields the statement.
n
14

---

Under review as a conference paper at ICLR 2021
In the Gaussian case it turns out that 1/4 yields the highest bound. For total variation of Gaussian variables N (111 of) and N NHz, oī), Devroye et al. (2018) show that
TV (N (uI, .N (22,02)
3/0
(py #1-P2 201
20
which in our case yields TV - 6. From this we obtain μ T and in turn R4 2 c (2 c). The
2.
maximum of the right-hau side is obtained at = 3.- This justifies the choice of in the proof of 3
C PROOF OF RESULTS IN SECTION 3.2
C.1 PROOF FOR THEOREM 4
Proof. Since the rewards can be unbounded in our setting, we consider truncating the reward with any A for any arm by rf = F; + where
rf. (-ASHASA) = ((()>)))-
Then for any parameter
choose such A that satisfies
P(r p/ K) P(-A P(-ASAsA - S A)
[ f(11 KK dz de 2 17
(2)
The existence of such = A(r) follows from elementary calculus.
Let flrl S A for every S K,t S T). Then the probability of this event is
P(A) P = p/.
< T) (1-
With probability (1 17 T" the rewards of the player are bounded in [-A, A] throughout the game.
Then RD = -T= (max, : - +)) < T E 7i the regret under event A, i.c. Rr R with probability (1 - 7))a For the EXP3.P algorithm and Rf, for every > 0, according to Auer al. (2002b) have
VKTTlog log(
KT ))
5 Kogog log K log( )
KT {
n < 44
+ AV
KT
with probability 1 6.
Then we have
Rr < 4A(n)
(VKTlog( KT
+ 4v KT K + 8 logg( KTT) with probability (1-6)-(1-m)
8
C.2 PROOF FOR THEOREM
Lemma 2. For any non-decreasing differentiable function A A(T) 0 satisfying
limy +00 log(T] = oc,
A(T)²
limp 000
(T) S Co oo,
and any < 1, > 2 have
p P(R < A(T) log(1/6) -(((T) 2 211 (1-8) (1-
1 T Tu
for any large enough.
15

---

Under review as a conference paper at ICLR 2021
Proof. Let a > 2 and let denote
F(9) { D2,,,,2,..,,38 1 ... drk.
((T) = F(((T) - T
for y E R and 1 (l,..., 1) RRK Let also 1/-i (V1..... . -/4-11 .. ,/)) and x|a,=y
(01, (21,...,, F1-1 1, y/ F1+1........ ,K.
ÆK). We have limy- ((T) =
The gradient of F can be estimated as
- (1"))
P- I (x)aa mnl daz ... dak.....
g-K
I (x dor dex-1)
VF S
v-K
According to the chain rule and since (T))) 2 0. we have
dF(A(T)
A
/ (fle)=)(TT) do2....rp. ('(
dT
-A(T)_L
A(T)-1x
I (Flex=A(T)) dr ... do d= (T).
-ATTAL
Next we consider
A(T)--
LATTI (a)); dxi .......de ddd:-1di41111.. dr
A(T)) este de ... ddi-1dr;+1- ... dd..
=e-tou(A(T)**uaa +M.(()
_
Here co(e-.) is the conditional density function
given
A(T) and thus
(((T) eg(a +) dr .......o d ... dx S 1. We have
(-A(T)L_,
A
A[T)L-; S (x)e,=A(TT) den dr, d do
I e (a:lA(T))+
Se miny (A)())))) +maxy ATT())
Then for T > we have Af S Co + and in turn
<'TT) < (C. + 1) - 1/ min, a. (A(()))))) +max, Ay)(T) a - a--1
Since only consider non-degenerate Gaussian bandits with min oz 0, μ4 constants and
A(T) + oo as + oo according to the assumptions in Lemma there exits C₁2 > 0 and Ti such that
} miny as (A(() HTA(T) < -CA(T)) for every T>> Tí.
Since limm-+00 (Tg(T) 00, we have
A(T)
A(T)2 > 2(a+1) log(T) for T > T2.
16

---

Under review as a conference paper at ICLR 2021
These give that
S(TY - (Co + -))Ke-((++)nan 2(0+1) aT a-1
ae (Co + 1)Ke 2(a+1) log -a (a+ log
< 0 for T' 2 T3 2 mmx (To, T2)
This concludes that (")) 0 for T > T3. We also have limm ((T) 0 according to the assumptions. Therefore, we finally arrive at ((T) > 0 for T T3. This equivalent to
A(1)-1
IK) do dx 2
To
A(T)-11
i.e. the rewards are bounded by A(T) with probability
Then by the same argument for T
T
large enough as the proof of Theorem 4 we have
P (RT s A(T) log((16)) (0())) 2 (1-8)(1-
-111-
Proof of Theorem In Lemma 2 choose ((T) logg which meets all of the assumptions.
The result now follows from log T O" (vT) = 0 (vT), Lemmaa and Theorem
C.3 PROOF FOR THEOREM 6
We first list known lemmas. The following lemma by Duchi 2009) provides a way to bound deviations.
Lemma 3. For any function class F, and i..d. random variable { 02. -.. ,T), the result
Eg suP
Egf ET f (oz) s 2R)
holds where (F) En sup,
Ein S.f (mx) and or is a 11, random walk of steps.
The following result holds according to Balcan 2011).
/2log | where R(A,T) =
Lemma 4. For any subclass A C F, we have RG < R(A,T)
suP (ET- f(z:)) and RG supy ET= or (z:)
random variable is Sub--Gaaanni for any 0, the tail probability satisfies
P(X > t) < Be 2²
where B is positive constant. The following lemma is listed in the Appendix A of Chatterjee (2014).
Lemma 5. For i..dd. pa-sub-Gaussae random variables {Yı, Y2,..,, Yrh.
we have
E [maxisesT [Y]]] S SoV2log1 +
4n
V2log
Proof for Theorem 0 Let define F F= (f : - æzيū 1,2, ... K). Let.r, (rf, r............ ..k where r is the reward of arm at step and let be the arm selected at time by EXP3.P. Then for any f, F. (xz) rf. In Gaussian-MAB, {x1, ,2, i.i.d. random variables since the Gaussian distribution A (J,, E) is invariant time and independent of time. Then by Lemma 3 have
E maxi p4:
< (F)
17

---

Under review as a conference paper at ICLR 2021
We consider
T
T
E PT
Rr|] = E
T max
Mai
max
t=1
T max 14 max E
Pas
(3)
T max pr max E
Σ
Ma.
T
T
$ E
max
T 14
E
Σ
Pa,
S 2 + 27, RG,
+ 2T R (F)
where T; is the number of pulls of arm i. Clearly Ti + T2 + + TTK = T. By Lemma
with
F get
V2log
RG ( (F) S E[R(F,T)
T
(F) S ( T.)) 22 K
i (1,2,...., K}.
Since RF,, T) is increasing in T and T; S T, we have R2; (F) E (R(
/log K
7:
We next bound the expected deviation E [
Rr based on 3 as follows
log K
K
E log K
E| Brll S 2TE
T
T
s 2(K + 1) 2 log K F. ((((F,)))
(4)
Regarding E[R(F,T) have
T
E(R(F,T) = E
sup JEF
Σ f(21)
E
sup
Σ 1=1
(r!))
K
K E
E
(r:))2
T
max (rt)2 1st57
VT
max ISES
|r|
(5)
We next use Lemma 5 for any arm i. To this end let Y, = Since x, Gaussian, the marginals Y, are also Gaussian with mean and standard deviation of a.. Combining this with the fact that Gaussian random variable also gussub-Gaussian justifies the of the lemma. Thus
E maxIsiST
ai,i 2lg
4az,
/2
Continuing with equation 5 we further obtain
4a
E|R(F,T) VT K max
(i,.V 2log
/2 log
4VT
K 2T logogT
(6)
22log
18

---

Under review as a conference paper at ICLR 2021
By combining equation 4 and equation 6 we conclude
E E RT|] s 2(K 2og K maxa ( (2VTTloTT log
4VT
12log
(7)
-VT()))
We now turn our attention to the expectation of regret E[RT]. It can be written as
Rrl = Rr Ry + Rr (T=()o)-(V
< PT S0*(()) + Rr BRSOr(VT) s00(VT) + E Prr RT>O)((T))
= = + RT oo + E HTT Rr (VT) (8)
We consider 5 = 1/V7 and T for > 2. We have
1
lim (1 6) - -n)² = lim (1- - 8)(1 T-x
)r
T-x00
Ta
= Iim (1 - -0 - T
(TT)
lim e T+000
T-300
and
lim (1-(1-8)C 8)(1 7)) -logg T T
lim (1 e -log(T)) TT
T+x
T
(9)
<
lim log(T) T T T1 lim 22-a log(()) = 0. T-200
T-200
Let Pi = P RT (Vg()) which equals to P Rí <0((V)) since log(1/8)
log( (T) = OV By Theorem we have P1 = (1 - 6) (1 - 1))²
Note that [i[RT] s Co logooo)) (T") T shown by
T
T
T
E = E
max
r!
rf
< 2E
max
|r
< 2T E
max max |r!]
1=1
1=1
1=1
4aj,s vlog T
< 2T
E
max |r:|
< 2T
2T
Σ
+
(V2logT
4
< 2T
max as,i
Vlog7
< Co T log((")
for a constant Co.
The asymptotic behavior of the second term in equation
reads
E Ri Bu
R no- -V-TTooA-VT)))).
E [RT O'(T)) > | + +0"
< E P -0 (()
< E P Ry -V) + +0
x C. log (T): -1
where at the end equation]
19

---

Under review as a conference paper at ICLR 2021
Regarding the third term in equation using equation
note that R, I E[Rr] by the Jensen's inequality. By 7 and again equation we obtain
RT 1l Ry 20 (VT))
E [Rr - RTT (Rr - ((--)2200) + Ri 1| (Rr (Br--[RRR)) (R--ER)))20
s E - R2 + 12 RT 2 +
SE|Rr - R2 + E R4 P RT 2 E + +0
(O)(V)) + Co (og T P Rr 2 0((T))
= =0" C. (T) ( Pi) (v
Combining all these together we obtain B(RT) = 0² which concludes the proof.
20


Reviews:
[{"review_id": "mr6VACkYmZ9", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors consider analyzing the EXP3.P algorithm for the case of unbounded reward functions, in the sense that the rewards are governed by a Gaussian distribution. The authors first demonstrate a regret lower bound result on the Gaussian MABs when the time horizon is bounded from above. Then, the authors proceed to the analysis of the EXP3.P algorithm on the Gaussian MABs, and establish a regret bound similar to that of Auer et al. 2002. Finally, the authors apply the EXP3.P, where an expert corresponds to a Q-learning network, in the EXP4-RL algorithm, and evaluate it on multiple RL instances.\n\nMajor comments: The major technical contributions seem to be the regret bound for EXP3.P for the case of Gaussian MAB, as stated in Theorem 4. Based on the authors' notation in the first paragraph of page 3, the Gaussian reward distribution is stationary across time. This contribution appears marginal, since the Theorem appears to be a straightforward consequence of the EXP3.P regret by Auer et al. 2002 by conditioning on all realized rewards to lie in [-\\Delta, \\Delta]. The technical part on how to identify the best expert is already dealt with by the analysis in Auer et al. 2002. \n\nAnother contributions are Theorems 1-3, which are regret lower bounds for Gaussian MABs. I am not sure how to interpret these regret lower bounds, since they require the horizon length to be bounded from above. More precisely, the authors show that for any algorithm, there exists a Gaussian MAB instance such that $\\text{Reg}(T) \\geq c T$ when $T\\leq C$, where $c, C$ are instance-dependent  constants. While this bound is a mathematically sound statement, it does not imply anything about the difficulty of the underlying problem when T is large. For example, for regret upper bound of an MAB algorithm, one almost always establishes a guarantee of the form $\\text{Reg}(T) \\leq \\text{Bound}(T)$ for all $T \\geq C'$, where $C'$ an instance dependent constant. I am not too sure what is the message the authors are trying to convey here, since we know that the state-of-the-art regret lower bound is $\\Omega(\\sqrt{KT})$ for sufficiently large T. \n\nFinally, if I understand the underlying motivation of the authors correctly, the ultimate problem that the authors are trying to address seems to be a stochastic best arm identification problem with (sub-)Gaussian rewards, where an arm here corresponds to a Q-network. I am not sure why the authors resort to EXP type algorithms for a stochastic problem. \n\nMinor Comments:\n\nI believe that the inequality w RL(T) ≥ O(√T · γ ) on page 4 should be \\leq.\n\nIn Algorithm 1, in the initialization, w_i should be replaced by w_i(1).\n\nIn Algorithm 2, it requires to compute  y_k = E[ˆx_{kj} ], and the authors should elaborate on how the expectation is computed.\n\nIn general, there are quite a few typos, and some parts of the writing are  a bit ambiguous in the way they are phrased. I advise the authors to proofread and also polish the writing.", "extra_scores": {}, "extra_text": {}}, {"review_id": "mY9SU72M6-b", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper develops EXP4-style algorithms for Gaussian bandit and RL, proving upper and lower bounds and give empirical evaluations. I have a few questions:\n\n1. I think MAB with unbounded loss is a solved problem? At least these regret bound should be known. For example , see [Hannan consistency in on-line learning in case of unbounded losses under partial monitoring]\n2. The RL part is even more confusing. Say we have n experts:\n(1) when n is big, then we need to maintain n DQN simultaneously, which sounds unrealistic.\n(2) when n is small, as in this paper, a good ensemble can only guarantee you get to match the better one of the two experts.  However, a simple way to do that is to train them and evaluate the policies separately. A lot of technicalities can be avoided this way. So why bother using EXP4?\n3. Actually many existing algorithms, at least in tabular RL, are inspired by EXP4. Indeed, consider the policy gradient method on a MAB, then you get an EXP-style algorithm (of course this also depends on the feedback model). See [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift] for example. More sophisticated ways like the Nash V-learning algorithm in [ Near-Optimal Reinforcement Learning with Self-Play], could be applied to solve competitive RL problems. \n\nOf course, these papers are for tabular RL, which is too simplified. How to use function approximation with EXP4 is an interesting yet challenging question. I think the main weakness of the approaches in this paper is that, it is not clear why exploration with EXP4 is more desirable and why a naive combination with DQN should work. Indeed, I think this comination can be very data inefficient.", "extra_scores": {}, "extra_text": {}}, {"review_id": "CM_0qtnWh6B", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper contributes to the study of EXP-based algorithms in two aspects. One is on the theoretical aspect: It analyzes the lower and upper bounds of EXP-3 for Gaussian multi-bandit setting for which the reward can be unbounded. The other is on the empirical aspect: It applied EXP4, originally developed for MAB, to Rl applications and demonstrated its advanced empirical performance. \n\nThis paper is overall clearly written. However, my general feeling is EXP3 part and EXP4 part are quite separated and have different flavors. Other than both are algorithms in the EXP family, I did not find much connection between them. \n\n\nFor the EXP3P part, I have difficulty to appreciate the value of a linear-in-T lower bound for small T. (And this small T range further depends on bandit setting such as \\mu, q). In fact, the lower bound has in Theorem also involves \\epsilon, which together with T are restricted by an inequality. If I further manipulate the lower bound expression and the required T range, I think it is not hard to obtain quadric or cubic in T lower bound. (One extremal but obviously non-interesting lower bound is  constant*T^n for any  with T<=1).  So I really want to understand why a bound for small T is useful? Even if it is useful, why the order regarding T matters?\n\nThe lower bound part also has some basic conceptual mistakes.  When you study a lower bound, please use \\Omega() or \\Theta() instead of O(). You can say your regret has a lower bound given by \\Theta() or simply say your regret = (or \\in) \\Omega().  But don't say your regret has a lower bound O(), which means nothing. (Technically, T^2 has a lower bound O(T^3) is still correct because T = (or \\in) O(T^3).   Further, big O notation is asymptotical notation, i.e., meaningful only for large T. I don't think you can use O(T) to represent a lower bound for small T. \n\n\nThe experiments only compare Alg 2 with RND. What if you consider a baseline that involve multiple different DQNs and randomizes/explores among them?\n\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper consider a classical multi-armed bandit problem (then a more general RL setting) and prove some upper and lower bounds, in cases that were not explicitly studied in the literature.

However, those results are very incremental and do not justify (maybe yet, going beyond the sub-Gaussian case could be interesting) yet acceptance.
Decision: Reject