Solving Bellman Equations

Hello! Welcome back to our module on Reinforcement Learning Foundations.

In our previous lesson, we established the language of reinforcement learning by learning how to formulate problems as Markov Decision Processes (MDPs). We defined the 5-tuple $(S,A,P,R,\gamma )$ and saw how it can represent a sequential decision-making problem like a grid world.

Today, we move from describing the problem to solving it. The central question is: given an MDP, how do we find the optimal policy, ${\pi }_{\ast }$? The answer lies in the Bellman equations, named after the mathematician Richard Bellman. These equations are arguably the most important theoretical tool in reinforcement learning. Our goal is to derive these fundamental equations and understand how they lead to algorithms that can solve for the optimal values of states.

1. The Value of Being in a State

Before we can find the best policy, we need a way to quantify how "good" it is to be in a particular state. We do this with value functions.

Recall from our last lesson the concept of the discounted return, $G_t$, which is the sum of all future rewards from time step $t$, discounted by $\gamma$:
$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots$

Since the transitions and rewards can be stochastic, $G_t$ is a random variable. The "value" of a state is the expected return we can get starting from that state.

There are two main types of value functions:

• State-Value Function, $v_{\pi }(s)$: The expected return when starting in state $s$ and following policy $\pi$ thereafter.
  $v_{\pi }(s)={\mathbb{E}}_{\pi }[G_t|S_t=s]$
• Action-Value Function, $q_{\pi }(s,a)$: The expected return after taking action $a$ in state $s$ and then following policy $\pi$.
  $q_{\pi }(s,a)={\mathbb{E}}_{\pi }[G_t|S_t=s,A_t=a]$

The action-value function, $q_{\pi }$, is often called the "Q-function", and its values are "Q-values". It tells us not just how good a state is, but how good it is to take a specific action from that state.

2. The Bellman Expectation Equation: Evaluating a Policy

The core insight of the Bellman equation is that value functions have a recursive structure. The value of the current state is directly related to the value of the possible next states.

Let's derive this relationship. We start with the definition of the state-value function and break down the return $G_t$ into two parts: the immediate reward $R_{t+1}$ and the discounted return from the next step onward, $\gamma G_{t+1}$.

$$\begin{array}{rl}{v}_{\pi }(s)& ={\mathbb{E}}_{\pi }[G_t|S_t=s]\\ & ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma G_{t+1}|S_t=s]\\ & ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s]\end{array}$$

The final step substitutes $v_{\pi }(S_{t+1})$ for $G_{t+1}$ inside the expectation, which is valid because, by definition, the value of the next state is the expected return from that point on.

To get the final equation, we need to average over all possibilities: the actions the policy might take, and the next states the environment might transition to.

The process shown in the video leads us to the Bellman expectation equation:

$v_{\pi }(s)={\sum }_{a\in A}\pi (a|s){\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma v_{\pi }(s^{\prime })\right]$

Let's break this down:

• ${\sum }_{a\in A}\pi (a|s)$: We sum over all possible actions, weighted by the probability of the policy $\pi$ choosing each action.
• ${\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)$: For each action, we sum over all possible next states $s^{\prime }$ and rewards $r$, weighted by the environment's transition probability.
• $[r+\gamma v_{\pi }(s^{\prime })]$: This is the core of the recursion. The value is the immediate reward $r$ plus the discounted value of whatever state $s^{\prime }$ we land in.

This equation provides a consistency condition. For a given policy $\pi$, the value of every state must equal the expected value of its successors. If we have the full MDP dynamics ($p$), this gives us a system of linear equations we can solve to find the value function $v_{\pi }$ for that policy. This process is called policy evaluation.

For those interested in the rigorous probabilistic derivation, the following resource provides several formal proofs. Given your mathematical background, you might find these satisfying.

3. The Bellman Optimality Equation: Finding the Best Policy

Evaluating a policy is useful, but our ultimate goal is to find the best policy, ${\pi }_{\ast }$. This policy corresponds to the optimal value functions, denoted $v_{\ast }(s)$ and $q_{\ast }(s,a)$.

$v_{\ast }(s)={\max }_{\pi }{v}_{\pi }(s)$ for all $s\in S$.

How does the Bellman equation change for an optimal policy? An optimal policy has a simple rule: it must greedily choose the action that yields the highest expected return. Instead of averaging over all actions according to a policy $\pi$, it will simply pick the best one. This means we replace the summation over actions with a max operator.

This leads us to the Bellman optimality equations:

For the state-value function:
$v_{\ast }(s)={\max }_{a\in A}{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma v_{\ast }(s^{\prime })\right]$

Notice this is the same as the expectation equation, but with ${\max }_a$ instead of ${\sum }_a\pi (a|s)$.

For the action-value function, the logic is similar. After taking action $a$ and landing in $s^{\prime }$, the optimal policy will then choose the best possible next action from $s^{\prime }$.
$q_{\ast }(s,a)={\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma {\max }_{a^{\prime }}{q}_{\ast }(s^{\prime },a^{\prime })\right]$

This last equation is particularly important and will be the foundation for many RL algorithms, like Q-Learning.

Test your understanding!

Let's use the Q-value optimality equation. Look at the grid world in the image below. The discount factor $\gamma$ is 0.5. The states are numbered 1-6, and some states have immediate rewards. The numbers inside the states represent their current estimated optimal state values, $v_{\ast }(s)$.

Assume the transitions are deterministic (if you choose to move to a state, you get there with 100% probability). Calculate the optimal Q-value for being in state 1 and moving to state 4, i.e., $q_{\ast }(s=1,a=\text{move to 4})$.

Hint: The equation is $q_{\ast }(s,a)=R(s,a,s^{\prime })+\gamma v_{\ast }(s^{\prime })$. Here, $s=1$, $a=\text{move to 4}$, so the next state is $s^{\prime }=4$. The reward is given upon entry to the next state.

Show answer

Let's break it down using the formula:
$q_{\ast }(s,a)=R(s,a,s^{\prime })+\gamma v_{\ast }(s^{\prime })$

• s: Current state is 1.
• a: Action is "move to state 4".
• s': The resulting state is 4.
• R(s, a, s'): The reward for entering state 4 is 0.
• γ: The discount factor is 0.5.
• v_*(s'): The optimal value of the next state (state 4) is given as 85.

Plugging these in:
$q_{\ast }(s=1,a=\text{move to 4})=0+0.5\times 85=42.5$

This calculation tells us the expected total future reward if we start in state 1, move to state 4, and then continue to behave optimally from there is 42.5.

4. Solving the Bellman Equations: Dynamic Programming

The Bellman optimality equations give us a consistency condition for the optimal values, but they don't give us the values directly. The max operator makes this a system of non-linear equations.

However, we can turn the optimality equation into an iterative update rule. This is the core idea behind Value Iteration, a classic algorithm from the field of Dynamic Programming.

The idea is simple:

1. Start with some initial guess for the value function, $v_0(s)$ (e.g., all zeros).
2. Repeatedly apply the Bellman optimality equation as an update rule to compute the next iteration of the value function, $v_{k+1}$, from the previous one, $v_k$.

$v_{k+1}(s)\leftarrow {\max }_{a\in A}{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma v_k(s^{\prime })\right]$

We keep applying this update for all states until the value function converges.

An alternative to Value Iteration is Policy Iteration. This algorithm iterates between two steps:

1. Policy Evaluation: Given the current policy ${\pi }_k$, calculate its exact value function $v_{{\pi }_k}$ by solving the linear Bellman expectation equation.
2. Policy Improvement: Create a new, better policy ${\pi }_{k+1}$ by acting greedily with respect to $v_{{\pi }_k}$. For each state, the new policy chooses the action that maximizes the expected one-step lookahead.

This process is guaranteed to converge to the optimal policy, often in fewer iterations than Value Iteration.

Conclusion

Today, we've journeyed from defining the value of states to deriving the fundamental equations that govern them, and finally to outlining the algorithms that solve these equations.

Key Takeaways:

• Value Functions ($v_{\pi }(s)$ and $q_{\pi }(s,a)$) quantify the expected long-term return of a policy.
• The Bellman Expectation Equation relates the value of a state to the values of its successor states for a fixed policy. It is used for policy evaluation.
• The Bellman Optimality Equation uses a max operator to define the value of a state under an optimal policy. It gives us a target to aim for.
• The Bellman equations are not solved directly but are used as the basis for iterative Dynamic Programming algorithms like Value Iteration and Policy Iteration. These methods are guaranteed to converge to the optimal value function.

Preview of the Next Lesson:

We have now covered the theory behind Value Iteration and Policy Iteration. In our next lesson, we will get our hands dirty. We will take the grid world MDP we formulated in the last lesson and implement these algorithms from scratch in Python. This will solidify your understanding by translating these mathematical update rules into working code.