Answers.Body: <p>The first thing to note here is that your results seem aligned with the results commonly found in the bandit literature.</p>
  <p>Second thing to note would be that the performance of bandit algorithms is usually measured in terms of <em>regret</em>. This is the difference between (i) the amount of rewards accumulated by an <em>oracle</em> policy having prior knowledge about the <em>true</em> rewards of the bandit arms and (ii) the amount of rewards accumulated by the bandit strategy you are evaluating. In other words, this measures the loss your incur due to not knowing what the optimal arm is.</p>
  <p>Ideally, the regret should be <em>logarithmic</em>. In theory, all three algorithms achieve logarithmic regret.
  See <a href="https://link.springer.com/article/10.1023/A:1013689704352" rel="nofollow noreferrer">[1]</a> for the regret of decaying <span class="math-container">$\epsilon$</span>-greedy and UCB and <a href="http://proceedings.mlr.press/v23/agrawal12/agrawal12.pdf" rel="nofollow noreferrer">[2]</a> for the regret of Thompson sampling.</p>
  <p>Despite their similar regret bounds, these algorithms may behave differently in practice.
  For example, according to experiments in <a href="https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/thompson.pdf" rel="nofollow noreferrer">[3]</a>:</p>
  <blockquote>
  <p>It appears that Thompson
  sampling is more robust than UCB when the delay is long. Thompson sampling alleviates the
  influence of delayed feedback<span class="math-container">$^*$</span> by randomizing over actions; on the other hand, UCB is deterministic
  and suffers a larger regret in case of a sub-optimal choice.</p>
  </blockquote>
  <p>For decaying <span class="math-container">$\epsilon$</span>-greedy, the fact that it obtained the lowest rewards may be due to the fact that the action selected for exploration is chosen <em>uniformly at random</em> (even if it has a bad reward estimate). In addition, it will explore actions even if they have already been selected many times, unlike UCB which considers the number of action selections to refine the confidence bound.</p>
  <p>That said, besides these aspects, there may be other factors that could influence the results obtained by a given bandit algorithm. These may include:</p>
  <ul>
  <li>The reward distributions you chose to model your actions, and their
  characteristics.</li>
  <li>The number of actions you have, and how far each
  action’s reward is from the optimal action’s reward.</li>
  </ul>
  <p><span class="math-container">$^*$</span> Delayed feedback occurs when the outcome of an action selection is not revealed immediately but after some time delay.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-16T08:34:08.777Z
Answers.LastActivityDate: 2020-06-16T08:34:08.777Z
Answers.LastEditDate: 2020-06-17T09:57:20.710Z
Answers.UserDisplayName: user5093249
Body: <p>I ran a test using 3 strategies for multi-armed bandit: UCB, <span class="math-container">$\epsilon$</span>-greedy, and Thompson sampling.</p>
  
  <p>The results for the rewards I got are as follows:</p>
  
  <ol>
  <li>Thompson sampling had the highest average reward</li>
  <li>UCB was second</li>
  <li><span class="math-container">$\epsilon$</span>-greedy was third, but relatively close to UCB</li>
  </ol>
  
  <p>Can someone explain to me why the results are like this?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-15T22:33:17.353Z
Comments.Text: Hi. Just to clarify, in the $\epsilon$-greedy, you used a constant value for $\epsilon$ (if so what was this value?) or did you decay it?
Comments.UserDisplayName: user5093249
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-15T22:41:45.940Z
Comments.Text: for epsilon greedy, epsilon is decayed at each iteration: 1/i, where i is the current iteration
Comments.UserDisplayName: Java coder
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-16T08:13:49.900Z
Comments.Text: What was the problem domain? In general these techniques will sort in effectiveness depending on the problem domain. If it is a test or toy problem, please characterise it (how reward functions were set up). Also, can you give more details of your experiment and clarify what you mean *precisely* by "highest average reward" - there is a large difference in terms of approach when considering reward from start of training, or results after training. The number of training episodes is also a big factor.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-16T10:04:56.823Z
Comments.Text: Please, address Neil's comment by editing your post and adding more details about your problem domain, etc., otherwise, I will not re-open this post.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-16T11:33:06.503Z
Comments.Text: Hi @nbro, I see you closed the post. In fact, I agree with Neil's comment, but I've only seen it after finishing typing my answer. Should I delete my answer accordingly?
Comments.UserDisplayName: user5093249
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-16T11:36:25.567Z
Comments.Text: @user5093249 Hi. I didn't fully read your answer, but it looks good. I wouldn't delete it for now. Let's wait a little bit more until the user clarifies his/her question. Maybe your answer will still be valid, as it is. Please, next time, if you find an post that is unclear or needs more details to be answered, you should flag it to be closed. This is a very important work that the community members should do and that rarely do here (on this site). I shouldn't need to close questions. The community should do it. Anyway, thanks for caring about the post and to make the site a better place!
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><multi-armed-bandits><thompson-sampling><upper-confidence-bound><epsilon-greedy-policy>
Title: Why am I getting better performance with Thompson sampling than with UCB or $\epsilon$-greedy in a multi-armed bandit problem?
UserDisplayName: Java coder
ThreadText: # Why am I getting better performance with Thompson sampling than with UCB or $\epsilon$-greedy in a multi-armed bandit problem?
  
  (Asked by: username_0 on 2020-06-15)
  
  I ran a test using 3 strategies for multi-armed bandit: UCB, $\epsilon$-greedy, and Thompson sampling.
  
  The results for the rewards I got are as follows:
  
  1. Thompson sampling had the highest average reward
  2. UCB was second
  3. $\epsilon$-greedy was third, but relatively close to UCB
  
  Can someone explain to me why the results are like this?
  
  **Tags:** reinforcement-learning, multi-armed-bandits, thompson-sampling, upper-confidence-bound, epsilon-greedy-policy
  > **Comments:**
  > **username_1**: Hi. Just to clarify, in the $\epsilon$-greedy, you used a constant value for $\epsilon$ (if so what was this value?) or did you decay it?  
  > **username_0**: for epsilon greedy, epsilon is decayed at each iteration: 1/i, where i is the current iteration  
  > **username_2**: What was the problem domain? In general these techniques will sort in effectiveness depending on the problem domain. If it is a test or toy problem, please characterise it (how reward functions were set up). Also, can you give more details of your experiment and clarify what you mean *precisely* by "highest average reward" - there is a large difference in terms of approach when considering reward from start of training, or results after training. The number of training episodes is also a big factor.  
  > **username_3**: Please, address Neil's comment by editing your post and adding more details about your problem domain, etc., otherwise, I will not re-open this post.  
  > **username_1**: Hi @nbro, I see you closed the post. In fact, I agree with Neil's comment, but I've only seen it after finishing typing my answer. Should I delete my answer accordingly?  
  > **username_3**: @user5093249 Hi. I didn't fully read your answer, but it looks good. I wouldn't delete it for now. Let's wait a little bit more until the user clarifies his/her question. Maybe your answer will still be valid, as it is. Please, next time, if you find an post that is unclear or needs more details to be answered, you should flag it to be closed. This is a very important work that the community members should do and that rarely do here (on this site). I shouldn't need to close questions. The community should do it. Anyway, thanks for caring about the post and to make the site a better place!  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-06-16. Score: 3
  
  The first thing to note here is that your results seem aligned with the results commonly found in the bandit literature.
  
  Second thing to note would be that the performance of bandit algorithms is usually measured in terms of *regret*. This is the difference between (i) the amount of rewards accumulated by an *oracle* policy having prior knowledge about the *true* rewards of the bandit arms and (ii) the amount of rewards accumulated by the bandit strategy you are evaluating. In other words, this measures the loss your incur due to not knowing what the optimal arm is.
  
  Ideally, the regret should be *logarithmic*. In theory, all three algorithms achieve logarithmic regret.
  See [[1]](https://link.springer.com/article/10.1023/A:1013689704352) for the regret of decaying $\epsilon$-greedy and UCB and [[2]](http://proceedings.mlr.press/v23/agrawal12/agrawal12.pdf) for the regret of Thompson sampling.
  
  Despite their similar regret bounds, these algorithms may behave differently in practice.
  For example, according to experiments in [[3]](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/thompson.pdf):
  
  > It appears that Thompson
  > sampling is more robust than UCB when the delay is long. Thompson sampling alleviates the
  > influence of delayed feedback$^\*$ by randomizing over actions; on the other hand, UCB is deterministic
  > and suffers a larger regret in case of a sub-optimal choice.
  
  For decaying $\epsilon$-greedy, the fact that it obtained the lowest rewards may be due to the fact that the action selected for exploration is chosen *uniformly at random* (even if it has a bad reward estimate). In addition, it will explore actions even if they have already been selected many times, unlike UCB which considers the number of action selections to refine the confidence bound.
  
  That said, besides these aspects, there may be other factors that could influence the results obtained by a given bandit algorithm. These may include:
  
  * The reward distributions you chose to model your actions, and their
    characteristics.
  * The number of actions you have, and how far each
    action’s reward is from the optimal action’s reward.
  
  $^\*$ Delayed feedback occurs when the outcome of an action selection is not revealed immediately but after some time delay.
  
  
  ---
  
  