Bellman Equation

The Bellman equation defines the optimal value of a state as the maximum expected sum of future rewards, achievable by following an optimal policy. It is expressed recursively:

• Value Function V(s): The expected return starting from state s.
• Immediate Reward R(s, a): The reward received after taking action a in state s.
• Discount Factor γ: A factor between 0 and 1 that reduces the value of future rewards.
• Successor State Value V(s'): The value of the state s' reached after the action.

The equation formalizes the principle of optimality: an optimal policy has the property that whatever the initial state and decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.

This form directly defines the optimal value function V(s)* and the *optimal action-value function Q(s, a)**. It is the cornerstone of value iteration algorithms.

For V(s):* V*(s) = max_a [ R(s, a) + γ * Σ_s' P(s' | s, a) * V*(s') ]

• P(s' | s, a) is the transition probability to state s'.
• The max operator selects the action that yields the highest expected return.

For Q(s, a):* Q*(s, a) = R(s, a) + γ * Σ_s' P(s' | s, a) * max_a' Q*(s', a')

• The Q-function evaluates the quality of a state-action pair, making the optimal policy simply π*(s) = argmax_a Q*(s, a).

This form evaluates the value of following a specific policy π, rather than the optimal one. It is fundamental to policy evaluation and policy iteration.

For V^π(s): V^π(s) = Σ_a π(a | s) * [ R(s, a) + γ * Σ_s' P(s' | s, a) * V^π(s') ]

• π(a | s) is the probability of taking action a in state s under policy π.
• This equation forms a system of linear equations (one per state) that can be solved to find the value of a given policy.

For Q^π(s, a): Q^π(s, a) = R(s, a) + γ * Σ_s' P(s' | s, a) * Σ_a' π(a' | s') * Q^π(s', a') This describes the expected return starting from (s, a) and thereafter following policy π.

In deterministic settings (where actions have certain outcomes), the Bellman equation simplifies and becomes the workhorse of dynamic programming algorithms for solving shortest path and optimal control problems.

Deterministic Bellman Equation: V(s) = max_a [ R(s, a) + γ * V( T(s, a) ) ]

• T(s, a) is the deterministic transition function that returns the next state s'.

This form enables efficient algorithms like:

• Value Iteration: Iteratively applying the Bellman update until convergence: V_{k+1}(s) = max_a [ R(s, a) + γ * V_k( T(s, a) ) ].
• Policy Iteration: Alternating between policy evaluation (solving V^π) and policy improvement (greedily acting on V^π).

In model-free reinforcement learning, where transition probabilities P and rewards R are unknown, the Bellman equation is used to derive temporal difference (TD) learning updates. These updates learn directly from experience.

The core idea is to use the current estimate to update a previous estimate, a concept called bootstrapping.

TD Update for V(s): V(s) ← V(s) + α * [ r + γ * V(s') - V(s) ]

• α is the learning rate.
• r + γ * V(s') is the TD target, an estimate of the true value.
• r + γ * V(s') - V(s) is the TD error, driving the learning.

This leads to key algorithms:

• SARSA: An on-policy TD control method that learns the Q-function: Q(s,a) ← Q(s,a) + α * [ r + γ * Q(s',a') - Q(s,a) ].
• Q-Learning: An off-policy algorithm using the Bellman optimality equation: Q(s,a) ← Q(s,a) + α * [ r + γ * max_a' Q(s',a') - Q(s,a) ].

The Bellman equation provides the solution methods for Markov Decision Processes (MDPs), the standard mathematical framework for sequential decision-making.

Key MDP Components Linked to Bellman:

• State Space S & Action Space A: Define the domain of the value functions V(s) and Q(s,a).
• Transition Model P(s' | s, a): Appears inside the expectation Σ_s' in the full Bellman equations.
• Reward Function R(s, a): Provides the immediate reward term.
• Discount Factor γ: Weights future rewards in the recursive sum.
• Policy π: The solution to an MDP is an optimal policy π*, which is derived from the optimal value functions defined by the Bellman optimality equation: π*(s) = argmax_a Q*(s, a).

The Bellman equations are the necessary and sufficient conditions for optimality in an MDP, making them the central tool for planning and learning in this framework.

An MDP is the formal mathematical framework for which the Bellman equation provides the optimality condition. It models sequential decision-making under uncertainty with four core components:

• 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' after taking action a in state s.
• Reward Function R(s, a, s'): The immediate numerical feedback received after a transition. The Bellman equation recursively defines the value function for an MDP, representing the expected long-term return from any given state.

The value function V(s) is the core object defined by the Bellman equation. It represents the expected cumulative discounted future reward an agent can achieve starting from state s and following a specific policy thereafter. The Bellman equation decomposes this value into:

• Immediate Reward: The reward for the next action.
• Discounted Future Value: The value of the state you land in, weighted by a discount factor γ (e.g., 0.9). In optimal control, we seek the *optimal value function V(s)**, which satisfies the Bellman optimality equation: V*(s) = max_a [ R(s,a) + γ Σ P(s'|s,a) V*(s') ].

Dynamic Programming (DP) is the algorithmic paradigm for solving complex problems by breaking them down into overlapping subproblems. The Bellman equation is the recurrence relation at the heart of DP for sequential problems. Key DP algorithms that operationalize the Bellman equation include:

• Value Iteration: Iteratively applies the Bellman optimality equation to converge on V*.
• Policy Iteration: Alternates between evaluating a policy (solving its Bellman equation) and improving it. These algorithms assume a perfect model of the environment (the MDP's P and R). They are foundational but often computationally intensive for large state spaces.

Q-Learning is a model-free reinforcement learning algorithm that directly learns the optimal action-value function Q(s,a)* without requiring a model of the environment's dynamics. It is based on a Bellman-like update rule: Q(s,a) ← Q(s,a) + α [ R + γ * max_a' Q(s',a') - Q(s,a) ] The term R + γ * max_a' Q(s',a') is the Bellman target, representing the estimated optimal future return. The algorithm continually adjusts its Q estimates towards this target. This approach enables agents to learn optimal policies through trial-and-error interaction, scaling to problems where the transition probabilities P are unknown.

This is the specific form of the Bellman equation that defines the optimal value function V* and optimal policy π*. For the state-value function, it is: V*(s) = max_a Σ P(s'|s,a) [ R(s,a,s') + γ V*(s') ] For the action-value function (Q-function), it is: Q*(s,a) = Σ P(s'|s,a) [ R(s,a,s') + γ max_a' Q*(s', a') ] The equation expresses a fundamental principle of optimality: an optimal policy has the property that, regardless of the initial state and initial decision, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.

Temporal Difference (TD) Learning is a class of model-free methods that learn value estimates by bootstrapping from subsequent estimates, as dictated by the Bellman equation. The core update is: V(s) ← V(s) + α [ R + γV(s') - V(s) ] Here, R + γV(s') is the TD target, a direct embodiment of the Bellman equation's one-step lookahead. The difference (TD Target - V(s)) is the TD error. Algorithms like Q-Learning and SARSA are specific TD methods. This approach unifies the ideas of Monte Carlo sampling (learning from experience) and Dynamic Programming (bootstrapping), enabling efficient online learning.