JAO Lemma 13 for a two-class MDP: change of measure for the number of plays of the planted pair

The two-class planted gadget. The MDP is given by its defining equations rather than through an auxiliary definition. The data are a class map $\rho : S \to \{0,1\}$, an escape map $\mathrm{up}$, a return map $\mathrm{down}$ and a navigation map $\mathrm{nav}$, and $M$ satisfies: the reward is the class, $r(s,b) = \rho(s)$; from a class-$0$ state $s$ every action $b$ goes to the class-$1$ state $\mathrm{up}(s)$ with probability $\delta + \varepsilon\,[\,(s,b) = (s^*,b^*)\,]$ and to the class-$0$ state $\mathrm{nav}(s,b)$ otherwise; from a class-$1$ state $s$ every action goes to the class-$0$ state $\mathrm{down}(s)$ with probability $\delta$ and stays at $s$ otherwise. Every row is supported on two distinct states whose masses sum to $1$, so the transition function is pinned down completely. The reference MDP $M_0$ is the same shape with $\varepsilon = 0$. For $S = 2$ and $\rho = \mathrm{id}$ this is JAO Figure 3 with $D' = 1/\delta$; for $S > 2$ it is the composite of Figure 4, its class-$0$ states being the $s_\circ^{(i)}$.

The whole of JAO Section 6 is run at this level of generality, on the composite MDP itself rather than on the collapsed two-state MDP they pass to on p. 1583. That reduction is not available as an inequality between regrets: the simulating policy would have to be produced before the planting is chosen, and it sees neither which copy the composite is in nor which of the $A$ actions was played. Working with the class in place of the state avoids it, and no step of the argument is lost.

Throughout, the initial state $s_0$ is arbitrary and of either class.

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

This is equation (37) of JAO (p. 1584), obtained from their Lemma 13 applied to $f = N_{(s^*,b^*)}$, a function of the observed state-action history with values in $[0,T]$.

Proof. A divergence decomposition followed by Pinsker's inequality. The planted and reference MDPs differ in exactly one row of the transition function, namely $(s^*,b^*)$, so the relative entropy between the two trajectory laws under a common policy and a common initial distribution is $\mathbb{E}_{\mathrm{unif}}[N_{(s^*,b^*)}]$ times the relative entropy of the two rows. Both rows are two-point distributions on $\{\mathrm{up}(s^*), \mathrm{nav}(s^*,b^*)\}$ — this is why the gadget is set up with two-point rows — with masses $\delta$ and $\delta+\varepsilon$, so that relative entropy is the Bernoulli one $\mathrm{kl}(\delta \Vert \delta+\varepsilon)$, and $\delta + (\delta+\varepsilon) \le 3\delta \le 1$ gives $\mathrm{kl}(\delta \Vert \delta+\varepsilon) \le \varepsilon^2/\delta$. Pinsker then converts this into a bound on the difference of expectations of any $[0,1]$-valued function, applied to $N_{(s^*,b^*)}/T$.

JAO note that the observation in an MDP is the next state rather than the reward, which is harmless because the reward is a deterministic function of the state; the same remark applies here with the class in place of the state.