Issue #01: All about Reinforcement Learning(2)

This week is on MDPs, TD and Bellman's Equation with RL environment. Next week would be on Deep Q-Nets. Sorry for the delay:caught up with work. After q-learning, I will get to Issue #02: on optimizers used along with a general deep dive into DL.

Giving the Agent a World:MDPs, Bellman & TD Learning

Part 1 showed how an agent picks the best slot machine using ε-greedy and UCB. The key gap left open: bandits have no state. Every pull is independent. Real environments are different — your action today changes the world you wake up in tomorrow. That is exactly what MDPs formalise.

1 — Markov Decision Processes

An MDP is the mathematical skeleton of almost every RL problem. It has exactly four ingredients: States (S) — every situation the agent can find itself in; Actions (A) — the choices available; Transitions T(s,a,s') — the probability of each next state given the current state and action; and Rewards R(s,a,s') — the signal received after each transition.

The "Markov" in MDP is a critical assumption: the next state depends only on the current state and action, not on any prior history. Your entire past is compressed into where you are right now.

P(s_t+1 | s_t, a_t, s_t-1, ...) = P(s_t+1 | s_t, a_t)

The Markov property: the past is irrelevant given the present state. Everything needed to decide is in s_t.

REAL-WORLD ANALOGY

Think of GPS navigation. Your next turn depends on where you are right now (state) and which way you go (action) — not every road you drove to get here. That is Markov. Contrast with poker: the history of bets reveals hidden information. Knowing only the current hand is insufficient — which is exactly why poker is so much harder to solve.

Policy, Return, and the Discount Factor γ

The agent's behaviour is described by its policy π(s) — a mapping from every state to an action. The goal is to find the optimal policy π* that maximises the expected return: the total discounted sum of future rewards.

G_t = R_t+1 + γ·R_t+2 + γ²·R_t+3 + ... = Σ γᵏ · R_t+k+1

γ ∈ [0,1] is the discount factor. γ → 0 = myopic agent (only cares about immediate reward). γ → 1 = far-sighted. Most real systems use γ = 0.95–0.99.

Figure 1 — Discount weight γᵏ for a reward k steps in the future. With γ=0.5 the agent is nearly blind beyond 5 steps; with γ=0.99 it cares substantially about rewards 50+ steps ahead.

2 — The Bellman Equation

In 1957, Richard Bellman had a deceptively simple insight: the value of a state is the immediate reward you get leaving it, plus the discounted value of wherever you end up. This recursive relationship is the backbone of all of modern RL.

V*(s) = max_a  Σ_s'  T(s,a,s') · [ R(s,a,s') + γ · V*(s') ]

V*(s) = optimal value of state s. The max is over actions; the sum is over possible next states. V*(s) appears on both sides — it is a system of equations, not a closed-form formula.

The Q-function is the action-level equivalent — how good is taking action a in state s, then acting optimally afterwards? This will be the heart of Q-Learning in Part 3:

Q*(s,a) = Σ_s'  T(s,a,s') · [ R(s,a,s') + γ · max_a'  Q*(s',a') ]

Once you know Q*, the optimal policy is trivial: π*(s) = argmax_a Q*(s,a) — no further calculation needed.

Figure 2 — Value Iteration across Bellman sweeps for γ=0.90 (left) and γ=0.99 (right). Each sweep propagates reward information one step further back from the goal state. Higher γ requires more sweeps but produces higher absolute values across all states.

THE DOMINO ANALOGY

Value Iteration is like toppling dominoes in reverse. The goal state has a known value. One step back, states adjacent to the goal can now be estimated. Two steps back, states adjacent to those. Each sweep propagates the signal one step further from the reward source. After enough sweeps, the value reaches every reachable state in the MDP.

3 — Temporal Difference Learning

Value Iteration is exact but impractical — it requires knowing the full transition model T(s,a,s') upfront, which we almost never have. Temporal Difference (TD) learning is the model-free escape: learn V(s) purely from experience, one step at a time, without ever knowing the environment's mechanics.

After every real transition (s → s' with reward r), compute how wrong your estimate was — the TD error δ — and nudge V(s) in the right direction:

δ  =  r + γ·V(s')  −  V(s)

V(s)  ←  V(s) + α · δ

δ = TD error. Positive δ = V(s) was underestimated. Negative δ = overestimated. α = learning rate. This is TD(0), the simplest variant.

TD vs Monte Carlo: Two Philosophies

Before TD, the dominant approach was Monte Carlo (MC) — run the full episode to completion, collect the actual return G, then update every state visited. TD does not wait. It bootstraps: using its own current estimate V(s') as a stand-in for the future, updating after every single step.

Property	Monte Carlo	TD(0)
Update timing	End of episode	Every single step
Target used	Actual return Gₜ	r + γ·V(s') estimate
Works on continuing tasks?	No	Yes
Variance	High (full trajectory)	Low (one-step only)
Bias	None — uses real G	Yes — bootstraps estimate
Converges to	V^π exactly	V^π with decaying α

Figure 3 — TD(0) vs Monte Carlo estimation error over 600 episodes (averaged over 5 seeds). TD converges faster and more stably due to lower variance, while MC has unbiased but noisy updates. The gap is larger with a slow learning rate (left).

TD(λ) — The Best of Both Worlds

TD(0) looks one step ahead. Monte Carlo looks all the way to the end. TD(λ) slides smoothly between the two using eligibility traces and a parameter λ ∈ [0,1]. When λ = 0, it collapses to TD(0). When λ = 1, it approximates Monte Carlo. Most practical implementations use λ ≈ 0.9.

G^λ_t = (1−λ)  Σ_n=1^∞  λⁿ⁻¹ · G^(n)_t

G^(n) = n-step return. TD(λ) is a geometric blend of all n-step returns — higher λ means more weight on longer look-ahead horizons.

Figure 4 — The TD(λ) spectrum. As λ increases from 0 to 1, the effective look-ahead horizon grows from a single step (TD) to the full episode (Monte Carlo). The practical sweet spot around λ ≈ 0.9 balances variance and bias effectively.

Key Takeaways — Part 2

• An MDP formalises the world with four components: States, Actions, Transitions, and Rewards. The Markov property — that the future depends only on the present — is what makes the math tractable.

• The discount factor γ controls how far ahead the agent plans. Too low and it sacrifices long-term gains for immediate rewards; too high and learning becomes slow and unstable.

• The Bellman equation is the recursive backbone of all RL: value now = reward now + discounted value of the next state. It is a system of equations solved by repeated sweeping.

• Value Iteration solves Bellman exactly but requires a known model — impractical for the vast majority of real environments.

• TD Learning is model-free: it bootstraps from raw experience, correcting V(s) after every single step using the TD error δ = r + γV(s') − V(s).

• TD(0) is low-variance but biased; Monte Carlo is unbiased but high-variance. TD(λ) with eligibility traces provides a principled blend.

  
  

  Based on Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow, 3rd Ed., Chapter 18  ·  Aurélien Géron  ·  O'Reilly Media