Bellman Equation

Main ideas / concepts

• Value functions under a fixed policy:

  • Define the state-value function (V^\pi(s)) as the expected return when starting in state (s) and then following policy (\pi).
  • Define the action-value function (Q^\pi(s,a)) similarly, but with the first action fixed to (a) in state (s), then following (\pi).

• “Unrolling” expectations:

  • Start from the definition of (V^\pi(s)) as an expectation over returns.
  • Expand the expectation one step into:
    • the immediate reward at time (t+1),
    • plus the discounted value of the next state (S’),
    • while properly handling that the expectation is only partially conditioned (since (S’) is random).

• Generative-process view for MDP transitions:

  • From state (s):
    1. Choose an action (a) according to (\pi).
    2. Transition to a next state (S’) according to the environment dynamics (P(\cdot \mid s,a)).
    3. Receive reward (R_{t+1}) whose expectation depends on ((s,a,S’)).
    4. Continue from (S’) following policy (\pi).

• Bellman equations as a system of equations:

  • The resulting Bellman equation for (V^\pi) gives one equation per state.
  • There are as many unknowns as states (variables (V^\pi(s)) for each state (s)).
  • The speaker notes:
    • In general, such systems have a unique solution under the given conditions.
    • Uniqueness is linked to properties of the stochastic transition matrix (rows sum to 1).
  • The Bellman equation is attributed to Richard Bellman.

• Bellman equation for (Q^\pi):

  • When expanding (Q^\pi(s,a)), since (s) and (a) are already fixed:
    • you sum only over next states (S’) (not over actions).
  • The next state value term involves (V^\pi(S’)).

• Relationship between (V^\pi) and (Q^\pi):

  • (Q^\pi(s,a)) can be written in terms of (V^\pi) at subsequent states (not (V^\pi(s)) at the same state).
  • There is an implied equation connecting them (the “ancillary equation”):
    • (V^\pi) is obtained by combining (Q^\pi) with the policy over actions.

---

Methodology / instruction-like steps (as presented)

Deriving the Bellman equation for (V^\pi(s))

• Start with the definition:
  • (V^\pi(s)) = expected return when starting at (s) and following (\pi).
• Unroll one time step:
  • Represent return as:
    • immediate reward (R_{t+1}),
    • plus discounted continuation (\gamma) times the value of the next state (V^\pi(S’)).
• Handle expectations carefully:
  • Reordering expectations is allowed, but note it’s only partial conditioning until (S’) is conditioned on.
• Use the MDP generative process:
  • For each possible action (a) sampled from (\pi(\cdot\mid s)),
  • for each possible next state (S’) sampled from (P(\cdot \mid s,a)),
  • include:
    • the probability of choosing (a),
    • the probability of transitioning to (S’),
    • the expected reward conditioned on ((s,a,S’)),
    • plus (\gamma V^\pi(S’)).
• Resulting structure:
  • Sum over all next states (S’) and all actions (a).

Solving the resulting equations (conceptual)

• Treat the Bellman equation for (V^\pi) as:
  • a linear system with:
    • one equation per state,
    • one unknown (V^\pi(s)) per state.
• The speaker claims uniqueness of the solution under stochasticity:
  • the transition matrix (P) has rows summing to 1.
  • (Details are deferred to “next class”.)

Deriving the Bellman equation for (Q^\pi(s,a))

• Fix (s) and (a):
  • no action-sampling sum is needed (because (a) is already chosen).
• Sum only over next states:
  • (S’) is random under (P(\cdot \mid s,a)).
• Use expected reward conditioned on ((s,a,S’)):
  • immediate expected reward term plus (\gamma V^\pi(S’)).
• Note:
  • (Q^\pi) is expressed using (V^\pi) of the subsequent state.

---

Speakers / sources featured

• Richard Bellman (cited as the namesake/pioneer associated with the “Bellman equation”).
• No other speakers are explicitly identified in the subtitles.