You already know that the goal in reinforcement learning is to maximize the expected total return, $G_t$, from any given time step $t$. It’s the sum of all future rewards, discounted by a factor $\gamma$ at each step.

This formula is correct, but it's not very practical for calculation. To make it useful, we need to rephrase it recursively. Notice that the expression for $G_t$ contains a familiar-looking term. If we factor out $\gamma$ from all terms except the first, we get something interesting.

The expression inside the parentheses is just the definition of the total return starting from the next time step, $t+1$. This means we can rewrite the entire equation in a compact, recursive form.

With our recursive definition of return, we can now define the value functions. The state-value function, $V_\pi(s)$, is the expected return an agent can get starting from state $s$ and then following policy $\pi$. The action-value function, $Q_\pi(s, a)$, is the expected return from taking action $a$ in state $s$ and then following policy $\pi$.

Let's derive the equation for $V_\pi(s)$. We start with its definition and substitute our recursive formula for $G_t$.

This final line is the Bellman expectation equation for $V_\pi$. It expresses the value of a state in terms of the expected values of its successor states. It creates a system of linear equations, one for each state, whose unique solution is the value function $V_\pi$. A similar derivation gives us the equation for the action-value function, $Q_\pi(s, a)$.

The state-value and action-value functions are tightly linked. The value of a state is the expected value of the actions you can take from that state, weighted by your policy.

The expectation equations tell us the value of a given policy, but our goal is to find the best policy, $\pi_*$. An optimal policy is one that achieves a value function greater than or equal to all other policies for all states. The corresponding optimal value functions are denoted $V_*(s)$ and $Q_*(s, a)$.

To find these, we invoke the Principle of Optimality and introduce a max operator into our equations. The value of a state under an optimal policy must be equal to the expected return for the best action from that state.

This equation is the core of many reinforcement learning algorithms. Unlike the expectation equation, it is non-linear due to the max operator. Solving it requires iterative methods like value iteration or policy iteration, which are foundational to dynamic programming in RL.

Similarly, we can write the optimality equation for the action-value function.

Once we have $Q_*(s, a)$, determining the optimal policy is straightforward. For any state $s$, the best action is the one that maximizes $Q_*(s, a)$. There is always at least one such action.

Ready to test your understanding?

These equations provide the theoretical foundation for finding optimal policies in any finite Markov Decision Process, forming the bedrock of modern reinforcement learning.