This paper studies directed exploration for reinforcement learning agents by tracking uncertainty about the value of each available action. We identify two sources of uncertainty that are relevant for exploration. The first originates from limited data (parametric uncertainty), while the second originates from the distribution of the returns (return uncertainty). We identify methods to learn these distributions with deep neural networks, where we estimate parametric uncertainty with Bayesian drop-out, while return uncertainty is propagated through the Bellman equation as a Gaussian distribution. Then, we identify that both can be jointly estimated in one network, which we call the Double Uncertain Value Network. The policy is directly derived from the learned distributions based on Thompson sampling. Experimental results show that both types of uncertainty may vastly improve learning in domains with a strong exploration challenge.
We also want to note that the exact same exploration problem occurs in classical (tree) search. Succesful Monte Carlo Tree Search (MCTS) algorithms, like Upper Confidence Bounds for Trees (UCT) @cite_10 , act on the upper confidence bound of a frequentist confidence interval of the value at each state-action pair. The overlap between reinforcement learning and (model-based) search has been identified for long @cite_4 , where RL i) does not assume an a-priori known environment model, and ii) usually includes a parametric function approximator to represent the value policy, while search stores these in a tree structure (which is technically an effective sparse form of tabular representation). But besides that, the same exploration themes appear in both fields.
@cite_10 @cite_4
1625390266 2108738385
For large state-space Markovian Decision Problems Monte-Carlo planning is one of the few viable approaches to find near-optimal solutions. In this paper we introduce a new algorithm, UCT, that applies bandit ideas to guide Monte-Carlo planning. In finite-horizon or discounted MDPs the algorithm is shown to be consistent and finite sample bounds are derived on the estimation error due to sampling. Experimental results show that in several domains, UCT is significantly more efficient than its alternatives. Thompson sampling is one of oldest heuristic to address the exploration exploitation trade-off, but it is surprisingly unpopular in the literature. We present here some empirical results using Thompson sampling on simulated and real data, and show that it is highly competitive. And since this heuristic is very easy to implement, we argue that it should be part of the standard baselines to compare against.