2
$\begingroup$

In Sutton and Barto's book (Reinforcement learning: An introduction. MIT press, 2018), the algorithm "Policy Iteration" is: Policy Iteration algorithm

Here, $V(s)$ is initialized arbitrarily, meaning that I can choose anything I want. Moreover, I think nothing is stated about $\gamma$ here so we can consider undiscounted environments where $\gamma = 1$. Now suppose we use the following environment:

MDP2

If I initialize:

  • $V(s_1) = 10$
  • $V(s_2) = 10$
  • $V(s_3) = 0$
  • $\pi(s_1) = a_1$
  • $\pi(s_2) = a_3$

With this, it appears that the "Policy Evaluation" part will not have any effect and the algorithm will immediately stops, outputing a policy where the optimal actions are $\pi(s_1) = a_1$ and $\pi(s_2) = a_3$. What am I missing ?

EDIT: I made a toy repository to reproduce, if you want to tweak the numbers of point out something I misunderstood: https://github.com/Gregwar/policy_iteration_initialization/blob/master/policy_iteration.py

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ (I think the thing is that $\gamma = 1$ can only be used if all episodes terminate, else it has to be $< 1$. Else the episode returns is not well-defined.) $\endgroup$
    – Gregwar
    Commented Feb 17, 2022 at 13:38

1 Answer 1

Reset to default
1
$\begingroup$

I think you have constructed a bad case for the algorithm as given. You have created an infinite loop and set starting values such that there is no chance for the loop to break out. You have also deliberately set up a starting policy for an episodic problem where the episode cannot terminate.

One simple rule to avoid this is to set $\pi$ to the stochastic equiprobable policy initially (i.e. the first policy will explore all edges of the MDP, making it very hard - maybe impossible - to construct bad cases), and all initial $V$ to $0$. Although these can be set arbitrarily, it is not the user of the solver that normally gets to decide these initialisations, but the person implementing the solver.

So, yes, the algorithm as shown does let you deliberately break it through apparently free choices that are not covered in the book. However, these look like edge cases that were maybe not worth covering in detail. The algorithm works if you pick reasonable arbitrary choices, but defining "reasonable" is fiddly and might distract from the introduction to the topic.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I agree with your second point, but not with the first. If $\gamma < 1$ it seems to always work. I made a toy repository if you want to fiddle with the numbers and/or check if I did something wrong: github.com/Gregwar/policy_iteration_initialization $\endgroup$
    – Gregwar
    Commented Feb 19, 2022 at 11:06
  • $\begingroup$ @Gregwar: You are right, it works. I was forgetting that the update step re-evaluates the bootstrap values to pick the optimal action. As soon as predicted values from evaluation drop below the actual reward received by transitioning to the terminal state, the polciy switches to that final transition. $\endgroup$
    – Neil Slater
    Commented Feb 19, 2022 at 12:13
  • $\begingroup$ @Gregwar I dropped my bullet points as they are not relevant to the take-away, which is "arbitrary" means "person writing solver controls it, and has plenty of free choice", and not literally "works for all values". $\endgroup$
    – Neil Slater
    Commented Feb 19, 2022 at 12:15
  • $\begingroup$ Ok, I see. But I feel like they'd better give slightly more conservative preconditions that works all the time and let the "person writing solver" take advantages of less conservative reality rather than writing "arbitrary", where it is easy to find a counter-example and thus deceptive :-) $\endgroup$
    – Gregwar
    Commented Feb 19, 2022 at 12:27

You must log in to answer this question.

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