Title: EXPLORATION USING DISTRIBUTIONAL RL AND UCB

Abstract: We establish the relation between Distributional RL and the Upper Confidence Bound (UCB) approach to exploration. In this paper we show that the density of the Q function estimated by Distributional RL can be successfully used for the estimation of UCB. This approach does not require counting and, therefore, generalizes well to the Deep RL. We also point to the asymmetry of the empirical densities estimated by the Distributional RL algorithms like QR-DQN. This observation leads to the reexamination of the variance's performance in the UCB type approach to exploration. We introduce truncated variance as an alternative estimator of the UCB and a novel algorithm based on it. We empirically show that newly introduced algorithm achieves better performance in multi-armed bandits setting. Finally, we extend this approach to high-dimensional setting and test it on the Atari 2600 games. New approach achieves better performance compared to QR-DQN in 26 of games, 13 ties out of 49 games.
1 Proved by Hoeffding (1963) 

1. INTRODUCTION:

Exploration is a long standing problem in Reinforcement Learning (RL). It's been the main focus of the multi-armed bandits literature. Here the algorithms are easier to design and analyze. However, these solutions are quite unfeasible for high dimensional Deep RL setting, where the complication comes from the presence of the function approximator.

The multi-armed bandit can be represented by a slot machine with several arms. Each arms' expected reward is unknown to the gambler. Her/his goal is to maximize cumulative reward by pulling bandit's arms. If the true expected rewards are known, then the best strategy is to pull the arm with the highest value. However, gambler only observes stochastic reward after the arm is pulled. One possible solution described by Sutton et al. (1998) is to initialize values of arms' estimated means optimistically and then improve the estimates by pulling the same arm again. Arm with a lower true mean will get its estimate decreased over time. Eventually, the best arm will be discovered. The drawback is that the set of the arms has to be enumerated and every arm has to be pulled infinitely many times. In the RL setting an arm corresponds to a state-action pair, which implies that both assumptions are too strong for the Deep RL.

Another line of reasoning is Upper Confidence Bound (UCB) type algorithms, e.g. UCB-1, introduce by Kocsis & Szepesvári (2006) . The essence of the approach is nicely summarized by Audibert et al. (2009) : 'optimism in the face of uncertainty principle'. The idea is statistically intuitive: pull the arm which has the highest upper confidence bound, hoping for a better mean. Estimation of the arm's UCB is performed via Hoeffdings Inequality 1 which is entirely based on counting the number of times the arm was pulled. UCB extends to the tree search case in the form of UCT developed by Kocsis & Szepesvári (2006) . Although this idea was successfully applied to the problem when perfect model is accessible, i.e. AlphaGo by Silver et al. (2016) , it does not generalize in a straightforward fashion to the general Deep RL setting without perfect model. The main obstacle is the requirement of counting of the state-action pairs. Another popular variation is UCB-V introduced by Audibert et al. (2009) . It estimates UCB via the empirical variance, which again involves counting. Therefore, the requirement of counting prevents UCB ideas from successful generalization to the high dimensional setting of Deep RL.

The generalization of exploration ideas from multi-armed bandits to Deep RL is challenging. Therefore, one the most popular exploration approaches in Deep RL is the annealed epsilon greedy approach popularized by Mnih et al. (2015) . However, epsilon greedy approach is not very efficient, especially in Deep RL. It does not take into account the underlying structure of the environment. Therefore, researchers have been looking for other more efficient ways of exploration in Deep RL setting. For example the idea of parametric noise was explored by Fortunato et al. (2017) . Posterior sampling for reinforcement learning (Osband et al. (2013) ) in Deep RL setting was developed by Osband et al. (2016) . Uncertainty Bellman Equation proposed by O'Donoghue et al. (2017) , generalizes Bellman equation to the uncertainty measure. The closest UCB type approach was developed by Chen et al. (2017) . In order to avoid counting authors estimate UCB based on the empirical distribution of the Q function produced by Bootstrapped DQN (Osband et al. (2016) ). The approach reduces to estimating an ensemble of randomly initialized Q functions. According to the averaged human normalized learning curve the performance improvement was insignificant. Currently, there is a much better approach to estimating empirical distributions of Q function, i.e. distributional RL (Bellemare et al. (2017) , Dabney et al. (2017) ). The results in the distributional RL are both theoretically sound and achieve state of the art performance in Deep RL environments, like Atari 2600. However, we should note that Distributional RL does not use the whole distribution, but only the mean.

Another important characteristic of Distributional RL is that both C51 (Bellemare et al. ( 2017)) and Quantile Regression DQN (QR-DQN) (Dabney et al. (2017) ) are non parametric in the sense that the estimated distribution is not assumed to belong to any specific parametric family. Hence, it is not assumed to be symmetric or even unimodal2 . We argue that in the case of asymmetric distributions, variance might become less sensitive in estimating UCB. This problem seems to be overseen by the existing literature. However, this issue might become more important in a more general setting, when symmetric assumption is not simply relaxed but is a very rare case. We empirically show in the Section 4 that symmetry is in fact rare in Distributional RL.

In this paper we build upon generic UCB idea. We generalize it to the asymmetric distributions and high-dimensional setting. In order to extend UCB approach to asymmetric distributions, we introduce truncated variability measure and show empirically that it achieves higher performance than variance in bandits setting. Extension of this measure to rich visual environments provided by Atari 2600 platform is based on recent advances in Distributional RL.

2. BACKGROUND:



2.1. UCB:

As it was mentioned in the introduction UCB is based on the statistical relation between the number of observations of a random variable and the tightness of the mean estimates based on these observations. More formally the connection is provided the inequality proved by Hoeffding (1963) :

Theorem 1 (Hoeffdings Inequality) Let X 1 , . . . X t be independent random variables bounded by

EQUATION

Therefore, Theorem 1 quantifies the relation between upper confidence bound for X and the number of realizations of X. On the other hand if the estimate of the probability density function (PDF) is available, then UCB can be estimated directly:

X ≤ µ + c √ σ2 (2)

where σ2 is the variance computer from P (X) and c is a constant reflecting the confidence level. Now the question is how to estimate the empirical PDF. Bayes-UCB introduced by Kaufmann et al.

(2012) uses restricted family of distributions which allows for the closed form Bayesian update.

On the other hand it is possible to model P [X] in a more expressive way using Neural Networks as it is done in the Distributional RL. We lose closed form solutions, but gain more realistic estimates of the underlying distribution. In this paper we explore Quantile Regression approach towards Distributional RL, which we introduce next.

2.2. DISTRIBUTIONAL RL:

The core idea behind QR-DQN is the Quantile Regression introduced by Koenker & Bassett Jr (1978) . Let us first describe QR in the supervised machine learning setting. Given data {(y i , x i )} i , τ -th linear quantile regression loss is defined as:

EQUATION

where

ρ τ (u) = u(τ -I u<0 ) = τ |u|I u≥0 + (1 -τ )|u|I u<0 (4)

is the weighted sum of residuals. Weights are proportional to the counts of the residual signs and order of the estimated quantile τ . For higher quantiles positive residuals get higher weight and vice versa. If τ = 0.5, then the estimate of the median for

y i is Q 0.5 (y i |x i ) = x i β, with β = arg min L(β).

Dabney et al. ( 2017) introduced QR in a more general setting of RL with function approximator. The design of the neural network is the same as in the original DQN introduced by Mnih et al. (2015) except for the last linear layer, which outputs N quantiles {θ i } i instead of the a single estimate of Q. For a given transition (x, a, r, x ) and a discount factor γ the Bellman update is:

EQUATION

Note the similarity between loss in 3 and Algorithm 1. The difference is in the type of the function approximator: linear in the former and neural network in the later. This work is closely related to that of Bellemare et al. ( 2017) with a major contribution in the way the empirical distribution is estimated. Bellemare et al. ( 2017) use Boltzmann distribution in conjunction with a projection step. QR-DQN seems to be a more elegant solution, since it does not involve the projection step and and there is no need for explicitly bounding the support.

It is worth emphasizing that function approximator in this case is crucial for generalization of UCB approach to DeepRL, since it eliminates the need for state-action pair counting.

Algorithm 1 Quantile Regression Q-learning

Input: w, w -, (x, a, r, x ), γ ∈ [0, 1) network weights, sampled transition, discount factor 1: Q(x , a ) = j q j θ j (x , a ; w -)

2: a * = arg max a Q(x, a ) 3: T θ j = r + γθ j (x , a * ; w -) 4: L(w) = i 1 N j [ρ τi (T θ j -θ i (x, a; w))] 5: w = arg min w L(w) Output: w Updated weights of θ()

3. ALGORITHM:

QR approach allows for a very elegant estimation of distributions in the RL setting. We apply this idea to the multi-armed bandits. This environment is more tractable and easier to explore. Since the distributions are not assumed to have any regularities, like symmetry, we conjecture that variance might not the best UCB measure. Therefore, we explore truncated variability measure. We, then, generalize this idea to the Deep RL setting.

3.1. QUCB:

We propose to estimate empirical distribution of returns for each arm by the means of the QR. The basic idea is to estimate mean and variance of the return for each arm based on the empirical distribution provided by QR and pick the arm according to the highest mean plus standard deviation. We call this algorithm QUCB.

In the setting of multi-armed bandits denote quantiles by {θ i } i and observed reward for by R. Then for a single arm the set of estimates of quantiles is the solution to:

EQUATION

As opposed to the supervised example there are no features x i . Algorithm 2 outlines the QUCB. Note the definitions of θt,k and V ar(θ t,k ):

EQUATION

V ar(θ

t,k ) = 1 N N i=1 ( θt,k -θ t,k,i ) 2 (8)

Note the presence of the multiplier c t in the Algorithm 2. To ensure the optimality in the limit t → ∞, {c t } t have to be chosen so that lim t→∞ c t = 0. In case the number of quantiles is big compared to the sample size, it might help to warm-up the initial estimates by performing a few steps of pure exploration ( = 1).

Hence, the algorithm estimates empirical quantiles. QR approach allows to estimate any quantile.

In fact it allows to estimate multiple quantiles in one update step producing empirical density. More importantly, having empirical distribution at hand opens up the way for new possible approaches to computing upper confidence bound, exploration bonuses or some other means of ordering empirical distributions when choosing action/arm. One such approach is developed in the next section.

Algorithm 2 QUCB

Input: {θ 0,k,i } k,i , N, α, {c t } t

Initial values, number of quantiles, learning rate, schedule 1: for t in [0, number of runs] do 2:

if t ≤ number of burn-in steps then 3:

I t ∼ U nif orm(K)

Pick an arm randomly 4:

else 5:

I t = arg max k { θt,k + c t V ar(θ t,k )} 6: end if 7: draw reward R t 8: θ t+1,It,i = θ t,It,i + α∇ θ i ρ τi (θ t,It,i -R t )

Update quantiles of the corresponding arm 9: end for 3.2 ASSYMETRY, TRUNCATED MEASURES, QUCB+

In the case of non parametric approaches or parametric approaches that are not exclusively restricted to symmetric distributions the symmetry is not guaranteed. In fact, it might be a very rare case as it can be seen from Figure 1 . Note that the game of Pong from Atari 2600 is the simplest one. In the end of training presented in Figure 1 , agent achieves almost the perfect score. Hence the distributions in the end of training correspond to the near optimal policy and these distributions are not symmetric. That is, the asymmetry of empirical distributions is the regular case, but not an exception. Hence, the question: is the variance a 'good' measure of the upper confidence bound for asymmetric distributions in the setting of multi-armed bandits and RL?

For the sake of the argument consider a simple decomposition of the variance into the two truncated variability measures: lower and upper variance3 :

V ar(X) = 1 N N i=1 ( X -X i ) 2 = 1 2N 1 2N i=1 ( X -X i ) 2 + 1 2N N i= 1 2N ( X -X i ) 2 = σ 2 l + σ 2 u (9)

It is clear that in the case of a symmetric probability density function (PDF) the lower and upper variances are equivalent. However, in the case of asymmetric distribution the equality σ 2 l = σ 2 u does In case of the UCB type approach to the exploration problem upper tail variability seem to be more relevant than lower tail one, especially if the estimated PDF is asymmetric. Intuitively speaking, σ 2 u is an optimistic measure of variability. σ 2 u is biased towards rare 'positive' rewards. However, the availability of empirical PDF makes it possible to truncate the variance in many different ways. σ 2 u might be a good candidate, although one potential draw back is the robustness of the estimator of the mean. In order to mitigate that, we propose the following truncated measure of the variability based on the median rather than the mean5 :

σ 2 + = 1 2N N i= N 2 ( θ -θ i ) 2 (10)

where θ i 's are i N -th quantiles. As opposed to σ 2 u , σ 2 + captures some 'negative' variability but still being optimistic.

We propose QUCB+, the algorithm based on σ 2 + which is a slight modification of QUCB. Instead of the V ar(θ t,k ) we propose to use σ 2 + . We hypothesize that σ 2 + might be a more robust upper tail variability measure. We support our hypothesis by empirical results in multi-armed bandits setting and Atari 2600, presented in Section 4.

3.3. DQN-QUCB+:

The ideas presented in the previous section generalize in a straightforward fashion to the tabular RL and most importantly to the Deep RL setting. As it was mentioned QR-DQN's output is the quantile distribution with equispaced quantiles: { i N } N i=1 . The update step does not change. Action selection step incorporates bias in the form of σ 2 + from Equation 10. Algorithm 3 outlines DQN-QUCB+. In the presence of the function approximator the variance encoded in the θ i is largely effected by the variation in the parameters. Therefore, the variance produced by QR-DQN has at least two sources: intrinsic variation coming from the underlying MDP and parametric variation. The important question is the dynamics of the parametric uncertainty during training. As it can be seen from Figure 1 the variance drops significantly meaning that the parametric uncertainty goes down as the network approaches optimal solution. Hence, if the model tends to learn then the parametric component in the variance decreases.

Algorithm 3 DQN-QUCB+ Input: w, w -, (x, a, r, x ), γ ∈ [0, 1) network weights, sampled transition, discount factor 1: Q(x , a ) = j q j θ j (x , a ; w -) 

2: a * = arg max a (Q(x, a ) + c t σ 2 + ) 3: T θ j = r + γθ j (x , a * ; w -) 4: L(w) = i 1 N j [ρ τi (T θ j -θ i (x

4. EXPERIMENTS:



4.1. MULTI-ARMED BANDITS:

Following Sutton et al. (1998) we applied QUCB and QUCB+ to the multi-armed bandits test bed. In order to study the effect of asymmetric distributions we set up two configurations of the test bed: with normally and asymmetrically distributed rewards. Both configurations consist of 10 arms. In both configurations true means of arms {µ i } K k=1 are drawn from the normal distribution with µ = 1, σ = 1.

In the first configuration. During each step the the reward for the k-th arm is drawn from N (µ k , 1). As it can be seen from 2 there is no statistically significant difference between QUCB and QUCB+. It is expected, since the the rewards are normally distributed, hence, symmetric around the mean. In addition median and mean of the normal distribution coincide. Therefore, estimate of σ 2 is close to that of σ 2 + . In the second configuration the reward for the best arm is drawn from the lognormal distribution centered at µ k and variance 1. And the rewards for other arms are drawn from the reflected about µ k lognormal distribution with variance one. Hence true variances of all arms are the same, however in the presence of slight asymmetry QUCB+ performs better, see Figure 2 .

4.2. ATARI 2600:

As it was claimed earlier in the paper the QUCB generalizes to the Deep RL setting in the straightforward fashion. The architecture of the network is that of QR-DQN. Dabney et al. (2017) experimented with two losses: the original QR loss and Huber loss with κ = 1. Both architectures proved to be stable. For our experiments we chose only one loss: the Huber loss with κ = 16 , due to high computational costs of experiments. Another reason for picking the Huber loss is its smoothness compared to L1 loss of QR. Smoothness is better suited for gradient descent methods. Overall, we followed closely Dabney et al. (2017) in setting the hyper parameters, except for the learning rate of the Adam optimizer which we set to α = 0.0001.

The most significant distinction is the way the exploration is performed in DQN-QUCB. As opposed to QR-DQN there is no epsilon greedy exploration schedule in DQN-QUCB. The exploration is performed via the σ 2 + term only. An important hyper parameter which is introduced by DQN-QUCB is the schedule, i.e. the sequence of multipliers for σ 2 + , {c t } t . The choice depends on the specific problem. In case of the stationary environment the UCB term involving σ 2 + should eventually vanish, i.e. c t → ∞. In the non stationary environment the agent might always need to explore, so that c t is eventually a constant7 .

In our experiments we used the following schedule:

EQUATION

The motivation behind the schedule is to gradually vanish the exploration term as it is done in QR-DQN. This makes performance comparison more adequate. During experiments we observed that DQN-QUCB is sensitive to the schedule to some extent, see for example Figure 3 . We conjecture that tuning the schedule might yield better performance across games.

We evaluated DQN-QUCB on the set of 49 Atari games initially proposed by Mnih et al. (2015) . 

:

See analysis byBellemare et al. (2017).

In case N is odd, partition indexes into lower and upper sets as {1, N 2 }, { N 2 . . . N }.

Consider discrete empirical distribution with support {-1, 0, 2} and probability atoms { 1 3 , 1 3 , 1 3 }.

For details seeHuber (2011), Hampel et al. (2011)

QR-DQN with κ = 1 is denoted as QR-DQN-1 in the work byDabney et al. (2017). We use QR-DQN and QR-DQN-1 interchangeably.

Here by is eventually a constant, we mean ∃T ∀t ≥ T ct = c

Equivalently, 10 million agent steps.

We present leaning curves for all 49 games in the Appendix.

Figures and Tables:

Figure 1: Pong. (left) Empirical distributions of the Q function for a single action obtained from QR-DQN-1 during training for 20 millions of frames. y-axis is the training step number. (right) Standard deviation of the empirical distribution of the Q function for a single action.

Figure 2: Comparison of performance of QUCB and QUCB+ in multi-armed bandits with 10 arms. Lines represent averages over 2000 runs, bands are standard errors. (left) The rewards are normally distributed with unit variance. (right) Rewards are drawn from (right-and left-skewed) lognormal distribution with unit variance.

Figure 3: Atari 2600 Venture game. Online training curves for QUCB with vanishing schedule and QUCB with constant schedule. Curves are averaged over 3 runs. Shaded area represents corresponding standard errors.

Figure 5: Online learning curves for DQN-QUCB+ and QR-DQN-1 averaged over 3 runs for 40 millions of frames. Bands represent standard errors.

Peer review (iclr2019):
 This paper proposes new algorithms (QUCB and QUCB+) to handle the exploration exploitation tradeoff in Multi-Armed Bandits and more generally in Reinforcement Learning. The first idea of the paper is to use an Upper Confidence Bound based on the variance estimation rather than an exploration factor based on a concentration inequality such as Hoeffding inequality. The variance estimation is done using Quantile Regression. The second idea of the paper is to adapt the proposed algorithm, QUCB, to the case of asymmetrical distributions. .sigma+ is defined as the standard deviation of the quantiles higher than the median,. .sigma+ isused in place of .sigma in QUCB. Synthetic experiments are done for MAB, and Atari game are used to test DQN-UCB+ for RL. Major concern: The authors claim that the main advantage of QUCB is that no counter is needed to evaluate the Upper Confidence Bound, and therefore that QUCB can be used in RL where the number of state-action pairs is too high to be stored. Indeed, QUCB does not use counts on the number of times each action has been selected. However, the upper confidence bound that is used in QUCB (see eq 2, line 5 of algorithm 2) is not optimistic in face of uncertainty but reckless: the arm, that is selected, is the arm with the highest mean plus standard deviation. The reviewer understands that to obtain an accurate estimate of means, the arms with high variance need to be sampled more than the arms with low variance, as in UCB-V. The reviewer does not understand why equation 2 solves the exploration-exploitation tradeoff. No theoretical analysis of the algorithm is given. No convincing arguments are provided. At a minimum, 1/ the authors have to explain why it could work. May be based on Chebyshev*s inequality or Follow the Perturbed Leader ? 2/ QUCB has to be compared with UCB (Auer et al 2002) in the experiments. 3/ The variance and/or the distribution of arms have to be different in the experiment. Notably it could be interesting to launch an experiment where the best arm has a low variance while the worst arm has an high variance. Minor concerns: Theorem 1 is not used in QUCB, so I suggest removing it. q_j is not defined and not initialized in algorithm 1 and 3. c_t is not defined in algorithm 3. The right reference for UCB is Finite Time Analysis of the Multi-Armed Bandit Problem, P. Auer, N. Cesa-Bianchi, P. Fischer, 2002.