0
$\begingroup$

I've seen this question answered here Why does the policy iteration algorithm converge to optimal policy and value function? and here The proof for policy iteration algorithm's optimality however I'm still unable to connect the dots and I'm not even sure if my question is related. I'm hoping a slightly less mathematical and more intuitive explanation would be possible

I feel I'm making a fundamental mistake in my embarkation into RL. Now, on to my question.

Following Sutton's RL Version 2, Chapter 4, Generalized Iteration Policy is explained:

The value function stabilizes only when it is consistent with the current policy, and the policy stabilizes only when it is greedy with respect to the current value function. Thus, both processes stabilize only when a policy has been found that is greedy with respect to its own evaluation function. This implies that the Bellman optimality equation (4.1) holds, and thus that the policy and the value function are optimal.

Furthermore, the Bellman optimality equation seems to make sense regarding this since the equation specifically lists all states. I can accept this in the event all states are visited after each iteration.

However, when applying GPI to Q-Learning to my own toy problems or even examples from the book, I cannot see how an optimal policy is reached even though both conditions of GPI are satisfied.

Take for example this toy problem:

[5 0 X 0 0 20]

whereby a reward of 5 exists to the extreme left, a reward of 20 to the extreme right, and all other locations a reward of 0. Termination occurs at either end. X indicates the starting location. The agent can move either left or right.

Let's say X explores to the left by a greedy-random policy with no exploration (since the EV is 0 for both left and right it will tie-break). After 3 iterations of moving to the left, it will update its Qtable with values that, under this greedy policy the agent will constantly move to the left. The following are eventually observed -

1) The value function stabilizes in accordance with this greedy policy (ie: values are no longer updated)

2) The policy stabilizes with respect to the value function (ie: the agent will always greedily move left, never anything else).

According to the GPI as far as I understand, this is the definition of the optimal policy. Yet as we can see, moving to the right would provide far better EV and converge on the optimal solution. In fact, if we sum over all states, the agent would solve to always move to the right.

So how come the 2 principles of GPI seem to apply even though this policy isn't optimal? Since I can't see how the agent is ever given a chance to sum over all the states, despite it seemingly matching the definition of the optimal policy?

If someone could explain it with as little math as necessary it would be greatly appreciated, thank you.

$\endgroup$
  • $\begingroup$ This is why you make exploration steps sometimes - so you can learn about regions of the policy space you haven't explored and not get trapped in local maxima. $\endgroup$ – jbowman May 4 at 18:34
  • $\begingroup$ @jobwman Agreed, but simply following the definitions given, this "left only" policy seems to satisfy the GPI definition of the optimal policy? Ie: 1) V no longer updates, 2) Pi always moves in the same direction. I'm curious what I'm missing in that regard. $\endgroup$ – user4779 May 4 at 18:47
  • $\begingroup$ Bellman assumes you actually know the payoffs and transition probabilities; at the point at which you start the exploration, you don't, so there's no guarantee you'll get to the global optimum any more. $\endgroup$ – jbowman May 4 at 18:50
  • $\begingroup$ @jbowman So we could say we have the optimal policy so long as condition 1 & 2 apply, and our exploration is non-zero? $\endgroup$ – user4779 May 4 at 18:54

Your Answer

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

Browse other questions tagged or ask your own question.