Reinforcement Learning from Scratch (Part 3): Policies, Value Functions, Bellman Equations, and Dynamic Programming

In the previous article, we learned how Markov Decision Processes (MDPs) model sequential decision-making problems. Now, the next question is: How does an agent decide which action to take?

To answer this, we introduce policies and value functions. Policies determine the agent’s behavior, while value functions estimate the long-term reward of states and actions. We will also explore the Bellman Equation and Bellman Optimality Equation, which form the mathematical foundation of planning and optimal decision-making in Reinforcement Learning.

Building on these ideas, we introduce Dynamic Programming (DP), the first planning approach in Reinforcement Learning. We study its core algorithms : Policy Evaluation, Policy Improvement, Policy Iteration, and Value Iteration and demonstrate how they are used to solve practical problems through the classic Recycling Robot and Jack’s (Rajat’s) Car Rental examples.

Introduction to Value Functions

Value functions are one of the fundamental concepts in Reinforcement Learning.

They estimate how good it is for an agent to be in a particular state or to take a specific action by measuring the expected cumulative future reward.

Value Function

These functions form the basis for evaluating policies, making optimal decisions, and deriving the Bellman equations used in many RL algorithms.

Introduction to Optimal Value Functions

Optimal value functions represent the maximum expected return an agent can achieve from a state or a state–action pair by following the best possible policy.

Optimal Value function

They provide the foundation for finding optimal policies and are characterized by the Bellman Optimality Equation, which recursively selects the action with the highest expected future reward.

Example: Recycling Robot Problem

The Recycling Robot Problem is a classic example used to illustrate how value functions and the Bellman Optimality Equation work in Reinforcement Learning.

Recycling Bot Problem

It demonstrates how an agent evaluates different actions in each state, computes their expected long-term rewards, and uses Value Iteration to find the optimal value function and the best policy.

Worked Example: Solving the Recycling Robot Problem

In this example, we apply the Bellman Optimality Equation to the Recycling Robot MDP step by step.

Starting from the MDP transition table, we construct the backup diagrams, derive the optimal value equations for each state, and solve them using Value Iteration.

Recycling Robot

This demonstrates how an agent computes the optimal state values and learns the best action to maximize long-term reward.

Example: Value Iteration for the Recycling Robot MDP

This example demonstrates how the Value Iteration algorithm computes the optimal value function for the Recycling Robot MDP. Starting with arbitrary state values, the algorithm repeatedly applies the Bellman Optimality Equation to update each state’s value until convergence. The final values represent the maximum expected long-term reward and can be used to derive the optimal policy.

Recycling Robot MDP

Appendix

Derivation of Bellman Equation

Derivation of Bellman Optimality Equation

From Bellman Equations to Dynamic Programming

Dynamic Programing

So far, we have developed the mathematical foundation of Reinforcement Learning by introducing value functions and deriving the Bellman equations. We also applied the Bellman Optimality Equation to the Recycling Robot problem and used Value Iteration to compute the optimal value function.

This naturally raises the next question: How can we systematically use the Bellman equations to solve any Markov Decision Process?

The answer is Dynamic Programming (DP).

Unlike the Dynamic Programming commonly studied in Data Structures and Algorithms (DSA), which solves optimization problems by breaking them into overlapping subproblems.

Dynamic Programming in Reinforcement Learning is a planning method that repeatedly applies the Bellman equations to compute value functions and improve policies.

It assumes that the agent has complete knowledge of the environment, including the transition probabilities and reward function.

Dynamic Programming consists of four fundamental algorithms:

• Policy Evaluation — Computes the value function for a given policy.
• Policy Improvement — Updates the policy using the computed values.
• Policy Iteration — Alternates between policy evaluation and policy improvement until the policy converges.
• Value Iteration — Directly computes the optimal value function by repeatedly applying the Bellman Optimality Equation.

In the following sections, we will study each of these algorithms in detail and apply them to the classic Jack’s Car Rental problem.

Intro to DP in Reinforment Learning

Dynamic Programming (DP) is the first planning method in Reinforcement Learning for finding an optimal policy when the agent has a complete model of the environment.

Dynamic Programing

It uses the Bellman equations to iteratively evaluate the value of states and improve the policy until it converges to the optimal solution.

In this section, we introduce the core ideas of Dynamic Programming, including its two fundamental tasks

— Policy Evaluation, which estimates the value of a given policy, and

— Control, which improves the policy to obtain a better one.

These concepts form the foundation of Policy Iteration and Value Iteration algorithms.

Policy Evaluation

Policy Evaluation is the process of computing the state-value function for a given policy.

Starting with an initial estimate of the state values (typically all zeros), the Bellman Expectation Equation is applied repeatedly to update the value of every state.

Dynamic Programming

These updates continue until the values converge, providing an estimate of the expected long-term return when following the given policy.

Policy Improvement

Policy Improvement is the process of improving a policy using the state-value function obtained from Policy Evaluation.

For each state, the expected return of all possible actions is compared, and the action with the highest expected return is selected.

Policy Improvement

Repeating policy evaluation and policy improvement alternately produces increasingly better policies until the policy no longer changes, resulting in the optimal policy.

Policy Iteration

Policy Iteration is a Dynamic Programming algorithm used to find the optimal policy in a Markov Decision Process (MDP). Instead of searching directly for the best policy, it alternates between two complementary steps: Policy Evaluation, which computes the value function for the current policy, and Policy Improvement, which updates the policy by selecting actions that yield higher expected returns. Each iteration produces a policy that is at least as good as the previous one, and this process continues until the policy no longer changes. At convergence, the algorithm returns the optimal policy (π) along with its corresponding optimal value function (V).

Policy Iteration

Example : Rajat’s Car Rental Problem using Policy Iteration

Rajat’s Car Rental Problem is a classic Dynamic Programming example that demonstrates how Policy Iteration can be used to solve a real-world decision-making problem.

Rajat’s Car Rental Problem

By modeling the car rental business as a Markov Decision Process (MDP), we define the states, actions, rewards, and transition probabilities, then repeatedly apply Policy Evaluation and Policy Improvement to learn the optimal policy for maximizing the expected long-term profit.

Conclusion

In this article, we developed the mathematical foundation of Reinforcement Learning by introducing policies, value functions, optimal value functions, and the Bellman and Bellman Optimality Equations. We then showed how these equations become practical planning algorithms through Dynamic Programming, covering Policy Evaluation, Policy Improvement, Policy Iteration, and Value Iteration.

Using the Recycling Robot and Rajat’s Car Rental examples, we saw how an agent can iteratively evaluate states, improve its policy, and ultimately learn an optimal decision-making strategy when the environment model is known.

These concepts form the foundation of many classical Reinforcement Learning algorithms and provide the intuition needed for the next stage of Reinforcement Learning, where the environment model is no longer available.

In the next article, we will explore Monte Carlo methods, which learn directly from experience without requiring knowledge of the transition probabilities or reward function.