Q-learning

Summary

Q-learning (“Q” for quality; Watkins 1989) estimates the optimal dynamic treatment regime by directly modeling the Q-functions and fitting them by backward-recursive regression. At each decision $k$ (from $K$ down to $1$) one posits a parametric model $Q_k({\bar{s}}_k,{\bar{a}}_k;{\xi }_k)$, regresses the current “value-to-go” response on it by OLS/WLS, and reads off the optimal rule ${\hat{d}}_k^{\text{opt}}=\arg {\max }_{a_k}{Q}_k(\cdot ;{\hat{\xi }}_k)$. Simple and using familiar regression machinery, but consistent only if every Q-function is correctly specified — and for $k<K$ the response is an estimated, typically highly nonlinear value function, so linear working models are easily misspecified and errors propagate backward.

Overview

Q-learning is the more transparent of the two methods in Q- and A-learning - Overview: it turns the dynamic-programming recursion into a sequence of regressions. This note gives the backward-fitting algorithm, the linear-model illustration, and the misspecification concern that motivates A-learning and Robustness.

Main Content

Backward-recursive fitting

Q-learning estimating equations (§5.1, Eqs. 26-27)

Posit models $Q_k({\bar{s}}_k,{\bar{a}}_k;{\xi }_k)$ for $k=K,\dots ,1$. Fit backward:

• Decision $K$ (response ${\bar{V}}_{(K+1)i}=Y_i$): solve for ${\hat{\xi }}_K$

$$\sum _{i=1}^n\frac{\partial Q_K({\bar{S}}_{Ki},{\bar{A}}_{Ki};{\xi }_K)}{\partial {\xi }_K}{\Sigma }_K^{-1}({\bar{S}}_{Ki},{\bar{A}}_{Ki})\{{\bar{V}}_{(K+1)i}-Q_K({\bar{S}}_{Ki},{\bar{A}}_{Ki};{\xi }_K)\}=0,$$

where ${\Sigma }_K$ is a working variance model (constant ${\Sigma }_K\Rightarrow$ OLS).

• Form the fitted value-to-go for the previous stage: ${\bar{V}}_{Ki}={\max }_{a_K\in {\Psi }_K}{Q}_K({\bar{S}}_{Ki},{\bar{A}}_{(K-1)i},a_K;{\hat{\xi }}_K)$.
• Decision $k$ ($k=K-1,\dots ,1$, response ${\bar{V}}_{(k+1)i}$): solve the analogous equation for ${\hat{\xi }}_k$, then form ${\bar{V}}_{ki}={\max }_{a_k}{Q}_k({\bar{S}}_{ki},{\bar{A}}_{(k-1)i},a_k;{\hat{\xi }}_k)$.

The estimated optimal regime is

$${\hat{d}}_{Q,1}^{\text{opt}}(s_1)=d_1^{\text{opt}}(s_1;{\hat{\xi }}_1),{\hat{d}}_{Q,k}^{\text{opt}}({\bar{s}}_k,{\bar{a}}_{k-1})=d_k^{\text{opt}}({\bar{s}}_k,{\bar{a}}_{k-1};{\hat{\xi }}_k),k=2,\dots ,K.\text{\hspace{1em}(28)}$$

Linear two-decision illustration ( $K=2$, binary treatment) (§5.1, Eq. 29)

With ${\Psi }_k=\{0,1\}$ and history vectors ${\mathcal{H}}_1=(1,s_1^{\top }{)}^{\top }$, ${\mathcal{H}}_2=(1,s_1^{\top },a_1,s_2^{\top }{)}^{\top }$, posit linear models

$$Q_1(s_1,a_1;{\xi }_1)={\mathcal{H}}_1^{\top }{\beta }_1+a_1({\mathcal{H}}_1^{\top }{\psi }_1),Q_2({\bar{s}}_2,{\bar{a}}_2;{\xi }_2)={\mathcal{H}}_2^{\top }{\beta }_2+a_2({\mathcal{H}}_2^{\top }{\psi }_2),$$

with ${\xi }_k=({\beta }_k^{\top },{\psi }_k^{\top }{)}^{\top }$. Then the optimal rules are threshold rules on the treatment-interaction term:

$$d_2^{\text{opt}}({\bar{s}}_2,a_1;{\xi }_2)=I({\mathcal{H}}_2^{\top }{\psi }_2>0),d_1^{\text{opt}}(s_1;{\xi }_1)=I({\mathcal{H}}_1^{\top }{\psi }_1>0).$$

The catch: $Q_2$ is a standard regression of $Y$ on observed data, but $Q_1$ models $\mathbb{E}\{V_2({\bar{s}}_2,a_1)\mid S_1=s_1,A_1=a_1\}$ where $V_2={\max }_{a_2}{Q}_2$ — a max of a regression, generally highly nonlinear, only approximated by the linear $Q_1$.

Explicitly, if $S_2\mid S_1,A_1$ is normal, the true $Q_1(s_1,a_1)$ involves the normal cdf $\Phi$ and is clearly nonlinear (§5.3, Eq. 33) — so the posited linear $Q_1$ is misspecified, and for larger $K$ this incompatibility propagates from $K$ down to $1$.

Efficiency, robustness, and remedies

• Efficiency. At decision $K$ (response $Y$), taking ${\Sigma }_K=\mathrm{var}(Y\mid \cdot )$ gives the asymptotically efficient estimator; in practice OLS/WLS is standard. Some authors define Q-learning as OLS fitting (Chakraborty, Murphy & Strecher 2010).
• Consistency requires all models correct. Even under sequential randomization, ${\hat{d}}_Q^{\text{opt}}$ is generally inconsistent for the true optimal regime if any $Q_k$ is misspecified.
• Flexible models. Misspecification risk can be reduced with flexible/ML regressions (e.g. SVR; Zhao, Kosorok & Zeng 2009) tuned by cross-validated MSE — at the cost of interpretability (“black box” rules). A compromise is to fit a simple, interpretable model (e.g. a decision tree) to the complex model’s fitted values.

Connections

• Implements the backward-induction recursion by stagewise regression; the dynamic-programming analog in reinforcement learning is also called Q-learning (Watkins & Dayan 1992).
• Contrast with A-learning and Robustness, which models only the treatment contrast $C_k=Q_k(\cdot ,1)-Q_k(\cdot ,0)$ and the propensity, gaining double robustness.
• The stagewise-regression idea generalizes single-stage outcome modeling such as the T-learner.

See Also

• A-learning and Robustness — the contrast-based, doubly-robust alternative
• Optimal Regime via Dynamic Programming — the Q-functions being modeled
• Q- and A-learning - Overview — comparison and findings