Q-learning algorithm: Question bank — AI-ML deep dive

Before we start, some words must be crystal clear, because most traps hinge on confusing them.

Now the three words that most traps hinge on.

Definition Three words you must never blur

Behaviour policy — the rule the agent actually uses to pick actions while collecting data (e.g. $ε$ -greedy).
Target policy — the policy the algorithm is trying to learn about. In Q-learning this is the greedy policy (always take the action with the largest Q-value).
Off-policy — a precise technical property, not merely "two different policies." It means the algorithm can use data generated by the behaviour policy to correctly estimate the value of the different target policy. Q-learning achieves this because its update target, $r + γ max_{a^{'}} Q (s^{'}, a^{'})$ , refers only to the greedy action's value; it never needs the probability of the action the behaviour policy actually chose, so exploratory data still yields a valid estimate of the greedy policy's Q-values.

The picture below shows this split at a glance — one arrow is what the agent does, the other is what it learns about.

Definition The learning-rate schedule

$α_{t}$ and its two convergence conditions $α_{t}$ is simply the learning rate at time step $t$ — we allow it to change as learning proceeds. A schedule is the rule that sets it, e.g. $α_{t} = 1/ t$ (start big, shrink each step) or $α_{t} = 0.1$ constant. For Q-learning to converge to the exact $Q^{*}$ , the schedule must satisfy both:

$\sum_{t} α_{t} = \infty$ — the steps must add up to infinity so learning never dries out and can still move Q by any needed amount, no matter how late.
$\sum_{t} α_{t}^{2} < \infty$ — the squared steps must add up to something finite so the random sample noise gets averaged away and Q stops jittering. $α_{t} = 1/ t$ threads the needle (it satisfies both); a constant $α_{t} = 0.1$ fails the second (never settles); $α_{t} = 1/ t^{2}$ fails the first (dies too soon).

The figure shows all three schedules. The horizontal axis is the time step $t$ ; the vertical axis is the learning rate $α_{t}$ . The lavender curve $1/ t$ decays gently (good), the dashed coral line stays flat at $0.1$ (keeps jittering), and the dotted mint curve $1/ t^{2}$ plunges to near-zero almost immediately (stops learning too soon).

Definition The Bellman operator

$T$ and the $\infty$ -norm

The ==Bellman optimality operator $T$ == is a machine that eats a whole Q-table and outputs an improved one: $[T Q] (s, a) = E_{s^{'}, r \sim P (\cdot ∣ s, a)} [r + γ max_{a^{'}} Q (s^{'}, a^{'})]$ . The expectation is taken over the random next state $s^{'}$ and reward $r$ , drawn from the environment's transition/reward model $P (\cdot ∣ s, a)$ . Applying $T$ once is "look one step ahead, averaging over where the environment might send you."
The ==infinity norm $∥ Q ∥_{\infty}$ == means "the single largest absolute value in the table." So $∥ Q_{1} - Q_{2} ∥_{\infty}$ is the worst-case gap between two tables over all $(s, a)$ .
" $T$ is a contraction" means: after applying $T$ to both tables, that worst-case gap shrinks — $∥ T Q_{1} - T Q_{2} ∥_{\infty} \leq γ ∥ Q_{1} - Q_{2} ∥_{\infty}$ . The picture makes the shrinking-gap idea concrete.

The figure below drives this home. The horizontal axis counts how many times we have applied $T$ ; the vertical axis (bar heights) is the worst-case gap $∥ Q_{1} - Q_{2} ∥_{\infty}$ between two Q-tables. Each bar is $γ = 0.7$ times the previous one, so the gap shrinks geometrically toward zero — both tables are pulled to the same unique fixed point $Q^{*}$ , no matter where they started.

The single fact that generates most Q-learning traps: the update uses $max_{a^{'}} Q (s^{'}, a^{'})$ , not the value of the action you will actually take next. That $max$ is what makes the target policy greedy, and it is what separates Q-learning from SARSA.

True or false — justify

Q-learning cannot be used unless you know the transition probabilities

P (s^{'} ∣ s, a)

False. Q-learning is model-free — it only needs sampled transitions

(s, a, r, s^{'})

from experience; the

max

term replaces the expectation without ever writing down

P

Q-learning learns the optimal Q-values even while the agent behaves badly (explores randomly).

True. The update bootstraps off

max_{a^{'}} Q (s^{'}, a^{'})

(greedy target), so the estimate it converges to is

Q^{*}

regardless of the exploratory behaviour policy — that is exactly what "off-policy" means.

If we set the exploration rate

ε = 0

from the very first episode, Q-learning still converges to

Q^{*}

False. With pure greedy behaviour many state-action pairs may never be visited, violating convergence condition 1 (every

(s, a)

visited infinitely often); the agent can lock into a suboptimal loop.

A constant learning rate

α = 0.1

guarantees convergence to the exact

Q^{*}

False. Exact convergence needs

\sum_{t} α_{t} = \infty

and

\sum_{t} α_{t}^{2} < \infty

; a constant

α_{t}

makes

\sum_{t} α_{t}^{2} = \infty

, so Q keeps jittering. It gives a "good enough" estimate, useful when the environment is non-stationary.

Q-learning and SARSA produce identical updates whenever the agent happens to act greedily on that step.

True. If the next action actually taken is the greedy one, then SARSA's

Q (s^{'}, a^{'})

equals Q-learning's

max_{a^{'}} Q (s^{'}, a^{'})

, so the two update rules coincide for that step — they only differ when exploration picks a non-greedy

a^{'}

The discount factor

γ

can safely be set to

1

in any Q-learning problem.

False in general. In continuing tasks

γ = 1

lets the summed return diverge to infinity, and it also removes the contraction guarantee; it is only safe in episodic tasks where every path terminates so the sum stays finite.

Because the update uses only

r

and one next state

s^{'}

, Q-learning ignores long-term consequences.

False. The bootstrap term

γ max_{a^{'}} Q (s^{'}, a^{'})

already carries the whole future value of

s^{'}

; long-term reward propagates backward one step per visit, so distant rewards eventually reach early states.

The

max

in the target guarantees Q-values are always accurate estimates of true value.

False. Taking the max over noisy estimates systematically picks overestimated ones — this is maximization bias, the very reason Double Q-learning exists.

Spot the error

"Q-learning is on-policy because it updates the Q-value of the action the agent just took."

Error: the label. Updating

Q (s, a)

for the taken action does not make it on-policy; the target uses

max_{a^{'}} Q (s^{'}, a^{'})

(greedy), not the value of the next taken action, so it is off-policy.

"Set

Q (terminal, \cdot) = 5

so the agent knows the goal is good."

Error. Terminal states must have

Q = 0

— there is no future after termination. The goal's desirability enters through the reward

r

on the transition into the terminal state, not through a nonzero terminal Q.

"To fix overestimation, just lower the learning rate

α

Error. Maximization bias comes from the

max

over noisy estimates, not from step size; shrinking

α

slows learning but the bias remains. The fix is decoupling selection and evaluation, i.e. Double Q-learning.

"With

ε

-greedy the agent explores

30%

of the time, so

30%

of updates are wrong."

Error. The one-step target

r + γ max_{a^{'}} Q (s^{'}, a^{'})

depends only on the observed reward and next state and on the greedy value at

s^{'}

— none of which cares which action the behaviour policy chose to reach

s^{'}

. So an exploratory action still delivers a valid, unbiased sample of the greedy target; exploration changes which

(s, a)

you update, never the correctness of the update.

"Since the Bellman operator is a contraction, Q-learning converges after one sweep."

Error. Contraction guarantees convergence in the limit of infinitely many applications/visits; each application of

T

only shrinks the worst-case gap by a factor

γ

, so it takes many iterations, not one.

γ

close to

1

means the agent is greedy;

γ

close to

0

means it explores."

Error: confusing two knobs.

γ

controls how much future reward matters (far-sighted vs myopic); exploration vs exploitation is governed by

ε

(the behaviour policy), a completely separate parameter.

"Q-learning needs a neural network to handle large state spaces — that's what makes it Q-learning."

Error. Tabular Q-learning stores an explicit table and is the base algorithm; using a network is Function Approximation, which upgrades it to Deep Q-Networks (DQN) — a variant, not the definition.

Why questions

Why does the update use

max_{a^{'}} Q (s^{'}, a^{'})

rather than the value of the action actually taken next?

Because the target policy we want to learn is the greedy one; taking the max assumes optimal future behaviour, which is exactly what makes

Q

converge to the optimal

Q^{*}

instead of some exploratory policy's value.

Why must the learning rate satisfy

\sum_{t} α_{t}^{2} < \infty

So that the noise from individual random samples averages out and dies down over time; if the squared steps summed to infinity, the estimate would never settle and would keep oscillating around

Q^{*}

Why does

γ < 1

make the Bellman optimality operator

T

a contraction?

Applying

T

multiplies the worst-case gap (the

\infty

-norm distance) between two Q-tables by

γ

; since

γ < 1

shrinks that gap every time, repeated application drives any two starting estimates to the same unique fixed point

Q^{*}

Why can Q-learning start with arbitrary initial Q-values and still converge?

The contraction property means all differences from

Q^{*}

shrink geometrically regardless of the starting point, so the initial table only affects speed, not the final answer (given enough visits).

Why does Double Q-learning use one estimator to select the action and a different one to evaluate it?

Because the estimator that picks the max is biased upward by its own noise; a statistically independent estimator evaluating that choice does not share the same noise, so the systematic overestimation cancels.

Why does a large reward at the goal take many episodes to influence the starting state?

Value propagates only one step backward per visit (through the bootstrap term), so the goal's value must be relayed state-by-state along the path across repeated episodes before it reaches the start.

Why is exploration a requirement for convergence and not just a nice-to-have?

Concretely, imagine a two-door room where door A gives

+ 1

and untried door B secretly gives

+ 100

; a greedy-only agent that stumbles on A first will keep choosing A forever, never sampling B, so its Q-value for B stays at its wrong initial guess and the "optimal" policy it learns is actually suboptimal. Exploration guarantees every

(s, a)

is sampled infinitely often, which is the only way the true best action can ever reveal its higher value.

Edge cases

What is the Q-learning target when

s^{'}

is a terminal state?

Just the reward:

r + γ \cdot 0 = r

, because

Q (terminal, \cdot) = 0

— there is no future value to bootstrap from.

What happens to the update if

α = 0

Nothing —

Q (s, a)

never changes, so no learning occurs; the agent is frozen at its initial table forever.

What happens if

α = 1

in a deterministic environment?

Q (s, a)

is fully replaced by the target each step; in a deterministic world this is fine and often fast, but in a stochastic one it makes updates high-variance because a single lucky/unlucky sample overwrites the estimate.

Why is

γ = 1

dangerous specifically in a continuing (non-episodic) task?

With no terminal state the return

r_{0} + γ r_{1} + γ^{2} r_{2} + \dots

has infinitely many terms; if

γ = 1

they do not shrink, so the sum can diverge to infinity and no finite

Q^{*}

exists —

γ < 1

keeps the geometric sum finite.

In a purely deterministic environment, does maximization bias still hurt?

Much less — the overestimation of

max

comes from noise in the estimates; with deterministic rewards and transitions the sampled targets are exact once visited, so the bias largely vanishes and plain Q-learning is usually fine.

If a state-action pair is visited only once and never again, what is its final Q-value?

Whatever it became after that single update — it is stuck; without repeated visits it cannot approach

Q^{*}

, which is why "infinitely often" appears in the convergence conditions.

What does Q-learning do in a non-stationary environment (rewards change over time)?

A decaying

α_{t}

would freeze the old (now wrong) values; a small constant

α

is preferred so the agent keeps re-adapting to the changed rewards — trading exact convergence for responsiveness.

If two actions in a state have exactly equal Q-values, which does the greedy target pick?

The

max

value is identical either way, so the target is unaffected; only the tie-breaking rule of the behaviour policy decides which action is actually executed, and that choice does not change what is learned.

Recall Self-test: state the one fact that generates most Q-learning traps

The update bootstraps off $max_{a^{'}} Q (s^{'}, a^{'})$ (the greedy/target policy value), not the value of the next action actually taken — this is what makes Q-learning off-policy and what distinguishes it from SARSA.