Offline reinforcement learning and off-policy evaluation

There are two finite one-step Markov decision processes with the same logged-data law under one behavior policy, but different target-policy values and different uniquely optimal actions. A finite one-step Markov decision process here has a finite state set, finite nonempty action sets, a finite reward set, and a probability mass on the next-state/reward pair for every state/action pair. Let the state set be $\{s_0,z\}$, the action sets be $A(s_0)=\{a,b\}$ and $A(z)=\{c\}$, the reward set be $\{-1,0,1\}$, and the horizon be $H=1$. In both processes, action $a$ at $s_0$ gives reward $0$ and moves to $z$, and action $c$ at $z$ gives reward $0$ and stays at $z$. In process $M_{+}$, action $b$ at $s_0$ gives reward $1$ and moves to $z$; in process $M_{-}$, it gives reward $-1$ and moves to $z$. The behavior policy chooses $a$ at $s_0$ with probability $1$, while the target policy chooses $b$ there with probability $1$; both policies choose $c$ at $z$ with probability $1$. Every behavior-generated logged trajectory is $(s_0,a,0,z)$ in both processes, so every sample size $n\ge 1$ has the same logged-data law in $M_{+}$ and $M_{-}$. The target value is the expected one-step reward: it is $1$ in $M_{+}$ and $-1$ in $M_{-}$, and the unique value-maximizing initial action is $b$ in $M_{+}$ and $a$ in $M_{-}$. An estimator here is a real-valued function of the logged dataset; it is unbiased for a target value when its expectation under the logged-data law equals that value. Consequently, no such estimator can be unbiased for the target value in both processes, and no data-based action selector can identify the unique optimal initial action with certainty in both.

Expectation is the Lebesgue integral under a probability law.

Levine, Kumar, Tucker, and Fu, Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems

Jiang and Li, Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

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

Assume AC and the finite-horizon dataset conditions of the preceding definition, with full horizon coverage $P_H^{\pi }\ll P_H^{\mu }$. For $0\le t<H$, let ${\mathrm{\Omega }}_{t+1}$ be the finite set of trajectory prefixes through $(R_{t+1},S_{t+1})$, and let $P_{t+1}^{\sigma }$ be the marginal law of this prefix under policy $\sigma \in \{\pi ,\mu \}$. On a behavior-positive prefix define

$W_{0:t}={\prod }_{k=0}^t\frac{\pi (A_k\mid S_k)}{\mu (A_k\mid S_k)},$

and set $W_{0:t}=0$ on behavior-null prefixes. Then $P_{t+1}^{\pi }\ll P_{t+1}^{\mu }$, and $W_{0:t}$ is a version of $d{P}_{t+1}^{\pi }\mathrm{/}d{P}_{t+1}^{\mu }$ up to $P_{t+1}^{\mu }$-almost-everywhere equality. In particular, for every real $G$ integrable under $P_H^{\pi }$, the full-horizon weight $W_{0:H-1}$ satisfies

${\mathbb{E}}_{P_H^{\mu }}[W_{0:H-1}G]={\mathbb{E}}_{P_H^{\pi }}[G],{\mathbb{E}}_{P_H^{\mu }}[W_{0:H-1}\mathrm{\mid }G\mathrm{\mid }]<\mathrm{\infty }\mathrm{.}$

The same identity holds prefixwise: for each $0\le t<H$ and every real $g$ integrable under $P_{t+1}^{\pi }$, with $g$ evaluated on the observed prefix,

${\mathbb{E}}_{P_H^{\mu }}[W_{0:t}g]={\mathbb{E}}_{P_H^{\pi }}[g],{\mathbb{E}}_{P_H^{\mu }}[W_{0:t}\mathrm{\mid }g\mathrm{\mid }]<\mathrm{\infty }\mathrm{.}$

Finite MDP, fixed-start trajectory law, target value, behavior propensities, and full trajectory coverage.

Under AC, a stationary policy has finite-prefix atom masses formed from its action probabilities and the shared joint transition/reward law.

Absolute continuity transfers null sets from the behavior measure to the target measure.

Under AC, a sigma-finite signed measure absolutely continuous with respect to a sigma-finite positive measure has a unique almost-everywhere density.

The Radon-Nikodym derivative is the almost-everywhere class of densities.

Radon-Nikodym derivatives satisfy the chain rule along nu << mu << lambda: For sigma-finite measures on a common finite exhaustion, the derivative of $\nu \ll \mu \ll \lambda$ factors as the product of the two derivatives.

Integrating a nonnegative function against a density measure equals integrating its product against the base measure.

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

The Lebesgue integral is linear on integrable real and complex functions.

Sutton and Barto, Reinforcement Learning: An Introduction, 2nd ed.

Jiang and Li, Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

Assume AC for the policy-induced trajectory laws. Input a finite-horizon logged dataset of $n\ge 1$ independent behavior trajectories, a target policy $\pi$, the true behavior propensities $\mu (a\mid s)$, horizon $H$, and discount $0\le \gamma \le 1$. Require full horizon coverage $P_H^{\pi }\ll P_H^{\mu }$. For trajectory $i$, compute ${\rho }_{i,t}=\pi (A_t^i\mid S_t^i)\mathrm{/}\mu (A_t^i\mid S_t^i)$ for $0\le t<H$, and $W_{i,t}={\prod }_{k=0}^t{\rho }_{i,k}$; set $W_{i,-1}=1$. If an observed pair has $\mu (A_t^i\mid S_t^i)=0<\pi (A_t^i\mid S_t^i)$, return status unsupported; if both probabilities are zero, set that ratio to zero. Let $G_i={\sum }_{t=0}^{H-1}{\gamma }^t{R}_{t+1}^i$. Return the ordinary trajectory estimator

${\widehat{J}}_{\mathrm{O}\mathrm{I}\mathrm{S}}=\frac{1}{n}{\sum }_{i=1}^n{W}_{i,H-1}{G}_i,$

the per-decision estimator

${\widehat{J}}_{\mathrm{P}\mathrm{D}\mathrm{I}\mathrm{S}}=\frac{1}{n}{\sum }_{i=1}^n{\sum }_{t=0}^{H-1}{\gamma }^t{W}_{i,t}{R}_{t+1}^i,$

and the self-normalized weighted estimator

${\widehat{J}}_{\mathrm{W}\mathrm{I}\mathrm{S}}=\{\begin{array}{ll}{\displaystyle \frac{\sum _{i=1}^n{W}_{i,H-1}{G}_i}{\sum _{i=1}^n{W}_{i,H-1}},}& {\sum }_{i=1}^n{W}_{i,H-1}>0,\\ 0,& {\sum }_{i=1}^n{W}_{i,H-1}=0.\end{array}$

The procedure specifies estimators; it includes no finite-sample unbiasedness assertion for the self-normalized output.

Finite-horizon trajectory data, behavior propensities, return, and coverage.

The cumulative action-propensity product is the RN density on each finite trajectory prefix.

Sutton and Barto, Reinforcement Learning: An Introduction, 2nd ed.

Jiang and Li, Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

Levine, Kumar, Tucker, and Fu, Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems

Assume AC for the behavior-policy trajectory law. Input a finite-horizon logged dataset with $n\ge 1$ behavior trajectories, a target policy $\pi$, finite real functions ${\widehat{Q}}_t(s,a)$ for $0\le t<H$, and finite nonnegative action-weight multipliers ${\widehat{\rho }}_t(s,a)$ for $0\le t<H$. Hold the functions and multipliers fixed when taking expectation over the evaluation dataset; they may be conditioned on an independent training sample. Define ${\widehat{V}}_H(s)=0$ for every $s$, and for $t=H-1,\dots ,0$ define

${\widehat{V}}_t(s)={\sum }_{a\in A(s)}\pi (a\mid s){\widehat{Q}}_t(s,a)\mathrm{.}$

For each logged trajectory $i$, set ${\widehat{W}}_{i,-1}=1$ and ${\widehat{W}}_{i,t}={\widehat{W}}_{i,t-1}{\widehat{\rho }}_t(S_t^i,A_t^i)$ for $0\le t<H$. Compute

$D_i={\widehat{V}}_0(s_0)+{\sum }_{t=0}^{H-1}{\gamma }^t{\widehat{W}}_{i,t}(R_{t+1}^i+\gamma {\widehat{V}}_{t+1}(S_{t+1}^i)-{\widehat{Q}}_t(S_t^i,A_t^i)),$

and return ${\widehat{J}}_{\mathrm{D}\mathrm{R}}=n^{-1}{\sum }_{i=1}^n{D}_i$. When supplied as propensity ratios, the multipliers have the form ${\widehat{\rho }}_t(s,a)=\pi (a\mid s)\mathrm{/}{\tilde{\mu }}_t(a\mid s)$, with positive denominators on target-positive actions. In the exact-ratio case they equal the target-to-behavior action-likelihood factors $\pi (a\mid s)\mathrm{/}\mu (a\mid s)$; the procedure also permits finite fitted multipliers for the correct-value-model case. The fixed terminal value ${\widehat{V}}_H=0$ is part of the procedure.

The finite-horizon evaluation dataset, target value, and behavior-data law.

Exact behavior propensities yield the finite-prefix target-to-behavior density.

Jiang and Li, Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

Levine, Kumar, Tucker, and Fu, Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems

Assume AC and the finite-horizon dataset conditions with full trajectory coverage $P_H^{\pi }\ll P_H^{\mu }$, true known behavior propensities, and the integrability hypotheses in the dataset definition. Whenever the preceding algorithm returns numerical estimates, all three estimates are finite. Under the behavior-generated law of the $n$ independent trajectories, its unsupported status occurs only on a null event; assign any fixed finite values to the three estimator expressions there. The ordinary trajectory estimator and per-decision estimator then each have expectation $J_H(\pi ;s_0)$. This statement makes no finite-sample unbiasedness claim for the self-normalized weighted estimator.

The fixed-start finite-horizon data law, target value, independent sample, and coverage assumptions.

The OIS and PDIS formulas and their finite-horizon prefix weights.

The full and prefix policy-ratio density identities.

The Axiom of Choice required by the path-law and RN suppliers.

Sutton and Barto, Reinforcement Learning: An Introduction, 2nd ed.

Jiang and Li, Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

Assume AC and the finite-horizon dataset conditions with fixed target policy $\pi$, behavior policy $\mu$, horizon $H$, discount $0\le \gamma \le 1$, and initial state $s_0$. Hold the finite functions ${\widehat{Q}}_t$ and multipliers ${\widehat{\rho }}_t$ fixed when taking expectation over the evaluation trajectories. Set ${\widehat{V}}_H(s)=0$ and ${\widehat{V}}_t(s)={\sum }_{a\in A(s)}\pi (a\mid s){\widehat{Q}}_t(s,a)$. Let

$D(\tau )={\widehat{V}}_0(s_0)+{\sum }_{t=0}^{H-1}{\gamma }^t{\widehat{W}}_{0:t}(\tau )(R_{t+1}+\gamma {\widehat{V}}_{t+1}(S_{t+1})-{\widehat{Q}}_t(S_t,A_t)),{\widehat{W}}_{0:t}={\prod }_{k=0}^t{\widehat{\rho }}_k(S_k,A_k)\mathrm{.}$

For a dataset of $n$ independent evaluation trajectories, let ${\widehat{J}}_{\mathrm{D}\mathrm{R}}=n^{-1}{\sum }_{i=1}^{n}D({\tau }_i)$. Then $\mathbb{E}[{\widehat{J}}_{\mathrm{D}\mathrm{R}}]=J_H(\pi ;s_0)$ under either of these separate conditions:

1. The full target trajectory law is absolutely continuous with respect to the behavior trajectory law, and every multiplier is the correct action ratio ${\widehat{\rho }}_t(s,a)=\pi (a\mid s)\mathrm{/}\mu (a\mid s)$ on every behavior-positive state-action pair reachable before time $H$; the ratio is $0$ when $\pi (a\mid s)=0<\mu (a\mid s)$. No correctness assumption is imposed on the functions ${\widehat{Q}}_t$.

2. For every $0\le t<H$, state $s$, and action $a$, the value model is exact:

   ${\widehat{Q}}_t(s,a)=Q_t^{\pi }(s,a):={\sum }_{s^{\mathrm{\prime }}\in S}{\sum }_{r\in \mathcal{R}}p(s^{\mathrm{\prime }},r\mid s,a)(r+\gamma V_{t+1}^{\pi }(s^{\mathrm{\prime }})),V_H^{\pi }(s)=0,V_t^{\pi }(s)={\sum }_{a\in A(s)}\pi (a\mid s)Q_t^{\pi }(s,a),$

   so ${\widehat{V}}_t=V_t^{\pi }$ at every step, including the zero terminal value. This branch requires no trajectory coverage and no correctness assumption on the fixed finite multipliers. If neither exact condition holds, this theorem asserts no unbiasedness.

The finite-horizon doubly robust score and its zero terminal-value convention.

The finite-horizon path law, target value, and behavior-data sampling convention.

Exact prefix density change under correct action ratios.

The shared transition/reward law conditional on each finite history.

AC is used for path-law, RN-density, and conditional-expectation existence.

Jiang and Li, Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

Levine, Kumar, Tucker, and Fu, Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems

Under the finite-horizon data assumptions above, full trajectory-law coverage, true known behavior propensities, and integrable weighted returns, the ordinary trajectory and per-decision importance-sampling estimators are unbiased for the expected return of the fixed target policy. In this finite trajectory setting their finite numerical outputs have finite variance, but they do not provide a variance bound uniform over behavior policies, a confidence bound, or a guarantee that the target policy outperforms the behavior policy. For each fixed model, horizon, and sample size, the trajectory dataset space is finite; after any fixed finite assignment on the behavior-null unsupported event, each estimator has finitely many finite values, so its second moment and variance are finite. Product weights can vary exponentially with horizon; self-normalization and clipping can change finite-sample expectations. With missing coverage, two environments can agree on every logged trajectory and assign different values to an unobserved action. A conservative policy constraint explicitly restricts candidate policies, for example by limiting their divergence from the behavior policy; a pessimistic value adjustment lowers predicted values for poorly supported actions. These choices can reduce unsupported action selection but can also limit policy improvement, and they are not by themselves safety guarantees. Model exploitation occurs when optimization selects state-action pairs where an approximate dynamics or value model overpredicts return; optimizing such errors can worsen real performance. A finite-sample safety or performance guarantee needs its own assumptions and error bounds.

The fixed-data, target-policy, behavior-policy, and full-coverage conventions.

OIS, PDIS, and the self-normalized WIS procedure.

The finite-horizon doubly robust residual estimator.

A finite example showing that missing behavior support can prevent value identification.

Under finite-horizon coverage and the stated behavior-data assumptions, OIS and PDIS are unbiased.

Sutton and Barto, Reinforcement Learning: An Introduction, 2nd ed.

Jiang and Li, Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

Levine, Kumar, Tucker, and Fu, Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems