Answers.Body: <p>You appear to comparing the value table update steps in <em>policy iteration</em> and <em>value iteration</em>, which are both derived from Bellman equations.</p>
  <h2>Policy iteration</h2>
  <p>In <em>policy iteration</em>, a policy lookup table is generated, which can be arbitrary. It usually maps a deterministic policy <span class="math-container">$\pi(s): \mathcal{S} \rightarrow \mathcal{A}$</span>, but can also be of the form <span class="math-container">$\pi(a|s): \mathcal{A} \times  \mathcal{S} \rightarrow \mathbb{R} = Pr\{A_t = a |S_t =s\}$</span>. Policy iteration then alternately evaluates then improves that policy, with the improvement always being to act greedily with respect to expected return. Because the policy function can be arbitrary, and also the current value estimates during evaluation might not relate to it directly, the function <span class="math-container">$\pi(s)$</span> or <span class="math-container">$\pi(a|s)$</span> needs to be shown.</p>
  <p>Typically with policy iteration, you will see this update rule:</p>
  <p><span class="math-container">$$V(s) \leftarrow \sum_{r,s'} p(r,s'|s,\pi(s))(r + \gamma V(s'))$$</span></p>
  <p>The above rule is for evaluating a deterministic policy, and is probably more commonly used. There is no real benefit in policy iteration to working with stochastic policies.</p>
  <p>For completeness, the update rule for an arbitrary stochastic policy is:</p>
  <p><span class="math-container">$$V(s) \leftarrow \sum_a \pi(a|s) \sum_{r,s'} p(r,s'|s,a)(r + \gamma V(s'))$$</span></p>
  <h2>Value iteration</h2>
  <p>In <em>value iteration</em>, the current policy to evaluate is to always take the greedy action with respect to the current evaluations. As such, it does not need to be explicity written, because it can be derived from the value function, and so can the terms in the Bellman equation (specifically the Bellman equation for the optimal value function is used here, which usually does not refer the policy). What you would typically write for the update step is:</p>
  <p><span class="math-container">$$V(s) \leftarrow \text{max}_a \sum_{r,s'} p(r,s'|s,a)(r + \gamma V(s'))$$</span></p>
  <p>However, you can write this out as if there was a policy table:</p>
  <p><span class="math-container">$$\pi(s) \leftarrow \text{argmax}_a \sum_{r,s'} p(r,s'|s,a)(r + \gamma V(s'))$$</span>
  <span class="math-container">$$a \leftarrow \pi(s)$$</span>
  <span class="math-container">$$V(s) \leftarrow \sum_{r,s'} p(r,s'|s,a)(r + \gamma V(s'))$$</span></p>
  <p>This is not the usual way to implement it though, because of the extra maximum value search required to identify the action. In simple value iteration it does not matter what the interim action choices and policies actually are, and you can always derive them from the value function if you want to know.</p>
  <h2>Other value-based methods</h2>
  <p>You will find other algorithms that drive the current policy direct from a value function, and when they are described in pseudo-code they might not have an explicit policy function. It is still there, only the Bellman update is easily calculated directly from the value function, so the policy is not shown in the update step. Descriptions of SARSA and Q-learning are often like that.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-25T14:15:47.700Z
Answers.LastActivityDate: 2020-08-25T14:44:04.807Z
Answers.LastEditDate: 2020-08-25T14:44:04.807Z
Answers.UserDisplayName: Neil Slater
Body: <p>I was looking at the Bellman equation, and I noticed a difference between the equations used in policy evaluation and value iteration.</p>
  <p>In policy evaluation, there was the presence of <span class="math-container">$\pi(a \mid s)$</span>, which indicates the probability of choosing action <span class="math-container">$a$</span> given <span class="math-container">$s$</span>, under policy <span class="math-container">$\pi$</span>. But this probability seemed to be omitted in the value iteration formula. What might be the reason? Maybe an omission?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-08-25T13:41:54.760Z
Comments.Text: Do you really mean "policy evaluation", or are you asking about "policy iteration"? "Policy evaluation" is also the name of a phase *within* policy iteration. However, value iteration and policy iteration are both optimal control solvers, so it would be more usual to compare those. Also policy evaluation in general is not a single algorithm, but a whole family of them.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-08-25T13:51:18.007Z
Comments.Text: Iterative policy evaluation , where we iterate many times to find the value of a state wheelie following a policy, while the value iteration deals with the optimal action set, my question is the absence of Pi(a|s) in value iteration
Comments.UserDisplayName: Chukwudi Ogbonna
Tags: <reinforcement-learning><policies><value-iteration><policy-iteration><bellman-equations>
Title: Why doesn't value iteration use $\pi(a \mid s)$ while policy evaluation does?
UserDisplayName: Chukwudi Ogbonna
ThreadText: # Why doesn't value iteration use $\pi(a \mid s)$ while policy evaluation does?
  
  (Asked by: username_0 on 2020-08-25)
  
  I was looking at the Bellman equation, and I noticed a difference between the equations used in policy evaluation and value iteration.
  
  In policy evaluation, there was the presence of $\pi(a \mid s)$, which indicates the probability of choosing action $a$ given $s$, under policy $\pi$. But this probability seemed to be omitted in the value iteration formula. What might be the reason? Maybe an omission?
  
  **Tags:** reinforcement-learning, policies, value-iteration, policy-iteration, bellman-equations
  > **Comments:**
  > **username_1**: Do you really mean "policy evaluation", or are you asking about "policy iteration"? "Policy evaluation" is also the name of a phase *within* policy iteration. However, value iteration and policy iteration are both optimal control solvers, so it would be more usual to compare those. Also policy evaluation in general is not a single algorithm, but a whole family of them.  
  > **username_0**: Iterative policy evaluation , where we iterate many times to find the value of a state wheelie following a policy, while the value iteration deals with the optimal action set, my question is the absence of Pi(a|s) in value iteration  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-08-25. Score: 4 | Accepted answer
  
  You appear to comparing the value table update steps in *policy iteration* and *value iteration*, which are both derived from Bellman equations.
  
  ## Policy iteration
  
  In *policy iteration*, a policy lookup table is generated, which can be arbitrary. It usually maps a deterministic policy $\pi(s): \mathcal{S} \rightarrow \mathcal{A}$, but can also be of the form $\pi(a|s): \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R} = Pr\{A\_t = a |S\_t =s\}$. Policy iteration then alternately evaluates then improves that policy, with the improvement always being to act greedily with respect to expected return. Because the policy function can be arbitrary, and also the current value estimates during evaluation might not relate to it directly, the function $\pi(s)$ or $\pi(a|s)$ needs to be shown.
  
  Typically with policy iteration, you will see this update rule:
  
  $$V(s) \leftarrow \sum\_{r,s'} p(r,s'|s,\pi(s))(r + \gamma V(s'))$$
  
  The above rule is for evaluating a deterministic policy, and is probably more commonly used. There is no real benefit in policy iteration to working with stochastic policies.
  
  For completeness, the update rule for an arbitrary stochastic policy is:
  
  $$V(s) \leftarrow \sum\_a \pi(a|s) \sum\_{r,s'} p(r,s'|s,a)(r + \gamma V(s'))$$
  
  ## Value iteration
  
  In *value iteration*, the current policy to evaluate is to always take the greedy action with respect to the current evaluations. As such, it does not need to be explicity written, because it can be derived from the value function, and so can the terms in the Bellman equation (specifically the Bellman equation for the optimal value function is used here, which usually does not refer the policy). What you would typically write for the update step is:
  
  $$V(s) \leftarrow \text{max}\_a \sum\_{r,s'} p(r,s'|s,a)(r + \gamma V(s'))$$
  
  However, you can write this out as if there was a policy table:
  
  $$\pi(s) \leftarrow \text{argmax}\_a \sum\_{r,s'} p(r,s'|s,a)(r + \gamma V(s'))$$
  $$a \leftarrow \pi(s)$$
  $$V(s) \leftarrow \sum\_{r,s'} p(r,s'|s,a)(r + \gamma V(s'))$$
  
  This is not the usual way to implement it though, because of the extra maximum value search required to identify the action. In simple value iteration it does not matter what the interim action choices and policies actually are, and you can always derive them from the value function if you want to know.
  
  ## Other value-based methods
  
  You will find other algorithms that drive the current policy direct from a value function, and when they are described in pseudo-code they might not have an explicit policy function. It is still there, only the Bellman update is easily calculated directly from the value function, so the policy is not shown in the update step. Descriptions of SARSA and Q-learning are often like that.
  
  
  ---
  
  