optimal policy

An optimal policy is a way of behaving that you cannot beat — no other policy earns a higher expected return from any state. It is the goal that all the value machinery is built to find: the rule that, followed faithfully, maximizes the long-run discounted reward. In a maze it is the set of turns that reaches the exit fastest; in a game, the strategy that wins as often as possible.

A reassuring theorem says that for any finite Markov decision process at least one optimal policy always exists, and at least one of them is deterministic — you never need to gamble to play perfectly. There may be ties, several equally good policies, but they all share the same optimal value function. The usual recipe to obtain one is to compute Q-star and then, in each state, pick the action with the largest optimal action value.