Why aren't exploration techniques, such as UCB or Thompson sampling, typically used in bandit problems, used in full RL problems?

Monte Carlo Tree Search may use the above-mentioned methods in its selection step, but why do value-based and policy gradient methods not use these techniques?


Compared to $\epsilon$-greedy (widely used in RL), UCB1 is more computationally expensive, given that, for each action, you need to recompute this upper confidence bound for every time step (or, equivalently, action taken during learning).

To see why, let's take a look at the UCB1 formula

$$ \underbrace{\bar{x}_{j}}_{\text{value estimate}}+\underbrace{\sqrt{\frac{2 \ln n}{n_{j}}}}_{\text{UCB}}, $$ where

  • $\bar{x}_{j}$ is the value estimate for action $j$
  • $n_{j}$ is the number of times action $j$ has been taken
  • $n$ is the total number of actions taken so far

So, at each time step (or new action taken), we need to recompute that square root for each action, which depends on other factors that evolve during learning.

So, the higher time complexity than $\epsilon$-greedy is probably the first reason why UCB1 is not so much used in RL, where interaction with the environment can be the bottleneck. You could argue that this recomputation (for each action) also needs to be done in bandits. Yes, it's true, but, in the RL problem, you have multiple states, so you need to compute value estimates for each action in all states (i.e. the full RL problem is more complex than bandits or contextual bandits).

Moreover, $\epsilon$-greedy is so conceptually simple that everyone can easily implement it in less than $5$ minutes (though this is not really a problem, given that both are simple to implement). Finally, I am not sure how UCB1 would really extend to multiple states (I guess that can be done). I guess you should keep track of $n_j$ for each state separately (I don't know for sure because my experience with UCB1 is only restricted to bandits).

I am currently not familiar with Thompson sampling, but I guess (from some implementations I have seen) it's also not as cheap as $\epsilon$-greedy, where you just need to perform an argmax (can be done in constant time if you keep track of the highest value) or sample a random integer (it's also relatively cheap). There's a tutorial on Thompson sampling here, which also includes a section dedicated to RL, so you may want to read it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.