# Bellman Equations

Recursive relations expressing a state's value in terms of immediate reward and the discounted value of successors.

**Rests on:** Markov Decision Processes, Recursive Thinking

*Machine Learning · Reinforcement Learning*


## Why learn this

You want to teach a computer to make good choices in situations where today’s actions change tomorrow’s options, like deciding which route to take to avoid traffic or when to wait for a better price on an item. The Bellman equation is the tool that allows a system to break this big, complex problem into small, manageable steps. It lets the system calculate how much value each current step adds to the total goal, ensuring that short-term gains don't accidentally lead to long-term losses. Without it, trying to plan for every possible future outcome would be computationally impossible.


## The intuition

Imagine you are navigating a maze. You stand at a junction (a **state**) and have several paths to choose from (an **action**). You don't know which path leads out immediately; you have to find out by trying. The Bellman equation answers the question: 'How valuable is it to be at this specific junction?' It breaks this value down into two parts:

1. The immediate reward you get right now for being here (for example, finding a gold coin on the floor).
2. The value of the next junction you will arrive at.

The equation says: Value = Immediate Reward + (Discounted Value of Next Junction).

The 'discount' is crucial. Imagine you are promised $10 today or $10 in a year. Most people prefer the money today because they can use it, invest it, or simply enjoy it sooner. In our maze, if you move toward the exit, the value of being one step closer is high. If you move away from the exit, even if you get a small coin now, the value of your position drops because the future exits are further away.

Here is how the math works with specific numbers in a simplified maze:
- Suppose being at the Exit is worth 10 points.
- Suppose moving to the Exit gives an immediate reward of 2 points (for effort).
- You set a discount factor of 0.8, meaning future value counts as 80% of present value.

If you are at Junction A and choosing between:
Option 1: Move to Junction B, which is one step away from the Exit.
The immediate reward for moving to B is 0 points (it’s just a hallway). The value of Junction B is therefore calculated as: 0 + (0.8 * 10) = 8 points. So, being at Junction A via Option 1 has a projected value of 8 points.

Option 2: Move to Junction C, which is far from the Exit, but gives you a treasure worth 5 points immediately.
The immediate reward is 5 points. Suppose Junction C leads back toward the exit but adds complexity. Let's say the calculated future value of Junction C is 6 points (from its own sub-calculations). With the discount factor, the future part is 0.8 * 6 = 4.8 points. Total value for Option 2 is 5 + 4.8 = 9.8 points.

Even though Option 1 gets you closer to the goal linearly, Option 2 offers a higher total 'value' because the immediate reward is substantial enough to offset being slightly further from the final target. The Bellman equation lets you compare these two options precisely.


## An analogy

Think of calculating the value of your job salary by looking at your bank account balance every day. You don't just look at today's deposit; you look at today's deposit plus what that money will be worth tomorrow when it sits in the savings account earning interest. The Bellman equation is like a daily report card that says: 'Today’s Value = Money in Hand + (Interest Rate × Money Saved for Tomorrow).' It forces you to weigh immediate cash against future growth in a single, consistent formula.

Where the analogy stops working: In banking, the interest rate and rules are fixed and known. In real decision-making, like navigating a maze or trading stocks, you often don't know exactly what will happen next until you try it.


## Definition

The Bellman equation is a self-referential formula—one where the answer depends on solving the same question for future steps—that defines the value of a current situation as the sum of the immediate reward received plus a discounted estimate of the value of the next situation reached by taking an action.

Formally: V(state) = Reward + Discount_Factor * V(next_state)


## How it connects

This concept sits beside Dynamic Programming, which is a general problem-solving strategy that solves complex issues by breaking them into simpler, overlapping sub-problems and storing their results to avoid repetition, and Markov Decision Processes, which are mathematical models used to describe environments where outcomes are partly random and partly under the control of a decision-maker. Understanding this equation is the first step toward learning how systems make sequential decisions.


## The mathematics

The branch of mathematics here is **algebra and recursion**. Algebra because we are forming equations with variables and constants, and recursion because the equation refers to itself—the value of a state is defined in terms of the value of other states. No calculus or probability is needed for the basic Bellman equation, but we'll build a tiny bit of arithmetic to see it numerically.

Let's put it in plain words. Imagine you have a set of states, like locations in a maze. In each state, you can choose an action, and that action leads you to a new state with some probability (maybe it's deterministic—one action always leads to the same next state). Along the way, you receive a reward—a number, maybe positive, maybe negative. The **value** of a state is: *the sum of the immediate reward and the (discounted) value of the next state*. The discount is a number between 0 and 1, often called **gamma**. If gamma is 0.9, then a reward of +10 next step is only worth +9 today. This reflects the fact that future rewards are uncertain and you'd rather have them sooner.

The Bellman equation for a deterministic environment is:

*V(s) = R(s, a) + gamma × V(s')*

where `s` is the current state, `a` is the action you take, `s'` is the next state, and `R(s, a)` is the reward you get for taking action `a` in state `s`. Notice that this equation is recursive: to compute V(s), you need V(s'), and to compute V(s'), you need V(s''), and so on. In practice, we don't compute it all at once; we use iteration, starting with an arbitrary guess and updating until the values settle down.

V(s) = R(s, a) + γ * V(s')

where V(s) is the value of state s, R(s, a) is the immediate reward for taking action a in state s, γ (gamma) is the discount factor between 0 and 1, and s' is the next state after taking action a.


## A worked example

```
Consider a simple two-state world: State A and State B. From State A, you can take an action that leads to State B with a reward of +5. From State B, you can take an action that leads back to State A with a reward of +2. The discount factor gamma = 0.9. Initially, we guess that the value of both states is 0.

Step 1: Initial guess: V(A) = 0, V(B) = 0   # We start with a guess for the values.
Step 2: Update V(A): 5 + 0.9 × V(B) = 5 + 0.9 × 0 = 5   # Using the Bellman equation, V(A) is the immediate reward (5) plus discounted value of next state (B).
Step 3: Update V(B): 2 + 0.9 × V(A) = 2 + 0.9 × 0 = 2   # Similarly, V(B) updates using its immediate reward and the guessed value of A.
Step 4: Now we have V(A) = 5, V(B) = 2. Iterate again.   # We use these new values to compute better estimates.
Step 5: Update V(A): 5 + 0.9 × 2 = 5 + 1.8 = 6.8   # Now V(B) influences V(A) more.
Step 6: Update V(B): 2 + 0.9 × 5 = 2 + 4.5 = 6.5   # And V(A) influences V(B).
Step 7: Update V(A): 5 + 0.9 × 6.5 = 5 + 5.85 = 10.85   # Values keep growing as they bootstrap from each other.
Step 8: Update V(B): 2 + 0.9 × 10.85 = 2 + 9.765 = 11.765   # And so on.
Step 9: After many iterations, V(A) and V(B) converge to the same value, around 70.   # The recursive chain sums to a geometric series. The exact solution can be found by solving V = R + gamma × V, which gives V = R / (1 - gamma) for this symmetric case.

Result: After many iterations, V(A) ≈ 70 and V(B) ≈ 70. The exact value is 5 / (1 - 0.9) = 50 for A's immediate reward, but because rewards are cyclical, the total value grows more—actually the equations are coupled, and solving them gives V(A) = V(B) = 35? But let's redo the arithmetic properly. We'll do a few more steps until convergence: Let's compute analytically: V(A) = 5 + 0.9*V(B); V(B) = 2 + 0.9*V(A). Solving: Substitute V(B) into first: V(A) = 5 + 0.9*(2 + 0.9*V(A)) = 5 + 1.8 + 0.81V(A) => 0.19V(A) = 6.8 => V(A) = 35.789. Similarly V(B) = 2 + 0.9*35.789 = 34.21. That's the fixed point.
```


## From scratch, in Python

```python
# Plain Python implementation of value iteration for the simple two-state world

# A list of states
states = ['A', 'B']

# A dictionary to hold the current value of each state
values = {'A': 0.0, 'B': 0.0}

# The discount factor
gamma = 0.9

# A dictionary that maps each (state, action) to the next state and reward
# For simplicity, we assume there's only one action per state
environment = {
    ('A', 'go'): {'next': 'B', 'reward': 5},
    ('B', 'go'): {'next': 'A', 'reward': 2},
}

# Value iteration: repeat many times until values stop changing
for iteration in range(100):
    new_values = {}
    for state in states:
        # We only have one action 'go' for each state in this simple example
        action = 'go'
        transition = environment[(state, action)]
        next_state = transition['next']
        reward = transition['reward']
        # Bellman update: V(s) = reward + gamma * V(s')
        new_values[state] = reward + gamma * values[next_state]
    # Check if values changed significantly
    delta = max(abs(new_values[s] - values[s]) for s in states)
    values = new_values
    if delta < 0.001:
        break

print("Converged values:", values)
```


## The same thing, with a framework

NumPy is not needed for such a small example, but for larger state spaces, you'd use vectorized operations. Here is a NumPy version:

```python
import numpy as np

# States: 0 and 1
num_states = 2
values = np.zeros(num_states)
gamma = 0.9
# Reward for moving from state 0 to 1, and from 1 to 0
rewards = np.array([5, 2])
# Transition matrix: next_state = transition[current_state]
transition = np.array([1, 0])  # deterministic

for i in range(100):
    new_values = rewards + gamma * values[transition]
    if np.max(np.abs(new_values - values)) < 0.001:
        break
    values = new_values

print(values)
```

Under the hood, `values[transition]` is picking the value of the next state using the state index, just like the dictionary lookup in the plain Python version.


## What the code does

First, we create a **list** of states: `['A', 'B']`. A list is a container that holds items in order. Next, we create a **dictionary** called `values` to store the current value for each state. A dictionary is like a lookup table: it maps keys (like the string 'A') to values (like the initial guess 0.0). We set both to 0.0 as our starting guess. The **discount factor** `gamma` is set to 0.9. Then we define the `environment` as another dictionary. The keys are tuples `(state, action)` and the values are themselves dictionaries with 'next' and 'reward'. This captures the transition: taking 'go' in 'A' leads to 'B' with reward 5, and vice versa. Now we do the main loop: we iterate 100 times. In each iteration, we create a new empty dictionary `new_values`. For each state, we look up the transition, get the next state and reward, and apply the Bellman update. The line `delta = max(abs(new_values[s] - values[s]) for s in states)` computes how much the values changed across all states, and if the change is small (less than 0.001), we stop early. This is called **value iteration**. Finally, we print the converged values.


## Common misconceptions

**Bellman equation is only for toy problems** — I can understand this simple two-state example, but it's not used in real AI systems.

The Bellman equation scales to millions of states (like Atari game screens) and to continuous action spaces (like robotic control). It is the foundation of deep RL, which has mastered Go, Dota 2, and many real-world robotics tasks. In fact: The recursive principle is the same at any scale. In deep RL, the value function is approximated by a neural network rather than a lookup table, but the update rule still follows the Bellman equation.

**Gamma is optional or just a hyperparameter that doesn't change behavior** — The discount factor just slows down learning, but I can set it to 1 and it's fine.

If gamma = 1, the equation becomes V(s) = R + V(s') and can blow up to infinity for continuing tasks, unless there are absorbing terminal states. Also, it changes the optimal policy: a higher gamma makes the agent care more about long-term rewards, which could lead it to favor strategies that pay off later, even if the immediate cost is high. In fact: Gamma is between 0 and 1, and it determines how far the agent looks into the future. Setting it too low makes the agent myopic; setting it too high can lead to divergence. It is a knob that directly controls the effective planning horizon.

**Bellman equation is only for deterministic environments** — The equation only works when taking an action always leads to the same next state, but real environments are stochastic.

The Bellman equation has a version for stochastic environments where you sum over all possible next states, weighted by their probability: V(s) = Σ_a π(a|s) Σ_s' P(s'|s,a) [R(s,a,s') + γ V(s')]. This is the expected value form. In fact: The deterministic version is a special case. The general form uses expectations, which assumes you know the transition probabilities (model-based) or have to estimate them from data (model-free).

**The Bellman equation is the same as the Q-learning update** — I read that Q-learning uses the Bellman equation, so learning the Bellman equation means I already know Q-learning.

The Bellman equation is a mathematical relation that defines the value of a state. Q-learning is a specific *algorithm* that estimates the optimal Q-values (action values) using a particular update rule, often without knowing the transition probabilities and by sampling from experience. In fact: Q-learning uses a Bellman-like equation for Q-values, but it is a procedure for learning them, not the definition itself. The Bellman equation is the theoretical foundation; Q-learning is one way to solve it.


## In short

The Bellman equation is a recursive rule: the value of a state is the immediate reward plus the discounted value of the next state. It is the cornerstone of reinforcement learning, enabling algorithms like value iteration and Q-learning to compress a potentially infinite sequence of rewards into a single update step. Understanding this equation is your gateway to RLHF, AlphaGo, and the entire field of AI agents that learn from interaction.


## Where this is used

The Bellman equation is the engine of **reinforcement learning**, and its fingerprints are everywhere in modern AI.

### Large Language Models (LLMs)
You might be surprised to hear this, but the same Bellman-style recursion powers **RLHF (Reinforcement Learning from Human Feedback)**. When a company like OpenAI fine-tunes a model like ChatGPT, they first train a reward model that scores a response based on how aligned it is with human preferences. Then they use RL algorithms—specifically **PPO (Proximal Policy Optimization)**—which internally estimate the value of being in a particular state (i.e., having generated a certain sequence of tokens so far). The reward model provides the immediate reward for generating the next token, and the value function (estimated via Bellman-style updates) predicts the expected future reward from that point. PPO uses the Bellman equation to compute an 'advantage'—how much better it is to take a specific action versus the average—and then updates the LLM's weights to increase the probability of actions that lead to higher-than-average rewards. Without the Bellman equation, the credit for a good response would have to be assigned uniformly across all tokens, which is inefficient; the recursive formalism lets the algorithm assign blame to the specific token that caused the good outcome.

### Small Language Models on Devices
When running a language model on a phone or laptop, you usually don't do RL training directly (it's too expensive). However, you might use a model distilled (compressed) from a larger, RLHF-aligned model. The distillation process often uses a value function from the teacher model to guide the student, and that value function is computed using Bellman-style recursive reasoning. Also, on-device reinforcement learning for lightweight tasks like keyboard auto-correction or simple chatbots uses the same Bellman machinery, albeit with smaller state spaces and simpler value estimates.

### Retrieval-Augmented Generation (RAG)
Bellman equations don't appear directly in vanilla RAG, where you just retrieve documents and stuff them into the context. However, if you are doing *iterative* retrieval—where the LM decides whether to search again, look at a new set of documents, or stop—you can model that as a Markov decision process. The decision to continue vs. stop is a policy, and the Bellman equation helps compute the expected value of continuing, which informs the stopping criterion. More advanced agentic RAG systems use RL (again relying on Bellman-style value functions) to learn when to stop fine-tuning.

### Agentic Systems (Planning and Tool Use)
This is the most direct application after classical RL. An agent, like a software assistant that can browse the web, call APIs, or send emails, is operating in a state space. Each action (tool call) gives a reward or penalty (e.g., success, failure). The agent needs to decide whether to take a shortcut or a long but reliable path. The Bellman equation is the theoretical foundation for computing the expected value of being in any particular point of its task. In practice, you might use **Monte Carlo Tree Search** (as in AlphaGo) to evaluate which actions are best; MCTS uses a value network (trained via Bellman updates) to estimate the value of a node without expanding all possibilities. The combination of search and value estimation is precisely the Bellman principle—the value of a node is the reward plus the discounted value of the best successor.

### Everyday Applied Machine Learning (Recommendation, Vision, Forecasting, Fraud)
Reinforcement learning and the Bellman equation are used in **recommendation systems** to model user engagement as a sequence of actions (show recommendation, user clicks or not). The reward is the click, and the Bellman equation helps decide which recommendation to show now to maximize long-term click-through. In **fraud detection**, an RL agent could decide whether to block a transaction or not; the reward is a trade-off between blocking legitimate transactions (false positave) and letting fraudulent ones through. The Bellman equation helps decide the optimal blocking policy over time. In **autonomous driving**, the vehicle's decision to brake or accelerate is an MDP, and the value of a state is computed with Bellman equations to maximize safety and efficiency. In **speech recognition**, sequence-to-sequence models often use RL with Bellman-style objectives to generate transcriptions that maximize expected user satisfaction (e.g., for custom wake words).

### What a Developer Actually Does
A developer using RL will typically use a library like **OpenAI Gym** (or its successor, Gymnasium) to define the environment, then use a RL library like **Stable Baselines3** that implements PPO or DQN. The Bellman equation is built into those libraries' internal value network updates. In a custom setting, they might write PyTorch code to implement a Q-network that estimates Q(s, a) = reward + γ max_a' Q(s', a'). That is the Bellman equation in action. If done badly—forgetting the discount, using too high a learning rate, or not exploring enough—the values may diverge or the agent may converge to a suboptimal policy. The Bellman equation is not just a nice theory; it's the mathematical guarantee that if you update your value estimates using the recursive relation, you will converge to the true values under certain conditions.


---

Read this on the web: https://basavapurushottam.com/learn-ai/bellman-equations
