Answers.Body: <blockquote>
  <p>I would like to know if the optimal value function can also be defined as
  <span class="math-container">$$v_*(s_t) = \max_{a \in A(s_t)} \big\{ E_F \left[ r_{t+1} |  s_t,a \right]+ \delta E_F \left[v_* \left(s_{t+1}\right)| s_t,a \right] \big\},$$</span></p>
  </blockquote>
  <p>This looks correct to me, although I am used to different notation, and viewing this after resolving the expectations. From Sutton &amp; Barto, I would write the following:</p>
  <p><span class="math-container">$$v^*(s) = \text{max}_a \sum_{r,s'}p(r,s'|s,a)(r + \gamma v^*(s'))$$</span></p>
  <p>which I think matches your equation term-for-term.</p>
  <blockquote>
  <p>To me, behaving greedily and chosing the optimal policy seem equivalent, which confuses me a bit.</p>
  </blockquote>
  <p>You have to take care with the self-reference to the optimal value function - it occurs on both sides of the Bellman equation.</p>
  <ul>
  <li><p>Behaving greedily with respect to an <em>optimal</em> value function is an optimal policy.</p>
  </li>
  <li><p>Behaving greedily with respect to any other value function is a greedy policy, but may not be the optimal policy for that environment.</p>
  </li>
  <li><p>Behaving greedily with respect to a non-optimal value function is  not the policy that the value function is <em>for</em>, and there is no Bellman equation that shows this relationship.</p>
  </li>
  <li><p>Only the optimal policy has Bellman equation that includes <span class="math-container">$\text{max}_a$</span>. All others must use the more general <span class="math-container">$v_{\pi}(s) = \sum_a \pi(a|s) \sum_{r,s'}p(r,s'|s,a)(r + \gamma v_{\pi}(s'))$</span></p>
  </li>
  <li><p>However, a greedy policy over a non-optimal value function is an improvement on the policy that resulted in that value function, which is shown by the <a href="http://incompleteideas.net/book/ebook/node42.html" rel="noreferrer">policy improvement theorem</a>.</p>
  </li>
  </ul>
  <p>If you can solve the Bellman equation for the optimal value function - either as a system of simultaneous equations, or using iteration in Dynamic Programming, then you will have the optimal value function and by implication behaving greedily with respect to it will be an optimal policy. This is the basis for Value Iteration.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-03-06T10:19:00.600Z
Answers.LastActivityDate: 2022-03-06T10:26:07.970Z
Answers.LastEditDate: 2022-03-06T10:26:07.970Z
Answers.UserDisplayName: Neil Slater
Body: <p>I am struggling to understand what is the difference between an optimal policy and a greedy policy.</p>
  <p>Let <span class="math-container">$F(r_{t+1},s_{t+1}| s_t,a_t)$</span> be the probability distribution accorting to which, given action <span class="math-container">$a_t$</span> in state <span class="math-container">$s_t$</span>, reward <span class="math-container">$r_{t+1}$</span> realizes and the process transitions to a new state <span class="math-container">$s_{t+1}$</span>. The value function for a generic policy <span class="math-container">$\pi$</span> then is</p>
  <p><span class="math-container">$$v_\pi(s_t) = E_\pi \left[ E_F \left[ r_{t+1} |  s_t,a_t \right]+ \delta E_F \left[v_\pi \left(s_{t+1}\right)| s_t,a_t \right] \right],$$</span></p>
  <p>and the optimal value function is</p>
  <p><span class="math-container">$$ v_*(s_t) = \max_\pi \, v_\pi(s_t).$$</span></p>
  <p>I would like to know if the optimal value function can also be defined as
  <span class="math-container">$$v_*(s_t) = \max_{a \in A(s_t)} \big\{ E_F \left[ r_{t+1} |  s_t,a \right]+ \delta E_F \left[v_* \left(s_{t+1}\right)| s_t,a \right] \big\},$$</span>
  and if not, why. Here, the bellman equation prescribes to behave greedily by always choosing the best action <span class="math-container">$a \in A(s)$</span>.</p>
  <p>To me, behaving greedily and choosing the optimal policy seem equivalent, which confuses me a bit.</p>
  
Tags: <reinforcement-learning><comparison><value-functions><bellman-equations><optimal-policy>
Title: What is the difference between a greedy policy and an optimal policy?
UserDisplayName: fennel
ThreadText: # What is the difference between a greedy policy and an optimal policy?
  
  (Asked by: username_0 on 2022-03-06)
  
  I am struggling to understand what is the difference between an optimal policy and a greedy policy.
  
  Let $F(r\_{t+1},s\_{t+1}| s\_t,a\_t)$ be the probability distribution accorting to which, given action $a\_t$ in state $s\_t$, reward $r\_{t+1}$ realizes and the process transitions to a new state $s\_{t+1}$. The value function for a generic policy $\pi$ then is
  
  $$v\_\pi(s\_t) = E\_\pi \left[ E\_F \left[ r\_{t+1} | s\_t,a\_t \right]+ \delta E\_F \left[v\_\pi \left(s\_{t+1}\right)| s\_t,a\_t \right] \right],$$
  
  and the optimal value function is
  
  $$ v\_\*(s\_t) = \max\_\pi \, v\_\pi(s\_t).$$
  
  I would like to know if the optimal value function can also be defined as
  $$v\_\*(s\_t) = \max\_{a \in A(s\_t)} \big\{ E\_F \left[ r\_{t+1} | s\_t,a \right]+ \delta E\_F \left[v\_\* \left(s\_{t+1}\right)| s\_t,a \right] \big\},$$
  and if not, why. Here, the bellman equation prescribes to behave greedily by always choosing the best action $a \in A(s)$.
  
  To me, behaving greedily and choosing the optimal policy seem equivalent, which confuses me a bit.
  
  **Tags:** reinforcement-learning, comparison, value-functions, bellman-equations, optimal-policy
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-03-06. Score: 5 | Accepted answer
  
  > I would like to know if the optimal value function can also be defined as
  > $$v\_\*(s\_t) = \max\_{a \in A(s\_t)} \big\{ E\_F \left[ r\_{t+1} | s\_t,a \right]+ \delta E\_F \left[v\_\* \left(s\_{t+1}\right)| s\_t,a \right] \big\},$$
  
  This looks correct to me, although I am used to different notation, and viewing this after resolving the expectations. From Sutton & Barto, I would write the following:
  
  $$v^\*(s) = \text{max}\_a \sum\_{r,s'}p(r,s'|s,a)(r + \gamma v^\*(s'))$$
  
  which I think matches your equation term-for-term.
  
  > To me, behaving greedily and chosing the optimal policy seem equivalent, which confuses me a bit.
  
  You have to take care with the self-reference to the optimal value function - it occurs on both sides of the Bellman equation.
  
  * Behaving greedily with respect to an *optimal* value function is an optimal policy.
  * Behaving greedily with respect to any other value function is a greedy policy, but may not be the optimal policy for that environment.
  * Behaving greedily with respect to a non-optimal value function is not the policy that the value function is *for*, and there is no Bellman equation that shows this relationship.
  * Only the optimal policy has Bellman equation that includes $\text{max}\_a$. All others must use the more general $v\_{\pi}(s) = \sum\_a \pi(a|s) \sum\_{r,s'}p(r,s'|s,a)(r + \gamma v\_{\pi}(s'))$
  * However, a greedy policy over a non-optimal value function is an improvement on the policy that resulted in that value function, which is shown by the [policy improvement theorem](http://incompleteideas.net/book/ebook/node42.html).
  
  If you can solve the Bellman equation for the optimal value function - either as a system of simultaneous equations, or using iteration in Dynamic Programming, then you will have the optimal value function and by implication behaving greedily with respect to it will be an optimal policy. This is the basis for Value Iteration.
  
  
  ---
  
  