What is the difference between a greedy policy and an optimal policy?

Question

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.

Answer 1

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.

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.