Evaluating Policies with Hidden States

• We observe one trajectory of length $T$ under a known behavior policy $b$.
• Each date records observed state $X_t$, binary action $A_t$, and reward $Y_t$.
• A known target policy $e$ chooses actions differently.
• We want its long-run average reward, including how earlier actions change today’s hidden state.

Changing today’s treatment can change tomorrow’s condition. How can we evaluate that accumulated effect from a partially observed record?

Current-action importance weighting replaces today’s behavior action probabilities with target probabilities.

It still averages rewards over states generated by earlier behavior actions.

• With the full Markov state observed, stationary distribution corrections can support parametric estimation: Mehrabi and Wager (2025).
• With hidden state, Hu and Wager (2023) weight recent action histories. Longer histories reduce bias but increase variance.

Does bounded target-to-behavior stationary occupancy restore parametric accuracy when the state is hidden?

Let $d_b$ and $d_e$ be the behavior and target stationary distributions of the full state $s$, including its hidden component.

Restrict how much the target can increase occupancy:

$$d_e(s)\le C\,d_b(s), \qquad s\in\mathcal S .$$

Here $\mathcal S$ is the full state space and $C\ge1$ is the occupancy bound. Its distance from equality is:

$$q_C:=\frac{C-1}{C}.$$

The radius $q_C$ bounds the state imbalance inherited from behavior actions.

Our answer: with finite states, binary actions, stationary data, known observed-state randomization, bounded rewards and action ratios, and geometric forgetting, calibrated history weighting attains matching minimax bounds.

Fixed $C>1$ still allows slower than parametric estimation. Parametric accuracy emerges when the radius is sufficiently small.

The observed state is constant. Hidden state contains depth $J_t\in\{0,\ldots,Q\}$, with $Q\ge1$, and sign $U_t\in\{-1,+1\}$.

Depth transitions: below $Q$, advance to $J_t+1$ with probability $\alpha$, and reset to zero with probability $1-\alpha$. At $Q$, reset with probability one. Here $0<\alpha<1$.

• An advance preserves sign under action one; action zero redraws sign fairly.
• A reset draws a fresh sign with mean $\varepsilon_C=\min\{(C-1)/2,1/2\}$.

$$b(A_t=1)=\frac{1}{L},\qquad b(A_t=0)=1-\frac{1}{L}, \qquad e(A_t=1)=1,\qquad e(A_t=0)=0.$$

Here $L>1$ controls action overlap. The target always preserves sign; behavior can erase it.

Rewards depend on sign only at terminal depth $Q$. Earlier actions therefore affect today’s reward even though the observed state never changes.

The full Markov state is $S_t=(X_t,H_t)$, with hidden component $H_t$. A time-invariant kernel $K$ generates reward and next state from current full state and action.

• Known policies $b,e$ depend only on $X_t$.
• Sequential ignorability: given $X_t$, behavior randomization additionally depends on neither hidden state nor past history.
• Stationary start: $S_0\sim d_b$.
• Rewards satisfy $|Y_t|\le1$; both state spaces are finite and actions are binary.

Our stationary target value is:

$$\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].$$

Here $\mathcal A=\{0,1\}$. The function $g_e(s)$ averages current reward over target actions at state $s$. The outer average uses the full-state distribution produced by running the target in the long run.

Action overlap controls observable importance weights:

$$e(a\mid x)\le L b(a\mid x).$$

Here $L=\exp(\zeta)$, with $\zeta>0$. Every target action has behavior support; larger $L$ permits larger weights.

Geometric mixing makes both policies forget their starting states:

$$\|\nu P_p-\nu'P_p\|_{\mathrm{TV}} \le \alpha\|\nu-\nu'\|_{\mathrm{TV}}.$$

For $p=b,e$, $P_p$ is the full-state transition under policy $p$. Total variation measures the difference between distributions $\nu,\nu'$.

Here $\alpha=\exp(-1/t_0)$, with $t_0>0$; larger $t_0$ means slower forgetting.

Together with stationary overlap $d_e(s)\le C d_b(s)$ and the model conditions, these define $\mathcal M_T(t_0,\zeta,C)$.

In the example, every state shares a reset component of probability $1-\alpha$. That component forgets both depth and sign, giving contraction by at most $\alpha$.

Let $R_T(t_0,\zeta,C)$ be the smallest worst-case mean squared error attainable from observed data and known policies over $\mathcal M_T(t_0,\zeta,C)$.

$$\beta=\frac{2}{2+t_0\zeta}, \qquad \mathfrak r_T(t_0,\zeta,C) = T^{-1}+T^{-\beta}q_C^{2(1-\beta)} .$$

The exponent $\beta$ combines mixing and action overlap. The risk surface $\mathfrak r_T$ adds ordinary sampling error to the cost of repairing hidden-state imbalance.

$$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),$$

The positive constants and sample-size threshold depend only on $t_0,\zeta$, uniformly over $C$ and all finite state counts.

The estimator uses supplied values of $t_0,\zeta,C$. Every observable estimator faces the lower bound.

Three readings of the same surface:

• Fixed $C>1$: mean squared error is comparable to $T^{-\beta}$, retaining the Hu–Wager hidden-state exponent.
• Equality, $C=1$: $d_e=d_b$, and current-action weighting attains the $T^{-1}$ scale.
• Shrinking radius: the transition occurs at $q_C\asymp T^{-1/2}$. If $Tq_C^2$ remains bounded, current-action weighting attains parametric accuracy.

In the example, fixed $C>1$ permits a fixed positive reset-sign bias. Increasing terminal depth then sustains the slower hidden-state rate while respecting stationary overlap.

Define the observed action ratio $\rho_t=e(A_t\mid X_t)/b(A_t\mid X_t)$ on behavior-supported actions.

Choose depth $k$: $k$ past actions plus the current action.

$$Z_t(k) := Y_t\prod_{j=t-k}^{t}\rho_j,$$

The score $Z_t(k)$ reweights reward $Y_t$ by target-to-behavior action ratios throughout the window.

$$\widehat\theta_k := \operatorname{clip}_{[-1,1]} \left\{ \frac{1}{T-k}\sum_{t=k}^{T-1} Z_t(k) \right\}.$$

The estimator averages the complete windows, then clips to the reward range $[-1,1]$.

In the example, only all-one action windows receive positive weight. Weighting them reproduces the target’s sign-preserving action sequence.

Sequential ignorability makes the weight product replace behavior actions with target actions throughout the window.

Its population mean is $\sum_s d_b(s)(P_e^k g_e)(s)$: start under $d_b$, run $k$ target transitions, then average reward under the target action rule.

• Stationary overlap means $d_b$ contains at least a $1/C$ share of $d_e$. Their total variation distance is therefore at most $q_C$.
• Each target transition contracts this mismatch by $\alpha$.
• Remaining reward bias is controlled on the scale $q_C\alpha^k$.

At depth zero, the state distribution remains $d_b$.

In the example, longer weighted histories preserve more sign memory. Resets make sign information predating the window progressively less consequential.

Action ratios have conditional mean one and are bounded by $L$. Multiplying them makes the variance grow on the scale $L^k/T$.

Overlapping windows do not add another factor of $k$: nonshared ratios average out, leaving geometric covariance bounds. For separated windows, behavior mixing controls the dependence.

For $M\in\mathcal M_T(t_0,\zeta,C)$ and $k\le T/2$:

$$\mathbb E_M\!\left[\{\widehat\theta_k-\theta(K,e)\}^2\right] \le 4q_C^2\alpha^{2k} +\frac{2}{T}\left\{ L^{k+1}\left(1+\frac{4}{L-1}\right) +\frac{4}{1-\alpha} \right\},$$

The expectation averages over the behavior trajectory.

• Squared bias decreases with history length.
• Action-weighting variance increases with history length.

A smaller occupancy radius means less bias needs repair.

Balance squared bias $q_C^2\alpha^{2k}$ against variance $L^k/T$:

$$\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}$$

The chosen depth $\kappa_T^{\mathrm{rad}}(C)$ uses trajectory length and supplied mixing, action-overlap, and stationary-overlap bounds.

• When $Tq_C^2\le1$, use depth zero: occupancy bias is already small enough.
• Otherwise, history grows logarithmically with $Tq_C^2$.

The denominator combines two mixing exponents from squared bias with one action-overlap exponent from variance. This balance produces $\beta$ and the upper risk bound.

Could another observable estimator avoid this tradeoff?

Return to the depth-and-sign example. Actions change sign memory, while depth transitions are identical under both policies.

Only an advance from $j-1$ reaches depth $j>0$, so stationary masses satisfy $w_j=\alpha w_{j-1}$. The forced reset at $Q$ closes the chain; normalizing this finite geometric sequence gives:

$$w_j\frac{1+u\varepsilon_C L^{-j}}{2}, \qquad w_j= \frac{(1-\alpha)\alpha^j}{1-\alpha^{Q+1}}, \qquad j\in\{0,\ldots,Q\},\ u\in\{-1,+1\}.$$

The first expression is behavior’s stationary probability of depth $j$ and sign $u$.

Both policies have depth mass $w_j$. Behavior’s sign mean is $\varepsilon_C L^{-j}$; the target preserves $\varepsilon_C$.

Their full-state laws satisfy:

$$d_e(s)\le (1+\varepsilon_C)d_b(s), \qquad 1+\varepsilon_C\le C.$$

Increasing terminal depth preserves the occupancy restriction.

The alternatives $v=+1$ and $v=-1$ share dynamics and policies. They reverse only the reward response.

Conditional on the current hidden state, the probability of reward $y\in\{-1,+1\}$ is:

$$\frac{1+yvc_0U_t\mathbf 1\{J_t=Q\}}{2}$$

Here $c_0=(1-\alpha)/4$ is the reward amplitude. The indicator turns on the sign response only at depth $Q$; all other rewards are fair coins.

Under the target, terminal sign has mean $\varepsilon_C$. Thus:

$$\theta(K,e) = v\,c_0(t_0)\,\varepsilon_C\,w_Q .$$

The notation $c_0(t_0)$ emphasizes that the amplitude depends on the mixing scale.

The target-value gap is twice amplitude times reset-sign bias times terminal occupancy. Its square is comparable to $\varepsilon_C^2\alpha^{2Q}$.

Let $\mathcal F_{t-1}^{\mathrm{obs}}$ be the past action-and-reward record, and $o$ one realized record.

Define $q_t^v(o)=\Pr_v(J_t=Q\mid\mathcal F_{t-1}^{\mathrm{obs}}=o)$, the conditional terminal probability.

With $\ell_t=\min\{Q,t\}$, surviving sign memory is recorded by:

$$a_t^{(Q)} := L^{-(Q-\ell_t)} \prod_{j=t-\ell_t}^{t-1}\mathbf 1\{A_j=1\},$$

After $Q$ dates, this is the indicator that the previous $Q$ actions were all one. Earlier, the power of $L$ accounts for pre-sample actions.

A run ending at $Q$ has encountered only fair rewards since its reset. Those rewards cannot select its current sign.

The exact observed reward mean is:

$$\mathbb E_v[Y_t\mid \mathcal F_{t-1}^{\mathrm{obs}}=o] = v\,c_0\,\varepsilon_C\,a_t^{(Q)}(o)\,q_t^v(o),$$

The signal requires both surviving sign memory and a chance of terminal depth.

Why can favorable reward histories not concentrate the conditional probability at $Q$?

• Ending at $Q$ requires $Q$ consecutive advances. They contribute $\alpha^Q$, and their preceding rewards are fair.
• An informative reward occurs at $Q$ and is followed by a forced reset. Its information cannot carry forward along that same advance run.
• Conditioning still divides by the likelihood of observed rewards across all hidden paths.

At date $i$, a reward’s likelihood relative to a fair coin is at least $1-c_0q_i^v$.

Consequently, for $t\ge Q$, the conditional terminal probability obeys $q_t^v\le\alpha^Q\prod_{i=t-Q}^{t-1}(1-c_0q_i^v)^{-1}$, evaluated along the observed history.

Only the latest $Q$ reward updates enter. Before $Q$ dates, the stationary geometric depth tail supplies the missing advance probabilities.

The reward-update bound can be used twice.

1. Start with $q_i^v\le1$. Even the most favorable reward sequence gives $q_t^v\le(\alpha/(1-c_0))^Q$.
2. Write $\eta_0=\alpha/(1-c_0)$. Our amplitude choice $c_0=(1-\alpha)/4$ ensures $\eta_0<1$.
3. Insert the first bound back into the update: each likelihood denominator is now at least $1-c_0\eta_0^Q$.

The cumulative inflation is at most $(1-c_0\eta_0^Q)^{-Q}$. The exponentially small correction $\eta_0^Q$ outweighs the $Q$ possible updates, so this inflation is bounded uniformly over depth.

Therefore, for every observed history:

$$q_t^v(o)\le K_0\,\alpha^Q .$$

Here $K_0$ depends only on $t_0$.

Terminal probability stays on its rarity scale even for reward sequences that favor terminal depth.

Hidden terminal probability enters the observed reward mean before information squares it.

Reward probabilities stay between $(1-c_0)/2$ and $(1+c_0)/2$. Thus information is quadratic in the conditional mean difference, giving the squared terminal factor $\alpha^{2Q}$.

The surviving-memory factor supplies another restriction: under behavior, an all-one history of length $Q$ occurs with probability $L^{-Q}$. Its indicator remains unchanged when squared. Initial incomplete windows have no larger second moment.

Let $\mathbb P_{Q,+1}^{\mathrm{obs},T}$ and $\mathbb P_{Q,-1}^{\mathrm{obs},T}$ be the two observed-trajectory laws. Their Kullback–Leibler divergence measures distinguishability:

$$\operatorname{KL}\!\left(\mathbb P_{Q,+1}^{\mathrm{obs},T}\,\middle\|\,\mathbb P_{Q,-1}^{\mathrm{obs},T}\right) \le \frac{4c_0^2K_0^2}{1-c_0^2}\, T\,\varepsilon_C^2\,\alpha^{2Q}L^{-Q}.$$

Across $T$ dates, reset bias and hidden terminal probability are squared; the frequency of informative action histories enters once.

When $Tq_C^2>1$, choose terminal depth $Q$ so that $T\varepsilon_C^2\alpha^{2Q}L^{-Q}$ stays bounded.

The two alternatives remain statistically hard to distinguish, while their squared target-value separation is comparable to $\varepsilon_C^2\alpha^{2Q}$.

The reset bias tracks the occupancy radius:

$$\frac{q_C}{2}\le \varepsilon_C \le q_C$$

• Increasing depth reduces squared target separation through $\alpha^{2Q}$.
• Observable information falls faster, through $\alpha^{2Q}L^{-Q}$.

Balancing these effects leaves squared separation on the scale $T^{-\beta}q_C^{2(1-\beta)}$, with the same $\beta$ as the estimator’s balance. Hard-to-distinguish values force that order of worst-case error.

Ordinary reward uncertainty also forces a $T^{-1}$ floor, including when the radius is small. Together these give the matching risk surface.

• Choosing history depth when the stationary-overlap radius is unknown.
• Confidence intervals for stationary target values.
• Policy-learning regret built on value estimation.
• Risk with a fixed hidden-state size: our matching alternatives increase terminal depth, and therefore state count, with $T$.

• History weighting changes the transitions that generated today’s state. Mixing limits how much unreweighted history still matters.
• Action overlap determines the variance cost of longer histories; stationary overlap determines how much initial imbalance needs repair.
• Fixed $C>1$ retains the hidden-state rate. At $q_C\lesssim T^{-1/2}$, parametric accuracy is possible. The matching construction keeps terminal depth rare even after conditioning on rewards.

The complete all-radius statement gives matching minimax bounds and an observable estimator attaining them.

At every fixed nonunit radius, partial histories attain the hidden-state exponent and finite depth-and-sign alternatives force it.

Along radii approaching unit overlap, the same surface describes the transition to immediate weighting and parametric risk.