# What is Policy Iteration in RL?

Consider the Gridworld problem in RL. Formally, policy in RL is defined as $$\pi(a|s)$$. If we are solving Gridworld by Policy Iteration then the following pseudocode is used:

Now the question is in the Policy Improvement step I can have 2 interpretations of the second step in the for loop:

$$\pi(s) \leftarrow arg max_a \sum_{s'}p(s'|s,a)[r(s,a,s') + \gamma v(s')]$$

1. In this step we check which action (Say going right for a particular state) has the highest reward and assign going right a probability of 1 and rest actions a probability of 0. Thus in PE step we will always go right for all iterations for that state even if it might not be the most rewarding function after certain iterations.
2. We keep the Policy Improvement step in mind and while doing the PE step we update sthe $$v(s)$$ based on the action giving highest reward (say for 1st iteration $$k=0$$ going right gives highest reward we update based on that while for $$k=1$$ we see going left gives highest reward and update our value based on that likewise. Thus action changes depending on Maximum reward.

For me the second interpretation is very similar to Value Iteration. So which one is the correct Interpretation of a Policy Iteration?

• Your first interpretation is correct, in policy evaluation step, every loop iteration you act considering the current fixed policy that you think is the best, that policy may not be the overall best policy, but currently we think it is. You learn about how good that policy is by updating values (while acting according to our current policy) and then you improve it in policy improvement step based on those values that you got in PE step. – Brale_ May 12 at 15:29
• @Brale_ The first interpretation is wrong. You don't necessarily always go "right" for all iterations of a single PE step. The greedy action might change, after each PE step. I also clarify in my answer that the greedy action might not be the same for all states, so you don't necessarily go "right" for all states (during a single run of PE or, equivalently, for different iterations of the same PI step). – nbro May 12 at 15:31
• @nbro greedy action changes after policy improvement step (hence the name improvement), in policy evaluation you evaluate your current policy, action that you choose for specific state doesn't change in every loop iteration of policy evaluation step – Brale_ May 12 at 15:33
• @Brale_ Yes, even though there might not be a strict improvement for all states in PI. However, note that in the OP stated "Thus in PE step we will always go right for all iterations even if it might not be the most rewarding function after certain iterations.". To me this seems to imply that $\pi(s)$ is "right" for all states, but this is not necessarily the case. Maybe I am just wrongly interpreting this statement, which is ambiguous. – nbro May 12 at 15:35
• there might be a misunderstanding, I thought the OP was saying that we act according to our current policy in states, obviously if an action for $s_1$ is going right it would be incorrect going right in $s_2$, unless that is the greedy action for that state – Brale_ May 12 at 15:37

A policy can be stochastic or deterministic. A deterministic policy is a function of the form $$\pi_{\text{deterministic}}: S \rightarrow A$$, that is, a function from the set of states to the set of actions. A stochastic policy is a map of the form $$\pi_{\text{stochastic}} : S \rightarrow P(A)$$, where $$P(A)$$ is a set of probability distributions ($$P(A) = \{ p_{s_1}(A), p_{s_2}(A), \dots, p_{s_{|S|}}(A) \}$$, where $$p_{s_i}(A)$$ is a probability distribution over the set of actions $$A$$ for the state $$s_i$$ and $$|S|$$ is the size of the set of states of the environment) over the set of actions $$A$$. A deterministic policy can be interpreted as a stochastic policy that gives the probability of $$1$$ to one of the available actions (and $$0$$ to the remaining actions), for each state.

In the case of value iteration (VI) and policy iteration (PI), the policy is deterministic, both in the policy evaluation (PE) or policy improvement (PI) steps.

In the PE step, for a specific state $$s$$ (inside the for loop), you use $$\pi(s)$$, that is, you assume that the action taken in the specific state $$s$$ is the greedy action, because of the $$\text{argmax}$$ in the PI, according to the current policy. However, in general, $$\pi_k(s_i) \neq \pi_k(s_j)$$, for $$i \neq j$$, where $$k$$ is the current iteration step (of PE and PI).

The update rule

$$\pi_{k+1}(s) \leftarrow arg max_a \sum_{s'}p(s' \mid s, a)[r(s, a, s') + \gamma v_k(s')]$$

computes the action that is expected to give the highest return, given the current and fixed value function $$(v_k$$). Have a look at the definition of expectation for discrete random variables: it is defined as a weighted sum (like in the update rule above, where the weights are $$p(s' \mid s, a)$$).

Value iteration is a shorter version of policy iteration. In VI, rather than performing a PI step for each state of the environment, when performing PE, the action that is expected to give the highest return is chosen. In VI, the policy is updated only once and at the end of policy evaluation. In PI, you alternate between PE and PI, and, at each PI, you update the policy.

• So the main question is the probablity assigned during the Pimprovement step or Pevaluation step? If you see that was the two of my interpretations. Basically if you use tensorflow then you'll know in it we don't explicitly define any data, but we just build a model. So is the policy an explicit definition of probablity or is it a rule which is used in PE step (I.e act greedily). – DuttaA May 12 at 15:21
• Thus would the probablity be already assigned before the beginning of PE step or would it be assigned for each PE iteration? – DuttaA May 12 at 15:22
• @DuttaA When you perform one PE step, the policy is fixed (so the probabilities for that specific PE step have already been assigned). When you perform the next PE step, the policy is also fixed, but it might be different than the fixed policy you used in the previous PE step (because, during PI, you change the policy). – nbro May 12 at 15:38
• @DuttaA Given that the policy used in this context is deterministic, it might not be convenient to think of probabilities. However, the policy you use in PE is fixed (as I said above). This fixed policy used in PE has been computed using a "greedy" method in PI, so I would think of the fixed policy used in PE as a greedy policy with respect to the previous value function. I think this diagram might help: http://incompleteideas.net/book/first/ebook/node46.html. It gives you the idea behind policy iteration. – nbro May 12 at 15:44
• @DuttaA policy iteration and value iteration are basically the same thing. Value iteration is a special case of policy iteration where you do a single step of policy evaluation (no for loop for $n$ steps, only a single step) and after that policy improvement, while in policy iteration you do policy evaluation for $n$ steps (for loop with $n$ steps) and then policy improvement. Also, in value iteration policy improvement is sort of implicit, its "blended" in in policy evaluation step. – Brale_ May 12 at 15:57