Bellman Equations

The Bellman Equation, named after Richard Bellman, is a fundamental mathematical relationship that defines the optimal behavior of a system over time in a sequential decision-making process. It is a cornerstone of Dynamic Programming and Reinforcement Learning.

Core Concept

At the heart of the Bellman equation is the Principle of Optimality:

“An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.”

The equation decomposes a multi-stage decision problem into a series of simpler recursive steps. It expresses the value of a state as the sum of the immediate reward and the discounted value of the next state:

$V(s)={\max }_a\left(R(s,a)+\gamma {\sum }_{s^{\prime }}P(s^{\prime }|s,a)V(s^{\prime })\right)$

where:

• $V(s)$ is the value of state $s$.
• $a$ is the action taken.
• $R(s,a)$ is the immediate reward.
• $\gamma \in [0,1]$ is the discount factor.
• $P(s^{\prime }|s,a)$ is the transition probability from state $s$ to state $s^{\prime }$ given action $a$.

Key Features

1. Recursive Decomposition: Breaks down the total expected return of a trajectory into the immediate reward plus the discounted expected return from the subsequent state, avoiding the need to calculate the entire trajectory.
2. Two Primary Forms:
   • Bellman Expectation Equation: Computes the expected return of a state under a specific policy $\pi$.
   • Bellman Optimality Equation: Computes the maximum possible expected return from a state under the optimal policy ${\pi }^{\ast }$.
3. Model-Based vs. Model-Free Division:
   • In Dynamic Programming (model-based), the exact transition probabilities $P$ and reward function $R$ are known, allowing direct calculation of the value functions via algorithms like Value Iteration or Policy Iteration.
   • In Reinforcement Learning (model-free), the environment’s dynamics are unknown, and algorithms estimate the values using temporal difference errors and sample experiences.

Related Topics

• Markov Decision Process (MDP): The formal mathematical framework for modeling decision-making where outcomes are partly random and partly under the control of a decision maker.
• Q-Learning: A model-free reinforcement learning algorithm that uses a variant of the Bellman equation (specifically, Q-value iteration) to find the optimal action-selection policy.
• Value Iteration & Policy Iteration: Iterative algorithms in dynamic programming that solve the Bellman optimality equation to find optimal policies.
• Temporal Difference (TD) Learning: A method that updates value estimates based on other learned estimates, directly utilizing the recursive structure of the Bellman equation.