Finite-horizon offline reinforcement-learning dataset and coverage

Assume the Axiom of Choice for the policy-induced path laws below. Let $S$ be a nonempty finite state set, let $A(s)$ be a finite nonempty action set for each $s\in S$, and let $\mathcal{R}\subset \mathbb{R}$ be a finite nonempty reward set. A finite Markov decision process here consists of these sets and a joint next-state/reward probability mass $p(s^{\mathrm{\prime }},r\mid s,a)\ge 0$, defined for $s,s^{\mathrm{\prime }}\in S$, $a\in A(s)$, and $r\in \mathcal{R}$, with ${\sum }_{s^{\mathrm{\prime }}\in S}{\sum }_{r\in \mathcal{R}}p(s^{\mathrm{\prime }},r\mid s,a)=1$ for every $(s,a)$. A stationary Markov policy $\sigma$ assigns probabilities $\sigma (a\mid s)\ge 0$ with ${\sum }_{a\in A(s)}\sigma (a\mid s)=1$ at every state.

Fix a horizon $H\ge 1$, a discount $0\le \gamma \le 1$, and an initial state $s_0\in S$. A trajectory is a tuple $\tau =(s_0,a_0,r_1,s_1,\dots ,a_{H-1},r_H,s_H)$ with $s_t\in S$, $a_t\in A(s_t)$, and $r_{t+1}\in \mathcal{R}$ for each $0\le t<H$. Write ${\mathrm{\Omega }}_H$ for the finite set of all such tuples. For each stationary policy $\sigma$, let $P_H^{\sigma }$ be the probability law on ${\mathrm{\Omega }}_H$ whose atom masses are

$P_H^{\sigma }(\{\tau \})={\prod }_{t=0}^{H-1}\sigma (a_t\mid s_t)p(s_{t+1},r_{t+1}\mid s_t,a_t)\mathrm{.}$

For a trajectory $\tau$, its finite-horizon return is $G_H(\tau )={\sum }_{t=0}^{H-1}{\gamma }^t{r}_{t+1}$, and the value of target policy $\pi$ from $s_0$ is $J_H(\pi ;s_0)={\int }_{{\mathrm{\Omega }}_H}{G}_{H}d{P}_H^{\pi }$. A fixed logged dataset of size $n\ge 1$ consists of independent trajectories $({\tau }_1,\dots ,{\tau }_n)$, each with law $P_H^{\mu }$ for a behavior policy $\mu$; the true behavior propensities $\mu (a\mid s)$ used to generate the data are known. Full horizon coverage means $P_H^{\pi }\ll P_H^{\mu }$, so every behavior-null trajectory event is also target-null. In this finite setting, the condition $\pi (a\mid s)>0\Rightarrow \mu (a\mid s)>0$ at every state-action pair reachable under $\pi$ before time $H$ is sufficient for full horizon coverage. A trajectory function is integrable under a law $P$ when ${\int }_{{\mathrm{\Omega }}_H}\mathrm{\mid }f\mathrm{\mid }dP<\mathrm{\infty }$. All returns are integrable in this finite-horizon finite-reward setting; importance-weighted return expressions below are used only when they are integrable.

Under AC, a stationary policy on a finite MDP has the stated finite-prefix action-state-reward law.

Independent sample trajectories are random elements with independent generated sigma-algebras.

Absolute continuity means every null set for the behavior law is null for the target law.

A probability measure is a measure of total mass one.

Expectation is the Lebesgue integral under the trajectory law.

A real trajectory function is integrable when its absolute value has finite integral.

The stated state-action support condition implies full horizon coverage. Here a state-action pair $(s,a)$ is reachable under $\pi$ before time $H$ when $P_H^{\pi }(S_t=s,A_t=a)>0$ for some $0\le t<H$. Suppose a trajectory atom $\tau$ has $P_H^{\pi }(\{\tau \})>0$. Its atom mass is a product of nonnegative factors, so every target action probability and every shared transition/reward factor along $\tau$ is positive. Each state-action pair on $\tau$ is therefore reachable under $\pi$, and the support condition gives $\mu (a_t\mid s_t)>0$ at every time. The same initial state and transition/reward factors then give $P_H^{\mu }(\{\tau \})>0$. Since ${\mathrm{\Omega }}_H$ is finite, every event is a finite union of atoms; thus every $P_H^{\mu }$-null event is also $P_H^{\pi }$-null, proving $P_H^{\pi }\ll P_H^{\mu }$.