Principle of Optimality

A problem is said to satisfy the Principle of Optimality if the subsolutions of an optimal solution of the problem are themselves optimal solutions for their subproblems.

Examples:

• The shortest path problem satisfies the Principle of Optimality
• Optimal Policy

Principle of Optimality

Any Optimal Policy can be subdivided into two components:

1. An optimal first action $A_{\ast }$
2. Followed by an optimal policy from successor state $S^{\prime }$

Theorem (Principle of Optimality)

A policy $\pi (a|s)$ achieves the optimal value from state $s$, $v_{\pi }(s)=v_{\ast }(s)$, if and only if

• For any state $s^{\prime }$ reachable from $s$,
• $\pi$ achieves the optimal value from state $s^{\prime }$, $v_{\pi }(s^{\prime })=v_{\ast }(s^{\prime })$

From F1TENTH An algorithm is said to be optimal if it returns the minimum cost solution when a solution exists.