Bellman Equation

This is the foundational form used for policy evaluation. It defines the value of a state under a specific policy π as the expected sum of immediate reward and the discounted value of the next state.

• For State-Value Function (Vπ): Vπ(s) = Σ_a π(a|s) Σ_s' P(s'|s,a) [ R(s,a,s') + γ Vπ(s') ]
• For Action-Value Function (Qπ): Qπ(s,a) = Σ_s' P(s'|s,a) [ R(s,a,s') + γ Σ_a' π(a'|s') Qπ(s', a') ]

This equation is a system of linear equations, one for each state, which can be solved to find the exact value function for a given policy.

This form defines the optimal value functions, V* and Q*, which are the maximum achievable values. It underpins planning and optimal control.

• *For Optimal State-Value (V)**: V*(s) = max_a Σ_s' P(s'|s,a) [ R(s,a,s') + γ V*(s') ]
• *For Optimal Action-Value (Q)**: Q*(s,a) = Σ_s' P(s'|s,a) [ R(s,a,s') + γ max_a' Q*(s', a') ]

The key change from the expectation equation is the replacement of the expectation over the policy's actions (Σ_a π(a|s)) with a max operator, representing the choice of the best possible action.

This is the computational procedure derived from the equations. It's an update rule applied iteratively to converge towards the true value function.

• Policy Evaluation Backup: V_{k+1}(s) ← Σ_a π(a|s) Σ_s' P(s'|s,a) [ R + γ V_k(s') ]
• *Value Iteration Backup (for V)**: V_{k+1}(s) ← max_a Σ_s' P(s'|s,a) [ R + γ V_k(s') ]
• Q-Learning Backup: Q(s,a) ← Q(s,a) + α [ R + γ max_a' Q(s',a') - Q(s,a) ]

These backups are the workhorse of algorithms like Dynamic Programming, Value Iteration, and Temporal Difference (TD) Learning.

The Bellman equation adapts based on whether a model of the environment (transition P and reward R functions) is known.

• Model-Based: The full expectation Σ_s' P(s'|s,a)[...] is used, as shown in the classic equations. This enables planning via Dynamic Programming.
• Model-Free: The expectation is replaced by sampling. For example, in Temporal Difference (TD) Learning, the update uses a single sample (s, a, r, s'): V(s) ← V(s) + α [ r + γ V(s') - V(s) ]. The Bellman equation provides the target r + γV(s') for this update.

This distinction is crucial for understanding algorithms like Q-Learning (model-free) versus Value Iteration (model-based).

The Bellman equation can be expressed in terms of the Advantage Function Aπ(s,a) = Qπ(s,a) - Vπ(s), which measures how much better an action is than the average.

• Relation: Qπ(s,a) = Vπ(s) + Aπ(s,a)
• Bellman for Aπ: This formulation is central to Actor-Critic methods. The Critic learns Vπ(s), and the advantage Aπ(s,a) ≈ r + γVπ(s') - Vπ(s) (the TD error) is used to update the Actor's policy π.

Using the advantage reduces variance in policy gradient updates, leading to more stable learning in algorithms like PPO and A2C/A3C.

In environments with deterministic dynamics, the Bellman equations simplify significantly, as the transition probability P(s'|s,a) is 1 for a specific next state.

• Deterministic Bellman Optimality: Q*(s,a) = R(s,a,s') + γ max_a' Q*(s', a') where s' is the known next state.
• Application: This simplified form is directly leveraged by algorithms like Deep Deterministic Policy Gradient (DDPG) for continuous control. The target Q-value is computed using the next state provided by a deterministic environment model or replay buffer.

This simplification is common in physics simulations used for robotic training, where the simulator's dynamics are deterministic.

A dynamic programming algorithm that directly applies the Bellman optimality equation to compute the optimal value function. It operates by iteratively updating value estimates for all states until convergence.

• Mechanism: Repeatedly applies the Bellman backup operator: V_{k+1}(s) = max_a [ R(s,a) + γ Σ_s' P(s'|s,a) V_k(s') ]
• Use Case: Solves for an optimal policy when a perfect model of the environment's dynamics (transition probabilities P and reward function R) is known.
• Property: Guaranteed to converge to the optimal value function V*.

An alternative dynamic programming algorithm that alternates between two steps: policy evaluation (computing the value of the current policy) and policy improvement (greedily updating the policy based on the new value function).

• Policy Evaluation: Uses the Bellman expectation equation to find V^π for the current policy π.
• Policy Improvement: Creates a new, better policy π' that is greedy with respect to V^π: π'(s) = argmax_a Q^π(s,a).
• Advantage: Often converges to the optimal policy π* in fewer iterations than Value Iteration, though each iteration is more computationally expensive.

A model-free, off-policy temporal difference (TD) control algorithm. It learns the optimal action-value function Q*(s,a) by directly applying a sampled version of the Bellman optimality equation.

• Update Rule: Q(s,a) ← Q(s,a) + α [ r + γ max_a' Q(s', a') - Q(s,a) ]
• Key Feature: The max operator uses the estimated value of the best next action, allowing it to learn about the optimal policy while following a different exploratory policy (e.g., ε-greedy).
• Foundation: The core of Deep Q-Networks (DQN), which uses a neural network to approximate Q(s,a) for high-dimensional state spaces.

A model-free, on-policy TD control algorithm. It learns the action-value function Q^π(s,a) for the policy π currently being executed, using the Bellman expectation equation.

• Update Rule: Q(s,a) ← Q(s,a) + α [ r + γ Q(s', a') - Q(s,a) ]
• Key Difference from Q-Learning: It uses the actual action a' taken by the current policy in the next state (s'), not the maximum value action. This makes it an on-policy learner.
• Use Case: Suitable when learning the value of the policy being followed, including during continual online learning where exploration is part of the policy.

A broad class of model-free methods for learning value functions directly from raw experience without a model. TD methods bootstrap, updating estimates based on other estimates, as formalized by the Bellman equation.

• TD(0) Update for V(s): V(s) ← V(s) + α [ r + γ V(s') - V(s) ]
• TD Error: The term δ = [r + γ V(s') - V(s)] is the TD error, driving all updates. It represents the difference between the current estimate and a better, bootstrapped estimate.
• Generalization: Algorithms like TD(λ) and Eligibility Traces provide a spectrum between pure TD (bootstrapping) and Monte Carlo (full waiting for returns) methods.

A hybrid framework that combines a policy (the Actor) and a value function (the Critic). The Critic uses the Bellman equation to evaluate the Actor's actions, providing a low-variance learning signal.

• Critic's Role: Estimates the value function V(s) or Q(s,a). It is typically trained using TD learning (e.g., minimizing TD error), which is derived from the Bellman equation.
• Actor's Update: The policy (Actor) is updated in the direction suggested by the Critic (e.g., using the advantage function A(s,a) = Q(s,a) - V(s)).
• Algorithms: Advantage Actor-Critic (A2C), Asynchronous Advantage Actor-Critic (A3C), Proximal Policy Optimization (PPO), and Soft Actor-Critic (SAC) are all advanced Actor-Critic methods.

Dynamic Programming (DP) is a mathematical optimization method for solving complex problems by breaking them down into simpler overlapping subproblems. It relies on the Bellman equation to define the optimal substructure and uses memoization or tabulation to store solutions to subproblems, avoiding redundant calculations. DP is the foundation for solving Markov Decision Processes (MDPs) when a perfect model of the environment is known.

• Key Principle: Optimal solutions are composed of optimal solutions to subproblems.
• Algorithms: Value Iteration and Policy Iteration are classic DP algorithms that apply the Bellman equation iteratively to find optimal policies.
• Limitation: Requires a complete and accurate model of the environment's transition and reward dynamics, which is often unavailable in real-world RL.

A Value Function is a core component in reinforcement learning that estimates the expected cumulative future reward. The Bellman equation provides the recursive definition for these functions.

• State-Value Function V(s): Estimates the expected return starting from state s and following a specific policy π. Defined by the Bellman Expectation Equation: V^π(s) = E[R + γV^π(S')].
• Action-Value Function Q(s, a): Estimates the expected return after taking action a in state s and thereafter following policy π. Defined by: Q^π(s, a) = E[R + γQ^π(S', A')].
• Optimal Value Functions (V, Q)**: The maximum achievable value, defined by the Bellman Optimality Equation. These functions are the fixed point of the Bellman optimality operator and define the optimal policy.

Temporal Difference (TD) Learning is a class of model-free algorithms that learn value functions directly from experience by bootstrapping—updating estimates based on other estimates. It implements a sampled, incremental version of the Bellman equation.

• TD Error: The difference between the current estimate and a better estimate (R + γV(S')). This error drives learning: δ = R + γV(S') - V(S).
• Connection to Bellman: TD methods like TD(0) and SARSA perform stochastic approximations of the Bellman expectation equation using sampled transitions instead of expected values.
• Advantage: Can learn online, from incomplete sequences, without a model of the environment. Q-Learning is a TD method that approximates the Bellman optimality equation.

A Markov Decision Process (MDP) is the formal mathematical framework for modeling sequential decision-making in reinforcement learning. The Bellman equations are defined within the MDP framework.

• Core Components: A set of states (S), actions (A), transition probabilities (P), reward function (R), and discount factor (γ).
• Markov Property: The future is independent of the past given the present state. This property is essential for the recursive form of the Bellman equation.
• Solution: Solving an MDP means finding an optimal policy π*. The Bellman equations (for expectation and optimality) are the systems of equations that the optimal value functions must satisfy, providing the basis for solution algorithms like Value Iteration.

Bootstrapping in reinforcement learning refers to updating an estimate of a state's value based on the estimated value of subsequent states. It is the mechanism by which the Bellman equation is implemented in learning algorithms.

• Mechanism: Instead of waiting for a full episode's return (Monte Carlo method), bootstrapping methods like TD learning use the current estimate V(S') as a proxy for the future.
• Bellman Connection: The term γV(S') in the Bellman update V(S) ← R + γV(S') is the bootstrap target. The agent "pulls itself up by its bootstraps" using its own predictions.
• Impact: Enables faster, online learning but introduces bias because the target depends on potentially inaccurate estimates. This is a fundamental trade-off in RL algorithm design.

The Bellman Optimality Equation is a specific form of the Bellman equation that defines the optimal value functions V* and Q*. It is the foundation for finding optimal policies.

• For V*: V*(s) = max_a E[R + γV*(S') | S=s, A=a]. The value of a state under the optimal policy is the maximum expected return achievable from that state.
• For Q*: Q*(s, a) = E[R + γ max_a' Q*(S', a') | S=s, A=a]. The optimal Q-value is the immediate reward plus the discounted value of the best action in the next state.
• Significance: These equations are contraction mappings. Algorithms like Value Iteration and Q-Learning iteratively apply these equations to converge to the optimal values, from which the optimal policy (π*(s) = argmax_a Q*(s, a)) can be directly derived.