Why is On-Policy MC/TD Algorithm guaranteed to converge to optimal policy?

Question

Let's say we have a task where the cost depends entirely on the path length to a terminal state, so the goal of an agent would be to take actions to reach terminal state as quickly as possible.

Now let us say, we know the optimal path length is of length $10$, and there are $n$ such paths possible. Each state has 5 possible actions. Let's say the scheme we are using to find optimal policy is On-Policy MC/TD(n) along with GLIE Policy improvement (Generalised Policy Iteration).

In the first Policy Iteration Step, each actions are equally likely, there for the probability of sampling this optimal path (or the agent discovering this path) is $n* \frac {1}{5^{10}} \approx n* \frac {1}{2^{20}}$. So, according to probability theory we need to sample around $2^{20}/n$ steps to atleast discover one of the best paths (worst case scenario).

Since, it is not possible to go through such huge number of samplings, let's say we do not sample the path, thus in the next Policy Iteration step (after GLIE Policy Improvement) some other sub-optimal path will have a higher probability of being sampled than the optimal path, hence the probability falls even lower. So, like this there is a considerably high probability that we may not find the best path at all, yet theory says we will find $\pi^*$ which indicates the best path.

So what is wrong in my reasoning here?

Answer 1

Your reasoning is fine. GLIE - Greedy in the Limit with Infinite Exploration assumes that our agent does not act greedily all the time. As the number of samples approaches infinity all state-action pairs will be explored -> hence the policy will converge on a greedy policy. The emphasis is on "number of samples approaches infinity". Also for GLIE Monte-Carlo initial values of Q does not matter, since they are replaced after the first update.