    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. 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 BID18 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 BID10 . The essence of the approach is nicely summarized by BID0 : '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 BID10 . Although this idea was successfully applied to the problem when perfect model is accessible, i.e. AlphaGo by BID17 , 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 BID0 . 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 BID13 . 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 BID4 . Posterior sampling for reinforcement learning BID15 ) in Deep RL setting was developed by BID16 . Uncertainty Bellman Equation proposed by BID14 , generalizes Bellman equation to the uncertainty measure. The closest UCB type approach was developed by BID2 . In order to avoid counting authors estimate UCB based on the empirical distribution of the Q function produced by Bootstrapped DQN BID16 ). 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 , ). 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 ) and Quantile Regression DQN (QR-DQN) ) 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 unimodal 2 . 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. Recent advancements in RL, namely Distributional RL, not only established new theoretically sound principles but also achieved state-of-the-art performance in challenging high dimensional environments like Atari 2600. The by-product of the Distributional RL is the empirical PDF for the Q function which is not directly used except for the mean computation. UCB on the other hand is a very attractive exploration algorithm in the multi-armed bandits setting, which does not generalize in a straightforward fashion to Deep RL.In this paper we established the connection between the UCB idea and Distributional RL. We also pointed to the asymmetry of the PDFs estimated by Distributional RL, which is not a rare exception but rather the only case. We introduced truncated variability measure as an alternative to the variance and empirically showed that it can be successfully applied to multi-armed bandits and rich visual environments like Atari 2600. It is highly likely that DQN-QUCB+ might be improved through schedule tuning. DQN-QUCB+ might be combined with other advancements in Deep RL, e.g. Rainbow by BID6 , to yield better results.
Exploration using Distributional RL and truncagted variance. Presents an RL method to manage exploration-explotation trade-offs via UCB techniques. A method to use the distribution learned by Quantile Regression DQN for exploration, in place of the usual epsilon-greedy strategy. Proposes new algorithsms (QUCB and QUCB+) to handle the exploration tradeoff in Multi-Armed Bendits and more generally in Reinforcement Learning