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.

On the two-valuedness hypothesis. The statement carries $\forall s,\ \rho(s) \in \{0,1\}$ explicitly. It is not decoration: the row equations above only constrain states of class $0$ and of class $1$, so without it a state of neither class has a completely unconstrained transition row and an arbitrarily large reward, and the conclusion fails outright from such an initial state. An earlier version of this node omitted it and has been deprecated.

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.