# How is policy iteration capable of improving on a deterministic policy?

Given a policy $$\pi$$ and the improved version upon it using policy iteration $$\pi'$$ we have, for $$\forall s \in S$$, $$v_{\pi'}(s)\geq v_{\pi}(s)$$.

I think the way we choose $$\pi'$$ makes it deterministic (unless there is a tie but let's not consider it) because we take $$\pi'(s) = \arg\max_{a} \mathbb{E}[R_{t+1} + \gamma v_{\pi}(S_{t+1})|S_{t}=s, A_{t}=a]$$.

Following policy $$\pi'$$ now (in order to evaluate it), if at time step $$t$$ we're in state $$s$$, then we'll take action $$a$$ given by $$\pi'(a|s)$$ and we'll arrive at a state $$s'$$ while getting a reward $$r$$. For simplicity let's suppose the environment isn't stochastic, the initial state is the same and that the MDP is finite. Since the policy is stochastic and the initial state is the same, we'll always take the same path and evaluate the same states.

When we start evaluating for $$\pi'$$, the initial values for the value function $$v_{\pi'}$$ are $$v_{\pi}(s)$$. Since we have the condition $$v_{\pi'}(s)\geq v_{\pi}(s)$$ (because $$\pi'$$ is an improvement over $$\pi$$), those values can only increase, and since we only evaluate particular states, then only the values for these particular states will increase.

Now if we want to take improvement step $$\pi'' \geq \pi'$$ then this new policy will be exactly the same as $$\pi'$$ since the only states that saw their values increased are the ones taken by $$\pi'$$.

I feel I'm misundertanding something but I can't really put my finger on it so I hope you can help me figure out what I'm missing. Thank you in advance.

EDIT: Formulated my incomprehension in a clearer manner.

• Could be clearer on what you mean by "take us through the same path" and "same path over and over"? Which paths are you comparing and deciding will be the same? Do you think the path taken by $\pi$, then $\pi'$ and $\pi''$ will be the same? If so, then why? Commented Apr 25, 2022 at 20:27
• @NeilSlater Thank you for your comment, I edited my question I hope it's clearer now ^^ Commented Apr 25, 2022 at 20:58
• Thanks for the update. I can see whatis wrong with your analysis now. Commented Apr 26, 2022 at 6:50

Your analysis would be true for any model-free algorithm that did not explore, such as Monte Carlo Control or SARSA if you removed the exploration components (e.g. set $$\epsilon = 0$$ for $$\epsilon$$-greedy), because those algorithms rely completely on observations of experienced trajectories.