Bellman Equation

This form defines the state-value function Vπ(s) for a given policy π. It expresses the value of being in a state s as the expected immediate reward plus the discounted expected value of the following state, averaged over all actions according to the policy.

• Formula: Vπ(s) = Σ_a π(a|s) Σ_s' P(s'|s,a) [ R(s,a,s') + γ Vπ(s') ]
• Purpose: Used in policy evaluation to compute how good a given policy is.
• Key Insight: It's a system of linear equations (one per state) that can be solved iteratively.

This form defines the action-value function Qπ(s,a) for a given policy π. It expresses the value of taking action a in state s and thereafter following policy π.

• Formula: Qπ(s,a) = Σ_s' P(s'|s,a) [ R(s,a,s') + γ Σ_a' π(a'|s') Qπ(s', a') ]
• Purpose: Provides a more granular evaluation than Vπ, crucial for policy improvement.
• Relation to Vπ: Vπ(s) = Σ_a π(a|s) Qπ(s,a). The Q-function is the fundamental building block for model-free algorithms like Q-Learning.

This form defines the *optimal state-value function V(s)**. It assumes the agent selects the action that maximizes the expected return, leading to a recursive definition of the best possible value.

• Formula: V*(s) = max_a Σ_s' P(s'|s,a) [ R(s,a,s') + γ V*(s') ]
• Purpose: The cornerstone of dynamic programming and planning. If you know V*, the optimal policy is to take the greedy action.
• Non-linearity: The max operator makes this a non-linear system of equations, typically solved via iterative methods like Value Iteration.

This form defines the *optimal action-value function Q(s,a)**, the most important equation in model-free RL. It gives the value of taking action a in state s and thereafter acting optimally.

• Formula: Q*(s,a) = Σ_s' P(s'|s,a) [ R(s,a,s') + γ max_a' Q*(s', a') ]
• Purpose: Directly enables learning without a model of the environment's dynamics (P). Algorithms like Q-Learning and Deep Q-Networks (DQN) approximate this equation using sampled experience.
• Key Property: The optimal policy π*(s) = argmax_a Q*(s,a).

In continuous state and action spaces (common in robotics), the sums in the standard Bellman equations are replaced by integrals, and the value functions are approximated by neural networks.

• Continuous Form: Vπ(s) = ∫_a π(a|s) ∫_s' P(s'|s,a) [ R(s,a,s') + γ Vπ(s') ] da ds'
• Algorithmic Impact: This necessitates policy gradient methods (e.g., PPO, SAC) and actor-critic architectures, which use gradient ascent to optimize the policy parameters θ.
• Challenge: The integrals are generally intractable, leading to the use of Monte Carlo sampling and stochastic gradient descent.

Temporal Difference (TD) Learning is a direct algorithmic realization of the Bellman equation. It uses bootstrapping—updating an estimate based on other estimates—which is implicit in the Bellman recursion.

• TD Error (δ): δ_t = R_t + γ V(S_{t+1}) - V(S_t). This is the difference between the TD target (R + γV) and the current estimate V, as dictated by the Bellman equation.
• Update Rule: V(S_t) ← V(S_t) + α δ_t. This incrementally moves the estimate toward satisfying the Bellman equation.
• Foundation: TD(0), SARSA, and Q-Learning are all derived by applying this TD update to different forms (Vπ, Qπ, Q*) of the Bellman equation.

The Bellman equation is the computational engine behind the two fundamental dynamic programming algorithms for solving Markov Decision Processes (MDPs). Value Iteration applies the Bellman optimality equation repeatedly until the value function converges to the optimal one. Policy Iteration alternates between policy evaluation (solving the Bellman expectation equation for the current policy) and policy improvement. These algorithms are foundational for computing optimal policies in known, discrete environments, forming the basis for more advanced RL methods.

Temporal Difference learning methods, such as TD(0) and TD(λ), are derived directly from the Bellman equation. Instead of waiting for a complete episode (like Monte Carlo methods), TD methods bootstrap by updating the value estimate of a state based on the immediate reward and the estimated value of the next state. This is a sampled, incremental approximation of the Bellman equation. Q-Learning and SARSA are quintessential TD algorithms that learn action-value functions, enabling model-free learning from interaction.

In high-dimensional state spaces (e.g., camera images), tabular value functions are impossible. The Bellman equation provides the training target for deep neural networks. In DQN, the network's parameters are updated by minimizing the difference between its current Q-value prediction and the Bellman target: reward + γ * max_a Q(next_state, a). This use of a target network stabilizes training by temporarily freezing the target used in the Bellman equation, preventing destructive feedback loops.

Actor-Critic methods decompose the learning problem into two components, both grounded in the Bellman equation. The Critic estimates the value function (or advantage function) by solving a Bellman equation, often using TD learning. The Actor updates the policy using guidance from the Critic's evaluation. Algorithms like Advantage Actor-Critic (A2C), Proximal Policy Optimization (PPO), and Soft Actor-Critic (SAC) rely on the Critic's Bellman-based value estimates to provide low-variance gradient estimates for policy improvement.

In model-based reinforcement learning, an agent learns or is given a model of the environment's dynamics (transition and reward functions). The Bellman equation is then used for planning within this internal model. Algorithms like Model Predictive Control (MPC) repeatedly solve a finite-horizon Bellman equation online to choose optimal actions. In robotics, this allows for replanning in real-time as new sensor data arrives, enabling robust control in dynamic environments where the model is approximate.

In real-world robotics, sensors provide noisy, incomplete data. The Partially Observable MDP (POMDP) framework addresses this. The core Bellman equation is extended to operate on the belief state—a probability distribution over possible true states. The Bellman equation for POMDPs defines the value of a belief state, enabling optimal decision-making under uncertainty. While exact POMDP solving is intractable, approximate solvers and modern deep RL methods for POMDPs (using recurrent networks to maintain belief) are derived from this foundational equation.

A Markov Decision Process is the foundational mathematical framework for modeling sequential decision-making, upon which the Bellman equation is defined. It formalizes an environment as a tuple (S, A, P, R, γ):

• S: A finite set of states.
• A: A finite set of actions.
• P: Transition probability function, P(s' | s, a).
• R: Reward function, R(s, a, s').
• γ: Discount factor (0 ≤ γ ≤ 1). The Markov property—that the future depends only on the present state and action—is what enables the recursive decomposition expressed by the Bellman equation.

These are the core functions decomposed by the Bellman equation.

• State-Value Function V(s): The expected cumulative discounted reward starting from state s and following policy π. The Bellman equation for V is: V^π(s) = Σ_a π(a|s) Σ_s' P(s'|s,a)[ R(s,a,s') + γV^π(s') ].
• Action-Value Function Q(s, a): The expected cumulative discounted reward after taking action a in state s and thereafter following policy π. Its Bellman equation is: Q^π(s,a) = Σ_s' P(s'|s,a)[ R(s,a,s') + γ Σ_a' π(a'|s') Q^π(s', a') ]. The optimal value functions V* and Q* satisfy the Bellman optimality equations, where the max over actions is taken.

Dynamic Programming is the classical algorithmic approach for solving planning problems given a perfect model of the environment's dynamics (P and R). It directly implements the Bellman equation through iterative application.

• Policy Evaluation: Iteratively applies the Bellman expectation equation to compute V^π for a given policy π.
• Policy Improvement: Uses the computed V^π to greedily select a better policy.
• Policy Iteration & Value Iteration: These DP algorithms alternate evaluation/improvement or directly iterate the Bellman optimality equation to find an optimal policy. They are model-based and require exhaustive sweeps of the state space, limiting them to problems with tractable, known dynamics.

Temporal Difference Learning is a class of model-free methods that learn value estimates directly from raw experience without a dynamics model. They bootstrap, updating an estimate based on a subsequent estimate, as mandated by the Bellman equation.

• TD(0) Update for V(s): V(s) ← V(s) + α [ r + γV(s') - V(s) ]. The term in brackets is the TD error.
• Connection to Bellman: The update moves V(s) towards the Bellman target r + γV(s'). Q-Learning and SARSA are TD methods that learn the Q-function. These algorithms are the primary means of solving the Bellman equation through sampling in unknown environments.

These are the two key concepts that differentiate algorithmic approaches to the Bellman equation.

• Bootstrapping: Updating an estimate of a state's value based on the estimated values of successor states. This is inherent to the Bellman equation's recursive structure and is used by DP and TD methods. It introduces bias but reduces variance and enables online learning.
• Sampling: Using individual transitions (s, a, r, s') rather than full expectation sums over all possible next states and rewards. Model-free RL (like TD learning) uses sampling to approximate the expectations in the Bellman equation, trading off computational tractability for the need for many samples. Monte Carlo methods use sampling but do not bootstrap.

The Bellman Optimality Equation is a specific form of the Bellman equation that defines the optimal value functions V* and Q*. It incorporates a max operation over actions, representing the value of following an optimal policy.

• For V*: V*(s) = max_a Σ_s' P(s'|s,a)[ R(s,a,s') + γV*(s') ]
• For Q*: Q*(s,a) = Σ_s' P(s'|s,a)[ R(s,a,s') + γ max_a' Q*(s', a') ] Significance: The fixed point of this equation is the optimal value function. Algorithms like Value Iteration and Q-Learning are driven by this optimality equation. The greedy policy derived from Q*, π*(s) = argmax_a Q*(s,a), is provably optimal.