JAO Lemma 13: change of measure for the number of plays of the planted action

Throughout, the MDP is the collapsed two-state gadget of JAO Figure 3, presented by its defining equations rather than through an auxiliary definition: state $0$ is $s_\circ$ with reward $0$, state $1$ is $s_p$ with reward $1$, the return probability is $p(s_\circ \mid s_p, b) = \delta$ for every action $b$, and the escape probability is $p(s_p \mid s_\circ, b) = \delta$ for every action other than the planted action $a$, for which it is $\delta + \varepsilon$. The gadget has diameter $D' = 1/\delta$. The reference MDP $M_0$ is the same gadget with no planting.

Statement. For $0 < \varepsilon \le \delta \le \tfrac13$, every horizon $T$ and every policy $\pi$,

where $N_\circ^*$ counts the rounds in which the planted action $a$ is played in state $s_\circ$.

This is equation (37) of JAO (p. 1584), obtained from their Lemma 13 applied to $f = N_\circ^*$, a function of the observed state-action history taking values in $[0, T]$. Lemma 13 itself states that for $f$ with values in $[0, B]$, $0 \le \delta \le \tfrac12$ and $0 \le \varepsilon \le 1 - 2\delta$,

the hypothesis $\varepsilon \le \delta \le \tfrac13$ of the present statement gives $\varepsilon \le \tfrac13 \le 1 - 2\delta$, so the lemma applies.

The proof is a divergence decomposition followed by Pinsker's inequality. The planted and reference gadgets differ in exactly one row of the transition function, namely $(s_\circ, a)$, so the relative entropy between the two trajectory laws under a common policy is $\mathbb{E}_{\mathrm{unif}}[N_\circ^*]$ times the relative entropy $\mathrm{kl}(\delta + \varepsilon \,\|\, \delta) \le \frac{\varepsilon^2}{\delta(1-\delta)}$ of the two rows; Pinsker's inequality then converts this into a bound on the difference of expectations of any $[0,B]$-valued function. JAO note that the observation in an MDP is the next state rather than the reward, which is harmless here because the reward is a deterministic function of the state, so $N_\circ^*$ is a function of the state-action sequence and the argument of Auer et al. goes through verbatim.