Example showing that tied bound is right

  

Figure: Example Diagram

• The optimal policy is : V^*(1) = V^*(2) = 0
• Let $V(1) = +\epsilon , V(2) = -\epsilon$, than $\vert\vert V - V^* \vert\vert = 2\epsilon$
  
• Greedy policy
  
  $$-2\epsilon\lambda + \lambda V(1) = -2\epsilon\lambda + \lambda\epsilon = -\epsilon\lambda$$
  
  
  The return of $\pi$ is,
  
  $$V^{\pi}(1) = \sum_{i}\lambda^{i}(-2\epsilon\lambda) = \frac{-2\epsilon\lambda}{1-\lambda}.$$