Answers.Body: <p>These statements are not true for policy iteration and dynamic programming:</p>
  <blockquote>
  <p>Since the policy is stochastic and the initial state is the same, we'll always take the same path and evaluate the same states.</p>
  </blockquote>
  <blockquote>
  <p>since we only evaluate particular states, then only the values for these particular states will increase</p>
  </blockquote>
  <p>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 <strong>all</strong> 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.</p>
  <p>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 <span class="math-container">$\epsilon = 0$</span> for <span class="math-container">$\epsilon$</span>-greedy), because those algorithms rely completely on observations of experienced trajectories.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-26T21:14:08.223Z
Answers.Text: Thank you for your answer, it completely cleared my incomprehension. Thanks again.
Answers.UserDisplayName: Daviiid
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-26T07:00:56.873Z
Answers.LastActivityDate: 2022-04-26T07:00:56.873Z
Answers.UserDisplayName: Neil Slater
Body: <p>Given a policy <span class="math-container">$\pi$</span> and the improved version upon it using policy iteration <span class="math-container">$\pi'$</span> we have, for <span class="math-container">$\forall s \in S$</span>, <span class="math-container">$v_{\pi'}(s)\geq v_{\pi}(s)$</span>.</p>
  <p>I think the way we choose <span class="math-container">$\pi'$</span> makes it deterministic (unless there is a tie but let's not consider it) because we take <span class="math-container">$\pi'(s) = \arg\max_{a} \mathbb{E}[R_{t+1} + \gamma v_{\pi}(S_{t+1})|S_{t}=s, A_{t}=a]$</span>.</p>
  <p>Following policy <span class="math-container">$\pi'$</span> now (in order to evaluate it), if at time step <span class="math-container">$t$</span> we're in state <span class="math-container">$s$</span>, then we'll take action <span class="math-container">$a$</span> given by <span class="math-container">$\pi'(a|s)$</span> and we'll arrive at a state <span class="math-container">$s'$</span> while getting a reward <span class="math-container">$r$</span>. 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.</p>
  <p>When we start evaluating for <span class="math-container">$\pi'$</span>, the initial values for the value function <span class="math-container">$v_{\pi'}$</span> are <span class="math-container">$v_{\pi}(s)$</span>. Since we have the condition <span class="math-container">$v_{\pi'}(s)\geq v_{\pi}(s)$</span> (because <span class="math-container">$\pi'$</span> is an improvement over <span class="math-container">$\pi$</span>), those values can only increase, and since we only evaluate particular states, then only the values for these particular states will increase.</p>
  <p>Now if we want to take improvement step <span class="math-container">$\pi'' \geq \pi'$</span> then this new policy will be exactly the same as <span class="math-container">$\pi'$</span> since the only states that saw their values increased are the ones taken by <span class="math-container">$\pi'$</span>.</p>
  <p>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.</p>
  <p>EDIT: Formulated my incomprehension in a clearer manner.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-04-25T20:27:06.590Z
Comments.Text: 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?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-04-25T20:58:57.910Z
Comments.Text: @NeilSlater Thank you for your comment, I edited my question I hope it's clearer now ^^
Comments.UserDisplayName: Daviiid
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-04-26T06:50:42.257Z
Comments.Text: Thanks for the update. I can see whatis wrong with your analysis now.
Comments.UserDisplayName: Neil Slater
Tags: <reinforcement-learning><value-functions><policy-iteration><optimal-policy><deterministic-policy>
Title: How is policy iteration capable of improving on a deterministic policy?
UserDisplayName: Daviiid
ThreadText: # How is policy iteration capable of improving on a deterministic policy?
  
  (Asked by: username_0 on 2022-04-25)
  
  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.
  
  **Tags:** reinforcement-learning, value-functions, policy-iteration, optimal-policy, deterministic-policy
  > **Comments:**
  > **username_1**: 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?  
  > **username_0**: @NeilSlater Thank you for your comment, I edited my question I hope it's clearer now ^^  
  > **username_1**: Thanks for the update. I can see whatis wrong with your analysis now.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-04-26. Score: 1 | Accepted answer
  
  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.
  
  > **Comments:**
  > **username_0**: Thank you for your answer, it completely cleared my incomprehension. Thanks again.  
  
  ---
  
  