Exploration, exploitation and Q-learning
Notes on exploration vs exploitation in reinforcement learning, multi-armed bandits, common exploration strategies (ε-greedy, softmax, UCB), and the Q-learning algorithm with its update, assumptions and a one-step program example.
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
Exploration vs exploitation decisions appear in any system that must learn from interaction: a robot deciding whether to try a new route, an online system choosing which advertisement to show, or a control agent optimizing energy use. Q-learning is a simple, widely used algorithm that learns action values for decision-making in unknown environments, letting engineers build agents that improve through experience without a model of the environment.
Key ideas
All terms are defined before first use.
- Agent: the learner/decision-maker interacting with an environment.
- Environment: everything outside the agent; it returns a new state and a reward when the agent acts.
- State (s): a complete description of the environment at a time step used for decision-making. (Finite set assumed in most exam derivations.)
- Action (a): a choice available to the agent at a state.
- Reward (r): a scalar numerical signal given by the environment after an action. Higher reward is better.
- Policy (π): a mapping from states to probabilities over actions. If π(a|s)=1 for one action, the policy is deterministic.
- Episode: a sequence of states, actions and rewards that ends in a terminal state (if episodic). Non-episodic is continuing.
- Exploration: choosing actions to gain information about the environment (possibly lower immediate reward).
- Exploitation: choosing actions that currently seem best to maximise immediate or cumulative reward.
- Multi-armed bandit: a simplified problem with one state and several actions (arms) each giving stochastic rewards. Used to study exploration strategies.
- Regret: the difference between the reward the agent could have obtained by always choosing the best action and the reward actually obtained; used to measure exploration performance.
- Value function V^π(s): expected cumulative (discounted) reward when starting in state s and following policy π.
- Action-value function Q^π(s,a): expected cumulative reward starting from state s, taking action a, then following π.
- Optimal value functions V(s), Q(s,a)**: the maximum possible values over all policies.
Bandit exploration strategies (short statements / exact forms asked in exams):
- ε-greedy: with probability ε choose a random action (explore); with probability 1−ε choose argmax action (exploit). Tune ε: small constant or decaying schedule.
- Softmax / Boltzmann: choose action a with probability proportional to exp(Q(a)/τ), where τ (temperature) controls randomness.
- Upper Confidence Bound (UCB1): choose arm i maximizing x̄_i + sqrt(2 ln t / n_i), where x̄_i is sample mean, n_i is pulls of arm i, t is total pulls. This balances mean estimate and uncertainty.
Q-learning (core theory university students must know):
- Assume a finite Markov decision process (MDP) with states S, actions A, transition probabilities P(s'|s,a), reward function R(s,a) (expected immediate reward), and discount factor γ in [0,1).
- The Bellman optimality equation for action values is: Q*(s,a) = R(s,a) + γ Σ_{s'} P(s'|s,a) max_{a'} Q*(s',a').
Derivation of the Q-learning update (exam-style step-by-step):
- Start from the Bellman optimality equation (above) which holds for Q*.
- For unknown P and R, we replace the expectation on the right by a sample obtained from one transition (s,a,r,s'). The sample backup target is r + γ max_{a'} Q(s',a'). This is an unbiased estimate of R(s,a) + γ E_{s'|s,a}[max_{a'} Q(s',a')] for the current Q; when Q = Q*, it is an unbiased sample of the Bellman optimality RHS.
- Use stochastic approximation (a sample-based version of fixed-point iteration). For current estimate Q(s,a), update toward the target with step size α ∈ (0,1]: Q(s,a) ← Q(s,a) + α [r + γ max_{a'} Q(s',a') − Q(s,a)].
- That single-step rule is the standard Q-learning update; iterating it under appropriate conditions converges to Q*.
Important assumptions for convergence (exam-style precision):
- Finite state and action spaces.
- Bounded rewards (|r_t| ≤ R_max < ∞) and a stationary MDP.
- The learning rates α_t(s,a) satisfy the Robbins–Monro conditions: Σ_t α_t(s,a) = ∞ and Σ_t α_t(s,a)^2 < ∞ for each (s,a). Often implemented by α_t = 1 / n_t where n_t is the visit count (this choice satisfies Σ α_t = ∞ and Σ α_t^2 < ∞), or α_t = 1/(1+t) on each pair.
- Each state–action pair is visited infinitely often (sufficient exploration).
- Discount factor 0 ≤ γ < 1 for continuing tasks ensures contraction; if γ = 1 special care is needed.
- Q-learning is off-policy: it learns Q* (the optimal action-value function) while the actions can be chosen by a different behaviour policy (e.g., ε-greedy).
What to draw (diagrams):
- Draw an MDP state diagram for a simple chain of three states S0 → S1 → S2 with arrows labelled by actions (left, right) and edges labelled by rewards (0 except edge to S2 labelled +1). Label start and terminal states. This helps explain transitions and the backup r + γ max Q(s',·).
- Draw a plot for UCB showing x̄_i on x-axis and confidence width sqrt(2 ln t / n_i) as an added vertical bar to show exploration bonus.
Formulas
Q*(s,a) = R(s,a) + γ ∑_{s'} P(s'|s,a) max_{a'} Q*(s',a') — Q* is optimal action-value. Symbols: Q*(s,a) (expected cumulative reward, unit: same unit as reward), R(s,a) (expected immediate reward), γ (discount factor, unitless, 0≤γ<1 for convergence), P(s'|s,a) (transition probability, unitless). Applies for MDPs.
Q(s,a) ← Q(s,a) + α [r + γ max_{a'} Q(s',a') − Q(s,a)] — Q-learning update. α is learning rate (unitless, 0<α≤1), r is scalar immediate reward (units of reward), γ discount factor.
ε-greedy: π(a|s) = {1−ε + ε/|A| if a = argmax Q(s,·); ε/|A| otherwise} — defines behaviour policy; ε unitless, |A| cardinality of action set. Assumes a unique greedy action; with ties, split the (1−ε) mass uniformly among greedy actions.
Softmax: π(a|s) = exp(Q(s,a)/τ) / ∑_{b} exp(Q(s,b)/τ) — τ (temperature) unitless, controls randomness.
UCB1 selection: choose i maximizing x̄_i + sqrt(2 ln t / n_i) — x̄_i sample mean reward for arm i, t total pulls so far, n_i pulls of i. Assume each arm has been selected at least once so n_i ≥ 1 to avoid division by zero.
Robbins–Monro conditions: Σ_t α_t = ∞ and Σ_t α_t^2 < ∞ — conditions on α_t values for stochastic approximation convergence.
Worked examples
Example 1 — Multi-armed bandit sample-average updates (numerical): Problem: Two arms A and B. Observed reward sequence when pulled: A → 1.0, then B → 2.0, then A → 0.0, then A → 2.0. Use sample-average estimate (step-size = 1 / count) and show estimates after each pull. Start with Q_A = 0, Q_B = 0. Steps:
- Pull 1: choose A, observed r=1.0. Count_A=1. Update: Q_A = Q_A + (1/1)(1.0 − 0) = 1.0.
- Pull 2: choose B, observed r=2.0. Count_B=1. Update: Q_B = 0 + 1*(2.0 − 0) = 2.0.
- Pull 3: choose A, observed r=0.0. Count_A=2. Update: Q_A = 1.0 + (1/2)(0.0 − 1.0) = 1.0 − 0.5 = 0.5.
- Pull 4: choose A, observed r=2.0. Count_A=3. Update: Q_A = 0.5 + (1/3)(2.0 − 0.5) = 0.5 + (1/3)*1.5 = 0.5 + 0.5 = 1.0. Final estimates: Q_A = 1.0, Q_B = 2.0. Bold final answer: Q_A = 1.0, Q_B = 2.0. (Show this in exams to explain sample-average and how counts affect learning rate.)
Example 2 — One-step Q-learning update (Python program): Purpose: illustrate a single deterministic Q-learning update for a transition (no randomness). This is exam-friendly because the output is exact and reproducible.
Python program (complete):
# One-step Q-learning update example
Q = { 'S1': {'left': 0.0, 'right': 0.0},
'S2': {'left': 0.0, 'right': 0.0} }
alpha = 0.5
gamma = 0.9
# transition: from S1 taking 'right' yields reward r and moves to S2
s = 'S1'
a = 'right'
r = 1.0
s_prime = 'S2'
# current estimate of best action value at s_prime
max_q_s_prime = max(Q[s_prime].values())
Q[s][a] = Q[s][a] + alpha * (r + gamma * max_q_s_prime - Q[s][a])
print("Updated Q[S1]['right'] =", Q['S1']['right'])
Sample input: none (the program runs with fixed values). Exact output (one line):
Updated Q[S1]['right'] = 0.5
Explanation: initial Q[S1]['right'] = 0, alpha = 0.5, r = 1.0, max Q at S2 = 0 → update = 0 + 0.5*(1 + 0.9*0 − 0) = 0.5.
Common mistakes
- Using constant α without stating its effect on convergence; forgetting Robbins–Monro conditions when claiming convergence.
- Incorrect UCB constant: forgetting the sqrt(2 ln t / n_i) factor or misplacing t and n_i.
- Mixing up Q(s,a) and V(s). Q includes the immediate action; V assumes following policy after choosing action.
- Forgetting to ensure every state–action pair is visited infinitely often when proving convergence.
- Writing the Bellman optimality equation without the discount factor γ or missing the max_{a'}.
For your exam
Typical question types:
- Definitions: define exploration, exploitation, policy, Q(s,a).
- Short notes: explain ε-greedy, softmax, UCB and when to use each.
- Derivation: derive the Q-learning update from the Bellman optimality equation using stochastic approximation.
- Numerical: perform a few sample-average updates for a bandit or compute one Q-learning update with numbers (as in worked examples).
- Programs: short Python snippet to show a Q update or a simple bandit simulation; provide exact output for a deterministic run.
- Diagrams: draw a simple MDP (3 states chain or 2-state) and label transitions and rewards; show the backup arrow from Q(s,a) to r + γ max_{a'} Q(s',a').
What full-marks answers include:
- Clear definitions with bolded terms and units if applicable.
- Statement of assumptions (finite MDP, γ range, learning-rate conditions, exploration requirement) when claiming convergence.
- Step-by-step derivation for the Q update, explaining replacement of expectation by sample and the stochastic approximation idea.
- If asked for an algorithm, show pseudocode for Q-learning with clear initialization, action selection (e.g., ε-greedy), update rule and termination condition.
Quick check
- What does “off-policy” mean for Q-learning?
- Write the Q-learning update rule.
- In ε-greedy with ε = 0.1 and |A| = 5, what is the probability of choosing the greedy action?
Answers: 1) Learning the optimal value Q* while behaviour policy may be different (it learns from transitions regardless of how actions were chosen). 2) Q(s,a) ← Q(s,a) + α [r + γ max_{a'} Q(s',a') − Q(s,a)]. 3) 0.9 + 0.1/5 = 0.92.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?