Bellman Equation

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.

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.