Bellman Equations and Optimality Conditions

To evaluate the effectiveness of different strategies, or policies, within a Markov Decision Process (MDP) framework, and ultimately to find the optimal policy, a mathematical foundation is essential. This evaluation is central to reinforcement learning. The Bellman equations provide this foundation, relating the value of a state (or state-action pair) to the values of subsequent states, and serving as the basis upon which many reinforcement learning algorithms are built.

Bellman Expectation Equations: Evaluating a Given Policy

Let's assume we have a fixed policy $\pi$, which is a mapping from states to probabilities of taking each possible action $\pi(a|s)$. How valuable is it to be in a particular state $s$ while following this policy? We quantify this using the state-value function, $V^\pi(s)$, defined as the expected total discounted reward starting from state $s$ and subsequently following policy $\pi$:

$V^\pi(s) = \mathbb{E}_\pi \left[ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s \right]$

Here, $\mathbb{E}_\pi[\cdot]$ denotes the expected value given that the agent follows policy $\pi$, $R_{t+k+1}$ is the reward received at timestep $t+k+1$, and $\gamma \in [0, 1]$ is the discount factor that trades off immediate versus future rewards.

The Bellman expectation equation provides a recursive definition for $V^\pi(s)$. It breaks down the value of a state into the expected immediate reward and the expected discounted value of the next state:

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

Let's dissect this equation:

• $\sum_{a} \pi(a|s)$: We sum over all possible actions $a$ the agent might take in state $s$, weighted by the probability of taking that action under policy $\pi$.
• $\sum_{s', r} p(s', r|s, a)$: For a chosen action $a$, we sum over all possible next states $s'$ and rewards $r$, weighted by the environment's transition dynamics $p(s', r|s, a)$. This gives the expected outcome of taking action $a$ in state $s$.
• $[r + \gamma V^\pi(s')]$: This is the core of the recursion. It's the immediate reward $r$ plus the discounted value $V^\pi(s')$ of the next state $s'$, assuming we continue to follow policy $\pi$ from $s'$ onwards.

Similarly, we can define the action-value function, $Q^\pi(s, a)$, which represents the expected return starting from state $s$, taking action $a$, and then following policy $\pi$:

$Q^\pi(s, a) = \mathbb{E}_\pi \left[ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s, A_t = a \right]$

The Bellman expectation equation for $Q^\pi(s, a)$ is:

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

This equation states that the value of taking action $a$ in state $s$ is the expected immediate reward plus the expected discounted value of the next state-action pair, averaged over all possible next actions $a'$ chosen according to policy $\pi$ in the next state $s'$.

Notice the direct relationship between $V^\pi$ and $Q^\pi$:

• The value of a state is the expected value of the action-values available in that state, according to the policy: $V^\pi(s) = \sum_{a} \pi(a|s) Q^\pi(s, a)$
• The value of a state-action pair is the expected immediate reward plus the expected discounted value of the next state: $Q^\pi(s, a) = \sum_{s', r} p(s', r|s, a) [r + \gamma V^\pi(s')]$

For a given policy $\pi$ and known dynamics $p(s', r|s, a)$, the Bellman expectation equations define a system of linear equations. If the state space is small enough, we could solve this system directly to find the value function $V^\pi$ or $Q^\pi$ corresponding to the policy $\pi$.

Recursive calculation for $Q^\pi(s, a)$. The value depends on the expected immediate reward $r$ and the discounted expected value of the next state-action pair $Q^\pi(s', a')$, averaged over environment dynamics and the policy's choices in the next state.

Bellman Optimality Equations: Finding the Best Policy

While evaluating a given policy is useful, the ultimate objective in many RL settings is to find an optimal policy, denoted $\pi_*$, that achieves the highest possible expected return from any starting state. We define the optimal state-value function $V^*(s)$ and the optimal action-value function $Q^*(s, a)$ as:

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

The Bellman optimality equations define the value of the optimal policy. Unlike the expectation equations, they incorporate a maximization step, reflecting the fact that an optimal policy must choose the best action in each state.

The Bellman optimality equation for $V^*(s)$ is:

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

This equation states that the optimal value of a state $s$ is obtained by choosing the action $a$ that maximizes the expected sum of the immediate reward $r$ and the discounted optimal value $\gamma V^*(s')$ of the resulting next state $s'$.

The Bellman optimality equation for $Q^*(s, a)$ is often more convenient for decision-making:

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

Here, the optimal value of taking action $a$ in state $s$ is the expected immediate reward plus the expected discounted value of the best possible action $a'$ available in the next state $s'$. The term $\max_{a'} Q^*(s', a')$ is equivalent to $V^*(s')$, highlighting the connection:

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

Crucially, the Bellman optimality equations form a system of non-linear equations due to the $\max$ operator. Solving this system yields the optimal value functions $V^*$ and $Q^*$. Once we have $Q^*$, finding the optimal policy $\pi_*$ is straightforward: in any state $s$, act greedily with respect to $Q^*$. That is, choose the action $a$ that maximizes $Q^*(s, a)$:

$\pi_*(s) = \arg\max_{a} Q^*(s, a)$ (If multiple actions share the maximum value, any of them can be chosen.)

These optimality equations don't directly tell us how to find $V^*$ or $Q^*$, but they define the conditions that the optimal values must satisfy. Algorithms like Value Iteration and Policy Iteration (discussed next) leverage these equations to compute optimal policies in settings where the model $p(s', r|s, a)$ is known. For model-free settings, methods like Q-Learning approximate $Q^*$ iteratively based on experience. Understanding Bellman equations is therefore essential for grasping nearly all fundamental reinforcement learning algorithms.