Reinforcement Learning — Quick Glance
RL Interaction Loop
state → action → reward → next state → . . .
• Agent chooses actions
• Environment responds with reward and next state
Core Elements
• Agent Learner / decision-maker; chooses actions using a policy
• Environment Everything outside the agent; produces rewards and next states
• State (S) Representation of the current situation; summarizes the past (Markov property)
• Action (A) What the agent can do in a state
• Reward (R) Scalar feedback signal; immediate, delayed, or misleading
• Policy (π) Mapping from states to actions (or action probabilities)
Return and Discounting
Return (what we maximize):
Gt = Rt+1 + γRt+2 + γ 2 Rt+3 + . . .
• Total future reward from time t onward
Discount factor (γ):
• γ ∈ [0, 1]
• γ ≈ 0 → short-term focus
• γ ≈ 1 → long-term planning
Policy
The policy is what we are ultimately learning.
π(a | s) = Pr(At = a | St = s)
• Maps states to action probabilities
• Can be deterministic or stochastic
Value Functions
State-value function:
V π (s) = E[Gt | St = s]
“How good is it to be in this state?”
Action-value function:
Qπ (s, a) = E[Gt | St = s, At = a]
“How good is it to take this action here?”
1
How Everything Connects (The Loop)
• Policy → chooses actions
• Actions → affect environment
• Environment → gives rewards and states
• Rewards → define return
• Return → defines value
• Value → improves policy
This is a loop, not a pipeline.
Method Classification
see p(s’ | s, a)? → Dynamic Programming
else see G_t? → Monte Carlo
else see V(s’)? → Temporal Difference (bootstrapping)
if max_a Q(s’,a)→ Q-learning
see log ? → Policy Gradients
Episodic vs Continuing Tasks
• Episodic tasks: have terminal states
• Continuing tasks: no terminal state
Monte Carlo requires episodic tasks; TD methods do not.
Sanity Check
• Who chooses actions? → Agent
• Who gives rewards? → Environment
• What summarizes the past? → State
• What do we maximize? → Return
• What controls long vs. short-term? → γ
• What are we learning? → Policy
RL Algorithms at a Glance
• Bandits: No states, only actions; balance exploration vs. exploitation.
• Dynamic Programming (DP): Model known; compute values using Bellman equations; bootstraps.
• Monte Carlo (MC): Model-free; learn from complete episodes using full return Gt .
• Temporal Difference (TD): Model-free; learn step-by-step using reward + estimated next value.
• SARSA: TD control; learns Q(s, a); on-policy.
• Q-learning: TD control; learns optimal Q(s, a); off-policy using max Q.
• Policy Gradients (REINFORCE): Learn policy directly via gradient ascent; high variance.
Reinforcement Learning — Methods vs Variables
Method Learns p(s′ |s, a) Gt V (s) Q(s, a) maxa Q Bootstrap ∇ log π Fingerprint
Dynamic Programming V, π ✓ – ✓ O ✓ ✓ – Model-based, Bellman equations
Monte Carlo V or Q – ✓ ✓ O – – – Episodic, no bootstrapping
TD (TD(0), SARSA) V or Q – – ✓ ✓ – ✓ – Online, bootstraps
Q-learning Q – – – ✓ ✓ ✓ – Control, off-policy
Policy Gradients π – ✓ O – – O ✓ Learn policy directly
Legend: ✓= explicitly used O = used implicitly – = not used
2
Bootstrapping
Bootstrapping: updating value estimates using other learned estimates (e.g. V (s′ ), Q(s′ , a′ )).
Exploration vs Exploitation
• Exploration: trying actions to gain information
• Exploitation: choosing actions with highest estimated value
Bias–Variance Trade-off in Reinforcement Learning
Method Bias Variance
Dynamic Programming (DP) High Low
Monte Carlo (MC) Low High
Temporal Difference (TD) Medium Medium
Core Update Rules (Must-Know)
V (s) ← V (s) + α R + γV (s′ ) − V (s)
TD(0):
Q(s, a) ← Q(s, a) + α R + γQ(s′ , a′ ) − Q(s, a)
SARSA (on-policy):
Q(s′ , a′ ) − Q(s, a)
Q-learning (off-policy): Q(s, a) ← Q(s, a) + α R + γ max
′ a
One-Step Update Example
Given: α = 0.1, γ = 0.9, R = 1, V (s) = 5, V (s′ ) = 6
V (s) ← 5 + 0.1(1 + 0.9 · 6 − 5)
On- vs Off-Policy
• SARSA → on-policy
• Q-learning → off-policy
Behavior vs Target Policy
• Behavior policy: generates actions (exploration)
• Target policy: policy being learned / optimized
SARSA: behavior policy = target policy
Q-learning: behavior policy ̸= target policy
Value-based vs Policy-based
• Value-based: DP, MC, TD, Q-learning
• Policy-based: Policy Gradients