The Bellman Optimality Equation

The Bellman expectation equation provides a recursive relationship for the value function ($V^{\pi}$) and action-value function ($Q^{\pi}$) under a specific, given policy $\pi$. This equation helps determine the expected return when following that particular policy. However, in many reinforcement learning problems, the main goal extends beyond just evaluating a policy; it is to discover the best policy, the one that achieves the maximum possible cumulative reward.

To find this optimal policy, we need a way to describe the value functions associated with it. This leads us to the Bellman optimality equations. These equations define the value functions not for an arbitrary policy $\pi$, but for the optimal policy $\pi^*$.

Optimal Value Functions: $V^*$ and $Q^*$

First, let's define what we mean by optimal value functions. The optimal state-value function, denoted $V^*(s)$, represents the maximum expected return achievable starting from state $s$ and following any policy thereafter. Similarly, the optimal action-value function, $Q^*(s, a)$, is the maximum expected return achievable starting from state $s$, taking action $a$, and then following the optimal policy.

Mathematically, they are defined as:

$V^*(s) = \max_{\pi} V^{\pi}(s)$ $Q^*(s, a) = \max_{\pi} Q^{\pi}(s, a)$

These functions represent the upper bound on performance for the given MDP.

The Bellman Optimality Equation for $V^*$

The Bellman optimality equation for $V^*$ expresses the idea that the optimal value of a state $s$ must equal the expected return obtained by taking the best possible action $a$ in that state, and then continuing optimally from the resulting state $s'$. It incorporates a maximization step over actions, unlike the expectation equation which averages according to the policy $\pi$.

The equation is:

$V^*(s) = \max_{a \in \mathcal{A}(s)} \sum_{s', r} p(s', r | s, a) [r + \gamma V^*(s')]$

Let's break this down:

• $\max_{a \in \mathcal{A}(s)}$: We consider all possible actions $a$ available in state $s$ and choose the one that maximizes the expected return.
• $p(s', r | s, a)$: This is the probability of transitioning to state $s'$ and receiving reward $r$, given that we are in state $s$ and take action $a$. This represents the environment's dynamics.
• $r$: The immediate reward received after taking action $a$ in state $s$.
• $\gamma$: The discount factor, balancing immediate and future rewards.
• $V^*(s')$: The optimal value of the next state $s'$. This recursive component assumes we will act optimally from state $s'$ onwards.

This equation states that the value of a state under an optimal policy is the expected return for the best action from that state.

The Bellman Optimality Equation for $Q^*$

Similarly, we can define the Bellman optimality equation for the optimal action-value function $Q^*$. The optimal value of taking action $a$ in state $s$ is the expected immediate reward $r$ plus the discounted expected value of the best possible action $a'$ taken in the next state $s'$.

The equation is:

$Q^*(s, a) = \sum_{s', r} p(s', r | s, a) [r + \gamma \max_{a' \in \mathcal{A}(s')} Q^*(s', a')]$

Here's the breakdown:

• $\sum_{s', r} p(s', r | s, a) [\dots]$: We sum over all possible next states $s'$ and rewards $r$, weighted by their transition probabilities.
• $r$: The immediate reward.
• $\gamma$: The discount factor.
• $\max_{a' \in \mathcal{A}(s')} Q^*(s', a')$: This is the important part. After transitioning to state $s'$, we assume we will choose the action $a'$ that yields the highest optimal action-value $Q^*(s', a')$. This represents acting optimally from the next state onwards.

Notice the relationship between $V^*$ and $Q^*$. The optimal value of a state is simply the value of the best action taken from that state:

$V^*(s) = \max_{a} Q^*(s, a)$

Substituting this into the Bellman optimality equation for $Q^*$ gives an alternative form:

$Q^*(s, a) = \sum_{s', r} p(s', r | s, a) [r + \gamma V^*(s')]$

Finding the Optimal Policy

The Bellman optimality equations are significant because if we can solve them to find $V^*$ or $Q^*$, we can easily determine the optimal policy $\pi^*$. Specifically, if we have $Q^*(s, a)$, the optimal policy is to act greedily with respect to $Q^*$ in every state:

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

This means that in state $s$, the optimal policy $\pi^*$ chooses the action $a$ that maximizes the optimal action-value function $Q^*(s, a)$. If we only have $V^*$, we can still find the optimal action by looking one step ahead, using the dynamics $p(s', r | s, a)$:

$\pi^*(s) = \arg\max_{a \in \mathcal{A}(s)} \sum_{s', r} p(s', r | s, a) [r + \gamma V^*(s')]$

Optimality vs. Expectation

It's important to distinguish the Bellman optimality equations from the Bellman expectation equations.

• Expectation Equations: Describe the value of a given policy $\pi$. They involve expectations based on the actions dictated by $\pi$.
• Optimality Equations: Describe the value of the optimal policy $\pi^*$. They involve a maximization step over actions, selecting the best action at each stage.

The optimality equations define a system of non-linear equations. Unlike the expectation equations (which are linear for a fixed policy), solving the optimality equations directly can be more complex. However, they form the foundation for algorithms like Value Iteration, which we will discuss next, that aim to find these optimal values when a model of the environment is available. These equations capture the essence of finding the best way to behave in an MDP.