1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ Nov 11, 2022 at 18:47

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – k2pctdn
    Nov 12, 2022 at 22:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .