Consistency Of Plug-In Q-Learning

Why Q-Function Consistency Matters for Decisions

Q-learning estimates conditional mean outcomes and chooses the action with the largest estimated value at each history. A good estimate of the values is useful, but the decision depends on their ordering: an estimate can have some error and still select the correct action, or a small error can reverse the choice when two actions are nearly tied. This tutorial gives a precise condition under which plug-in decisions are consistent: the optimal action must be uniquely separated from its alternatives, and the estimated Q-functions must converge sufficiently accurately.

The result concerns the action selected at a history, not the quality of every numerical Q estimate. For a finite-horizon regime, apply the argument at each stage to the Q-function obtained by backward recursion. The key requirement is that the estimation error for the action-specific conditional means, including any error propagated through estimated future values, vanishes at the histories where decisions are to be made.

Setup and Separation

At stage $t$, let $H_t$ denote the observed history and let $\mathcal A_t$ be the available finite action set. Write $Q_t(h,a)$ for the conditional mean outcome from taking action $a$ at history $h$ and then acting optimally at later stages. The corresponding optimal value is $V_t(h)=\max_{a\in\mathcal A_t}Q_t(h,a)$. A deterministic tie rule can be used to define an estimated action even when estimated Q-values tie.

Definition: Suppose $\mathcal A_t$ contains at least two actions. The oracle action $a_t^*(h)$ is the unique maximizer of $Q_t(h,a)$ over $a\in\mathcal A_t$. Its separation gap is $$ \Delta_t(h)=Q_t(h,a_t^*(h))-\max_{a\in\mathcal A_t,\ a\ne a_t^*(h)}Q_t(h,a). $$ The action is uniquely separated at $h$ when $\Delta_t(h)>0$. The plug-in action is $\hat a_t(h)=\arg\max_{a\in\mathcal A_t}\hat Q_t(h,a)$, with a fixed tie rule if needed.

The requirement of at least two actions matters for this definition: if there is only one available action, the maximum over competing actions is over an empty set. In that case the decision is trivially consistent, since the estimated and oracle decisions must both select the sole available action.

Worked Example: A Fixed History With a Visible Margin

At a particular history, suppose there are three actions with true values $Q(a_1)=5.2$, $Q(a_2)=4.6$, and $Q(a_3)=3.9$. The unique best action is $a_1$, and its gap is $5.2-4.6=0.6$.

Suppose the estimates are $\hat Q(a_1)=5.3$, $\hat Q(a_2)=4.4$, and $\hat Q(a_3)=4.0$. The largest absolute estimation error is $0.2$, and the plug-in action remains $a_1$. More generally, if every action's error is at most $0.2$, then the estimated value of $a_1$ is at least $5.0$, while the estimated value of $a_2$ is at most $4.8$, and that of $a_3$ is at most $4.1$. Thus $a_1$ still wins.

The strict half-gap threshold is sufficient: an error bound below $0.6/2=0.3$ guarantees the decision. It is not necessary for a particular set of estimates; errors larger than $0.3$ might still preserve the ordering. The threshold is a simple uniform guarantee.

The Basic Argmax Result

Theorem: Let $\mathcal A$ be finite with at least two actions. At a fixed history $h$, suppose $Q(h,\cdot)$ has a unique maximizer $a^*(h)$ and gap $\Delta(h)>0$. If $$ \max_{a\in\mathcal A}|\hat Q(h,a)-Q(h,a)|<\frac{\Delta(h)}{2}, $$ then $\arg\max_{a\in\mathcal A}\hat Q(h,a)=a^*(h)$.

Proof. Put $e=\max_a|\hat Q(h,a)-Q(h,a)|$. For every competing action $a\ne a^*(h)$, the definition of the gap gives $Q(h,a^*)-Q(h,a)\ge\Delta(h)$. Therefore, $$ \hat Q(h,a^*)-\hat Q(h,a) \ge Q(h,a^*)-Q(h,a)-|\hat Q(h,a^*)-Q(h,a^*)|-|\hat Q(h,a)-Q(h,a)| \ge \Delta(h)-2e>0. $$ So the estimated value of $a^*$ is strictly larger than that of every competitor, and the estimated argmax equals $a^*$. $\square$

For a fixed history with a fixed positive gap, if $\max_a|\hat Q(h,a)-Q(h,a)|\xrightarrow{p}0$, the probability that the estimated action is wrong tends to zero. Indeed, the theorem bounds that probability by $P\{\max_a|\hat Q(h,a)-Q(h,a)|\ge\Delta(h)/2\}$, which tends to zero by convergence in probability.

Worked Example: Consistency With a Small Margin in the Population

Let a target history $H$ be uniformly distributed on $(0,1)$, and consider two actions with $Q(H,a_1)=0$ and $Q(H,a_0)=-H$. The oracle action is $a_1$ at every history, and the gap is $\Delta(H)=H>0$ with probability one. Suppose an estimator satisfies, for every history in this example, $\max_a|\hat Q(H,a)-Q(H,a)|\le n^{-1/2}$.

The argmax theorem guarantees a correct choice whenever $H>2n^{-1/2}$. Thus the probability of a possible error is bounded by $$ P\{H\le 2n^{-1/2}\}= \begin{cases} 2n^{-1/2},&n>4,\\ 1,&n\le4. \end{cases} $$ For $n>4$, this follows because a uniform variable on $(0,1)$ has probability equal to the interval length, and $2n^{-1/2}<1$. The bound tends to zero. There is no uniform positive lower bound on the gap across histories, yet the decision is still consistent for a randomly drawn history.

Consistency at Random Histories

In applications, the decision is evaluated at histories drawn from a target population. Let $H_t$ have a distribution that does not change with sample size, and define the maximum error $E_n(H_t)=\max_{a\in\mathcal A_t}|\hat Q_t(H_t,a)-Q_t(H_t,a)|$. The following result allows the gap to vary across histories.

Theorem: Suppose $\mathcal A_t$ is finite with at least two actions, the oracle maximizer is unique with probability one, and $E_n(H_t)\xrightarrow{p}0$. Then $P\{\hat a_t(H_t)\ne a_t^*(H_t)\}\to0$.

Proof. For any $\epsilon>0$, if $\Delta_t(H_t)>2\epsilon$ and $E_n(H_t)\le\epsilon$, the fixed-history theorem implies that the estimated action is correct. Consequently, $$ P\{\hat a_t(H_t)\ne a_t^*(H_t)\} \le P\{\Delta_t(H_t)\le2\epsilon\}+P\{E_n(H_t)>\epsilon\}. $$ For fixed $\epsilon$, the second term tends to zero by convergence in probability. Hence the limit superior of the error probability is at most $P\{\Delta_t(H_t)\le2\epsilon\}$. As $\epsilon$ decreases to zero, these events decrease to $\{\Delta_t(H_t)=0\}$, which has probability zero by unique optimality almost surely. Continuity of probability for decreasing events then gives the claimed result. $\square$

This proof does not require a single positive gap that works at every history. It does require that histories with an exact tie have probability zero. Pointwise convergence at each fixed $h$, by itself, is not enough to conclude convergence for random histories: errors could remain large on a region whose location changes with sample size. The theorem instead assumes convergence in probability at the target random history, which rules out that failure.

How Recursive Q-Estimation Supplies the Required Accuracy

For a finite horizon with terminal stage $T$, the recursion has the form $$ Q_t(h,a)=E\!\left[R_t+V_{t+1}(H_{t+1})\mid H_t=h,A_t=a\right],\qquad V_t(h)=\max_{a\in\mathcal A_t}Q_t(h,a), $$ with $V_{T+1}=0$. Here $R_t$ is the stage reward. Plug-in Q-learning replaces the future value by an estimated value when constructing the pseudo-outcome $\hat Y_t=R_t+\hat V_{t+1}(H_{t+1})$, and fits action-specific conditional means to that target.

A useful sufficient condition makes the two sources of error explicit. For each action, let $\hat m_{t,a}(h)$ be the fitted conditional mean of $\hat Y_t$, and suppose the fitted mean is consistent for its own target: $\max_a|\hat m_{t,a}(H_t)-E[\hat Y_t\mid H_t,A_t=a]|\xrightarrow{p}0$. Also require the propagated target error to vanish: $\max_a E[|\hat V_{t+1}(H_{t+1})-V_{t+1}(H_{t+1})|\mid H_t,A_t=a]\xrightarrow{p}0$. These statements are understood at target histories and actions with well-defined conditional means and adequate data support. The triangle inequality yields $$ \max_a|\hat m_{t,a}(H_t)-Q_t(H_t,a)| \le \max_a|\hat m_{t,a}(H_t)-E[\hat Y_t\mid H_t,A_t=a]| +\max_a E[|\hat V_{t+1}(H_{t+1})-V_{t+1}(H_{t+1})|\mid H_t,A_t=a]. $$ Thus both terms tending to zero imply Q-function consistency at stage $t$. At the terminal stage the future-value error is zero. Backward through the stages, consistent conditional-mean fits and control of the generated-target error give consistent Q-functions; the argmax theorem then gives consistent actions wherever the oracle optimum is uniquely separated. Bounded rewards and values, or suitable integrability and uniform-integrability conditions, are useful for controlling the conditional expectations involved. Conditional-mean consistency alone does not justify ignoring the error in an estimated pseudo-outcome.

Worked Example: Propagating a Terminal-Stage Error

At stage 2, suppose the true Q-values are $Q_2(x=0,a_0)=2$, $Q_2(x=0,a_1)=3$, $Q_2(x=1,a_0)=4$, and $Q_2(x=1,a_1)=1$. Therefore $V_2(0)=3$ and $V_2(1)=4$. At stage 1, action $a_0$ gives reward 1 and leads to $x=0$ with probability $0.75$, while action $a_1$ gives reward 0 and leads to $x=0$ with probability $0.2$. The other transitions lead to $x=1$.

The stage-1 values are $$ Q_1(a_0)=1+0.75(3)+0.25(4)=4.25,\qquad Q_1(a_1)=0.2(3)+0.8(4)=3.8. $$ So $a_0$ is optimal, with gap $4.25-3.8=0.45$.

Suppose each stage-2 Q estimate is within $0.05$ of its truth. Since the maximum operation changes by at most the largest input error, each estimated stage-2 value is within $0.05$ of its truth. Suppose also that each stage-1 fitted conditional mean is within $0.08$ of the conditional mean for its estimated pseudo-outcome. Its total stage-1 Q error is then at most $0.08+0.05=0.13$. The estimated difference between $a_0$ and $a_1$ is at least $0.45-2(0.13)=0.19>0$, so the estimated action remains $a_0$. This calculation shows why future-value error must be included, rather than treating the stage-1 regression error as the only source of error.

What to Check, and What the Result Does Not Say

The result is an asymptotic guarantee, not a promise of a correct action in every finite sample. It also presumes that relevant action-specific conditional means can be learned. If some actions are rarely observed at histories where they matter, their fitted Q-values may be unstable; consistency claims need sufficient support or other valid identification and estimation conditions. In practice, examine action-specific sample sizes, the stability of fitted values across reasonable specifications or resamples, and whether small estimated gaps are concentrated in sparse regions. A small estimated gap is a warning sign, although it is not proof that the true gap is small.

Plug-in Q-learning estimates conditional values and then maximizes them. A direct policy-learning approach instead targets the decision rule itself, while a g-formula analysis can evaluate a specified regime by recursively averaging outcomes. These approaches target related questions but use different estimation steps; the argmax proof here applies specifically when the estimated action is obtained by maximizing estimated Q-functions. Consistency of the fitted means does not by itself establish consistency if their errors fail to converge at the decision histories, if generated pseudo-outcomes remain inaccurate, or if the oracle has ties with positive probability. The analysis of ties and the comparison between decision consistency and value consistency require separate considerations.

Common mistake: “Every action-specific Q estimate converges, so the estimated action must be correct.” Convergence without a rate or margin argument does not settle the ordering at finite $n$, especially near a tie.
Correction: For a fixed positive gap, errors smaller than half that gap preserve the maximizer. For random histories, require convergence in probability there and uniqueness almost surely; the probability of histories with very small gaps must then vanish as the threshold shrinks.
Another mistake: Checking only the final regression fit while ignoring estimated future values in its pseudo-outcome.
Correction: Bound both the fitted conditional-mean error and the propagated conditional error in the future value, as in the recursive inequality above.

Check Your Understanding

Answer each question, then compare with the solutions below.

At a fixed history, two actions have Q-values 7.0 and 6.2. What uniform bound on the absolute estimation errors guarantees the correct action?
Why does a singleton action set not have a separation gap defined by the maximum over competing actions, and what happens to its decision?
If the gap is positive at every history except a set of target probability zero, must it be bounded below by one common positive constant?
In backward Q-learning, name the two errors that can contribute to the stage-$t$ Q-estimation error when the pseudo-outcome uses an estimated future value.

Solutions. (1) The gap is $7.0-6.2=0.8$, so any maximum absolute error strictly below $0.8/2=0.4$ guarantees the correct action. (2) With only one action, the set of competitors is empty, so that maximum is undefined; nevertheless the decision is trivial because both oracle and estimated rules must select the sole action. (3) No. For example, the gap can be positive but arbitrarily close to zero across histories. Random-history consistency can still follow if the gap is positive almost surely and the Q-estimation error converges in probability at a target history. (4) The fitted conditional-mean error for its estimated pseudo-outcome, and the conditional expected absolute error between the estimated and true future values.