3
$\begingroup$

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?

$\endgroup$
0
3
$\begingroup$

You can indeed use UCB in the RL setting. See e.g. section 38.5 Upper Confidence Bounds for Reinforcement Learning (page 521) of the book Bandit Algorithms by Csaba Szepesvari and Tor Lattimore for the details.

However, 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).

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.

$\endgroup$
3
$\begingroup$

Many techniques for the exploration/exploitation dilemma that are inspired by multi-armed bandit problems, such as UCB1, assume that you can explicitly enumerate all state-action pairs; in fact, multi-armed bandit problems usually only have just one "state", and then this requirement turns into only requiring the ability to enumerate actions.

In RL problems that are small enough to be handled with tabular approaches (without any function approximation), this may still be feasible. But for many interesting RL problems, the state and/or action spaces grow so large that you have to use function approximators (Deep Neural Networks are a popular choice, but others exist too). When you are unable to enumerate your state-action space, you can no longer keep track of things like the visit counts that are normally used in UCB1 and related approaches.

There certainly are more advanced exploration techniques for RL than just $\epsilon$-greedy though, and some may even resemble / take inspiration from bandit-based approaches. There's an excellent blog post on Exploration Strategies in Deep Reinforcement Learning here. For example, you may think of some of the approaches described under "Count-based Exploration" as trying to solve the issue of tracking visit counts as I described above in settings with function approximation.

$\endgroup$
0
$\begingroup$

In fact, I think that the formula can be used as it is for multi-state problems.

However, the formula probably overlaps with adjusting the reward bias because it considers the bias of the true expected value for a particular situation.

Rather, this makes learning unstable, so I think it is not used.

$\endgroup$

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.