Answers.Body: <blockquote>
  <p>in the limit as the number of steps increases</p>
  </blockquote>
  <p>Means for the value we are interested in (number of samples for action <span class="math-container">$a$</span>, let's call that <span class="math-container">$N(a)$</span>), then we want to find</p>
  <p><span class="math-container">$$\lim\limits_{t \to \infty} N(a)$$</span></p>
  <p><span class="math-container">$$ \approx \lim\limits_{t \to \infty} tp(a)$$</span></p>
  <p>Where <span class="math-container">$p(a)$</span> is the probability of taking action <span class="math-container">$a$</span>.</p>
  <p>Provided <span class="math-container">$p(a)$</span> is not zero, the limit for this expression when <span class="math-container">$t$</span> tends to infinity also tends to infinity as it is (on average) a fraction of <span class="math-container">$t$</span>. This also relies on the law of large numbers - the innaccuracy of the approximation becomes smaller relative to the total value as <span class="math-container">$t$</span> increases.</p>
  <p>In an <span class="math-container">$\epsilon$</span>-greedy policy, then this sets a lower bound for <span class="math-container">$p(a)$</span>, and we can use that to set a lower bound of the expected value of <span class="math-container">$N(a)$</span> in the limit of <span class="math-container">$t \to \infty$</span>. Provided you don't set <span class="math-container">$\epsilon = 0$</span>, then this lower bound limit for <span class="math-container">$N(a) \approx \epsilon t$</span> still tends to <span class="math-container">$\infty$</span> along with <span class="math-container">$t$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-12T22:08:15.470Z
Answers.Text: Thank you very much, I misunderstand this part: "in the limit as the number of steps increases". If it is mean time step $t \to \infty$ then everything is clear now.
Answers.UserDisplayName: k2pctdn
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-11T18:58:11.403Z
Answers.LastActivityDate: 2022-11-11T19:10:10.067Z
Answers.LastEditDate: 2022-11-11T19:10:10.067Z
Answers.UserDisplayName: Neil Slater
Body: <p>I am reading the book Reinforcement Learning: An Introduction. Second edition (Richard S. Sutton and Andrew G. Barto). In the k-armed bandit problem using <span class="math-container">$\varepsilon$</span>-greedy selection method, the authors say that</p>
  <blockquote>
  <p>An advantage of these methods is that, in the limit as the number of steps increases,
  every action will be sampled an infinite number of times, thus ensuring that all the <span class="math-container">$Q_t(a)$</span>
  converge to their respective <span class="math-container">$q_*(a)$</span>.</p>
  </blockquote>
  <p>May I ask why &quot;<em>every action will be sampled an infinite number of times</em>&quot; since at each time step <span class="math-container">$t$</span> (for limited time steps), we only select one action <span class="math-container">$A_t = a$</span>?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-11-11T18:47:19.367Z
Comments.Text: Welcome to AI stack exchange. I'm not quite getting what your issue is, and why you are focused on the single action per time step? Can you explain what you understand by the phrase "in the limit as the number of steps increases" from the quote?
Comments.UserDisplayName: Neil Slater
Tags: <reinforcement-learning><sutton-barto><multi-armed-bandits>
Title: Why will every action be sampled an infinite number of times?
UserDisplayName: k2pctdn
ThreadText: # Why will every action be sampled an infinite number of times?
  
  (Asked by: username_0 on 2022-11-11)
  
  I am reading the book Reinforcement Learning: An Introduction. Second edition (Richard S. Sutton and Andrew G. Barto). In the k-armed bandit problem using $\varepsilon$-greedy selection method, the authors say that
  
  > An advantage of these methods is that, in the limit as the number of steps increases,
  > every action will be sampled an infinite number of times, thus ensuring that all the $Q\_t(a)$
  > converge to their respective $q\_\*(a)$.
  
  May I ask why "*every action will be sampled an infinite number of times*" since at each time step $t$ (for limited time steps), we only select one action $A\_t = a$?
  
  **Tags:** reinforcement-learning, sutton-barto, multi-armed-bandits
  > **Comments:**
  > **username_1**: Welcome to AI stack exchange. I'm not quite getting what your issue is, and why you are focused on the single action per time step? Can you explain what you understand by the phrase "in the limit as the number of steps increases" from the quote?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-11-11. Score: 1 | Accepted answer
  
  > in the limit as the number of steps increases
  
  Means for the value we are interested in (number of samples for action $a$, let's call that $N(a)$), then we want to find
  
  $$\lim\limits\_{t \to \infty} N(a)$$
  
  $$ \approx \lim\limits\_{t \to \infty} tp(a)$$
  
  Where $p(a)$ is the probability of taking action $a$.
  
  Provided $p(a)$ is not zero, the limit for this expression when $t$ tends to infinity also tends to infinity as it is (on average) a fraction of $t$. This also relies on the law of large numbers - the innaccuracy of the approximation becomes smaller relative to the total value as $t$ increases.
  
  In an $\epsilon$-greedy policy, then this sets a lower bound for $p(a)$, and we can use that to set a lower bound of the expected value of $N(a)$ in the limit of $t \to \infty$. Provided you don't set $\epsilon = 0$, then this lower bound limit for $N(a) \approx \epsilon t$ still tends to $\infty$ along with $t$.
  
  > **Comments:**
  > **username_0**: Thank you very much, I misunderstand this part: "in the limit as the number of steps increases". If it is mean time step $t \to \infty$ then everything is clear now.  
  
  ---
  
  