Reinforcement learning basics
Basic reinforcement learning: Markov decision processes, policies, returns, value and action-value functions, Bellman equations, solution methods (value/policy iteration, Q-learning), and exploration–exploitation.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Reinforcement learning (RL) is used when an engineer must make sequential decisions under uncertainty to maximise long-term performance: examples include robot control, resource allocation, and game-playing agents. RL provides algorithms to learn good decision rules (policies) from interaction with an environment, without requiring labelled input–output pairs as in supervised learning.
Key ideas
(Definitions are stated before use.)
Markov decision process (MDP): a tuple (S, A, P, R, γ) where
- S is a finite set of states; A is a finite set of actions;
- P(s'|s,a) is the transition probability of next state s' given current state s and action a;
- R(s,a,s') is the reward received on transition (s,a)→s' (can be deterministic or random);
- γ ∈ [0,1] is the discount factor (explained below). Assumption: the Markov property holds — the next-state and reward distributions depend only on the current state and action, not on earlier history.
Policy (π): a rule for choosing actions. For stochastic policies, π(a|s) is the probability of taking action a in state s. For deterministic policies, π(s) maps s to a single action.
Return (G_t): the total discounted future reward from time t: G_t = R_{t+1} + γ R_{t+2} + γ^2 R_{t+3} + … . Assumption: rewards are bounded so the infinite sum converges when γ < 1. In episodic tasks that terminate with probability 1 and have finite expected episode length, γ may be set to 1 and the (finite) sum still defines the return.
State-value function (v_π(s)): expected return starting from state s and following policy π: v_π(s) = E_π[G_t | S_t = s]. This measures long-term desirability of a state under π.
Action-value function (q_π(s,a)): expected return starting from state s, taking action a, then following π: q_π(s,a) = E_π[G_t | S_t = s, A_t = a].
Bellman expectation equation (for v_π): expresses v_π(s) recursively in terms of successor states. Exact statement: v_π(s) = Σ_a π(a|s) Σ_{s',r} p(s',r|s,a) [ r + γ v_π(s') ]. Derivation: use definition of return and linearity of expectation (see worked example).
Optimal value functions (v_*, q_*) and optimal policy (π_*): v_*(s) = max_π v_π(s); q_*(s,a) = max_π q_π(s,a). An optimal policy π_* attains these maxima for all s. In finite discounted MDPs, there exists at least one deterministic stationary optimal policy. The Bellman optimality equation for v_*: v_*(s) = max_a Σ_{s',r} p(s',r|s,a)[ r + γ v_*(s') ]. This is nonlinear because of the max.
Dynamic programming solution methods (require known model P and R):
- Policy evaluation: compute v_π for a fixed π (solve Bellman linear system or iterate);
- Policy improvement: make policy greedy w.r.t. current value: π'(s) = argmax_a Σ_{s',r} p(s',r|s,a)[ r + γ v_π(s') ];
- Policy iteration: alternate evaluation and improvement until convergence to optimal π;
- Value iteration: repeatedly apply Bellman optimality backup v_{k+1}(s) = max_a Σ_{s',r} p(s',r|s,a)[ r + γ v_k(s') ] until convergence. Assumption: finite state-action spaces and γ < 1 (or proper termination) ensure contraction and convergence.
Model-free learning (no P, R known): agent learns from experience samples. Main ideas:
- Temporal-difference (TD) learning: update value estimates using one-step samples; TD(0) update for v(S_t): v(S_t) ← v(S_t) + α [ R_{t+1} + γ v(S_{t+1}) - v(S_t) ];
- Q-learning (off-policy control): update Q(S_t, A_t) toward target R_{t+1} + γ max_a Q(S_{t+1}, a): Q ← Q + α [R + γ max Q - Q]. Q-learning converges to q_* under assumptions: (i) learning rate α decays properly, (ii) every state–action pair visited infinitely often, (iii) finite MDP, (iv) bounded rewards.
Exploration versus exploitation: trade-off between choosing best-known action (exploit) and trying other actions to discover possibly better options (explore). Common practical strategy: ε-greedy — with probability ε choose a random action, otherwise choose greedy action.
Contraction and convergence: Bellman optimality operator is a γ-contraction in max-norm, which guarantees a unique fixed point v_* and convergence of value iteration when γ ∈ [0,1).
Diagram to draw for exam answers: draw a small MDP with 3 circles labeled s1, s2, s3. Draw arrows for actions (label actions a1, a2). On each arrow write transition probability p and immediate reward r. Also indicate policy π at each state (e.g., arrows thickness or probabilities). Label γ on the side and state-value v(s) near each state.
Formulas
G_t = R_{t+1} + γ R_{t+2} + γ^2 R_{t+3} + … — G_t is return (units: same as rewards; dimension depends on the application); applies to discounted infinite-horizon problems with γ∈[0,1).
v_π(s) = E_π[G_t | S_t = s] — v_π(s) is expected return from s under policy π (unit: same as rewards); applies for any policy π.
q_π(s,a) = E_π[G_t | S_t = s, A_t = a] — action-value function (unit: same as rewards). Relationship: v_π(s) = Σ_a π(a|s) q_π(s,a).
v_π(s) = Σ_a π(a|s) Σ_{s',r} p(s',r|s,a) [ r + γ v_π(s') ] — Bellman expectation equation; p(s',r|s,a) is joint prob. of next state and reward; applies for any policy π in an MDP.
v_*(s) = max_a Σ_{s',r} p(s',r|s,a) [ r + γ v_*(s') ] — Bellman optimality equation; applies for optimal value function v_*. Equivalent for action-values: q_*(s,a) = Σ_{s',r} p(s',r|s,a) [ r + γ max_{a'} q_*(s',a') ].
TD(0): v(S_t) ← v(S_t) + α [ R_{t+1} + γ v(S_{t+1}) - v(S_t) ] — α ∈ (0,1] is step-size; applies for incremental model-free policy evaluation.
Q-learning: Q(S_t,A_t) ← Q(S_t,A_t) + α [ R_{t+1} + γ max_a Q(S_{t+1},a) - Q(S_t,A_t) ] — off-policy control update; applies under assumptions for convergence.
Value iteration backup: v_{k+1}(s) = max_a Σ_{s',r} p(s',r|s,a) [ r + γ v_k(s') ] — iterative algorithm to compute v_*; applies when model known.
Policy improvement (greedy): π'(s) = argmax_a Σ_{s',r} p(s',r|s,a) [ r + γ v_π(s') ] — constructs improved policy from value v_π.
Worked examples
Example 1 — small deterministic chain, policy evaluation (numerical): Problem: States S = {s1, s2, s3}. Actions are deterministic: from s1 action moves to s2 with reward 0; from s2 action moves to s3 with reward 1; s3 is terminal with zero reward thereafter. Policy π always chooses the available action. Let γ = 0.9. Compute v_π(s) for each state. Solution steps:
- v_π(s3) = 0 because s3 is terminal.
- v_π(s2) = E[R_{t+1} + γ v_π(s3)] = 1 + 0.9·0 = 1. Unit: reward units.
- v_π(s1) = E[R_{t+1} + γ v_π(s2)] = 0 + 0.9·1 = 0.9. Answer: v_π(s1) = 0.9, v_π(s2) = 1, v_π(s3) = 0. (All arithmetic exact; final answers in same reward units.)
Example 2 — one Q-learning update (numerical): Problem: Current Q(S,A) = 2.0. Observed transition yields reward R = 3.0 and next state's maximum Q is max_a Q(S',a) = 4.0. Use α = 0.1 and γ = 0.9. Compute updated Q. Solution:
- TD target = R + γ max Q = 3.0 + 0.9·4.0 = 3.0 + 3.6 = 6.6.
- TD error = target - Q = 6.6 - 2.0 = 4.6.
- Q_new = Q + α·TD_error = 2.0 + 0.1·4.6 = 2.0 + 0.46 = 2.46. Answer: Q_new = 2.46.
Example 3 — model exam question: derive the Bellman expectation equation for v_π(s). Model answer (steps):
- Start from definition: v_π(s) = E_π[G_t | S_t = s] = E_π[R_{t+1} + γ G_{t+1} | S_t = s].
- Use linearity of expectation: v_π(s) = E_π[R_{t+1} | S_t = s] + γ E_π[G_{t+1} | S_t = s].
- Condition on action A_t and next state S_{t+1}: E_π[R_{t+1} | S_t = s] = Σ_a π(a|s) Σ_{s',r} p(s',r|s,a) r.
- Similarly E_π[G_{t+1} | S_t = s] = Σ_a π(a|s) Σ_{s',r} p(s',r|s,a) v_π(s').
- Combine to get v_π(s) = Σ_a π(a|s) Σ_{s',r} p(s',r|s,a) [ r + γ v_π(s') ]. This completes the derivation.
Common mistakes
- Mixing up policy π and value v: policy maps states to actions; value maps states to expected returns under a policy.
- In Q-learning, using the wrong sign or placing max inside wrong term. Write the update carefully.
- Assuming model-based DP methods apply without a known model — they require P and R.
- Using greedy policy for exploration (no exploration) when learning; forgetting to ensure all state–action pairs are visited.
- In derivations, failing to expand expectations by conditioning on actions and next states.
For your exam
Question types you can expect: definitions (MDP, policy, return), short notes (Bellman equations, TD learning), derivations (derive Bellman expectation equation), numericals (compute v_π in a small MDP or one-step Q update), algorithm explanation (value iteration vs policy iteration; Q-learning pseudocode), and diagram questions (draw an MDP and label transitions).
What a full-marks answer includes:
- Precise definitions with notation (e.g., MDP = (S,A,P,R,γ)).
- Clear assumptions (Markov property; γ in [0,1); bounded rewards; finite state-action spaces where relevant).
- Step-by-step derivations using expectations and conditioning where required.
- For numericals: show each formula used, substitute numbers, carry units (if any), and give final answer clearly.
- For algorithms: give pseudocode or correct update equations and state convergence conditions.
Quick check
- Define an MDP in one line.
- Write the Bellman optimality equation for v_*.
- In Q-learning, what is the role of α and ε? Answers: 1) MDP = (S,A,P,R,γ), where P gives transition probabilities and R rewards; 2) v_*(s) = max_a Σ_{s',r} p(s',r|s,a)[ r + γ v_*(s') ]; 3) α is the learning-rate (step-size) controlling update magnitude; ε is exploration probability in ε-greedy policy controlling random action selection.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?