1
$\begingroup$

I am reading about "Iterative Policy Evaluation" algorithm in the context of Reinforcement Learning (http://incompleteideas.net/book/ebook/node41.html). If I have understood this correctly - in a problem that contains multiple "states", this algorithm is used to estimate the "value" of being in any of these states. Once we are able to estimate these "values", we should then be able to study the optimality of selecting different actions to navigate these different states contingent on the state we are currently situated in (i.e. "policies").

For example, consider a problem in which there is there is a grid made of 16 squares. The goal is to reach the "shaded grey squares" by moving "up, down, left and right" (i.e. "actions"):

enter image description here

If we were to use the "Iterative Policy Evaluation" algorithm in this problem, we would be able to estimate the "value" (in this problem, lower values are considered better than higher values) of being in any "square" (i.e. "state"):

enter image description here

This part is understandable so far - the next part is what confuses me. In this particular problem, (after we have used the "Iterative Policy Evaluation" algorithm) we are able to "peak" and see the "value" of all neighboring states relative to the state we are currently in. This means that in the very immediate sense ("greedy"), depending on where we are currently located - we are able to infer which square (i.e. "state") to visit next and which "action" to take next : this is simply done by examining which "neighboring square" has the smallest "value":

enter image description here

This means, we can use the "Iterative Policy Evaluation" algorithm to get a "value map". For instance:

enter image description here

  • If I am in Square 9, the "optimal policy" could be to go "UP, UP, LEFT" or "RIGHT, RIGHT, DOWN" or "UP, LEFT, UP" or "RIGHT, DOWN, RIGHT".

But as the diagram indicates, this is a "greedy policy" - and I am not sure if this "greedy policy" is ALWAYS optimal (i.e. leads to the shaded grey squares in the fewest number of movements). This leads me to my question - how can I be certain that "following the arrows" will ALWAYS lead me to the "shaded squares" in the least number of turns - should I sometimes ignore the arrows?:

  • In problems where there are far more "states" (e.g. 1000 squares), after we have estimated the values of all these states using the "Iterative Policy Evaluation" algorithm: is it possible that sometimes taking "non-greedy actions" (i.e. moving to a neighboring square having a "less-desirable value" than some other neighboring square) might result in you reaching the "shaded grey squares" in fewer movements (i.e. "more optimal") than a "greedy policy"?

  • In other words, is the "Iterative Policy Evaluation" algorithm able to estimate the values of states in such a way, such that : no matter which square you are currently, the greedy policy will always be the "optimal policy" (i.e. take you to the grey shaded squares in the fewest turns)? Or does the "Iterative Policy Evaluation" algorithm only estimate the values of states and the "optimal policy" remains to be determined using some other algorithm?

Thank you!

PS: I am aware of a theorem called the "Policy Improvement Theorem" that has the ability to update and improve the values of the states estimated by the "Iterative Policy Evaluation" - but my question still remains: Even when all states have had their optimal values estimated, will selecting the "greedy policy" at each state necessarily become the "overall optimal policy"? Is it possible that even when all states have had their optimal values estimated, perhaps selecting the policy that leads to the highest reward after "n-steps" instead of "1 step" could be better - or is there some math proof that suggests otherwise?

$\endgroup$

1 Answer 1

1
$\begingroup$

Such an algorithm does not guarantee that you will always arrive at an optimal policy. In only gets you to a local minimum which in general may or may not be the global one.

One can modify your example slightly to see this effect. Suppose that the 4 corners values are not equal in value but have small differences between them but each of them is still better than the inner values. The algorithm you described will still find its way to some corner but whether this is the corner with the lowest value depends on the starting square.

Edit: The text above describes what happens if you go through the search once. If you do this procedure multiple times with different random starting points, eventually you should find the global minimum as well. There is a big difference between theory and practical applications here. In theory you never know whether you have actually found all possible end states and it can take arbitrarily many tries to find the global minimum. In practice most real world problems only have a single local maximum or at most very few so a couple of tries is usually good enough.

$\endgroup$
4
  • $\begingroup$ Thank you for your answer! The "Policy Improvement Theorem" talks about exhaustively re-calculating values of all states (using random actions) until the values of all states converge. I know that this is impractical in real world problems - but wouldn't this in theory guarantee a globally optimal solution? $\endgroup$
    – stats_noob
    May 15, 2022 at 6:32
  • $\begingroup$ In my memory after convergence policy iteration is guaranteed to get a globally optimal solution.... I'm trying to find the reference for it. $\endgroup$ May 15, 2022 at 6:37
  • $\begingroup$ @ Binxu Wang : Thank you for your reply! Let me know if you were able to find the proof. I am still trying to understand the essence of this algorithm. If we iterate enough times, for each square in this example - we can find the "overall best action" to take for being in that square? $\endgroup$
    – stats_noob
    May 15, 2022 at 16:10
  • $\begingroup$ I am having trouble understanding this general idea : after iterative policy evaluation - we now have the luxury of taking the optimal action assigned to each state we are currently in (without consideration of what lies ahead) ... and we will eventually reach the terminal state via the optimal policy by virtue of the "policy improvement theorem"? Once all states have had their optimal values estimated and optimal actions assigned to them, following these optimal actions at each local state will be equivalent to the "overall global optimal policy"? $\endgroup$
    – stats_noob
    May 15, 2022 at 17:21

You must log in to answer this question.

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