- Rest of Sutton & Barto Chapter 3
- Sutton & Barto Summary of Notation,
- Sutton & Barto Section 4.1
Optimal Policy
Define: given a MDP problem, we have a corresponding policy spaces $\Pi$ of all possible policies for the problem. $\Pi$ is preordered by Pareto ordering:
\[\pi_1 \succeq \pi_2 \quad \text{iff} \quad \forall s\in S, v_{\pi_1}(s) \ge v_{\pi_2}(s)\]
That is, a policy is better than another iff using it does not deprove the expected value in all situations, and improves in at least one.
A policy $\pi$ is optimal iff it is a maximal element in $\Pi$ thus preordered.
The optimal state-value function is defined as as the best that can be done by any policy at a certain state, it's a bit subtler than that
\[v_*(s) = \max_\pi v_\pi(s)\]
and similarly for $q_*$
