Bellman Equation

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

Formula: V^π(s) = Σ_a π(a|s) Σ_{s', r} p(s', r | s, a) [ r + γ V^π(s') ]

• p(s', r | s, a): Environment dynamics (transition probability & reward).
• γ: Discount factor (0 ≤ γ ≤ 1).
• This is a consistency condition that any value function for a given policy must satisfy.

This equation defines the *optimal state-value function V(s)**. It assumes the agent selects the single action that maximizes the sum of immediate and future value, rather than averaging over a policy.

Formula: V*(s) = max_a Σ_{s', r} p(s', r | s, a) [ r + γ V*(s') ]

• The max operator replaces the policy-weighted sum.
• V*(s) represents the maximum achievable expected return starting from state s.
• Solving this equation yields the optimal value function, from which an optimal policy can be derived (e.g., π*(s) = argmax_a Q*(s,a)).

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

Formula: Q^π(s, a) = Σ_{s', r} p(s', r | s, a) [ r + γ Σ_{a'} π(a'|s') Q^π(s', a') ]

• The inner sum averages over actions a' in the next state s'.
• This form is central to policy evaluation algorithms and is the foundation for SARSA.

This equation defines the *optimal action-value function Q(s,a)**. It assumes optimal actions are taken in all future steps.

Formula: Q*(s, a) = Σ_{s', r} p(s', r | s, a) [ r + γ max_{a'} Q*(s', a') ]

• The future value is the maximum Q* value over actions in the next state.
• This is the fundamental equation of Q-Learning. The optimal policy is π*(s) = argmax_a Q*(s, a).
• It provides a recursive target for Temporal Difference (TD) learning.

All Bellman equations can be viewed as fixed-point equations. Define a Bellman operator T^π (for policy evaluation) or T* (for optimality). The equation V = T(V) states that applying the operator to the value function leaves it unchanged.

Key Properties:

• Contraction Mapping: For γ < 1, the Bellman operator is a contraction. This guarantees that repeated application (value iteration) converges to a unique fixed point.
• Algorithmic Foundation: Value Iteration (V_{k+1} = T* V_k) and Policy Iteration (alternating policy evaluation V = T^π V and policy improvement) are direct applications of this fixed-point view.

In deterministic environments, the equations simplify dramatically, as the transition probability p(s', r | s, a) is 1 for a specific outcome.

Optimality Equation (Deterministic): V*(s) = max_a [ r(s, a) + γ V*(s') ] Q*(s, a) = r(s, a) + γ max_{a'} Q*(s', a')

Implications:

• The expectation operators (Σ) disappear.
• This simplification is often used in planning algorithms and textbook examples.
• It clearly illustrates the recursive, one-step lookahead structure of the Bellman principle.

The Markov Decision Process (MDP) is the formal mathematical framework that defines the sequential decision-making problem the Bellman equation solves. An MDP is defined by:

• State Space (S): All possible situations the agent can be in.
• Action Space (A): All possible moves the agent can make.
• Transition Function P(s'|s, a): The probability of moving to state s' from state s after taking action a.
• Reward Function R(s, a, s'): The immediate feedback received for the transition.
• Discount Factor (γ): A value between 0 and 1 that reduces the importance of future rewards. The Bellman equation provides the recursive solution for finding the optimal value function within this MDP framework.

The Value Function, denoted as V(s), is the core object defined by the Bellman equation. It represents the expected cumulative discounted reward an agent can achieve starting from state s and following a specific policy thereafter. The Bellman Expectation Equation for a policy π is: V^π(s) = Σ_a π(a|s) Σ_s' P(s'|s,a) [ R(s,a,s') + γ V^π(s') ] This equation states that the value of a state is the weighted average (over actions and next states) of the immediate reward plus the discounted value of the next state. The Bellman Optimality Equation defines the optimal value function V*(s), which is the maximum value achievable from any state.

The Q-Function, or Action-Value Function, denoted as Q(s, a), is a more granular cousin of the value function. It represents the expected cumulative reward of taking a specific action a in state s and then following a policy. Its Bellman equation is central to algorithms like Q-Learning: Q(s,a) = Σ_s' P(s'|s,a) [ R(s,a,s') + γ max_a' Q(s', a') ] Key differences from the V-function:

• Input: Takes both a state and an action.
• Use: Directly informs the optimal policy: choose the action with the highest Q-value.
• Algorithm Link: The update rule in Q-Learning Q(s,a) ← Q(s,a) + α [ r + γ max_a' Q(s',a') - Q(s,a) ] is a stochastic approximation of the Bellman optimality equation for Q.

Dynamic Programming (DP) is the overarching algorithmic paradigm for solving complex problems by breaking them down into simpler overlapping subproblems. The Bellman equation is the optimal substructure property that makes DP applicable to MDPs. DP algorithms like Value Iteration and Policy Iteration work by:

1. Initializing arbitrary value estimates.
2. Iteratively applying the Bellman equation as an update rule (e.g., V_{k+1}(s) = max_a Σ_s' P(s'|s,a)[R + γ V_k(s')]).
3. Converging to the optimal value function as k → ∞. This "bootstrapping"—using current estimates to improve future estimates—is the essence of DP and is inherited by temporal difference learning methods.

Temporal Difference (TD) Learning is a class of model-free RL algorithms that learn directly from experience without a model of the environment (P and R). They operationalize the Bellman equation through incremental updates. The core TD error for value prediction is: δ = r + γ V(s') - V(s) This error quantifies the difference between the current estimate V(s) and the better estimate r + γV(s') suggested by the Bellman equation (the TD target). The update V(s) ← V(s) + αδ moves the estimate toward the target. SARSA and Q-Learning are TD methods for learning the Q-function. TD learning blends ideas from Monte Carlo (learning from actual returns) and DP (bootstrapping).

In the continuous-time and continuous-state domain of Optimal Control, the Bellman equation generalizes to the Hamilton-Jacobi-Bellman (HJB) equation, a partial differential equation. For a continuous-time system with dynamics dx/dt = f(x, u) and cost rate c(x, u), the HJB equation for the optimal cost-to-go function J*(x) is: min_u [ c(x, u) + ∇J*(x) · f(x, u) ] = 0 This is the continuous-time analog of the discrete Bellman optimality equation. Solving the HJB equation yields the optimal control policy u*(x). While often intractable to solve exactly for nonlinear systems, it provides the theoretical foundation for approximate methods like Model Predictive Control (MPC), which solves a finite-horizon version of the problem online.