Why will every action be sampled an infinite number of times?

Question

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$?

Answer 1

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$.