Finding Optimal Policies

Sequential decision problems are modeled using Markov Decision Processes (MDPs). A given policy $\pi$ can be evaluated with its value functions, $V^\pi(s)$ and $Q^\pi(s, a)$. The value function $V^\pi(s)$ represents the expected return starting from state $s$ and following policy $\pi$. Additionally, $Q^\pi(s, a)$ is the expected return starting from state $s$, taking action $a$, and subsequently following policy $\pi$.

The ultimate objective in solving an MDP is not just to evaluate any policy, but to find the best policy. What does "best" mean? In the context of RL and MDPs, it means maximizing the expected cumulative discounted reward. We call such a policy an optimal policy, typically denoted as $\pi^*$.

Formally, a policy $\pi$ is considered optimal if its expected return is greater than or equal to the expected return of any other policy $\pi'$ for all states $s \in S$.

$V^\pi(s) \ge V^{\pi'}(s) \quad \text{for all } s \in S \text{ and all policies } \pi'$

It's important to note that there might be more than one optimal policy, but they all achieve the maximum possible expected return. All optimal policies share the same optimal state-value function, denoted $V^*$, and the same optimal action-value function, denoted $Q^*$.

These optimal value functions are defined as:

$V^*(s) = \max_{\pi} V^\pi(s) \quad \text{for all } s \in S$

$Q^*(s, a) = \max_{\pi} Q^\pi(s, a) \quad \text{for all } s \in S, a \in A$

$V^*(s)$ gives the largest expected return achievable starting from state $s$, regardless of the specific optimal policy followed. Similarly, $Q^*(s, a)$ gives the largest expected return achievable starting from state $s$, taking action $a$, and then following an optimal policy thereafter.

The Connection Between Optimal Value Functions and Optimal Policies

There's a direct and powerful relationship between the optimal action-value function $Q^*$ and an optimal policy $\pi^*$. If you knew the true $Q^*$ function, finding an optimal policy would be straightforward. You would simply choose the action that maximizes $Q^*(s, a)$ in each state $s$. A policy that acts greedily with respect to the optimal action-value function $Q^*$ is guaranteed to be an optimal policy.

So, an optimal policy $\pi^*$ can be defined as:

$\pi^*(s) = \arg\max_{a \in A} Q^*(s, a)$

This means that in state $s$, an optimal policy selects the action $a$ that yields the highest expected return, according to $Q^*$. If multiple actions share the maximum value, any of them can be chosen by the optimal policy.

Bellman Optimality Equations

Just as the value functions for an arbitrary policy $\pi$ satisfy the Bellman expectation equations, the optimal value functions $V^*$ and $Q^*$ satisfy their own specific Bellman equations, known as the Bellman Optimality Equations. These equations provide a recursive definition for the optimal values.

The Bellman Optimality Equation for $V^*$ is:

$V^*(s) = \max_{a \in A} Q^*(s, a)$ $V^*(s) = \max_{a \in A} \sum_{s' \in S} P(s'|s, a) [R(s, a, s') + \gamma V^*(s')]$

This equation expresses that the optimal value of a state $s$ must equal the expected return obtained by taking the best possible action $a$ from that state, and then following an optimal policy thereafter. The max operator indicates that the agent chooses the action that maximizes the expected subsequent value.

Similarly, the Bellman Optimality Equation for $Q^*$ is:

$Q^*(s, a) = \sum_{s' \in S} P(s'|s, a) [R(s, a, s') + \gamma V^*(s')]$ Since $V^*(s') = \max_{a' \in A} Q^*(s', a')$, we can write: $Q^*(s, a) = \sum_{s' \in S} P(s'|s, a) [R(s, a, s') + \gamma \max_{a' \in A} Q^*(s', a')]$

This equation states that the optimal value of taking action $a$ in state $s$ is the expected immediate reward $R(s, a, s')$ plus the discounted expected value of the next state $s'$, assuming that the agent acts optimally ($\max_{a'} Q^*(s', a')$) from that next state onwards.

These optimality equations are fundamental. If we can find a value function $V$ or $Q$ that satisfies the corresponding Bellman optimality equation, then that value function is the optimal value function ($V^*$ or $Q^*$), and we can derive an optimal policy from it.

Solving an MDP essentially means finding $V^*$ or $Q^*$. While the Bellman optimality equations define these functions, they don't directly provide a solution method, especially since they often form a system of non-linear equations. The next chapter will introduce algorithms based on Dynamic Programming, like Value Iteration and Policy Iteration, which are designed to compute these optimal value functions, assuming we have a complete model of the MDP (i.e., we know the transition probabilities $P$ and reward function $R$). Later chapters will explore how to find optimal policies even when such a model is unavailable.