Provably Safe Sim-to-Real Transfer

Provably Safe Sim-to-Real Transfer

arXiv:2609.01418v1 [cs.LG] 1 Sep 2026

Tingting Ni SYCAMORE, EPFL tingting.ni@epfl.ch

Maryam Kamgarpour SYCAMORE, EPFL maryam.kamgarpour@epfl.ch

Abstract To mitigate the sample complexity of real-world reinforcement learning (RL), a common practice is to first train a policy in a simulator, where samples are cheap, and then deploy the learned policy in the real world with the hope that it generalizes effectively. Such direct sim-to-real transfer is not guaranteed to succeed: simulator-trained policies can be suboptimal in the real world due to sim-to-real mismatch. Correcting this mismatch requires collecting data from the real system, but in many applications, such as robotics and healthcare, this data-collection process is itself subject to safety constraints. This gives rise to the problem of safe sim-to-real transfer: how can an agent exploit an imperfect simulator while ensuring safe real-world data collection and learning a near-optimal feasible policy for the target system? We address this problem by formulating safe sim-to-real transfer within the framework of reward-free safe RL. We design a computationally efficient algorithm that exploits simulator information to provably reduce real-world interaction while ensuring safe exploration and enabling the computation of a near-optimal feasible policy for any potential reward function. Our real-world sample complexity bound characterizes the benefit of using the simulator in terms of the sim-to-real mismatch.

1

Introduction

Over the last decade, reinforcement learning (RL) has achieved remarkable success in domains ranging from games and robotics to the natural sciences [Mnih et al., 2013, Silver et al., 2016, Ouyang et al., 2022, Lee et al., 2020, Degrave et al., 2022]. Despite this progress, deploying RL in real world remains challenging due to two central obstacles: sample complexity and safety. Learning directly on the target system can require many interactions, each of which may be costly and subject to safety requirements, such as collision avoidance in robotics [Haddadin et al., 2009] or compliance with operational constraints in healthcare [Kyrarini et al., 2021]. A common way to reduce costly real-world interaction is to use a simulator. In robotics and control, simulators are often constructed from physical models, system knowledge, or prior calibration, and can provide many cheap interactions. However, the real world is difficult to model perfectly, leading to simto-real mismatch [Tan et al., 2018, Peng et al., 2018]. Consequently, policies optimized in simulation may be suboptimal in the real world. In safety-critical applications, this mismatch is even more problematic: a policy that appears safe in simulation may violate safety constraints after deployment. This motivates safe sim-to-real transfer, where the goal is to exploit cheap simulator access while ensuring that the deployed policy is both near-optimal and feasible on the real system. To incorporate safety requirements, we model environments as constrained Markov decision processes (CMDPs), allowing the agent to learn policies that maximize reward while satisfying safety constraints. One approach to addressing sim-to-real mismatch is to enlarge the set of environments considered during simulation training. This is often done by assuming a distribution over simulated CMDPs and training policies that are robust across this distribution. For example, As et al. [2026] consider domain randomization for simulated CMDPs and optimize policies under worst-case constraints, Preprint.

while Zhang et al. [2024] study distributionally robust constrained RL. These methods can be viewed as one-shot transfer: the agent learns a policy in simulation that can be safely deployed on the real system. However, they may be conservative: the learned policies are designed to be safe in the real world, but their performance may be suboptimal because they optimize for worst-case or distributional performance rather than performance on the specific real system [Ye et al., 2023]. To reduce this conservatism, one can collect real-world data to fine tune the policy learned in simulation. This data-collection process must itself ensure constraint satisfaction, a requirement commonly referred to as safe exploration [Koller et al., 2018]. This gives rise to safe meta RL, which trains agents over a distribution of simulated CMDPs. When deployed on a real system assumed to be drawn from the same distribution, these agents can fine tune using relatively few real-world interactions while ensuring safe exploration [Ni and Kamgarpour, 2026, Xu and Zhu, 2026]. Among these works, Ni and Kamgarpour [2026] prove that learning a near-optimal policy while ensuring safe exploration requires only Õ(ε−2 C(D)) real-world samples, with a matching lower bound. Here, C(D) measures the complexity of the environment distribution D. This quantity can be small when D is concentrated on a low-dimensional family of environments, such as tasks described by a few latent parameters, but it can still suffer from the curse of dimensionality when D spreads broadly across the environment space, such as uniform distribution. Moreover, both one-shot transfer methods and safe meta RL rely on an important coverage assumption: the real system must be drawn from, or at least well covered by, the prescribed family or distribution of simulated CMDPs. This assumption may fail when the simulator is biased. For example, a robot may be trained with randomized friction or actuator parameters in simulation, while the real system exhibits unmodeled delays or contact effects. To handle settings without this coverage assumption, recent sim-to-real RL methods use the simulator to guide real-world data collection, either to correct simulator mismatch [Qu et al., 2025, Wu et al., 2026] or to learn an optimal policy in the real world [Wagenmaker et al., 2024]. However, they are developed for unconstrained settings. Directly applying them in safety-critical systems may lead to unsafe real-world interaction, which is unacceptable in applications such as autonomous driving, surgical robotics, and power-grid control. Online safe RL methods can ensure safe exploration in the real world. Prior model-based [Yu et al., 2025, Bura et al., 2022, Liu et al., 2021] and model-free [Ni and Kamgarpour, 2025b] methods provide high probability guarantees for learning a near-optimal policy under safe exploration, but they typically assume a single prespecified reward. In practice, reward functions are often iteratively engineered or vary across deployments [Jin et al., 2020, Ménard et al., 2021]; for example, in autonomous driving, different rewards may encode different target locations. Collecting new realworld data for each reward is therefore highly sample inefficient. This motivates reward-free safe RL [Miryoosefi and Jin, 2022, Huang et al., 2023], where the agent explores the environment without a prespecified reward, and later uses the learned information for planning under arbitrary reward functions. Specifically, after data collection, the agent should be able to compute a near-optimal feasible policy for any given reward without further real-world interaction. However, Miryoosefi and Jin [2022] do not ensure safe exploration during data collection, while Huang et al. [2023] ensure safe exploration but require solving a constrained nonconvex optimization problem to compute exploration policies, which is intractable in general.1 Moreover, these works are fully online and do not leverage simulators, which can be sample inefficient especially when simulator information is available. This motivates safe sim-to-real transfer without a simulator coverage assumption: how can an agent leverage a simulator to reduce real-world interaction while ensuring safe exploration and reward-free planning in the real system? We summarize our contributions below: 1. We formulate safe sim-to-real transfer as a reward-free safe RL problem, where the agent uses a simulator and limited real-world interaction under safe exploration guarantees to support accurate reward-free planning. We propose a computationally efficient algorithm that identifies reliable simulator regions, uses certified simulator transitions to reduce real-world interaction, and corrects sim-to-real mismatch with collected real-world data. 2. For our algorithm, we provide high-probability guarantees for safe real-world exploration and accurate reward-free planning; see Theorem 4.1. The sample-complexity bound characterizes the benefit of simulator access through the size of the mismatch region and the separation gap. When the sim-to-real 1

Their method maximizes a concave objective over a feasible set defined by a concave sublevel constraint over the policy space, which yields a nonconvex optimization problem.

2

mismatch is large, our framework recovers the fully online setting of Huang et al. [2023] and improves upon its sample-complexity bound. Additional comparisons with prior work are provided in Table 2. 3. We validate our theoretical results in a safety-critical gridworld environment. Our experiments show that the benefit of using the simulator is larger when the sim-to-real mismatch is smaller.

2

Problem setting

We first review background on constrained Markov decision processes (CMDPs), then formally state the safe sim-to-real transfer problem and its underlying assumptions. Notation. Let N and R denote the sets of natural numbers and real numbers, respectively. For a set X , ∆(X ) denotes the probability measure over X , and |X | denotes P its cardinality. For any p, q ∈ ∆(X ), their total variation distance is defined as ∥p − q∥TV := 21 x∈X |p(x) − q(x)|. For any integer m, we set [m] := {1, . . . , m}. For any scalar z ∈ R, we denote its positive part by [z]+ := max{z, 0}. Logical conjunction and disjunction are denoted by ∧ and ∨, respectively. 2.1

Constrained Markov Decision Processes

We consider a CMDP defined by a tuple M = (S, A, H, P, s1 , F, c) , where S and A are finite state and action spaces, and H is the horizon. The transition dynamics are given by P := {Ph }H h=1 , where Ph (s′ |s, a) denotes the probability of transitioning from state s to state s′ after taking action a at timestep h ∈ [H]. Without loss of generality, each iteration starts from a fixed initial state 2 s1 ∈ S. the CMDP may be equipped with a class of deterministic utility functions3  In addition, H F := f = {fh }h=1 fh : S × A → [0, 1], ∀h ∈ [H] . Each f ∈ F measures the performance of a policy, which we introduce next. Among these utility functions, the constraint function c ∈ F encodes the safety requirement. A Markov policy π = {πh }H h=1 is a collection of mappings πh : S → ∆(A), and we let Π denote the set of all such policies. Given a utility function f ∈ F, the agent interacts with M as follows. Starting from the initial state s1 , at each timestep h, it selects an action ah ∼ πh (· | sh ), receives utility fh (sh , ah ), and transitions to the next state sh+1 ∼ Ph (· | sh , ah ). To measure the cumulative utility collected by π under dynamics P , we define the state-action value function for each timestep PH ′ ′ ′ h and f ∈ F as QP,π h′ =h fh (sh , ah ) | (sh , ah ) = (s, a)], and the corresponding f,h (s, a) = EP,π [ PH P,π state value function as Vf,h (s) = EP,π [ h′ =h fh′ (sh′ , ah′ ) | sh = s]. We call a policy π feasible P,π in M if its constraint value satisfies Vc,1 (s1 ) ≥ ℓ, where ℓ ∈ [0, H] is a prescribed safety threshold. P,π The set of feasible policies is defined as ΠP feas := {π ∈ Π | Vc,1 (s1 ) ≥ ℓ}. And we call π strictly P,π feasible if Vc,1 (s1 ) > ℓ. 2.2

Safe sim-to-real transfer

In safe sim-to-real transfer, the agent has full access to a simulator during learning but is ultimately deployed in the real world. The goal is to exploit cheap simulator access so that the learned policies are feasible and near-optimal in the real world. However, two challenges remain. First, the simulator is only an approximation of the real world, and this mismatch may cause a policy that is feasible or optimal in simulation to become unsafe or suboptimal in the real world. Thus, simulator access alone is not sufficient: the agent must collect some real-world data to learn or correct for this mismatch. Second, the task objective may vary across deployments, such as when the agent must reach different target locations. We therefore allow the reward function to range over a family F of possible reward functions. In contrast, we assume a common constraint function c, since the simulator is intended to model the same physical system in which the learned policy will ultimately operate. Consequently, safety specifications, such as collision avoidance in autonomous driving 2

As explained by Fiechter [1994], if the initial state is instead drawn from a distribution s1 ∼ ρ, one can equivalently introduce an artificial initial state s0 such that P (· | s0 , a) := ρ(·) for every action a. This augments the state space and horizon each by one, and all bounds carry over with only this constant-size modification. 3 While we study deterministic utility functions for notational simplicity, our results generalize to randomized utility functions.

3

or joint limits in robotic manipulation, are determined by the underlying real system and remain unchanged across simulation and deployment. However, collecting new real-world data for every reward function would be highly sample inefficient. These considerations motivate a hybrid, reward-free safe RL formulation. In online RL, the agent learns only through interactions with the real world. By contrast, hybrid RL [Song et al., 2023, Xie et al., 2021] allows the agent to leverage both simulator information and real-world interactions, making it well suited for correcting sim-to-real mismatch with limited real-world data. To accommodate varying reward functions under safety constraints, we further adopt the reward-free safe RL perspective [Miryoosefi and Jin, 2022, Huang et al., 2023]: the agent first learns a real-world dynamics model, which can then be used to compute near-optimal feasible policies for any reward function in F. Combining these two perspectives, we formulate the learning problem as follows. During learning, the agent can interact with the real world Mreal = (S, A, H, P real , s1 , F, c) by rolling out policies. A rollout of policy π generates a trajectory τ π = {sh , ah , sh+1 }H h=1 , where real ah ∼ πh (· | sh ) and sh+1 ∼ Ph (· | sh , ah ). The agent also has full knowledge of the simulator Msim = (S, A, H, P sim , s1 , F, c), which differs from Mreal only in its transition dynamics. Since data collection occurs in the real world, where constraint violations such as collisions in autonomous navigation are not permitted, every policy deployed in Mreal must satisfy the safety constraint. We formalize this requirement as safe exploration. Definition 2.1 (Safe exploration). An algorithm that produces a sequence of policies {π t }Tt=1 ensures safe exploration in Mreal if π t is feasible in Mreal for every t ∈ [T ]. Objective. Design an algorithm that ensures safe exploration in Mreal during data collection and, for any reward function r ∈ F, computes without further real-world interaction a policy π satisfying real

(Near-optimality)

P Vr,1

,π ⋆

real

P where π ⋆ ∈ arg maxπ∈ΠP real Vr,1

real

P (s1 ) − Vr,1 ,π

,π

(s1 ) ≤ ϵ

and

(Feasibility)

real

π ∈ ΠP feas , (1)

(s1 ).

feas

We say that the algorithm achieves ϵ-planning accuracy if the above condition holds for all r ∈ F. The efficiency of the algorithm is measured by the number of state-action pairs sampled from real world, which we refer to as the sample complexity. 2.3

Assumptions

To achieve this objective, we make two assumptions, both of which we will discuss in our experimental setup (see Section 5). The first is a standard Slater-type condition in safe RL [Bura et al., 2022, Yu et al., 2025, Ni and Kamgarpour, 2025b]: safe exploration requires a baseline policy that is strictly feasible in Mreal . Assumption 2.2 (Slater’s condition). There exist a known constant ξ > 0 and a known policy π 0 ∈ Π P real ,π 0 such that Vc,1 (s1 ) ≥ ℓ + ξ. The strict margin serves two purposes. Algorithmically, it provides a safety buffer that allows the agent to introduce exploratory behavior while maintaining feasibility. Statistically, it is required for finite-sample safety certification: if the baseline policy were only exactly feasible, that is, if ξ = 0, then estimation error arising from estimating its constraint value using rollouts of π 0 in Mreal could make it impossible to reliably distinguish the baseline policy from an infeasible one. Next, we adopt an assumption commonly used in hierarchical RL [Chua et al., 2023], meta RL [Chen et al., 2022, Mutti and Tamar, 2024, Brunskill and Li, 2013], and hybrid RL [Qu et al., 2025] to characterize the difference between two MDPs. In our setting, this difference corresponds to the mismatch between Mreal and Msim . The assumption requires this mismatch in transition dynamics to be statistically identifiable: for each time-state-action triple, the real-world and simulator transition kernels are either identical or well separated. We formalize this condition as follows. Assumption 2.3 (σs -separable shift). There exists a known constant σs ∈ (0, 1] such that, for every (h, s, a) ∈ [H] × S × A, Phreal (· | s, a) ̸= Phsim (· | s, a) =⇒ Phreal (· | s, a) − Phsim (· | s, a) TV ≥ σs . 4

This separation condition ensures that mismatch (h, s, a) triples can be distinguished from nonmismatch ones using finitely many real-world samples, where σs quantifies the magnitude of the mismatch in total variation distance. Without prior knowledge of σs , simulator knowledge may not be reliably exploitable. Indeed, Cheung and Lyu [2024] show that, in multi-armed bandits with access to a mismatch simulator Msim , no hybrid method can be guaranteed to outperform an online method without prior knowledge of σs . Since multi-armed bandits are a special case of MDPs with horizon H = 1, this suggests that such prior shift information is also necessary in our setting. Under Assumption 2.3, we define the mismatch region as the set of (h, s, a) triples at which the real-world and simulator transition kernels differ. Definition 2.4 (Mismatch region). The mismatch region B is defined as  B = (h, s, a) ∈ [H] × S × A : Phreal (· | s, a) ̸= Phsim (· | s, a) . When the simulator accurately models the real world, the mismatch region B is small.

3

Algorithm Design

In this section, we present our algorithm for safe sim-to-real transfer. The algorithm exploits simulator knowledge to reduce real-world interactions while ensuring safe exploration and ϵ-accurate planning for any reward r ∈ F. Our approach is inspired by the algorithm of Huang et al. [2023], referred to as RF-RL, which achieves the guarantees in Objective in the online RL setting. Directly applying RF-RL in our setting presents two challenges. First, RF-RL learns solely through interactions with Mreal and therefore cannot exploit simulator knowledge to reduce real-world sample complexity. Second, inspired by the unconstrained reward-free RL approach of Ménard et al. [2021], they compute the exploration policy by solving a constrained non-convex optimization problem, which is generally intractable. Our algorithm, presented in Algorithm 1, addresses these challenges by three components. First, it maintains confidence bounds around the empirical transition model constructed from real-world data and uses them to shrink the estimated mismatch region, which is initialized as the entire time-state-action space. Second, it constructs a hybrid model that uses empirical real-world transitions on the estimated mismatch region and simulator transitions elsewhere. Compared with the online RL setting in Huang et al. [2023], it improves sample efficiency by avoiding the need to relearn transition dynamics in the non-mismatch region. Third, it efficiently computes a safe exploration policy that visits the parts of the estimated mismatch region where real-world transition uncertainty can affect reward-free planning. Our algorithm is summarized below. Estimating the mismatch region. We start by initializing the estimated mismatch region as the entire time-state-action space, B̂ 0 = [H] × S × A, as in Line 1 of Algorithm 1. In Line 3, the algorithm iteratively shrinks this region by removing triples estimated to be non-mismatch. At the beginning of real each iteration t, given the trajectories {τ i }t−1 during previous iterations, we i=1 collected from M define the visitation counts for each (h, s, a) ∈ [H] × S × A as nth (s, a) :=

t−1 X

1{(sih ,aih )=(s,a)} , nth (s, a, s′ ) :=

i=1

t−1 X

1{(sih ,aih ,sih+1 )=(s,a,s′ )} .

i=1

The empirical transition model estimated from real-world data is defined as P̂ht,real (s′ | s, a) := 1{nth (s,a)>0}

nth (s, a, s′ ) 1 + 1{nth (s,a)=0} . nth (s, a) |S|

(2)

As shown in Lemma C.1, its statistical uncertainty is quantified by the confidence bound  q  t t t ρh (s, a) = min 1, β(nh (s, a), δ)/(2nh (s, a) ∨ 1) , where β(n, δ) := log(2|S||A|H/δ) + |S| log(8e(n + 1)). A triple (h, s, a) is classified as a non-mismatch triple only when its empirical real-world transition model P̂ht,real (· | s, a) is sufficiently close to the simulator transition model Phsim (· | s, a), after 5

Algorithm 1 Sim-to-real safe RL Require: A strictly feasible baseline policy π 0 with margin ξ, safety threshold ℓ, mismatch parameter σs , accuracy ε, simulator information Msim , and access to Mreal 1: Initialize n0h (s, a) ← 0 for all (h, s, a) ∈ [H] × S × A, and initialize B̂ 0 ← [H] × S × A 2: for t = 1, 2, . . . do 3: Construct B̂ t as in Equations (3) and (4) // Estimating the mismatch region 4: Construct P̂ t as in Equations (2) and (5) // Constructing the hybrid model P̂ t ,π 0 5: if Vc,1 (s1 ) < ℓ + ξ/2 then 6: πt ← π0 7: else P̂ t ,π 8: π̄ t ∈ arg maxπ∈ΠP̂ t Vb,1 (s1 ). feas   q Computing safe P̂ t ,π̄ t P̂ t ,π̄ t 9: ∆t ← min H, 3e HVb,1 (s1 ) + HVb,1 (s1 ) exploration policy 10: if ∆t ≤ ε/2 then 11: break the for loop 12: end if 13: π t ← αt π̄ t + (1 − αt )π 0 , where αt is defined in Equation (9) 14: end if 15: Roll out π t in Mreal and observe τ t := {(sth , ath , sth+1 )}H h=1 16: end for n t o t P̂ ,π P̂ ,π 17: return P̂ t and π out ∈ arg maxπ∈Π Vr,1 (s1 ) : Vc,1 (s1 ) ≥ ℓ + ε/2 for any r ∈ F

accounting for confidence bound ρth (s, a) of P̂ht,real (· | s, a). Specifically, define n o G t := (h, s, a) ∈ B̂ t−1 : P̂ht,real (· | s, a), Phsim (· | s, a) + ρth (s, a) ≤ σs /2 .

(3)

TV

The threshold σs /2 is chosen using Assumption 2.3: every mismatch triple is at least σs away from the simulator in total variation distance and therefore cannot belong to G t . We then update the estimated mismatch region as B̂ t := B̂ t−1 \ G t .

(4)

Lemma C.3 shows that, with high probability, no mismatch triple is removed. In particular, B̂ t is monotonically decreasing in t and satisfies B ⊆ B̂ t for every iteration t. Constructing the hybrid model. Given the estimated mismatch region B̂ t , we construct the hybrid model, as in Line 4 of Algorithm 1, P̂ht (· | s, a) := 1{(h,s,a)∈B̂t } P̂ht,real (· | s, a) + 1{(h,s,a)∈/ B̂t } Phsim (· | s, a).

(5)

Thus, the algorithm uses empirical real-world transition estimates on triples that may still be mismatch and reuses simulator transition dynamics elsewhere. Computing safe exploration policy. Given the hybrid model P̂ t , we seek a safe policy that visits the parts of the estimated mismatch region where real-world transition uncertainty can affect rewardfree planning. Since reward-free planning error is captured by the value estimation error et,π f,1 (s1 ) := real

P |Vf,1

,π

t

P̂ ,π (s1 )−Vf,1 (s1 )| for any policy π and utility function f ∈ F, the ideal exploration objective is

max

real f ∈F , π∈ΠP feas

et,π f,1 (s1 )

(6)

Solving this problem would yield a safe policy that collects real-world data in the regions most relevant to reducing the value estimation error. And the algorithm could then use these data to refine the hybrid model. However, this problem depends on the unknown real-world transition model and therefore cannot be optimized directly. Instead, we introduce the following lemma, which gives a computable certificate that upper-bounds this value estimation error et,π f,1 (s1 ). 6

Lemma 3.1. With probability at least 1 − δ, for every iteration t, policy π, and utility function f ∈ F,  q  P̂ t ,π P̂ t ,π et,π (s ) ≤ min 3e HV (s ) + HV (s ), H . 1 1 f,1 1 b,1 b,1 Here, for every h ∈ [H], s ∈ S, and π ∈ Π, # " H X P̂ t ,π h′ −h t Vb,h (s) := EP̂ t ,π (1 + 1/H) bh′ (sh′ , ah′ ) | sh = s , h′ =h

and for every h ∈ [H], s ∈ S, and a ∈ A, bth (s, a) := 1{(h,s,a)∈B̂t } min



 11Hβ(nth (s, a), δ) ,1 . nth (s, a) ∨ 1

The proof of Lemma 3.1 is provided in Appendix C.3. The bonus bth (s, a) is inspired by Ménard et al. [2021]: it is large when the empirical model P̂ht (· | s, a) has high uncertainty over (h, s, a). Unlike Ménard et al. [2021], our bonus is restricted to the estimated mismatch region and is zero outside it, since triples outside this region have been certified as non-mismatch with high probability P̂ t ,π and therefore introduce no real-world transition-estimation error. Consequently, Vb,1 (s1 ), which accumulates these bonuses along trajectories under π, upper bounds the value-estimation error. 4 P̂ t ,π As more real-world data are collected, bth (s, a) decreases, and so does Vb,1 (s1 ). t

P̂ ,π Lemma 3.1 shows that Vb,1 (s1 ) is a computable upper bound on the unknown value-estimation error t,π ef,1 (s1 ), uniformly over all policies π ∈ Π and utility functions f ∈ F. Therefore, we approximate t

real

P̂ ,π P Problem (6) by replacing its objective et,π f,1 (s1 ) with Vb,1 (s1 ), and its real-world feasible set Πfeas t

with the hybrid-model feasible set ΠP̂ feas . This gives the following computable optimization problem: t

P̂ ,π π̄ t ∈ arg maxt Vb,1 (s1 ).

(7)

π∈ΠP̂ feas

This is a standard CMDP defined by the hybrid model P̂ t , with reward given by the bonus function bt and constraint given by c. It can be solved efficiently using existing CMDP solvers, such as constrained policy optimization [Achiam et al., 2017], or exactly via linear programming in the occupancy-measure formulation [Altman, 2021]. t

Before solving (7), Algorithm 1 checks whether the feasible set ΠP̂ feas is empty. Line 5 verifies whether the hybrid model P̂ t gives sufficient safety margin for the strictly feasible baseline policy π 0 . If not, Line 6 uses π 0 as the safe exploration policy. Otherwise, Line 8 solves (7) to obtain π̄ t , the empirically feasible policy with the largest value estimation error. Its estimation error is bounded by   q P̂ t ,π̄ t P̂ t ,π̄ t ∆t := min H, 3e HVb,1 (s1 ) + HVb,1 (s1 ) . (8) ∆t is used in two places. First, it serves as the stopping criterion: when ∆t ≤ ε/2, Algorithm 1 terminates at Line 11, since the hybrid model is accurate enough for reward-free planning under the tightened constraint in Line 17, as formalized by Lemma C.6. Second, it bounds the possible constraint violation of π̄ t in Mreal , since π̄ t is guaranteed to be feasible only under the hybrid model. Indeed, real

P Vc,1

,π̄ t

t

t

P̂ ,π̄ (s1 ) ≥ Vc,1 (s1 ) − ∆t ≥ ℓ − ∆t .

Thus, π̄ t violates the safety constraint in Mreal by at most ∆t . To offset this possible violation and ensure safe exploration, the algorithm mixes π̄ t with the strictly feasible baseline policy π 0 . We use the following notion of a mixture policy. ′

The weights (1 + 1/H)h −h arise from the error recursion established in Appendix C.3: each Bellman backup propagates future error and adds a inflation factor 1 + 1/H due to the empirical Bernstein variance term. 4

7

PK Definition 3.2 (Mixture policy). A mixture policy is defined as π := k=1 dk πk , where {πk }K k=1 ⊂ K ∈ ∆(K). It is implemented by sampling an index i ∼ {d } once at the beginning Π and {dk }K k k=1 k=1 and then executing the corresponding policy πi for all timesteps. Specifically, Line 13 of Algorithm 1 defines the exploration policy as
P̂ t ,π̄ t π t := αt π̄ t + (1 − αt )π 0 , αt := ξ/(ξ + ℓ + ∆t − Vc,1 (s1 ) + ).

(9)

Here, αt is chosen so that the strict feasibility margin of π 0 compensates for the possible real-world constraint violation of π̄ t .

4

Theoretical Guarantees

In this section, we formalize the theoretical guarantees of our algorithm, including the real-world sample complexity required for safe exploration and ϵ-accurate planning. The main result is stated below. Theorem 4.1. Let Assumptions 2.2 and 2.3 hold. For ϵ ∈ (0, H] and δ ∈ (0, 1), set ε = ξϵ/(2H). Then, with probability at least 1 − δ, Algorithm 1 requires at most o  n
H 6 |S| H 6 |S| e max |B|, 2 H|S||A| − |B| log2 σs −1 O 2 ξ ϵ min{1, ϵ, ξ} ξ ϵ min{1, ϵ, ξ} | {z } | {z } (i)

(ii)

samples from Mreal and guarantees the following: 1. Safe exploration. Every executed policy is feasible in Mreal . 2. Planning accuracy. For any r ∈ F, the output policy π out is feasible and ϵ-optimal for the P real ,π true CMDP defined by maxπ∈ΠP real Vr,1 (s1 ). feas

The sample complexity of Algorithm 1 reflects two statistically different tasks. Term (i) is the cost of learning the real dynamics on the mismatch region B, and it scales linearly with |B|. Term (ii) is the cost of certifying the remaining triples as non-mismatch triples; it scales linearly with H|S||A| − |B| and polynomial with log σs−1 . Thus, larger separation makes non-mismatch triples easier to identify. Overall, the bound shows that Algorithm 1 adaptively balances using the simulator with learning the real dynamics, paying the real-dynamics learning cost primarily on the mismatch region.
e |A||S|2 H 8 /(ϵ2 ξ 4 ) samples from Mreal to The RF-RL algorithm of Huang et al. [2023] uses O obtain same guarantees as in Theorem 4.1, but in the online setting.5 By comparison, our algorithm improves on this benchmark in two ways. First, it is computationally efficient: whereas Huang et al. [2023] compute their exploration policy by solving a constrained non-convex program, we replace this step with a standard CMDP problem. Second, our algorithm recovers the online setting as a special case by taking B = [H] × S × A, so that every triple is treated as a mismatch triple and the simulator is never used. In this worst-case regime, and when ϵ ≤ min{1, ξ}, our sample complexity improves over Huang et al. [2023] by a factor of H/ξ 2 , showing that part of the gain comes from the algorithmic design itself. The improvement is even larger when the simulator is accurate on most triples, |B| ≪ H|S||A|, and the mismatch is well-seperated, σs ≫ 0. In this case, real-world interaction is concentrated on the small region where the simulator differs substantially from the real e 2 |S||A|/(ξ 2 |B|)). Thus, our algorithm preserves safe world, yielding a total saving of order O(H exploration while using real-world samples only where simulator knowledge is insufficient. Proof sketch. The full proof of Theorem 4.1 is given in Appendix C.4. The proof has three main ingredients. First, the estimated mismatch region is reliable. Lemma C.3 guarantees that no mismatch triple from B is removed, while Lemma C.4 guarantees that every non-mismatch triple is removed 2 e after O(|S|/σ s ) samples. Thus, real-world learning eventually concentrates on the true mismatch region, while identifying the non-mismatch triples incurs only finite sample complexity. Second, Lemma 3.1 shows that the uncertainty certificate ∆t defined in (8) upper-bounds both the planning 5 Huang et al. [2023] state their sample-complexity result in terms of the number of trajectories and assume that cumulative rewards and costs are bounded by 1. We rescale their bound to cumulative utilities of order H and multiply by H, since we measure the total number of state-action pairs sampled from Mreal .

8

Constraint value

12

Sim-to-real safe RL Reward-free safe RL

Unconstrained sim-to-real RL Safety threshold = 10.78

10 8 6 0

102

103

Iteration t

104

(a) Gridworld instance: red cells are the (b) Constraint values of deployed policies for three algorithms over mismatch region B, hatched cells are un- iterations. Markers denote termination points. Shaded regions safe, and the star marks the initial state s1 . indicate the min–max range across 10 seeds.

error and the possible constraint violation when transferring a policy from the hybrid model to Mreal . The algorithm uses this bound, together with the Slater margin of the baseline policy π 0 , to construct a mixture policy that guarantees safe exploration in Mreal . Finally, the algorithm terminates once ∆t ≤ ε/2. At this point, Lemma C.6 implies that the hybrid model is accurate enough for reward-free planning. Next, we bound the number of iterations until termination by counting how often each triple can contribute to the uncertainty certificate. Mismatch triples may need to be learned accurately, giving a learning cost proportional to |B|. Non-mismatch triples contribute only until they are identified and removed, giving an identification cost proportional to H|S||A| − |B|. These two terms give final sample complexity bound in Theorem 4.1.

5

Computational experiment

We evaluate our algorithm on a 5 × 5 gridworld with horizon H = 12, adapted from Sutton et al. [1998]. We compare against two baselines: (i) Reward-free safe RL, which treats all state-action pairs as mismatch triples and does not exploit simulator information, thereby isolating the benefit of simulator access; and (ii) Unconstrained sim-to-real RL, which exploits simulator information without enforcing safety, allowing us to quantify the cost of safe exploration. Both baselines are modifications of Algorithm 1 and are described in Appendix B. Experiment setup We consider a CMDP with stationary dynamics, i.e., Ph = P for all h ∈ [H] (a special case of our setting). The agent starts in the bottom-left corner (star in Figure 1a) and has four actions: up, right, down, and left. With probability 0.85, the intended action is executed; otherwise, the agent moves uniformly to a neighboring cell. The environment contains a central unsafe wall formed by three cells (hatched cells in Figure 1a). The constraint function is defined P real ,π as c(s, a) = 1{s is safe} , so Vc,1 (s1 ) ≥ ℓ limits the expected number of unsafe visits to at most sim H − ℓ. The simulator P corresponds to the nominal gridworld, while the real environment introduces three windy cells near the unsafe wall (red cells in Figure 1a). In these cells the transition kernel is overridden by the wind: with probability 0.8 the agent is pushed to the cell opposite the chosen direction (e.g., up sends it downward) instead of to the intended neighbor, while the remaining probability mass is distributed uniformly among neighboring cells. Because these windy cells are located adjacent to the unsafe wall, the resulting model mismatch is safety-critical: a policy optimized in the simulator expects to move away from the wall, but is instead pushed toward it. Safety versus sample complexity. Table 1 and Figure 1b summarize the performance of all methods. All methods achieve accurate planning, but differ substantially in safety and sample complexity. The unconstrained sim-to-real baseline is the most sample-efficient, but violates the safety constraint in 68.5% of learning iterations. At the other extreme, the reward-free safe RL baseline guarantees safety throughout learning but requires 7.5× as many samples from Mreal compared with unconstrained sim-to-real baseline. Our method strikes a favorable balance: it maintains safe exploration while using only 2× more samples than the unconstrained baseline. These results show that simulator 9

Table 1: Performance comparison over 10 seeds. Planning accuracy is defined in (1) and is reported as mean ± standard deviation over 20 random reward functions per seed. Unsafe iterations denote the fraction of learning iterations in which the constraint is violated.

Algorithm

Samples from Mreal

Planning accuracy

Unsafe iterations

Sim-to-real safe RL Reward-free safe RL Unconstrained sim-to-real RL

77, 958 ± 1, 334 296, 910 ± 1, 484 39, 342 ± 140

0.000 ± 0.000 0.000 ± 0.000 0.000 ± 0.000

0.0% 0.0% 68.5%

information can be exploited safely to substantially reduce real-world interaction without sacrificing planning accuracy. Figure 2 provides further insight into how these gains arise by visualizing the state visitation distribution of each algorithm. Sim-to-real safe RL concentrates its exploration on the mismatch region, while the reward-free safe RL baseline spreads visits almost uniformly across the grid, re-learning dynamics that the simulator already models correctly. Meanwhile, sim-to-real safe RL spends less time visiting the unsafe region compared with the unconstrained baseline.

Reward-free safe RL (295,980 samples)

Unconstrained sim-to-real RL (39,360 samples)

30%

Share of state visits

Sim-to-real safe RL (79,380 samples)

10% 5% 2% 1%

Figure 2: State visitation of the three algorithms. Each panel is normalized by the algorithm’s total number of samples, reported in the panel title, so the plots show the share of visits falling in each cell and compare where real-world interaction is spent. The color scale is shared across panels and logarithmic. We use a logarithmic scale because s1 accounts for 10–29% of visits simply by being visited once per iteration by construction, which would otherwise dominate the rest of the grid on a linear scale. Assumption verification. For Assumption 2.2, π 0 can be obtained in practice either from expert demonstrations via behavior cloning [Torabi et al., 2018] or from a known safe controller. The margin ξ can then be estimated by rolling out π 0 in Mreal . In our experiments, we manually construct π 0 using the gridworld structure. For Assumption 2.3, σs can be specified using domain knowledge or estimated from independent data [Brunskill and Li, 2013]. We further provide a practical estimation procedure in Algorithm 4. Proposition B.1 shows that the resulting estimate is conservative, i.e., σ̂s ≤ σs , when all mismatch triples are covered; otherwise, it gives a lower bound over the detected mismatch region. Appendix B.4.2 studies the sample complexity of estimating σs , showing that smaller values of σs require more samples for accurate estimation. Experiments in Appendix B.4.3 shows that misspecifying σ̂s affects sample complexity and planning accuracy, but not safe exploration. Underestimating σs preserves planning accuracy but increases sample complexity; when σ̂s = 0, the algorithm degenerates to reward-free safe RL. Overestimating σs can reduce sample complexity, but may remove true mismatch triples from B̂ t ; in our experiments, planning failures appear when σ̂s is as large as 2.5σs , as the returned policy is not feasible in Mreal . Implementation details and additional ablation results on |B| and σs are provided in Appendix B.

6

Conclusion and future work

We proposed a computationally efficient algorithm for safe sim-to-real transfer that uses simulator to guide real-world data collection under safe exploration, identifies sim-to-real mismatch, and corrects 10

it using the collected data. Our analysis shows that the algorithm guarantees safe exploration and supports ϵ-accurate planning with high probability. The sample-complexity bound characterizes the benefit of simulator access: when the mismatch region is small and well separated, the required number of real-world samples scales with the size of the mismatch region rather than the full state-action-time space. Experiments in a gridworld illustrate the benefit of exploiting simulator information for safe exploration and reward-free planning. Limitations and future work. This work considers tabular CMDPs. Extending it to continuous settings, such as linear CMDPs, is an important future direction. It would also be useful to relax the separability condition and study more general forms of simulator bias. Another direction is to further P̂ t ,π improve sample efficiency. Replacing the computable certificate Vb,1 with the tighter certificate from Lemma C.5 could improve sample complexity by a factor of H, but doing so would require an efficient way to exploit problem structure in the resulting non-convex optimization problem.

References Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International conference on machine learning, pages 22–31. Pmlr, 2017. Eitan Altman. Constrained Markov decision processes. Routledge, 2021. Yarden As, Chengrui Ray Qu, Benjamin Unger, Dongho Kang, Max van der Hart, Laixi Shi, Stelian Coros, Adam Wierman, and Andreas Krause. Spidr: A simple approach for zero-shot safety in sim-to-real transfer. Advances in Neural Information Processing Systems, 38:90882–90924, 2026. Emma Brunskill and Lihong Li. Sample complexity of multi-task reinforcement learning. In Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence, UAI’13, page 122–131, Arlington, Virginia, USA, 2013. AUAI Press. Archana Bura, Aria HasanzadeZonuzy, Dileep Kalathil, Srinivas Shakkottai, and Jean-Francois Chamberland. Dope: Doubly optimistic and pessimistic exploration for safe reinforcement learning. Advances in neural information processing systems, 35:1047–1059, 2022. Xiaoyu Chen, Jiachen Hu, Chi Jin, Lihong Li, and Liwei Wang. Understanding domain randomization for sim-to-real transfer. In International Conference on Learning Representations, 2022. Wang Chi Cheung and Lixing Lyu. Leveraging (Biased) information: Multi-armed bandits with offline data. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 8286–8309. PMLR, 21–27 Jul 2024. Kurtland Chua, Qi Lei, and Jason Lee. Provable hierarchy-based meta-reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 10918–10967. PMLR, 2023. Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017. Jonas Degrave, Federico Felici, Jonas Buchli, Michael Neunert, Brendan Tracey, Francesco Carpanese, Timo Ewalds, Roland Hafner, Abbas Abdolmaleki, Diego de Las Casas, et al. Magnetic control of tokamak plasmas through deep reinforcement learning. Nature, 602(7897):414–419, 2022. Claude-Nicolas Fiechter. Efficient reinforcement learning. In Proceedings of the seventh annual conference on Computational learning theory, pages 88–97, 1994. Sami Haddadin, Alin Albu-Schäffer, and Gerd Hirzinger. Requirements for safe robots: Measurements, analysis and new insights. The International Journal of Robotics Research, 28(11-12): 1507–1527, 2009. Ruiquan Huang, Jing Yang, and Yingbin Liang. Safe exploration incurs nearly no additional sample complexity for reward-free RL. In The Eleventh International Conference on Learning Representations, 2023. 11

Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International conference on machine learning, pages 4870–4879. PMLR, 2020. Anders Jonsson, Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Edouard Leurent, and Michal Valko. Planning in Markov decision processes with gap-dependent sample complexity. Advances in Neural Information Processing Systems, 33:1253–1263, 2020. Torsten Koller, Felix Berkenkamp, Matteo Turchetta, and Andreas Krause. Learning-based model predictive control for safe exploration. In 2018 IEEE conference on decision and control (CDC), pages 6059–6066. IEEE, 2018. Maria Kyrarini, Fotios Lygerakis, Akilesh Rajavenkatanarayanan, Christos Sevastopoulos, Harish Ram Nambiappan, Kodur Krishna Chaitanya, Ashwin Ramesh Babu, Joanne Mathew, and Fillia Makedon. A survey of robots in healthcare. Technologies, 9(1):8, 2021. Joonho Lee, Jemin Hwangbo, Lorenz Wellhausen, Vladlen Koltun, and Marco Hutter. Learning quadrupedal locomotion over challenging terrain. Science robotics, 5(47):eabc5986, 2020. Xin Liu, Bin Li, Pengyi Shi, and Lei Ying. An efficient pessimistic-optimistic algorithm for stochastic linear bandits with general constraints. Advances in Neural Information Processing Systems, 34: 24075–24086, 2021. Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. In International Conference on Machine Learning, pages 7599–7608. PMLR, 2021. Sobhan Miryoosefi and Chi Jin. A simple reward-free approach to constrained reinforcement learning. In International conference on machine learning, pages 15666–15698. PMLR, 2022. Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013. Mirco Mutti and Aviv Tamar. Test-time regret minimization in meta reinforcement learning. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 37016–37040. PMLR, 21–27 Jul 2024. Tingting Ni and Maryam Kamgarpour. A learning-based approach to stochastic optimal control under reach-avoid constraint. In Proceedings of the 28th ACM International Conference on Hybrid Systems: Computation and Control, pages 1–8, 2025a. Tingting Ni and Maryam Kamgarpour. A safe exploration approach to constrained markov decision processes. In Yingzhen Li, Stephan Mandt, Shipra Agrawal, and Emtiyaz Khan, editors, Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pages 3592–3600. PMLR, 03–05 May 2025b. Tingting Ni and Maryam Kamgarpour. Constrained meta reinforcement learning with provable test-time safety. In Forty-third International Conference on Machine Learning, 2026. Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730– 27744, 2022. Xue Bin Peng, Marcin Andrychowicz, Wojciech Zaremba, and Pieter Abbeel. Sim-to-real transfer of robotic control with dynamics randomization. In 2018 IEEE international conference on robotics and automation (ICRA), pages 3803–3810. IEEE, 2018. 12

Chengrui Qu, Laixi Shi, Kishan Panaganti, Pengcheng You, and Adam Wierman. Hybrid transfer reinforcement learning: Provable sample efficiency from shifted-dynamics data. In Yingzhen Li, Stephan Mandt, Shipra Agrawal, and Emtiyaz Khan, editors, Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pages 1054–1062. PMLR, 03–05 May 2025. David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484–489, 2016. Yuda Song, Yifei Zhou, Ayush Sekhari, Drew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hybrid RL: Using both offline and online data can make RL efficient. In The Eleventh International Conference on Learning Representations, 2023. Richard S Sutton, Andrew G Barto, and Andrew Barto. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998. Jie Tan, Tingnan Zhang, Erwin Coumans, Atil Iscen, Yunfei Bai, Danijar Hafner, Steven Bohez, and Vincent Vanhoucke. Sim-to-real: Learning agile locomotion for quadruped robots. arXiv preprint arXiv:1804.10332, 2018. Faraz Torabi, Garrett Warnell, and Peter Stone. Behavioral cloning from observation. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI’18, page 4950–4957. AAAI Press, 2018. ISBN 9780999241127. Andrew Wagenmaker, Kevin Huang, Liyiming Ke, Kevin Jamieson, and Abhishek Gupta. Overcoming the sim-to-real gap: Leveraging simulation to learn to explore for real-world rl. Advances in Neural Information Processing Systems, 37:78715–78765, 2024. Zheshun Wu, Renjie Zheng, Jinhang Zuo, Zenglin Xu, and Fang Kong. A unified algorithmic framework for hybrid reinforcement learning in tabular mdps with shifted transition dynamics. arXiv preprint arXiv:2607.25207, 2026. Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample-efficient offline and online reinforcement learning. Advances in neural information processing systems, 34:27395–27407, 2021. Siyuan Xu and Minghui Zhu. Efficient safe meta-reinforcement learning: Provable near-optimality and anytime safety. Advances in Neural Information Processing Systems, 38:31362–31406, 2026. Haotian Ye, Xiaoyu Chen, Liwei Wang, and Simon Shaolei Du. On the power of pre-training for generalization in rl: provable benefits and hardness. In International Conference on Machine Learning, pages 39770–39800. PMLR, 2023. Kihyun Yu, Duksang Lee, William Overman, and Dabeen Lee. Improved regret bound for safe reinforcement learning via tighter cost pessimism and reward optimism. In Reinforcement Learning Conference, 2025. Zhengfei Zhang, Kishan Panaganti, Laixi Shi, Yanan Sui, Adam Wierman, and Yisong Yue. Distributionally robust constrained reinforcement learning under strong duality. In Reinforcement Learning Conference, 2024.

13

Organization of the Appendix A Comparison with related work

15

B Experimental details

15

B.1 Baseline algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

B.2 Sample complexity versus the size of the mismatch region |B| . . . . . . . . . . .

17

B.3 Sample complexity versus the value of the separation parameter σs . . . . . . . . .

17

B.4 Estimating the separation parameter σs from real-world data . . . . . . . . . . . .

18

B.4.1 Algorithm for estimating σs and its guarantees . . . . . . . . . . . . . . .

19

B.4.2

Sample complexity of estimating σs . . . . . . . . . . . . . . . . . . . . .

21

B.4.3

Effect of misspecifying σs . . . . . . . . . . . . . . . . . . . . . . . . . .

21

C Proofs

22

C.1 Concentration events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

C.2 Analysis of the estimated mismatch region . . . . . . . . . . . . . . . . . . . . . .

24

C.3 Proof of Lemma 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

C.4 Proof of Theorem 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

D Supporting lemmas

38

14

A

Comparison with related work

In this section, we compare our setting with the best-known prior work along four directions: (i) sim-to-real, whether the algorithm exploits simulator information despite mismatch with the real world or learns entirely from real-world interaction, corresponding to the fully online setting; (ii) reward-free learning, whether the returned model supports planning for arbitrary reward functions or only the single reward used during learning; (iii) constraints, whether constraints are part of the problem formulation; and (iv) safe exploration, whether the algorithm guarantees that constraints are satisfied during learning. We also compare the total number of state-action pairs sampled from the real world to obtain ϵ-accurate planning, for either a fixed reward or arbitrary rewards depending on the setting of each paper. The results are summarized in Table 2. Our method is the only one in the comparison that simultaneously handles simulator mismatch, constraints, safe real-world exploration, and reward-free planning for arbitrary rewards. To the best of our knowledge, it is the first provable algorithm with all four properties. Table 2: Comparison with related work. Algorithm

Sim-to-real

Reward

Constraints

Safe exploration

Sample complexity

Ménard et al. [2021]

×

any

×

×

Miryoosefi and Jin [2022]

×

any

✓

×

H 4 |S||A| 2  4ϵ  H |S||A| e O ϵ2

Huang et al. [2023]

×

any

✓

✓

e O

Yu et al. [2025]

×

fixed

✓

✓

Ni and Kamgarpour [2025a]

×

fixed

✓

✓

Wagenmaker et al. [2024] Qu et al. [2025]

✓

fixed

×

×

✓

fixed

×

×

Wu et al. [2026]

✓

fixed

×

×

Algorithm 1 (ours)

✓

any

✓

✓









e O

|A||S|2 H 8 2 4  ϵ ξ2 6  |A||S| H e O 2 2  ϵ ξ 

e O

1 min{ϵ6 ,ξ6 }

e O



H 16 ϵ8



  4  3 3 2 e min H |A||S| , H |B| + H |S| |A| O 2 2 2 2 ϵ  ϵ  σs σr

e O

 e O

H 4 |A||S| ϵ2

  |S|H 6 |B| + (H|S||A| − |B|)log2 σ1s  ξ 2 ϵ min{1, ϵ, ξ}

Remark. Both Qu et al. [2025], Wu et al. [2026] study finite-horizon MDPs with stationary transition dynamics. In Table 2, we report all bounds in terms of the number of state-action pairs sampled from the real environment and in our non-stationary finite-horizon setting. Thus, when a prior result is stated for stationary transitions and counts online iterations, we multiply by H to convert iterations to state-action samples and replace SA by HSA to account for time-dependent transition kernels. Moreover, Qu et al. [2025] assume σr -reachability: there exists a known constant σr ∈ (0, 1] such that, for every (h, s, a) ∈ [H] × S × A, max dP h π∈Π

real

,π

(s, a) ≥ σr ,

real

,π where dP (s, a) is the probability of visiting (s, a) at timestep h under policy π. As shown in h Table 2, their sample complexity depends polynomially on 1/σr . In contrast, our analysis does not require this reachability assumption and therefore has no dependence on σr .

B

Experimental details

Computational resources. All experiments were conducted on a single desktop machine equipped with an AMD Ryzen 9 9950X3D CPU (16 cores) and 128 GB RAM. No GPU was used. All planning subproblems were formulated as linear programs over the occupancy-measure polytope and solved using the HiGHS solver through SciPy. In our largest instance, each linear program contained H|S||A| = 1200 decision variables. 15

Stationary adaptation. Here, we describe how we adapt Algorithm 1 to the stationary setting, where the transition dynamics are time-independent. In this case, visitation counts are aggregated across timesteps: nt (s, a) =

t−1 X H X

1{(sih ,aih )=(s,a)} , nt (s, a, s′ ) =

i=1 h=1

t−1 X H X

1{(sih ,aih ,sih+1 )=(s,a,s′ )} .

i=1 h=1

The empirical model is P̂ t (s′ | s, a) = 1{nt (s,a)>0}

nt (s, a, s′ ) 1 + 1{nt (s,a)=0} , nt (s, a) |S|

The mismatch region and the exploration bonuses are indexed by (s, a) instead of (h, s, a), and each trajectory contributes H samples to the aggregated counts. B.1

Baseline algorithms

In this section, we describe two baseline algorithms: a reward-free safe RL algorithm and an unconstrained sim-to-real RL algorithm. Both are modifications of Algorithm 1 and are designed to isolate the benefits of simulator access and safe exploration, respectively. Reward-free safe RL setting. To adapt Algorithm 1 to the reward-free safe RL setting, we treat all state-action pairs as mismatch triples, i.e., B = [H] × S × A. In this case, the algorithm does not exploit simulator information and reduces to an online reward-free safe RL algorithm. Correspondingly, we define the empirical model P̂ t and the bonus bt as P̂ht (s′ | s, a) := 1{nth (s,a)>0} nth (s, a, s′ )/nth (s, a) + 1{nth (s,a)=0} /|S|  bth (s, a) := min 11Hβ(nth (s, a), δ)/(nth (s, a) ∨ 1), 1 .

(10)

We present reward-free safe RL algorithm below. Algorithm 2 Reward-free safe RL Require: A strictly feasible baseline policy π 0 with margin ξ, safety threshold ℓ, accuracy ε, and access to Mreal 1: Initialize n0h (s, a) ← 0 for all (h, s, a) ∈ [H] × S × A. 2: for t = 1, 2, . . . do 3: Construct P̂ t and bt from trajectories {τ i }t−1 i=1 , as defined in Equation (10). t

4: 5: 6: 7: 8:

0

P̂ ,π if Vc,1 (s1 ) < ℓ + ξ/2 then πt ← π0 else n t o // Computing safe exploration policy P̂ ,π P̂ t ,π t π̄ ∈ arg maxπ∈Π Vb,1 (s1 ) : Vc,1 (s1 ) ≥ ℓ   q P̂ t ,π̄ t P̂ t ,π̄ t t ∆ ← min H, 3e HVb,1 (s1 ) + HVb,1 (s1 )

9: if ∆t ≤ ε/2 then 10: break the for loop 11: end if 12: π t ← αt π̄ t + (1 − αt )π 0 , where αt is defined in Equation (9) 13: end if 14: Roll out π t in Mreal and observe τ t := {(sth , ath , sth+1 )}H h=1 15: end for o n t t P̂ ,π P̂ ,π 16: return P̂ t and π out ∈ arg maxπ∈Π Vr,1 (s1 ) : Vc,1 (s1 ) ≥ ℓ + ε/2 for any r ∈ F

Unconstrained sim-to-real RL setting. To adapt Algorithm 1 to the unconstrained sim-to-real RL setting, we ignore the safety constraint and compute the exploration policy directly by maximizing the bonus value, without enforcing safe exploration. Correspondingly, we choose t

P̂ ,π π t ∈ arg max Vb,1 (s1 ) π∈Π

16

as the exploration policy. We present the unconstrained sim-to-real RL algorithm below. Algorithm 3 Unconstrained sim-to-real RL Require: Accuracy ε, simulator information Msim , and access to Mreal 1: Initialize n0h (s, a) ← 0 for all (h, s, a) ∈ [H] × S × A. 2: for t = 1, 2, . . . do 3: Construct B̂ t as in Equations (3) and (4) // Estimating the mismatch region 4: Construct P̂ t as in Equations (2) and (5) // Constructing the hybrid model P̂ t ,π t 5: π ∈ arg maxπ∈Π Vb,1 (s1 ) // Computing exploration policy   q t t t ,π t P̂ P̂ ,π 6: ∆t ← min H, 3e HVb,1 (s1 ) + HVb,1 (s1 ) 7: if ∆t ≤ ε/2 then 8: break the for loop 9: end if 10: Roll out π t in Mreal and observe τ t := {(sth , ath , sth+1 )}H h=1 11: end for n t o t P̂ ,π P̂ ,π 12: return P̂ t and π out ∈ arg maxπ∈Π Vr,1 (s1 ) : Vc,1 (s1 ) ≥ ℓ + ε/2 for any r ∈ F

B.2

Sample complexity versus the size of the mismatch region |B|

In this section, we study how the size of the mismatch region, |B|, affects the sample complexity of Algorithm 1 in achieving safe exploration and accurate planning. The size of the mismatch region is controlled by the number of windy cells in the gridworld. Since each windy cell affects all four actions, n windy cells correspond to |B| = 4n mismatch stateaction pairs. We vary the number of windy cells so that |B| ∈ {4, 8, 12, 24, 40, 64, 84, 100}, out of |S||A| = 100. The default configuration has three windy cells adjacent to the unsafe wall, yielding |B| = 12. Windy cells are selected according to a fixed priority order rather than by uniform sampling. We first rank all regular cells, excluding the three unsafe cells and the initial state, by increasing Manhattan distance to the center of the unsafe wall. Cells at the same distance are ordered randomly using the instance seed. The unsafe cells are appended next, followed by the initial state s1 . The first n cells in this ordering are then designated as windy cells. This construction has two important properties. First, mismatch is introduced closest to the unsafe wall first, so the sparse-mismatch regime is safety-critical rather than benign. Second, the construction is incremental: the windy set for a smaller |B| is always contained in the windy set for any larger |B|. Thus, the experiment adds mismatch to a fixed layout instead of redrawing unrelated instances, making the growth in Figure 3 attributable to the size of B. As shown in Figure 3, the number of iterations required by Algorithm 1 to achieve safe exploration and accurate planning grows approximately linearly with |B|. When the mismatch region covers the entire state-action space, Algorithm 1 no longer exploits simulator information, and the total number of iterations coincides with that of the reward-free safe RL baseline. B.3

Sample complexity versus the value of the separation parameter σs

In this section, we study how different values of the separation parameter σs affect the sample complexity of Algorithm 1 in achieving safe exploration and accurate planning. To vary value of σs , we vary the wind strength pwind , defined as the probability that the wind reverses the intended move. On a windy cell, the real transition is P real (· | s, a) = (1 − pwind )P sim (· | s, a) + pwind P sim (· | s, ā), where ā denotes the action opposite to a. Hence, the total-variation gap from the simulator is pwind P sim (· | s, ā) − P sim (· | s, a) TV , which scales linearly with pwind . We vary pwind ∈ {0.15, 0.2, 0.3, 0.4, 0.55, 0.7, 0.85}, 17

Sim-to-real safe RL

0 10

84

64

40

24

250 200 150 100 50 4 182

Total iterations (×100)

Reward-free safe RL

Mismatch region | | (state-action pairs)

Figure 3: Total iterations versus the size of the mismatch region, |B|, at fixed σs = 0.68, where all runs ensure safe exploration and accurate planning. Shaded regions indicate the min–max range across 10 seeds. which gives σs ∈ {0.1275, 0.17, 0.255, 0.34, 0.4675, 0.595, 0.7225}.

Total iterations (×100)

As shown in Figure 4, Algorithm 1 requires more iterations when σs is smaller, because non-mismatch state-action pairs become harder to distinguish from mismatch state-action pairs. When the separation is sufficiently small, the total number of iterations approaches that of the reward-free safe RL baseline.

250

Reward-free safe RL

Sim-to-real safe RL

200 150 100 50 0.0

0.2

0.4

0.6

log10 (1/ s)

0.8

1.0

Figure 4: Total iterations versus log10 (1/σs ) at fixed |B| = 12, where all runs ensure safe exploration and accurate planning. Shaded regions indicate the min–max range across 10 seeds.

B.4

Estimating the separation parameter σs from real-world data

From the design of Algorithm 1, the separation parameter σs is used only in Line 3 to obtain the estimated mismatch region B̂ t through the deletion rule G t defined in Equation (3), where it enters through the threshold σs /2. In practice, σs is unknown and need to be estimated from data. To this end, in Appendix B.4.1, we describe how we estimate σs in our experiments and present the 18

estimation procedure in Algorithm 4, together with its theoretical guarantees in Proposition B.1. In Appendix B.4.2, we study the sample complexity of estimating σs , namely the number of samples that Algorithm 4 needed from Mreal for computing σ̂s to approach σs . Finally, in Appendix B.4.3, we study how Algorithm 1 performs when it is run with an estimated separation parameter σ̂s that differs from the true value σs . We evaluate its effect on three aspects: sample complexity, safe exploration, and the planning accuracy of the returned policy. For planning accuracy, we check whether the returned policy is both near-optimal and feasible in Mreal . B.4.1

Algorithm for estimating σs and its guarantees

To estimate σs , we roll out the strictly feasible baseline policy π 0 in Mreal for N episodes, which ensures safe exploration by Assumption 2.2. We then use the collected trajectories to estimate the separation parameter σs as follows. real Given the trajectories {τ i }N by the policy π 0 , we define the visitation counts i=1 collected from M for each (h, s, a) ∈ [H] × S × A as

nh (s, a) :=

N X

1{(sih ,aih )=(s,a)} , nh (s, a, s′ ) :=

i=1

N X

1{(sih ,aih ,sih+1 )=(s,a,s′ )} .

i=1

The empirical transition model estimated from real-world data is defined as P̂hreal (s′ | s, a) := 1{nh (s,a)>0}

1 nh (s, a, s′ ) + 1{nh (s,a)=0} , nh (s, a) |S|

(11)

and its statistical uncertainty is quantified by the confidence bound o n p ρh (s, a) = min 1, β(nh (s, a), δ)/(2nh (s, a) ∨ 1) , where β(n, δ) := log(2|S||A|H/δ) + |S| log(8e(n + 1)). The quantity we estimate is the minimum total variation gap over all (h, s, a) ∈ [H] × S × A. For every (h, s, a) ∈ [H] × S × A, let gh (s, a) := Phreal (· | s, a), Phsim (· | s, a) TV , so that mismatch region B = {(h, s, a) : gh (s, a) > 0} by Definition 2.4 and σs = min(h,s,a)∈B gh (s, a) is the constant for which Assumption 2.3 holds. Neither B nor the gaps gh are observable, since P real is unknown. Then, for each (h, s, a) ∈ [H] × S × A, we compute a lower confidence bound on gh (s, a), Lh (s, a) :=



P̂hreal (· | s, a), Phsim (· | s, a)

TV

 − ρh (s, a) .

(12)

+

Consider  C := (h, s, a) : nh (s, a) ≥ nmin and Lh (s, a) > 0 ,

(13)

the set of triples that are visited at least nmin times and whose gap is provably positive; as we show below, every such triple is certified to be a mismatch triple. Unvisited triples have ρh (s, a) = 1 and hence Lh (s, a) = 0, so they never enter C. Finally, we compute the estimated separation parameter as n σ̂s := min 1,

min (h,s,a)∈C

o Lh (s, a) ,

and

σ̂s := 0 if C = ∅.

The procedure of estimation of σs is summarized in Algorithm 4. 19

Algorithm 4 Safe estimation of the separation parameter σs Require: Strictly feasible baseline policy π 0 , simulator information Msim , number of iterations N from Mreal , confidence level δ, coverage requirement nmin ≥ 1 1: for i = 1, . . . , N do 2: Roll out π 0 in Mreal and observe τ i := {(sih , aih , sih+1 )}H h=1 3: end for 4: Compute P̂ real as in Equation (11), Lh as in Equation (12) and C as in Equation (13). 5: if C ̸= ∅ then 6: return σ̂s ← min{1, min(h,s,a)∈C Lh (s, a)} 7: else 8: return σ̂s ← 0 9: end if In the following, we characterize the statistical guarantee for σ̂s returned by Algorithm 4. Proposition B.1. With probability at least 1 − δ, Algorithm 4 ensures: (i) C ⊆ B; (ii) σ̂s ≤

min (h,s,a)∈C

Phreal (· | s, a) − Phsim (· | s, a) TV =

min (h,s,a)∈C

gh (s, a);

and (iii) consequently, if B ⊆ C, then σs − 2 max(h,s,a)∈B ρh (s, a) ≤ σ̂s ≤ σs . Proposition B.1 shows that Algorithm 4 provides a conservative estimate of both the mismatch region and the separation parameter: with high probability, every triple in C is a true mismatch triple, and σ̂s lower bounds the smallest simulator-real gap over this set. Consequently, if the collected data are sufficiently rich to identify all mismatch triples, i.e., B ⊆ C, then σ̂s ≤ σs . As shown in Appendix B.4.2, when sufficient data are sampled from Mreal , the estimated separation parameter σ̂s approaches the true value σs with high probability. In this case, C = B, and σ̂s is a conservative estimate of σs . Furthermore, as shown in Appendix B.4.3 and implied by Theorem 4.1, such a conservative estimate is sufficient for Algorithm 1 to achieve safe exploration and accurate planning, at the cost of increased sample complexity. Next, we present proof of Proposition B.1. Proof of Proposition B.1. By Lemma D.1, applied to each (h, s, a) at level δ/(2|S||A|H), and by a union bound over the H|S||A| triples, exactly as in Lemma C.1, with probability at least 1 − δ,   β(n (s, a), δ) h ∀(h, s, a) ∈ [H] × S × A : KL P̂hreal (· | s, a), Phreal (· | s, a) ≤ . nh (s, a) ∨ 1 Condition on this event. For every triple with nh (s, a) ≥ 1, Pinsker’s inequality gives P̂hreal (· | s, a), Phreal (· | s, a)

TV

≤ ρh (s, a).

By the triangle inequality, P̂hreal (· | s, a), Phsim (· | s, a)

TV

− gh (s, a) ≤ ρh (s, a).

Consequently, Lh (s, a) =



P̂hreal (· | s, a), Phsim (· | s, a)

TV

 − ρh (s, a) ≤ gh (s, a). +

Thus, Lh (s, a) > 0 implies gh (s, a) > 0, so every triple in C belongs to B. This proves (i). For (ii), if C = ∅, Algorithm 4 returns σ̂s = 0. If C ̸= ∅, then   σ̂s = min 1, min Lh (s, a) ≤ min Lh (s, a) ≤ (h,s,a)∈C

(h,s,a)∈C

min (h,s,a)∈C

gh (s, a).

For (iii), we assume that B ̸= ∅. Indeed, if B = ∅, then the simulator is exact, σs is unconstrained by Assumption 2.3, and part (i) forces C = ∅ and σ̂s = 0, so the claim is vacuous. Now suppose that B ⊆ C and B ̸= ∅. Since B ̸= ∅, this implies C ̸= ∅. Together with (i), it gives C = B. Hence, σ̂s ≤

min (h,s,a)∈C

gh (s, a) =

min (h,s,a)∈B

20

gh (s, a) = σs .

Furthermore, P̂hreal (· | s, a), Phsim (· | s, a)

TV

≥ gh (s, a) − ρh (s, a),

so Lh (s, a) ≥ (gh (s, a) − 2ρh (s, a))+ ≥ gh (s, a) − 2ρh (s, a). Using C = B, min (h,s,a)∈C

Lh (s, a) ≥

min (h,s,a)∈B

≥

min (h,s,a)∈B

(gh (s, a) − 2ρh (s, a)) gh (s, a) − 2 max ρh (s, a) (h,s,a)∈B

= σs − 2 max ρh (s, a). (h,s,a)∈B

Since σs − 2 max(h,s,a)∈B ρh (s, a) ≤ σs ≤ 1, clipping at 1 preserves this lower bound. Therefore, σs − 2 max ρh (s, a) ≤ σ̂s ≤ σs . (h,s,a)∈B

B.4.2

Sample complexity of estimating σs

In this section, we investigate the sample complexity required to obtain a sufficiently accurate estimate σ̂s . Here, sample complexity refers to the number of samples collected by rolling out the safe baseline policy π 0 in Mreal . We consider the gridworld example with mismatch region |B| = 64, shown in Figure 1a, while varying the profile of the wind strength across the windy cells. Specifically, we consider three instances: (i) a homogeneous instance with pwind = 0.8 throughout the mismatch region; (ii) a homogeneous instance with pwind = 0.35 throughout the mismatch region, since this value yields a small separation parameter σs , making σs more sample-demanding to estimate; and (iii) a heterogeneous instance in which pwind varies from 0.2 to 0.8 across the mismatch region, with values equispaced in this range. In the heterogeneous instance, the windy cells are ordered by increasing distance from the unsafe wall, and the wind strength increases along this order. Thus, the weakest and hardest-to-certify mismatch lies closest to the unsafe wall, making the instance more challenging rather than benign. We summarize the three instances in the table below. pwind

σs

0.8 everywhere 0.35 everywhere 0.2 to 0.8, equispaced

0.68 0.2975 0.17

Instance I (homogeneous) II (homogeneous) III (heterogeneous)

Table 3: Three gridworld instances As shown in Figure 5, with a sufficient number of samples (more than 3 × 103 in these experiments), the estimate σ̂s is conservative with respect to the true value σs , i.e., σ̂s ≤ σs . As the number of samples increases, σ̂s converges to σs , and the estimated mismatch set C coincides with the true mismatch region B. Instance I is the easiest to estimate because it has the largest σs , whereas Instances II and III are harder because they have smaller separation parameters. B.4.3

Effect of misspecifying σs

In this section, we investigate the effect of using an estimated separation parameter σ̂s , instead of the true value σs , in Algorithm 1. We consider the same three example as in Table 3. By varying the value of σ̂s used by the algorithm, we study its effect on three aspects of algorithm performance: sample complexity, safe exploration, and the planning accuracy of the returned policy. For planning accuracy, we check whether the returned policy is both near-optimal and feasible in Mreal . We summarize the results in Table 4. As shown in the table, Algorithm 1 ensures safe exploration for all values of σ̂s , due to its mixture-policy design. However, sample complexity and planning accuracy differ across choices of σ̂s . When σ̂s underestimates σs , the algorithm preserves both safe exploration and accurate planning, but requires more samples from the real environment to identify 21

I (homogeneous) s

0.68

100

II (homogeneous)

0.2975

10 1 10 2 103 104 105 106

Samples from

true s

real

100

10 1

0.17

10 2

10 2 103 104 105 106

Samples from

real

output s (Alg. 4)

III (heterogeneous)

103 104 105 106

Samples from

real

= in every seed

Figure 5: Sample complexity of estimating σs in the three instances. The curves show the mean over 20 seeds, with shaded regions indicating the min–max range. the mismatch triples. This leads to higher sample complexity. The worst case occurs when σ̂s = 0, in which case Algorithm 1 degenerates to an online reward-free RL algorithm. On the other hand, when σ̂s overestimates σs , the algorithm may require fewer real-environment samples than in the underestimation case, but it can incorrectly remove true mismatch triples from B̂ t . As a result, the returned transition model may be insufficiently accurate for planning: although the output policy may remain near-optimal for any reward function under the learned model, it may no longer be feasible in Mreal . This failure occurs for Instances II and III when σ̂s is 2.5× larger than the true value. In summary, underestimating σs is safe but can increase sample complexity, whereas overestimating σs may lead to inaccurate planning. Therefore, a conservative estimate of σs is important for safe learning.

C

Proofs

For simplicity of notation, we introduce the following operators. ′ ′ Notation For any function f : S → R, h we define Ph f (s, a)
i:= Es ∼Ph (·|s,a) [f (s )] as the 2 expectation operator, and Varp (f ) ≜ Es∼p f (s) − Es′ ∼p [f (s′ )] as the variance operator. For P any function g : S × A → R, we define πg(s) := a π(a|s)g(s, a) as the policy operator. Unless indicated otherwise, an unadorned Ph abbreviates the real-world kernel Phreal .

C.1

Concentration events real

,π Let dP (s, a) denote the probability of visiting (s, a) at step h under the policy π. Define the h cumulative visitation probability

n̄th (s, a) :=

t−1 X real ,π i dP (s, a) h i=1

which represents the expected number of visits to (s, a) at step h during the first t − 1 iterations of Algorithm 1, and when t = 1 we set n̄1h (s, a) = 0. We introduce two favorable events. The event E ensures that the empirical transition model is close to the true transition model, while E cnt guarantees that the pseudo-counts are close to their expected values:    β(nth (s, a), δ) t,real real E := ∀t ∈ N, ∀h ∈ [H], ∀(s, a) ∈ S × A : KL P̂h (· | s, a), Ph (· | s, a) ≤ , nth (s, a)  E cnt := ∀t ∈ N, ∀h ∈ [H], ∀(s, a) ∈ S × A : nth (s, a) ≥ 21 n̄th (s, a) − β cnt (δ) . 

22

Table 4: Performance of Algorithm 1 with different values of σ̂s . Samples from Mreal : total number of samples required from Mreal before termination, reported as mean ± standard deviation over 20 seeds. Unsafe iterations: share of seeds for which there exists at least one iteration t such that the deployed policy π t is infeasible during the execution of Algorithm 1. Pairs of B lost: mean number of mismatch pairs from B incorrectly removed from B̂ t , averaged over 20 seeds. Runs with false ∗ deletion: share of seeds in which at least one pair from B is lost. Output optimality: Vrπ − Vrπ , averaged over 10 random reward functions per seed, where π is the output optimal policy for reward r, and π ∗ is the true optimal policy for reward r. Output feasibility: share of output policies that are feasible in Mreal . Rows in bold indicate settings in which the output policy is infeasible in Mreal for at least one reward and seed. σ̂s

Samples from Mreal

Unsafe iterations (share of seeds)

Pairs of B lost (out of 64)

Runs with false deletion

Output optimality

Output feasibility

0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0

0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%

0.0003 0.0003 0.0002 0.0003 0.0004 0.0002 0.0003 0.0003 0.0002 0.0005 0.0004 0.0003 0.0003 0.0004 0.0003 0.0004 0.0005 0.0004 0.0003 0.0003

100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0%

0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.8 10.0 31.1 46.6 62.7

0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 90% 100% 100% 100% 100%

0.0005 0.0005 0.0004 0.0004 0.0005 0.0004 0.0004 0.0004 0.0004 0.0005 0.0005 0.0005 0.0005 0.0004 0.0004 0.0087 0.0559 0.1089 0.1453 0.1601

100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 98.5% 92.5% 90.0% 90.0%

0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.1 0.8 2.8 5.7 6.8 8.6 11.3 13.4 15.9 18.4 26.6

0% 0% 0% 0% 0% 0% 0% 0% 0% 5% 65% 100% 100% 100% 100% 100% 100% 100% 100% 100%

0.0007 0.0007 0.0007 0.0007 0.0006 0.0007 0.0006 0.0005 0.0006 0.0006 0.0008 0.0018 0.0031 0.0033 0.0050 0.0099 0.0166 0.0244 0.0289 0.0451

100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 99.0% 98.0% 96.0% 93.5%

I (homogeneous), σs = 0.68 0.000 0.050 0.100 0.150 0.200 0.250 0.300 0.340 0.400 0.450 0.500 0.550 0.595 0.620 0.650 0.700 0.750 0.800 0.850 1.000

269,658 ± 6,792 269,658 ± 6,792 266,637 ± 6,520 252,378 ± 4,095 232,344 ± 3,346 209,784 ± 3,092 184,668 ± 3,881 174,948 ± 3,940 166,146 ± 3,843 162,051 ± 4,041 158,172 ± 3,655 155,784 ± 3,646 154,203 ± 3,544 153,375 ± 3,561 152,460 ± 3,496 151,461 ± 3,581 150,519 ± 3,451 149,562 ± 3,339 149,106 ± 3,260 147,816 ± 3,326

0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0%

II (homogeneous), σs = 0.2975 0.000 0.050 0.100 0.150 0.200 0.250 0.300 0.340 0.400 0.450 0.500 0.550 0.595 0.620 0.650 0.700 0.750 0.800 0.850 1.000

291,447 ± 4,586 291,324 ± 4,550 286,770 ± 3,295 277,749 ± 2,789 262,854 ± 6,689 252,834 ± 8,453 235,734 ± 7,056 217,677 ± 8,188 201,945 ± 9,807 193,515 ± 11,638 187,689 ± 12,893 182,604 ± 13,441 180,267 ± 13,974 178,860 ± 14,514 177,414 ± 15,049 185,628 ± 14,777 186,582 ± 11,558 178,083 ± 14,329 162,444 ± 12,923 107,913 ± 7,517

0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0%

III (heterogeneous), σs = 0.17 0.000 0.050 0.100 0.150 0.200 0.250 0.300 0.340 0.400 0.450 0.500 0.550 0.595 0.620 0.650 0.700 0.750 0.800 0.850 1.000

283,437 ± 6,806 283,281 ± 6,660 278,700 ± 5,605 270,189 ± 5,877 255,762 ± 9,410 242,670 ± 11,522 223,038 ± 11,942 205,590 ± 11,723 191,334 ± 11,695 184,200 ± 11,361 178,368 ± 12,508 173,556 ± 12,592 168,756 ± 13,252 166,314 ± 13,007 162,690 ± 13,555 158,874 ± 15,081 154,278 ± 13,504 151,353 ± 12,925 146,103 ± 11,516 133,131 ± 11,364

0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0%

23

We next show that, for appropriate choices of the confidence functions β and β cnt , the events E and E cnt hold simultaneously with high probability. Lemma C.1. With the choices β(n, δ) := log(2SAH/δ) + S log(8e(n + 1)) , β cnt (δ) := log(2SAH/δ) , it holds that Pr(E ∩ E cnt ) ≥ 1 − δ. Proof of Lemma C.1. By Lemma D.1, we have Pr(E) ≥ 1 − δ/2. Similarly, by Lemma D.2, Pr(E cnt ) ≥ 1 − δ/2. Applying the union bound yields Pr(E ∩ E cnt ) ≥ 1 − δ. Lemma C.2. On the event E cnt , for all h ∈ [H], (s, a) ∈ S × A and t ∈ N, o n β(nth (s, a), δ) β(n̄t (s,a),δ) ∧ 1 ≤ 4 min 14 , n̄t h(s,a)∨1 . t h nh (s, a) Proof of Lemma C.2. By [Ménard et al., 2021, Lemma 10], we have β(n̄t (s, a), δ) β(nth (s, a), δ) ∧1≤4 t h . t nh (s, a) n̄h (s, a) ∨ 1 Moreover, since the left-hand side is clipped at 1, it follows that n o β(n̄t (s, a), δ) β(nth (s, a), δ) β(n̄t (s,a),δ) ∧ 1 ≤ min{1, 4 t h } = 4 min 14 , n̄t h(s,a)∨1 . t h nh (s, a) n̄h (s, a) ∨ 1

Next, we establish the guarantees of Algorithms 1, under the events E and E cnt , which jointly hold with high probability by Lemma C.1. C.2

Analysis of the estimated mismatch region

This section proves the theoretical guarantees for Algorithm 1 on the estimated mismatch region. Lemma C.3 shows that, with high probability, no mismatch triple is removed from B̂ t during the learning process, while Lemma C.4 shows that every non-mismatch triple is removed once it has been sampled sufficiently often. Lemma C.3. On the event E, for every t ∈ N, the following hold: (i) B̂ t ⊆ B̂ t−1 ; and (ii) B ⊆ B̂ t . Proof of Lemma C.3. By definition, B̂ t = B̂ t−1 \ G t , which immediately implies B̂ t ⊆ B̂ t−1 . To establish (ii), fix (h, s, a) ∈ B and suppose, towards a contradiction, that (h, s, a) ∈ G t for some iteration t. By the definition of G t , we have σs P̂ht,real (· | s, a), Phsim (· | s, a) + ρth (s, a) ≤ . 2 TV Moreover, on the event E, Pinsker’s inequality yields r   1 t,real real KL P̂ht,real (· | s, a), Phreal (· | s, a) ≤ ρth (s, a). P̂h (· | s, a), Ph (· | s, a) ≤ 2 TV Hence, by the triangle inequality, Phreal (· | s, a), Phsim (· | s, a) TV ≤ Phreal (· | s, a), P̂ht,real (· | s, a) ≤ρth (s, a) +

TV

+ P̂ht,real (· | s, a), Phsim (· | s, a)

P̂ht,real (· | s, a), Phsim (· | s, a)

TV

TV

σs . 2 However, since (h, s, a) ∈ B, Assumption 2.3 implies Phreal (· | s, a), Phsim (· | s, a) TV ≥ σs , which is a contradiction. Therefore, (h, s, a) ∈ / G t . Since B ⊆ B̂ 0 by initialization, no element of B is ever removed from B̂ t , and thus B ⊆ B̂ t for all t ∈ N. ≤

24

Lemma C.4. On the event E, for every (h, s, a) ∈ / B and every t ∈ N, if nth (s, a) ≥ n, then t (h, s, a) ∈ / B̂ , where    16 16|S| 16|S| n := 1 + 2 (log(2|S||A|H/δ) + |S| log(8e)) + log max ,e . σs σs2 σs2 Proof of Lemma C.4. Fix (h, s, a) ∈ / B and t ∈ N. Since (h, s, a) ∈ / B, we have Phreal (· | s, a) = sim Ph (· | s, a). On the event E, Pinsker’s inequality gives P̂ht,real (· | s, a), Phsim (· | s, a)

TV

= P̂ht,real (· | s, a), Phreal (· | s, a)

TV

≤ ρth (s, a).

By Algorithm 1, (h, s, a) ∈ G t whenever P̂ht,real (· | s, a), Phsim (· | s, a)

TV

+ ρth (s, a) ≤

σs . 2

Therefore, it suffices to ensure 2ρth (s, a) ≤ σs /2. Using ρth (s, a) =

p

β(nth (s, a), δ)/(2nth (s, a)), the condition 2ρth (s, a) ≤ σs /2 is equivalent to nth (s, a) ≥

8β(nth (s, a), δ) . σs2

Now write β(n, δ) = log(2|S||A|H/δ) + |S| log(8e(n + 1)). Equivalently, β(n, δ) = log(2|S||A|H/δ) + |S| log(8e) + |S| log(n + 1). Thus Lemma D.6 applies with κ = σs2 /8, b = |S|, and c = log(2|S||A|H/δ) + |S| log(8e). It follows that nth (s, a) ≥ n implies 8β(nth (s, a), δ) nth (s, a) ≥ . σs2 Hence 2ρth (s, a) ≤ σs /2, so the removal test in Equation (3) is satisfied. If (h, s, a) ∈ B̂ t−1 , this gives (h, s, a) ∈ G t and therefore (h, s, a) ∈ / B̂ t = B̂ t−1 \ G t . Otherwise (h, s, a) ∈ / B̂ t−1 , and t t−1 t part (i) of Lemma C.3 gives B̂ ⊆ B̂ , so again (h, s, a) ∈ / B̂ . C.3

Proof of Lemma 3.1

In this section, we prove a stronger version of Lemma 3.1. We first define At,π b,h recursively by setting t,π Ab,H+1 (s, a) := 0, and for h ∈ [H],     1 t,π t t At,π (s, a) = min 1, b (s, a) + 1 + P̂ π A (s, a) . (14) h h h+1 b,h+1 b,h H t

real

P̂ ,π P ,π For the proof analysis, we further define et,π (s, a) , which will be f,h (s, a) := Qf,h (s, a) − Qf,h used to bound et,π (s), noting that f,h h t i P̂ ,π P real ,π et,π (s) = E Q (s, a) − Q (s, a) ≤ Ea∼πh (·|s) et,π a∼πh (·|s) f,h f,h f,h f,h (s, a).

Lemma C.5. With probability at least 1 − δ, for any iteration t, policy π, function f ∈ F, timestep h ∈ [H], and state-action pair (s, a),  q  t,π t,π et,π (s, a) ≤ min 3e HA (s, a) + HA (s, a), H , f,h b,h b,h  q  t,π t,π et,π (s) ≤ min 3e Hπ A (s) + Hπ A (s), H . h b,h h b,h f,h 25

Remark. Lemma C.5 is tighter than Lemma 3.1. In particular, we show by backward induction that t

t

P̂ ,π At,π b,h (s, a) ≤ Qb,h (s, a),

P̂ ,π πh At,π b,h (s) ≤ Vb,h (s).

The claim is immediate at h = H + 1. Suppose it holds at step h + 1. Then, for any (s, a),     1 t,π t,π t t Ab,h (s, a) = min 1, bh (s, a) + 1 + P̂h πh+1 Ab,h+1 (s, a) H     t 1 t t P̂ ,π ≤ min 1, bh (s, a) + 1 + P̂h Vb,h+1 (s, a) H   1 P̂ t ,π P̂ht Vb,h+1 (s, a) ≤ bth (s, a) + 1 + H t

,π = QP̂ b,h (s, a),

where the first inequality uses the induction hypothesis. Taking expectation over a ∼ πh (· | s) yields t

t

P̂ ,π P̂ ,π πh At,π b,h (s) ≤ πh Qb,h (s) = Vb,h (s).

Proof of Lemma C.5. By Lemma C.1, the event E ∩ E cnt holds with probability at least 1 − δ, and on E Lemma C.3 gives B ⊆ B̂ t for every t. In the remainder of the analysis, we condition on the event E ∩ E cnt , on which B ⊆ B̂ t therefore also holds. We fix an iteration t, a policy π, and a function f ∈ F. Throughout the proof, we adopt the convention that if nth (s, a) = 0, then β(nth (s, a), δ)/nth (s, a) = +∞. Due to the clipping, all recursively defined quantities remain finite. Step 1: Recursive empirical Bernstein bound. Fix a timestep-state-action tuple (h, s, a) ̸∈ B̂ t , then by part (ii) of Lemma C.3 together with Definition 2.4, P̂ht (·|s, a) = Phreal (·|s, a). Hence, t

real

P̂ ,π P ,π t,π t t et,π f,h (s, a) ≤ P̂h |Vf,h+1 − Vf,h+1 |(s, a) ≤ P̂h πh+1 ef,h+1 (s, a),

where we use t

real

P̂ ,π P ,π ′ |Vf,h+1 (s′ ) − Vf,h+1 (s )| =

X

≤

X

 t  ,π P real ,π ′ ′ ′ ′ πh+1 (a′ |s′ ) QP̂ (s , a ) − Q (s , a ) f,h+1 f,h+1

a′ t,π ′ ′ ′ πh+1 (a′ |s′ )et,π f,h+1 (s , a ) = πh+1 ef,h+1 (s ).

(15)

a′

Now consider (h, s, a) ∈ B̂ t , we decompose the estimation error as et,π f,h (s, a) real

t

real

P ,π P̂ ,π P ,π ≤ [(P̂ht − Phreal )Vf,h+1 ](s, a) + P̂ht |Vf,h+1 − Vf,h+1 |(s, a) s β(nth (s, a), δ) 2Hβ(nth (s, a), δ) P real ,π P̂ t ,π P real ,π )(s, a) + + P̂ht |Vf,h+1 ≤ 2VarPhreal (Vf,h+1 − Vf,h+1 |(s, a) t t nh (s, a) 3nh (s, a) (16) real

P ,π where the last step follows from Lemma D.3 and Vf,h+1 ∈ [0, H]. real

P ,π Again, by Lemma D.3 and the fact that Vf,h+1 ∈ [0, H], we have real

P ,π VarPhreal (Vf,h+1 )(s, a) real

P ,π ≤2VarP̂ t (Vf,h+1 )(s, a) + 4H 2 KL(P̂ht (·|s, a), Phreal (·|s, a)) h

26

real

P ,π )(s, a) + 4H 2 ≤2VarP̂ t (Vf,h+1 h

β(nth (s, a), δ) nth (s, a)

β(nth (s, a), δ) , h nth (s, a) √ √ √ √ Plugging this bound into the first term in Inequality (16) and using x + y + z ≤ x + y + z, we obtain s β(nth (s, a), δ) P real ,π )(s, a) 2VarPhreal (Vf,h+1 nth (s, a) s s β(nth (s, a), δ) β(nth (s, a), δ) 1 t P real ,π P̂ t ,π P̂ t ,π ≤ 8VarP̂ t (Vf,h+1 )(s, a) + P̂h |Vf,h+1 − Vf,h+1 |(s, a) · 8H 2 t h nh (s, a) H nth (s, a) √ β(nth (s, a), δ) + 2 2H nth (s, a) s t β(nth (s, a), δ) 1 P̂ t ,π P real ,π P̂ t ,π 2 β(nh (s, a), δ) ≤3 VarP̂ t (Vf,h+1 + 7H + P̂ht |Vf,h+1 )(s, a) − Vf,h+1 |(s, a), t t h nh (s, a) nh (s, a) H √ where the last step uses the Arithmetic Mean–Geometric Mean inequality xy ≤ 12 (x + y) on the t

real

t

P̂ ,π P ,π P̂ ,π )(s, a) + 4H P̂ht |Vf,h+1 − Vf,h+1 |(s, a) + 4H 2 ≤4VarP̂ t (Vf,h+1

real

t

P ,π P̂ ,π 1 third term with x = H P̂ht |Vf,h+1 − Vf,h+1 |(s, a) and y = 8H 2 β(nth (s, a), δ)/nth (s, a). Therefore, Inequality (16) can be bounded as s β(nth (s, a), δ) β(nth (s, a), δ) P̂ t ,π t,π ef,h (s, a) ≤ 3 VarP̂ t (Vf,h+1 )(s, a) + 8H 2 t h nh (s, a) nth (s, a)   1 P̂ t ,π P real ,π P̂ht |Vf,h+1 + 1+ − Vf,h+1 |(s, a). (17) H We next replace the unclipped square root factor in Inequality (17) by its clipped version. If H 2 β(nth (s, a), δ)/nth (s, a) ≤ 1, the term is unchanged. Otherwise, H 2 β(nth (s, a), δ)/nth (s, a) > 1, p P̂ t ,π so H 2 β(nth (s, a), δ)/nth (s, a) ≤ H 2 β(nth (s, a), δ)/nth (s, a), and using VarP̂ t (Vf,h+1 )(s, a) ≤ h 2 H we get v  u  u Var t (V P̂ t ,π )(s, a)  t β(nth (s, a), δ)H 2 u f,h+1 P̂h 2 β(nh (s, a), δ)  3t ≤ 3H . H2 nth (s, a) nth (s, a)

Therefore, Inequality (17) can be bounded as s s P̂ t ,π t VarP̂ t (Vf,h+1 )(s, a) β(nt (s, a), δ)H 2 t,π 2 β(nh (s, a), δ) h h ∧ 1 + 11H ef,h (s, a) ≤ 3 t H2 nh (s, a) nth (s, a)   1 + 1+ P̂ht πh+1 et,π f,h+1 (s, a), H where the last term uses Inequality (15). t,π Next, we define the functions B recursively. Let Bf,H+1 (s, a) := 0, and for h ∈ [H] define s s ( P̂ t ,π  VarP̂ t (Vf,h+1 )(s, a) β(nt (s, a), δ)H 2 t,π h h Bf,h (s, a) := min H, 1{(h,s,a)∈B̂t } 3 ∧1 H2 nth (s, a) )    1 11H 2 β(nth (s, a), δ) t,π t + + 1+ P̂h πh+1 Bf,h+1 (s, a) . nth (s, a) H

Since et,π f,h (s, a) ≤ H, the recursive bound above implies, by backward induction on h, that for all (s, a, h), t,π et,π (18) f,h (s, a) ≤ Bf,h (s, a). 27

t,π Step 2: Law of total variance. For all (s, a), we recursively define C by setting Cf,H+1 (s, a) := 0 and, for h < H + 1, v u  u Var t (V P̂ t ,π )(s, a)  β(nth (s, a), δ)H 2 f,h+1 t P̂h t,π Cf,h (s, a) := 1{(h,s,a)∈B̂t } × 3 ∧ 1 H2 nth (s, a)   1 t,π + 1+ P̂ht πh+1 Cf,h+1 (s, a). H

We first show by backward induction that, for all h, s, a, t,π t,π Bf,h (s, a) ≤ Cf,h (s, a) + HAt,π b,h (s, a),

where At,π b,h (s, a) is defined in Equation (14). The claim is trivial for h = H + 1. Suppose the claim holds at step h + 1. By the induction hypothesis, we have t,π Bf,h (s, a)

 v  u  u Var t (V P̂ t ,π )(s, a)  t t 2 β(nh (s, a), δ)H P̂h f,h+1 β(nh (s, a), δ)   t ≤ min H, 1{(h,s,a)∈B̂t } 3 ∧ 1 + 11H 2  H2 nth (s, a) nth (s, a) (

)     1 1 t,π (s, a) + H 1 + (s, a) P̂ht πh+1 Cf,h+1 P̂ht πh+1 At,π + 1+ b,h+1 H H     11Hβ(nth (s, a), δ) 1 t,π t t,π ≤Cf,h (s, a) + H min 1, 1{(h,s,a)∈B̂t } + 1+ P̂h πh+1 Ab,h+1 (s, a) nth (s, a) H       11Hβ(nth (s, a), δ) 1 t,π t t,π (s, a) + H min 1, min 1{(h,s,a)∈B̂t } =Cf,h , 1 + 1 + (s, a) P̂ π A h+1 h b,h+1 nth (s, a) H t,π (s, a) + HAt,π =Cf,h b,h (s, a),

where the second inequality uses min(x, y + z) ≤ min(x, y) + z, the third inequality uses min{a, b + c} ≤ min{a, min{a, b} + c} for c ≥ 0, and the final equality follows from the definition   11Hβ(nth (s, a), δ) t ,1 bh (s, a) := 1{(h,s,a)∈B̂t } min nth (s, a)   11Hβ(nth (s, a), δ) = min 1{(h,s,a)∈B̂t } ,1 nth (s, a) together with the recursive definition of At,π b,h . Combining the above with Inequality (18), we have, for all π ∈ Π, h ∈ [H], and (s, a) ∈ S × A, t,π t,π et,π f,h (s, a) ≤ Cf,h (s, a) + HAb,h (s, a),

(19)

t,π t,π et,π f,h (s) ≤ πh Cf,h (s) + Hπh Ab,h (s). t,π It remains to upper-bound Cf,h by At,π b,h , thereby removing the explicit dependence on the empirical t

,π variance of the value function under policy π. We define dP̂ (s, a | sh = s′ ) as the state-action ℓ occupancy distribution at step ℓ ∈ {h, . . . , H} induced by policy π and the empirical transition model t,π P̂ t , conditioned on starting from state s′ at step h. By recursively expanding Cf,h over the timestep h
m ≤ e for all m ∈ {0, . . . , H}, and applying the Cauchy–Schwarz inequality together with 1 + H1 we obtain  ℓ−h H XX t 1 t,π ′ ,π ′ πh Cf,h (s ) =3 1{(ℓ,s,a)∈B̂t } dP̂ (s, a | s = s ) 1 + h ℓ H s,a ℓ=h v u  u Var t (V P̂ t ,π )(s, a)  2 H β(ntℓ (s, a), δ) f,ℓ+1 t P̂ℓ × ∧1 H2 ntℓ (s, a)

28

v u t t uX X H dP̂ ,π (s, a | s = s′ )Var (V P̂ ,π )(s, a) h u f,ℓ+1 ℓ P̂ℓt ≤3et H2 s,a ℓ=h v u   2 H uX X H β(ntℓ (s, a), δ) t ×t ∧ 1 1{(ℓ,s,a)∈B̂t } dℓP̂ ,π (s, a | sh = s′ ) ntℓ (s, a) s,a ℓ=h v   u !2 H u X u 1 P̂ t ,π ≤ 3et 2 Eπ,P̂ t  fℓ (sℓ , aℓ ) − Vf,h (sh ) sh = s′  H ℓ=h

v u H uX X ×t 1

t

{(ℓ,s,a)∈B̂t }

dℓP̂ ,π (s, a | sh = s′ )



s,a ℓ=h

H 2 β(ntℓ (s, a), δ) ∧1 ntℓ (s, a)



v u   2 H uX X H β(ntℓ (s, a), δ) t ≤ 3et ∧ 1 . 1{(ℓ,s,a)∈B̂t } dℓP̂ ,π (s, a | sh = s′ ) ntℓ (s, a) s,a ℓ=h

Here the second-to-last step follows from Lemma D.8 applied to the empirical CMDP with transition PH model P̂ t , and the last step uses ℓ=h fℓ (sℓ , aℓ ) ∈ [0, H]. For this step, define Ât,π recursively by Ât,π H+1 (s, a) := 0 and     2 H β(nth (s, a), δ) t,π t ∧ 1 + P̂ π Â (s, a) . Ât,π (s, a) := min H, 1 h h+1 h+1 h {(h,s,a)∈B̂t } nth (s, a)

Step 3: Clipping.

Then, by construction, H XX

t ,π 1{(ℓ,s,a)∈B̂t } dP̂ (s, a | sh = s′ ) ℓ



s,a ℓ=h

H 2 β(ntℓ (s, a), δ) ∧1 ntℓ (s, a)



′ ≤ πh Ât,π h (s ).

We next show by backward induction that t,π Ât,π h (s, a) ≤ HAb,h (s, a).

The claim is immediate at h = H + 1. Suppose it holds at step h + 1. Then   2   H β(nth (s, a), δ) t,π t Ât,π ∧ 1 + P̂ π Â (s, a) (s, a) = min H, 1 h h+1 h+1 h {(h,s,a)∈B̂t } nt (s, a)     h2 H β(nth (s, a), δ) t,π t , H + H P̂h πh+1 Ab,h+1 (s, a) ≤ min H, 1{(h,s,a)∈B̂t } min nt (s, a)    h  1 t,π t t ≤ H min 1, bh (s, a) + 1 + P̂h πh+1 Ab,h+1 (s, a) H = HAt,π b,h (s, a), t,π t where we used the induction hypothesis Ât,π h+1 ≤ HAb,h+1 and the definition bh (s, a). Consequently, q q t,π t,π πh Cf,h (s) ≤ 3e πh Ât,π h (s) ≤ 3e Hπh Ab,h (s).

Finally, to obtain the action-value bound, we fix (h, s, a) and define a modified policy π h,s,a which takes action a at state s and time h, and follows π from time h + 1 onward. Applying the preceding state-value bound to π h,s,a thus gives q q h,s,a t,π t,π h,s,a t,π h,s,a Cf,h (s, a) = Cf,h (s, a) = πhh,s,a Cf,h (s) ≤ 3e Hπhh,s,a At,π (s) = 3e HAt,π b,h b,h (s, a). 29

Plugging these bounds into Inequality (19) yields q t,π t,π et,π f,h (s, a) ≤ 3e HAb,h (s, a) + HAb,h (s, a), q t,π et,π (s) ≤ 3e Hπh At,π f,h b,h (s) + πh HAb,h (s). We further note that, by definition, t,π et,π f,h (s, a) ≤ H, ef,h (s) ≤ H.

C.4

Proof of Theorem 4.1

Before proceeding with the proof of Theorem 4.1, we state the following lemma, which shows that once the estimation error is sufficiently small, solving the empirical CMDP under a slightly tightened safety constraint yields a policy that is feasible and near-optimal for the true CMDP. We then use this lemma to prove Theorem 4.1. Lemma C.6 (Connection between estimation error and CMDPs). Suppose Assumption 2.2 holds. At iteration t, assume that there exists a constant ε > 0 such that q ξ P̂ t ,π 0 P̂ t ,π 0 3e H Vb,1 (s1 ) + H Vb,1 (s1 ) ≤ , 4 n q o ξ P̂ t ,π P̂ t ,π P̂ t ,π max 3e H Vb,1 (20) (s1 ) + H Vb,1 (s1 ) : Vc,1 (s1 ) ≥ ℓ ≤ ε ≤ . π∈Π 4 Then, on the high-probability event of Lemma 3.1, for any reward function r ∈ F, every optimal solution n t o P̂ ,π P̂ t ,π π out ∈ arg max Vr,1 (s1 ) : Vc,1 (s1 ) ≥ ℓ + ε π∈Π

is feasible for the true CMDP and satisfies real

P Vr,1

where

,π ⋆

real

P (s1 ) − Vr,1

,π out

(s1 ) ≤

2Hε + 2ε, ξ

n real o P ,π P real ,π π ⋆ ∈ arg max Vr,1 (s1 ) : Vc,1 (s1 ) ≥ ℓ . π∈Π

In particular, π out is feasible for the true CMDP and is O(Hε/ξ)-optimal. Proof of Lemma C.6. We work on the high-probability event of Lemma 3.1. On this event, for every policy π ∈ Π and every f ∈ F, q P̂ t ,π P real ,π P̂ t ,π P̂ t ,π Vf,1 (s1 ) − Vf,1 (s1 ) ≤ 3e H Vb,1 (s1 ) + H Vb,1 (s1 ). By the assumed upper bound, we have t

real

P̂ ,π P max Vf,1 (s1 ) − Vf,1 f ∈F

,π

t

P̂ ,π (s1 ) ≤ ε, ∀π ∈ {π ∈ Π | Vc,1 (s1 ) ≥ ℓ}.

(21)

By the first two conditions in Lemma C.6, the policy π 0 satisfies ξ P real ,π 0 P̂ t ,π 0 (s1 ) ≥ ℓ + ξ. Vc,1 (s1 ) ≥ ℓ + , Vc,1 2 Let π ⋆ be an optimal feasible policy for the true CMDP: n real o P ,π P real ,π π ⋆ ∈ arg max Vr,1 (s1 ) : Vc,1 (s1 ) ≥ ℓ .

(22)

π∈Π

For each λ ∈ [0, 1], let π λ be the episode-level mixture policy that follows π 0 with probability λ and follows π ⋆ with probability 1 − λ. For every f ∈ F, we have 30

real

P Vf,1

,π λ

real

P (s1 ) = (1 − λ)Vf,1

,π ⋆

real

P (s1 ) + λVf,1

,π 0

(s1 ),

(23)

and analogously, t

λ

t

⋆

t

0

P̂ ,π P̂ ,π P̂ ,π Vf,1 (s1 ) = (1 − λ)Vf,1 (s1 ) + λVf,1 (s1 ).

(24)

λ

Although π is a mixture policy and therefore may not belong to Π, Inequality (21) still applies √ P̂ t ,π λ whenever Vc,1 (s1 ) ≥ ℓ. To see this, define g(x) := 3e Hx + Hx. By Inequalities (23)–(24) and the triangle inequality, t

λ

real

λ

P̂ ,π P ,π max Vf,1 (s1 ) − Vf,1 (s1 ) f ∈F  t ⋆   t 0  P̂ ,π P̂ ,π ≤ (1 − λ)g Vb,1 (s1 ) + λg Vb,1 (s1 )  t λ  P̂ ,π ≤ g Vb,1 (s1 ) ,

where the first inequality applies Lemma 3.1 to π ⋆ , π 0 ∈ Π, and the second uses the concavity of P̂ t ,π λ g together with the linearity of Vb,1 (s1 ) in the mixing weight. Moreover, π λ induces the same state-action occupancy measure under P̂ t as some π̃ ∈ Π. Hence t

t

λ

t

t

λ

P̂ ,π̃ P̂ ,π P̂ ,π̃ P̂ ,π Vc,1 (s1 ) = Vc,1 (s1 ) ≥ ℓ, Vb,1 (s1 ) = Vb,1 (s1 ),

and therefore

  t   t λ P̂ ,π P̂ ,π̃ g Vb,1 (s1 ) = g Vb,1 (s1 ) ≤ ε

by Inequality (20). Since ε ≤ 4ξ , we have t

0

P̂ ,π Vc,1 (s1 ) ≥ ℓ +

Then the set

ξ ≥ ℓ + ε. 2

n o P̂ t ,π λ Λ := λ ∈ [0, 1] : Vc,1 (s1 ) ≥ ℓ + ε

is nonempty. Define λ⋆ := inf Λ. P̂ t ,π λ By the linearity of λ 7→ Vc,1 (s1 ) and the set Λ is closed, we have λ⋆ ∈ Λ, and therefore t

λ⋆

P̂ ,π (s1 ) ≥ ℓ + ε. Vc,1

(25)

We next show that λ⋆ is small. If λ⋆ = 0, the desired bound is trivial. Suppose λ⋆ > 0. By the P̂ t ,π λ minimality of λ⋆ and the continuity of λ 7→ Vc,1 (s1 ), t

λ⋆

P̂ ,π Vc,1 (s1 ) = ℓ + ε.

Since π λ⋆ is empirically feasible at level ℓ, Inequality (21) gives real

P Vc,1

,π λ⋆

t

λ⋆

P̂ ,π (s1 ) ≤ Vc,1 (s1 ) + ε = ℓ + 2ε.

On the other hand, by Inequalities (22) and (23), and feasibility of π ⋆ , real

P Vc,1

,π λ⋆

real

P (s1 ) = (1 − λ⋆ )Vc,1

,π ⋆

real

P (s1 ) + λ⋆ Vc,1

,π 0

(s1 ) ≥ (1 − λ⋆ )ℓ + λ⋆ (ℓ + ξ) = ℓ + λ⋆ ξ.

Combining the two bounds yields ℓ + λ⋆ ξ ≤ ℓ + 2ε =⇒ λ⋆ ≤

2ε . ξ

(26)

The same bound also holds when λ⋆ = 0. We now prove feasibility of π out in the true CMDP. Since π out is feasible for the tightened empirical CMDP, P̂ t ,π out Vc,1 (s1 ) ≥ ℓ + ε. 31

Thus π out is empirically feasible at level ℓ, and Inequality (21) gives real

P Vc,1

,π out

t

P̂ ,π (s1 ) ≥ Vc,1

out

(s1 ) − ε ≥ ℓ.

Therefore, π out is feasible for the true CMDP. It remains to prove near-optimality of π out . By Inequality (25), π λ⋆ is feasible for the tightened empirical CMDP. Since π out is an optimal solution of that problem, and since by the occupancymeasure argument above π λ⋆ has the same empirical constraint and reward values as some Markov policy π̃ ∈ Π, which is therefore itself feasible for the tightened empirical CMDP, t

P̂ ,π Vr,1

out

t

λ⋆

t

P̂ ,π P̂ ,π̃ (s1 ) ≥ Vr,1 (s1 ) = Vr,1 (s1 ).

Both π out and π λ⋆ are empirically feasible at level ℓ, so we can apply Inequality (21) to both and get real

P Vr,1

,π out

t

P̂ ,π (s1 ) ≥ Vr,1

out

t

λ⋆

real

P̂ ,π P (s1 ) − ε ≥ Vr,1 (s1 ) − ε ≥ Vr,1

,π λ⋆

(s1 ) − 2ε.

(27)

Using the linearity of the episode-level mixture and the non-negativity of rewards, real

P Vr,1

,π λ⋆

real

P (s1 ) = (1 − λ⋆ )Vr,1 real

P Since rh ∈ [0, 1], we have Vr,1 real

P Vr,1

,π ⋆

,π ⋆

real

P (s1 ) + λ⋆ Vr,1

,π 0

real

P (s1 ) ≥ (1 − λ⋆ )Vr,1

,π ⋆

(s1 ).

(s1 ) ≤ H. Together with Inequality (26), this implies

real

P (s1 ) − Vr,1

,π ⋆

,π λ⋆

real

P (s1 ) ≤ λ⋆ Vr,1

,π ⋆

(s1 ) ≤ λ⋆ H ≤

2εH . ξ

Combining this bound with Inequality (27), we obtain real

P Vr,1

,π ⋆

real

P (s1 ) − Vr,1

,π out

real

P (s1 ) ≤ Vr,1

,π ⋆

real

P (s1 ) − Vr,1

,π λ⋆

(s1 ) + 2ε ≤

2εH + 2ε. ξ

This completes the proof. Now, we are ready to prove Theorem 4.1. Proof of Theorem 4.1. In the following, we condition on the high-probability events in Lemmas C.1 and 3.1. Throughout, we may assume ϵ ≤ H without loss of generality: since rh ∈ [0, 1] for every r ∈ F, P real ,π we have Vr,1 (s1 ) ∈ [0, H] for every policy π, so for ϵ > H the near-optimality requirement in Objective is satisfied by any feasible policy, in particular by π 0 . Moreover, ch ∈ [0, 1] gives P real ,π 0 Vc,1 (s1 ) ≤ H, so Assumption 2.2 yields ξ ≤ H − ℓ ≤ H. Consequently, with ε = ξϵ/(2H), ε ξϵ H = ≤ <H 2 4H 4 t

and

ε ξϵ ξ = ≤ . 2 4H 4

(28)

0

P̂ ,π Safe exploration. If Vc,1 (s1 ) < ℓ + 2ξ , we execute the initial safe policy π 0 . Otherwise, we t execute the mixture policy π , which satisfies real

P Vc,1

,π t

real

P = αt Vc,1

,π̄ t

real

0

P ,π + (1 − αt )Vc,1 q (i)
P̂ t ,π̄ t P̂ t ,π̄ t P̂ t ,π̄ t ≥ αt Vc,1 (s1 ) + HVb,1 (s1 )} + (1 − αt )(ξ + ℓ) − min{H, 3e HVb,1 q
P̂ t ,π̄ t P̂ t ,π̄ t P̂ t ,π̄ t = ξ + ℓ − αt min{H, 3e HVb,1 (s1 ) + HVb,1 (s1 )} + ℓ − Vc,1 (s1 ) + ξ (ii)

≥ ℓ. Here, step (i) follows from Assumption 2.2 and Lemma 3.1, while step (ii) uses the definition of αt . Therefore, safe exploration is ensured. 32

Optimality. We first establish optimality. If the algorithm terminates at iteration t, the break t condition gives ∆q ≤ ε/2. By the first bound in (28) we have ε/2 < H, so the minimum in t

t

t

t

P̂ ,π̄ P̂ ,π̄ ∆t = min{H, 3e HVb,1 (s1 ) + HVb,1 (s1 )} is attained by its second argument, and therefore q n t o ξϵ P̂ t ,π̄ t P̂ t ,π̄ t P̂ ,π P̂ t ,π 3e HVb,1 (s1 ) + HVb,1 (s1 ) ≤ , where π̄ t = arg max Vb,1 (s1 ) : Vc,1 (s1 ) ≥ ℓ . π∈Π 4H

√ P̂ t ,π Since Vb,1 (s1 ) ≥ 0 for all π ∈ Π, the function x 7→ 3e x + x is nondecreasing. Therefore,   q q ξϵ P̂ t ,π̄ t P̂ t ,π P̂ t ,π P̂ t ,π̄ t 3e HVb,1 (s1 ) + HVb,1 (s1 ) ≤ 3e HVb,1 (s1 ) + HVb,1 (s1 ) ≤ max . P̂ t ,π 4H π∈Π:V (s1 )≥ℓ c,1

Hence, the optimal value of  q  P̂ t ,π P̂ t ,π P̂ t ,π max 3e HVb,1 (s1 ) + HVb,1 (s1 ) : Vc,1 (s1 ) ≥ ℓ π∈Π

ξϵ . By Lemma 3.1, we have that the optimal value of is upper bounded by 4H

max

P̂ t ,π π:Vc,1 (s1 )≥ℓ

et,π f,1 (s1 )

ξϵ . is also upper bounded by 4H t

0

P̂ ,π Moreover, Algorithm 1 terminates only if Vc,1 (s1 ) ≥ ℓ + 2ξ (see line 5). Thus, π 0 is empirically feasible at level ℓ, and the bound above applies to π 0 as well. Line 17 of Algorithm 1 returns n t o P̂ ,π P̂ t ,π π out ∈ arg max Vr,1 (s1 ) : Vc,1 (s1 ) ≥ ℓ + ε/2 . π∈Π

This is exactly the tightened empirical problem in Lemma C.6, with accuracy parameter ε/2 = ξϵ/(4H). Therefore, real

P Vr,1

,π ⋆

real

P (s1 ) − Vr,1

,π out

(s1 ) ≤

ε ϵ ξϵ 2H ε · +2· = + ≤ ϵ, ξ 2 2 2 2H

where the last inequality uses ξ ≤ H. Sample complexity. It remains to upper bound the sample complexity. We fix an iteration t and t ,π derive a uniform upper bound on QP̂ b,h (s, a) for all (s, a, h) and π ∈ Π. By definition,   11Hβ(nth (s, a), δ) 1 P̂ t ,π P̂ t ,π Qb,h (s, a) ≤ + 1+ P̂ht Vb,h+1 (s, a) nth (s, a) H     11Hβ(nth (s, a), δ) 1 1 P̂ t ,π P̂ t ,π t = + 1+ (P̂h − Ph )Vb,h+1 (s, a) + 1 + Ph Vb,h+1 (s, a).(29) nth (s, a) H H t

t

,π P̂ ,π For the well definiteness of QP̂ b,h (s, a), we define Vb,H+1 (s) = 0. Applying Lemma D.3 on the t

P̂ ,π 1 H−1 above bound with Vb,h+1 (s) ≤ (1 + H ) H yields: v u u 2Var (V P̂ t ,π )(s, a)β(nt (s, a), δ) 2(1 + 1 )H−1 Hβ(nt (s, a), δ) Ph t b,h+1 h P̂ t ,π h t H (P̂h − Ph )Vb,h+1 (s, a) ≤ + . nth (s, a) 3nth (s, a) (30) t √ P̂ t ,π P̂ ,π 1 H−1 Using VarPh (Vb,h+1 )(s, a) ≤ (1 + H ) HPh Vb,h+1 (s, a) and xy ≤ x + y for x, y ≥ 0, we bound the square-root term as v u P̂ t ,π u 2Var (V P̂ t ,π )(s, a)β(nt (s, a), δ) Ph Vb,h+1 (s, a) 2(1 + H1 )H−1 H 2 β(nth (s, a), δ) Ph t b,h+1 h ≤ + . nth (s, a) H nth (s, a)

33

Substituting into Inequality (30) gives   P̂ t ,π 1 8eH 2 β(nth (s, a), δ) 2Ph Vb,h+1 (s, a) P̂ t ,π t 1+ (P̂h − Ph )Vb,h+1 (s, a) ≤ + . H 3nth (s, a) H t

P̂ ,π Plugging this into Inequality (29) and using Qb,h (s, a) ≤ eH, we obtain for all nth (s, a) ≥ 0,     3 β(nth (s, a), δ) P̂ t ,π P̂ t ,π 2 ∧1 + 1+ Ph Vb,h+1 (s, a). (31) Qb,h (s, a) ≤ 7eH t nh (s, a) H

Meanwhile, for (h, s, a) ̸∈ B̂ t , we have     t t 1 1 ,π P̂ t ,π t P̂ ,π QP̂ (s, a) = 1 + P̂ V Phreal Vb,h+1 (s, a) = 1 + (s, a). h b,h+1 b,h H H Together with Inequality (31), we have     t 3 β(nth (s, a), δ) P̂ t ,π ,π 2 + 1 + ∧ 1 1 Ph Vb,h+1 (s, a). QP̂ (s, a) ≤ 7eH b,h (h,s,a)∈B̂t t nh (s, a) H Unrolling the above inequality over timestep h and using (1 + 3/H)H ≤ e3 yields   X real β(nth (s, a), δ) P̂ t ,π ,π (s1 ) ≤ 7H 2 e4 dP (s, a) Vb,1 ∧ 1 , h nth (s, a) t (h,s,a)∈B̂

Applying Lemma C.2 to replace counts by pseudo-counts gives n o X real β(n̄t (s,a),δ) P̂ t ,π ,π Vb,1 (s1 ) ≤ 28H 2 e4 dP (s, a) min 41 , n̄t h(s,a)∨1 . h

(32)

h

(h,s,a)∈B̂t

If the algorithm does not terminate before T , we divide the iterations into two sets: Eπ0 := {t ∈ [T ] | π t = π 0 is executed in line 6 of Algorithm 1}, and

Erest := {t ∈ [T ] | π t is the mixture policy executed in line 13 of Algorithm 1}. We bound these two sets separately. The set Eπ0 consists of iterations where the algorithm falls back to the initial safe policy π 0 , which happens when its empirical safety guarantee for π 0 is not yet reliable; this part can be controlled using the estimation error of π 0 . The set Erest consists of iterations where the adaptive mixture policy is executed; this part is controlled using the stopping rule together with the growth of pseudo-counts induced by the mixing weight αt . Combining these two bounds yields the desired upper bound on T . Summing Inequality (32) over t ∈ Eπ0 gives X P̂ t ,πt X X Vb,1 (s1 ) ≤ 28H 2 e4 t∈Eπ0

dP h

real

,π t

(s, a) min

n

t 1 β(n̄h (s,a),δ) 4 , n̄th (s,a)∨1

o

t∈Eπ0 (h,s,a)∈B̂t

≤ 28H 2 e4

T X

X

t (n̄t+1 h (s, a) − n̄h (s, a)) min

t=1 (h,s,a)∈B̂t

where last step uses dP h

real

,π

t

n

t 1 β(n̄h (s,a),δ) 4 , n̄th (s,a)∨1

o ,

t (s, a) = n̄t+1 h (s, a) − n̄h (s, a).

For each (h, s, a) ∈ [H] × S × A, define the last iteration at which it remains in B̂ t−1 by n o ′ τh,s,a := max t ∈ {0, . . . , T } : (h, s, a) ∈ B̂ t −1 for every t′ ∈ {1, . . . , t} . By fact (i) from Lemma C.3, (h, s, a) ∈ B̂ t implies t ≤ τh,s,a . Therefore, τh,s,a

X t∈Eπ0

t

t

P̂ ,π Vb,1 (s1 ) ≤ 28H 2 e4

X

X

(h,s,a)∈[H]×S×A t=1

t (n̄t+1 h (s, a) − n̄h (s, a)) min

n

t 1 β(n̄h (s,a),δ) 4 , n̄th (s,a)∨1

o .

(33) 34

Since for any fixed (h, s, a) and apply Lemma D.5, we have τh,s,a

X

o  n
τ +1 β(n̄t ,δ) ≤ 2β(n̄hh,s,a (s, a), δ) 1 + (log n̄t+1 − n̄th min 41 , n̄t h∨1 h h

t=1

τ

n̄hh,s,a

+1

(s,a)

τh,s,a +1

4β(n̄h

(s,a),δ)

 )+ .

real PT τ +1 ,π i If (h, s, a) ∈ B, then n̄hh,s,a (s, a) ≤ T , since n̄Th +1 (s, a) = i=1 dP (s, a) ≤ T . Now h σ consider (h, s, a) ∈ / B. If there exists an iteration σh,s,a such that nhh,s,a (s, a) ≥ n, let σh,s,a be the σh,s,a first such iteration. Since nth (s, a) − nt−1 (s, a) = n. By Lemma C.4, h (s, a) ∈ {0, 1}, we have nh (h, s, a) is removed at or before iteration σh,s,a , and thus τh,s,a ≤ σh,s,a . Together with the event E cnt ,

τ σ σ n̄hh,s,a (s, a) ≤ n̄hh,s,a (s, a) ≤ 2 nhh,s,a (s, a) + β cnt (δ) = 2 n + β cnt (δ) .

If no such iteration exists, then nTh (s, a) < n. Hence, in either case,
τ n̄hh,s,a (s, a) ≤ 2 n + β cnt (δ) ≤ 4n, where last inequality uses the fact that β cnt (δ) ≤ n. Combining these two cases together with Lemma D.5 and the monotonicity of φ, we obtain τh,s,a

X

X

(h,s,a)∈[H]×S×A

t=1

n o t
t 1 β(n̄h (s,a),δ) n̄t+1 ≤ M, h (s, a) − n̄h (s, a) min 4 , n̄t (s,a)∨1

(34)

h

where    
T 4n+1 )+ + 2 H|S||A| − |B| β(4n+1, δ) 1 + (log 4β(4n+1,δ) )+ . M := 2|B| β(T, δ) 1 + (log 4β(T,δ) Therefore, applying Inequality (34) on Inequality (33) gives X P̂ t ,πt Vb,1 (s1 ) ≤ 28M H 2 e4 .

(35)

t∈Eπ0

Moreover, by Assumption 2.2 and the definition of Eπ0 , for every t ∈ Eπ0 ,   ξ ξ P real ,π 0 P̂ t ,π 0 Vc,1 (s1 ) − Vc,1 (s1 ) ≥ (ℓ + ξ) − ℓ + = . 2 2 Together with Lemma 3.1, this implies  q  ξ|E 0 | X  X  P real ,π0 π P̂ t ,π t P̂ t ,π t P̂ t ,π 0 HVb,1 (s1 ) + 3e HVb,1 (s1 ) ≥ Vc,1 . (s1 ) − Vc,1 (s1 ) ≥ 2 t∈Eπ0

t∈Eπ0

Combining this bound with Inequality (35) and applying Cauchy–Schwarz inequality gives  q X  ξ|Eπ0 | P̂ t ,π t P̂ t ,π t (s1 ) ≤ HVb,1 (s1 ) + 3e HVb,1 2 t∈Eπ0 s X P̂ t ,πt X P̂ t ,πt ≤H Vb,1 (s1 ) + 3e H|Eπ0 | Vb,1 (s1 ) t∈Eπ0 3 4

≤ 28M H e + 3e

t∈Eπ0

p

28M |Eπ

3 4 0 |H e √

2

Since ax2 − bx − c ≤ 0 with a, b, c > 0 implies x ≤ b+ b2a+4ac , solving the above quadratic inequality gives p
2 28M 3e + 9e2 + 2ξ H 3 e4 |Eπ0 | ≤ . (36) ξ2 For each iteration t ∈ Erest , using Inequality (32), the monotonicity of β(·, δ), and Lemma D.5, we have n o X real β(n̄t (s,a),δ) P̂ t ,π̄ t ,π̄ t Vb,1 (s1 ) ≤ 28H 2 e4 dP (s, a) min 41 , n̄t h(s,a)∨1 h h

(h,s,a)∈B̂t

35

X

≤ 28H 2 e4

(h,s,a)∈B̂

o n t n̄t+1 β(n̄t (s,a),δ) h (s, a) − n̄h (s, a) min 14 , n̄t h(s,a)∨1 , t h α t

where last step uses P t n̄t+1 h (s, a) − n̄h (s, a) = dh

real

,π t

(s, a) = αt dhP

real

,π̄ t

≥ αt dhP

real

t

,π̄

(s, a) + (1 − αt )dhP

real

,π 0

(s, a)

(s, a).

We further split Erest into  EA :=

P̂ t ,π̄ t t ∈ Erest : HVb,1 (s1 ) + 3e

 q P̂ t ,π̄ t HVb,1 (s1 ) ≤ ξ ,

EB := Erest \ EA . t

t

P̂ ,π̄ For every t ∈ EA , by the definition of αt and the fact that Vc,1 (s1 ) ≥ ℓ by construction,

αt ≥ 

ξ  q P̂ t ,π̄ t P̂ t ,π̄ t P̂ t ,π̄ t (s1 ) + 3e HVb,1 ℓ + HVb,1 (s1 ) − Vc,1 (s1 ) +ξ +

1 ≥ . ≥ P̂ t ,π̄ t 2 (ℓ + ξ − V (s1 ))+ + ξ ξ

c,1

Therefore, X P̂ t ,π̄t X Vb,1 (s1 ) ≤ 56H 2 e4 t∈EA

X

t (n̄t+1 h (s, a) − n̄h (s, a)) min

n

t 1 β(n̄h (s,a),δ) 4 , n̄th (s,a)∨1

o

t∈EA (h,s,a)∈B̂t

≤ 56H 2 e4

T X

X

t (n̄t+1 h (s, a) − n̄h (s, a)) min

t=1 (h,s,a)∈B̂t

n

t 1 β(n̄h (s,a),δ) 4 , n̄th (s,a)∨1

o

τh,s,a

X

≤ 56H 2 e4

X

t (n̄t+1 h (s, a) − n̄h (s, a)) min

n

(h,s,a)∈[H]×S×A t=1

t 1 β(n̄h (s,a),δ) 4 , n̄th (s,a)∨1

o

2 4

≤ 56M H e , where the last step follows from Inequality (34). For any t ∈ [T ], since ∆t ≤ H by clipping, we also have αt ≥

ξ . H +ξ

Thus, for any subset E ′ ⊆ Erest , X

t

t

P̂ ,π̄ Vb,1 (s1 ) ≤

t∈E ′

28(H + ξ)M H 2 e4 . ξ

Applying this bound with E ′ is EB , Erest and using the sharper bound above for EA , Cauchy–Schwarz inequality gives  q X  P̂ t ,π̄ t P̂ t ,π̄ t HVb,1 (s1 ) + 3e HVb,1 (s1 ) t∈Erest

s ≤3e

H|EA |

X

P̂ t ,π̄ t Vb,1 (s1 ) + 3e

s H|EB |

t∈EA

√ ≤ 504M H 3 e6

t

X t∈EB

s p

|EA | +

(H + ξ)|EB | ξ

36

! +

t

P̂ ,π̄ Vb,1 (s1 ) + H

X

t

t

P̂ ,π̄ Vb,1 (s1 )

t∈Erest

28(H + ξ)M H 3 e4 . ξ

(37)

Since the algorithm does not terminate before T , the stopping rule implies that for every t ∈ Erest , q ξϵ P̂ t ,π̄ t P̂ t ,π̄ t ≤ HVb,1 (s1 ). (s1 ) + 3e HVb,1 4H Moreover, by the definition of EB , for every t ∈ EB , q P̂ t ,π̄ t P̂ t ,π̄ t ξ ≤ HVb,1 (s1 ) + 3e HVb,1 (s1 ). Combining these inequalities gives  q X  ξϵ|EA | P̂ t ,π̄ t P̂ t ,π̄ t + ξ|EB | ≤ HVb,1 (s1 ) + 3e HVb,1 (s1 ) . 4H t∈Erest

Plugging this into Inequality (37), we obtain √ ξϵ|EA | + ξ|EB |≤ 504M H 3 e6 4H

s p

|EA | +

(H + ξ)|EB | ξ

! +

28(H + ξ)M H 3 e4 . ξ

By Lemma D.7 with α = 2, we obtain |Erest | =|EA | + |EB | s s " !2 # 4H H +ξ 224(H + ξ)e4 H 3 HM 6 3 2016e H + + ≤ ξϵ ξϵ ξ2 ξ   2 2 4 4 4032e (H + ξ) 224(H + ξ) M H e 16128e H + + . ≤ ξϵ ξϵ ξ2 ξ where the last step uses (x + y)2 ≤ 2x2 + 2y 2 . Combining this with the bound on |Eπ0 | in (36), we obtain T = |Eπ0 | + |Erest | p
2   28M 3e + 9e2 + 2ξ H 3 e4 M H 4 e4 16128e2 H 4032e2 (H + ξ) 224(H + ξ) ≤ + + + ξϵ ξϵ ξ2 ξ ξ2 6 5 49280 e H M. (38) ≤ 2 ξ ϵ min{1, ϵ, ξ} 6

5

e H For simplicity, define C := ξ249280 ϵ min{1,ϵ,ξ} . We next bound T by splitting M = MB (T ) + Mid , where 
 T MB (T ) := 2|B| β(T, δ) 1 + log 4β(T,δ) , + 

 4n+1 Mid := 2 H|S||A| − |B| β(4n+1, δ) 1 + log 4β(4n+1,δ) . +

If CMid ≥ T /2, then T ≤ 2CMid . By the definition of n, we have e T ≤O

 H 5 |S| H|S||A| − |B|
ξ 2 ϵ min{1, ϵ, ξ}

 log2 σ1s .

(39)

On the other hand, if CMid ≤ T /2, then Inequality (38) gives T ≤ 2CMB (T ). Applying Lemma D.4, we have e T ≤O



H 5 |S||B|  . ξ 2 ϵ min{1, ϵ, ξ} 37

(40)

Combining Inequalities (39) and (40), we obtain
 n 5 H 5 |S||B| o e max H |S| H|S||A| − |B| log2 1 , . T ≤O σ 2 2 s ξ ϵ min{1, ϵ, ξ} ξ ϵ min{1, ϵ, ξ} Since each iteration collects one trajectory of length H, the total number of samples drawn from Mreal is at most  n H 6 |S| H|S||A| − |B|
H 6 |S||B| o 2 1 e max , . HT ≤ O log σs ξ 2 ϵ min{1, ϵ, ξ} ξ 2 ϵ min{1, ϵ, ξ}

D

Supporting lemmas

We first state a deviation inequality for empirical distributions of i.i.d. categorical samples, which will be used to control the estimation error of empirical transition models. Let (Xt )t∈N be i.i.d. samples from a distribution supported on [m] with probability vector p ∈ ∆([m]). We denote by p̂n the empirical distribution, i.e., n 1X 1{Xℓ =k} , k ∈ [m]. p̂n,k = n ℓ=1

Lemma D.1 ([Jonsson et al., 2020, Proposition 1]). For all p ∈ ∆([m]) and all δ ∈ (0, 1),     n Pr ∃n ∈ N, nKL(p̂n , p) > log(1/δ) + (m − 1) log e 1 + ≤ δ. m−1 Next, we state a deviation inequality for adapted Bernoulli random variables, which will be used to control state-action visitation counts. Let (Ft )t∈N be a filtration and let (Xt )t∈N be Bernoulli random variables such that Xt is Ft -measurable and Pr(Xt = 1 | Ft−1 ) = Pt , where Pt is Ft−1 -measurable. Lemma D.2 ([Dann et al., 2017, Lemma F.4]). For all δ > 0, n X

n

1X 1 Pr ∃n ∈ N : Xt < Pt − log 2 δ t=1 t=1

! ≤ δ.

Lemma D.3 ([Ménard et al., 2021, Lemmas 10, 11, 12]). Let p, q ∈ ∆(S). For any α, b > 0 and any functions f, g : S → [0, b], if KL(p, q) ≤ α, then Varq (f ) ≤ 2Varp (f ) + 4b2 α, Varp (f ) ≤ 2Varq (f ) + 4b2 α, Varp (f ) ≤ 2Varp (g) + 2bp|f − g|, Varq (f ) ≤ Varp (f ) + 3b2 ∥p − q∥1 , q q 2 2 |Ep f − Eq f | ≤ 2Varq (f )α + bα, |Eq f − Ep f | ≤ 2Varp (f )α + bα. 3 3 Lemma D.4 ([Ménard et al., 2021, Lemma 13]). Let C be a non-negative scalar and A, B, D, E, and α be positive scalars such that 1 ≤ B ≤ E and α ≥ e. If τ ≥ 0 satisfies q

τ ≤ C τ A log(ατ ) + B log(ατ )2 + D A log(ατ ) + E log(ατ )2 then

  √ τ ≤ C 2 (A + B) C12 + D + 2 DC (A + E) C12 + 1,

where

8 log 11α2 (A + E) (C + D) . 5 Remark. [Ménard et al., 2021, Lemma 13] is stated for C be positive, but the same proof applies C be non-negative. C1 =

38

Lemma D.5. Let β : [0, ∞) → [1, ∞) be nondecreasing. For any τ ∈ N and any sequence (ut )t∈N Pt with ut ∈ [0, 1], define U0 := 0 and Ut := ℓ=1 uℓ . Then τ o   n X Uτ +1 t) ≤ 2 β(Uτ +1 ) 1 + (log 4β(U ) . ut+1 min 14 , β(U + Ut ∨1 ) τ +1 t=0

Proof of Lemma D.5. If Uτ +1 ≤ 4β(Uτ +1 ), we have τ τ o X n X ut+1 Uτ +1 t) ≤ ut+1 min 14 , β(U = ≤ β(Uτ +1 ), Ut ∨1 4 4 t=0 t=0 which implies the lemma. Hence, assume that Uτ +1 > 4β(Uτ +1 ), and let t0 := max{t ∈ {0, . . . , τ } : Ut ≤ 4β(Uτ +1 )}. This index is well-defined because U0 = 0. We first bound the part of the sum with t ≤ t0 by t0 t0 o X n X ut+1 Ut +1 4β(Uτ +1 ) + 1 1 t) ≤ ut+1 min 14 , β(U = 0 ≤ ≤ β(Uτ +1 ) + . Ut ∨1 4 4 4 4 t=0 t=0 Here we used Ut0 +1 ≤ Ut0 + 1 ≤ 4β(Uτ +1 ) + 1. We now bound the part of the sum with t > t0 . For such t, we have Ut > 4β(Uτ +1 ). Since Ut ≤ Uτ +1 and β is nondecreasing, β(Ut ) ≤ β(Uτ +1 ). Therefore Ut > 4β(Ut ), so Ut > 1 and n o β(U ) β(Uτ +1 ) t t) min 14 , β(U = ≤ . Ut ∨1 Ut Ut Also, since Ut+1 = Ut + ut+1 with ut+1 ≤ 1, and Ut > 4β(Uτ +1 ) ≥ 4, we have 5 ut+1 1 1 Ut+1 ≤ . =1+ ≤1+ ≤1+ Ut Ut Ut 4β(Uτ +1 ) 4 Applying − log(1 − v) ≥ v with v = ut+1 /Ut+1 ∈ [0, 1) gives ut+1 Ut+1 ≤ log . Ut+1 Ut Thus, τ X

τ τ n o X X Ut+1 5 ut+1 t) ut+1 min 14 , β(U β(U ) log ≤ ≤ β(U ) τ +1 τ +1 Ut ∨1 U 4 Ut t t=t +1 t=t +1 t=t +1 0

0

0

Uτ +1 Uτ +1 5 5 ≤ β(Uτ +1 ) log . = β(Uτ +1 ) log 4 Ut0 +1 4 4β(Uτ +1 ) The last inequality uses Ut0 +1 > 4β(Uτ +1 ), which follows from the definiton of t0 and the assumption Uτ +1 > 4β(Uτ +1 ). Combining the bounds for t ≤ t0 and t > t0 , and using β(Uτ +1 ) ≥ 1, we obtain τ o n X 1 5 Uτ +1 t) ut+1 min 14 , β(U ≤ β(Uτ +1 ) + + β(Uτ +1 ) log Ut ∨1 4 4 4β(Uτ +1 ) t=0   Uτ +1 ≤ 2β(Uτ +1 ) 1 + (log )+ . 4β(Uτ +1 ) Lemma D.6. Let c ≥ 0 and b ≥ 1, and suppose f : N → R+ satisfies f (m) ≤ c + b + b log(m + 1) for all m ∈ N. Then, for any κ > 0, define    2c 2b 2b † m := 1 + + log max ,e . κ κ κ Then m ≥ m† implies m ≥ f (m)/κ. 39

Proof. Let t := max{2b/κ, e}. By concavity of the logarithm, for all z, t > 0, z−t z = + log t − 1. t t Applying this with z = m + 1 and multiplying by b gives log z ≤ log t +

b(m + 1) + b log t − b. t Since t ≥ 2b/κ, we have b/t ≤ κ/2, and hence b log(m + 1) ≤

b log(m + 1) ≤

κ(m + 1) + b log t − b. 2

By definition of f (m), we obtain f (m) ≤ c + b + b log(m + 1) ≤ c +

κ(m + 1) + b log t. 2

Therefore, κm ≥ f (m) holds whenever κm ≥ c +

κ(m + 1) + b log t. 2

The last condition is equivalent to    2c 2b 2c 2b 2b m≥1+ + log t = 1 + + log max ,e = m† . κ κ κ κ κ Thus m ≥ m† implies κm ≥ f (m), equivalently m ≥ f (m)/κ. Lemma D.7. Let A, B, C, D, E and α be positive scalars with α > 1. If m, n ≥ 0 satisfy √ √  Am + Bn ≤ C m + Dn + E,

(41)

then  1  α2 m+n≤ C2 A ∧ B 4(α − 1)

1 √ + A

r

D B

!2

 α + E . α−1

Proof of Lemma D.7. Let Z := Am + Bn. Since m, n ≥ 0, we have m ≤ Z/A and n ≤ Z/B. Hence, r ! r r √ √ Z DZ D √ 1 m + Dn ≤ + = √ + Z. A B B A Substituting this into Inequality (41) gives r ! 1 D √ Z≤C √ + Z + E. B A q   √ Define a := C √1A + D B . Then Z ≤ a Z + E. By Young’s inequality, for any α > 1, √ Z αa2 a Z≤ + . α 4 Therefore, Z≤

Z αa2 + + E, α 4

and rearranging yields Z≤

α2 α a2 + E. 4(α − 1) α−1

Substituting the definition of a and using Z = Am + Bn ≥ (A ∧ B)(m + n) proves the Lemma. 40

Lemma D.8. Given a transition dynamics P , for any policy π, any function f ∈ F, any h ∈ [H], and any state s, we have " H # H X X X P,π P,π
′ ′ π 2 ′ ′ EP ( fℓ (sℓ , aℓ ) − Vf,h (sh )) | sh = s ≥ dP,π h′ (s , a |sh = s)VarPh′ Vf,h′ +1 (s , a ), h′ =h s′ ,a′

ℓ=h

(42) ′ where dP,π ℓ (s, a | sh = s ) is the state-action occupancy distribution at step ℓ ∈ {h, . . . , H} induced by policy π and the transition model P , conditioned on starting from state s′ at step h. Remark. Note that [Qu et al., 2025, Lemma 15] states a related result with an equality in (42) for stochastic policies. This equality is valid for deterministic policies, as shown in [Ménard et al., 2021, Lemma 7], but it does not hold in general for stochastic policies because policy randomness introduces additional variance terms. We prove and use the corresponding inequality, which suffices for our analysis.

Proof of Lemma D.8. First, note that P,π Vf,h (sh ) = EπP

"H X

# fℓ (sℓ , aℓ ) sh .

ℓ=h

Hence,  EπP 

H X

!2 P,π fℓ (sℓ , aℓ ) − Vf,h (sh )

 sh  = VarπP

ℓ=h

H X

! fℓ (sℓ , aℓ ) sh

.

(43)

ℓ=h

For any t ∈ {h, . . . , H}, applying the law of total variance with respect to at ∼ π t (·|st ) gives ! H X π VarP fℓ (sℓ , aℓ ) st ℓ=t

" VarπP

=Eat ∼πt (·|st )

H X

!# fℓ (sℓ , aℓ ) st , at

  + Varat ∼πt (·|st ) QP,π f,t (st , at )

ℓ=t

" ≥Eat ∼πt (·|st )

VarπP

H X

!# fℓ (sℓ , aℓ ) st , at

.

(44)

ℓ=t

Conditioned on (st , at ), the term ft (st , at ) is deterministic, so ! ! H H X X π π VarP fℓ (sℓ , aℓ ) st , at = VarP fℓ (sℓ , aℓ ) st , at . ℓ=t+1

ℓ=t

Applying the law of total variance again with respect to st+1 ∼ Pt (·|st , at ) yields ! H X π VarP fℓ (sℓ , aℓ ) st , at ℓ=t+1 P,π =VarPt (Vf,t+1 )(st , at ) + Pt VarπP

H X

! fℓ (sℓ , aℓ ) st+1

(st , at ).

(45)

ℓ=t+1

Combining Inequalities (44) and (45), we obtain the following lower bound ! H X π fℓ (sℓ , aℓ ) st VarP ℓ=t

h

i

P,π ≥Eat ∼πt (·|st ) VarPt (Vf,t+1 )(st , at )

" + Eat ∼πt (·|st )

Pt VarπP

H X ℓ=t+1

41

! fℓ (sℓ , aℓ ) st+1

# (st , at ) .

Unrolling this recursion from t = h to H gives ! H H X X X P,π ′ ′ ′ ′ dP,π VarπP fℓ (sℓ , aℓ ) sh = s ≥ h′ (s , a | sh = s)VarPh′ (Vf,h′ +1 )(s , a ). ℓ=h

h′ =h s′ ,a′

Combining this with Equation (43) proves the lemma.

42

Related documents

• PixSim: a calibrated open-source simulator of instant-payment fraud, recovery and interdiction under analyst capacity constraints#1105243
• Mitigating Front-Running Attacks through Fair and Resilient Transaction Dissemination#1051117
• Mitigating Front-Running Attacks through Fair and Resilient Transaction Dissemination#1028650
• CVE-2026-97602 — HIGH 7.8#1098320
• The concept of 'transfer' of data under European data protection law: In the context of transborder data flows#461940