Optimal Policy

Definition

Optimal Policy ( ${\pi }_{\ast }$)

A policy $\pi$ is defined to be better than or equal to a policy ${\pi }^{\prime }$ if its expected return is greater than or equal to that of ${\pi }^{\prime }$ for all states. An optimal policy ${\pi }_{\ast }$ is any policy that is better than or equal to all other policies.

Key Properties

• Existence: At least one optimal policy always exists for any Markov Decision Process (MDP).
• Shared Value Function: All optimal policies share the same optimal state-value function $v_{\ast }$ and optimal action-value function $q_{\ast }$.
• Greedy Selection: Once $q_{\ast }$ is known, an optimal policy can be found by being greedy with respect to it: ${\pi }_{\ast }(s)=\arg {\max }_a{q}_{\ast }(s,a)$
• Uniqueness: While the value functions $v_{\ast }$ and $q_{\ast }$ are unique, the optimal policy ${\pi }_{\ast }$ may not be (e.g., if multiple actions share the same maximum value).

Mathematical Relation

Relationship to Optimal Value Function

$v_{\ast }(s)={\max }_{\pi }{v}_{\pi }(s)\forall s\in \mathcal{S}$ $q_{\ast }(s,a)={\max }_{\pi }{q}_{\pi }(s,a)\forall s\in \mathcal{S},a\in \mathcal{A}$

The Bellman Optimality Equation for $v_{\ast }$ is: $v_{\ast }(s)={\max }_a{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_{\ast }(s^{\prime })]$

Intuition

The Ceiling of Performance

The optimal policy represents the best possible way to behave in an environment. Reinforcement Learning algorithms (like Q-Learning or REINFORCE) are essentially searching for this policy or its corresponding value function.

Connections

• Attained when solving: Bellman Equation (optimality version)
• Goal of: Q-Learning (approximates $q_{\ast }$)
• Foundation for: MDP theory

Appears In

• RL-L01 - Intro & MDPs
• RL-L02 - Bellman Equations
• RL-Book Ch3 - Finite Markov Decision Processes