Optimal Regime via Dynamic Programming

Summary

The optimal dynamic treatment regime $d^{\text{opt}}$ is characterized by backward induction (dynamic programming). Working from the last decision $K$ to the first, define Q-functions $Q_k({\bar{s}}_k,{\bar{a}}_k)=\mathbb{E}(\text{value-to-go}\mid \text{history})$ measuring the “quality” of taking treatment $a_k$ now and behaving optimally thereafter, and value functions $V_k={\max }_{a_k}{Q}_k$. The optimal rule at each stage maximizes the Q-function: $d_k^{\text{opt}}({\bar{s}}_k,{\bar{a}}_{k-1})=\arg {\max }_{a_k}{Q}_k$. Under consistency, sequential randomization, and positivity these observed-data Q-functions coincide with the potential-outcome definitions, so $d^{\text{opt}}$ is identifiable. A key result: the optimal rules do not depend on when a patient presents (decision 1 vs. “midstream”), so a single rule set $d^{\text{opt}}$ applies to all patients.

Overview

This note gives the engine shared by Q-learning and A-learning and Robustness: the dynamic-programming characterization of $d^{\text{opt}}$. The two methods differ only in how they estimate the pieces of this recursion. The recursion is first written in potential outcomes, then shown to equal an observed-data version under the identification assumptions.

Main Content

Backward induction in potential outcomes

Optimal regime by backward recursion (§3, Eqs. 5-8)

At the last decision $K$, for histories $({\bar{s}}_K,{\bar{a}}_{K-1})\in {\Gamma }_K$:

$$d_K^{(1)\text{opt}}({\bar{s}}_K,{\bar{a}}_{K-1})=\arg \underset{a_K\in {\Psi }_K}{\max }\mathbb{E}\{Y^{\ast }({\bar{a}}_{K-1},a_K)\mid {\bar{S}}_K^{\ast }({\bar{a}}_{K-1})={\bar{s}}_K\},$$

with value $V_K^{(1)}={\max }_{a_K}\mathbb{E}\{Y^{\ast }\mid \cdot \}$. Then for $k=K-1,\dots ,1$:

$$d_k^{(1)\text{opt}}({\bar{s}}_k,{\bar{a}}_{k-1})=\arg \underset{a_k\in {\Psi }_k}{\max }\mathbb{E}[V_{k+1}^{(1)}\{{\bar{s}}_k,S_{k+1}^{\ast }({\bar{a}}_{k-1},a_k),{\bar{a}}_{k-1},a_k\}\mid {\bar{S}}_k^{\ast }({\bar{a}}_{k-1})={\bar{s}}_k].$$

Each stage chooses the treatment maximizing the expected outcome assuming optimal behavior at all later stages — the defining property of dynamic programming. (Section A.1 of the supplement proves this $d^{(1)\text{opt}}$ is optimal in the sense of the regime definition.)

Observed-data Q- and value functions

Q-functions and value functions (§3, Eqs. 9-14)

In terms of the observed data, define at decision $K$:

$$Q_K({\bar{s}}_K,{\bar{a}}_K)=\mathbb{E}(Y\mid {\bar{S}}_K={\bar{s}}_K,{\bar{A}}_K={\bar{a}}_K),V_K({\bar{s}}_K,{\bar{a}}_{K-1})=\underset{a_K\in {\Psi }_K}{\max }{Q}_K({\bar{s}}_K,{\bar{a}}_{K-1},a_K),$$

and recursively for $k=K-1,\dots ,1$:

$$Q_k({\bar{s}}_k,{\bar{a}}_k)=\mathbb{E}\{V_{k+1}({\bar{s}}_k,S_{k+1},{\bar{a}}_k)\mid {\bar{S}}_k={\bar{s}}_k,{\bar{A}}_k={\bar{a}}_k\},$$ $$d_k^{\text{opt}}({\bar{s}}_k,{\bar{a}}_{k-1})=\arg \underset{a_k\in {\Psi }_k}{\max }{Q}_k({\bar{s}}_k,{\bar{a}}_{k-1},a_k),V_k({\bar{s}}_k,{\bar{a}}_{k-1})=\underset{a_k}{\max }{Q}_k({\bar{s}}_k,{\bar{a}}_{k-1},a_k).$$

$Q_k$ measures the “quality” of treatment $a_k$ given the history, then following the optimal regime thereafter; $V_k$ is the “value” of a history assuming optimal future decisions.

Identification: observed-data optimum equals potential-outcome optimum (§3, Eq. 19)

Under consistency, sequential randomization, and positivity, the conditional distributions of the observed data in (9)–(14) equal those of the potential outcomes in (5)–(8), so

$$d_k^{(1)\text{opt}}({\bar{s}}_k,{\bar{a}}_{k-1})=d_k^{\text{opt}}({\bar{s}}_k,{\bar{a}}_{k-1}),V_k^{(1)}=V_k,k=1,\dots ,K.$$

Thus an optimal regime in the $\Psi$-specific class $\mathcal{D}$ can be obtained from the distribution of the observed data. (The optimum need not be unique — any rule selecting an arg-max treatment is optimal.)

Midstream regimes: the rule set is presentation-invariant

Optimal rules do not depend on when a patient presents (§4, Eq. 25)

A new patient may present “midstream” — immediately prior to decision $\ell >1$, having received $\ell -1$ treatments under routine practice. One can define an optimal regime $d^{(\ell )\text{opt}}$ starting at decision $\ell$. Under the same assumptions (plus consistency of the presenting covariates), the midstream rules coincide with the original recursion:

$$d_k^{(\ell )\text{opt}}({\bar{s}}_k,{\bar{a}}_{k-1})=d_k^{\text{opt}}({\bar{s}}_k,{\bar{a}}_{k-1}),k=\ell ,\dots ,K,$$

subsuming the $\ell =1$ case. Consequence: the single rule set $d^{\text{opt}}=(d_1^{\text{opt}},\dots ,d_K^{\text{opt}})$ is relevant for any patient regardless of when they present — treatment for a midstream patient is $d_{\ell }^{\text{opt}}$ evaluated at their history (Robins 2004).

Caveat: this presentation-invariance requires the conditioning sets to carry the same information; it relies on the sequential-randomization and consistency assumptions holding for the routine-practice history.

Connections

• The shared target of Q-learning (which models the Q-functions directly) and A-learning and Robustness (which models only the contrast $C_k=Q_k(\cdot ,1)-Q_k(\cdot ,0)$, sufficient for the arg-max).
• Backward induction over Q/value functions is exactly the dynamic-programming / Bellman structure used in reinforcement learning.
• Builds on the estimand and assumptions of the Dynamic Treatment Regimes Framework.

See Also

• Dynamic Treatment Regimes Framework — estimand and identification assumptions
• Q-learning — estimating the Q-functions
• A-learning and Robustness — estimating only the contrast functions