Answers.Body: <p>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 &quot;state&quot;, and then this requirement turns into only requiring the ability to enumerate actions.</p>
  <p>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 <em>visit counts</em> that are normally used in UCB1 and related approaches.</p>
  <p>There certainly are more advanced exploration techniques for RL than just <span class="math-container">$\epsilon$</span>-greedy though, and some may even resemble / take inspiration from bandit-based approaches. There's an excellent <a href="https://lilianweng.github.io/lil-log/2020/06/07/exploration-strategies-in-deep-reinforcement-learning.html#count-based-exploration" rel="nofollow noreferrer">blog post on Exploration Strategies in Deep Reinforcement Learning here</a>. For example, you may think of some of the <a href="https://lilianweng.github.io/lil-log/2020/06/07/exploration-strategies-in-deep-reinforcement-learning.html#count-based-exploration" rel="nofollow noreferrer">approaches described under &quot;Count-based Exploration&quot;</a> as trying to solve the issue of tracking visit counts as I described above in settings with function approximation.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-11T19:24:18.933Z
Answers.LastActivityDate: 2021-02-11T19:24:18.933Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <p>In fact, I think that the formula can be used as it is for multi-state problems.</p>
  <p>However, the formula probably overlaps with adjusting the reward bias because it considers the bias of the true expected value for a particular situation.</p>
  <p>Rather, this makes learning unstable, so I think it is not used.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-24T00:39:42.857Z
Answers.LastActivityDate: 2021-01-24T00:39:42.857Z
Answers.UserDisplayName: ground clown
Answers.Body: <p>You can indeed use UCB in the RL setting. See e.g. section <a href="https://tor-lattimore.com/downloads/book/book.pdf#page=530" rel="nofollow noreferrer"><strong>38.5 Upper Confidence Bounds for Reinforcement Learning</strong> (page 521)</a> of the book <a href="https://tor-lattimore.com/downloads/book/book.pdf" rel="nofollow noreferrer">Bandit Algorithms</a> by Csaba Szepesvari and Tor Lattimore for the details.</p>
  <p>However, compared to <span class="math-container">$\epsilon$</span>-greedy (widely used in RL), UCB1 is more computationally expensive, given that, for each action, you need to recompute this upper confidence bound <strong>for every time step</strong> (or, equivalently, action taken during learning).</p>
  <p>To see why, let's take a look at <a href="https://homes.di.unimi.it/cesa-bianchi/Pubblicazioni/ml-02.pdf#page=3" rel="nofollow noreferrer">the UCB1 formula</a></p>
  <p><span class="math-container">$$
  \underbrace{\bar{x}_{j}}_{\text{value estimate}}+\underbrace{\sqrt{\frac{2 \ln n}{n_{j}}}}_{\text{UCB}},
  $$</span>
  where</p>
  <ul>
  <li><span class="math-container">$\bar{x}_{j}$</span> is the value estimate for action <span class="math-container">$j$</span></li>
  <li><span class="math-container">$n_{j}$</span> is the number of times action <span class="math-container">$j$</span> has been taken</li>
  <li><span class="math-container">$n$</span> is the total number of actions taken so far</li>
  </ul>
  <p>So, at each time step (or new action taken), we need to recompute that square root <em>for each action</em>, which depends on other factors that evolve during learning.</p>
  <p>So, the higher time complexity than <span class="math-container">$\epsilon$</span>-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).</p>
  <p>Moreover, <span class="math-container">$\epsilon$</span>-greedy is so conceptually simple that everyone can easily implement it in less than <span class="math-container">$5$</span> minutes (though this is not really a problem, given that both are simple to implement).</p>
  <p>I am currently not familiar with Thompson sampling, but I guess (from some implementations I have seen) it's also not as cheap as <span class="math-container">$\epsilon$</span>-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 <a href="https://web.stanford.edu/%7Ebvr/pubs/TS_Tutorial.pdf" rel="nofollow noreferrer">here</a>, which also includes a section dedicated to RL, so you may want to read it.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-16T00:36:57.387Z
Answers.LastActivityDate: 2021-02-11T18:02:08.677Z
Answers.LastEditDate: 2021-02-11T18:02:08.677Z
Answers.UserDisplayName: nbro
Body: <p>Why aren't exploration techniques, such as UCB or Thompson sampling, typically used in bandit problems, used in full RL problems?</p>
  <p>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?</p>
  
Tags: <reinforcement-learning><multi-armed-bandits><upper-confidence-bound><thompson-sampling><exploration-strategies>
Title: Why aren't exploration techniques, such as UCB or Thompson sampling, used in full RL problems?
UserDisplayName: Mika
ThreadText: # Why aren't exploration techniques, such as UCB or Thompson sampling, used in full RL problems?
  
  (Asked by: username_0 on 2020-11-15)
  
  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?
  
  **Tags:** reinforcement-learning, multi-armed-bandits, upper-confidence-bound, thompson-sampling, exploration-strategies
  
  ---
  
  ## 3 answers
  
  ### Answer by username_3 on 2020-11-16. Score: 4 | Accepted answer
  
  You can indeed use UCB in the RL setting. See e.g. section [**38.5 Upper Confidence Bounds for Reinforcement Learning** (page 521)](https://tor-lattimore.com/downloads/book/book.pdf#page=530) of the book [Bandit Algorithms](https://tor-lattimore.com/downloads/book/book.pdf) 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](https://homes.di.unimi.it/cesa-bianchi/Pubblicazioni/ml-02.pdf#page=3)
  
  $$
  \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](https://web.stanford.edu/%7Ebvr/pubs/TS_Tutorial.pdf), which also includes a section dedicated to RL, so you may want to read it.
  
  
  ---
  
  ### Answer by username_1 on 2021-02-11. Score: 3
  
  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](https://lilianweng.github.io/lil-log/2020/06/07/exploration-strategies-in-deep-reinforcement-learning.html#count-based-exploration). For example, you may think of some of the [approaches described under "Count-based Exploration"](https://lilianweng.github.io/lil-log/2020/06/07/exploration-strategies-in-deep-reinforcement-learning.html#count-based-exploration) as trying to solve the issue of tracking visit counts as I described above in settings with function approximation.
  
  
  ---
  
  ### Answer by username_2 on 2021-01-24. Score: 0
  
  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.
  
  
  ---
  
  