Hidden-State Overlap in POMDP Policy Evaluation

For the joint state $S_t$ and the target-policy reward regression $g_e$, $$\theta(K,e) := \sum_{s=(x,h)\in\mathcal S} d_e(s)g_e(s) = \sum_{s=(x,h)\in\mathcal S} d_e(s) \sum_{a\in\mathcal A} e(a\mid x)\,E_K[Y_t\mid S_t=s,A_t=a].$$

For the overlap constant $C$ and experiment $M$, the latent stationary overlap condition holds when $C\ge 1$ and, writing $d_e$ and $d_b$ for the stationary laws of the target-policy and behavior-policy joint-state transition kernels, respectively, $$d_e(s)\le C\,d_b(s), \qquad s\in\mathcal S .$$

For $0\le k<T$, define $$Z_t(k) := Y_t\prod_{j=t-k}^{t}\rho_j,$$ where $\rho_t$ is the observable one-step policy ratio with the zero-cell convention. The clipped partial-history importance-weighted estimator is $$\widehat\theta_k := \operatorname{clip}_{[-1,1]} \left\{ \frac{1}{T-k}\sum_{t=k}^{T-1} Z_t(k) \right\}.$$

For $C\ge 1$, define $$q_C:=\frac{C-1}{C}.$$

For $T\in\mathbb N$ and $C\ge 1$, define $$\kappa_T^{\mathrm{rad}}(C):= \begin{cases} 0, & Tq_C^2\le 1,\\[3pt] \displaystyle \min\!\left\{ \left\lfloor\frac T2\right\rfloor, \left\lfloor\frac{\log(Tq_C^2)}{2\log(1/\alpha)+\log L}\right\rfloor \right\}, & Tq_C^2>1. \end{cases}$$

Fix $t_0>0$ and $\zeta>0$. Let $R_T(t_0,\zeta,C)$ be the minimax squared-error risk in Definition P-3, let $q_C=(C-1)/C$ be the overlap-distance radius in Definition P-10, and set $$\beta=\frac{2}{2+t_0\zeta}, \qquad \mathfrak r_T(t_0,\zeta,C) = T^{-1}+T^{-\beta}q_C^{2(1-\beta)} .$$ There exist constants $c_{\mathrm{lo}},c_{\mathrm{hi}}>0$, with $c_{\mathrm{lo}}\le c_{\mathrm{hi}}$, and an integer $T_\star\ge 1$, all depending only on $t_0$ and $\zeta$, such that for every $C\ge 1$ and every $T\ge T_\star$, $$c_{\mathrm{lo}}\mathfrak r_T(t_0,\zeta,C) \le R_T(t_0,\zeta,C) \le c_{\mathrm{hi}}\mathfrak r_T(t_0,\zeta,C),$$ and the radius-adaptive partial-history importance-weighted estimator with depth $\kappa_T^{\mathrm{rad}}(C)$ from Definition P-11 satisfies $$\sup_{m\in\mathcal M_T(t_0,\zeta,C)} \mathbb E_m\!\left[ \bigl(\widehat\theta_{\kappa_T^{\mathrm{rad}}(C)}-\theta_m\bigr)^2 \right] \le c_{\mathrm{hi}}\mathfrak r_T(t_0,\zeta,C).$$ Moreover, for every sequence $C_T\ge 1$, if $Tq_{C_T}^2$ is eventually bounded, then there is a constant $c_{\mathrm{imm}}>0$, depending on the sequence and on $t_0,\zeta$, such that eventually $$\sup_{m\in\mathcal M_T(t_0,\zeta,C_T)} \mathbb E_m\!\left[ \bigl(\widehat\theta_{0}-\theta_m\bigr)^2 \right] \le \frac{c_{\mathrm{imm}}}{T}.$$

Fix $t_0,\zeta,C\in\mathbb R$. Assume:

• (Positive memory exponent.) $t_0>0$.
• (Positive overlap exponent.) $\zeta>0$.
• (Fixed latent-overlap radius.) $C>1$.

Let the exponent $\beta$ be $$\beta=\frac{2}{2+t_0\zeta}.$$ There exist constants $c_\star,c^\star\in\mathbb R$ and an integer $T_\star\ge 1$ such that $$0<c_\star\le c^\star$$ and, for every integer $T\ge T_\star$, $$c_\star T^{-\beta} \le R_T(t_0,\zeta,C) \le c^\star T^{-\beta},$$ where $R_T(t_0,\zeta,C)$ is the minimax squared-error risk in Definition P-3. Moreover, the clipped partial-history importance-weighted estimator $\widehat\theta_{k_T}$, with $k_T$ as in Definition P-5, satisfies $$\sup_{M\in\mathcal M_T(t_0,\zeta,C)} \mathbb E_M\!\left[ \{\widehat\theta_{k_T}-\theta(M)\}^2 \right] \le c^\star T^{-\beta},$$ with $\theta(M)$ the stationary target-policy mean reward in Definition P-2. For each integer $T\ge T_\star$, there is an integer $Q\ge 1$ such that the lower bound is witnessed by the two signed-depth alternatives $M_{Q,v}^T$, $v\in\{-1,+1\}$, generated by Definition P-6 with one observed state and $2(Q+1)$ latent states: for every measurable observable-data estimator $\widehat\theta$, under the usual squared-error integrability conditions for both alternatives, $$c_\star T^{-\beta} \le \max_{v\in\{-1,+1\}} \mathbb E_{M_{Q,v}^T}\!\left[ \{\widehat\theta-\theta(M_{Q,v}^T)\}^2 \right].$$

Let $t_0>0$ and $\zeta>0$. At unit latent overlap, $C=1$, the following assertions hold. For every trajectory length $T$, every finite observed and hidden state cardinalities, and every experiment $M\in\mathcal M_T(t_0,\zeta,1)$ in the model class of Definition P-1, the target stationary law $d_e$ and the behavior stationary law $d_b$ of the corresponding policy-induced joint-state transition kernels coincide: $$d_e=d_b .$$ Moreover, there is a constant $c_{\mathrm{imm}}>0$, depending only on $t_0$ and $\zeta$, such that for every integer $T\ge 1$, the worst-case squared risk of the immediate observable estimator $\widehat\theta_0$ satisfies $$\sup_{M\in\mathcal M_T(t_0,\zeta,1)} \mathbb E_M\!\left[\bigl(\widehat\theta_0-\theta(K,e)\bigr)^2\right] \le \frac{c_{\mathrm{imm}}}{T}.$$ Finally, for the minimax squared-error risk $R_T(t_0,\zeta,1)$ of Definition P-3, there are constants $c_{\mathrm{lo}},c_{\mathrm{hi}}>0$ with $c_{\mathrm{lo}}\le c_{\mathrm{hi}}$ and an integer $T_\star\ge 1$ such that, for every $T\ge T_\star$, $$\frac{c_{\mathrm{lo}}}{T} \le R_T(t_0,\zeta,1) \le \frac{c_{\mathrm{hi}}}{T}.$$ The hidden-state exponent at these positive scales satisfies $$\frac{2}{2+t_0\zeta}<1 .$$

The following conditions hold:

• (Fixed smoothness.) The constants satisfy $t_0>0$ and $\zeta>0$.
• (Shrinking radius.) The deterministic radius excess sequence $(\delta_T)_{T\ge1}$ satisfies $\delta_T\ge0$ for every $T$.
• (Local limit.) The sequence satisfies $\delta_T\to0$.
• (Rate exponent.) Let $\beta=2/(2+t_0\zeta)$.
• (Local rate and depth.) Define $$r_T(\delta) = T^{-1}+T^{-\beta}\delta_T^{2(1-\beta)}$$ and $$\kappa_T = \begin{cases} 0, & T\delta_T^2\le 1,\\[3pt] \displaystyle \min\left\{\left\lfloor T/2\right\rfloor, \left\lfloor \frac{\log(T\delta_T^2)} {2\log(1/\alpha)+\log L} \right\rfloor\right\}, & T\delta_T^2>1. \end{cases}$$

Then there exist constants $c_{\mathrm{loc}},C_{\mathrm{loc}}$ with $0<c_{\mathrm{loc}}\le C_{\mathrm{loc}}$, depending only on $t_0$ and $\zeta$, such that, for all sufficiently large $T$, $$c_{\mathrm{loc}}\,r_T(\delta) \le R_T(t_0,\zeta,1+\delta_T) \le C_{\mathrm{loc}}\,r_T(\delta),$$ where $R_T$ is the minimax squared-error risk in Definition P-3. Moreover, the observable partial-history importance-weighted estimator $\widehat\theta_{\kappa_T}$ of Definition P-4 satisfies $$\sup_{M\in\mathcal M_T(t_0,\zeta,1+\delta_T)} \mathbb E_M\!\left[ \bigl(\widehat\theta_{\kappa_T}-\theta(M)\bigr)^2 \right] \le C_{\mathrm{loc}}\,r_T(\delta)$$ for all sufficiently large $T$. Finally, if there is a constant $D\ge0$ such that $T\delta_T^2\le D$ for all sufficiently large $T$, then there is a constant $c_{\mathrm{imm}}>0$ such that $$\sup_{M\in\mathcal M_T(t_0,\zeta,1+\delta_T)} \mathbb E_M\!\left[ \bigl(\widehat\theta_{0}-\theta(M)\bigr)^2 \right] \le \frac{c_{\mathrm{imm}}}{T}$$ for all sufficiently large $T$.

For every horizon $T$, the refreshed insulin experiment $\mathcal I_{\mathrm{grid}}$ of Definition P-9 satisfies:

• (State count.) Its observed--latent joint-state alphabet has cardinality $90\cdot 4=360$.
• (Uniform contraction.) It satisfies Assumption A-6 with contraction parameter $\alpha=1/2$.
• (Policy overlap.) It satisfies Assumption A-5 with one-step overlap constant $L=10/3$.
• (Stationary overlap.) It satisfies Assumption A-7 with stationary-overlap constant $C=720$.

Define the immediate-weighting bias diagnostic by $$\Delta_{\mathrm{imm}}(T) = \sum_s d_b(s)\sum_{a\in\{0,1\}} b(a\mid s_X)\, \frac{e(a\mid s_X)}{b(a\mid s_X)} \int r\,K(ds',dr\mid s,a) - \theta(K,e),$$ where $K,b,e$ are the transition kernel, behavior policy, and target policy of $\mathcal I_{\mathrm{grid}}$, $s_X$ is the observed coordinate of $s$, and $d_b$ is the stationary law induced by $b$. This diagnostic is interval-certified as strictly negative: $$-0.006 < \Delta_{\mathrm{imm}}(T) < -0.0058 .$$