Answers.Body: <blockquote>
  <p>Does &quot;optimal action&quot; mean sequence of actions chosen such that in the end total reward is maximized?</p>
  </blockquote>
  <p>No, although that is conceptually related to the optimal policy for reinforcement learning. Chapter 2 is not about the full reinforcement learning problem, it is about bandit problems. As such there is no &quot;sequence of actions&quot; that can be taken. You can repeat the experiment and take lots of actions. But they are not in a sequence, in the sense of there being any dependency between them.</p>
  <p>Instead the &quot;optimal action&quot; is the one that has the highest expected reward. In a simple bandit problem, where no rules about reward change, this is always the same action, and solving the bandit problem involves finding that action. Often there's a side-effect that you want to maximise reward received <em>whilst</em> learning (this is often viewed as &quot;minimising regret&quot; although S&amp;B do not go into that), but that is not important to the paragraph you quoted.</p>
  <p>This sentence from the book is a little clumsy:</p>
  <blockquote>
  <p>This of course implies that the probability of selecting the optimal action converges to greater than 1−, that is, to near certainty.</p>
  </blockquote>
  <p>I take it to mean this:</p>
  <p>In the limit of infinite samples, the estimated values can be arbitarily close to the true expected rewards, thus the greedy action choice will also the optimal action choice, with a probability arbitrarily close to 1.</p>
  <p>Within the <span class="math-container">$\epsilon$</span>-greedy framework, the probabilty of selecting the greedy action is actually <span class="math-container">$1 - \epsilon + \frac{\epsilon}{|A|}$</span>, which is higher then <span class="math-container">$1 - \epsilon$</span>. The extra term appears because when behaving randomly you may still select the greedy action. That's just how the
  <span class="math-container">$\epsilon$</span>-greedy behaviour is defined (you could define it differently)</p>
  <p>I think at the current stage of explanation, the author didn't want to distract with the logically correct probability and maths so just used &quot;greater than <span class="math-container">$1 - \epsilon$</span>&quot; as shorthand.</p>
  <p>The point is that if <span class="math-container">$\epsilon$</span> is relatively small, then in the limit of very large numbers of trials, the basic <span class="math-container">$\epsilon$</span>-greedy framework guarantees close-to-optimal behaviour.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-10-11T17:33:59.563Z
Answers.LastActivityDate: 2024-10-11T17:42:02.733Z
Answers.LastEditDate: 2024-10-11T17:42:02.733Z
Answers.UserDisplayName: Neil Slater
Body: <p>I am reading Reinforcement Learning by Sutton. In chapter 2 they say that:</p>
  <blockquote>
  <p>An advantage of <span class="math-container">$\epsilon$</span>-greedy methods is that, in the limit as the
  number of plays increases, every action will be sampled an infinite number
  of times, guaranteeing that <span class="math-container">$N_t(a)\to \infty$</span> for all <span class="math-container">$a$</span>, and thus ensuring that all
  the <span class="math-container">$Q_t(a)$</span> converge to <span class="math-container">$q(a)$</span>. This of course implies that the probability of selecting
  the optimal action converges to greater than <span class="math-container">$1 − \epsilon$</span>, that is, to near
  certainty.</p>
  </blockquote>
  <p>Does &quot;optimal action&quot; mean sequence of actions chosen such that in the end total reward is maximized?</p>
  <p>Also how to mathematically see that whatever optimal action means, it is implied by <span class="math-container">$\epsilon-$</span>greedy method that the probability of selecting optimal action converges to some quantity greater than <span class="math-container">$1- \epsilon$</span>?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-10-11T15:12:35.997Z
Comments.Text: oh wait is it just that at some step the probability that a non optimal action is chosen is $\epsilon$ and thus the probability that the best action is chosen is $1 - \epsilon$.
  And optimal action means at given step the action which has highest expected reward.
Comments.UserDisplayName: Debu
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-10-11T16:54:05.650Z
Comments.Text: Hello, and welcome to AI Stack Exchange! This post seems to have 2 different questions being asked. To help you get a faster answer to each question, it is recommended that you ask these two questions in separate posts. See the 'needs more focus' section of <https://ai.stackexchange.com/help/closed-questions> for more details. Thank you for joining, and we hope to see more of your questions here soon!
Comments.UserDisplayName: DeepQZero
Tags: <reinforcement-learning>
Title: The probability of selecting optimal action
UserDisplayName: Debu
ThreadText: # The probability of selecting optimal action
  
  (Asked by: username_0 on 2024-10-11)
  
  I am reading Reinforcement Learning by Sutton. In chapter 2 they say that:
  
  > An advantage of $\epsilon$-greedy methods is that, in the limit as the
  > number of plays increases, every action will be sampled an infinite number
  > of times, guaranteeing that $N\_t(a)\to \infty$ for all $a$, and thus ensuring that all
  > the $Q\_t(a)$ converge to $q(a)$. This of course implies that the probability of selecting
  > the optimal action converges to greater than $1 − \epsilon$, that is, to near
  > certainty.
  
  Does "optimal action" mean sequence of actions chosen such that in the end total reward is maximized?
  
  Also how to mathematically see that whatever optimal action means, it is implied by $\epsilon-$greedy method that the probability of selecting optimal action converges to some quantity greater than $1- \epsilon$?
  
  **Tags:** reinforcement-learning
  > **Comments:**
  > **username_0**: oh wait is it just that at some step the probability that a non optimal action is chosen is $\epsilon$ and thus the probability that the best action is chosen is $1 - \epsilon$. And optimal action means at given step the action which has highest expected reward.  
  > **username_1**: Hello, and welcome to AI Stack Exchange! This post seems to have 2 different questions being asked. To help you get a faster answer to each question, it is recommended that you ask these two questions in separate posts. See the 'needs more focus' section of <https://ai.stackexchange.com/help/closed-questions> for more details. Thank you for joining, and we hope to see more of your questions here soon!  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2024-10-11. Score: 3
  
  > Does "optimal action" mean sequence of actions chosen such that in the end total reward is maximized?
  
  No, although that is conceptually related to the optimal policy for reinforcement learning. Chapter 2 is not about the full reinforcement learning problem, it is about bandit problems. As such there is no "sequence of actions" that can be taken. You can repeat the experiment and take lots of actions. But they are not in a sequence, in the sense of there being any dependency between them.
  
  Instead the "optimal action" is the one that has the highest expected reward. In a simple bandit problem, where no rules about reward change, this is always the same action, and solving the bandit problem involves finding that action. Often there's a side-effect that you want to maximise reward received *whilst* learning (this is often viewed as "minimising regret" although S&B do not go into that), but that is not important to the paragraph you quoted.
  
  This sentence from the book is a little clumsy:
  
  > This of course implies that the probability of selecting the optimal action converges to greater than 1−, that is, to near certainty.
  
  I take it to mean this:
  
  In the limit of infinite samples, the estimated values can be arbitarily close to the true expected rewards, thus the greedy action choice will also the optimal action choice, with a probability arbitrarily close to 1.
  
  Within the $\epsilon$-greedy framework, the probabilty of selecting the greedy action is actually $1 - \epsilon + \frac{\epsilon}{|A|}$, which is higher then $1 - \epsilon$. The extra term appears because when behaving randomly you may still select the greedy action. That's just how the
  $\epsilon$-greedy behaviour is defined (you could define it differently)
  
  I think at the current stage of explanation, the author didn't want to distract with the logically correct probability and maths so just used "greater than $1 - \epsilon$" as shorthand.
  
  The point is that if $\epsilon$ is relatively small, then in the limit of very large numbers of trials, the basic $\epsilon$-greedy framework guarantees close-to-optimal behaviour.
  
  
  ---
  
  