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?


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.

  • $\begingroup$ To tell the truth even in a toy problem like windy gridworld it does not require more than 100 states (10*10) for the approach to be infeasible as I have shown. $\endgroup$ – DuttaA Jul 29 '19 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.