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

Question

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.

Answer 1

These statements are not true for policy iteration and dynamic programming:

Since the policy is stochastic and the initial state is the same, we'll always take the same path and evaluate the same states.

since we only evaluate particular states, then only the values for these particular states will increase

Policy iteration does not learn from experience, and does not visit states based on observing trajectories. It is a planning/off-policy algorithm that in the simplest form visits and updates all states equally (more sophisticated forms may prioritise certain states). It can do so because it does not use observations of reward and next state, but instead uses a model of the environment to calculate updates. This is also true for value iteration.

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.