Optimal Policy

Define a partial ordering over policies $\pi \ge {\pi }^{\prime }\text{ if }{v}_{\pi }(s)\ge v_{{\pi }^{\prime }}(s),\forall s$

Theorem

For any MDP,

• There exists an optimal policy ${\pi }_{\ast }$ that is better than or equal to all other policies, ${\pi }_{\ast }\ge \pi ,\forall \pi$
• All optimal policies achieve the Optimal Value Function, $v_{{\pi }_{\ast }}(s)=v_{\ast }(s)$
• All optimal policies achieve the optimal action-value function, $q_{{\pi }_{\ast }}(s,a)=q_{\ast }(s,a)$

How to arrive at $q_{\ast }$ values? We need to use Bellman Equation, central to solving these.

See Dynamic Programming.

• Evaluation and Control