Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluation

# Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluation
Source: [https://arxiv.org/html/2608.24146](https://arxiv.org/html/2608.24146)
Shuze Daniel LiuAffiliation:Massachusetts Institute of TechnologyEmail:[shuzel@mit\.edu](mailto:)Affiliation:Purdue UniversityEmail:[daniel\.liu@purdue\.edu](mailto:)Licheng LuoAffiliation:University of California, RiversideEmail:[lichengl@ucr\.edu](mailto:)Rohan ChandraAffiliation:University of VirginiaEmail:[rohanchandra@virginia\.edu](mailto:)Nan JiangAffiliation:University of Illinois Urbana\-ChampaignEmail:[nanjiang@illinois\.edu](mailto:)Shangtong ZhangAffiliation:University of VirginiaEmail:[shangtong@virginia\.edu](mailto:)

###### Abstract

In reinforcement learning policy evaluation, classic on\-policy methods often suffer from high variance when estimating policy performance\. To mitigate this issue,behavior policy searchhas been proposed to learn data\-collecting policies tailored to reduce online evaluation variance\. However, these approaches do not account for uncertainties in the transition functions\. In practice, simulator transitions often differ from the real world due to modeling errors or approximation limitations\. As a result, behavior policies trained in simulation may still yield high variance when deployed in real environments, leading to costly reliance on real\-world evaluation samples\. In this work, we propose a double\-loop gradient\-based algorithm for learning behavior policies that are both efficient and robust to transition uncertainty\. Theoretically, we derive novel transition\-variance gradient expressions and establish global convergence guarantees for the algorithm\. Numerically, we demonstrate that our method is less sensitive to transition perturbations than existing approaches, providing supportive evidence for its practical utility\.

## 1Introduction

Reinforcement learning \(RL\) has achieved remarkable success in recent years across domains such as robotics, healthcare, recommendation systems, and natural language processing\([Mnih et al\., 2015](https://arxiv.org/html/2608.24146#bib.bib56);[Silver et al\., 2017](https://arxiv.org/html/2608.24146#bib.bib24);[Jumper et al\., 2021](https://arxiv.org/html/2608.24146#bib.bib46);[Xie et al\., 2026](https://arxiv.org/html/2608.24146#bib.bib11);[Liu et al\., 2026c](https://arxiv.org/html/2608.24146#bib.bib13);[Liu et al\., 2026d](https://arxiv.org/html/2608.24146#bib.bib15)\)\. A central component in these advances is policy evaluation, the task of estimating the performance of a policy\. The most direct approach is the on\-policy Monte Carlo method, which collects trajectories from the target policy and estimates its value by averaging the observed returns\. Although conceptually simple and widely used, this method often suffers from high evaluation variance, limiting the reliability of the resulting estimates\.

To improve efficiency, a growing body of work has investigated learning a separate data\-collecting behavior policy to reduce evaluation variance via off\-policy evaluation\([Hanna et al\., 2017](https://arxiv.org/html/2608.24146#bib.bib49);[Zhong et al\., 2022](https://arxiv.org/html/2608.24146#bib.bib48);[Liu and Zhang, 2024](https://arxiv.org/html/2608.24146#bib.bib47);[Liu et al\., 2025a](https://arxiv.org/html/2608.24146#bib.bib41);[Liu, 2025](https://arxiv.org/html/2608.24146#bib.bib10)\)\. This line of research, known as behavior policy search \(BPS\), optimizes a variance\-reducing behavior policy so that the collected trajectories yield more informative evaluations\. With an appropriately chosen behavior policy, BPS has been shown to achieve lower variance than naive on\-policy evaluation\. By contrast, in the standard formulation of off\-policy evaluation \(OPE\), the data are assumed to be pre\-logged by a fixed behavior policy and the focus is on designing improved estimators\. In comparison, BPS explicitly optimizes the behavior policy itself to reduce variance and is broadly applicable across different OPE estimators\.

Despite this progress, existing BPS methods generally optimize behavior policies under prespecified transition functions, without accounting for underlying uncertainties\. In practice, the true transition functions often deviate from the assumed model due to approximation errors, adversarial perturbations, or partial observability\. Such discrepancies can compromise evaluation reliability: a behavior policy optimized under simulator transition may still yield high variance when deployed in the real environment\. Consequently, prior methods may continue to require a large number of costly real\-world samples to achieve accurate evaluation\.

To address these two challenges—variance reduction and transition mismatch—we propose anefficient and robust policy evaluationframework that explicitly accounts for transition uncertainty\. Our method formulates BPS as a minimax optimization problem, where an adversarial transition model seeks to maximize the evaluation variance while the behavior policy is optimized to minimize it\. Our contributions are summarized as follows:\(1\)We introduce a novel adversarial framework for robust behavior policy search in policy evaluation \(Section[3\.3](https://arxiv.org/html/2608.24146#S3.SS3)\);\(2\)We derive analytical transition\-gradient expressions for both on\-transition and off\-transition settings, and provide convergence guarantees for the inner\-loop adversarial optimization \(Section[4](https://arxiv.org/html/2608.24146#S4)\);\(3\)We propose a double\-loop robust gradient algorithm and provide global convergence guarantee for variance\-minimizing behavior policy search \(Section[5](https://arxiv.org/html/2608.24146#S5)\);\(4\)We numerically show that our method is less sensitive to transition perturbations than existing approaches \(Section[6](https://arxiv.org/html/2608.24146#S6)\), verifying the utility of our theoretical results\.

## 2Related Work

Behavior Policy Search\.Behavior policy search \(BPS\) reduces evaluation variance by optimizing the data\-collecting policy\.[Hanna et al\. \(2017\)](https://arxiv.org/html/2608.24146#bib.bib49)formulate this as an optimization problem, using stochastic gradient descent to outperform standard Monte Carlo methods\.[Zhong et al\. \(2022\)](https://arxiv.org/html/2608.24146#bib.bib48)extend this via adaptive behavior policies that prioritize under\-sampled regions\. However, these approaches overlook transition uncertainty; consequently, behavior policies optimized in simulation may still induce high variance under real\-world dynamics\. In contrast, our method explicitly models transition uncertainty to ensure the learned behavior policy remains effective even under perturbed dynamics\.

[Liu and Zhang \(2024\)](https://arxiv.org/html/2608.24146#bib.bib47)also study the variance reducing problem, deriving a closed\-form, offline\-learnable behavior policy with theoretical guarantees\. However, their formulation relies on pre\-logged data with prespecified and fixed transition probabilities, and cannot adapt when these probabilities shift at deployment, leaving it vulnerable to modeling errors and sim\-to\-real mismatches\. Our method fills this gap by integrating adversarial transition modeling into behavior policy search, combining efficiency with robustness to transition shifts\. Similarly, while[Russo and Pacchiano \(2025\)](https://arxiv.org/html/2608.24146#bib.bib16)optimize adaptive exploration for multi\-policy evaluation, they assume fixed dynamics; in contrast, our framework proactively targets robustness to adversarial transition shifts\.

Robust Policy Evaluation\.Recent work has begun addressing robustness in reinforcement learning policy evaluation\. For example,[Katdare et al\. \(2023\)](https://arxiv.org/html/2608.24146#bib.bib26)and[Voloshin et al\. \(2021\)](https://arxiv.org/html/2608.24146#bib.bib25)propose techniques to improve robustness under simulator mismatch via estimator modification or robust model learning\. However, these methods either rely on access to real\-world data or focus on minimizing worst\-case prediction errors, and do not directly address the high\-variance issue central to policy evaluation\. In contrast, our work proactively reduces variance by designing behavior policies that are robust to adversarial transition shifts, without requiring target\-environment data\.

While robust MDP \(RMDP\) frameworks\([Iyengar, 2005](https://arxiv.org/html/2608.24146#bib.bib40);[Nilim and El Ghaoui, 2005](https://arxiv.org/html/2608.24146#bib.bib23)\)also consider robustness under transition uncertainty, they are typically designed for reward maximization and rely on linear programming techniques\. These approaches \(e\.g\.,[Wang et al\. \(2023a\)](https://arxiv.org/html/2608.24146#bib.bib42);[Wang et al\. \(2024\)](https://arxiv.org/html/2608.24146#bib.bib44)\) do not apply to our setting, where the goal is to minimize the variance of policy value estimators, a fundamentally non\-linear objective\. We fill this gap by proposing a novel adversarial transition variance gradient method that explicitly targets variance reduction under transition uncertainty\.

## 3Background

### 3\.1Markov Decision Process

We study a finite\-horizon Markov Decision Process \(MDP,[Puterman \(2014\)](https://arxiv.org/html/2608.24146#bib.bib50)\) with finite state space𝒮\\mathcal\{S\}and finite action space𝒜\\mathcal\{A\}\. For a finite set𝒳\\mathcal\{X\}, we denote the probability simplex over𝒳\\mathcal\{X\}byΔ\(𝒳\)≐\{p:𝒳→\[0,1\]∣∑x∈𝒳p\(x\)=1\}\\Delta\(\\mathcal\{X\}\)\\doteq\\\{p:\\mathcal\{X\}\\to\[0,1\]\\mid\\sum\_\{x\\in\\mathcal\{X\}\}p\(x\)=1\\\}\. The MDP consists of a transition probability functionp:𝒮×𝒜→Δ⁡\(𝒮\)p:\\mathcal\{S\}\\times\\mathcal\{A\}\\to\\Delta\(\\mathcal\{S\}\), a reward functionr:𝒮×𝒜→\[0,1\]r:\\mathcal\{S\}\\times\\mathcal\{A\}\\to\[0,1\], an initial state distributionp0∈Δ⁡\(𝒮\)p\_\{0\}\\in\\Delta\(\\mathcal\{S\}\), and a fixed horizon lengthTT\. To simplify notation, we consider the undiscounted setting without loss of generality\. Our method naturally applies to the discounted setting as long as the horizon is fixed and finite\([Puterman, 2014](https://arxiv.org/html/2608.24146#bib.bib50)\)\.

A policyπ:𝒮→Δ⁡\(𝒜\)\\pi:\\mathcal\{S\}\\to\\Delta\(\\mathcal\{A\}\)maps each state to a probability distribution over actions\. We consider the parameterized policiesπθ\\pi\_\{\\theta\}, where the parametersθ∈Θ\\theta\\in\\Thetais a vector withΘ⊆ℝn\\Theta\\subseteq\\mathbb\{R\}^\{n\}for some constantnn\. Likewise, we parameterize the transition functionpω:𝒮×𝒜→Δ⁡\(𝒮\)p\_\{\\omega\}:\\mathcal\{S\}\\times\\mathcal\{A\}\\to\\Delta\(\\mathcal\{S\}\)by a parameterω∈Ω\\omega\\in\\Omega, whereΩ⊆ℝm\\Omega\\subseteq\\mathbb\{R\}^\{m\}and is compact\. Unless stated otherwise, all norms used in this work are Euclidean \(i\.e\.,‖x‖=‖x‖2\\norm\{x\}=\\norm\{x\}\_\{2\}\)\.

The MDP process begins at time step00, where an initial stateS0S\_\{0\}is sampled fromp0p\_\{0\}\. At each time stept∈\[T−1\]t\\in\[T\-1\], an actionAtA\_\{t\}is sampled based onπ\(⋅∣St\)\\pi\(\\cdot\\mid S\_\{t\}\)\. Then, a finite rewardRt\+1≐r⁡\(St,At\)R\_\{t\+1\}\\doteq r\(S\_\{t\},A\_\{t\}\)is given by the environment and a successor stateSt\+1S\_\{t\+1\}is obtained based onp\(⋅∣St,At\)p\(\\cdot\\mid S\_\{t\},A\_\{t\}\)\. AfterTTsteps, the agent’s interaction with the environment terminates\. If the agent reaches any terminal state before time stepTT, it stays there and receives zero reward\.

We useh≐\{S0,A0,R1,S1,A1,…​ST−1,AT−1,RT\}h\\doteq\\\{S\_\{0\},A\_\{0\},R\_\{1\},S\_\{1\},A\_\{1\},\.\.\.S\_\{T\-1\},A\_\{T\-1\},R\_\{T\}\\\}to denote the trajectory of this MDP\. We then define thereturnofhhasg⁡\(h\)≐∑t=0T−1Rt\+1g\(h\)\\doteq\\sum\_\{t=0\}^\{T\-1\}R\_\{t\+1\}\. For any policy, we have a distribution over the trajectory asPr⁡\(H=h\|π\)\\mathrm\{Pr\}\(H=h\|\\pi\), whereHHis a random variable used to denote the trajectory\. Lastly, we define thevalueof a policy asv⁡\(π\)≐𝔼H∼π​\[g⁡\(H\)\]v\(\\pi\)\\doteq\\mathbb\{E\}\_\{H\\sim\\pi\}\[g\(H\)\]\. To simplify notations, we also defineℓpω≐∑t=0T−1log⁡\(pω​\(St\+1\|St,At\)\)\\textstyle\\ell\_\{p\_\{\\omega\}\}\\doteq\\sum\_\{t=0\}^\{T\-1\}\\log\(p\_\{\\omega\}\(S\_\{t\+1\}\|S\_t,A\_t\)\)\.

### 3\.2Variance Reduction in Policy Evaluation

We consider the task of reinforcement learning policy evaluation, where the goal is to estimate the value of an interested policyπe\\pi\_\{e\}, called thetarget policy\. The traditionalon\-policyMonte Carlo \(MC\) method estimatesv⁡\(πe\)v\(\\pi\_\{e\}\)by repeatedly executing the target policyπe\\pi\_\{e\}online and averaging the observed returns\. That is,MC⁡\(πe,H\)≐1n​∑i=0n−1g⁡\(Hi\)\\mathrm\{MC\}\(\\pi\_\{e\},H\)\\doteq\\frac\{1\}\{n\}\\sum\_\{i=0\}^\{n\-1\}g\(H\_\{i\}\)for allHi∼πeH\_\{i\}\\sim\\pi\_\{e\}\. However, in practice, this straightforward method can induce high evaluation variance, leading to less reliable results\([Liu and Zhang, 2024](https://arxiv.org/html/2608.24146#bib.bib47);[Liu et al\., 2025b](https://arxiv.org/html/2608.24146#bib.bib27);[Liu et al\., 2025a](https://arxiv.org/html/2608.24146#bib.bib41);[Chen et al\., 2025](https://arxiv.org/html/2608.24146#bib.bib28)\)\.

To mitigate this challenge, recent work has proposed to useoff\-policyevaluation method to reduce variance, where we execute a different policyπθ\\pi\_\{\\theta\}\(thebehavior policy\), to collect data\. For wide applicability, we consider a general off\-policy estimatorOPE⁡\(πe,πθ,H\)\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\), which estimates the value ofπe\\pi\_\{e\}using trajectoriesHHfromπθ\\pi\_\{\\theta\}\. A standard example is importance sampling,IS⁡\(πe,πθ,H\)≐g⁡\(H\)​∏t=0T−1πe​\(At\|St\)πθ​\(At\|St\)\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\\doteq g\(H\)\\prod\_\{t=0\}^\{T\-1\}\\tfrac\{\\pi\_\{e\}\(A\_\{t\}\|S\_\{t\}\)\}\{\\pi\_\{\\theta\}\(A\_\{t\}\|S\_\{t\}\)\}\. Prior work has shown that with a properly designed behavior policyπθ\\pi\_\{\\theta\}, one can achieve lower evaluation variance with an off\-policy estimator than the traditional on\-policy MC method\([Hanna et al\., 2017](https://arxiv.org/html/2608.24146#bib.bib49);[Zhong et al\., 2022](https://arxiv.org/html/2608.24146#bib.bib48)\)\. This is known as theBehavior Policy Search\(BPS\) problem, where we aim to solveminθ∈Θ⁡𝕍H∼πθ​\[OPE⁡\(πe,πθ,H\)\]\\min\_\{\\theta\\in\\Theta\}\\mathbb\{V\}\_\{H\\sim\\pi\_\{\\theta\}\}\\left\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\\right\]\.

### 3\.3Robust Behavior Policy Search

Standard behavior policy search methods typically assume fixed transition probabilities, but in practice there are often discrepancies between simulators and real environments\. After learning a variance\-reducing behavior policy in simulation, practitioners typically deploy it to evaluate the target policy in the real system\. However, becauserobustness to dynamics shiftsis not considered during the behavior policy search phase, the resulting policy may still induce high variance when collecting real\-world data\. Consequently, achieving reliable evaluation often requires a large amount of costly real\-world samples, motivating a robustness\-aware formulation\.

To address this, we formulate the robust behavior policy search problem as a minimax optimization:

minθ∈Θ⁡maxω∈Ω​𝕍H∼pω,πθ​\[OPE⁡\(πe,πθ,H\)\],\\displaystyle\\min\_\{\\theta\\in\\Theta\}\\max\_\{\\omega\\in\\Omega\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\left\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\\right\],\(1\)where the inner maximization identifies worst\-case transition perturbations, and the outer minimization seeks a behavior policy that mitigates this adversarial effect\. Such min–max formulations are standard in the robust RL literature for modeling adversarial dynamics\([Katdare et al\., 2023](https://arxiv.org/html/2608.24146#bib.bib26);[Voloshin et al\., 2021](https://arxiv.org/html/2608.24146#bib.bib25)\)\. Following standard practice in robust RL\([Iyengar, 2005](https://arxiv.org/html/2608.24146#bib.bib40);[Nilim and El Ghaoui, 2005](https://arxiv.org/html/2608.24146#bib.bib23);[Ho et al\., 2021](https://arxiv.org/html/2608.24146#bib.bib37);[Wang et al\., 2023a](https://arxiv.org/html/2608.24146#bib.bib42)\), our robustness guarantees are defined with respect to a user\-specified transition uncertainty set, enabling practitioners to encode transition uncertainties appropriate to their application\.

To further analyze the min\-max problem in \([1](https://arxiv.org/html/2608.24146#S3.E1)\), we can write it as the following equivalent problem

minθ∈Θ\{Φ\(θ\)≐maxω∈Ω𝕍H∼pω,πθ\[OPE\(πe,πθ,H\)\]\},\\displaystyle\\min\_\{\\theta\\in\\Theta\}\\\{\\Phi\(\\theta\)\\doteq\\max\_\{\\omega\\in\\Omega\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]\\\},\(2\)which minimizes the worst\-case evaluation variance\([Jin et al\., 2020](https://arxiv.org/html/2608.24146#bib.bib38)\)\. Notably, the functionΦ\\Phiis not differentiable, and is neither convex nor concave\. Thus, we are unable to solve the problem through direct gradient descent on the functionΦ\\Phi, which motivates our double\-loop approach \(Algorithm[2](https://arxiv.org/html/2608.24146#alg2)\) in Section[5](https://arxiv.org/html/2608.24146#S5)with global convergence guarantee\.

## 4Solving the Inner Loop

In this section, we study the inner loop of the optimization problem \([1](https://arxiv.org/html/2608.24146#S3.E1)\), which identifies adversarial dynamics that maximize evaluation variance\. We derive analytical gradient expressions of the variance with respect to the transition probability, considering both*on\-transition*and*off\-transition*cases, in analogy to on\-policy and off\-policy settings\. In the on\-transition case, the simulator transition can be modified, so trajectories are sampled directly from the evolvingpωp\_\{\\omega\}at each iteration\. In the off\-transition case, the simulator transition is fixed atpω0p\_\{\\omega\_\{0\}\}, and trajectories are collected under this fixed transition probability while reweighted toward the targetpωp\_\{\\omega\}\. We introduce Algorithm[1](https://arxiv.org/html/2608.24146#alg1), which adaptspωp\_\{\\omega\}to maximize evaluation variance, serving as the adversarial player against the robust behavior policyπθ\\pi\_\{\\theta\}\(Section[5](https://arxiv.org/html/2608.24146#S5)\)\. We provide theoretical convergence guarantees for this algorithm\. To the best of our knowledge, this is the first work to develop adversarial transition\-gradient methods for variance objectives in reinforcement learning\.

### 4\.1On\-Transition Gradient of the Variance

We begin with theon\-transitioncase, analogous to the on\-policy setting, where the simulator transition can be directly modified to follow the target transitionpωp\_\{\\omega\}at each iteration\. Given a fixed behavior policyπθ\\pi\_\{\\theta\}, we look for the variance\-maximizing adversarial transitionpωp\_\{\\omega\}\. Formally, we need to solve

maxω∈Ω⁡𝕍H∼pω,πθ​\[OPE⁡\(πe,πθ,H\)\]\.\\displaystyle\\textstyle\\max\_\{\\omega\\in\\Omega\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\left\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\\right\]\.\(3\)In the following theorem, we give a gradient expression of the evaluation variance\. Importantly, this analytical form is general and applies to any off\-policy evaluation estimator, forming the foundation of our transition\-gradient method\.

###### Theorem 4\.1\(Transition Gradient of the Variance\)\.

For a fixed behavior policyπθ\\pi\_\{\\theta\},

∂∂ω​𝕍H∼pω,πθ​\[OPE⁡\(πe,πθ,H\)\]=\\displaystyle\\textstyle\\frac\{\\partial\}\{\\partial\\omega\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]=𝔼H∼pω,πθ​\[OPE​\(πe,πθ,H\)2​∂∂ω​ℓpω\]\\displaystyle\\textstyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\\!\\quantity\[\\\!\\OPE\(\\pi\_e, \\pi\_\\theta,H\)^2\\gradomega\\ell\_\{p\_\\omega\}\]\(4\)−\\displaystyle\-2​𝔼H∼pω,πθ​\[OPE⁡\(πe,πθ,H\)\]​𝔼H∼pω,πθ​\[OPE⁡\(πe,πθ,H\)​∂∂ω​ℓpω\]\.\\displaystyle 2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\\!\[\\mathrm\{OPE\}\(\\\!\\pi\_\{e\},\\pi\_\{\\theta\},H\\\!\)\\\!\]\\textstyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\\!\\quantity\[\\\!\\OPE\(\\\!\\pi\_e, \\pi\_\\theta, H\\\!\)\\gradomega\\ell\_\{p\_\\omega\}\\\! \]\.\(5\)

Its proof is in Appendix[A\.2](https://arxiv.org/html/2608.24146#A1.SS2)\. This gradient expression is in expectation forms and can be estimated unbiasedly from sampled trajectories without additional structural assumptions on the OPE estimator\. Building on Theorem[4\.1](https://arxiv.org/html/2608.24146#S4.Thmtheorem1), we now present the On\-transition Variance Gradient method in Algorithm[1](https://arxiv.org/html/2608.24146#alg1)\. We instantiate our algorithm with the importance sampling estimator \(IS\), but our framework is ready to accommodate any off\-policy evaluation estimator\.

To discuss the convergence property of Algorithm[1](https://arxiv.org/html/2608.24146#alg1), we impose the standard Robbins\-Monro step\-size condition∑i=0∞αi=∞​and​∑i=0∞αi2<∞\\textstyle\\sum\_\{i=0\}^\{\\infty\}\\alpha\_\{i\}=\\infty\\text\{ and \}\\sum\_\{i=0\}^\{\\infty\}\\alpha^\{2\}\_\{i\}<\\infty\([Robbins and Monro, 1951](https://arxiv.org/html/2608.24146#bib.bib52);[Liu et al\., 2025c](https://arxiv.org/html/2608.24146#bib.bib17);[Mahadevan et al\., 2026](https://arxiv.org/html/2608.24146#bib.bib14)\)\. We assume the importance sampling ratioπe​\(a\|s\)πθ​\(a\|s\)\\frac\{\\pi\_\{e\}\(a\|s\)\}\{\\pi\_\{\\theta\}\(a\|s\)\}exists and is bounded above for allss,aa, andθ\\theta\([Hanna et al\., 2024](https://arxiv.org/html/2608.24146#bib.bib43)\)\. Besides, we require the transitionpωp\_\{\\omega\}to be twice\-differentiable with respect toω\\omegawith uniformly bounded first\- and second\-order derivatives\. These conditions forpωp\_\{\\omega\}hold, for example, when it is parameterized by a neural network with smooth activations and a softmax output layer, and are commonly adopted in policy gradient literature \(e\.g\.,[Hanna et al\. \(2017\)](https://arxiv.org/html/2608.24146#bib.bib49);[Hanna et al\. \(2024\)](https://arxiv.org/html/2608.24146#bib.bib43)\)\. Then, we have the following lemma for the convergence of Algorithm[1](https://arxiv.org/html/2608.24146#alg1), whose proof is in Appendix[A\.3](https://arxiv.org/html/2608.24146#A1.SS3)\.

###### Lemma 4\.2\(Transition Gradient Convergence\)\.

For a fixed behavior policyπθ\\pi\_\{\\theta\}, Algorithm[1](https://arxiv.org/html/2608.24146#alg1)converges\. That is,𝕍Hi∼pωi,πθ​\[IS⁡\(πe,πθ,Hi\)\]\\mathbb\{V\}\_\{H\_\{i\}\\sim p\_\{\\omega\_\{i\}\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\_\{i\}\)\]converges to a finite value and limi→∞∂∂ω​𝕍Hi∼pωi,πθ​\[IS⁡\(πe,πθ,Hi\)\]=0\\lim\_\{i\\to\\infty\}\\frac\{\\partial\}\{\\partial\\omega\}\\mathbb\{V\}\_\{H\_\{i\}\\sim p\_\{\\omega\_\{i\}\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\_\{i\}\)\]=0\.

Algorithm 1On\-Transition Variance Gradient\.1:Input:an initial transition parameter

ω0\\omega\_\{0\}, a target policy

πe\\pi\_\{e\}, a fixed behavior policy

πθ\\pi\_\{\\theta\}, a number of iteration

nn, a batch size

kk, a step\-size

αi\\alpha\_\{i\}for each

ii
2:Output:a final adversarial transition parameter

ωn\\omega\_\{n\}
3:For all

i∈0,…,n−1i\\in 0,\.\.\.,n\-1do

4:Sample

kktrajectories

H∼πθ,pωiH\\sim\\pi\_\{\\theta\},p\_\{\\omega\_\{i\}\}
5:

ωi\+1=ωi\+αik​∑j=1k\(IS​\(πe,πθ,Hj\)2​∑t=0T−1∂∂ω​log⁡\(pωij​\(St\+1\|St,At\)\)\)−8​αik2∑j=1k2IS\(πe,πθ,Hj\)∑j=k2\+1k\(IS⁡\(πe,πθ,Hj\)​∑t=0T−1∂∂ω​log⁡\(pωij​\(St\+1\|St,At\)\)\)\.\\begin\{aligned\} &\\omega\_\{i\+1\}=\\omega\_\{i\}\\textstyle\+\\frac\{\\alpha\_\{i\}\}\{k\}\\sum\_\{j=1\}^\{k\}\\quantity\(\\IS\(\\pi\_e,\\pi\_\\theta,H^j\)^2\\sum\_\{t=0\}^\{T\-1\}\\gradomega\\log\(p^j\_\{\\omega\_i\}\(S\_\{t\+1\}\|S\_t,A\_t\)\)\)\\\\ &\\textstyle\-\\frac\{8\\alpha\_\{i\}\}\{k^\{2\}\}\\sum\_\{j=1\}^\{\\frac\{k\}\{2\}\}\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H^\{j\}\)\\sum\_\{j=\\frac\{k\}\{2\}\+1\}^\{k\}\\quantity\(\\IS\(\\pi\_e, \\pi\_\\theta,H^j\)\\sum\_\{t=0\}^\{T\-1\}\\gradomega\\log\(p^j\_\{\\omega\_i\}\(S\_\{t\+1\}\|S\_t,A\_t\)\) \)\.\\end\{aligned\}
6:End for

7:Return:

ωn\\omega\_\{n\}

In practice, although discrepancies often exist between the transition probability in the deployment environment and the original simulator, the simulator typically remains a reasonable approximation\. Thus, to ensure the learned adversarial transition remains realistic rather than overly pessimistic, we also offer an optional Kullback–Leibler \(KL\) divergence penalty that discourages large deviations betweenpωp\_\{\\omega\}and the initial simulator transitionpω0p\_\{\\omega\_\{0\}\}\([Tang et al\., 2025](https://arxiv.org/html/2608.24146#bib.bib9);[Zhang et al\., 2026](https://arxiv.org/html/2608.24146#bib.bib5);[Chen et al\., 2026b](https://arxiv.org/html/2608.24146#bib.bib6);[Chen and Zhang, 2026a](https://arxiv.org/html/2608.24146#bib.bib8);[Chen and Zhang, 2026b](https://arxiv.org/html/2608.24146#bib.bib7)\)\. Given a behavior policyπθ\\pi\_\{\\theta\}, we consider the following inner\-loop optimization problem under KL regularization:

maxω∈Ω\\displaystyle\\max\_\{\\omega\\in\\Omega\}𝕍H∼pω,πθ\[OPE\(πe,πθ,H\)\]−ηKL\(Pr⁡\(H\|pω\)∥Pr⁡\(H\|pω0\)\),\\displaystyle\\mathbb\{V\}\_\{H\\\!\\sim\\\!p\_\{\\omega\}\\\!,\\\!\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\\!\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]\-\\eta\{\\text\{\\rm KL\}\}\(\\Pr\(\\\!H\|p\_\{\\omega\}\\\!\)\\\|\\Pr\(\\\!H\|p\_\{\\omega\_0\}\\\!\)\\\!\),\(6\)whereη\>0\\eta\>0is the regularization coefficient and the KL\-divergence term is defined asKL\(Pr⁡\(H\|pω\)∥Pr⁡\(H\|pω0\)\)≐𝔼H∼pω,πθ\[log⁡Pr⁡\(H\|pω\)Pr⁡\(H\|pω0\)\]\.\\textstyle\{\\text\{\\rm KL\}\}\(\\Pr\(\\\!H\|p\_\{\\omega\}\)\\\|\\Pr\(\\\!H\|p\_\{\\omega\_0\}\)\)\\\!\\doteq\\\!\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\quantity\[ \\\!\\log\\frac\{\\Pr\(H\|p\_\{\\omega\}\)\}\{\\Pr\(H\|p\_\{\\omega\_0\}\)\}\\\!\]\.We provide the gradient expression of this regularized optimization problem in the following theorem\.

###### Theorem 4\.3\(Transition Gradient of Variance with KL\)\.

For a fixed behavior policyπθ\\pi\_\{\\theta\}and a regularization coefficientη\>0\\eta\>0,

∂∂ω𝕍H∼pω,πθ\[OPE\(πe,πθ,H\)\]−ηKL\(Pr⁡\(H\|pω\)∥Pr⁡\(H\|pω0\)\)=𝔼H∼pω,πθ\[OPE​\(πe,πθ,H\)2​∂∂ω​ℓpω\]\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\\!\\mathbb\{V\}\_\{H\\\!\\sim\\\!p\_\{\\omega\}\\\!,\\\!\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\\!\\pi\_\{e\},\\pi\_\{\\theta\},H\\\!\)\]\\\!\\\!\-\\\!\\\!\\eta\{\\text\{\\rm KL\}\}\(\\Pr\(\\\!H\|p\_\{\\omega\}\\\!\)\\\|\\Pr\(\\\!H\|p\_\{\\omega\_0\}\\\!\)\\\!\)=\\textstyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\\!\\quantity\[\\OPE\(\\pi\_e, \\pi\_\\theta,H\)^2\\gradomega\\ell\_\{p\_\\omega\}\]\(7\)−\\displaystyle\\vskip\-7\.5pt\-2​𝔼H∼pω,πθ​\[OPE⁡\(πe,πθ,H\)\]​𝔼H∼pω,πθ​\[OPE⁡\(πe,πθ,H\)​∂∂ω​ℓpω\]−η​𝔼H∼pω,πθ​\[\(∂∂ω​ℓpω\)​\(1\+ℓpω−ℓpω0\)\]\.\\displaystyle 2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\\!\[\\mathrm\{OPE\}\(\\\!\\pi\_\{e\},\\pi\_\{\\theta\},H\\\!\)\\\!\]\\textstyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\\!\\quantity\[\\\!\\OPE\(\\\!\\pi\_e, \\pi\_\\theta, H\\\!\)\\gradomega\\ell\_\{p\_\\omega\}\\\! \\\!\]\\textstyle\-\\eta\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\left\[\\quantity\(\\gradomega\\ell\_\{p\_\\omega\}\)\\quantity\(1\+\\ell\_\{p\_\\omega\}\\\!\-\\\!\\ell\_\{p\_\{\\omega\_0\}\}\)\\right\]\.\(8\)

Its proof is in Appendix[A\.4](https://arxiv.org/html/2608.24146#A1.SS4)\. This regularization balances robustness with realism, ensuring that the learned adversary remains close to plausible dynamics\.

### 4\.2Off\-Transition Gradient of the Variance

In theoff\-transitioncase, analogous to the off\-policy setting, simulator transitions are fixed atpω0p\_\{\\omega\_\{0\}\}and may differ from the target transitionpωp\_\{\\omega\}\. This situation arises naturally when using black\-box simulators that permit data collection but do not allow modifying transition probabilities \(e\.g\.,[Komorowski et al\. \(2018\)](https://arxiv.org/html/2608.24146#bib.bib29)\)\. In this case, we introduce a transition importance sampling ratio to reweight the collected trajectories, mirroring the familiar correction used in off\-policy evaluation for policies\. For a general off\-policy estimator OPE, we overload the notation as

OPE⁡\(πe,πθ,pω,H\)≐∏t=0T−1pω​\(St\+1\|St,At\)∏t=0T−1pω0​\(St\+1\|St,At\)​OPE​\(πe,πθ,H\)\.\\displaystyle\\textstyle\\mathrm\{OPE\}\(\\\!\\pi\_\{e\},\\pi\_\{\\theta\},p\_\{\\omega\},H\\\!\)\\\!\\doteq\\\!\\textstyle\\frac\{\\prod\_\{t=0\}^\{T\-1\}p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\}\{\\prod\_\{t=0\}^\{T\-1\}p\_\{\\omega\_\{0\}\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\}\\mathrm\{OPE\}\(\\\!\\pi\_\{e\},\\pi\_\{\\theta\},\\\!H\\\!\)\.\(9\)We omit the inputpω0p\_\{\\omega\_\{0\}\}inOPE⁡\(πe,πθ,pω,H\)\\textstyle\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},p\_\{\\omega\},H\)to simplify notations\. Similar to Theorem[4\.1](https://arxiv.org/html/2608.24146#S4.Thmtheorem1), we first give an analytical gradient expression of the evaluation variance\.

###### Theorem 4\.4\(Off\-Transition Gradient of Variance\)\.

Whenpω≠pω0p\_\{\\omega\}\\neq p\_\{\\omega\_\{0\}\}, for a fixed behavior policyπθ\\pi\_\{\\theta\},

∂∂ω​𝕍H∼pω0,πθ​\[OPE⁡\(πe,πθ,pω,H\)\]=2​𝔼H∼pω0,πθ​\[OPE2​\(πe,πθ,pω,H\)​∂∂ω​ℓpω\]\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},p\_\{\\omega\},H\)\]=\\textstyle 2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\\quantity\[\\mathrm\{OPE\}^2\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\)\\gradomega\\ell\_\{p\_\\omega\} \]\(10\)−2​𝔼H∼pω0,πθ​\[OPE⁡\(πe,πθ,pω,H\)\]​𝔼H∼pω0,πθ​\[OPE⁡\(πe,πθ,pω,H\)​∂∂ω​ℓpω\]\.\\displaystyle\\textstyle\-2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\\quantity\[\\mathrm\{OPE\}\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\)\]\\textstyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\\quantity\[\\mathrm\{OPE\}\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\)\\gradomega\\ell\_\{p\_\\omega\} \]\.\(11\)

Its proof is in Appendix[A\.5](https://arxiv.org/html/2608.24146#A1.SS5)\. In the next theorem, we incorporate a KL\-divergence term to penalize large deviations ofpωp\_\{\\omega\}from the simulator’s transitionpω0p\_\{\\omega\_\{0\}\}, with the KL direction chosen so that the expectation aligns with the available sampling distributionpω0p\_\{\\omega\_\{0\}\}\. This design ensures the realism of the learned adversarial transition\.

###### Theorem 4\.5\(Off\-transition Gradient of Variance with KL\)\.

For a fixed behavior policyπθ\\pi\_\{\\theta\}and a regularization coefficientη\>0\\eta\>0,

∂∂ω𝕍H∼pω0,πθ\[OPE\(πe,πθ,pω,H\)\]−ηKL\(Pr⁡\(H\|pω0\)∥Pr⁡\(H\|pω\)\)\\displaystyle\\textstyle\\frac\{\\partial\}\{\\partial\\omega\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},p\_\{\\omega\},H\)\]\-\\eta\{\\text\{\\rm KL\}\}\(\\Pr\(H\|p\_\{\\omega\_0\}\)\\\|\\Pr\(H\|p\_\{\\omega\}\)\)\(12\)=\\displaystyle=2​𝔼H∼pω0,πθ​\[OPE2​\(πe,πθ,pω,H\)​∂∂ω​ℓpω\]−2​𝔼H∼pω0,πθ​\[OPE⁡\(πe,πθ,pω,H\)\]\\displaystyle\\textstyle 2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\\quantity\[\\mathrm\{OPE\}^2\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\)\\gradomega\\ell\_\{p\_\\omega\} \]\\textstyle\-2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\\quantity\[\\mathrm\{OPE\}\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\)\]\(13\)⋅𝔼H∼pω0,πθ​\[OPE⁡\(πe,πθ,pω,H\)​∂∂ω​ℓpω\]−η​𝔼H∼pω0,πθ​\[−∂∂ω​ℓpω\]\.\\displaystyle\\cdot\\textstyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\\quantity\[\\mathrm\{OPE\}\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\)\\gradomega\\ell\_\{p\_\\omega\} \]\-\\textstyle\\eta\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\\quantity\[\-\\gradomega\\ell\_\{p\_\\omega\} \]\.\(14\)

Its proof is in Appendix[A\.6](https://arxiv.org/html/2608.24146#A1.SS6)\. Note that the gradient expression in the off\-transition setting \(Theorem[4\.5](https://arxiv.org/html/2608.24146#S4.Thmtheorem5)\) differs from that in the on\-transition case \(Theorem[4\.3](https://arxiv.org/html/2608.24146#S4.Thmtheorem3)\), reflecting the distinct data sampling mechanisms\.

## 5Solving the Outer Loop

In this section, we propose a behavior policy search \(BPS\) method that is robust to potential discrepancies in the environment\. Specifically, we adopt a policy gradient approach to search for a variance\-reducing behavior policy under an adversarial transition probability\. We first introduce this algorithm, theoretically analyzing its global convergence guarantee\. Then, in Section[6](https://arxiv.org/html/2608.24146#S6), we demonstrate its empirical robustness under perturbed transition probabilities\.

### 5\.1Double\-Loop Robust Variance Gradient

To begin with, recall that in \([1](https://arxiv.org/html/2608.24146#S3.E1)\), our goal is to solve the min\-max objective

minθ∈Θ⁡maxω∈Ω​𝕍H∼pω,πθ​\[OPE⁡\(πe,πθ,H\)\]\.\\displaystyle\\min\_\{\\theta\\in\\Theta\}\\max\_\{\\omega\\in\\Omega\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\left\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\\right\]\.\(15\)In Section[4](https://arxiv.org/html/2608.24146#S4)and Algorithm[1](https://arxiv.org/html/2608.24146#alg1), we present methods to solve the inner maximization problem by performing gradient ascent on the transition parameterω\\omega\. In this section, we focus on performing gradient descent for the variance objective on the policy parameterθ\\theta\. This is also known as thebehavior policy searchproblem in off\-policy evaluation \(OPE\) community\([Hanna et al\., 2017](https://arxiv.org/html/2608.24146#bib.bib49);[Hanna et al\., 2024](https://arxiv.org/html/2608.24146#bib.bib43)\), which aims at finding a variance minimizing behavior policy to collect data through gradient based methods\. In Lemma[5\.1](https://arxiv.org/html/2608.24146#S5.Thmtheorem1), we present the gradient expression for variance with respect to the behavior policy adopted from[Hanna et al\. \(2017\)](https://arxiv.org/html/2608.24146#bib.bib49)\.

###### Lemma 5\.1\(Variance Gradient Expression\)\.

With a fixed transition probabilitypωp\_\{\\omega\},∀θ\\forall\\theta,

∂∂θ𝕍H∼pω,πθ\[IS\(πe,πθ,H\)\]=𝔼H∼pω,πθ\[−IS\(πe,πθ,H\)2∑t=0T−1∂∂θlogπθ\(At\|St\)\]\.\\displaystyle\\textstyle\\frac\{\\partial\}\{\\partial\\theta\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]=\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\-\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)^\{2\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\theta\}\\log\\pi\_\{\\theta\}\(A\_\{t\}\|S\_\{t\}\)\]\.\(16\)

Importantly, this lemma shows that we can estimate the gradient with trajectories sampled from the behavior policyπθ\\pi\_\{\\theta\}\. With this analytical expression, we are now ready to present our double loop algorithm, namedDouble\-Loop Robust Variance Gradient\(DRVG\)\.

Algorithm 2Double\-Loop Robust Variance Gradient \(DRVG\)1:Input:a target policy parameter

θe\\theta\_\{e\}, a number of iteration

nn, a batch size

kk, a step\-size

α\\alpha, tolerance sequence

\{ϵi\}\\\{\\epsilon\_\{i\}\\\}
2:Output:a final robust behavior policy parameter

θ∗\\theta^\{\*\}
3:For all

i=0,…,n−1i=0,\.\.\.,n\-1do

4:

Find​pωi​s\.t\.𝕍H∼pωi,πθi​\[IS⁡\(πe,πθi,H\)\]≥maxpω⁡𝕍H∼pω,πθi​\[IS⁡\(πe,πθi,H\)\]−ϵi\.\\begin\{aligned\} \\text\{Find \}p\_\{\\omega\_\{i\}\}\\text\{ s\.t\. \}\\\!&\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\_\{i\}\},\\pi\_\{\\theta\_\{i\}\}\}\\\!\\left\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{i\}\},H\)\\right\]\\geq&\\max\_\{p\_\{\\omega\}\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\_\{i\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{i\}\},H\)\]\-\\epsilon\_\{i\}\.\\end\{aligned\}
5:

𝒢i=∂∂θ​𝕍H∼pωi,πθi​\[IS⁡\(πe,πθi,H\)\];θi\+1=ProjΘ​\[θi−α​𝒢i\]\\mathcal\{G\}\_\{i\}=\\frac\{\\partial\}\{\\partial\\theta\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\_\{i\}\},\\pi\_\{\\theta\_\{i\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{i\}\},H\)\];\\quad\\theta\_\{i\+1\}=\\mathrm\{Proj\}\_\{\\Theta\}\[\\theta\_\{i\}\-\\alpha\\mathcal\{G\}\_\{i\}\]
6:End for

7:Return:

θ¯≐1n​∑i=0n−1θi\.\\bar\{\\theta\}\\doteq\\frac\{1\}\{n\}\\sum\_\{i=0\}^\{n\-1\}\\theta\_\{i\}\.

The double loop algorithm DRVG iteratively takes gradient steps on the evaluation variance objective to solve the min\-max problem in \([1](https://arxiv.org/html/2608.24146#S3.E1)\)\. Specifically, the inner loop of DRVG returns a worst\-case transition probabilitypωip\_\{\\omega\_\{i\}\}up to a precisionϵi\\epsilon\_\{i\}, which can be obtained through Algorithm[1](https://arxiv.org/html/2608.24146#alg1)\. Such a sequence\{ϵi\}\\\{\\epsilon\_\{i\}\\\}introduces more flexibility to this double\-loop algorithm, allowing for quick policy updates without hurting the global convergence property\. This choice is also adopted by some prior work in the robust MDP community\([Ho et al\., 2021](https://arxiv.org/html/2608.24146#bib.bib37);[Wang et al\., 2023a](https://arxiv.org/html/2608.24146#bib.bib42)\)\.

In the outer loop, DRVG takes aprojected gradient stepto minimize evaluation variance within the feasible parameter setΘ\\Theta\. A well\-known proximal representation of projected gradient in[Bertsekas \(1995\)](https://arxiv.org/html/2608.24146#bib.bib51)isθi\+1∈argminθ∈Θ⟨𝒢i,θ−θi⟩\+12​αi​‖θ−θi‖2=ProjΘ​\[θi−α​𝒢i\],\\theta\_\{i\+1\}\\in\\argmin\_\{\\theta\\in\\Theta\}\\langle\\mathcal\{G\}\_\{i\},\\theta\-\\theta\_\{i\}\\rangle\+\\frac\{1\}\{2\\alpha\_\{i\}\}\\norm\{\\theta\-\\theta\_i\}^\{2\}=\\mathrm\{Proj\}\_\{\\Theta\}\[\\theta\_\{i\}\-\\alpha\\mathcal\{G\}\_\{i\}\],whereProjΘ\\mathrm\{Proj\}\_\{\\Theta\}is the projection operator ontoΘ\\Theta\. In other words, it is identical to taking a plain gradient step, and then using the closest feasible point in Euclidean distance within the feasible set\. Notably, when the feasible setΘ\\Thetais convex, this projected gradient step can be implemented by a convex optimization solver with a quadratic objective\([Wang et al\., 2023a](https://arxiv.org/html/2608.24146#bib.bib42)\)\. Together, this double\-loop algorithm yields a robust behavior policy for off\-policy evaluation under environment uncertainty\.

### 5\.2Global Convergence Analysis

In this subsection, we present the global convergence analysis for Algorithm[2](https://arxiv.org/html/2608.24146#alg2)\. For the widely\-studied policy gradient methods in reinforcement learningpolicy improvement, the objective function is theperformanceof a given target policy\. In ourpolicy evaluationsetting, however, in order to minimize the ultimate online samples needed in the real\-world evaluation, the objective function is theperformance’s variance,

𝕍H∼pω,πθ​\[OPE⁡\(πe,πθ,H\)\]=𝔼H∼pω,πθ​\[OPE​\(πe,πθ,H\)2\]−𝔼H∼pω,πθ​\[OPE⁡\(πe,πθ,H\)\]2\.\\displaystyle\\\!\\mathbb\{V\}\_\{H\\\!\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]\\\!\\\!=\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)^\{2\}\]\\\!\\\!\-\\\!\\\!\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\\\!\]^\{2\}\.\(17\)The non\-linear nature of this variance objective introduces additional difficulties, making the min\-max optimization problem \([1](https://arxiv.org/html/2608.24146#S3.E1)\) nonconvex\-nonconcave, which is widely known to be challenging\([Jin et al\., 2020](https://arxiv.org/html/2608.24146#bib.bib38);[Nouiehed et al\., 2019](https://arxiv.org/html/2608.24146#bib.bib36);[Lin et al\., 2020](https://arxiv.org/html/2608.24146#bib.bib35)\)\. Besides, the objective functionΦ⁡\(θ\)\\Phi\(\\theta\)in the equivalent expression \([2](https://arxiv.org/html/2608.24146#S3.E2)\) is generally non\-differentiable and nonconvex, making the theoretical analysis to our Algorithm[2](https://arxiv.org/html/2608.24146#alg2)even more challenging\. In fact, even without the inner minimization problem, finding the global optima of such nonconvex objectives is already NP\-hard in the worst case\([Jin et al\., 2020](https://arxiv.org/html/2608.24146#bib.bib38)\)\.

Inpolicy improvementregime without robustness consideration \(i\.e\., a single\-loop performance maximization problem\), recent work has shown that some algorithms are guaranteed to converge to a globally\-optimal policy with a non\-convex objective function intabularMDPs\([Agarwal et al\., 2021](https://arxiv.org/html/2608.24146#bib.bib34);[Bhandari and Russo, 2021](https://arxiv.org/html/2608.24146#bib.bib33)\)\. When robustness is introduced via a min–max formalization, only recently was the first generic algorithm with global convergence proposed\([Wang et al\., 2023a](https://arxiv.org/html/2608.24146#bib.bib42)\)\. However, since their inner maximization objective \(policy performance\) reduces to a linear program in each update, the setting is considerably simpler than our variance\-based objective\.

In Section[6](https://arxiv.org/html/2608.24146#S6), we demonstrate the empirical performance of our Algorithm[2](https://arxiv.org/html/2608.24146#alg2)undera neural network policy parameterization\. While in this section, for the theoretical analysis of Algorithm[2](https://arxiv.org/html/2608.24146#alg2), we adopt a linear\-softmax parameterization for the behavior policyπθ\\pi\_\{\\theta\},πθ​\(a\|s\)≐exp⁡\(θa⊤​ϕ​\(s\)\)∑a′∈𝒜exp⁡\(θa′⊤​ϕ​\(s\)\),\\pi\_\{\\theta\}\(a\|s\)\\doteq\\frac\{\\exp\(\\theta^\\top\_a\\phi\(s\)\)\}\{\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\exp\(\\theta^\\top\_\{a'\}\\phi\(s\)\)\},whereϕ:s→ℝd\\phi:s\\to\\mathbb\{R\}^\{d\}is a state feature function, andθa∈ℝd\\theta\_\{a\}\\in\\mathbb\{R\}^\{d\}is the parameter associated with actiona∈𝒜a\\in\\mathcal\{A\}\. In this section, we assume that the parameters’ feasible setΘ\\Thetato be closed and convex with a diameterDD\(i\.e\.,∀θ,θ′∈Θ\\forall\\theta,\\theta^\{\\prime\}\\in\\Theta,‖θ−θ′‖≤D\\norm\{\\theta\-\\theta'\}\\leq D\), and assume the linear feature to be bounded \(i\.e\.,∀s,\\forall s,‖ϕ⁡\(s\)‖≤B\\norm\{\\phi\(s\)\}\\leq BforB∈ℝB\\in\\mathbb\{R\}\) \. This choice enables generalization across states through shared features, and makes the variance objective convex inθ\\theta\. This assumption has been widely adopted in recent theoretical work on policy gradient\([Agarwal et al\., 2021](https://arxiv.org/html/2608.24146#bib.bib34);[Yuan et al\., 2022](https://arxiv.org/html/2608.24146#bib.bib32);[Cayci et al\., 2024](https://arxiv.org/html/2608.24146#bib.bib31)\)\.

With the smoothness of this linear\-softmax parameterization, we first establish Lemma[5\.2](https://arxiv.org/html/2608.24146#S5.Thmtheorem2), which characterizes the behavior of the objective function𝕍\\mathbb\{V\}with respect to the policy parameterθ\\theta\. This lemma then helps to derive the Lipschitz continuity and convexity of the otherwise non\-convex and non\-differentiable objective functionΦ\\Phiin \([2](https://arxiv.org/html/2608.24146#S3.E2)\)\.

###### Lemma 5\.2\.

Under linear\-softmax policy parameterization, the objective function𝕍H∼pω,πθ​\[IS⁡\(πe,πθ,H\)\]\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]isLΘL\_\{\\Theta\}\-Lipschitz,ℓΘ\\ell\_\{\\Theta\}\-smooth, and convex inθ\\thetawithLΘ=2​B​C2​T​T3L\_\{\\Theta\}=\\sqrt\{2\}BC^\{2T\}T^\{3\}andℓΘ=B2​C2​T​T3​\(5\+8​T\)\\ell\_\{\\Theta\}=B^\{2\}C^\{2T\}T^\{3\}\\quantity\(5\+8T\), whereCCdenotes an upper bound on the importance sampling ratio withπe​\(a\|s\)πθ​\(a\|s\)≤C,∀\(s,a\),∀θ∈Θ\.\\frac\{\\pi\_\{e\}\(a\|s\)\}\{\\pi\_\{\\theta\}\(a\|s\)\}\\leq C,\\forall\(s,a\),\\forall\\theta\\in\\Theta\.

Its proof is in Appendix[A\.7](https://arxiv.org/html/2608.24146#A1.SS7)\. We assume bounded importance\-sampling ratios, as is standard in off\-policy evaluation to ensure finite variance\([Hanna et al\., 2017](https://arxiv.org/html/2608.24146#bib.bib49);[Hanna et al\., 2024](https://arxiv.org/html/2608.24146#bib.bib43)\), which can be simply satisfied by bounding the behavior policy away from zero\. While the theoretical constants scale with horizonTT, this dependence is intrinsic to importance sampling–based approaches and has also appeared in prior OPE analyses\([Liu et al\., 2018](https://arxiv.org/html/2608.24146#bib.bib55);[Liu et al\., 2020](https://arxiv.org/html/2608.24146#bib.bib30)\)\. Our result shows that global convergence still holds with finite\-sample guarantees despite this scaling\. With Lemma[5\.2](https://arxiv.org/html/2608.24146#S5.Thmtheorem2), we further obtain the desired properties ofΦ\\Phi, which serve as key building blocks for the global convergence of Algorithm[2](https://arxiv.org/html/2608.24146#alg2)\.

###### Lemma 5\.3\.

The functionΦ⁡\(θ\)\\Phi\(\\theta\)\([2](https://arxiv.org/html/2608.24146#S3.E2)\) isLΘL\_\{\\Theta\}\-Lipschitz and convex inθ\\theta\.

Its proof is in Appendix[A\.8](https://arxiv.org/html/2608.24146#A1.SS8)\. Equipped with Lemma[5\.2](https://arxiv.org/html/2608.24146#S5.Thmtheorem2)and Lemma[5\.3](https://arxiv.org/html/2608.24146#S5.Thmtheorem3), we are now ready to establish the convergence analysis despite the inherent nondifferentiability\. The following theorem provides a finite\-sample convergence guarantee for our double\-loop algorithm\.

###### Theorem 5\.4\(Double loop global convergence\)\.

With a constant step sizeα≐DLΘ​n\\alpha\\doteq\\frac\{D\}\{L\_\{\\Theta\}\\sqrt\{n\}\}, we have

Φ⁡\(θ¯\)−minθ∈Θ⁡Φ⁡\(θ\)≤D​LΘn\+1n​∑i=0n−1ϵi\.\\displaystyle\\textstyle\\Phi\(\\bar\{\\theta\}\)\-\\min\_\{\\theta\\in\\Theta\}\\Phi\(\\theta\)\\leq\\frac\{DL\_\{\\Theta\}\}\{\\sqrt\{n\}\}\+\\frac\{1\}\{n\}\\sum\_\{i=0\}^\{n\-1\}\\epsilon\_\{i\}\.\(18\)

Its proof is in Appendix[A\.9](https://arxiv.org/html/2608.24146#A1.SS9)\. This result shows that Algorithm[2](https://arxiv.org/html/2608.24146#alg2)converges to anϵ−\\epsilon\-optimal solution at a rate of𝒪⁡\(1n\)\\mathcal\{O\}\(\\frac\{1\}\{\\sqrt\{n\}\}\), wherennis the number of iterations\. This rate matches the optimal rate of projected gradient descent in convex optimization, although our min–max variance objective is more challenging than the performance\-based objectives studied in prior work\([Agarwal et al\., 2021](https://arxiv.org/html/2608.24146#bib.bib34);[Bhandari and Russo, 2021](https://arxiv.org/html/2608.24146#bib.bib33);[Wang et al\., 2023a](https://arxiv.org/html/2608.24146#bib.bib42)\)\. The error bound consists of two parts: the first termD​LΘn\\frac\{DL\_\{\\Theta\}\}\{\\sqrt\{n\}\}reflects the convergence rate of projected gradient descent, while the second term1n​∑i=0n−1ϵi\\frac\{1\}\{n\}\\sum\_\{i=0\}^\{n\-1\}\\epsilon\_\{i\}accounts for the chosen precision in the inner maximization\. To our knowledge, this is thefirstglobal convergence guarantee for variance\-minimizing behavior policy search under adversarial transitions, filling an important gap between classical off\-policy evaluation and robust reinforcement learning\. Finally, we note that double\-loop adversarial optimization is standard in robust reinforcement learning \(e\.g\.,[Wang et al\. \(2023a\)](https://arxiv.org/html/2608.24146#bib.bib42);[Ho et al\. \(2021\)](https://arxiv.org/html/2608.24146#bib.bib37);[Wang et al\. \(2024\)](https://arxiv.org/html/2608.24146#bib.bib44)\)\. As in prior work, our method trades additional, low\-cost simulator computation for improved robustness and reliability under transition uncertainty\.

Figure 1:Relative variance increase of each method under its tailored adversarial transition, compared to the variance under the original simulator transition\. All values are normalized by the variance increase of the on\-policy Monte Carlo \(MC\) method in the same environment\. More details are provided in Appendix[B](https://arxiv.org/html/2608.24146#A2)\. Error bars denote the standard error\.

## 6Numerical Results

In this section, we provide numerical results to validate the utility of our efficient and robust evaluation framework\. Our primary goal is to examine two key questions:\(1\)Is our method robust to adversarial transition perturbations?\(2\)Does it give lower evaluation variance under perturbed transitions compared with standard on\-policy Monte Carlo?

We evaluate these questions on two environments\. Garnet MDPs\([Archibald et al\., 1995](https://arxiv.org/html/2608.24146#bib.bib22)\)provide a class of randomly generated abstract MDPs that allow controlled investigation of robustness properties\. A Garnet instanceG⁡\(\|𝒮\|,\|𝒜\|,b\)G\(\|\\mathcal\{S\}\|,\|\\mathcal\{A\}\|,b\)is parameterized by the number of states\|𝒮\|\|\\mathcal\{S\}\|, number of actions\|𝒜\|\|\\mathcal\{A\}\|, and a branching factorbbthat controls the connectivity of transitions\. Owing to this flexibility, Garnets are a standard setting for analyzing robustness in controlled MDP studies\([Tarbouriech and Lazaric, 2019](https://arxiv.org/html/2608.24146#bib.bib20);[Wang et al\., 2023a](https://arxiv.org/html/2608.24146#bib.bib42);[Wang et al\., 2023b](https://arxiv.org/html/2608.24146#bib.bib21)\)\. Inventory management\([Porteus, 2002](https://arxiv.org/html/2608.24146#bib.bib19);[Ho et al\., 2018](https://arxiv.org/html/2608.24146#bib.bib18)\)is a classical stochastic control problem where a retailer makes ordering decisions under uncertain demand\. It provides a natural testbed for evaluating policy performance under transition uncertainties\. Notably, compared with recent related work in robust reinforcement learning, our experimental environments operate at comparable or higher complexity \(see Table[1](https://arxiv.org/html/2608.24146#S6.T1.fig1)\)\.

Table 1:Environments used in recent robust\-RL works\. LargerG⁡\(⋅,⋅\)G\(\\cdot,\\cdot\)settings indicate more challenging Garnet tasks\. Branching factors are omitted as they are not specified in the related work\.Figure 2:Relative variance of each method under the same perturbed transition\. Values are normalized by the variance of the on\-policy Monte Carlo \(MC\) method in the same environment\. Error bars denote the standard error\.To contextualize the results, we compare our approach with several representative methods: the on\-policy Monte Carlo estimator \(MC\), the behavior policy gradient estimator \(BPG,[Hanna et al\. \(2017\)](https://arxiv.org/html/2608.24146#bib.bib49)\), and the robust on\-policy sampling estimator \(ROS,[Zhong et al\. \(2022\)](https://arxiv.org/html/2608.24146#bib.bib48)\)\. All methods are trained with the same initial transition function to obtain their behavior policies\. We parameterize our behavior policy with a neural network and use the final iterate behavior policy from Algorithm[2](https://arxiv.org/html/2608.24146#alg2)to collect evaluation data\. Further experimental details are provided in Appendix[B](https://arxiv.org/html/2608.24146#A2)\.

We note that several related works consider settings that are not directly comparable to our online behavior\-policy search framework\. In particular,[Liu and Zhang \(2024\)](https://arxiv.org/html/2608.24146#bib.bib47)study a fully offline setting with fixed transitions, where the behavior policy is computed from pre\-logged data and cannot adapt to transition shifts at deployment\. Other robust evaluation approaches\([Katdare et al\., 2023](https://arxiv.org/html/2608.24146#bib.bib26);[Voloshin et al\., 2021](https://arxiv.org/html/2608.24146#bib.bib25)\)focus on estimator robustness or model learning under transition uncertainty, rather than learning variance\-minimizing behavior policies for data collection\. We therefore include baselines \(BPG and ROS\) that explicitly target the same behavior\-policy optimization objective as our method\.

### 6\.1Variance Increase under Tailored Adversarial Transitions

To answer the first question, we examine the robustness of each behavior policy when exposed to its own most adversarial transition\. For each method, we run Algorithm[1](https://arxiv.org/html/2608.24146#alg1)to obtain the transition that maximizes its evaluation variance\. Then, we use each behavior policy to collect data under itsmethod\-specific adversarial transition\. We report the relative variance increase compared to the original simulator transition, highlighting each method’s vulnerability to adversarial perturbations\. As shown in Figure[1](https://arxiv.org/html/2608.24146#S5.F1), our method exhibits the smallest variance increase, illustrating its robustness to adversarial transitions\. Notably, although designed for variance reduction, BPG and ROS incur larger variance increases than the on\-policy Monte Carlo baseline when the deployment transition is perturbed, underscoring the necessity of our robustness\-aware behavior policy search framework\.

### 6\.2Variance Comparison under Shared and Perturbed Transition

To address the second question, we evaluate all methods under a shared adversarial target transition identified by Algorithm[1](https://arxiv.org/html/2608.24146#alg1)for the on\-policy baseline\. We compare the variance of all four methods under thissame perturbed transition\. This setup contrasts with Section[6\.1](https://arxiv.org/html/2608.24146#S6.SS1), where each method faced its own tailored adversary\. As shown in Figure[2](https://arxiv.org/html/2608.24146#S6.F2), our method \(DRVG\) indeed achieves lower evaluation variance\. This demonstrates that explicitly accounting for transition uncertainty enables more reliable policy evaluation under perturbed environments\.

## 7Conclusion

In this work, we present an efficient and robust behavior policy search framework that tackles two central challenges in real\-world policy evaluation: variance reduction and transition mismatch\. Our method learns variance\-reducing behavior policies while explicitly accounting for transition uncertainty through a minimax formulation over adversarial dynamics\. Theoretically, we derive novel transition\-variance gradient expressions, establish convergence guarantees for the adversarial inner loop, and prove global convergence of our proposed double\-loop algorithm\. Numerically, our method demonstrates increased robustness under transition perturbations\. Taken together, these results unify variance reduction with robustness to transition shifts, offering a promising step toward reliable policy evaluation under uncertainty\.

## Acknowledgments and Disclosure of Funding

Shangtong Zhang acknowledges funding support from the US National Science Foundation under awards III\-2128019, SLES\-2331904, and CAREER\-2442098, the Commonwealth Cyber Initiative’s Central Virginia Node under award VV\-1Q26\-001, and a Cisco Faculty Research Award\. Nan Jiang acknowledges funding support from NSF CNS\-2112471, NSF CAREER IIS\-2141781, and Sloan Fellowship\.

## References

- Agarwalet al\.\(2021\)A\. Agarwal, S\. M\. Kakade, J\. D\. Lee, and G\. MahajanOn the theory of policy gradient methods: optimality, approximation, and distribution shift\.Journal of Machine Learning Research22\(98\),pp\. 1–76\.External Links:[Link](http://jmlr.org/papers/v22/19-736.html)Cited by:[§A\.1](https://arxiv.org/html/2608.24146#A1.SS1.SSS0.Px1.p1.1),[§A\.1](https://arxiv.org/html/2608.24146#A1.SS1.SSS0.Px2.p1.1),[§A\.1](https://arxiv.org/html/2608.24146#A1.SS1.SSS0.Px4.p1.1),[§A\.1](https://arxiv.org/html/2608.24146#A1.SS1.p2.1),[§5\.2](https://arxiv.org/html/2608.24146#S5.SS2.p2.1),[§5\.2](https://arxiv.org/html/2608.24146#S5.SS2.p3.1),[§5\.2](https://arxiv.org/html/2608.24146#S5.SS2.p7.1)\.
- Archibaldet al\.\(1995\)T\. W\. Archibald, K\. McKinnon, and L\. C\. ThomasOn the generation of markov decision processes\.Journal of the Operational Research Society46\(3\),pp\. 354–361\.Cited by:[§B\.2](https://arxiv.org/html/2608.24146#A2.SS2.p1.1),[§6](https://arxiv.org/html/2608.24146#S6.p2.1)\.
- Bertsekas \(1995\)D\.P\. BertsekasNonlinear programming\.Athena Scientific\.Cited by:[§5\.1](https://arxiv.org/html/2608.24146#S5.SS1.p4.1)\.
- Bertsekas and Tsitsiklis \(2000\)D\. P\. Bertsekas and J\. N\. TsitsiklisGradient convergence in gradient methods with errors\.SIAM Journal on Optimization10\(3\),pp\. 627–642\.Cited by:[§A\.3](https://arxiv.org/html/2608.24146#A1.SS3.p16.1.1),[§A\.3](https://arxiv.org/html/2608.24146#A1.SS3.p2.1.1),[§A\.3](https://arxiv.org/html/2608.24146#A1.SS3.p3.1.1)\.
- Bhandari and Russo \(2021\)J\. Bhandari and D\. RussoOn the linear convergence of policy gradient methods for finite mdps\.InProceedings of The 24th International Conference on Artificial Intelligence and Statistics,A\. Banerjee and K\. Fukumizu \(Eds\.\),Proceedings of Machine Learning Research, Vol\.130,pp\. 2386–2394\.External Links:[Link](https://proceedings.mlr.press/v130/bhandari21a.html)Cited by:[§A\.1](https://arxiv.org/html/2608.24146#A1.SS1.SSS0.Px4.p1.1),[§5\.2](https://arxiv.org/html/2608.24146#S5.SS2.p2.1),[§5\.2](https://arxiv.org/html/2608.24146#S5.SS2.p7.1)\.
- Cayciet al\.\(2024\)S\. Cayci, N\. He, and R\. SrikantConvergence of entropy\-regularized natural policy gradient with linear function approximation\.SIAM Journal on Optimization34\(3\),pp\. 2729–2755\.Cited by:[§5\.2](https://arxiv.org/html/2608.24146#S5.SS2.p3.1)\.
- Chenet al\.\(2025\)C\. Chen, S\. Liu, and S\. ZhangEfficient policy evaluation with safety constraint for reinforcement learning\.InProceedings of the International Conference on Learning Representations,Cited by:[§3\.2](https://arxiv.org/html/2608.24146#S3.SS2.p1.1)\.
- Chenet al\.\(2026a\)C\. Chen, J\. S\. Xiao, S\. D\. Liu, F\. P\. Paolino, L\. Handley, T\. J\. d\. Laz, R\. Nilsson, A\. Zou, M\. Graham, and A\. MahabalAstroAlertBench: evaluating the accuracy, reasoning, and honesty of multimodal LLMs in astronomical classification\.arXiv preprint arXiv:2605\.05573\.Cited by:[§B\.1](https://arxiv.org/html/2608.24146#A2.SS1.p3.1)\.
- Chenet al\.\(2026b\)C\. Chen, Y\. Zhang, X\. Liu, Z\. Xie, S\. D\. Liu, and N\. JiangOffline two\-player zero\-sum markov games with KL regularization\.InForty\-third International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=cQD2wxFhFG)Cited by:[§4\.1](https://arxiv.org/html/2608.24146#S4.SS1.p4.1)\.
- Chen and Zhang \(2026a\)C\. Chen and Y\. ZhangFast rates inα\\alpha\-potential games via regularized mirror descent\.ArXiv Preprint arXiv:2605\.00268\.Cited by:[§4\.1](https://arxiv.org/html/2608.24146#S4.SS1.p4.1)\.
- Chen and Zhang \(2026b\)C\. Chen and Y\. ZhangPessimism\-free offline learning in general\-sum games via KL regularization\.ArXiv Preprint arXiv:2605\.00264\.Cited by:[§4\.1](https://arxiv.org/html/2608.24146#S4.SS1.p4.1)\.
- Hannaet al\.\(2024\)J\. P\. Hanna, Y\. Chandak, P\. S\. Thomas, M\. White, P\. Stone, and S\. NiekumData\-efficient policy evaluation through behavior policy search\.Journal of Machine Learning Research25\(313\),pp\. 1–58\.Cited by:[\(By \(21\) of \( \) \)](https://arxiv.org/html/2608.24146#A1.Ex22),[§A\.1](https://arxiv.org/html/2608.24146#A1.SS1.SSS0.Px3.p1.1),[§A\.1](https://arxiv.org/html/2608.24146#A1.SS1.p2.1),[§A\.7](https://arxiv.org/html/2608.24146#A1.SS7.p10.7.1),[§A\.7](https://arxiv.org/html/2608.24146#A1.SS7.p4.1.1),[§B\.1](https://arxiv.org/html/2608.24146#A2.SS1.p1.1),[§4\.1](https://arxiv.org/html/2608.24146#S4.SS1.p3.1),[§5\.1](https://arxiv.org/html/2608.24146#S5.SS1.p1.2),[§5\.2](https://arxiv.org/html/2608.24146#S5.SS2.p5.1)\.
- Hannaet al\.\(2017\)J\. P\. Hanna, P\. S\. Thomas, P\. Stone, and S\. NiekumData\-efficient policy evaluation through behavior policy search\.InProceedings of the International Conference on Machine Learning,Cited by:[§A\.1](https://arxiv.org/html/2608.24146#A1.SS1.SSS0.Px3.p1.1),[§A\.1](https://arxiv.org/html/2608.24146#A1.SS1.p2.1),[§B\.1](https://arxiv.org/html/2608.24146#A2.SS1.p1.1),[§B\.1](https://arxiv.org/html/2608.24146#A2.SS1.p2.1),[§1](https://arxiv.org/html/2608.24146#S1.p2.1),[§2](https://arxiv.org/html/2608.24146#S2.p1.1),[§3\.2](https://arxiv.org/html/2608.24146#S3.SS2.p2.1),[§4\.1](https://arxiv.org/html/2608.24146#S4.SS1.p3.1),[§5\.1](https://arxiv.org/html/2608.24146#S5.SS1.p1.2),[§5\.2](https://arxiv.org/html/2608.24146#S5.SS2.p5.1),[§6](https://arxiv.org/html/2608.24146#S6.p3.1)\.
- Hoet al\.\(2018\)C\. P\. Ho, M\. Petrik, and W\. WiesemannFast bellman updates for robust mdps\.InInternational Conference on Machine Learning,pp\. 1979–1988\.Cited by:[§B\.3](https://arxiv.org/html/2608.24146#A2.SS3.p1.1),[§6](https://arxiv.org/html/2608.24146#S6.p2.1)\.
- Hoet al\.\(2021\)C\. P\. Ho, M\. Petrik, and W\. WiesemannPartial policy iteration for l1\-robust markov decision processes\.Journal of Machine Learning Research22\(275\),pp\. 1–46\.External Links:[Link](http://jmlr.org/papers/v22/20-445.html)Cited by:[§3\.3](https://arxiv.org/html/2608.24146#S3.SS3.p2.2),[§5\.1](https://arxiv.org/html/2608.24146#S5.SS1.p3.1),[§5\.2](https://arxiv.org/html/2608.24146#S5.SS2.p7.1)\.
- Iyengar \(2005\)G\. N\. IyengarRobust dynamic programming\.Mathematics of Operations Research30\(2\),pp\. 257–280\.Cited by:[§2](https://arxiv.org/html/2608.24146#S2.p4.1),[§3\.3](https://arxiv.org/html/2608.24146#S3.SS3.p2.2)\.
- Jinet al\.\(2020\)C\. Jin, P\. Netrapalli, and M\. JordanWhat is local optimality in nonconvex\-nonconcave minimax optimization?\.InInternational conference on machine learning,pp\. 4880–4889\.Cited by:[§3\.3](https://arxiv.org/html/2608.24146#S3.SS3.p3.2),[§5\.2](https://arxiv.org/html/2608.24146#S5.SS2.p1.2)\.
- Jumperet al\.\(2021\)J\. Jumper, R\. Evans, A\. Pritzel, T\. Green, M\. Figurnov, O\. Ronneberger, K\. Tunyasuvunakool, R\. Bates, A\. Žídek, A\. Potapenko,et al\.Highly accurate protein structure prediction with alphafold\.Nature\.Cited by:[§1](https://arxiv.org/html/2608.24146#S1.p1.1)\.
- Katdareet al\.\(2023\)P\. Katdare, N\. Jiang, and K\. R\. Driggs\-CampbellMarginalized importance sampling for off\-environment policy evaluation\.InConference on Robot Learning,pp\. 3778–3788\.Cited by:[§2](https://arxiv.org/html/2608.24146#S2.p3.1),[§3\.3](https://arxiv.org/html/2608.24146#S3.SS3.p2.2),[§6](https://arxiv.org/html/2608.24146#S6.p4.1)\.
- Kingma and Ba \(2015\)D\. P\. Kingma and J\. BaAdam: A method for stochastic optimization\.InProceedings of the International Conference on Learning Representations,Cited by:[§B\.1](https://arxiv.org/html/2608.24146#A2.SS1.p2.1)\.
- Komorowskiet al\.\(2018\)M\. Komorowski, L\. A\. Celi, O\. Badawi, A\. C\. Gordon, and A\. A\. FaisalThe artificial intelligence clinician learns optimal treatment strategies for sepsis in intensive care\.Nature medicine24\(11\),pp\. 1716–1720\.Cited by:[§4\.2](https://arxiv.org/html/2608.24146#S4.SS2.p1.1)\.
- Linet al\.\(2020\)T\. Lin, C\. Jin, and M\. JordanOn gradient descent ascent for nonconvex\-concave minimax problems\.InProceedings of the 37th International Conference on Machine Learning,H\. D\. III and A\. Singh \(Eds\.\),Proceedings of Machine Learning Research, Vol\.119,pp\. 6083–6093\.External Links:[Link](https://proceedings.mlr.press/v119/lin20a.html)Cited by:[§5\.2](https://arxiv.org/html/2608.24146#S5.SS2.p1.2)\.
- Liuet al\.\(2018\)Q\. Liu, L\. Li, Z\. Tang, and D\. ZhouBreaking the curse of horizon: infinite\-horizon off\-policy estimation\.InAdvances in Neural Information Processing Systems,Cited by:[§5\.2](https://arxiv.org/html/2608.24146#S5.SS2.p5.1)\.
- Liuet al\.\(2025a\)S\. Liu, C\. Chen, and S\. ZhangDoubly optimal policy evaluation for reinforcement learning\.InProceedings of the International Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2608.24146#S1.p2.1),[§3\.2](https://arxiv.org/html/2608.24146#S3.SS2.p1.1)\.
- Liuet al\.\(2025b\)S\. Liu, Y\. Chen, and S\. ZhangEfficient multi\-policy evaluation for reinforcement learning\.InProceedings of the AAAI Conference on Artificial Intelligence,Cited by:[§3\.2](https://arxiv.org/html/2608.24146#S3.SS2.p1.1)\.
- Liuet al\.\(2026a\)S\. D\. Liu, C\. Chen, C\. Gao, and D\. Simchi\-LeviOR\-Transformer: scaling real\-time decision\-making to 1,000 items\.Note:ManuscriptCited by:[§B\.3](https://arxiv.org/html/2608.24146#A2.SS3.p1.1)\.
- Liuet al\.\(2026b\)S\. D\. Liu, C\. Chen, J\. Wang, and D\. Simchi\-LeviPessimistic minimax learning for public\-private information games under unilateral coverage\.Note:ManuscriptCited by:[§A\.1](https://arxiv.org/html/2608.24146#A1.SS1.p2.1)\.
- Liuet al\.\(2026c\)S\. D\. Liu, C\. Chen, J\. S\. Xiao, X\. Chen, and D\. Simchi\-LeviStrategic bargaining in multi\-buyer markets: reinforcement learning from verifiable rewards for LLM negotiations\.arXiv preprint arXiv:2607\.05863\.Cited by:[§1](https://arxiv.org/html/2608.24146#S1.p1.1)\.
- Liuet al\.\(2026d\)S\. D\. Liu, C\. Chen, J\. S\. Xiao, L\. Lei, Y\. Zhang, Y\. Yue, and D\. Simchi\-LeviInstructing LLMs to negotiate using reinforcement learning with verifiable rewards\.arXiv preprint arXiv:2604\.09855\.Cited by:[§1](https://arxiv.org/html/2608.24146#S1.p1.1)\.
- Liuet al\.\(2025c\)S\. D\. Liu, S\. Chen, and S\. ZhangThe ode method for stochastic approximation and reinforcement learning with markovian noise\.Journal of Machine Learning Research26\(24\),pp\. 1–76\.Cited by:[§4\.1](https://arxiv.org/html/2608.24146#S4.SS1.p3.1)\.
- Liu \(2025\)S\. D\. LiuEfficient and robust policy evaluation for reinforcement learning\.Ph\.D\. Thesis,University of Virginia\.Cited by:[§1](https://arxiv.org/html/2608.24146#S1.p2.1)\.
- Liu and Zhang \(2024\)S\. Liu and S\. ZhangEfficient policy evaluation with offline data informed behavior policy design\.InProceedings of the International Conference on Machine Learning,Cited by:[§1](https://arxiv.org/html/2608.24146#S1.p2.1),[§2](https://arxiv.org/html/2608.24146#S2.p2.1),[§3\.2](https://arxiv.org/html/2608.24146#S3.SS2.p1.1),[§6](https://arxiv.org/html/2608.24146#S6.p4.1)\.
- Liuet al\.\(2026e\)X\. Liu, Z\. Xie, A\. Moeini, C\. Chen, S\. D\. Liu, Y\. Meng, A\. Zhang, and S\. ZhangMathliblemma: folklore lemma generation and benchmark for formal mathematics\.arXiv preprint arXiv:2602\.02561\.Cited by:[§B\.1](https://arxiv.org/html/2608.24146#A2.SS1.p3.1)\.
- Liuet al\.\(2020\)Y\. Liu, P\. Bacon, and E\. BrunskillUnderstanding the curse of horizon in off\-policy evaluation via conditional importance sampling\.InInternational Conference on Machine Learning,pp\. 6184–6193\.Cited by:[§5\.2](https://arxiv.org/html/2608.24146#S5.SS2.p5.1)\.
- Mahadevanet al\.\(2026\)V\. Mahadevan, C\. Chen, S\. D\. Liu, and S\. ZhangConvergence of two\-timescale Markovian stochastic approximations with applications in reinforcement learning\.InProceedings of the 43rd International Conference on Machine Learning,Cited by:[§4\.1](https://arxiv.org/html/2608.24146#S4.SS1.p3.1)\.
- Mnihet al\.\(2015\)V\. Mnih, K\. Kavukcuoglu, D\. Silver, A\. A\. Rusu, J\. Veness, M\. G\. Bellemare, A\. Graves, M\. A\. Riedmiller, A\. Fidjeland, G\. Ostrovski, S\. Petersen, C\. Beattie, A\. Sadik, I\. Antonoglou, H\. King, D\. Kumaran, D\. Wierstra, S\. Legg, and D\. HassabisHuman\-level control through deep reinforcement learning\.Nature\.Cited by:[§1](https://arxiv.org/html/2608.24146#S1.p1.1)\.
- Nilim and El Ghaoui \(2005\)A\. Nilim and L\. El GhaouiRobust control of markov decision processes with uncertain transition matrices\.Operations Research53\(5\),pp\. 780–798\.Cited by:[§2](https://arxiv.org/html/2608.24146#S2.p4.1),[§3\.3](https://arxiv.org/html/2608.24146#S3.SS3.p2.2)\.
- Nouiehedet al\.\(2019\)M\. Nouiehed, M\. Sanjabi, T\. Huang, J\. D\. Lee, and M\. RazaviyaynSolving a class of non\-convex min\-max games using iterative first order methods\.InAdvances in Neural Information Processing Systems,H\. Wallach, H\. Larochelle, A\. Beygelzimer, F\. d'Alché\-Buc, E\. Fox, and R\. Garnett \(Eds\.\),Vol\.32,pp\.\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2019/file/25048eb6a33209cb5a815bff0cf6887c-Paper.pdf)Cited by:[§5\.2](https://arxiv.org/html/2608.24146#S5.SS2.p1.2)\.
- Porteus \(2002\)E\. L\. PorteusFoundations of stochastic inventory theory\.Stanford University Press\.Cited by:[§B\.3](https://arxiv.org/html/2608.24146#A2.SS3.p1.1),[§6](https://arxiv.org/html/2608.24146#S6.p2.1)\.
- Puterman \(2014\)M\. L\. PutermanMarkov decision processes: discrete stochastic dynamic programming\.John Wiley & Sons\.Cited by:[§3\.1](https://arxiv.org/html/2608.24146#S3.SS1.p1.1)\.
- Robbins and Monro \(1951\)H\. Robbins and S\. MonroA stochastic approximation method\.The Annals of Mathematical Statistics\.Cited by:[§4\.1](https://arxiv.org/html/2608.24146#S4.SS1.p3.1)\.
- Russo and Pacchiano \(2025\)A\. Russo and A\. PacchianoAdaptive exploration for multi\-reward multi\-policy evaluation\.arXiv preprint arXiv:2502\.02516\.Cited by:[§2](https://arxiv.org/html/2608.24146#S2.p2.1)\.
- Silveret al\.\(2017\)D\. Silver, J\. Schrittwieser, K\. Simonyan, I\. Antonoglou, A\. Huang, A\. Guez, T\. Hubert, L\. Baker, M\. Lai, A\. Bolton,et al\.Mastering the game of go without human knowledge\.nature550\(7676\),pp\. 354–359\.Cited by:[§1](https://arxiv.org/html/2608.24146#S1.p1.1)\.
- Sunet al\.\(2024\)Z\. Sun, S\. He, F\. Miao, and S\. ZouPolicy optimization for robust average reward mdps\.Advances in Neural Information Processing Systems37,pp\. 17348–17372\.Cited by:[Table 1](https://arxiv.org/html/2608.24146#S6.T1.fig1.2.4.1)\.
- Sutton and Barto \(2018\)R\. S\. Sutton and A\. G\. BartoReinforcement learning: an introduction \(2nd edition\)\.MIT press\.Cited by:[§B\.3](https://arxiv.org/html/2608.24146#A2.SS3.p1.1)\.
- Tanget al\.\(2025\)C\. Tang, Z\. Liu, and P\. XuRobust offline reinforcement learning with linearly structuredff\-divergence regularization\.InProceedings of the 42nd International Conference on Machine Learning,pp\. 58842–58882\.Cited by:[§4\.1](https://arxiv.org/html/2608.24146#S4.SS1.p4.1)\.
- Tarbouriech and Lazaric \(2019\)J\. Tarbouriech and A\. LazaricActive exploration in markov decision processes\.InThe 22nd International Conference on Artificial Intelligence and Statistics,pp\. 974–982\.Cited by:[§B\.2](https://arxiv.org/html/2608.24146#A2.SS2.p1.1),[§6](https://arxiv.org/html/2608.24146#S6.p2.1)\.
- Voloshinet al\.\(2021\)C\. Voloshin, N\. Jiang, and Y\. YueMinimax model learning\.InInternational Conference on Artificial Intelligence and Statistics,pp\. 1612–1620\.Cited by:[§2](https://arxiv.org/html/2608.24146#S2.p3.1),[§3\.3](https://arxiv.org/html/2608.24146#S3.SS3.p2.2),[§6](https://arxiv.org/html/2608.24146#S6.p4.1)\.
- Wanget al\.\(2026\)J\. Wang, J\. Srinivasa, C\. Chen, S\. D\. Liu, A\. Payani, and S\. ZhangPredicting plasticity in deep continual learning: a theoretical perspective\.arXiv preprint arXiv:2605\.09044\.Cited by:[§B\.1](https://arxiv.org/html/2608.24146#A2.SS1.p2.1)\.
- Wanget al\.\(2023a\)Q\. Wang, C\. P\. Ho, and M\. PetrikPolicy gradient in robust mdps with global convergence guarantee\.InInternational Conference on Machine Learning,pp\. 35763–35797\.Cited by:[§A\.1](https://arxiv.org/html/2608.24146#A1.SS1.SSS0.Px1.p1.1),[§A\.1](https://arxiv.org/html/2608.24146#A1.SS1.p2.1),[§A\.7](https://arxiv.org/html/2608.24146#A1.SS7.p1.3.1),[§B\.2](https://arxiv.org/html/2608.24146#A2.SS2.p1.1),[§2](https://arxiv.org/html/2608.24146#S2.p4.1),[§3\.3](https://arxiv.org/html/2608.24146#S3.SS3.p2.2),[§5\.1](https://arxiv.org/html/2608.24146#S5.SS1.p3.1),[§5\.1](https://arxiv.org/html/2608.24146#S5.SS1.p4.1),[§5\.2](https://arxiv.org/html/2608.24146#S5.SS2.p2.1),[§5\.2](https://arxiv.org/html/2608.24146#S5.SS2.p7.1),[Table 1](https://arxiv.org/html/2608.24146#S6.T1.fig1.2.3.1),[§6](https://arxiv.org/html/2608.24146#S6.p2.1)\.
- Wanget al\.\(2024\)Q\. Wang, S\. Xu, C\. P\. Ho, and M\. PetrikPolicy gradient for robust markov decision processes\.arXiv preprint arXiv:2410\.22114\.Cited by:[§2](https://arxiv.org/html/2608.24146#S2.p4.1),[§5\.2](https://arxiv.org/html/2608.24146#S5.SS2.p7.1)\.
- Wanget al\.\(2023b\)Y\. Wang, A\. Velasquez, G\. Atia, A\. Prater\-Bennette, and S\. ZouRobust average\-reward markov decision processes\.InProceedings of the AAAI Conference on Artificial Intelligence,pp\. 15215–15223\.Cited by:[§B\.2](https://arxiv.org/html/2608.24146#A2.SS2.p1.1),[§6](https://arxiv.org/html/2608.24146#S6.p2.1)\.
- Xieet al\.\(2026\)Z\. Xie, X\. Liu, C\. Chen, S\. D\. Liu, R\. Chandra, and S\. ZhangBeyond linear attention: Softmax transformers implement in\-context reinforcement learning\.arXiv preprint arXiv:2605\.07333\.Cited by:[§1](https://arxiv.org/html/2608.24146#S1.p1.1)\.
- Yuanet al\.\(2022\)R\. Yuan, S\. S\. Du, R\. M\. Gower, A\. Lazaric, and L\. XiaoLinear convergence of natural policy gradient methods with log\-linear policies\.arXiv preprint arXiv:2210\.01400\.Cited by:[§5\.2](https://arxiv.org/html/2608.24146#S5.SS2.p3.1)\.
- Zhanget al\.\(2026\)Y\. Zhang, C\. Chen, and N\. JiangBeyond pessimism: offline learning in kl\-regularized games\.arXiv preprint arXiv:2604\.06738\.Cited by:[§4\.1](https://arxiv.org/html/2608.24146#S4.SS1.p4.1)\.
- Zhonget al\.\(2022\)R\. Zhong, D\. Zhang, L\. Schäfer, S\. V\. Albrecht, and J\. P\. HannaRobust on\-policy sampling for data\-efficient policy evaluation in reinforcement learning\.InAdvances in Neural Information Processing Systems,Cited by:[§B\.1](https://arxiv.org/html/2608.24146#A2.SS1.p1.1),[§B\.1](https://arxiv.org/html/2608.24146#A2.SS1.p2.1),[Appendix B](https://arxiv.org/html/2608.24146#A2.p2.1),[§1](https://arxiv.org/html/2608.24146#S1.p2.1),[§2](https://arxiv.org/html/2608.24146#S2.p1.1),[§3\.2](https://arxiv.org/html/2608.24146#S3.SS2.p2.1),[§6](https://arxiv.org/html/2608.24146#S6.p3.1)\.

## Appendix AProof

### A\.1Definitions

In this section, we show the standard optimization definitions used in our work\. Consider an optimization problem

minx∈𝒳⁡f⁡\(x\)\\displaystyle\\min\_\{x\\in\\mathcal\{X\}\}f\(x\)\(19\)where𝒳⊆ℝd\\mathcal\{X\}\\subseteq\\mathbb\{R\}^\{d\}is nonempty and closed, andf:ℝd→ℝf:\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}\. We have the following definitions for Lipschitz continuity and smoothness\.

###### Definition A\.1\(Lipschitz Continuity\)\.

The functionf:𝒳→ℝf:\\mathcal\{X\}\\to\\mathbb\{R\}isL−L\-Lipschitz if∀x1,x2∈𝒳,\\forall x\_\{1\},x\_\{2\}\\in\\mathcal\{X\},

‖f⁡\(x1\)−f⁡\(x2\)‖≤L​‖x1−x2‖\.\\displaystyle\\norm\{f\(x\_1\)\-f\(x\_2\)\}\\leq L\\norm\{x\_1\-x\_2\}\.\(20\)

###### Definition A\.2\(Smoothness\)\.

The functionf:𝒳→ℝf:\\mathcal\{X\}\\to\\mathbb\{R\}isℓ−\\ell\-smooth if∀x1,x2∈𝒳,\\forall x\_\{1\},x\_\{2\}\\in\\mathcal\{X\},

‖∇f​\(x1\)−∇f​\(x2\)‖≤ℓ​‖x1−x2‖\.\\displaystyle\\norm\{\\nabla f\(x\_1\)\-\\nabla f\(x\_2\)\}\\leq\\ell\\norm\{x\_1\-x\_2\}\.\(21\)

Our theoretical results are established within a standard analytical framework consistent with prior work in behavior\-policy search, robust reinforcement learning, and minimax learning\([Hanna et al\., 2017](https://arxiv.org/html/2608.24146#bib.bib49);[Agarwal et al\., 2021](https://arxiv.org/html/2608.24146#bib.bib34);[Wang et al\., 2023a](https://arxiv.org/html/2608.24146#bib.bib42);[Hanna et al\., 2024](https://arxiv.org/html/2608.24146#bib.bib43);[Liu et al\., 2026b](https://arxiv.org/html/2608.24146#bib.bib2)\)\. To ensure the existence of well\-defined gradients and the validity of our global convergence analysis, we consider environments and parameterizations that satisfy the following standard regularity conditions:

#### Smoothness of the Transition Model

We consider a class of transition functionspω​\(s′\|s,a\)p\_\{\\omega\}\(s^\{\\prime\}\|s,a\)that are twice\-differentiable with respect to their parametersω\\omega\. This is a standard property naturally satisfied by typical softmax or neural\-network parameterizations with smooth activation functions\([Agarwal et al\., 2021](https://arxiv.org/html/2608.24146#bib.bib34);[Wang et al\., 2023a](https://arxiv.org/html/2608.24146#bib.bib42)\)\.

#### Compactness of the Parameter Spaces

Consistent with established results in minimax optimization and projected gradient descent, the transition uncertainty setΩ\\Omegaand the behavior policy parameter spaceΘ\\Thetaare assumed to be compact and convex sets\([Agarwal et al\., 2021](https://arxiv.org/html/2608.24146#bib.bib34)\)\.

#### Finite Evaluation Variance

To ensure the stability of the behavior\-policy search, we assume the importance sampling ratios are uniformly bounded by a constantCC\. This is the standard condition for ensuring finite evaluation variance in off\-policy evaluation\([Hanna et al\., 2017](https://arxiv.org/html/2608.24146#bib.bib49);[Hanna et al\., 2024](https://arxiv.org/html/2608.24146#bib.bib43)\)\. In practice, this is satisfied by choosing a behavior policy parameter spaceΘ\\Thetathat keeps the data\-collection policy bounded away from zero\.

#### Bounded Feature Representations

For the global convergence guarantees established in Section 5\.2, we assume that the state featuresϕ⁡\(s\)\\phi\(s\)are bounded\([Agarwal et al\., 2021](https://arxiv.org/html/2608.24146#bib.bib34);[Bhandari and Russo, 2021](https://arxiv.org/html/2608.24146#bib.bib33)\)\.

With these definitions in hand, we are now ready to present the proofs\.

### A\.2Proof of Theorem[4\.1](https://arxiv.org/html/2608.24146#S4.Thmtheorem1)

See[4\.1](https://arxiv.org/html/2608.24146#S4.Thmtheorem1)

###### Proof\.

To prove Theorem[4\.1](https://arxiv.org/html/2608.24146#S4.Thmtheorem1), we aim at decomposing the termPr⁡\(H=h∣pω\)\\mathrm\{Pr\}\(H=h\\mid p\_\{\\omega\}\)into two parts: one that depends onpωp\_\{\\omega\}and one that does not\. By the standard trajectory factorization for a fixed initial\-state distributionp0p\_\{0\}and behavior policyπθ\\pi\_\{\\theta\},

Pr⁡\(H=h∣pω\)=p0​\(S0\)​∏t=0T−1πθ​\(At\|St\)​∏t=0T−1pω​\(St\+1\|St,At\)\.\\displaystyle\\mathrm\{Pr\}\(H=h\\mid p\_\{\\omega\}\)=p\_\{0\}\(S\_\{0\}\)\\prod\_\{t=0\}^\{T\-1\}\\pi\_\{\\theta\}\(A\_\{t\}\|S\_\{t\}\)\\prod\_\{t=0\}^\{T\-1\}p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\.\(22\)We separate theω\\omega\-dependent transition factor from theω\\omega\-independent factors by defining

mpω​\(h\)≐∏t=0T−1pω​\(St\+1\|St,At\)\\displaystyle m\_\{p\_\{\\omega\}\}\(h\)\\doteq\\prod\_\{t=0\}^\{T\-1\}p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\(23\)and

p⁡\(h\)≐p0​\(S0\)​∏t=0T−1πθ​\(At\|St\)\.\\displaystyle p\(h\)\\doteq p\_\{0\}\(S\_\{0\}\)\\prod\_\{t=0\}^\{T\-1\}\\pi\_\{\\theta\}\(A\_\{t\}\|S\_\{t\}\)\.\(24\)Note thatp⁡\(h\)p\(h\)is independent ofω\\omegasincep0p\_\{0\}is the fixed initial\-state distribution andπθ\\pi\_\{\\theta\}does not depend onω\\omega\. We thus obtain the decomposition

Pr⁡\(H=h∣pω\)=p⁡\(h\)​mpω​\(h\)\.\\displaystyle\\mathrm\{Pr\}\(H=h\\mid p\_\{\\omega\}\)=p\(h\)m\_\{p\_\{\\omega\}\}\(h\)\.\(25\)Next, we manipulate the term∂∂ω​mpω​\(h\)\\frac\{\\partial\}\{\\partial\\omega\}m\_\{p\_\{\\omega\}\}\(h\)\.

∂∂ω​mpω​\(h\)=\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}m\_\{p\_\{\\omega\}\}\(h\)=∂∂ω​∏t=0T−1pω​\(St\+1\|St,At\)\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\prod\_\{t=0\}^\{T\-1\}p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\(26\)=\\displaystyle=∑t=0T−1\(∏i≠tpω​\(Si\+1\|Si,Ai\)​∂pω​\(St\+1\|St,At\)∂ω\)\\displaystyle\\sum\_\{t=0\}^\{T\-1\}\\left\(\\prod\_\{i\\neq t\}p\_\{\\omega\}\(S\_\{i\+1\}\|S\_\{i\},A\_\{i\}\)\\frac\{\\partial p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\}\{\\partial\\omega\}\\right\)\(27\)=\\displaystyle=∑t=0T−1\(∏i=0T−1pω​\(Si\+1\|Si,Ai\)pω​\(St\+1\|St,At\)\.∂pω​\(St\+1\|St,At\)∂ω\)\\displaystyle\\sum\_\{t=0\}^\{T\-1\}\\left\(\\frac\{\\prod\_\{i=0\}^\{T\-1\}p\_\{\\omega\}\(S\_\{i\+1\}\|S\_\{i\},A\_\{i\}\)\}\{p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\}\.\\frac\{\\partial p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\}\{\\partial\\omega\}\\right\)\(28\)=\\displaystyle=∏i=0T−1pω​\(Si\+1\|Si,Ai\)⋅∑t=0T−1\(1pω​\(St\+1\|St,At\)​∂pω​\(St\+1\|St,At\)∂ω\)\\displaystyle\\prod\_\{i=0\}^\{T\-1\}p\_\{\\omega\}\(S\_\{i\+1\}\|S\_\{i\},A\_\{i\}\)\\cdot\\sum\_\{t=0\}^\{T\-1\}\\left\(\\frac\{1\}\{p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\}\\frac\{\\partial p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\}\{\\partial\\omega\}\\right\)\(29\)=\(a\)\\displaystyle\\overset\{\\text\{\(a\)\}\}\{=\}∏i=0T−1pω​\(Si\+1\|Si,Ai\)⋅∑t=0T−1\(1pω​\(St\+1\|St,At\)​pω​\(St\+1\|St,At\)​∂log⁡pω​\(St\+1\|St,At\)∂ω\)\\displaystyle\\prod\_\{i=0\}^\{T\-1\}p\_\{\\omega\}\(S\_\{i\+1\}\|S\_\{i\},A\_\{i\}\)\\cdot\\sum\_\{t=0\}^\{T\-1\}\\left\(\\frac\{1\}\{p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\}p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\\frac\{\\partial\\log p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\}\{\\partial\\omega\}\\right\)\(30\)=\\displaystyle=∏i=0T−1pω​\(Si\+1\|Si,Ai\)​∑t=0T−1\(∂∂ω​log⁡pω​\(St\+1\|St,At\)\)\\displaystyle\\prod\_\{i=0\}^\{T\-1\}p\_\{\\omega\}\(S\_\{i\+1\}\|S\_\{i\},A\_\{i\}\)\\sum\_\{t=0\}^\{T\-1\}\\left\(\\frac\{\\partial\}\{\\partial\\omega\}\\log p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\\right\)\(31\)=\\displaystyle=mpω​\(h\)​∑t=0T−1\(∂∂ω​log⁡pω​\(St\+1\|St,At\)\)\\displaystyle m\_\{p\_\{\\omega\}\}\(h\)\\sum\_\{t=0\}^\{T\-1\}\\left\(\\frac\{\\partial\}\{\\partial\\omega\}\\log p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\\right\)\(32\)=\\displaystyle=mpω​\(h\)​∑t=0T−1∂∂ω​log⁡\(pω​\(St\+1\|St,At\)\)\\displaystyle m\_\{p\_\{\\omega\}\}\(h\)\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\(33\)Here, \(a\) follows from the fact that

∂∂x​log⁡f​\(x\)=1f⁡\(x\)​∂f⁡\(x\)∂x\\displaystyle\\frac\{\\partial\}\{\\partial x\}\\log f\(x\)=\\frac\{1\}\{f\(x\)\}\\frac\{\\partial f\(x\)\}\{\\partial x\}\(34\)⟹\\displaystyle\\implies∂f⁡\(x\)∂x=f⁡\(x\)⋅∂log⁡f⁡\(x\)∂x\.\\displaystyle\\frac\{\\partial f\(x\)\}\{\\partial x\}=f\(x\)\\cdot\\frac\{\\partial\\log f\(x\)\}\{\\partial x\}\.\(35\)Then, we decompose the variance objective

∂∂ω​𝕍H∼pω,πθ​\[OPE⁡\(πe,πθ,H\)\]\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]\(36\)=\\displaystyle=∂∂ω​\(𝔼H∼pω,πθ​\[OPE​\(πe,πθ,H\)2\]−𝔼H∼pω,πθ​\[OPE⁡\(πe,πθ,h\)\]2\)\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\quantity\(\\E\_\{\\Hsample\}\[\\OPE\(\\pi\_e, \\pi\_\\theta,H\)^2\]\-\\E\_\{\\Hsample\}\[\\OPE\(\\pi\_e, \\pi\_\\theta,h\)\]^2\)\(37\)=\\displaystyle=∂∂ω​∑hPr⁡\(H=h\|pω\)​OPE​\(πe,πθ,h\)2\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\sum\_\{h\}\\Pr\(H=h\|p\_\\omega\)\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},h\)^\{2\}\(38\)−2𝔼H∼pω,πθ\[OPE\(πe,πθ,H\)\]∂∂ω∑hPr⁡\(H=h\|pω\)OPE\(πe,πθ,h\)\\displaystyle\-2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]\\frac\{\\partial\}\{\\partial\\omega\}\\sum\_\{h\}\\Pr\(H=h\|p\_\\omega\)\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},h\)\(39\)=\\displaystyle=∑hp⁡\(h\)​OPE​\(πe,πθ,h\)2​∂∂ω​mpω​\(h\)\\displaystyle\\sum\_\{h\}p\(h\)\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},h\)^\{2\}\\frac\{\\partial\}\{\\partial\\omega\}m\_\{p\_\{\\omega\}\}\(h\)\(40\)−2𝔼H∼pω,πθ\[OPE\(πe,πθ,H\)\]∑hp\(h\)OPE\(πe,πθ,h\)∂∂ωmpω\(h\)\\displaystyle\-2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]\\sum\_\{h\}p\(h\)\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},h\)\\frac\{\\partial\}\{\\partial\\omega\}m\_\{p\_\{\\omega\}\}\(h\)\(By \([25](https://arxiv.org/html/2608.24146#A1.E25)\)\)=\\displaystyle=∑hp⁡\(h\)​OPE​\(πe,πθ,h\)2​mpω​\(h\)​∑t=0T−1∂∂ω​log⁡\(pω​\(St\+1\|St,At\)\)\\displaystyle\\sum\_\{h\}p\(h\)\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},h\)^\{2\}m\_\{p\_\{\\omega\}\}\(h\)\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\(42\)−2𝔼H∼pω,πθ\[OPE\(πe,πθ,H\)\]∑hp\(h\)OPE\(πe,πθ,h\)mpω\(h\)∑t=0T−1∂∂ωlog⁡\(pω​\(St\+1\|St,At\)\)\\displaystyle\-2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]\\sum\_\{h\}p\(h\)\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},h\)m\_\{p\_\{\\omega\}\}\(h\)\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\(By \([33](https://arxiv.org/html/2608.24146#A1.E33)\)\)=\\displaystyle=𝔼H∼pω,πθ​\[OPE​\(πe,πθ,H\)2​∑t=0T−1∂∂ω​log⁡\(pω​\(St\+1\|St,At\)\)\]\\displaystyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)^\{2\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\]\(43\)−2​𝔼H∼pω,πθ​\[OPE⁡\(πe,πθ,H\)\]​𝔼H∼pω,πθ​\[OPE⁡\(πe,πθ,H\)​∑t=0T−1∂∂ω​log⁡\(pω​\(St\+1\|St,At\)\)\]\.\\displaystyle\-2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\quantity\[\\OPE\(\\pi\_e, \\pi\_\\theta, H\)\\sum\_\{t=0\}^\{T\-1\}\\gradomega\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\) \]\.\(44\)
∎

### A\.3Proof of Lemma[4\.2](https://arxiv.org/html/2608.24146#S4.Thmtheorem2)

See[4\.2](https://arxiv.org/html/2608.24146#S4.Thmtheorem2)

###### Proof\.

The proof leverages Proposition33in[Bertsekas and Tsitsiklis \(2000\)](https://arxiv.org/html/2608.24146#bib.bib45), for which we have to show that Algorithm[1](https://arxiv.org/html/2608.24146#alg1)satisfies the following conditions:

1. 1\.𝕍⁡\[IS⁡\(πθ,pωi,Hi\)\]\\mathbb\{V\}\[\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\_\{i\}\},H\_\{i\}\)\]is continuously differentiable w\.r\.t\.ω\\omega\.
2. 2\.The gradient of the variance objectives,∂∂ω​𝕍​\[IS⁡\(πθ,pωi,Hi\)\]\\frac\{\\partial\}\{\\partial\\omega\}\\mathbb\{V\}\[\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\_\{i\}\},H\_\{i\}\)\], is Lipschitz continuous w\.r\.t\.ω\\omega\.
3. 3\.The variance of the gradient estimate used by Algorithm[1](https://arxiv.org/html/2608.24146#alg1)is bounded\.

The other conditions of Proposition33in[Bertsekas and Tsitsiklis \(2000\)](https://arxiv.org/html/2608.24146#bib.bib45)are satisfied because of the unbiasedness of the gradient estimates in Algorithm[1](https://arxiv.org/html/2608.24146#alg1)\. Additionally, since the gradient objective, as a variance, is bounded below by zero, we can avoid the case of converging to−∞\-\\inftyaccording to Proposition33\([Bertsekas and Tsitsiklis, 2000](https://arxiv.org/html/2608.24146#bib.bib45)\)\.

By assumptions, we havepωp\_\{\\omega\}is twice\-differentiable, and quotientwπewπθ\\frac\{w\_\{\\pi\_\{e\}\}\}\{w\_\{\\pi\_\{\\theta\}\}\}and the estimatorIS⁡\(πθ,pω,H\)\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)always exist\. Therefore, by the gradient expression in Lemma[4\.1](https://arxiv.org/html/2608.24146#S4.Thmtheorem1), we conclude that∂∂ω​VH∼pω,πθ​\[IS⁡\(πθ,pω,H\)\]\\frac\{\\partial\}\{\\partial\\omega\}V\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)\]is continuously differentiable, verifying condition 1\.

Next, we show the Lipschitz continuity of∂∂ω​VH∼pω,πθ​\[IS⁡\(πθ,pω,H\)\]\\frac\{\\partial\}\{\\partial\\omega\}V\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)\]by verifying the boundedness of its second derivative\.

∂2∂ω2​𝕍H∼pω,πθ​\[IS⁡\(πθ,pω,H\)\]\\displaystyle\\frac\{\\partial^\{2\}\}\{\\partial\\omega^\{2\}\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)\]\(45\)=\\displaystyle=∂∂ω​𝔼H∼pω,πθ​\[IS​\(πe,πθ,H\)2​∑t=0T−1log⁡\(pω​\(St\+1\|St,At\)\)\]\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\textstyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\quantity\[\\IS\(\\pi\_e, \\pi\_\\theta,H\)^2\\sum\_\{t=0\}^\{T\-1\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\) \]\(46\)−2​𝔼H∼pω,πθ​\[IS⁡\(πe,πθ,H\)\]​𝔼H∼pω,πθ​\[IS⁡\(πe,πθ,H\)​∑t=0T−1log⁡\(pω​\(St\+1\|St,At\)\)\]\\displaystyle\-2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]\\textstyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\quantity\[\\IS\(\\pi\_e, \\pi\_\\theta,H\)\\sum\_\{t=0\}^\{T\-1\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\) \]\(47\)=\\displaystyle=∂∂ω​\(∑h\(p⁡\(h\)​mpω​\(h\)​IS​\(πe,πθ,H\)2​∑t=0T−1∂∂ω​log⁡\(pω​\(St\+1\|St,At\)\)\)CLOSE\\displaystyle\\textstyle\\frac\{\\partial\}\{\\partial\\omega\}\\left\(\\sum\_\{h\}\\quantity\(p\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\IS\(\\pi\_e, \\pi\_\\theta,H\)^2\\sum\_\{t=0\}^\{T\-1\} \\gradomega\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\)\\right\.\(48\)−2∑h\(p⁡\(h\)​mpω​\(h\)​IS​\(πe,πθ,H\)\)\\displaystyle\\textstyle\-2\\sum\_\{h\}\\quantity\(p\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\IS\(\\pi\_e, \\pi\_\\theta,H\)\)\(49\)⋅∑h\(p⁡\(h\)​mpω​\(h\)​IS​\(πe,πθ,H\)​∑t=0T−1∂∂ω​log⁡\(pω​\(St\+1\|St,At\)\)\)\)\\displaystyle\\textstyle\\left\.\\cdot\\sum\_\{h\}\\quantity\(p\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\IS\(\\pi\_e, \\pi\_\\theta,H\)\\sum\_\{t=0\}^\{T\-1\} \\gradomega\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\)\\right\)\(By Lemma[4\.1](https://arxiv.org/html/2608.24146#S4.Thmtheorem1)and \([25](https://arxiv.org/html/2608.24146#A1.E25)\)\)=\\displaystyle=∂∂ω​\(∑h\(p⁡\(h\)​mpω​\(h\)​IS​\(πe,πθ,H\)2​∂∂ω​log⁡mpω​\(h\)\)CLOSE\\displaystyle\\textstyle\\frac\{\\partial\}\{\\partial\\omega\}\\left\(\\sum\_\{h\}\\quantity\(p\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\IS\(\\pi\_e, \\pi\_\\theta,H\)^2\\gradomega\\log m\_\{p\_\\omega\}\(h\)\)\\right\.\(51\)−2∑h\(p⁡\(h\)​mpω​\(h\)​IS​\(πe,πθ,H\)\)⋅∑h\(p⁡\(h\)​mpω​\(h\)​IS​\(πe,πθ,H\)​∂∂ω​log⁡mpω​\(h\)\)\)\\displaystyle\\textstyle\\left\.\-2\\sum\_\{h\}\\quantity\(p\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\IS\(\\pi\_e, \\pi\_\\theta,H\)\)\\cdot\\sum\_\{h\}\\quantity\(p\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\IS\(\\pi\_e, \\pi\_\\theta,H\)\\gradomega\\log m\_\{p\_\\omega\}\(h\)\)\\right\)\(52\)=\\displaystyle=∂∂ω​\(∑h\(p⁡\(h\)​mpω​\(h\)​IS​\(πe,πθ,H\)2​1mpω​\(h\)​∂∂ω​mpω​\(h\)\)CLOSE\\displaystyle\\textstyle\\frac\{\\partial\}\{\\partial\\omega\}\\left\(\\sum\_\{h\}\\quantity\(p\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\IS\(\\pi\_e, \\pi\_\\theta,H\)^2\\frac\{1\}\{m\_\{p\_\\omega\}\(h\)\}\\gradomega m\_\{p\_\\omega\}\(h\)\)\\right\.\(53\)−2∑h\(p⁡\(h\)​mpω​\(h\)​IS​\(πe,πθ,H\)\)⋅∑h\(p⁡\(h\)​mpω​\(h\)​IS​\(πe,πθ,H\)​1mpω​\(h\)​∂∂ω​mpω​\(h\)\)\)\\displaystyle\\textstyle\\left\.\-2\\sum\_\{h\}\\quantity\(p\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\IS\(\\pi\_e, \\pi\_\\theta,H\)\)\\cdot\\sum\_\{h\}\\quantity\(p\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\IS\(\\pi\_e, \\pi\_\\theta,H\)\\frac\{1\}\{m\_\{p\_\\omega\}\(h\)\}\\gradomega m\_\{p\_\\omega\}\(h\)\)\\right\)\(54\)=\\displaystyle=∂∂ω​\(∑h\(p⁡\(h\)​IS​\(πe,πθ,H\)2​∂∂ω​mpω​\(h\)\)CLOSE\\displaystyle\\textstyle\\frac\{\\partial\}\{\\partial\\omega\}\\left\(\\sum\_\{h\}\\quantity\(p\(h\)\\IS\(\\pi\_e, \\pi\_\\theta,H\)^2\\gradomega m\_\{p\_\\omega\}\(h\)\)\\right\.\(55\)−2∑h\(p⁡\(h\)​mpω​\(h\)​IS​\(πe,πθ,H\)\)⋅∑h\(p⁡\(h\)​IS​\(πe,πθ,H\)​∂∂ω​mpω​\(h\)\)\)\\displaystyle\\textstyle\\left\.\-2\\sum\_\{h\}\\quantity\(p\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\IS\(\\pi\_e, \\pi\_\\theta,H\)\)\\cdot\\sum\_\{h\}\\quantity\(p\(h\)\\IS\(\\pi\_e, \\pi\_\\theta,H\)\\gradomega m\_\{p\_\\omega\}\(h\)\)\\right\)\(56\)=\\displaystyle=∑hp⁡\(h\)​\(IS​\(πe,πθ,H\)2⏟\(1\)​∂2∂ω2​mpω​\(h\)⏟\(2\)\)\\displaystyle\\textstyle\\sum\_\{h\}p\(h\)\\quantity\(\\underbrace\{\\IS\(\\pi\_e, \\pi\_\\theta,H\)^2\}\_\{\(1\)\}\\underbrace\{\\frac\{\\partial^2\}\{\\partial\\omega^2\}m\_\{p\_\\omega\}\(h\)\}\_\{\(2\)\}\)\(57\)−2​∂∂ω​\[∑h\(p⁡\(h\)​mpω​\(h\)​IS​\(πe,πθ,H\)\)⋅∑h\(p⁡\(h\)​IS​\(πe,πθ,H\)​∂∂ω​mpω​\(h\)\)\]\.\\displaystyle\\textstyle\-2\\frac\{\\partial\}\{\\partial\\omega\}\\quantity\[\\sum\_\{h\}\\qty\(p\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\IS\(\\pi\_e, \\pi\_\\theta,H\)\)\\cdot\\sum\_\{h\}\\qty\(p\(h\)\\IS\(\\pi\_e, \\pi\_\\theta,H\)\\gradomega m\_\{p\_\\omega\}\(h\)\)\]\.\(58\)
We further decompose the term in the square brackets\.

∂∂ω​\[∑h\(p⁡\(h\)​mpω​\(h\)​IS​\(πe,πθ,H\)\)⋅∑h\(p⁡\(h\)​IS​\(πe,πθ,H\)​∂∂ω​mpω​\(h\)\)\]\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\quantity\[\\sum\_\{h\}\\qty\(p\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\IS\(\\pi\_e, \\pi\_\\theta,H\)\)\\cdot\\sum\_\{h\}\\qty\(p\(h\)\\IS\(\\pi\_e, \\pi\_\\theta,H\)\\gradomega m\_\{p\_\\omega\}\(h\)\)\]\(60\)=\\displaystyle=∑hp⁡\(h\)​∂∂ω​\(mpω​\(h\)​IS​\(πe,πθ,H\)\)⋅∑h\(p⁡\(h\)​IS​\(πe,πθ,H\)​∂∂ω​mpω​\(h\)\)\\displaystyle\\sum\_\{h\}p\(h\)\\frac\{\\partial\}\{\\partial\\omega\}\(m\_\{p\_\{\\omega\}\}\(h\)\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\)\\cdot\\sum\_\{h\}\\quantity\(p\(h\)\\IS\(\\pi\_e, \\pi\_\\theta,H\)\\gradomega m\_\{p\_\\omega\}\(h\)\)\(61\)\+∑h\(p⁡\(h\)​mpω​\(h\)​IS​\(πe,πθ,H\)\)⋅∑hp\(h\)∂∂ω\(IS⁡\(πe,πθ,H\)​∂∂ω​mpω​\(h\)\)\\displaystyle\+\\sum\_\{h\}\\quantity\(p\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\IS\(\\pi\_e, \\pi\_\\theta,H\)\)\\cdot\\sum\_\{h\}p\(h\)\\frac\{\\partial\}\{\\partial\\omega\}\\quantity\(\\IS\(\\pi\_e, \\pi\_\\theta,H\)\\gradomega m\_\{p\_\\omega\}\(h\)\)\(62\)=\\displaystyle=∑hp⁡\(h\)​\(IS⁡\(πe,πθ,H\)⏟\(3\)​∂∂ω​mpω​\(h\)⏟\(4\)\)⋅∑hp⁡\(h\)​\(IS⁡\(πe,πθ,H\)​∂∂ω​mpω​\(h\)\)\\displaystyle\\sum\_\{h\}p\(h\)\\quantity\(\\underbrace\{\\IS\(\\pi\_e, \\pi\_\\theta,H\)\}\_\{\(3\)\}\\underbrace\{\\gradomega m\_\{p\_\{\\omega\}\}\(h\)\}\_\{\(4\)\}\)\\cdot\\sum\_\{h\}p\(h\)\\quantity\(\\IS\(\\pi\_e, \\pi\_\\theta,H\)\\gradomega m\_\{p\_\\omega\}\(h\)\)\(63\)\+∑hp\(h\)\(mpω​\(h\)⏟\(5\)​IS​\(πe,πθ,H\)\)⋅∑hp\(h\)\(IS⁡\(πe,πθ,H\)​∂2∂ω2​mpω​\(h\)\)\.\\displaystyle\+\\sum\_\{h\}p\(h\)\\quantity\(\\underbrace\{m\_\{p\_\{\\omega\}\}\(h\)\}\_\{\(5\)\}\\IS\(\\pi\_e, \\pi\_\\theta,H\)\)\\cdot\\sum\_\{h\}p\(h\)\\quantity\(\\IS\(\\pi\_e, \\pi\_\\theta,H\)\\frac\{\\partial^2\}\{\\partial\\omega^2\}m\_\{p\_\\omega\}\(h\)\)\.\(64\)
Notice that sincep⁡\(h\)=p0​\(S0\)​∏t=0T−1πθ​\(At\|St\)≤1p\(h\)=p\_\{0\}\(S\_\{0\}\)\\prod\_\{t=0\}^\{T\-1\}\\pi\_\{\\theta\}\(A\_\{t\}\|S\_\{t\}\)\\leq 1by \([24](https://arxiv.org/html/2608.24146#A1.E24)\),p⁡\(h\)p\(h\)is bounded above\. We then analyze the boundedness of∂2∂ω2​VH∼pω,πθ​\[IS⁡\(πθ,pω,H\)\]\\frac\{\\partial^\{2\}\}\{\\partial\\omega^\{2\}\}V\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)\]through the above55terms\.

For \(1\) and \(3\), the quotientπe​\(a\|s\)πθ​\(a\|s\)\\frac\{\\pi\_\{e\}\(a\|s\)\}\{\\pi\_\{\\theta\}\(a\|s\)\}is bounded above by assumption\. Besides, since the reward is bounded, so isg⁡\(h\)g\(h\)\. Therefore, both \(1\),IS​\(πe,πθ,H\)2\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)^\{2\}and \(3\)IS⁡\(πe,πθ,H\)\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)are bounded\.

For \(5\), it is bounded becausempω​\(h\)=∏t=0T−1pω​\(St\+1\|St,At\)≤1m\_\{p\_\{\\omega\}\}\(h\)=\\prod\_\{t=0\}^\{T\-1\}p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\\leq 1\. Then, for \(4\),

∂∂ω​mpω​\(h\)=\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}m\_\{p\_\{\\omega\}\}\(h\)=∂∂ω​∏t=0T−1pω​\(St\+1\|St,At\)\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\prod\_\{t=0\}^\{T\-1\}p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\(66\)=\\displaystyle=∑t=0T−1∂∂ω​pω​\(St\+1\|St,At\)​∏i=0T−1pω​\(Si\+1\|Si,Ai\)pω​\(St\+1\|St,At\)\.\\displaystyle\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\\frac\{\\prod\_\{i=0\}^\{T\-1\}p\_\{\\omega\}\(S\_\{i\+1\}\|S\_\{i\},A\_\{i\}\)\}\{p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\}\.\(67\)Here,∂∂ω​pω​\(St\+1\|St,At\)\\frac\{\\partial\}\{\\partial\\omega\}p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)is bounded by construction and∏i=0T−1pω​\(Si\+1\|Si,Ai\)pω​\(St\+1\|St,At\)≤1\\frac\{\\prod\_\{i=0\}^\{T\-1\}p\_\{\\omega\}\(S\_\{i\+1\}\|S\_\{i\},A\_\{i\}\)\}\{p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\}\\leq 1\. Thus, \(4\) is bounded\. Lastly, for \(2\)

∂2∂ω2​mpω​\(h\)\\displaystyle\\frac\{\\partial^\{2\}\}\{\\partial\\omega^\{2\}\}m\_\{p\_\{\\omega\}\}\(h\)\(68\)=\\displaystyle=∂∂ω​∑t=0T−1∂∂ω​pω​\(St\+1\|St,At\)​∏i=0T−1pω​\(Si\+1\|Si,Ai\)pω​\(St\+1\|St,At\)\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\\frac\{\\prod\_\{i=0\}^\{T\-1\}p\_\{\\omega\}\(S\_\{i\+1\}\|S\_\{i\},A\_\{i\}\)\}\{p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\}\(69\)=\\displaystyle=∂∂ω​∑t=0T−1∂∂ω​pω​\(St\+1\|St,At\)​∏i≠tpω​\(Si\+1\|Si,Ai\)\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\\prod\_\{i\\neq t\}p\_\{\\omega\}\(S\_\{i\+1\}\|S\_\{i\},A\_\{i\}\)\(70\)=\\displaystyle=∑t=0T−1∂2∂ω2​pω​\(St\+1\|St,At\)​∏i≠tpω​\(Si\+1\|Si,Ai\)\+∂∂ω​pω​\(St\+1\|St,At\)\\displaystyle\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial^\{2\}\}\{\\partial\\omega^\{2\}\}p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\\prod\_\{i\\neq t\}p\_\{\\omega\}\(S\_\{i\+1\}\|S\_\{i\},A\_\{i\}\)\+\\frac\{\\partial\}\{\\partial\\omega\}p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\(71\)⋅∑i≠t∂∂ω​pω​\(Si\+1\|Si,Ai\)​∏j≠t,ipω​\(Sj\+1\|Sj,Aj\),\\displaystyle\\cdot\\sum\_\{i\\neq t\}\\frac\{\\partial\}\{\\partial\\omega\}p\_\{\\omega\}\(S\_\{i\+1\}\|S\_\{i\},A\_\{i\}\)\\prod\_\{j\\neq t,i\}p\_\{\\omega\}\(S\_\{j\+1\}\|S\_\{j\},A\_\{j\}\),\(72\)which is bounded becausepωp\_\{\\omega\}is constructed to be twice differentiable with bounded first and second derivatives\.

Therefore, we conclude that the gradient objective∂∂ω​VH∼pω,πθ​\[IS⁡\(πθ,pω,H\)\]\\frac\{\\partial\}\{\\partial\\omega\}V\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)\]is Lipschitz continuous w\.r\.t\.ω\\omega, verifying condition 1\.

Finally, we show that the variance of the gradient estimate used by Algorithm[1](https://arxiv.org/html/2608.24146#alg1)is bounded\. According to Algorithm[1](https://arxiv.org/html/2608.24146#alg1), we use the unbiased estimate as

∂∂ω​VH∼pω,πθ​\[IS⁡\(πθ,pω,H\)\]≈\\displaystyle\\textstyle\\frac\{\\partial\}\{\\partial\\omega\}V\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)\]\\approxIS​\(πθ,pω,H\)2​∑t=0T−1∂∂ω​log⁡\(pω​\(St\+1\|St,At\)\)⏟A\\displaystyle\\textstyle\\underbrace\{\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)^\{2\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\}\_\{A\}\(73\)−2​IS​\(πθ,pω,H\)​IS​\(πθ,pω,H\)​∑t=0T−1∂∂ω​log⁡\(pω​\(St\+1\|St,At\)\)⏟B\.\\displaystyle\\textstyle\-\\underbrace\{2\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\}\_\{B\}\.\(74\)Then, the variance of the estimate is decomposed into

𝕍⁡\[A\]\+𝕍⁡\[B\]\+2​C​o​v​\[A,B\],\\displaystyle\\mathbb\{V\}\[A\]\+\\mathbb\{V\}\[B\]\+2\\mathrm\{Cov\}\[A,B\],\(75\)whereCov⁡\[A,B\]≤𝕍⁡\[A\]⋅𝕍⁡\[B\]\\mathrm\{Cov\}\[A,B\]\\leq\\sqrt\{\\mathbb\{V\}\[A\]\}\\cdot\\sqrt\{\\mathbb\{V\}\[B\]\}by the Cauchy\-Schwarz inequality\. Thus, it is sufficient to show the boundedness of𝕍⁡\[A\]\\mathbb\{V\}\[A\]and𝕍⁡\[B\]\\mathbb\{V\}\[B\]\. For𝕍⁡\[A\]\\mathbb\{V\}\[A\], since the variance of a bounded random variable is bounded, we aim to demonstrate that for any trajectoryhh, the termIS​\(πθ,pω,H\)2​∑t=0T−1log⁡\(pω​\(St\+1\|St,At\)\)\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)^\{2\}\\sum\_\{t=0\}^\{T\-1\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)is bounded\.

IS​\(πθ,pω,H\)2​∑t=0T−1∂∂ω​log⁡\(pω​\(St\+1\|St,At\)\)\\displaystyle\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)^\{2\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\(76\)=\\displaystyle=IS​\(πθ,pω,H\)2​∑t=0T−1∂∂ω​log⁡\(pω​\(St\+1\|St,At\)\)\\displaystyle\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)^\{2\}\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\(77\)=\\displaystyle=IS​\(πθ,pω,H\)2​∂∂ω​log⁡mpω​\(h\)\\displaystyle\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)^\{2\}\\frac\{\\partial\}\{\\partial\\omega\}\\log m\_\{p\_\{\\omega\}\}\(h\)\(78\)=\\displaystyle=IS​\(πθ,pω,H\)2​∂∂ω​mpω​\(h\)mpω​\(h\)\.\\displaystyle\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)^\{2\}\\frac\{\\frac\{\\partial\}\{\\partial\\omega\}m\_\{p\_\{\\omega\}\}\(h\)\}\{m\_\{p\_\{\\omega\}\}\(h\)\}\.\(79\)The boundedness ofIS​\(πθ,pω,H\)2\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)^\{2\}and∂∂ω​mpω​\(h\)\\frac\{\\partial\}\{\\partial\\omega\}m\_\{p\_\{\\omega\}\}\(h\)is shown by the argument above for terms \(3\) and \(4\)\. For the boundedness of1mpω​\(h\)=1∏t=0T−1pω​\(St\+1\|St,At\)\\frac\{1\}\{m\_\{p\_\{\\omega\}\}\(h\)\}=\\frac\{1\}\{\\prod\_\{t=0\}^\{T\-1\}p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\}, we invoke the Extreme Value Theorem\. Sincepω​\(s′\|s,a\)p\_\{\\omega\}\(s^\{\\prime\}\|s,a\)is strictly positive \(under softmax parameterization\) and continuous on the finite state\-action space𝒮×𝒜×𝒮\\mathcal\{S\}\\times\\mathcal\{A\}\\times\\mathcal\{S\}and the compact parameter spaceΩ\\Omega\(compactness ofΩ\\Omegais assumed in our background\), the Extreme Value Theorem ensures thatpωp\_\{\\omega\}attains a strictly positive minimumc≐mins,a,s′,ω⁡pω​\(s′\|s,a\)\>0c\\doteq\\min\_\{s,a,s^\{\\prime\},\\omega\}p\_\{\\omega\}\(s^\{\\prime\}\|s,a\)\>0\. Since the trajectory lengthTTis finite, we have1mpω​\(h\)≤\(1/c\)T<∞\\frac\{1\}\{m\_\{p\_\{\\omega\}\}\(h\)\}\\leq\(1/c\)^\{T\}<\\inftyuniformly inhhandω\\omega\. Thus, we conclude that𝕍⁡\[A\]\\mathbb\{V\}\[A\]is bounded\.

Next, we decompose termBBinto two parts because of the different samples used to estimate them:

IS⁡\(πθ,pω,H\)⏟C​IS⁡\(πθ,pω,H\)​∑t=0T−1∂∂ω​log⁡\(pω​\(St\+1\|St,At\)\)⏟D\.\\displaystyle\\underbrace\{\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)\}\_\{C\}\\underbrace\{\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)\\textstyle\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\}\_\{D\}\.\(81\)Since in Algorithm[1](https://arxiv.org/html/2608.24146#alg1)the cross\-product estimator is computed by sample splitting \(the firstk/2k/2trajectories estimateCCand the secondk/2k/2trajectories estimateDD\),CCandDDare independent\. Consequently, by the standard variance identity for products of independent random variables,

𝕍⁡\[B\]=𝕍⁡\[C​D\]=𝔼⁡\[C2\]​𝕍​\[D\]\+𝔼​\[D\]2​𝕍​\[C\]\.\\displaystyle\\mathbb\{V\}\[B\]=\\mathbb\{V\}\[CD\]=\\mathbb\{E\}\[C^\{2\}\]\\mathbb\{V\}\[D\]\+\\mathbb\{E\}\[D\]^\{2\}\\mathbb\{V\}\[C\]\.\(82\)We show their boundedness term by term\.

𝔼⁡\[C2\]=𝔼H∼pω,πθ​\[IS​\(πθ,pω,H\)2\]=∑hp⁡\(h\)​mpω​\(h\)​IS​\(πe,πθ,H\)2,\\displaystyle\\mathbb\{E\}\[C^\{2\}\]=\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)^\{2\}\]=\\sum\_\{h\}p\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)^\{2\},\(83\)where each term is shown to be bounded above\. Next, by Jensen’s inequality and the derivation from \([79](https://arxiv.org/html/2608.24146#A1.E79)\),

𝔼​\[D\]2≤𝔼⁡\[D2\]=∑hp⁡\(h\)​mpω​\(h\)​IS​\(πe,πθ,H\)2​\(∂∂ω​mpω​\(h\)mpω​\(h\)\)2,\\displaystyle\\mathbb\{E\}\[D\]^\{2\}\\leq\\mathbb\{E\}\[D^\{2\}\]=\\sum\_\{h\}p\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)^\{2\}\\quantity\(\\frac\{\\gradomega m\_\{p\_\\omega\}\(h\)\}\{m\_\{p\_\\omega\}\(h\)\}\)^\{2\},\(84\)where the boundedness of the right\-hand side follows from the analysis of \([83](https://arxiv.org/html/2608.24146#A1.E83)\) and \([79](https://arxiv.org/html/2608.24146#A1.E79)\), and hence𝔼​\[D\]2\\mathbb\{E\}\[D\]^\{2\}is bounded as well\.

As for the two variance terms,𝕍⁡\[C\]\\mathbb\{V\}\[C\]and𝕍⁡\[D\]\\mathbb\{V\}\[D\], we show the boundedness of the random variableCCandDDfor each trajectoryhh, whereIS⁡\(πθ,pω,H\)\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)is shown to be bounded in term\(3\)\(3\)above, and the boundedness of∑t=0T−1∂∂ω​log⁡\(pω​\(St\+1\|St,At\)\)\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)is incorporated in \([79](https://arxiv.org/html/2608.24146#A1.E79)\)\.

Therefore, we conclude that the variance of our estimate is bounded\. By far, we show that the three conditions of Proposition 3 in[Bertsekas and Tsitsiklis \(2000\)](https://arxiv.org/html/2608.24146#bib.bib45)are satisfied, demonstrating the convergence of Algorithm[1](https://arxiv.org/html/2608.24146#alg1)\.

∎

### A\.4Proof of Theorem[4\.3](https://arxiv.org/html/2608.24146#S4.Thmtheorem3)

###### Proof\.

See[4\.3](https://arxiv.org/html/2608.24146#S4.Thmtheorem3)We begin by manipulating the KL\-divergence term\.

KL\(Pr⁡\(H\|pω\)∥Pr⁡\(H\|pω0\)\)=\\displaystyle\{\\text\{\\rm KL\}\}\(\\Pr\(H\|p\_\{\\omega\}\)\\\|\\Pr\(H\|p\_\{\\omega\_0\}\)\)=𝔼H∼pω,πθ​\[log⁡Pr⁡\(H\|pω\)Pr⁡\(H\|pω0\)\]\\displaystyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\quantity\[\\log\\frac\{\\Pr\(H\|p\_\{\\omega\}\)\}\{\\Pr\(H\|p\_\{\\omega\_0\}\)\}\]\(85\)=\\displaystyle=𝔼H∼pω,πθ​\[log⁡mpω​\(H\)mpω0​\(H\)\]\\displaystyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\quantity\[\\log\\frac\{m\_\{p\_\{\\omega\}\}\(H\)\}\{m\_\{p\_\{\\omega\_0\}\}\(H\)\}\]\(By \([25](https://arxiv.org/html/2608.24146#A1.E25)\)\)=\\displaystyle=𝔼H∼pω,πθ​\[log⁡mpω​\(H\)−log⁡mpω0​\(H\)\]\.\\displaystyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\quantity\[\\log m\_\{p\_\{\\omega\}\}\(H\)\-\\log m\_\{p\_\{\\omega\_0\}\}\(H\)\]\.\(86\)Next, we decompose the following gradient:

∂∂ω​log⁡mpω​\(H\)\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\log m\_\{p\_\{\\omega\}\}\(H\)\(87\)=\\displaystyle=∑t=0T−1∂∂ω​log⁡pω​\(St\+1\|St,At\)\\displaystyle\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}\\log p\_\{\\omega\}\(S\_\{t\+1\}\|S\_\{t\},A\_\{t\}\)\(88\)=\\displaystyle=∑t=0T−1∂∂ω​log⁡\(pω​\(St\+1\|St,At\)\)\.\\displaystyle\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\.\(By definition\)Then, we take the gradient of the KL\-divergence with respect toω\\omega:

∂∂ωKL\(Pr⁡\(H\|pω\)∥Pr⁡\(H\|pω0\)\)\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\{\\text\{\\rm KL\}\}\(\\Pr\(H\|p\_\{\\omega\}\)\\\|\\Pr\(H\|p\_\{\\omega\_0\}\)\)\(90\)=\\displaystyle=∂∂ω​𝔼H∼pω,πθ​\[log⁡mpω​\(H\)−log⁡mpω0​\(H\)\]\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\quantity\[\\log m\_\{p\_\{\\omega\}\}\(H\)\-\\log m\_\{p\_\{\\omega\_0\}\}\(H\)\]\(91\)=\\displaystyle=∂∂ω​∑hPr⁡\(H=h\|pω\)​\[log⁡mpω​\(h\)−log⁡mpω0​\(h\)\]\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\sum\_\{h\}\\Pr\(H=h\|p\_\\omega\)\\quantity\[\\log m\_\{p\_\{\\omega\}\}\(h\)\-\\log m\_\{p\_\{\\omega\_0\}\}\(h\)\]\(92\)=\\displaystyle=∂∂ω​∑hp⁡\(h\)​mpω​\(h\)​\[log⁡mpω​\(h\)−log⁡mpω0​\(h\)\]\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\sum\_\{h\}p\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\quantity\[\\log m\_\{p\_\{\\omega\}\}\(h\)\-\\log m\_\{p\_\{\\omega\_0\}\}\(h\)\]\(By \([25](https://arxiv.org/html/2608.24146#A1.E25)\)\)=\\displaystyle=∑hp⁡\(h\)​\[∂∂ω​mpω​\(h\)​log⁡mpω​\(h\)−log⁡mpω0​\(h\)​∂∂ω​mpω​\(h\)\]\\displaystyle\\sum\_\{h\}p\(h\)\\quantity\[\\gradomega m\_\{p\_\{\\omega\}\}\(h\)\\log m\_\{p\_\{\\omega\}\}\(h\)\-\\log m\_\{p\_\{\\omega\_0\}\}\(h\)\\gradomega m\_\{p\_\{\\omega\}\}\(h\)\]\(93\)=\\displaystyle=∑hp\(h\)\[logmpω\(h\)∂∂ωmpω\(h\)\+mpω\(h\)∂∂ωlogmpω\(h\)\\displaystyle\\sum\_\{h\}p\(h\)\\left\[\\log m\_\{p\_\{\\omega\}\}\(h\)\\frac\{\\partial\}\{\\partial\\omega\}m\_\{p\_\{\\omega\}\}\(h\)\+m\_\{p\_\{\\omega\}\}\(h\)\\frac\{\\partial\}\{\\partial\\omega\}\\log m\_\{p\_\{\\omega\}\}\(h\)\\right\.\(94\)−logmpω0\(h\)mpω\(h\)∑t=0T−1∂∂ωlog⁡\(pω​\(St\+1\|St,At\)\)\]\\displaystyle\\left\.\-\\log m\_\{p\_\{\\omega\_\{0\}\}\}\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\\right\]\(By \([33](https://arxiv.org/html/2608.24146#A1.E33)\)\)=\\displaystyle=∑hp\(h\)\[logmpω\(h\)mpω\(h\)∑t=0T−1∂∂ωlog⁡\(pω​\(St\+1\|St,At\)\)\+mpω\(h\)∑t=0T−1∂∂ωlog⁡\(pω​\(St\+1\|St,At\)\)\\displaystyle\\sum\_\{h\}p\(h\)\\left\[\\log m\_\{p\_\{\\omega\}\}\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\+m\_\{p\_\{\\omega\}\}\(h\)\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\\right\.\(96\)−logmpω0\(h\)mpω\(h\)∑t=0T−1∂∂ωlog⁡\(pω​\(St\+1\|St,At\)\)\]\\displaystyle\\left\.\-\\log m\_\{p\_\{\\omega\_\{0\}\}\}\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\\right\]\(By \([33](https://arxiv.org/html/2608.24146#A1.E33)\) \([87](https://arxiv.org/html/2608.24146#A1.E87)\)\)=\\displaystyle=∑hp⁡\(h\)​mpω​\(h\)​∑t=0T−1∂∂ω​log⁡\(pω​\(St\+1\|St,At\)\)​\[log⁡mpω​\(h\)\+1−log⁡mpω0​\(h\)\]\\displaystyle\\sum\_\{h\}p\(h\)m\_\{p\_\{\\omega\}\}\(h\)\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\omega\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\\quantity\[\\log m\_\{p\_\{\\omega\}\}\(h\)\+1\-\\log m\_\{p\_\{\\omega\_0\}\}\(h\)\]\(97\)=\\displaystyle=∑hPr⁡\(H=h\|pω\)​∑t=0T−1\[∂∂ω​log⁡\(pω​\(St\+1\|St,At\)\)\]​\[log⁡mpω​\(h\)\+1−log⁡mpω0​\(h\)\]\\displaystyle\\sum\_\{h\}\\Pr\(H=h\|p\_\\omega\)\\sum\_\{t=0\}^\{T\-1\}\\quantity\[\\gradomega\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\]\\quantity\[\\log m\_\{p\_\{\\omega\}\}\(h\)\+1\-\\log m\_\{p\_\{\\omega\_0\}\}\(h\)\]\(By \([25](https://arxiv.org/html/2608.24146#A1.E25)\)\)=\\displaystyle=𝔼H∼pω,πθ​\[\(∂∂ω​ℓpω\)​\(1\+ℓpω−ℓpω0\)\]\.\\displaystyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\quantity\[\\qty\(\\gradomega\\ell\_\{p\_\\omega\}\)\\qty\(1\+\\ell\_\{p\_\\omega\}\-\\ell\_\{p\_\{\\omega\_0\}\}\)\]\.\(By \([23](https://arxiv.org/html/2608.24146#A1.E23)\)\)Thus,

∂∂ω𝕍H∼pω,πθ\[OPE\(πe,πθ,H\)\]−ηKL\(Pr⁡\(H\|pω\)∥Pr⁡\(H\|pω0\)\)\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\left\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\\right\]\-\\eta\{\\text\{\\rm KL\}\}\(\\Pr\(H\|p\_\{\\omega\}\)\\\|\\Pr\(H\|p\_\{\\omega\_0\}\)\)\(99\)=\\displaystyle=𝔼H∼pω,πθ​\[OPE​\(πe,πθ,H\)2​∑t=0T−1log⁡\(pω​\(St\+1\|St,At\)\)\]−2​𝔼H∼pω,πθ​\[OPE⁡\(πe,πθ,H\)\]\\displaystyle\\textstyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\quantity\[\\OPE\(\\pi\_e, \\pi\_\\theta,H\)^2\\sum\_\{t=0\}^\{T\-1\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\) \]\-2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]\(100\)⋅𝔼H∼pω,πθ\[OPE⁡\(πe,πθ,H\)​∑t=0T−1log⁡\(pω​\(St\+1\|St,At\)\)\]−η∂∂ωKL\(Pr⁡\(H\|pω\)∥Pr⁡\(H\|pω0\)\)\\displaystyle\\cdot\\textstyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\quantity\[\\OPE\(\\pi\_e, \\pi\_\\theta, H\)\\sum\_\{t=0\}^\{T\-1\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\) \]\-\\eta\\frac\{\\partial\}\{\\partial\\omega\}\{\\text\{\\rm KL\}\}\(\\Pr\(H\|p\_\{\\omega\}\)\\\|\\Pr\(H\|p\_\{\\omega\_0\}\)\)\(By Lemma[4\.1](https://arxiv.org/html/2608.24146#S4.Thmtheorem1)\)=\\displaystyle=𝔼H∼pω,πθ​\[OPE​\(πe,πθ,H\)2​∂∂ω​ℓpω\]−2​𝔼H∼pω,πθ​\[OPE⁡\(πe,πθ,H\)\]​𝔼H∼pω,πθ​\[OPE⁡\(πe,πθ,H\)​∂∂ω​ℓpω\]\\displaystyle\\textstyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\quantity\[\\OPE\(\\pi\_e, \\pi\_\\theta,H\)^2\\gradomega\\ell\_\{p\_\\omega\} \]\-2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]\\textstyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\quantity\[\\OPE\(\\pi\_e, \\pi\_\\theta, H\)\\gradomega\\ell\_\{p\_\\omega\} \]\(101\)−η​𝔼H∼pω,πθ​\[\(∂∂ω​ℓpω\)​\(1\+ℓpω−ℓpω0\)\]\.\\displaystyle\\textstyle\-\\eta\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\quantity\[\\qty\(\\gradomega\\ell\_\{p\_\\omega\}\)\\qty\(1\+\\ell\_\{p\_\\omega\}\-\\ell\_\{p\_\{\\omega\_0\}\}\)\]\.\(By \([90](https://arxiv.org/html/2608.24146#A1.E90)\)\)∎

### A\.5Proof of Theorem[4\.4](https://arxiv.org/html/2608.24146#S4.Thmtheorem4)

See[4\.4](https://arxiv.org/html/2608.24146#S4.Thmtheorem4)

###### Proof\.

For simplification, we definewπ​\(h\)≐∏t=0T−1π⁡\(At\|St\)w\_\{\\pi\}\(h\)\\doteq\\prod\_\{t=0\}^\{T\-1\}\\pi\(A\_\{t\}\|S\_\{t\}\)under trajectoryhh\. Then,

∂∂ω​𝕍H∼pω0,πθ​\[OPE⁡\(πe,πθ,pω,H\)\]\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},p\_\{\\omega\},H\)\]\(103\)=\\displaystyle=∂∂ω​\(𝔼H∼pω′​\[OPE2​\(πe,πθ,pω,H\)\]−𝔼H∼pω′​\[OPE⁡\(πe,πθ,pω,H\)\]2\)\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\quantity\(\\E\_\{\\Hsampleoff\}\[\\mathrm\{OPE\}^2\(\\pi\_e,\\pi\_\{\\theta\}, p\_\\omega,H\)\]\-\\E\_\{\\Hsampleoff\}\[\\mathrm\{OPE\}\(\\pi\_e,\\pi\_\{\\theta\}, p\_\\omega,H\)\]^2\)\(104\)=\\displaystyle=∂∂ω​\(𝔼H∼pω′​\[mpω2​\(H\)mpω02​\(H\)​OPE2​\(πe,πθ,H\)\]−𝔼H∼pω′​\[mpω​\(H\)mpω0​\(H\)​OPE​\(πe,πθ,H\)\]2\)\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\quantity\(\\E\_\{\\Hsampleoff\}\\qty\[\\frac\{m^2\_\{p\_\\omega\}\(H\)\}\{m^2\_\{p\_\{\\omega\_0\}\}\(H\)\}\\mathrm\{OPE\}^2\(\\pi\_e,\\pi\_\{\\theta\}, H\)\]\-\\E\_\{\\Hsampleoff\}\\qty\[\\frac\{m\_\{p\_\\omega\}\(H\)\}\{m\_\{p\_\{\\omega\_0\}\}\(H\)\}\\mathrm\{OPE\}\(\\pi\_e,\\pi\_\{\\theta\}, H\)\]^2\)\(105\)=\\displaystyle=∂∂ω​∑h\(Pr⁡\(H=h\|pω0\)​mpω2​\(H\)mpω02​\(H\)​OPE2​\(πe,πθ,H\)\)−2​𝔼H∼pω′​\[OPE⁡\(πe,πθ,pω,H\)\]\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\sum\_\{h\}\\quantity\(\\Pr\(H=h\|p\_\{\\omega\_0\}\)\\frac\{m^2\_\{p\_\\omega\}\(H\)\}\{m^2\_\{p\_\{\\omega\_0\}\}\(H\)\}\\mathrm\{OPE\}^2\(\\pi\_e,\\pi\_\{\\theta\}, H\)\)\-2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega^\{\\prime\}\}\}\\quantity\[\\mathrm\{OPE\}\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\)\]\(106\)∂∂ω​𝔼H∼pω′​\[mpω​\(H\)mpω0​\(H\)​OPE​\(πe,πθ,H\)\]\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\mathbb\{E\}\_\{H\\sim p\_\{\\omega^\{\\prime\}\}\}\\quantity\[\\frac\{m\_\{p\_\\omega\}\(H\)\}\{m\_\{p\_\{\\omega\_0\}\}\(H\)\}\\mathrm\{OPE\}\(\\pi\_e,\\pi\_\{\\theta\}, H\)\]\(107\)=\\displaystyle=∑h\(p⁡\(h\)​1mpω0​\(H\)​OPE2​\(πe,πθ,H\)​∂∂ω​mpω2​\(h\)\)\\displaystyle\\sum\_\{h\}\\quantity\(p\(h\)\\frac\{1\}\{m\_\{p\_\{\\omega\_0\}\}\(H\)\}\\mathrm\{OPE\}^2\(\\pi\_e,\\pi\_\{\\theta\}, H\)\\gradomega m^2\_\{p\_\\omega\}\(h\)\)\(108\)−2𝔼H∼pω′\[OPE⁡\(πe,πθ,pω,H\)\]∂∂ω∑h\(p⁡\(h\)​mpω0​\(h\)​mpω​\(h\)mpω0​\(h\)​OPE​\(πe,πθ,H\)\)\\displaystyle\-2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega^\{\\prime\}\}\}\\quantity\[\\OPE\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\)\]\\frac\{\\partial\}\{\\partial\\omega\}\\sum\_\{h\}\\quantity\(p\(h\)m\_\{p\_\{\\omega\_0\}\(h\)\} \\frac\{m\_\{p\_\\omega\}\(h\)\}\{m\_\{p\_\{\\omega\_0\}\}\(h\)\}\\OPE\(\\pi\_e, \\pi\_\\theta, H\) \)\(By \([25](https://arxiv.org/html/2608.24146#A1.E25)\)\)=\\displaystyle=2​∑h\(p⁡\(h\)​mpω​\(h\)mpω0​\(h\)​OPE2​\(πe,πθ,H\)​∂∂ω​mpω​\(h\)\)\\displaystyle 2\\sum\_\{h\}\\quantity\(p\(h\)\\frac\{m\_\{p\_\\omega\}\(h\)\}\{m\_\{p\_\{\\omega\_0\}\}\(h\)\}\\mathrm\{OPE\}^2\(\\pi\_e,\\pi\_\{\\theta\}, H\)\\gradomega m\_\{p\_\\omega\}\(h\)\)\(109\)−2𝔼H∼pω′\[OPE⁡\(πe,πθ,pω,H\)\]∑h\(p⁡\(h\)​OPE​\(πe,πθ,H\)​∂∂ω​mpω​\(h\)\)\\displaystyle\-2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega^\{\\prime\}\}\}\\quantity\[\\OPE\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\)\]\\sum\_\{h\}\\quantity\(p\(h\)\\OPE\(\\pi\_e, \\pi\_\\theta, H\) \\gradomega m\_\{p\_\\omega\}\(h\)\)\(By \([25](https://arxiv.org/html/2608.24146#A1.E25)\)\)=\\displaystyle=2​∑h\(p⁡\(h\)​OPE2​\(πe,πθ,H\)​mpω​\(h\)mpω0​\(h\)​mpω​\(h\)​∂∂ω​ℓpω\)\\displaystyle 2\\sum\_\{h\}\\quantity\(p\(h\)\\mathrm\{OPE\}^2\(\\pi\_e,\\pi\_\{\\theta\}, H\)\\frac\{m\_\{p\_\\omega\}\(h\)\}\{m\_\{p\_\{\\omega\_0\}\}\(h\)\}m\_\{p\_\\omega\}\(h\)\\gradomega\\ell\_\{p\_\\omega\} \)\(110\)−2𝔼H∼pω′\[OPE⁡\(πe,πθ,pω,H\)\]∑h\(p⁡\(h\)​OPE​\(πe,πθ,H\)​mpω​\(h\)​∂∂ω​ℓpω\)\\displaystyle\-2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega^\{\\prime\}\}\}\\quantity\[\\OPE\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\)\]\\sum\_\{h\}\\quantity\( p\(h\)\\OPE\(\\pi\_e, \\pi\_\\theta, H\)m\_\{p\_\\omega\}\(h\)\\gradomega\\ell\_\{p\_\\omega\} \)\(By \([33](https://arxiv.org/html/2608.24146#A1.E33)\)\)=\\displaystyle=2​∑h\(p⁡\(h\)​mpω0​\(h\)​mpω2​\(h\)mpω02​\(h\)​OPE2​\(πe,πθ,H\)​∂∂ω​ℓpω\)\\displaystyle 2\\sum\_\{h\}\\quantity\(p\(h\) m\_\{p\_\{\\omega\_0\}\}\(h\) \\frac\{m^2\_\{p\_\\omega\}\(h\)\}\{m^2\_\{p\_\{\\omega\_0\}\}\(h\)\}\\mathrm\{OPE\}^2\(\\pi\_e,\\pi\_\{\\theta\}, H\)\\gradomega\\ell\_\{p\_\\omega\} \)\(111\)−2​𝔼H∼pω′​\[OPE⁡\(πe,πθ,pω,H\)\]\\displaystyle\-2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega^\{\\prime\}\}\}\\quantity\[\\OPE\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\)\]\(112\)⋅∑h\(p⁡\(h\)​mpω0​\(h\)​mpω​\(h\)mpω0​\(h\)​OPE​\(πe,πθ,H\)​∑t=0T−1log⁡\(pω​\(St\+1\|St,At\)\)\)\\displaystyle\\cdot\\sum\_\{h\}\\quantity\( p\(h\)m\_\{p\_\{\\omega\_0\}\}\(h\)\\frac\{m\_\{p\_\\omega\}\(h\)\}\{m\_\{p\_\{\\omega\_0\}\}\(h\)\}\\OPE\(\\pi\_e, \\pi\_\\theta, H\)\\sum\_\{t=0\}^\{T\-1\}\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\) \)\(By \([33](https://arxiv.org/html/2608.24146#A1.E33)\)\)=\\displaystyle=2​∑h\(Pr⁡\(H=h\|pω0\)​OPE2​\(πe,πθ,pω,H\)​∂∂ω​ℓpω\)\\displaystyle 2\\sum\_\{h\}\\quantity\(\\Pr\(H=h\|p\_\{\\omega\_0\}\)\\mathrm\{OPE\}^2\(\\pi\_e,\\pi\_\{\\theta\}, p\_\\omega,H\)\\gradomega\\ell\_\{p\_\\omega\} \)\(113\)−2​𝔼H∼pω′​\[OPE⁡\(πe,πθ,pω,H\)\]\\displaystyle\-2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega^\{\\prime\}\}\}\\quantity\[\\OPE\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\)\]\(114\)⋅∑h\(Pr⁡\(H=h\|pω0\)​OPE​\(πe,πθ,pω,H\)​∑t=0T−1∂∂ω​log⁡\(pω​\(St\+1\|St,At\)\)\)\\displaystyle\\cdot\\sum\_\{h\}\\quantity\(\\Pr\(H=h\|p\_\{\\omega\_0\}\)\\OPE\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\) \\sum\_\{t=0\}^\{T\-1\}\\gradomega\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\)\(By \([25](https://arxiv.org/html/2608.24146#A1.E25)\)\)=\\displaystyle=2​𝔼H∼pω′​\[OPE2​\(πe,πθ,pω,H\)​∂∂ω​ℓpω\]\\displaystyle 2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega^\{\\prime\}\}\}\\quantity\[\\mathrm\{OPE\}^2\(\\pi\_e,\\pi\_\{\\theta\}, p\_\\omega,H\)\\gradomega\\ell\_\{p\_\\omega\} \]\(116\)−2​𝔼H∼pω′​\[OPE⁡\(πe,πθ,pω,H\)\]​𝔼H∼pω′​\[OPE⁡\(πe,πθ,pω,H\)​∂∂ω​ℓpω\]\.\\displaystyle\-2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega^\{\\prime\}\}\}\\quantity\[\\mathrm\{OPE\}\(\\pi\_e,\\pi\_\{\\theta\}, p\_\\omega,H\)\]\\mathbb\{E\}\_\{H\\sim p\_\{\\omega^\{\\prime\}\}\}\\quantity\[\\mathrm\{OPE\}\(\\pi\_e,\\pi\_\{\\theta\}, p\_\\omega,H\)\\gradomega\\ell\_\{p\_\\omega\} \]\.\(117\)∎

### A\.6Proof of Theorem[4\.5](https://arxiv.org/html/2608.24146#S4.Thmtheorem5)

See[4\.5](https://arxiv.org/html/2608.24146#S4.Thmtheorem5)The KL\-divergence between two probability distributionppandqqis defined asKL\(p∥q\)≐𝔼X∼p\[log⁡p⁡\(X\)q⁡\(X\)\]\{\\text\{\\rm KL\}\}\(p\\\|q\)\\doteq\\mathbb\{E\}\_\{X\\sim p\}\\quantity\[\\log\\frac\{p\(X\)\}\{q\(X\)\}\]\. Therefore, the KL\-divergence between the trajectory distribution of the target transitionpωp\_\{\\omega\}and the simulator’s transitionpω0p\_\{\\omega\_\{0\}\}is given by

KL\(Pr⁡\(H\|pω0\)∥Pr⁡\(H\|pω\)\)=\\displaystyle\{\\text\{\\rm KL\}\}\(\\Pr\(H\|p\_\{\\omega\_0\}\)\\\|\\Pr\(H\|p\_\{\\omega\}\)\)=𝔼H∼pω0,πθ​\[log⁡Pr⁡\(H\|pω0\)Pr⁡\(H\|pω\)\]\\displaystyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\\quantity\[\\log\\frac\{\\Pr\(H\|p\_\{\\omega\_0\}\)\}\{\\Pr\(H\|p\_\{\\omega\}\)\}\]\(119\)=\\displaystyle=𝔼H∼pω0,πθ​\[log⁡mpω0​\(H\)mpω​\(H\)\]\\displaystyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\\quantity\[\\log\\frac\{m\_\{p\_\{\\omega\_0\}\}\(H\)\}\{m\_\{p\_\{\\omega\}\}\(H\)\}\]\(By \([25](https://arxiv.org/html/2608.24146#A1.E25)\)\)=\\displaystyle=𝔼H∼pω0,πθ​\[log⁡mpω0​\(H\)−log⁡mpω​\(H\)\]\.\\displaystyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\\quantity\[\\log m\_\{p\_\{\\omega\_0\}\}\(H\)\-\\log m\_\{p\_\{\\omega\}\}\(H\)\]\.\(120\)We take the gradient of the KL\-divergence with respect toω\\omega:

∂∂ωKL\(Pr⁡\(H\|pω0\)∥Pr⁡\(H\|pω\)\)=\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\{\\text\{\\rm KL\}\}\(\\Pr\(H\|p\_\{\\omega\_0\}\)\\\|\\Pr\(H\|p\_\{\\omega\}\)\)=∂∂ω​𝔼H∼pω0,πθ​\[log⁡mpω0​\(H\)−log⁡mpω​\(H\)\]\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\\quantity\[\\log m\_\{p\_\{\\omega\_0\}\}\(H\)\-\\log m\_\{p\_\{\\omega\}\}\(H\)\]\(121\)=\\displaystyle=𝔼H∼pω0,πθ​\[−∂∂ω​log⁡mpω​\(H\)\]\\displaystyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\\quantity\[\-\\gradomega\\log m\_\{p\_\{\\omega\}\}\(H\)\]\(122\)=\\displaystyle=𝔼H∼pω0,πθ​\[−∑t=0T−1∂∂ωlogpω\(St\+1\|St,At\)\]\\displaystyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\\quantity\[\-\\sum\_\{t=0\}^\{T\-1\}\\gradomega\\log p\_\{\\omega\}\(S\_\{t\+1\}\|S\_t,A\_t\)\]\(123\)=\\displaystyle=𝔼H∼pω0,πθ​\[−∑t=0T−1∂∂ωlog⁡\(pω​\(St\+1\|St,At\)\)\]\.\\displaystyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\\quantity\[\-\\sum\_\{t=0\}^\{T\-1\}\\gradomega\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\]\.\(124\)Thus,

∂∂ω𝕍H∼pω0,πθ\[OPE\(πe,πθ,pω,H\)\]−ηKL\(Pr⁡\(H\|pω0\)∥Pr⁡\(H\|pω\)\)\\displaystyle\\frac\{\\partial\}\{\\partial\\omega\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\[\\mathrm\{OPE\}\(\\pi\_\{e\},\\pi\_\{\\theta\},p\_\{\\omega\},H\)\]\-\\eta\{\\text\{\\rm KL\}\}\(\\Pr\(H\|p\_\{\\omega\_0\}\)\\\|\\Pr\(H\|p\_\{\\omega\}\)\)\(126\)=\\displaystyle=2​𝔼H∼pω′​\[OPE2​\(πe,πθ,pω,H\)​∂∂ω​ℓpω\]\\displaystyle\\textstyle 2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega^\{\\prime\}\}\}\\quantity\[\\mathrm\{OPE\}^2\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\)\\gradomega\\ell\_\{p\_\\omega\} \]\(127\)−2​𝔼H∼pω′​\[OPE⁡\(πe,πθ,pω,H\)\]​𝔼H∼pω′​\[OPE⁡\(πe,πθ,pω,H\)​∂∂ω​ℓpω\]\\displaystyle\\textstyle\-2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega^\{\\prime\}\}\}\\quantity\[\\mathrm\{OPE\}\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\)\]\\textstyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega^\{\\prime\}\}\}\\quantity\[\\mathrm\{OPE\}\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\)\\gradomega\\ell\_\{p\_\\omega\} \]\(128\)−∂∂ωηKL\(Pr⁡\(H\|pω0\)∥Pr⁡\(H\|pω\)\)\\displaystyle\-\\textstyle\\frac\{\\partial\}\{\\partial\\omega\}\\eta\{\\text\{\\rm KL\}\}\(\\Pr\(H\|p\_\{\\omega\_0\}\)\\\|\\Pr\(H\|p\_\{\\omega\}\)\)\(129\)=\\displaystyle=2​𝔼H∼pω′​\[OPE2​\(πe,πθ,pω,H\)​∂∂ω​ℓpω\]\\displaystyle\\textstyle 2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega^\{\\prime\}\}\}\\quantity\[\\mathrm\{OPE\}^2\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\)\\gradomega\\ell\_\{p\_\\omega\} \]\(130\)−2​𝔼H∼pω′​\[OPE⁡\(πe,πθ,pω,H\)\]​𝔼H∼pω′​\[OPE⁡\(πe,πθ,pω,H\)​∂∂ω​ℓpω\]\\displaystyle\\textstyle\-2\\mathbb\{E\}\_\{H\\sim p\_\{\\omega^\{\\prime\}\}\}\\quantity\[\\mathrm\{OPE\}\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\)\]\\textstyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega^\{\\prime\}\}\}\\quantity\[\\mathrm\{OPE\}\(\\pi\_e, \\pi\_\\theta,p\_\\omega,H\)\\gradomega\\ell\_\{p\_\\omega\} \]\(131\)−η​𝔼H∼pω0,πθ​\[−∑t=0T−1∂∂ωlog⁡\(pω​\(St\+1\|St,At\)\)\]\.\\displaystyle\-\\textstyle\\eta\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\_\{0\}\},\\pi\_\{\\theta\}\}\\quantity\[\-\\sum\_\{t=0\}^\{T\-1\}\\gradomega\\log\(p\_\\omega\(S\_\{t\+1\}\|S\_t,A\_t\)\)\]\.\(By \([124](https://arxiv.org/html/2608.24146#A1.E124)\)\)

### A\.7Proof of Lemma[5\.2](https://arxiv.org/html/2608.24146#S5.Thmtheorem2)

###### Proof\.

By Lemma[5\.1](https://arxiv.org/html/2608.24146#S5.Thmtheorem1),

∂∂θ​𝕍H∼pω,πθ​\[IS⁡\(πe,πθ,H\)\]=\\displaystyle\\textstyle\\frac\{\\partial\}\{\\partial\\theta\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]=𝔼H∼pω,πθ​\[−IS\(πe,πθ,H\)2∑t=0T−1∂∂θlogπθ\(At\|St\)\]\.\\displaystyle\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\quantity\[\-\\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\theta\}\\log\\pi\_\{\\theta\}\(A\_t\|S\_t\)\]\.\(132\)To prove the Lipschitz property, we bound each term in the RHS\. First, we aim to bound‖∂∂θ​log⁡πθ​\(At\|St\)‖\\norm\{\\frac\{\\partial\}\{\\partial\\theta\}\\log\\pi\_\{\\theta\}\(A\_t\|S\_t\)\}\. Remember that we define

πθ​\(a\|s\)≐exp⁡\(θa⊤​ϕ​\(s\)\)∑a′∈𝒜exp⁡\(θa′⊤​ϕ​\(s\)\),\\displaystyle\\pi\_\{\\theta\}\(a\|s\)\\doteq\\frac\{\\exp\(\\theta^\\top\_a\\phi\(s\)\)\}\{\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\exp\(\\theta^\\top\_\{a'\}\\phi\(s\)\)\},\(133\)where we assumed the linear features‖ϕ⁡\(s\)‖\\norm\{\\phi\(s\)\}to be bounded by a constantBB\. Here,θ=\{θa\}a∈𝒜\\theta=\\\{\\theta\_\{a\}\\\}\_\{a\\in\\mathcal\{A\}\}is the whole parameter matrix, andθa\\theta\_\{a\}is the column for actionaaspecifically\. From[Wang et al\. \(2023a\)](https://arxiv.org/html/2608.24146#bib.bib42), we know that

‖∂∂θ​log⁡πθ​\(a\|s\)‖2=∑a′∈𝒜‖∂∂θa′​log⁡πθ​\(a\|s\)‖2\.\\displaystyle\\norm\{\\frac\{\\partial\}\{\\partial\\theta\}\\log\\pi\_\{\\theta\}\(a\|s\)\}^\{2\}=\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\norm\{\\frac\{\\partial\}\{\\partial\\theta\_\{a'\}\}\\log\\pi\_\{\\theta\}\(a\|s\)\}^\{2\}\.\(134\)Further decomposing, we get

‖∂∂θ​log⁡πθ​\(a\|s\)‖=\\displaystyle\\norm\{\\frac\{\\partial\}\{\\partial\\theta\}\\log\\pi\_\{\\theta\}\(a\|s\)\}=\[‖ϕ⁡\(s\)‖22​\(1−2​πθ​\(a\|s\)\+∑a′∈𝒜πθ​\(a′\|s\)2\)\]12\\displaystyle\\quantity\[\\norm\{\\phi\(s\)\}^2\_2\\qty\(1\-2\\pi\_\{\\theta\}\(a\|s\)\+\\sum\_\{a'\\in\\mathcal\{A\}\}\\pi\_\\theta\(a'\|s\)^2\)\]^\{\\frac\{1\}\{2\}\}\(135\)≤\\displaystyle\\leq2​B\.\\displaystyle\\sqrt\{2\}B\.\(136\)Thus, we have

‖∑t=0T−1∂∂θ​log⁡πθ​\(At\|St\)‖≤2​B​T\.\\displaystyle\\norm\{\\sum\_\{t=0\}^\{T\-1\} \\frac\{\\partial\}\{\\partial\\theta\}\\log\\pi\_\{\\theta\}\(A\_t\|S\_t\)\}\\leq\\sqrt\{2\}BT\.\(137\)We also make the standard assumption that the quotientπe​\(a\|s\)πθ​\(a\|s\)\\frac\{\\pi\_\{e\}\(a\|s\)\}\{\\pi\_\{\\theta\}\(a\|s\)\}is bounded above by a constantCCfor allss,aa, andθ\\theta\.

‖IS​\(πe,πθ,H\)2‖=‖\(∏t=0T−1πe​\(At\|St\)∏t=0T−1πθ​\(At\|St\)​g​\(H\)\)2‖≤C2​T​T2,\\displaystyle\\norm\{\\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2\}=\\norm\{\\qty\(\\frac\{\\prod\_\{t=0\}^\{T\-1\}\\pi\_e\(A\_t\|S\_t\)\}\{\\prod\_\{t=0\}^\{T\-1\}\\pi\_\\theta\(A\_t\|S\_t\)\}g\(H\) \)^2 \}\\leq C^\{2T\}T^\{2\},\(138\)since we assume the reward is bounded above by11\.

Then,

‖∂∂θ​VH∼pω,πθ​\[IS⁡\(πe,πθ,H\)\]‖≤2​B​C2​T​T3\.\\displaystyle\\norm\{\\frac\{\\partial\}\{\\partial\\theta\}V\_\{\\Hsample\}\[\\IS\(\\pi\_\{e\},\\pi\_\\theta,H\)\]\}\\leq\\sqrt\{2\}BC^\{2T\}T^\{3\}\.\(139\)Thus, the objective function𝕍H∼pω,πθ​\[IS⁡\(πe,πθ,H\)\]\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]isLΘL\_\{\\Theta\}\-Lipschitz inθ\\thetawithLΘ=2​B​C2​T​T3L\_\{\\Theta\}=\\sqrt\{2\}BC^\{2T\}T^\{3\}\.

Next, we aim to show that the objective function𝕍H∼pω,πθ​\[IS⁡\(πe,πθ,H\)\]\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]isℓΘ\\ell\_\{\\Theta\}\-smooth inθ\\theta\.

Under trajectoryhh, definewπθ​\(h\)≐∏t=0T−1πθ​\(At,St\)w\_\{\\pi\_\{\\theta\}\}\(h\)\\doteq\\prod\_\{t=0\}^\{T\-1\}\\pi\_\{\\theta\}\(A\_\{t\},S\_\{t\}\), andp~​\(h\)=Pr⁡\(H=h\|πθ\)wπθ​\(h\)\\tilde\{p\}\(h\)=\\frac\{\\Pr\(H=h\|\\pi\_\{\\theta\}\)\}\{w\_\{\\pi\_\{\\theta\}\}\(h\)\}\. For a fixed transitionpωp\_\{\\omega\}, we have the following decomposition as also shown in[Hanna et al\. \(2024\)](https://arxiv.org/html/2608.24146#bib.bib43):

∂2∂θ2​𝕍H∼pω,πθ​\[IS⁡\(πθ,pω,H\)\]\\displaystyle\\frac\{\\partial^\{2\}\}\{\\partial\\theta^\{2\}\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{\\theta\},p\_\{\\omega\},H\)\]\(140\)=\\displaystyle=∂∂θ​𝔼H∼pω,πθ​\[−IS\(πe,πθ,H\)2∑t=0T−1∂∂θlogπθ\(At\|St\)\]\\displaystyle\\frac\{\\partial\}\{\\partial\\theta\}\\mathbb\{E\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\\quantity\[\-\\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\theta\}\\log\\pi\_\{\\theta\}\(A\_t\|S\_t\)\]\(By \([132](https://arxiv.org/html/2608.24146#A1.E132)\)\)=\\displaystyle=∂∂θ​∑hp~​\(h\)​wπθ​\(h\)​\(−IS​\(πe,πθ,H\)2​∂∂θ​wπθ​\(h\)​1wπθ​\(h\)\)\\displaystyle\\frac\{\\partial\}\{\\partial\\theta\}\\sum\_\{h\}\\tilde\{p\}\(h\)w\_\{\\pi\_\{\\theta\}\}\(h\)\\quantity\(\-\\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2\\frac\{\\partial\}\{\\partial\\theta\}w\_\{\\pi\_\\theta\}\(h\)\\frac\{1\}\{w\_\{\\pi\_\\theta\}\(h\)\}\)\(141\)=\\displaystyle=∂∂θ∑h−p~\(h\)IS\(πe,πθ,H\)2∂∂θwπθ\(h\)\\displaystyle\\frac\{\\partial\}\{\\partial\\theta\}\\sum\_\{h\}\-\\tilde\{p\}\(h\)\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)^\{2\}\\frac\{\\partial\}\{\\partial\\theta\}w\_\{\\pi\_\{\\theta\}\}\(h\)\(142\)=\\displaystyle=∑h−p~\(h\)\[∂∂θ​IS​\(πe,πθ,H\)2​∂∂θ​wπθ​\(h\)\+IS​\(πe,πθ,H\)2​∂2∂θ2​wπθ​\(h\)\]\.\\displaystyle\\sum\_\{h\}\-\\tilde\{p\}\(h\)\\quantity\[\\frac\{\\partial\}\{\\partial\\theta\} \\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2\\frac\{\\partial\}\{\\partial\\theta\}w\_\{\\pi\_\\theta\}\(h\)\+\\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2\\frac\{\\partial^2\}\{\\partial\\theta^2\}w\_\{\\pi\_\\theta\}\(h\)\]\.\(143\)
For the terms here, we have

∂∂θ​IS​\(πe,πθ,H\)2=−2​g​\(h\)2​wπe​\(h\)2wπθ​\(h\)3​∂∂θ​wπθ​\(h\),\\displaystyle\\frac\{\\partial\}\{\\partial\\theta\}\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)^\{2\}=\\frac\{\-2g\(h\)^\{2\}w\_\{\\pi\_\{e\}\}\(h\)^\{2\}\}\{w\_\{\\pi\_\{\\theta\}\}\(h\)^\{3\}\}\\frac\{\\partial\}\{\\partial\\theta\}w\_\{\\pi\_\{\\theta\}\}\(h\),\(144\)∂∂θ​wπθ​\(h\)=\\displaystyle\\frac\{\\partial\}\{\\partial\\theta\}w\_\{\\pi\_\{\\theta\}\}\(h\)=∑t=0T−1∂∂θ​πθ​\(At\|St\)​∏t′=0,t′≠tT−1πθ​\(At′\|St′\),\\displaystyle\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\theta\}\\pi\_\{\\theta\}\(A\_\{t\}\|S\_\{t\}\)\\prod\_\{t^\{\\prime\}=0,t^\{\\prime\}\\neq t\}^\{T\-1\}\\pi\_\{\\theta\}\(A\_\{t^\{\\prime\}\}\|S\_\{t^\{\\prime\}\}\),\(145\)and

∂2∂θ2​wπθ​\(h\)=\\displaystyle\\frac\{\\partial^\{2\}\}\{\\partial\\theta^\{2\}\}w\_\{\\pi\_\{\\theta\}\}\(h\)=∂∂θ​∑t=0T−1\(∂∂θ​πθ​\(At\|St\)​∏t′=0,t′≠tT−1πθ​\(At′\|St′\)\)\\displaystyle\\frac\{\\partial\}\{\\partial\\theta\}\\sum\_\{t=0\}^\{T\-1\}\\quantity\(\\frac\{\\partial\}\{\\partial\\theta\} \\pi\_\\theta\(A\_t\|S\_t\)\\prod\_\{t'=0,t'\\neq t\}^\{T\-1\}\\pi\_\\theta\(A\_\{t'\}\|S\_\{t'\}\)\)\(146\)=\\displaystyle=∑t=0T−1\(∂2∂θ2​πθ​\(At\|St\)​∏t≠t′πθ​\(At′\|St′\)\+∂∂θ​πθ​\(At\|St\)​∑t≠t′∂∂θ​πθ​\(At′\|St′\)​∏t′′≠t,t′πθ​\(At′′\|St′′\)\)\.\\displaystyle\\sum\_\{t=0\}^\{T\-1\}\\quantity\(\\frac\{\\partial^2\}\{\\partial\\theta^2\}\\pi\_\\theta\(A\_t\|S\_t\)\\prod\_\{t\\neq t'\}\\pi\_\\theta\(A\_\{t'\}\|S\_\{t'\}\)\+\\frac\{\\partial\}\{\\partial\\theta\} \\pi\_\\theta\(A\_t\|S\_t\)\\sum\_\{t\\neq t'\}\\frac\{\\partial\}\{\\partial\\theta\} \\pi\_\\theta\(A\_\{t'\}\|S\_\{t'\}\)\\prod\_\{t''\\neq t,t'\}\\pi\_\\theta\(A\_\{t''\}\|S\_\{t''\}\)\)\.\(147\)
Denoteθα=θ\+α​u\\theta\_\{\\alpha\}=\\theta\+\\alpha u, whereα∈ℝ\\alpha\\in\\mathbb\{R\},u∈ℝd​\|𝒜\|u\\in\\mathbb\{R\}^\{d\|\\mathcal\{A\}\|\}, withddbeing the linear feature dimension\.

By chain rule, we have, for a fixed transitionpωp\_\{\\omega\},

∂2∂α2​𝕍H∼πθα,pω​\[IS⁡\(πe,πθα,H\)\]\|α=0\\displaystyle\\frac\{\\partial^\{2\}\}\{\\partial\\alpha^\{2\}\}\\mathbb\{V\}\_\{H\\sim\\pi\_\{\\theta\_\{\\alpha\}\},p\_\{\\omega\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{\\alpha\}\},H\)\]\\Big\|\_\{\\alpha=0\}\(148\)=\\displaystyle=u⊤​∂2∂θ2​𝕍H∼πθ,pω​\[IS⁡\(πe,πθ,H\)\]​u\\displaystyle u^\{\\top\}\\frac\{\\partial^\{2\}\}\{\\partial\\theta^\{2\}\}\\mathbb\{V\}\_\{H\\sim\\pi\_\{\\theta\},p\_\{\\omega\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]u\(149\)=\\displaystyle=u⊤∑h−p~\(h\)\[∂∂θ​IS​\(πe,πθ,H\)2​∂∂θ​wπθ​\(h\)⊤\+IS​\(πe,πθ,H\)2​∂2∂θ2​wπθ​\(h\)\]u\\displaystyle u^\{\\top\}\\sum\_\{h\}\-\\tilde\{p\}\(h\)\\quantity\[\\frac\{\\partial\}\{\\partial\\theta\} \\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2\\frac\{\\partial\}\{\\partial\\theta\}w\_\{\\pi\_\\theta\}\(h\)^\\top\+\\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2\\frac\{\\partial^2\}\{\\partial\\theta^2\}w\_\{\\pi\_\\theta\}\(h\)\]u\(By \([143](https://arxiv.org/html/2608.24146#A1.E143)\)\)=\\displaystyle=∑h−p~\(h\)\[⟨∂∂θ​IS​\(πe,πθ,H\)2,u⟩​⟨∂∂θ​wπθ​\(h\),u⟩\+IS​\(πe,πθ,H\)2​u⊤​∂2∂θ2​wπθ​\(h\)​u\]\.\\displaystyle\\sum\_\{h\}\-\\tilde\{p\}\(h\)\\quantity\[\\Big\\langle\\frac\{\\partial\}\{\\partial\\theta\} \\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2, u\\Big\\rangle\\Big\\langle\\frac\{\\partial\}\{\\partial\\theta\}w\_\{\\pi\_\\theta\}\(h\), u\\Big\\rangle\+\\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2u^\\top\\frac\{\\partial^2\}\{\\partial\\theta^2\}w\_\{\\pi\_\\theta\}\(h\) u\]\.\(150\)
We analyze the bound term by term\. First, for⟨∂∂θ​IS​\(πe,πθ,H\)2,u⟩\\Big\\langle\\frac\{\\partial\}\{\\partial\\theta\}\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)^\{2\},u\\Big\\rangle, note that

‖∂∂θ​IS​\(πe,πθ,H\)2‖\\displaystyle\\norm\{\\frac\{\\partial\}\{\\partial\\theta\} \\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2\}\(151\)=\\displaystyle=‖2​g​\(h\)2​wπe​\(h\)2wπθ​\(h\)3​∂∂θ​wπθ​\(h\)‖\\displaystyle\\norm\{\\frac\{2g\(h\)^2w\_\{\\pi\_e\}\(h\)^2\}\{w\_\{\\pi\_\\theta\}\(h\)^3\} \\frac\{\\partial\}\{\\partial\\theta\} w\_\{\\pi\_\\theta\}\(h\)\}\(152\)≤\\displaystyle\\leq2​T2​‖wπe​\(h\)2wπθ​\(h\)3​wπθ​\(h\)​∑t=0T−1∂∂θ​log⁡\(πθ​\(At\|St\)\)‖\\displaystyle 2T^\{2\}\\norm\{\\frac\{w\_\{\\pi\_e\}\(h\)^2\}\{w\_\{\\pi\_\\theta\}\(h\)^3\} w\_\{\\pi\_\\theta\}\(h\) \\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\theta\} \\log\(\\pi\_\\theta\(A\_t\|S\_t\)\)\}\(By \(21\) of[Hanna et al\. \(2024\)](https://arxiv.org/html/2608.24146#bib.bib43)\)≤\\displaystyle\\leq2​T2​C2​T​‖∑t=0T−1∂∂θ​log⁡\(πθ​\(At\|St\)\)‖\\displaystyle 2T^\{2\}C^\{2T\}\\norm\{\\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\theta\} \\log\(\\pi\_\\theta\(A\_t\|S\_t\)\)\}\(153\)≤\\displaystyle\\leq2​2​B​T3​C2​T\.\\displaystyle 2\\sqrt\{2\}BT^\{3\}C^\{2T\}\.\(By \([137](https://arxiv.org/html/2608.24146#A1.E137)\)\)Thus,

\|⟨∂∂θ​IS​\(πe,πθ,H\)2,u⟩\|≤2​2​B​T3​C2​T​‖u‖2\.\\displaystyle\\absolutevalue\{\\Big\\langle\\frac\{\\partial\}\{\\partial\\theta\} \\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2, u\\Big\\rangle\}\\leq 2\\sqrt\{2\}BT^\{3\}C^\{2T\}\\norm\{u\}\_\{2\}\.\(154\)Next, for⟨∂∂θ​wπθ​\(h\),u⟩\\Big\\langle\\frac\{\\partial\}\{\\partial\\theta\}w\_\{\\pi\_\{\\theta\}\}\(h\),u\\Big\\rangle, recall that

‖∂∂θ​wπθ​\(h\)‖\\displaystyle\\norm\{ \\frac\{\\partial\}\{\\partial\\theta\}w\_\{\\pi\_\\theta\}\(h\)\}\(155\)=\\displaystyle=‖wπθ​\(h\)​∑t=0T−1∂∂θ​log⁡\(πθ​\(At\|St\)\)‖\\displaystyle\\norm\{w\_\{\\pi\_\\theta\}\(h\) \\sum\_\{t=0\}^\{T\-1\}\\frac\{\\partial\}\{\\partial\\theta\} \\log\(\\pi\_\\theta\(A\_t\|S\_t\)\)\}\(156\)≤\\displaystyle\\leq1⋅2​B​T\.\\displaystyle 1\\cdot\\sqrt\{2\}BT\.\(157\)Thus,

\|⟨∂∂θ​wπθ​\(h\),u⟩\|≤2​B​T​‖u‖2\.\\displaystyle\\absolutevalue\{\\Big\\langle\\frac\{\\partial\}\{\\partial\\theta\}w\_\{\\pi\_\\theta\}\(h\), u\\Big\\rangle\}\\leq\\sqrt\{2\}BT\\norm\{u\}\_\{2\}\.\(158\)As for the second termIS​\(πe,πθ,H\)2​u⊤​∂2∂θ2​wπθ​\(h\)​u\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)^\{2\}u^\{\\top\}\\frac\{\\partial^\{2\}\}\{\\partial\\theta^\{2\}\}w\_\{\\pi\_\{\\theta\}\}\(h\)u, remember that by \([138](https://arxiv.org/html/2608.24146#A1.E138)\),

‖IS​\(πe,πθ,H\)2‖≤C2​T​T2\.\\displaystyle\\norm\{\\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2\}\\leq C^\{2T\}T^\{2\}\.\(159\)Besides, by \([147](https://arxiv.org/html/2608.24146#A1.E147)\),

u⊤​∂2∂θ2​wπθ​\(h\)​u=\\displaystyle u^\{\\top\}\\frac\{\\partial^\{2\}\}\{\\partial\\theta^\{2\}\}w\_\{\\pi\_\{\\theta\}\}\(h\)u=∑t=0T−1u⊤​∂2∂θ2​πθ​\(At\|St\)​u​∏t≠t′πθ​\(At′\|St′\)⏟\(a\)\\displaystyle\\underbrace\{\\sum\_\{t=0\}^\{T\-1\}u^\{\\top\}\\frac\{\\partial^\{2\}\}\{\\partial\\theta^\{2\}\}\\pi\_\{\\theta\}\(A\_\{t\}\|S\_\{t\}\)u\\prod\_\{t\\neq t^\{\\prime\}\}\\pi\_\{\\theta\}\(A\_\{t^\{\\prime\}\}\|S\_\{t^\{\\prime\}\}\)\}\_\{\(a\)\}\(160\)\+∑t=0T−1⟨∂∂θ​πθ​\(At\|St\),u⟩⋅∑t≠t′⟨∂∂θ​πθ​\(At′\|St′\),u⟩​∏t′′≠t,t′πθ​\(At′′\|St′′\)⏟\(b\)\.\\displaystyle\+\\underbrace\{\\sum\_\{t=0\}^\{T\-1\}\\Big\\langle\\frac\{\\partial\}\{\\partial\\theta\}\\pi\_\{\\theta\}\(A\_\{t\}\|S\_\{t\}\),u\\Big\\rangle\\cdot\\sum\_\{t\\neq t^\{\\prime\}\}\\Big\\langle\\frac\{\\partial\}\{\\partial\\theta\}\\pi\_\{\\theta\}\(A\_\{t^\{\\prime\}\}\|S\_\{t^\{\\prime\}\}\),u\\Big\\rangle\\prod\_\{t^\{\\prime\\prime\}\\neq t,t^\{\\prime\}\}\\pi\_\{\\theta\}\(A\_\{t^\{\\prime\\prime\}\}\|S\_\{t^\{\\prime\\prime\}\}\)\}\_\{\(b\)\}\.\(161\)
To bound term \(a\) and \(b\), notice that

∂πθ​\(a\|s\)∂θa′=πθ\(a\|s\)\(𝟏\{a′=a\}−πθ\(a′\|s\)\)ϕ\(s\),\\displaystyle\\frac\{\\partial\\pi\_\{\\theta\}\(a\|s\)\}\{\\partial\\theta\_\{a\}^\{\\prime\}\}=\\pi\_\{\\theta\}\(a\|s\)\(\\mathbf\{1\}\\\{a^\{\\prime\}=a\\\}\-\\pi\_\{\\theta\}\(a^\{\\prime\}\|s\)\)\\phi\(s\),\(162\)where𝟏\\mathbf\{1\}is the indicator function\. Now we also define a state\-wise logit directionvs∈ℝ\|𝒜\|v\_\{s\}\\in\\mathbb\{R\}^\{\|\\mathcal\{A\}\|\}with each componentvs​\(a′\)≐⟨ua′,ϕ⁡\(s\)⟩v\_\{s\}\(a^\{\\prime\}\)\\doteq\\langle u\_\{a^\{\\prime\}\},\\phi\(s\)\\rangle\. Then, for the first derivative,

\|∂πθα​\(a\|s\)∂α\|α=0\|=\\displaystyle\\absolutevalue\{\\frac\{\\partial\\pi\_\{\\theta\_\\alpha\}\(a\|s\)\}\{\\partial\\alpha\}\\Big\|\_\{\\alpha=0\} \}=\|⟨∂πθ​\(a\|s\)∂θ,u⟩\|\\displaystyle\\absolutevalue\{\\Big\\langle\\frac\{\\partial\\pi\_\{\\theta\}\(a\|s\)\}\{\\partial\\theta\} ,u\\Big\\rangle\}\(163\)=\\displaystyle=\|πθ​\(a\|s\)⋅\(vs​\(a\)−∑a′πθ​\(a′\|s\)​vs​\(a′\)\)\|\\displaystyle\\absolutevalue\{\\pi\_\{\\theta\}\(a\|s\)\\cdot\\qty\(v\_s\(a\)\-\\sum\_\{a'\}\\pi\_\\theta\(a'\|s\)v\_s\(a'\)\)\}\(164\)≤\\displaystyle\\leqπθ​\(a\|s\)​\(\|vs​\(a\)\|\+\|∑a′πθ​\(a′\|s\)​vs​\(a′\)\|\)\\displaystyle\\pi\_\{\\theta\}\(a\|s\)\\quantity\(\\abs\{v\_s\(a\)\}\+\\abs\{\\sum\_\{a'\}\\pi\_\\theta\(a'\|s\)v\_s\(a'\)\}\)\(Triangular Inequality\)≤\\displaystyle\\leq2​πθ​\(a\|s\)​‖vs‖2\\displaystyle 2\\pi\_\{\\theta\}\(a\|s\)\\norm\{v\_s\}\_\{2\}\(165\)≤\\displaystyle\\leq2​‖vs‖2\\displaystyle 2\\norm\{v\_s\}\_\{2\}\(166\)≤\\displaystyle\\leq2​‖ϕ⁡\(s\)‖2​‖u‖2\\displaystyle 2\\norm\{\\phi\(s\)\}\_\{2\}\\norm\{u\}\_\{2\}\(167\)≤\\displaystyle\\leq2​B​‖u‖2,\\displaystyle 2B\\norm\{u\}\_\{2\},\(168\)where we identifyuuwith its vectorization, so‖u‖22=∑a∈𝒜‖ua‖22\\norm\{u\}^\{2\}\_\{2\}=\\sum\_\{a\\in\\mathcal\{A\}\}\\norm\{u\_a\}^\{2\}\_\{2\}\. Similarly, for the second derivative,

\|∂2πθα​\(a\|s\)∂α2\|α=0\|=\\displaystyle\\absolutevalue\{\\frac\{\\partial^2 \\pi\_\{\\theta\_\\alpha\}\(a\|s\)\}\{\\partial\\alpha^2\}\\Big\|\_\{\\alpha=0\} \}=\|⟨∂2πθ​\(a\|s\)∂θ2​vs,vs⟩\|\\displaystyle\\absolutevalue\{\\Big\\langle\\frac\{\\partial^2 \\pi\_\{\\theta\}\(a\|s\)\}\{\\partial\\theta^2\}v\_s ,v\_s\\Big\\rangle\}\(169\)=\\displaystyle=\|πθ​\(a∣s\)​\[\(1−πθ​\(a∣s\)\)​vs​\(a\)2−∑a′≠aπθ​\(a′∣s\)​\(vs​\(a\)−vs​\(a′\)\)2\+∑a′πθ​\(a′∣s\)2​vs​\(a′\)2\]\|\\displaystyle\\absolutevalue\{\\pi\_\\theta\(a\\mid s\)\\qty\[ \(1\-\\pi\_\\theta\(a\\mid s\)\)v\_s\(a\)^2 \-\\sum\_\{a'\\neq a\}\\pi\_\\theta\(a'\\mid s\)\\bigl\(v\_s\(a\)\-v\_s\(a'\)\\bigr\)^2 \+\\sum\_\{a'\}\\pi\_\\theta\(a'\\mid s\)^\{2\}v\_s\(a'\)^2 \]\}\(170\)≤\\displaystyle\\leq5​‖vs‖22\\displaystyle 5\\norm\{v\_s\}^\{2\}\_\{2\}\(171\)≤\\displaystyle\\leq5​B2​‖u‖22\\displaystyle 5B^\{2\}\\norm\{u\}^\{2\}\_\{2\}\(172\)
Now, getting back to \(a\) in \([161](https://arxiv.org/html/2608.24146#A1.E161)\), we have

\|\(a\)\|=\\displaystyle\\absolutevalue\{\(a\)\}=\|∑t=0T−1u⊤​∂2∂θ2​πθ​\(At\|St\)​u​∏t≠t′πθ​\(At′\|St′\)\|\\displaystyle\\absolutevalue\{\\sum\_\{t=0\}^\{T\-1\}u^\\top\\frac\{\\partial^2\}\{\\partial\\theta^2\}\\pi\_\\theta\(A\_t\|S\_t\)u\\prod\_\{t\\neq t'\}\\pi\_\\theta\(A\_\{t'\}\|S\_\{t'\}\)\}\(173\)≤\\displaystyle\\leq\|∑t=0T−1u⊤​∂2∂θ2​πθ​\(At\|St\)​u\|\\displaystyle\\absolutevalue\{\\sum\_\{t=0\}^\{T\-1\}u^\\top\\frac\{\\partial^2\}\{\\partial\\theta^2\}\\pi\_\\theta\(A\_t\|S\_t\)u\}\(174\)≤\\displaystyle\\leq5​T​B2​‖u‖22\.\\displaystyle 5TB^\{2\}\\norm\{u\}^\{2\}\_\{2\}\.\(By \([172](https://arxiv.org/html/2608.24146#A1.E172)\)\)As for \(b\) in \([161](https://arxiv.org/html/2608.24146#A1.E161)\),

\|\(b\)\|=\\displaystyle\\absolutevalue\{\(b\)\}=\|∑t=0T−1⟨∂∂θ​πθ​\(At\|St\),u⟩⋅∑t≠t′⟨∂∂θ​πθ​\(At′\|St′\),u⟩​∏t′′≠t,t′πθ​\(At′′\|St′′\)\|\\displaystyle\\absolutevalue\{\\sum\_\{t=0\}^\{T\-1\}\\Big\\langle\\frac\{\\partial\}\{\\partial\\theta\} \\pi\_\\theta\(A\_t\|S\_t\),u\\Big\\rangle\\cdot\\sum\_\{t\\neq t'\}\\Big\\langle\\frac\{\\partial\}\{\\partial\\theta\} \\pi\_\\theta\(A\_\{t'\}\|S\_\{t'\}\),u\\Big\\rangle\\prod\_\{t''\\neq t,t'\}\\pi\_\\theta\(A\_\{t''\}\|S\_\{t''\}\)\}\(176\)≤\\displaystyle\\leq∑t=0T−1\|⟨∂∂θ​πθ​\(At\|St\),u⟩\|⋅∑t≠t′\|⟨∂∂θ​πθ​\(At′\|St′\),u⟩\|⋅1\\displaystyle\\sum\_\{t=0\}^\{T\-1\}\\absolutevalue\{\\Big\\langle\\frac\{\\partial\}\{\\partial\\theta\} \\pi\_\\theta\(A\_t\|S\_t\),u\\Big\\rangle\}\\cdot\\sum\_\{t\\neq t^\{\\prime\}\}\\absolutevalue\{\\Big\\langle\\frac\{\\partial\}\{\\partial\\theta\} \\pi\_\\theta\(A\_\{t'\}\|S\_\{t'\}\),u\\Big\\rangle\}\\cdot 1\(177\)≤\\displaystyle\\leq2​T​B​‖u‖2⋅2​T​B​‖u‖2\\displaystyle 2TB\\norm\{u\}\_\{2\}\\cdot 2TB\\norm\{u\}\_\{2\}\(By \([168](https://arxiv.org/html/2608.24146#A1.E168)\)\)=\\displaystyle=4​T2​B2​‖u‖22\.\\displaystyle 4T^\{2\}B^\{2\}\\norm\{u\}^\{2\}\_\{2\}\.\(178\)Thus, looking back at the \([161](https://arxiv.org/html/2608.24146#A1.E161)\), we have

\|u⊤​∂2∂θ2​wπθ​\(h\)​u\|\\displaystyle\\absolutevalue\{u^\\top\\frac\{\\partial^2\}\{\\partial\\theta^2\}w\_\{\\pi\_\\theta\}\(h\)u\}\(179\)≤\\displaystyle\\leq\|\(a\)\|\+\|\(b\)\|\\displaystyle\\absolutevalue\{\(a\)\}\+\\absolutevalue\{\(b\)\}\(180\)≤\\displaystyle\\leq5​T​B2​‖u‖22\+4​T2​B2​‖u‖22\.\\displaystyle 5TB^\{2\}\\norm\{u\}^\{2\}\_\{2\}\+4T^\{2\}B^\{2\}\\norm\{u\}^\{2\}\_\{2\}\.\(181\)Therefore,

\|IS​\(πe,πθ,H\)2​u⊤​∂2∂θ2​wπθ​\(h\)​u\|\\displaystyle\\absolutevalue\{\\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2u^\\top\\frac\{\\partial^2\}\{\\partial\\theta^2\}w\_\{\\pi\_\\theta\}\(h\) u\}\(183\)≤\\displaystyle\\leq\|IS​\(πe,πθ,H\)2\|⋅\|u⊤​∂2∂θ2​wπθ​\(h\)​u\|\\displaystyle\\absolutevalue\{\\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2\}\\cdot\\absolutevalue\{u^\\top\\frac\{\\partial^2\}\{\\partial\\theta^2\}w\_\{\\pi\_\\theta\}\(h\) u\}\(184\)≤\\displaystyle\\leqC2​T​T3​B2​‖u‖22​\(5\+4​T\)\.\\displaystyle C^\{2T\}T^\{3\}B^\{2\}\\norm\{u\}^\{2\}\_\{2\}\(5\+4T\)\.\(185\)Putting these all together,

\|∂2∂α2​𝕍H∼pω,πθα​\[IS⁡\(πe,πθα,H\)\]\|α=0\|\\displaystyle\\absolutevalue\{\\frac\{\\partial^2\}\{\\partial\\alpha^2\} \\V\_\{H\\sim p\_\\omega, \\pi\_\{\\theta\_\\alpha\}\}\[\\IS\(\\pi\_e, \\pi\_\{\\theta\_\\alpha\},H\)\]\\Big\|\_\{\\alpha=0\}\}\(187\)=\\displaystyle=\|∑h−p~\(h\)\[⟨∂∂θ​IS​\(πe,πθ,H\)2,u⟩​⟨∂∂θ​wπθ​\(h\),u⟩\+IS​\(πe,πθ,H\)2​u⊤​∂2∂θ2​wπθ​\(h\)​u\]\|\\displaystyle\\absolutevalue\{ \\sum\_h\-\\tilde\{p\}\(h\)\\qty\[\\Big\\langle\\frac\{\\partial\}\{\\partial\\theta\} \\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2, u\\Big\\rangle\\Big\\langle\\frac\{\\partial\}\{\\partial\\theta\}w\_\{\\pi\_\\theta\}\(h\), u\\Big\\rangle\+\\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2u^\\top\\frac\{\\partial^2\}\{\\partial\\theta^2\}w\_\{\\pi\_\\theta\}\(h\) u\]\}\(By \([150](https://arxiv.org/html/2608.24146#A1.E150)\)\)≤\\displaystyle\\leq\|⟨∂∂θ​IS​\(πe,πθ,H\)2,u⟩​⟨∂∂θ​wπθ​\(h\),u⟩\|\+\|IS​\(πe,πθ,H\)2​u⊤​∂2∂θ2​wπθ​\(h\)​u\|\\displaystyle\\absolutevalue\{\\Big\\langle\\frac\{\\partial\}\{\\partial\\theta\} \\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2, u\\Big\\rangle\\Big\\langle\\frac\{\\partial\}\{\\partial\\theta\}w\_\{\\pi\_\\theta\}\(h\), u\\Big\\rangle\}\+\\absolutevalue\{\\IS\(\\pi\_\{e\},\\pi\_\\theta, H\)^2u^\\top\\frac\{\\partial^2\}\{\\partial\\theta^2\}w\_\{\\pi\_\\theta\}\(h\) u\}\(188\)≤\\displaystyle\\leq\(2​2​B​T3​C2​T​‖u‖2\)⋅\(2​B​T​‖u‖2\)\+C2​T​T3​B2​‖u‖22​\(5\+4​T\)\\displaystyle\\quantity\(2\\sqrt\{2\}BT^3C^\{2T\} \\norm\{u\}\_2\)\\cdot\\quantity\( \\sqrt\{2\}BT\\norm\{u\}\_2 \)\+C^\{2T\}T^\{3\}B^\{2\}\\norm\{u\}^\{2\}\_\{2\}\(5\+4T\)\(By \([154](https://arxiv.org/html/2608.24146#A1.E154)\)\([158](https://arxiv.org/html/2608.24146#A1.E158)\)\([185](https://arxiv.org/html/2608.24146#A1.E185)\)\)=\\displaystyle=4​B2​C2​T​T4​‖u‖22\+C2​T​T3​B2​‖u‖22⋅\(5\+4​T\)\\displaystyle 4B^\{2\}C^\{2T\}T^\{4\}\\norm\{u\}^\{2\}\_\{2\}\+C^\{2T\}T^\{3\}B^\{2\}\\norm\{u\}^\{2\}\_\{2\}\\cdot\(5\+4T\)\(189\)=\\displaystyle=B2​C2​T​T3​‖u‖22​\(5\+8​T\)\.\\displaystyle B^\{2\}C^\{2T\}T^\{3\}\\norm\{u\}^\{2\}\_\{2\}\\quantity\( 5\+8T\)\.\(190\)Thus,

‖∂2∂θ2​𝕍H∼pω,πθ​\[IS⁡\(πe,πθ,H\)\]‖op=\\displaystyle\\norm\{\\frac\{\\partial^2\}\{\\partial\\theta^2\} \\V\_\{H\\sim p\_\\omega, \\pi\_\{\\theta\}\}\[\\IS\(\\pi\_e, \\pi\_\{\\theta\},H\)\]\}\_\{\\mathrm\{op\}\}=sup‖u‖2=1B2​C2​T​T3​‖u‖22​\(5\+8​T\)\\displaystyle\\sup\_\{\\norm\{u\}\_\{2\}=1\}B^\{2\}C^\{2T\}T^\{3\}\\norm\{u\}^\{2\}\_\{2\}\\quantity\( 5\+8T\)\(191\)=\\displaystyle=B2​C2​T​T3​\(5\+8​T\),\\displaystyle B^\{2\}C^\{2T\}T^\{3\}\\quantity\(5\+8T\),\(192\)where‖⋅‖op\\norm\{\\cdot\}\_\{\\mathrm\{op\}\}denotes the operator norm\. Therefore, we conclude that the objective function𝕍H∼pω,πθ​\[IS⁡\(πe,πθ,H\)\]\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]isℓΘ\\ell\_\{\\Theta\}\-smooth inθ\\thetawithℓΘ=B2​C2​T​T3​\(5\+8​T\)\\ell\_\{\\Theta\}=B^\{2\}C^\{2T\}T^\{3\}\(5\+8T\)\. Lastly, the convexity of the objective function follows directly from Lemma 2 of[Hanna et al\. \(2024\)](https://arxiv.org/html/2608.24146#bib.bib43)\. ∎

### A\.8Proof of Lemma[5\.3](https://arxiv.org/html/2608.24146#S5.Thmtheorem3)

###### Proof\.

We first show thatΦ⁡\(θ\)\\Phi\(\\theta\)isLΘL\_\{\\Theta\}\-Lipschitz inθ\\theta\. By Lemma[5\.2](https://arxiv.org/html/2608.24146#S5.Thmtheorem2), we know that𝕍H∼pω,πθ​\[IS⁡\(πe,πθ,H\)\]\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]isLΘL\_\{\\Theta\}\-Lipschitz\. ∀θ1\\forall\\theta\_\{1\},θ2∈Θ\\theta\_\{2\}\\in\\Theta, definepω1≐argmaxpω𝕍H∼pω,πθ1​\[IS⁡\(πe,πθ1,H\)\]p\_\{\\omega\_\{1\}\}\\doteq\\argmax\_\{p\_\{\\omega\}\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\_\{1\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{1\}\},H\)\],pω2≐argmaxpω𝕍H∼pω,πθ2​\[IS⁡\(πe,πθ2,H\)\]p\_\{\\omega\_\{2\}\}\\doteq\\argmax\_\{p\_\{\\omega\}\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\_\{2\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{2\}\},H\)\]\. Then,

Φ⁡\(θ1\)−Φ⁡\(θ2\)=\\displaystyle\\Phi\(\\theta\_\{1\}\)\-\\Phi\(\\theta\_\{2\}\)=maxpω⁡𝕍H∼pω,πθ1​\[IS⁡\(πe,πθ1,H\)\]−maxpω⁡𝕍H∼pω,πθ2​\[IS⁡\(πe,πθ2,H\)\]\\displaystyle\\max\_\{p\_\{\\omega\}\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\_\{1\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{1\}\},H\)\]\-\\max\_\{p\_\{\\omega\}\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\_\{2\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{2\}\},H\)\]\(193\)=\\displaystyle=𝕍H∼pω1,πθ1​\[IS⁡\(πe,πθ1,H\)\]−𝕍H∼pω2,πθ2​\[IS⁡\(πe,πθ2,H\)\]\\displaystyle\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\_\{1\}\},\\pi\_\{\\theta\_\{1\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{1\}\},H\)\]\-\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\_\{2\}\},\\pi\_\{\\theta\_\{2\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{2\}\},H\)\]\(194\)≤\\displaystyle\\leq𝕍H∼pω1,πθ1​\[IS⁡\(πe,πθ1,H\)\]−𝕍H∼pω1,πθ2​\[IS⁡\(πe,πθ2,H\)\]\\displaystyle\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\_\{1\}\},\\pi\_\{\\theta\_\{1\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{1\}\},H\)\]\-\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\_\{1\}\},\\pi\_\{\\theta\_\{2\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{2\}\},H\)\]\(195\)≤\\displaystyle\\leqLΘ​‖θ1−θ2‖\.\\displaystyle L\_\{\\Theta\}\\norm\{\\theta\_1\-\\theta\_2\}\.\(By Lemma[5\.2](https://arxiv.org/html/2608.24146#S5.Thmtheorem2)\)By symmetry, with also have

Φ⁡\(θ2\)−Φ⁡\(θ1\)≤LΘ​‖θ1−θ2‖\.\\displaystyle\\Phi\(\\theta\_\{2\}\)\-\\Phi\(\\theta\_\{1\}\)\\leq L\_\{\\Theta\}\\norm\{\\theta\_1\-\\theta\_2\}\.\(196\)Thus,

\|Φ⁡\(θ1\)−Φ⁡\(θ2\)\|≤LΘ​‖θ1−θ2‖,\\displaystyle\\absolutevalue\{\\Phi\(\\theta\_1\)\-\\Phi\(\\theta\_2\)\}\\leq L\_\{\\Theta\}\\norm\{\\theta\_1\-\\theta\_2\},\(197\)which shows the Lipschitz property\. Next, from Lemma[5\.2](https://arxiv.org/html/2608.24146#S5.Thmtheorem2), we also know that𝕍H∼pω,πθ​\[IS⁡\(πe,πθ,H\)\]\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]is convex inθ\\thetaunder the linear softmax parameterization of the behavior policyπθ\\pi\_\{\\theta\}\. Thus,∀θ1\\forall\\theta\_\{1\},θ2∈Θ\\theta\_\{2\}\\in\\Thetaandt∈\[0,1\]t\\in\[0,1\],

Φ⁡\(t​θ1\+\(1−t\)​θ2\)=\\displaystyle\\Phi\(t\\theta\_\{1\}\+\(1\-t\)\\theta\_\{2\}\)=maxpω⁡𝕍H∼pω,π\(t​θ1\+\(1−t\)​θ2\)​\[IS⁡\(πe,π\(t​θ1\+\(1−t\)​θ2\),H\)\]\\displaystyle\\max\_\{p\_\{\\omega\}\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\(t\\theta\_\{1\}\+\(1\-t\)\\theta\_\{2\}\)\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\(t\\theta\_\{1\}\+\(1\-t\)\\theta\_\{2\}\)\},H\)\]\(198\)≤\\displaystyle\\leqmaxpω⁡\[t​𝕍H∼pω,πθ1​\[IS⁡\(πe,πθ1,H\)\]\+\(1−t\)​𝕍H∼pω,πθ2​\[IS⁡\(πe,πθ2,H\)\]\]\\displaystyle\\max\_\{p\_\{\\omega\}\}\[t\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\_\{1\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{1\}\},H\)\]\+\(1\-t\)\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\_\{2\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{2\}\},H\)\]\]\(By Lemma[5\.2](https://arxiv.org/html/2608.24146#S5.Thmtheorem2)\)≤\\displaystyle\\leqtmaxpω\[𝕍H∼pω,πθ1\[IS\(πe,πθ1,H\)\]\+\(1−t\)maxpω′𝕍H∼pω′,πθ2\[IS\(πe,πθ2,H\)\]\\displaystyle t\\max\_\{p\_\{\\omega\}\}\[\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\_\{1\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{1\}\},H\)\]\+\(1\-t\)\\max\_\{p\_\{\\omega^\{\\prime\}\}\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega^\{\\prime\}\},\\pi\_\{\\theta\_\{2\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{2\}\},H\)\]\(199\)=\\displaystyle=t​Φ​\(θ1\)\+\(1−t\)​Φ​\(θ2\)\.\\displaystyle t\\Phi\(\\theta\_\{1\}\)\+\(1\-t\)\\Phi\(\\theta\_\{2\}\)\.\(200\)Therefore, we show thatΦ⁡\(θ\)\\Phi\(\\theta\)is convex inθ\\theta\. ∎

### A\.9Proof of Theorem[5\.4](https://arxiv.org/html/2608.24146#S5.Thmtheorem4)

###### Proof\.

To begin with, we defineθ∗≐argminθ∈ΘΦ​\(θ\)\\theta^\{\*\}\\doteq\\argmin\_\{\\theta\\in\\Theta\}\\Phi\(\\theta\)\. Since the setΘ\\Thetais closed and convex, the Euclidean projection is nonexpensive\. That is,∀u∈ℝd,z∈Θ\\forall u\\in\\mathbb\{R\}^\{d\},z\\in\\Theta,

‖ProjΘ​\(u\)−z‖2≤‖u−z‖2\.\\displaystyle\\norm\{\\mathrm\{Proj\}\_\\Theta\(u\)\-z\}^\{2\}\\leq\\norm\{u\-z\}^\{2\}\.\(201\)Withu≐θi−α​𝒢iu\\doteq\\theta\_\{i\}\-\\alpha\\mathcal\{G\}\_\{i\},z≐θ∗z\\doteq\\theta^\{\*\}, we have

ProjΘ​\(u\)=θi\+1\.\\displaystyle\\mathrm\{Proj\}\_\{\\Theta\}\(u\)=\\theta\_\{i\+1\}\.\(202\)Thus,

‖θi\+1−θ∗‖2\\displaystyle\\norm\{\\theta\_\{i\+1\}\-\\theta^\*\}^\{2\}≤‖θi−α​𝒢i−θ∗‖2\\displaystyle\\leq\\norm\{\\theta\_i\-\\alpha\\mathcal\{G\}\_i\-\\theta^\*\}^\{2\}\(203\)=‖θi−θ∗‖2−2​α​⟨𝒢i,θi−θ∗⟩\+α2​‖𝒢i‖2\.\\displaystyle=\\norm\{\\theta\_i\-\\theta^\*\}^\{2\}\-2\\alpha\\langle\\mathcal\{G\}\_\{i\},\\theta\_\{i\}\-\\theta^\{\*\}\\rangle\+\\alpha^\{2\}\\norm\{\\mathcal\{G\}\_i\}^\{2\}\.\(204\)From here, we first bound the last term,‖𝒢i‖2\\norm\{\\mathcal\{G\}\_i\}^\{2\}\. By Lemma[5\.2](https://arxiv.org/html/2608.24146#S5.Thmtheorem2)we know that the objective function𝕍H∼pω,πθ​\[IS⁡\(πe,πθ,H\)\]\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]isLΘL\_\{\\Theta\}\-Lipschitz and convex inθ\\theta\. Thus we have

‖𝒢i‖≤LΘ⟹‖𝒢i‖2≤LΘ2\.\\displaystyle\\norm\{\\mathcal\{G\}\_i\}\\leq L\_\{\\Theta\}\\implies\\norm\{\\mathcal\{G\}\_i\}^\{2\}\\leq L^\{2\}\_\{\\Theta\}\.\(205\)Next, since the gradient objective𝕍H∼pω,πθ​\[IS⁡\(πe,πθ,H\)\]\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]is differentiable and convex inθ\\theta, we have the subgradient inequality that

⟨𝒢i,θi−θ∗⟩≥𝕍H∼pωi,πθi​\[IS⁡\(πe,πθi,H\)\]−𝕍H∼pωi,πθ∗​\[IS⁡\(πe,πθ∗,H\)\]\.\\displaystyle\\Big\\langle\\mathcal\{G\}\_\{i\},\\theta\_\{i\}\-\\theta^\{\*\}\\Big\\rangle\\geq\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\_\{i\}\},\\pi\_\{\\theta\_\{i\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{i\}\},H\)\]\-\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\_\{i\}\},\\pi\_\{\\theta^\{\*\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta^\{\*\}\},H\)\]\.\(206\)Remember that we defined

Φ⁡\(θ\)≐maxpω⁡𝕍H∼pω,πθ​\[IS⁡\(πe,πθ,H\)\]\.\\displaystyle\\Phi\(\\theta\)\\doteq\\max\_\{p\_\{\\omega\}\}\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\},\\pi\_\{\\theta\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\},H\)\]\.\(207\)Thus,

𝕍H∼pωi,πθ∗​\[IS⁡\(πe,πθ∗,H\)\]≤Φ⁡\(θ∗\),\\displaystyle\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\_\{i\}\},\\pi\_\{\\theta^\{\*\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta^\{\*\}\},H\)\]\\leq\\Phi\(\\theta^\{\*\}\),\(208\)and by Algorithm[2](https://arxiv.org/html/2608.24146#alg2),

maxp⁡𝕍H∼p,πθi​\[IS⁡\(πe,πθi,p,H\)\]=Φ⁡\(θi\)≤𝕍H∼pωi,πθi​\[IS⁡\(πe,πθi,H\)\]\+ϵi\.\\displaystyle\\max\_\{p\}\\mathbb\{V\}\_\{H\\sim p,\\pi\_\{\\theta\_\{i\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{i\}\},p,H\)\]=\\Phi\(\\theta\_\{i\}\)\\leq\\mathbb\{V\}\_\{H\\sim p\_\{\\omega\_\{i\}\},\\pi\_\{\\theta\_\{i\}\}\}\[\\mathrm\{IS\}\(\\pi\_\{e\},\\pi\_\{\\theta\_\{i\}\},H\)\]\+\\epsilon\_\{i\}\.\(209\)Therefore,

⟨𝒢i,θi−θ∗⟩≥Φ⁡\(θi\)−ϵi−Φ⁡\(θ∗\)\.\\displaystyle\\Big\\langle\\mathcal\{G\}\_\{i\},\\theta\_\{i\}\-\\theta^\{\*\}\\Big\\rangle\\geq\\Phi\(\\theta\_\{i\}\)\-\\epsilon\_\{i\}\-\\Phi\(\\theta^\{\*\}\)\.\(210\)Putting it all together, by \([204](https://arxiv.org/html/2608.24146#A1.E204)\), \([205](https://arxiv.org/html/2608.24146#A1.E205)\), and \([210](https://arxiv.org/html/2608.24146#A1.E210)\), we have

‖θi\+1−θ∗‖2≤\\displaystyle\\norm\{\\theta\_\{i\+1\}\-\\theta^\*\}^\{2\}\\leq‖θi−θ∗‖2−2​α​\(Φ⁡\(θi\)−ϵi−Φ⁡\(θ∗\)\)\+α2​LΘ2\.\\displaystyle\\norm\{\\theta\_i\-\\theta^\*\}^\{2\}\-2\\alpha\\quantity\(\\Phi\(\\theta\_i\)\-\\epsilon\_i\-\\Phi\(\\theta^\*\)\)\+\\alpha^\{2\}L^\{2\}\_\{\\Theta\}\.\(211\)Rearranging the terms, we get

2​α​\[Φ⁡\(θi\)−Φ⁡\(θ∗\)\]≤‖θi−θ∗‖2−‖θi\+1−θ∗‖2\+2​α​ϵi\+α2​LΘ2\.\\displaystyle 2\\alpha\\quantity\[\\Phi\(\\theta\_i\)\-\\Phi\(\\theta^\*\)\]\\leq\\norm\{\\theta\_i\-\\theta^\*\}^\{2\}\-\\norm\{\\theta\_\{i\+1\}\-\\theta^\*\}^\{2\}\+2\\alpha\\epsilon\_\{i\}\+\\alpha^\{2\}L^\{2\}\_\{\\Theta\}\.\(212\)Taking the summation overii,

2​α​∑i=0n−1Φ⁡\(θi\)−Φ⁡\(θ∗\)≤‖θ0−θ∗‖2\+2​α​∑i=0n−1ϵi\+n​α2​LΘ2\.\\displaystyle 2\\alpha\\sum\_\{i=0\}^\{n\-1\}\\Phi\(\\theta\_\{i\}\)\-\\Phi\(\\theta^\{\*\}\)\\leq\\norm\{\\theta\_0\-\\theta^\*\}^\{2\}\+2\\alpha\\sum\_\{i=0\}^\{n\-1\}\\epsilon\_\{i\}\+n\\alpha^\{2\}L^\{2\}\_\{\\Theta\}\.\(213\)Sinceθ0,θ∗∈Θ\\theta\_\{0\},\\theta^\{\*\}\\in\\Theta, and we defineddiam⁡\(Θ\)≤D\\mathrm\{diam\}\(\\Theta\)\\leq Dwhere

diam⁡\(Θ\)≐maxθ,θ′∈Θ⁡‖θ−θ′‖,\\displaystyle\\mathrm\{diam\}\(\\Theta\)\\doteq\\max\_\{\\theta,\\theta^\{\\prime\}\\in\\Theta\}\\norm\{\\theta\-\\theta'\},\(214\)we have

‖θ0−θ∗‖2≤D2\.\\displaystyle\\norm\{\\theta\_0\-\\theta^\*\}^\{2\}\\leq D^\{2\}\.\(215\)Thus,

1n​∑i=0n−1Φ⁡\(θi\)−Φ⁡\(θ∗\)≤D22​α​n\+α​LΘ22\+1n​∑i=0n−1ϵi\.\\displaystyle\\frac\{1\}\{n\}\\sum\_\{i=0\}^\{n\-1\}\\Phi\(\\theta\_\{i\}\)\-\\Phi\(\\theta^\{\*\}\)\\leq\\frac\{D^\{2\}\}\{2\\alpha n\}\+\\frac\{\\alpha L^\{2\}\_\{\\Theta\}\}\{2\}\+\\frac\{1\}\{n\}\\sum\_\{i=0\}^\{n\-1\}\\epsilon\_\{i\}\.\(216\)
According to Algorithm[2](https://arxiv.org/html/2608.24146#alg2),

θ¯≐1n​∑i=0n−1θi\.\\displaystyle\\bar\{\\theta\}\\doteq\\frac\{1\}\{n\}\\sum\_\{i=0\}^\{n\-1\}\\theta\_\{i\}\.\(217\)By Lemma[5\.3](https://arxiv.org/html/2608.24146#S5.Thmtheorem3),Φ⁡\(πθ\)\\Phi\(\\pi\_\{\\theta\}\)is convex inθ\\theta\. Thus, by induction with the basic convex property, with the nonnegative weight1n\\frac\{1\}\{n\}and the fact that∑i=0n−1=1\\sum\_\{i=0\}^\{n\-1\}=1, we obtain

Φ⁡\(θ¯\)=Φ​\(1n​∑i=0n−1θi\)≤1n​∑i=0n−1Φ⁡\(θi\)\.\\displaystyle\\Phi\(\\bar\{\\theta\}\)=\\Phi\\quantity\(\\frac\{1\}\{n\}\\sum\_\{i=0\}^\{n\-1\}\\theta\_i\)\\leq\\frac\{1\}\{n\}\\sum\_\{i=0\}^\{n\-1\}\\Phi\(\\theta\_\{i\}\)\.\(218\)SubtractingΦ⁡\(θ∗\)\\Phi\(\\theta^\{\*\}\)form both sides, we get

Φ⁡\(θ¯\)−Φ⁡\(θ∗\)≤1n​∑i=0n−1Φ⁡\(θi\)−Φ⁡\(θ∗\)\.\\displaystyle\\Phi\(\\bar\{\\theta\}\)\-\\Phi\(\\theta^\{\*\}\)\\leq\\frac\{1\}\{n\}\\sum\_\{i=0\}^\{n\-1\}\\Phi\(\\theta\_\{i\}\)\-\\Phi\(\\theta^\{\*\}\)\.\(219\)Plugging it into \([216](https://arxiv.org/html/2608.24146#A1.E216)\),

Φ⁡\(θ¯\)−Φ⁡\(θ∗\)≤D22​α​n\+α​LΘ22\+1n​∑i=0n−1ϵi\.\\displaystyle\\Phi\(\\bar\{\\theta\}\)\-\\Phi\(\\theta^\{\*\}\)\\leq\\frac\{D^\{2\}\}\{2\\alpha n\}\+\\frac\{\\alpha L^\{2\}\_\{\\Theta\}\}\{2\}\+\\frac\{1\}\{n\}\\sum\_\{i=0\}^\{n\-1\}\\epsilon\_\{i\}\.\(220\)With the definitionθ∗≐argminθ∈ΘΦ​\(θ\)\\theta^\{\*\}\\doteq\\argmin\_\{\\theta\\in\\Theta\}\\Phi\(\\theta\)andα≐DLΘ​n\\alpha\\doteq\\frac\{D\}\{L\_\{\\Theta\}\\sqrt\{n\}\}, we then have

Φ⁡\(θ¯\)−minθ∈Θ⁡Φ⁡\(θ\)≤D​LΘn\+1n​∑i=0n−1ϵi\.\\displaystyle\\Phi\(\\bar\{\\theta\}\)\-\\min\_\{\\theta\\in\\Theta\}\\Phi\(\\theta\)\\leq\\frac\{DL\_\{\\Theta\}\}\{\\sqrt\{n\}\}\+\\frac\{1\}\{n\}\\sum\_\{i=0\}^\{n\-1\}\\epsilon\_\{i\}\.\(221\)∎

## Appendix BNumerical Studies

Figure 3:Supplementary figure for Section[6\.1](https://arxiv.org/html/2608.24146#S6.SS1)\. Relative variance of each method under its tailored adversarial transition\. All values are normalized by the variance of the on\-policy Monte Carlo \(MC\) method \(under its tailored adversarial transition\) in the same environment\. Error bars denote the standard error over 900 total runs per environment \(30 target policies with 30 independent runs each\)\.In our numerical studies, we leverage a wide range of target policies ranging from completely random to highly deterministic\. Specifically, a policyπtrain\\pi\_\{\\text\{train\}\}is computed as the optimal policy of the MDP model, andπrandom\\pi\_\{\\text\{random\}\}is randomly generated\. Then, the target policiesπe\\pi\_\{e\}are set to be\(1−β\)​πtrain\+β​πrandom\(1\-\\beta\)\\pi\_\{\\text\{train\}\}\+\\beta\\pi\_\{\\text\{random\}\}withβ∈\{130,230,…,1\}\\beta\\in\\\{\\frac\{1\}\{30\},\\frac\{2\}\{30\},\.\.\.,1\\\}\. For each of the3030target policies, we have3030independent runs, resulting in a total of900900runs for each value\.

In Section[6\.1](https://arxiv.org/html/2608.24146#S6.SS1), we generate method\-specific adversarial transitions by running Algorithm[1](https://arxiv.org/html/2608.24146#alg1)separately for each method, yielding one adversarial transition per behavior policy\. For ROS\([Zhong et al\., 2022](https://arxiv.org/html/2608.24146#bib.bib48)\), which adapts its behavior policy, we generate the adversarial transition by treating the target policy as the nominal behavior policy in Algorithm[1](https://arxiv.org/html/2608.24146#alg1)\. We first measure each method’s variance under the original simulator transitionp0p\_\{0\}, and then under its method\-specific adversarial transitionpadvp\_\{\\text\{adv\}\}\. Note thatpadvp\_\{\\text\{adv\}\}differs across methods\. We report the relative variance of each method under its ownpadvp\_\{\\text\{adv\}\}in Figure[3](https://arxiv.org/html/2608.24146#A2.F3), where each value is normalized by the variance of MC \(also under itspadvp\_\{\\text\{adv\}\}\)\. Finally, we report the variance increase for each method in Figure[1](https://arxiv.org/html/2608.24146#S5.F1), defined as the difference between its variance underpadvp\_\{\\text\{adv\}\}and underp0p\_\{0\}\. In Section[6\.2](https://arxiv.org/html/2608.24146#S6.SS2), we evaluate all methods under a shared adversarial target transition\. This transition is constructed by applying Algorithm[1](https://arxiv.org/html/2608.24146#alg1)to the on\-policy Monte Carlo baseline\. We then report each method’s variance under this transition in Figure[2](https://arxiv.org/html/2608.24146#S6.F2)\.

### B\.1Experimental Setup

To ensure reproducibility and to isolate the source of variance reduction across methods, we adopt a uniform experimental protocol across all four environments\. Our setup follows the standard conventions established in the behavior policy search literature\([Hanna et al\., 2017](https://arxiv.org/html/2608.24146#bib.bib49);[Hanna et al\., 2024](https://arxiv.org/html/2608.24146#bib.bib43);[Zhong et al\., 2022](https://arxiv.org/html/2608.24146#bib.bib48)\)\. We parameterize the behavior policyπθ\\pi\_\{\\theta\}as a two\-layer multilayer perceptron \(MLP\) with 64 hidden units per layer and tanh activations, followed by a softmax output head over the discrete action space\. We adopt the same architecture for the adversarial transition modelpωp\_\{\\omega\}, with its softmax head defined over the discrete next\-state space\. This shared architecture, deployed identically across environments and across all four methods, removes parameterization choices as a source of confounding variance in our comparisons\.

We optimize all network parameters with the Adam optimizer\([Kingma and Ba, 2015](https://arxiv.org/html/2608.24146#bib.bib54)\), using a learning rate of10−310^\{\-3\}and the default momentum coefficientsβ1=0\.9\\beta\_\{1\}=0\.9andβ2=0\.999\\beta\_\{2\}=0\.999, with related work studying deep\-network trainability under continued learning\([Wang et al\., 2026](https://arxiv.org/html/2608.24146#bib.bib3)\)\. For BPG\([Hanna et al\., 2017](https://arxiv.org/html/2608.24146#bib.bib49)\)and ROS\([Zhong et al\., 2022](https://arxiv.org/html/2608.24146#bib.bib48)\), we adopt the hyperparameters reported in their original publications, ensuring that each baseline is evaluated under conditions favorable to its own design\. All four methods \(MC, BPG, ROS, and DRVG\) are trained on the same initial simulator transition and evaluated against the same set of target policies, so any performance differences are attributable to the variance\-reduction strategy itself rather than to environment configuration\.

To establish the statistical reliability of our reported numbers, we evaluate each method across 30 target policies generated by the mixing schemeπe=\(1−β\)​πtrain\+β​πrandom\\pi\_\{e\}=\(1\-\\beta\)\\pi\_\{\\text\{train\}\}\+\\beta\\pi\_\{\\text\{random\}\}described in Appendix[B](https://arxiv.org/html/2608.24146#A2), with 30 independent runs per target policy\. This yields 900 total runs per reported value\. Error bars in Figures[1](https://arxiv.org/html/2608.24146#S5.F1),[2](https://arxiv.org/html/2608.24146#S6.F2), and[3](https://arxiv.org/html/2608.24146#A2.F3)denote the standard error of the mean computed across these 900 runs\. This protocol provides sufficient resolution to detect consistent variance differences between methods, which is essential given the high baseline variance of policy evaluation under transition perturbations\. Recent work also studies evaluation in scientific and formal reasoning settings\([Liu et al\., 2026e](https://arxiv.org/html/2608.24146#bib.bib4);[Chen et al\., 2026a](https://arxiv.org/html/2608.24146#bib.bib12)\)\.

All experiments were conducted on a single shared compute node equipped with two AMD EPYC 7663 processors \(56 cores per socket, two sockets, two threads per core, yielding 224 logical CPUs of which 222 are allocatable to jobs\) and 1024 GB of system memory \(1000 GB allocatable\)\.

### B\.2Garnet Examples

A Garnet environment\([Archibald et al\., 1995](https://arxiv.org/html/2608.24146#bib.bib22)\)is represented by three integers\(\|S\|,\|A\|,b\)\(\|S\|,\|A\|,b\), denoting the number of states, actions, and the branching factor, respectively\. By varyingbb, one controls the degree of stochasticity: smallbbyields sparse transitions, while largebbapproaches fully connected transitions\. This flexibility makes Garnets particularly suitable for stress\-testing reinforcement learning algorithms across a wide spectrum of transition structures\([Tarbouriech and Lazaric, 2019](https://arxiv.org/html/2608.24146#bib.bib20);[Wang et al\., 2023a](https://arxiv.org/html/2608.24146#bib.bib42);[Wang et al\., 2023b](https://arxiv.org/html/2608.24146#bib.bib21)\)\. We evaluate the four methods on three Garnet instances—G⁡\(5,3,3\)G\(5,3,3\),G⁡\(10,5,5\)G\(10,5,5\), andG⁡\(30,15,10\)G\(30,15,10\)—which span increasing environment sizes and connectivity levels\.

### B\.3Inventory Management

Inventory management\([Porteus, 2002](https://arxiv.org/html/2608.24146#bib.bib19);[Ho et al\., 2018](https://arxiv.org/html/2608.24146#bib.bib18);[Liu et al\., 2026a](https://arxiv.org/html/2608.24146#bib.bib1)\)is a classical stochastic control problem under transition uncertainty\. The state corresponds to inventory levels, actions represent order quantities, and stochastic demand drives the state transitions\. In our inventory management example, we adopt radial\-type basis functions as introduced in[Sutton and Barto \(2018\)](https://arxiv.org/html/2608.24146#bib.bib53), defined for statessand feature indexiiasϕi​\(s\)=exp⁡\(−‖s−ci‖22​σi2\),\\phi\_\{i\}\(s\)=\\exp\\\!\\left\(\-\\frac\{\\\|s\-c\_\{i\}\\\|^\{2\}\}\{2\\sigma\_\{i\}^\{2\}\}\\right\),wherecic\_\{i\}andσi\\sigma\_\{i\}denote the deterministic center and scaling parameter of theii\-th feature, respectively\. This nonlinear parameterization captures variations in state representation while controlling the expressive capacity of the model under uncertainty\.