Paper deep dive
Instance-Dependent Regret for CMDPs with Step-Wise Constraints
Qian Zuo, Francesco Emanuele Stradi, Leyang Xue, Sattar Vakili
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 10/5/2026, 6:22:49 AM
Summary
This paper studies online learning in episodic tabular constrained Markov decision processes (CMDPs) with step-wise safety constraints. The authors propose Safe Variance-Adaptive Exploration (SVAE), an algorithm that learns candidate safe subgraphs and performs variance-adaptive optimistic planning. SVAE achieves instance-dependent cumulative regret bounds that adapt to the variance of safe policies and the complexity of identifying safe actions, while maintaining sublinear step-wise constraint violation. The work establishes both upper bounds for SVAE and a matching lower bound, proving the necessity of dependence on instance-specific variance and safety identification complexity.
Entities (11)
Relation Signals (7)
Qian Zuo → affiliatedwith → University of Edinburgh
confidence 95% · Qian Zuo ... University of Edinburgh
Francesco Emanuele Stradi → affiliatedwith → Politecnico di Milano
confidence 95% · Francesco Emanuele Stradi ... Politecnico di Milano
SVAE → solves → CMDP
confidence 95% · We study online learning in episodic tabular constrained Markov decision processes... We propose Safe Variance-Adaptive Exploration (SVAE)
SVAE → achieves → cumulative regret bound
confidence 90% · With high probability, SVAE achieves cumulative regret of order O~(...)
SVAE → controls → step-wise constraint violation
confidence 90% · SVAE additionally attains O~(H sqrt(SAK)+S^2AH^2) step-wise constraint violation
Var* → isdefinedas → maximum return variance among safe policies
confidence 90% · Here, Var* is the maximum return variance among safe policies
Safe Subgraph → shapes → Variance
confidence 85% · In such a setting, the constraints induce a safe subgraph that shapes the variance of cumulative rewards under feasible policies
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study online learning in episodic tabular constrained Markov decision processes with step-wise safety constraints. In such a setting, the constraints induce a safe subgraph that shapes the variance of cumulative rewards under feasible policies and, consequently, the difficulty of learning. Exploiting this structure, however, requires learning which actions are safe while controlling constraint violations. We propose Safe Variance-Adaptive Exploration (SVAE), an efficient algorithm that learns candidate safe subgraphs and performs variance-adaptive optimistic planning within them. With high probability, SVAE achieves cumulative regret of order $\widetilde{\mathcal{O}}(\sqrt{SAH\min\{\mathbb{V}_\Sigma,K\mathrm{Var}^{\star}\}}+S\sqrt{AH^3\min\{K,\mathcal{C}\}}+S^2AH^2)$ over $K$ episodes, where $H$ is the horizon of a single episode, while $S$ and $A$ are the numbers of states and actions, respectively. Here, $\mathrm{Var}^{\star}$ is the maximum return variance among safe policies, $\mathbb{V}_\Sigma$ is the variance accumulated before the first unsafe action is encountered, and $\mathcal{C}$ captures the statistical complexity of eliminating actions incorrectly considered potentially safe. SVAE additionally attains $\widetilde{\mathcal{O}}(H\sqrt{SAK}+S^2AH^2)$ step-wise constraint violation and a gap-dependent violation bound that is polylogarithmic in $K$. Finally, we establish a lower bound showing that dependence on these instance-specific quantities is unavoidable.
Tags
Links
- Source: https://arxiv.org/abs/2610.02520v1
- Canonical: https://arxiv.org/abs/2610.02520v1
Trouble viewing inline? Open PDF directly →
Full Text
192,395 characters extracted from source content.
Expand or collapse full text
Instance-Dependent Regret for CMDPs with Step-Wise Constraints Qian Zuo Francesco Emanuele Stradi University of Edinburgh Politecnico di Milano qian.zuo@ed.ac.uk francescoemanuele.stradi@polimi.it Leyang Xue Sattar Vakili University of Edinburgh University College London lxue2@ed.ac.uk s.vakili@ucl.ac.uk Abstract We study online learning in episodic tabular constrained Markov decision processes with step-wise safety constraints. In such a setting, the constraints induce a safe subgraph that shapes the variance of cumulative rewards under feasible policies and, consequently, the difficulty of learning. Exploiting this structure, however, requires learning which actions are safe while controlling constraint violations. We propose Safe Variance-Adaptive Exploration (SVAE), an efficient algorithm that learns candidate safe subgraphs and performs variance-adaptive optimistic planning within them. With high probability, SVAE achieves cumulative regret of order ~(SAHminΣ,KVar⋆+SAH3minK,+S2AH2) O( SAH \V_ ,KVar \+S AH^3 \K,C\+S^2AH^2) over K episodes, where H is the horizon of a single episode, while S and A are the numbers of states and actions, respectively. Here, Var⋆Var is the maximum return variance among safe policies, ΣV_ is the variance accumulated before the first unsafe action is encountered, and C captures the statistical complexity of eliminating actions incorrectly considered potentially safe. SVAE additionally attains ~(HSAK+S2AH2) O(H SAK+S^2AH^2) step-wise constraint violation and a gap-dependent violation bound that is polylogarithmic in K. Finally, we establish a lower bound showing that dependence on these instance-specific quantities is unavoidable. 1 Introduction Constrained Markov decision processes (CMDPs) are widely used to model sequential decision making in robotics, autonomous driving, and wireless networks (Achiam et al., 2017; Liu et al., 2021; Bura et al., 2022). The objective is to maximize expected cumulative reward subject to safety or resource constraints, commonly imposed on expected cumulative costs (Altman, 1999; Miryoosefi and Jin, 2022; Stradi et al., 2025a). The potential harm from individual unsafe decisions motivates step-wise safety constraints, which impose a mean-cost threshold at each decision (Xiong et al., 2023; Shi et al., 2023). Violation is measured by summing positive excesses above this threshold without cancellation (Wei et al., 2024). In this work, we study online learning in episodic tabular constrained MDPs under this kind of step-wise constraint. Instance-dependent regret bounds distinguish the statistical difficulty of individual problems—namely, instances—and provide sharper guarantees on easier ones (Zanette and Brunskill, 2019; Dann et al., 2021). In unconstrained reinforcement learning, variance-dependent analyses relate regret to the uncertainty induced by rewards and transitions (Talebi and Maillard, 2018; Zhou et al., 2023b; Zhao et al., 2023; Chen et al., 2025). Such bounds can retain worst-case guarantees while improving on low-variance instances, including nearly constant regret in deterministic environments (Zhou et al., 2023b; Zamir et al., 2026). In CMDPs, unknown costs and transitions determine which policies are feasible (Bura et al., 2022; Yu et al., 2025). Exploratory policies can be unsafe, so their returns need not share the low variance of safe policies. Whether the benefits of variance-dependent learning can be retained under step-wise constraints is still unclear. Step-wise safety constraints can be represented by a safe subgraph that retains actions satisfying the cost threshold and leading only to states with feasible future decisions (Xiong et al., 2023; Shi et al., 2023). Our key observation is that even though learning under unknown constraints generally poses additional challenges, safety constraints can still simplify reward learning by removing stochastic branches or reducing differences in expected future rewards across possible next states under feasible policies. Even when the rewards and the transition kernel are fixed, changing costs can alter the safe subgraph and thereby reshape variances. However, small cost gaps and rare transitions to states with no feasible policy can still make safety identification difficult. Understanding how the safe subgraph relates to the variance and the statistical complexity is therefore central to instance-dependent regret analysis. These observations lead to the following questions: (i) Is it possible to design a computationally efficient algorithm that achieves variance-dependent regret bounds and sublinear cumulative step-wise violation? (i) How does the induced safe subgraph shape the statistical complexity of learning under step-wise constraints? To answer these questions, we first characterize how the induced safe subgraph shapes the variances and the safety identification complexity. We then propose Safe Variance-Adaptive Exploration (SVAE), which separates safe-subgraph learning from variance-adaptive planning. The algorithm learns candidate safe actions using variance-independent cost lower confidence bounds and observed successors, and plans optimistically over these sets using empirical reward and transition variances. We further evaluate SVAE and examine the effect of safe-subgraph properties on regret in synthetic experiments (Appendix H). Our contributions can be summarized as follows. • Safe-subgraph structure and variance In Section 3, we represent step-wise safety constraints through their induced safe subgraph and define two distinct variance quantities: (i)(i) the maximum safe-policy return variance Var⋆Var is the largest variance of the total episode return over all safe policies, and (ii)(i) the trajectory-based total variance ΣV_ sums reward variances and transition variances before the first unsafe action in each episode. We establish a tight bound on transition variance in terms of stochastic branching depth and differences in expected cumulative rewards across successor states within the safe subgraph. • Safety identification complexity In Section 3.3, we introduce a reward-independent instance quantity C to measure the difficulty of ruling out unsafe actions at states reachable under safe policies. Lower bounds for valid elimination establish its necessity. • Efficient variance-adaptive exploration In Section 4, we develop SVAE, an efficient algorithm that exploits low return variance within the unknown safe subgraph without prior knowledge of a safe policy. SVAE maintains candidate action sets that retain all safe actions with high probability and uses the resulting candidate subgraph to adapt its exploration bonuses to empirical reward and next-state value variances. • Instance-dependent learning guarantees In Section 5.1, we show that our algorithm attains, for a CMDP with S states, A actions, horizon H, a cumulative regret bound over K episodes of order ~(SAHminΣ,KVar⋆+SAH3minK,+S2AH2) O( SAH \V_ ,KVar \+S AH^3 \K,C\+S^2AH^2). Here ~ O hides polylogarithmic factors. Regret is polylogarithmic in K on fixed instances with Var⋆=0Var =0, while both regret and cumulative step-wise violation retain ~(K) O( K) worst-case dependence. Step-wise violation is also polylogarithmic in K for a fixed positive cost gap (Theorem 3). • Regret lower bound In Section 5.2, we establish a regret lower bound, showing that both return variance and safety identification dependencies are unavoidable. 1.1 Related Work Safe reinforcement learning Safe RL is a fundamental area of reinforcement learning, with diverse constraint formulations and measures of constraint violation. For episode-level constraints, regret and constraint-violation guarantees have been established in tabular settings (Efroni et al., 2020; Liu et al., 2021; Bura et al., 2022; Wei et al., 2022; Stradi et al., 2024; Stradi et al., 2025b) and with linear function approximation (Ding et al., 2021; Ghosh et al., 2022; Kitamura et al., 2025). For instantaneous constraints, Amani et al. (2021) and Roknilamouki et al. (2025) ensure constraint satisfaction with high probability using known safe actions or policies. Without a known safe policy, Xiong et al. (2023) and Wei et al. (2024) bound cumulative positive step-wise violation. Xiong et al. (2023) study tabular MDPs with costs that depend only on the state. Wei et al. (2024) consider linear MDPs and assume that a feasible action exists at every state and step. We study tabular MDPs with unknown state–action costs and require only the existence of a safe policy from the initial state. Variance-dependent regret Variance-dependent regret bounds can improve on worst-case rates in low-variance environments. Such guarantees have been established for episodic tabular MDPs (Zhou et al., 2023b), linear-mixture MDPs (Zhao et al., 2023), and infinite-horizon MDPs (Zamir et al., 2026), with recent work also combining variance and suboptimality gaps (Chen et al., 2025). In particular, Zhou et al. (2023b) derive bounds involving a maximum policy-return variance measure and a variance sum along the learner’s trajectories. For CMDPs, Yu et al. (2025) use total-variance analysis to improve the horizon dependence of a worst-case regret bound under episode-level constraints. Jiang and Ye (2024) obtain a different form of instance dependence through an optimal-basis characterization of the CMDP linear program. We control step-wise violation and derive a regret bound that separates safe-policy return variance from the complexity of ruling out actions outside the true safe set. Graph structure and safe exploration Graph structure has been used to guide safe exploration and refine regret bounds. Safe-region methods use reachability and returnability to expand the region that can be explored safely (Turchetta et al., 2016; Wachi and Sui, 2020). Shi et al. (2023) use safe subgraphs for learning under instantaneous constraints, assuming known transition supports and a known seed safe subgraph. For unconstrained MDPs, Bourel et al. (2020) combine variance-aware concentration with transition-support adaptation and obtain regret bounds involving local diameter and effective support. Our structural analysis examines how safety constraints change the graph available to safe policies and how this change affects their transition variance. We use this relation to bound the transition-variance contribution to regret in terms of stochastic branching and continuation-value differences within the safe subgraph. Due to space constraints, additional related works are provided in Appendix A. 2 Problem Formulation Episodic CMDP We consider an episodic constrained Markov decision process (CMDP) ℳ=(,,H,P,r,c,τ)M=(S,A,H,P,r,c,τ) with a state space S of size S, an action space A of size A, and horizon H. For a positive integer m, let [m]:=1,…,m[m]:=\1,…,m\. The transition kernel is P=Ph:×→Δh=1HP=\P_h:S×A→ _S\_h=1^H, where Δ _S denotes the set of probability distributions on S, and Ph(s′∣s,a)P_h(s s,a) denotes the transition probability from (s,a)(s,a) to s′s at step h. r=rh:×→[0,1]h=1Hr=\r_h:S×A→[0,1]\_h=1^H represents the reward function, and rh(s,a)r_h(s,a) is the reward of taking action a in state s at step h. A non-stationary policy π=πh:→h=1H∈Ππ=\ _h:S \_h=1^H∈ specifies an action πh(s) _h(s) at every state and step, and Π denotes the set of all such policies. The learner interacts with the CMDP for K episodes, each starting from a fixed initial state s1∈s_1 . For any episode k, the learner first chooses a policy πkπ^k based on previous observations. At step h∈[H]h∈[H] of episode k, the learner observes a state shks_h^k, chooses an action ahka_h^k, and transitions to a next state sh+1ks_h+1^k according to Ph(⋅∣shk,ahk)P_h(· s_h^k,a_h^k). For a policy π∈Ππ∈ , the state-value function Vhπ(s)V_h^π(s) and the state-action value function Qhπ(s,a)Q_h^π(s,a) are defined as: Vhπ(s):=π[∑t=hHrt(st,at)|sh=s],Qhπ(s,a):=π[∑t=hHrt(st,at)|sh=s,ah=a].V_h^π(s):=E^π\! [ _t=h^Hr_t(s_t,a_t)\, |\,s_h=s ], Q_h^π(s,a):=E^π\! [ _t=h^Hr_t(s_t,a_t)\, |\,s_h=s,a_h=a ]. The expectations start from s at step h and follow π, with the first action fixed to a for Qhπ(s,a)Q_h^π(s,a). We set VH+1π≡0V_H+1^π≡ 0 and let μhπ(s):=ℙπ(sh=s∣s1) _h^π(s):=P^π(s_h=s s_1) denote the step-h state occupancy under π, for h∈[H+1]h∈[H+1]. Similarly, c=ch:×→[0,1]h=1Hc=\c_h:S×A→[0,1]\_h=1^H denotes the cost function, and ch(s,a)c_h(s,a) is the cost of taking action a in state s at step h. Let τ∈[0,1]τ∈[0,1] denote the safety threshold. Under stochastic settings, the non-stationary reward and cost of state-action pair (s,a)(s,a) at step h are Rh(s,a)R_h(s,a) and Ch(s,a)C_h(s,a) supported on [0,1][0,1], with means rh(s,a)r_h(s,a) and ch(s,a)c_h(s,a), respectively. Conditional on the selected state–action pairs, reward and cost observations are independent across visits, and each observation is conditionally independent of the next state. Write RhkR_h^k and ChkC_h^k for the samples observed at step h of episode k. The threshold τ is known, whereas P=Phh=1HP=\P_h\_h=1^H, r=rhh=1Hr=\r_h\_h=1^H, and c=chh=1Hc=\c_h\_h=1^H are unknown. Safe subgraph The CMDP induces a layered directed graph =(,ℰ)G=(V,E) with vertex set =×[H+1]V=S×[H+1] (Jin et al., 2020). For h∈[H]h∈[H], the edge ((s,h),a,(s′,h+1))((s,h),a,(s ,h+1)) belongs to ℰE exactly when Ph(s′∣s,a)>0P_h(s s,a)>0. The safe subgraph safe=(safe,ℰsafe)G_safe=(V_safe,E_safe) is defined through safe actions and safe vertices by backward recursion. Set safe,H+1:=V_safe,H+1:=S. For h=H,…,1h=H,…,1, define recursively safe,h(s) _safe,h(s) :=a∈:ch(s,a)≤τ,supp(Ph(⋅∣s,a))⊆safe,h+1, := \a :c_h(s,a)≤τ,\ supp(P_h(· s,a)) _safe,h+1 \, (1) safe,h _safe,h :=s∈:safe,h(s)≠∅. :=\s :A_safe,h(s)≠ \. An action a is safe at (s,h)(s,h) if ch(s,a)≤τc_h(s,a)≤τ and all its successor vertices are safe. A vertex (s,h)(s,h) is safe when s∈safe,hs _safe,h. The vertex and edge sets of safeG_safe are safe:=(s,h)∈:s∈safe,hV_safe:= \(s,h) :s _safe,h \ and ℰsafe:=((s,h),a,(s′,h+1))∈ℰ:a∈safe,h(s)E_safe:= \((s,h),a,(s ,h+1)) :a _safe,h(s) \. For a policy π∈Ππ∈ , let π=(π,ℰπ)G^π=(V^π,E^π) denote the subgraph generated by π from s1s_1, containing the vertices and edges visited with positive probability (Shi et al., 2023). Its vertex and edge sets are π:=(s,h)∈:μhπ(s)>0V^π:=\(s,h) : _h^π(s)>0\ and ℰπ:=((s,h),a,(s′,h+1))∈ℰ:(s,h)∈π,a=πh(s)E^π:=\((s,h),a,(s ,h+1)) :(s,h) ^π,\ a= _h(s)\, respectively. Thus, πG^π includes all positive-probability successors of the action selected at each reachable vertex. We write π⊆safeG^π _safe when π⊆safeV^π _safe and ℰπ⊆ℰsafeE^π _safe. Therefore, the safe policy class is Πsafe:=π∈Π:π⊆safe _safe:=\π∈ :G^π _safe\. Let π⋆∈argmaxπ∈ΠsafeV1π(s1)π ∈ _π∈ _safeV_1^π(s_1) be an optimal safe policy, and write Vh⋆(s)=Vhπ⋆(s)V_h (s)=V_h^π (s). Performance metrics For the policies π1,…,πKπ^1,…,π^K executed by the learner, we define the cumulative regret and cumulative step-wise violation as: ℛ(K) (K) :=∑k=1K(V1⋆(s1)−V1πk(s1)), := _k=1^K (V_1 (s_1)-V_1^π^k(s_1) ), (2) Viol(K) (K) :=∑k=1K∑h=1H[ch(shk,ahk)−τ]+, := _k=1^K _h=1^H [c_h(s_h^k,a_h^k)-τ ]_+, (3) where [⋅]+:=max⋅,0[·]_+:= \·,0\. The regret ℛ(K)R(K) compares the learner’s cumulative expected return with that of the optimal safe policy, while Viol(K)Viol(K) accumulates positive mean-cost excesses along the learner’s trajectories. Xiong et al. (2023) study step-wise violation with state-only costs c(s)c(s), whereas our costs ch(s,a)c_h(s,a) depend on both the state and action and may vary across steps. Unlike constraints on expected cumulative costs, Equation (3) does not allow excess costs at one step to be offset by lower costs at another. We allow violations during exploration and control their cumulative magnitude, rather than require zero violation throughout learning as in Shi et al. (2023). Our goal is to obtain high-probability sublinear upper bounds in K on regret and violation, with regret adapting to the variance of safe policies and the difficulty of identifying actions outside the safe action sets. Our results generally require only that the initial state admit an unknown safe policy, which is a mild condition in the literature (Amani et al., 2021; Xiong et al., 2023; Shi et al., 2023; Wei et al., 2024; Roknilamouki et al., 2025). Assumption 1 (Feasibility). The initial state satisfies s1∈safe,1s_1 _safe,1. 3 Safety-Induced Variance and Identification Complexity Safety constraints shape the statistical difficulty of reinforcement learning, not only the set of feasible policies. They can impede exploration, but by restricting behavior they can also remove sources of reward uncertainty and simplify learning inside the feasible region. Under step-wise safety, these two effects are organized by the hidden safe subgraph. We show that its stochastic branching and successor-value differences control the transition variance available to reward learning, while actions outside the graph must be excluded based on cost or successor-viability evidence. This yields tight structural variance bounds together with a complexity for the separate task of safety identification. 3.1 Variance under Step-Wise Safety We first introduce two variance quantities for reward uncertainty under step-wise safety. Maximum safe-policy return variance We measure the return variability available to safe policies by the maximum safe-policy return variance. Write (X)V(X) for the variance of X and (q,f):=∑xq(x)f(x)2−(∑xq(x)f(x))2V(q,f):= _xq(x)f(x)^2-( _xq(x)f(x))^2 for the variance of f under a distribution q. We define: Var⋆:=supπ∈Πsafeπ[∑h=1H(Rh(sh,ah))+(Ph(⋅∣sh,ah),Vh+1π)|s1].Var := _π∈ _safeE^π\! [ _h=1^H \V(R_h(s_h,a_h))+V\! (P_h(· s_h,a_h),V_h+1^π ) \\, |\,s_1 ]. (4) Equation (4) captures two sources of variance. The reward term (Rh(sh,ah))V(R_h(s_h,a_h)) measures noise in the reward observation, while (Ph(⋅∣sh,ah),Vh+1π)V(P_h(· s_h,a_h),V_h+1^π) measures the transition-induced variance in continuation value. Their expected sum equals the variance of the total return under π, so Var⋆Var is the largest total-return variance over safe policies. It is a fixed property of the CMDP instance. Trajectory-based total variance The preceding quantity is uniform over the safe policy class, but it can be conservative for a particular interaction sequence. A complementary view therefore uses the conditional variances actually encountered during interaction. For episode k, let τk _k be the first step at which the selected action lies outside the true safe set, with τk=H+1 _k=H+1 if no such action is selected. We define the trajectory-based total variance as: Σ:=∑k=1K∑h<τk(Rh(shk,ahk))+(Ph(⋅∣shk,ahk),Vh+1⋆).V_ := _k=1^K _h< _k \V(R_h(s_h^k,a_h^k))+V\! (P_h(· s_h^k,a_h^k),V_h+1 ) \. (5) This quantity depends on the learner’s realized trajectories and is therefore algorithm dependent. It captures the local variance at state-action pairs visited before the first unsafe action is selected and measures transition uncertainty using the optimal safe value function. This truncation separates the interaction within the safe subgraph from the additional difficulty of identifying actions outside it. Remark 1. The two quantities capture different aspects of reward-learning uncertainty and neither generally subsumes the other. Similar policy-level and trajectory-level variance characterizations underlie variance-adaptive guarantees in unconstrained RL (Azar et al., 2017; Zanette and Brunskill, 2019; Zhou et al., 2023b; Zhao et al., 2023), and the corresponding quantities can be incomparable (Zhou et al., 2023b). The additional challenge under step-wise safety is that the region supporting these variance quantities is itself unknown, which leads to the separate safety identification complexity studied in Section 3.3. 3.2 Structure of the Safe Subgraph and Transition Variance Both variance measures introduced above are closely tied to the safe subgraph. We next study how the structure of the safe subgraph affects these quantities. In fact, it acts most directly on transition variance, through how often stochastic transitions can occur along a safe path and how large the value differences across their successors can be. We capture these two effects by the branching depth of the safe subgraph and successor-value spans. Let γ=(s1,a1,…,sH,aH,sH+1)γ=(s_1,a_1,…,s_H,a_H,s_H+1) range over directed paths in safeG_safe from (s1,1)(s_1,1) to step H+1H+1. The branching depth is the largest number of stochastic transitions on one such path, i.e., B(safe):=maxγ∑h=1H|supp(Ph(⋅∣sh,ah))|>1B(G_safe):= _γ _h=1^H1\! \|supp(P_h(· s_h,a_h))|>1 \. For a nonempty finite set X and a real-valued function f on X, write spanX(f):=maxx∈Xf(x)−minx∈Xf(x)span_X(f):= _x∈ Xf(x)- _x∈ Xf(x). For a policy π∈Πsafeπ∈ _safe, the successor-value span SπS^π measures the largest difference in continuation values among possible successors of an action selected by π at any reachable vertex. Formally, Sπ:=max(s,h)∈π,h∈[H]spansupp(Ph(⋅∣s,πh(s)))(Vh+1π)S^π:= _ subarrayc(s,h) ^π,\ h∈[H] subarrayspan_supp(P_h(· s, _h(s)))\!(V_h+1^π). Over the same safe paths, define the optimal successor-value span by S⋆:=maxγ,h∈[H]spansupp(Ph(⋅∣sh,ah))(Vh+1⋆)S := _γ,\ h∈[H]span_supp(P_h(· s_h,a_h))\!(V_h+1 ). This quantity measures the largest span of optimal safe continuation values across successors of actions on safe paths. The following result shows how these spans and the branching depth control transition variance. Theorem 1 (Safe-subgraph variance bound). Under Assumption 1, every π∈Πsafeπ∈ _safe satisfies: π[∑h=1H(Ph(⋅∣sh,ah),Vh+1π)|s1]≤14(Sπ)2B(safe).E^π\! [ _h=1^HV\! (P_h(· s_h,a_h),V_h+1^π )\, |\,s_1 ]≤ 14(S^π)^2B(G_safe). (6) Moreover, every realized interaction sequence satisfies ∑k=1K∑h=1τk−1(Ph(⋅∣shk,ahk),Vh+1⋆)≤K4(S⋆)2B(safe) _k=1^K _h=1 _k-1V\! (P_h(· s_h^k,a_h^k),V_h+1 )≤ K4(S )^2B(G_safe). The theorem bounds each safe policy’s transition variance using SπS^π and the trajectory-based transition variance using S⋆S . Small branching depth limits how often transition randomness can affect continuation value, while a small successor-value span limits the contribution of each stochastic transition. The full proof is given in Appendix F.1. Figure 1 shows how changing only the costs can change the safe subgraph, thereby removing or retaining stochastic branches and changing the continuation-value differences across their successors. The following proposition shows that the bound in Equation (6) is tight. In Appendix F.3, we provide the complete analysis and proof. Figure 1: The structure of the safe subgraph reshapes transition variance. All panels share the same reward function and transition kernel and differ only in their costs. Changing only the costs removes the stochastic branch in panel (a) and retains it in panels (b)–(c). Its successors have equal continuation values and zero transition variance in panel (b), but unequal values and positive transition variance in panel (c). With τ=1/2τ=1/2, crossed actions have cost 1>τ1>τ, while all other actions have cost 00. Blue solid elements denote the safe subgraph, gray solid elements denote actions excluded by the cost threshold and their transitions, and red dashed elements denote exclusion because a successor has no safe continuation. Proposition 1. For every n≥1n≥ 1, there exists a family of CMDPs with H=2nH=2n that share the same transition kernel and deterministic rewards and differ only in the cost function c. For every b∈0,…,nb∈\0,…,n\, the family contains an instance such that, for every π∈Πsafeπ∈ _safe, B(safe)=bB(G_safe)=b, Sπ=b>0S^π=1\b>0\, π[∑h=1H(Ph(⋅∣sh,ah),Vh+1π)|s1]=b4E^π\! [ _h=1^HV\! (P_h(· s_h,a_h),V_h+1^π )\, |\,s_1 ]= b4. Hence, Equation (6) holds with equality and Var⋆=b/4Var =b/4. 3.3 Safety Identification Complexity The previous results reveal a potential benefit of safety: removing random branches or successor-value variation can reduce reward uncertainty. However, even a low-variance safe subgraph can still be difficult to identify. Intuitively, a rare non-viable branch can contribute little transition variance and yet require many executions to discover. This creates a distinct safety identification problem. For an unsafe action, we first define a local complexity that captures the number of executions needed to identify it as unsafe. The action can be excluded either directly, when its mean cost exceeds the threshold, or recursively, through a successor state at which every action is unsafe. Formally, for every step h∈[H]h∈[H], state s∈s , and action a∉safe,h(s)a _safe,h(s), we define: κh(s,a):=ch(s,a)−τ−2,ch(s,a)>τ,mins′∈supp(Ph(⋅∣s,a))s′∉safe,h+1κh+1(s′)Ph(s′∣s,a),ch(s,a)≤τ,κh(s):=∑a∉safe,h(s)κh(s,a). _h(s,a):= cases\c_h(s,a)-τ\^-2,&c_h(s,a)>τ,\\[2.84526pt] _ subarraycs (P_h(· s,a))\\ s _safe,h+1 subarray _h+1(s )P_h(s s,a),&c_h(s,a)≤τ, cases _h(s):= _a _safe,h(s) _h(s,a). (7) This definition mirrors the recursive structure of safety. A positive cost gap yields an inverse-squared term. Otherwise, one non-viable successor suffices to exclude the parent action, giving the minimum over such successors, while reaching that successor incurs the factor 1/Ph(s′∣s,a)1/P_h(s s,a). At each state s, κh(s) _h(s) sums complexities of its unsafe actions. Instance-dependent identification complexity The first unsafe action can only be selected after a safe path. Hence its vertex is reachable under some safe policy. This motivates the safety identification complexity, which we define as follows: (ℳ):=∑(s,h)∈⋃π∈Πsafeπκh(s),C(M):= _(s,h)∈ _π∈ _safeV^π _h(s), (8) where we set κH+1(s)=0 _H+1(s)=0 for any state s. We write C for (ℳ)C(M) when the instance is clear from context. Thus C quantifies the difficulty of ruling out unsafe actions at the reachable boundary of the safe subgraph. Unlike the variance quantities, it is a reward-independent instance quantity determined by (P,c,τ,s1)(P,c,τ,s_1). The safety identification complexity also captures an unavoidable statistical cost of eliminating unsafe actions. Even on a simple tree-structured family, any δ-valid elimination rule requires Ω(κh(s,a)log(1/δ)) \! ( _h(s,a) (1/δ) ) expected executions to eliminate an unsafe root action, while for pairwise-disjoint trees these requirements add to Ω(log(1/δ)) \! (C (1/δ) ) expected executions. Thus, the cost-gap and rare-successor effects in κ, together with their accumulation in C, capture genuine safety identification difficulty. The construction and proof are given in Appendix G.2. 4 Safe Variance-Adaptive Exploration In this section, we provide our main algorithm, Safe Variance-Adaptive Exploration (SVAE). Section 3 shows that the safe subgraph can reduce reward uncertainty, while identifying it remains difficult even when the return variance is small. On the reward side, empirical variance can sharpen optimistic exploration, whereas on the cost side, empirical variance alone cannot reliably rule out unsafe actions. An unsafe action can exhibit zero empirical cost variance until a rare high-cost outcome is observed, as shown in Appendix E. SVAE therefore adopts an asymmetric design, combining variance-independent cost lower confidence bounds for safe-subgraph learning with variance-adaptive bonuses for reward exploration. We present SVAE in Algorithm 1. Algorithm 1 Safe Variance-Adaptive Exploration (SVAE) 1: S, A, H, K, s1s_1, τ, and δ 2: Set ι←log(32S2AHK/δ) ← (32S^2AHK/δ) and initialize all empirical statistics 3: for k=1,2,…,Kk=1,2,…,K do 4: Form nhkn_h^k, r^hk r_h^k, c^hk c_h^k, P^hk P_h^k, σ^R,h2,k σ_R,h^2,k, and supp^hk supp_h^k for all (s,a,h)∈×[H](s,a,h) ×A×[H] 5: Set c¯hk c_h^k by (9) for all (s,a,h)∈×[H](s,a,h) ×A×[H] 6: s1k←s1s_1^k← s_1, ^safe,H+1k← V_safe,H+1^k , and VH+1k(⋅)←0V_H+1^k(·)← 0 7: for h=H,H−1,…,1h=H,H-1,…,1 do 8: ^safe,hk(s)←a∈:c¯hk(s,a)≤τ,supp^hk(s,a)⊆^safe,h+1k A_safe,h^k(s)←\a : c_h^k(s,a)≤τ,\ supp_h^k(s,a) V_safe,h+1^k\ for all s∈s 9: ^safe,hk←s∈:^safe,hk(s)≠∅ V_safe,h^k←\s : A_safe,h^k(s)≠ \ ⊳ Safe-subgraph learning 10: Compute bhk(s,a)b_h^k(s,a) by (10) for all (s,a)∈×(s,a) ×A ⊳ Variance-adaptive bonus 11: Qhk(s,a)←minH−h+1,r^hk(s,a)+P^hk(⋅∣s,a)⊤Vh+1k+bhk(s,a)Q_h^k(s,a)← \H-h+1, r_h^k(s,a)+ P_h^k(· s,a) V_h+1^k+b_h^k(s,a)\ for all (s,a)∈×(s,a) ×A 12: for s∈s do 13: πhk(s)∈argmaxa∈^safe,hk(s)Qhk(s,a),^safe,hk(s)≠∅,argmaxa∈Qhk(s,a),otherwise, _h^k(s)∈ cases _a∈ A_safe,h^k(s)Q_h^k(s,a),& A_safe,h^k(s)≠ ,\\ _a Q_h^k(s,a),&otherwise, cases 14: Vhk(s)←Qhk(s,πhk(s))V_h^k(s)← Q_h^k(s, _h^k(s)) 15: end for 16: end for 17: for h=1,2,…,Hh=1,2,…,H do ⊳ Policy execution 18: Play ahk←πhk(shk)a_h^k← _h^k(s_h^k), observe (Rhk,Chk,sh+1k)(R_h^k,C_h^k,s_h+1^k), and update the empirical statistics 19: end for 20: end for Safe-subgraph learning SVAE maintains an optimistic outer approximation of the unknown safe subgraph. Fix a confidence parameter δ∈(0,1)δ∈(0,1) and set ι:=log(32S2AHK/δ) := (32S^2AHK/δ). Let Nhk(s,a)N_h^k(s,a) and Nhk(s,a,s′)N_h^k(s,a,s ) denote, respectively, the numbers of visits to (s,a)(s,a) and transitions from (s,a)(s,a) to s′s at step h before episode k. Write nhk(s,a):=maxNhk(s,a),1n_h^k(s,a):= \N_h^k(s,a),1\. Let r^hk r_h^k, c^hk c_h^k, and P^hk P_h^k denote the corresponding empirical estimates of rhr_h, chc_h, and PhP_h, respectively, with detailed definitions given in Appendix B.1. The observed successor set is supp^hk(s,a):=s′∈:Nhk(s,a,s′)>0 supp_h^k(s,a):=\s :N_h^k(s,a,s )>0\. We then compute the optimistic cost estimates for step h∈[H]h∈[H], state s∈s , and action a∈a as: c¯hk(s,a):=c^hk(s,a)−2ι/nhk(s,a). c_h^k(s,a):= c_h^k(s,a)- 2 /n_h^k(s,a). (9) SVAE constructs the candidate action sets ^safe,hk(s) A_safe,h^k(s) and state sets ^safe,hk V_safe,h^k by applying the backward recursion in Equation (1), with optimistic cost estimates in place of true costs and observed successors in place of the full successor sets. The following lemma shows that this recursion retains all safe actions and states with high probability. Its proof is given in Appendix B.4. Lemma 1 (Optimism of the candidate sets). With probability at least 1−δ/81-δ/8, it holds safe,h(s)⊆^safe,hk(s)A_safe,h(s) A_safe,h^k(s) and safe,h⊆^safe,hkV_safe,h V_safe,h^k for every episode k∈[K]k∈[K], step h∈[H]h∈[H], and state s∈s . Variance-adaptive planning SVAE then performs optimistic value iteration on the estimated safe subgraph using variance-adaptive bonuses. For each step h and state-action pair (s,a)(s,a), define the empirical reward variance σ^R,h2,k(s,a):=1nhk(s,a)∑ℓ<k(Rhℓ−r^hk(s,a))2(shℓ,ahℓ)=(s,a) σ_R,h^2,k(s,a):= 1n_h^k(s,a) _ <k(R_h - r_h^k(s,a))^21\(s_h ,a_h )=(s,a)\, where ⋅1\·\ denotes the indicator function. For any function V:→ℝV:S , write P^hkV(s,a):=∑s′∈P^hk(s′∣s,a)V(s′) P_h^kV(s,a):= _s P_h^k(s s,a)V(s ). Let QhkQ_h^k and VhkV_h^k denote the state-action value and state-value estimates computed in Algorithm 1. SVAE uses the following empirical-Bernstein exploration bonus: bhk(s,a)=4(P^hk(⋅∣s,a),Vh+1k)ιnhk(s,a)+2σ^R,h2,k(s,a)ιnhk(s,a)+16(H−h)+5ιnhk(s,a). splitb_h^k(s,a)=&4 V( P_h^k(· s,a),V_h+1^k)\, n_h^k(s,a)+2 σ_R,h^2,k(s,a)\, n_h^k(s,a)+ \16(H-h)+5\ n_h^k(s,a). split (10) The first two terms account for transition and reward uncertainty through the empirical variances of estimated next-state values and reward observations, respectively. The last term provides a finite-sample correction even when the empirical variances vanish. Using these bonuses, SVAE computes the state-action value estimates QhkQ_h^k by optimistic Bellman updates in the same backward pass that constructs the estimated safe subgraph. At each state s, it chooses πhk(s) _h^k(s) to maximize Qhk(s,⋅)Q_h^k(s,·) over ^safe,hk(s) A_safe,h^k(s) when this set is nonempty, and over A otherwise, with Vhk(s)=Qhk(s,πhk(s))V_h^k(s)=Q_h^k(s, _h^k(s)). SVAE then executes the resulting policy πkπ^k for one episode and uses the observed rewards, costs, and successor states to update the empirical statistics for the next episode. Remark 2. Variance-adaptive RL uses empirical next-state value variance, and in some cases reward variance, to sharpen optimism in unconstrained MDPs (Azar et al., 2017; Zanette and Brunskill, 2019; Zhou et al., 2023b). In SVAE, the continuation values entering the transition-variance term are obtained by planning over candidate safe action sets learned online. Hence, the bonus adapts to the return uncertainty under the evolving safety-induced graph structure. 5 Learning Guarantees In this section, we establish an instance-dependent regret bound and cumulative step-wise violation bounds for SVAE. We show how the variance and identification complexity introduced in Section 3 govern its learning guarantees. Throughout, we use Ω and Θ to hide universal constants. The notation ~ O additionally hides polylogarithmic factors in S,A,H,KS,A,H,K, and 1/δ1/δ. 5.1 Regret and Constraint Violation We first present the cumulative regret attained by Algorithm 1 over K episodes. Theorem 2 (Regret bound). Suppose Assumption 1 holds. For any integer K≥1K≥ 1 and confidence parameter δ∈(0,1)δ∈(0,1), SVAE (Algorithm 1) attains: ℛ(K)≤~(SAHminΣ,KVar⋆+SAH3minK,+S2AH2),R(K)≤ O\! ( SAH \! \V_ ,KVar \+S AH^3 \K,C\+S^2AH^2 ), with probability at least 1−δ1-δ. Theorem 2 separates the variance-dependent contribution to regret from the cost of safety identification, and gives polylogarithmic regret on fixed instances with Var⋆=0Var =0. By taking the minimum of ΣV_ and KVar⋆KVar , the bound refines the purely instance-dependent guarantee and can yield a smaller variance-dependent term when the learner encounters low-variance trajectories. When τ=1τ=1, our setting degenerates to unconstrained RL, and the bound recovers the variance-dependent term of MVP-V (Zhou et al., 2023b) in the time-inhomogeneous setting. Theorem 2 also yields ~(SAH3K) O(S AH^3K) regret in the worst case, matching the leading regret of OMDPD (Zhu et al., 2025). For uniformly bounded C and sufficiently large K, the leading regret term becomes ~(SAH3K) O( SAH^3K), which matches the corresponding minimax rate (Zhang et al., 2025). The proof is deferred to Appendix C. For deterministic rewards, combining Theorem 2 with Theorem 1 and the universal bound Var⋆≤H2/4Var ≤ H^2/4 yields the following graph-dependent corollary. Corollary 1 (Graph-dependent regret). Under the conditions of Theorem 2, if the rewards are deterministic, then with probability at least 1−δ1-δ, the reward regret of SVAE satisfies ℛ(K)≤~(SAHKminH2,(S⋆)2B(safe)+SAH3minK,+S2AH2)R(K)≤ O( SAHK \H^2,(S )^2B(G_safe)\+S AH^3 \K,C\+S^2AH^2). Corollary 1 bounds the variance-dependent regret term through the branching depth of the safe subgraph and the successor-value span of the optimal safe value function. In particular, with deterministic rewards, this term vanishes when S⋆=0S =0, even if the transitions are stochastic. Constraint violation We then bound the cumulative step-wise constraint violation of SVAE. In addition to a general bound, we can obtain a gap-dependent bound under the following assumption. The gap in the assumption controls how easily costs exceeding the threshold can be identified. Similar gap-dependent assumptions have been studied in safe RL and bandits (Chen et al., 2022; Gangrade et al., 2024). Assumption 2 (Positive cost gap). There exists Δc>0 _c>0 such that ch(s,a)−τ≥Δc_h(s,a)-τ≥ _c for every h∈[H]h∈[H] and (s,a)∈×(s,a) ×A with ch(s,a)>τc_h(s,a)>τ. We now give the cumulative step-wise constraint violation bounds of our algorithm. Theorem 3 (Cumulative constraint violation). Under Assumption 1, with probability at least 1−δ1-δ, SVAE satisfies Viol(K)≤~(HSAK+S2AH2)Viol(K)≤ O(H SAK+S^2AH^2). If Assumption 2 also holds, then on the same event, Viol(K)≤~(SAH/Δc+S2AH2)Viol(K)≤ O(SAH/ _c+S^2AH^2). Theorem 3 gives a ~(K) O( K) cumulative constraint violation in general and a violation bound that is polylogarithmic in K for a fixed positive cost gap. For state-only costs, pooling cost observations across actions and steps gives ~(SKH+S2AH2) O( SKH+S^2AH^2) violation or ~(S/Δc+S2AH2) O(S/ _c+S^2AH^2), which recovers the rates of SUCBVI (Xiong et al., 2023). If every state admits a safe action at every step, the bound becomes ~(HSAK) O(H SAK), matching the bound of LSVI-AE (Wei et al., 2024) in the tabular setting. Under Assumption 2, if every unsafe action at a vertex reachable under a safe policy has cost exceeding τ, we then have ≤SAH/Δc2C≤ SAH/ _c^2, as proved in Appendix C.7. 5.2 Regret Lower Bounds We next establish a regret lower bound that captures the dependence on both reward variance and safety identification complexity. Theorem 4 (Lower bound). Let S≥8S≥ 8, A≥2A≥ 2, H≥64H≥ 64, and K≥SAK≥ SA be integers. Fix v∈[0,H/128]v∈[0,H/128] and Γ∈[16(A−1),SAH/64] ∈[16(A-1),SAH/64] satisfying minK,Γ≥16SA/H \K, \≥ 16SA/H. For any learning algorithm, there exists a CMDP ℳM with S states, A actions, and horizon H satisfying Assumption 1, such that Var⋆(ℳ)∈[3v/4,v]Var (M)∈[3v/4,v], (ℳ)=Θ(Γ)C(M)= ( ), and the algorithm’s expected regret after K episodes satisfies ℳ[ℛ(K)]=Ω(SAHKv+SAHminK,Γ)E_M[R(K)]= ( SAHKv+ SAH \K, \). Moreover, Σ∈[3Kv/4,Kv]V_ ∈[3Kv/4,Kv] for every realized interaction sequence on ℳM. Theorem 4 demonstrates that both maximum safe-policy return variance and safety identification complexity contribute to the difficulty of learning. In particular, zero safe-policy return variance does not eliminate the regret incurred by identifying safe actions. The proof uses two families of CMDPs with the prescribed variance and identification complexity. One requires distinguishing actions with similar expected rewards, while the other requires identifying a hidden safe action. Taking the larger of the two lower bounds yields the stated result. The full proof is provided in Appendix G.1. References Achiam et al. (2017) J. Achiam, D. Held, A. Tamar, and P. Abbeel Constrained policy optimization. In Proceedings of the 34th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 70, p. 22–31. Cited by: Appendix A, §1. Alshiekh et al. (2018) M. Alshiekh, R. Bloem, R. Ehlers, B. Könighofer, S. Niekum, and U. Topcu Safe reinforcement learning via shielding. Proceedings of the AAAI Conference on Artificial Intelligence 32 (1), p. 2669–2678. Cited by: Appendix A. Altman (1999) E. Altman Constrained Markov decision processes. Stochastic Modeling, Vol. 7, Chapman & Hall/CRC, Boca Raton. Cited by: §1. Amani et al. (2021) S. Amani, C. Thrampoulidis, and L. Yang Safe reinforcement learning with linear function approximation. In Proceedings of the 38th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 139, p. 243–253. Cited by: §1.1, §2. Azar et al. (2017) M. G. Azar, I. Osband, and R. Munos Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 70, p. 263–272. Cited by: Appendix A, Remark 1, Remark 2. Berkenkamp et al. (2017) F. Berkenkamp, M. Turchetta, A. P. Schoellig, and A. Krause Safe model-based reinforcement learning with stability guarantees. In Advances in Neural Information Processing Systems, Vol. 30, p. 908–918. Cited by: Appendix A. Bourel et al. (2020) H. Bourel, O. Maillard, and M. S. Talebi Tightening exploration in upper confidence reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 119, p. 1056–1066. Cited by: §1.1. Bura et al. (2022) A. Bura, A. HasanzadeZonuzy, D. Kalathil, S. Shakkottai, and J. Chamberland DOPE: doubly optimistic and pessimistic exploration for safe reinforcement learning. In Advances in Neural Information Processing Systems, Vol. 35, p. 1047–1059. Cited by: §1.1, §1, §1. Chen et al. (2025) S. Chen, R. Zhou, Z. Zhang, M. Fazel, and S. S. Du Sharp gap-dependent variance-aware regret bounds for tabular MDPs. In Advances in Neural Information Processing Systems, Vol. 38, p. 124328–124364. Cited by: §1.1, §1. Chen et al. (2022) T. Chen, A. Gangrade, and V. Saligrama Strategies for safe multi-armed bandits with logarithmic regret and risk. In International Conference on Machine Learning, p. 3123–3148. Cited by: §5.1. Dann et al. (2021) C. Dann, T. V. Marinov, M. Mohri, and J. Zimmert Beyond value-function gaps: improved instance-dependent regret bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, Vol. 34, p. 1–12. Cited by: §1. Ding et al. (2021) D. Ding, X. Wei, Z. Yang, Z. Wang, and M. R. Jovanović Provably efficient safe exploration via primal-dual policy optimization. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 130, p. 3304–3312. Cited by: §1.1. Ding et al. (2025) D. Ding, K. Zhang, J. Duan, T. Başar, and M. R. Jovanović Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs. Journal of Machine Learning Research 26 (256), p. 1–76. Cited by: Appendix A. Du and Chen (2022) Y. Du and W. Chen Branching reinforcement learning. In Proceedings of the 39th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 162, p. 5494–5530. Cited by: Appendix A. Efroni et al. (2020) Y. Efroni, S. Mannor, and M. Pirotta Exploration-exploitation in constrained MDPs. arXiv preprint arXiv:2003.02189. External Links: Link Cited by: §1.1. Freedman (1975) D. A. Freedman On tail probabilities for martingales. The Annals of Probability 3 (1), p. 100–118. Cited by: §C.1. Ganai et al. (2023) M. Ganai, Z. Gong, C. Yu, S. Herbert, and S. Gao Iterative reachability estimation for safe reinforcement learning. In Advances in Neural Information Processing Systems, Vol. 36, p. 69764–69797. Cited by: Appendix A. Gangrade et al. (2024) A. Gangrade, T. Chen, and V. Saligrama Safe linear bandits over unknown polytopes. In Proceedings of Thirty Seventh Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 247, p. 1755–1795. Cited by: §5.1. Ghosh et al. (2022) A. Ghosh, X. Zhou, and N. Shroff Provably efficient model-free constrained RL with linear function approximation. In Advances in Neural Information Processing Systems, Vol. 35, p. 13303–13315. Cited by: §1.1. Howard et al. (2020) S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon Time-uniform Chernoff bounds via nonnegative supermartingales. Probability Surveys 17, p. 257–317. Cited by: §C.1. Huang et al. (2023) R. Huang, J. Yang, and Y. Liang Safe exploration incurs nearly no additional sample complexity for reward-free RL. In International Conference on Learning Representations, Cited by: Appendix A. Jiang and Ye (2024) J. Jiang and Y. Ye Achieving instance-dependent sample complexity for constrained Markov decision process. arXiv preprint arXiv:2402.16324. External Links: Link Cited by: Appendix A, §1.1. Jin et al. (2020) C. Jin, T. Jin, H. Luo, S. Sra, and T. Yu Learning adversarial Markov decision processes with bandit feedback and unknown transition. In Proceedings of the 37th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 119, p. 4860–4869. Cited by: §2. Kitamura et al. (2025) T. Kitamura, A. Ghosh, T. Kozuno, W. Kumagai, K. Kasaura, K. Hoshino, Y. Hosoe, and Y. Matsuo Provably efficient RL under episode-wise safety in constrained MDPs with linear function approximation. In Advances in Neural Information Processing Systems, Vol. 38, p. 52632–52681. Cited by: §1.1. Li et al. (2023) D. Li, R. Huang, C. Shen, and J. Yang Near-optimal conservative exploration in reinforcement learning under episode-wise constraints. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 19527–19564. Cited by: Appendix A. Li et al. (2026) M. Li, T. Tsuchiya, and K. Yamanishi Data- and variance-dependent regret bounds for online tabular MDPs. In International Conference on Machine Learning, Cited by: Appendix A. Liu et al. (2021) T. Liu, R. Zhou, D. Kalathil, P. R. Kumar, and C. Tian Learning policies with zero or bounded constraint violation for constrained MDPs. In Advances in Neural Information Processing Systems, Vol. 34, p. 17183–17193. Cited by: §1.1, §1. Maurer and Pontil (2009) A. Maurer and M. Pontil Empirical Bernstein bounds and sample variance penalization. In Proceedings of the 22nd Annual Conference on Learning Theory, Cited by: §B.3. Miryoosefi and Jin (2022) S. Miryoosefi and C. Jin A simple reward-free approach to constrained reinforcement learning. In Proceedings of the 39th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 162, p. 15666–15698. Cited by: Appendix A, §1. Mukherjee et al. (2022) S. Mukherjee, J. P. Hanna, and R. D. Nowak ReVar: strengthening policy evaluation via reduced variance sampling. In Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, Proceedings of Machine Learning Research, Vol. 180, p. 1413–1422. Cited by: Appendix A. Mukherjee et al. (2024) S. Mukherjee, J. P. Hanna, and R. D. Nowak SaVeR: optimal data collection strategy for safe policy evaluation in tabular MDP. In Proceedings of the 41st International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 235, p. 36531–36576. Cited by: Appendix A. Qadri et al. (2025) M. Qadri, G. Swamy, J. Francis, M. Kaess, and A. Bajcsy Your learned constraint is secretly a backward reachable tube. Reinforcement Learning Journal 6, p. 478–492. Cited by: Appendix A. Roknilamouki et al. (2025) A. Roknilamouki, A. Ghosh, M. Shi, F. Nourzad, E. Ekici, and N. Shroff Provably efficient RL for linear MDPs under instantaneous safety constraints in non-convex feature spaces. In Proceedings of the 42nd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 267, p. 51957–51995. Cited by: §1.1, §2. Shi et al. (2023) M. Shi, Y. Liang, and N. Shroff A near-optimal algorithm for safe reinforcement learning under instantaneous hard constraints. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 31243–31268. Cited by: §1.1, §1, §1, §2, §2, §2. Stradi et al. (2025a) F. E. Stradi, M. Castiglioni, A. Marchesi, and N. Gatti Learning adversarial MDPs with stochastic hard constraints. In Proceedings of the 42nd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 267, p. 56920–56951. Cited by: §1. Stradi et al. (2025b) F. E. Stradi, M. Castiglioni, A. Marchesi, and N. Gatti Optimal strong regret and violation in constrained MDPs via policy optimization. In International Conference on Learning Representations, Cited by: §H.1, §1.1. Stradi et al. (2024) F. E. Stradi, J. Germano, G. Genalti, M. Castiglioni, A. Marchesi, and N. Gatti Online learning in CMDPs: handling stochastic and adversarial constraints. In Proceedings of the 41st International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 235, p. 46692–46721. Cited by: §1.1. Stradi et al. (2025c) F. E. Stradi, A. Lunghi, M. Castiglioni, A. Marchesi, and N. Gatti Policy optimization for CMDPs with bandit feedback: learning stochastic and adversarial constraints. In Forty-Second International Conference on Machine Learning, Cited by: Appendix A. Talebi and Maillard (2018) M. S. Talebi and O. Maillard Variance-aware regret bounds for undiscounted reinforcement learning in MDPs. In Proceedings of Algorithmic Learning Theory, Proceedings of Machine Learning Research, Vol. 83, p. 770–805. Cited by: Appendix A, §1. Tessler et al. (2019) C. Tessler, D. J. Mankowitz, and S. Mannor Reward constrained policy optimization. In International Conference on Learning Representations, Cited by: Appendix A. Turchetta et al. (2016) M. Turchetta, F. Berkenkamp, and A. Krause Safe exploration in finite Markov decision processes with Gaussian processes. In Advances in Neural Information Processing Systems, Vol. 29, p. 4312–4320. Cited by: §1.1. Vaswani et al. (2022) S. Vaswani, L. F. Yang, and C. Szepesvári Near-optimal sample complexity bounds for constrained MDPs. In Advances in Neural Information Processing Systems, Vol. 35, p. 3110–3122. Cited by: Appendix A. Wachi and Sui (2020) A. Wachi and Y. Sui Safe reinforcement learning in constrained Markov decision processes. In Proceedings of the 37th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 119, p. 9797–9806. Cited by: §1.1. Wei et al. (2022) H. Wei, X. Liu, and L. Ying Triple-Q: a model-free algorithm for constrained reinforcement learning with sublinear regret and zero constraint violation. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 151, p. 3274–3307. Cited by: §1.1. Wei et al. (2024) H. Wei, X. Liu, and L. Ying Safe reinforcement learning with instantaneous constraints: the role of aggressive exploration. Proceedings of the AAAI Conference on Artificial Intelligence 38 (19), p. 21708–21716. Cited by: §1.1, §1, §2, §5.1. Wei et al. (2026) Y. Wei, X. Li, and L. F. Yang Near-optimal sample complexity bounds for constrained average-reward MDPs. In International Conference on Learning Representations, Cited by: Appendix A. Xiong et al. (2023) N. Xiong, Y. Du, and L. Huang Provably safe reinforcement learning with step-wise violation constraints. In Advances in Neural Information Processing Systems, Vol. 36, p. 54341–54353. Cited by: Appendix A, §H.1, §1.1, §1, §1, §2, §2, §5.1. Yu et al. (2025) K. Yu, D. Lee, W. Overman, and D. Lee Improved regret bound for safe reinforcement learning via tighter cost pessimism and reward optimism. Reinforcement Learning Journal 6, p. 493–546. Cited by: §1.1, §1. Zamir et al. (2026) G. Zamir, M. Zurek, and Y. Chen Optimal variance-dependent regret bounds for infinite-horizon MDPs. In Proceedings of Thirty Ninth Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 336, p. 7016–7061. Cited by: §1.1, §1. Zanette and Brunskill (2019) A. Zanette and E. Brunskill Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In Proceedings of the 36th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 97, p. 7304–7312. Cited by: §1, Remark 1, Remark 2. Zhang et al. (2025) Z. Zhang, Y. Chen, J. Lee, and S. S. Du Settling the sample complexity of online reinforcement learning. Journal of the ACM 72 (3), p. 1–63. Cited by: §5.1. Zhao et al. (2023) H. Zhao, J. He, D. Zhou, T. Zhang, and Q. Gu Variance-dependent regret bounds for linear bandits and reinforcement learning: adaptivity and computational efficiency. In Proceedings of Thirty Sixth Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 195, p. 4977–5020. Cited by: §1.1, §1, Remark 1. Zhou et al. (2023a) R. Zhou, R. Wang, and S. S. Du Horizon-free and variance-dependent reinforcement learning for latent Markov decision processes. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 42698–42723. Cited by: Appendix A. Zhou et al. (2023b) R. Zhou, Z. Zhang, and S. S. Du Sharp variance-dependent bounds in reinforcement learning: best of both worlds in stochastic and deterministic environments. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 42878–42914. Cited by: §B.5, §B.5, §H.1, §1.1, §1, §5.1, Remark 1, Remark 2. Zhu et al. (2025) J. Zhu, K. Yu, D. Lee, X. Liu, and H. Wei An optimistic algorithm for online CMDPS with anytime adversarial constraints. In Proceedings of the 42nd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 267, p. 80347–80372. Cited by: §5.1. Appendix Contents Appendix A Additional Related Work Constrained policy optimization Policy optimization methods approach constrained learning through different policy updates and penalty constructions. Achiam et al. [2017] use trust-region updates in Constrained Policy Optimization, while Tessler et al. [2019] use an adaptive penalty in Reward Constrained Policy Optimization to guide learning toward constraint satisfaction. For discounted CMDPs, Ding et al. [2025] analyze the convergence and sample complexity of natural policy gradient primal–dual methods with tabular and function-approximation parametrizations. In online CMDPs with adversarial losses and constraints, Stradi et al. [2025c] provide the first policy optimization primal-dual method to attain best-of-both-worlds results. Safe exploration and policy evaluation Safety during data collection is distinct from feasibility of the policy returned after exploration. Miryoosefi and Jin [2022] reduce constrained RL and approachability to reward-free RL oracles without requiring safe exploration. Huang et al. [2023] instead use a known safe baseline to satisfy an expected cumulative-cost budget in every exploration episode with high probability, while Xiong et al. [2023] study reward-free exploration with cumulative step-wise violation control. For conservative exploration, Li et al. [2023] maintain an episode-wise performance threshold with high probability using a known baseline policy or one learned from suitable offline data. For policy evaluation, Mukherjee et al. [2022] use reward-variance estimates to guide sampling in tree-structured MDPs. Mukherjee et al. [2024] impose a cumulative safety constraint relative to a known default policy and, under their tractability assumptions, bound the mean squared error of SaVeR. In these evaluation problems, the goal is to reduce estimation error for a fixed target policy, rather than learn which safe policy to execute. Safe control Control-theoretic and formal methods reason about safety through the future consequences of an action. Berkenkamp et al. [2017] combine learned dynamics with Lyapunov analysis to expand a region of attraction while maintaining stability. Alshiekh et al. [2018] use a shield to restrict or correct actions according to a temporal-logic specification. Reachability-based methods characterize states from which a violation can still be avoided. Ganai et al. [2023] combine reachability estimation with policy optimization, while Qadri et al. [2025] show that inverse constraint learning can recover a dynamics-dependent backward reachable tube rather than the underlying failure set. These approaches study safety through stability, specifications, or reachability, rather than through the variance-dependent regret of an online learner. They provide a related view of why local cost feasibility alone need not ensure safe continuation. Variance-dependent reinforcement learning Variance has been used both to sharpen worst-case regret bounds and to obtain guarantees that adapt to a particular instance. Azar et al. [2017] use empirical next-state value variance in finite-horizon exploration bonuses, while Talebi and Maillard [2018] establish variance-aware regret bounds for undiscounted MDPs. Zhou et al. [2023a] study variance-dependent learning in latent MDPs whose contexts are revealed in hindsight. With known transitions, Li et al. [2026] obtain data-dependent regret bounds for adversarial losses and variance-dependent bounds for stochastic losses. A different trajectory model appears in branching RL, where an episode generates a tree rather than a single path and the analysis requires a corresponding law of total variance [Du and Chen, 2022]. That model differs from the stochastic transitions along a single trajectory considered here. Thus, both the variance quantity and its role in a guarantee depend on the underlying MDP and observation model. Instance-dependent sample complexity Sample-complexity bounds for CMDPs capture several sources of difficulty beyond return variance. With generative-model access, Vaswani et al. [2022] distinguish relaxed and strict feasibility in discounted CMDPs and quantify the role of the Slater constant in learning a near-optimal policy with no constraint violation. Wei et al. [2026] study constrained average-reward MDPs under the same sampling model, with bounds involving bias span, transient time, and a feasibility margin. Jiang and Ye [2024] instead identify nonzero basic variables and supporting constraints that determine an optimal occupancy measure of the CMDP linear program. These analyses concern feasibility margins, long-run dynamics, or the variables and constraints that characterize an optimal occupancy measure. Our safety identification complexity measures the difficulty of ruling out actions outside the true safe set using local cost observations and evidence that a successor admits no safe continuation. Appendix B Preliminaries We first specify the empirical estimates and implementation of SVAE. We then fix an optimal safe policy, define the confidence events, and prove the candidate-set inclusions and optimism used in the analysis. Fix K≥1K≥ 1 and δ∈(0,1)δ∈(0,1). Recall that ι=log(32S2AHK/δ) = (32S^2AHK/δ), and set LK:=2+logKL_K:=2+ K. Throughout the appendix, (⋅)O(·) hides universal multiplicative constants. We write Phf(s,a):=∑s′∈Ph(s′∣s,a)f(s′)P_hf(s,a):= _s P_h(s s,a)f(s ). A state s is viable at step h if s∈safe,hs _safe,h. B.1 Empirical Estimates The estimates used in episode k∈[K]k∈[K] of Algorithm 1 use only observations from episodes ℓ<k <k. For s,s′∈s,s , a∈a , and h∈[H]h∈[H], define Nhk(s,a) N_h^k(s,a) :=∑ℓ<k(shℓ,ahℓ)=(s,a), := _ <k1\(s_h ,a_h )=(s,a)\, Nhk(s,a,s′) N_h^k(s,a,s ) :=∑ℓ<k(shℓ,ahℓ,sh+1ℓ)=(s,a,s′). := _ <k1\(s_h ,a_h ,s_h+1 )=(s,a,s )\. Write nhk(s,a):=maxNhk(s,a),1n_h^k(s,a):= \N_h^k(s,a),1\. The empirical reward and cost estimates are r^hk(s,a) r_h^k(s,a) :=1nhk(s,a)∑ℓ<kRhℓ(shℓ,ahℓ)=(s,a), := 1n_h^k(s,a) _ <kR_h 1\(s_h ,a_h )=(s,a)\, (B.1) c^hk(s,a) c_h^k(s,a) :=1nhk(s,a)∑ℓ<kChℓ(shℓ,ahℓ)=(s,a). := 1n_h^k(s,a) _ <kC_h 1\(s_h ,a_h )=(s,a)\. For Nhk(s,a)≥1N_h^k(s,a)≥ 1, the empirical transition probabilities are P^hk(s′∣s,a):=Nhk(s,a,s′)Nhk(s,a). P_h^k(s s,a):= N_h^k(s,a,s )N_h^k(s,a). (B.2) At zero count, let P^hk(⋅∣s,a) P_h^k(· s,a) be an arbitrary fixed probability distribution on S. The empirical reward variance and observed successor set from Section 4 are σ^R,h2,k(s,a) σ_R,h^2,k(s,a) :=1nhk(s,a)∑ℓ<k(Rhℓ−r^hk(s,a))2(shℓ,ahℓ)=(s,a), := 1n_h^k(s,a) _ <k (R_h - r_h^k(s,a) )^21\(s_h ,a_h )=(s,a)\, supp^hk(s,a) supp_h^k(s,a) :=s′∈:Nhk(s,a,s′)>0. :=\s :N_h^k(s,a,s )>0\. Thus, at zero count, r^hk=c^hk=σ^R,h2,k=0 r_h^k= c_h^k= σ_R,h^2,k=0 and the observed successor set is empty. The initialization of P^hk P_h^k does not add elements to the observed successor set. The linear term in (10) then gives Qhk(s,a)=H−h+1Q_h^k(s,a)=H-h+1. Before episode k, SVAE computes its candidate sets, bonuses, values, and policy from these estimates. Fix a deterministic rule for breaking ties in each maximization. At step h of the dynamic program, ^safe,h+1k V_safe,h+1^k and Vh+1kV_h+1^k are already available, so the candidate sets and Bellman updates can be computed in a single backward pass. The candidate sets, πkπ^k, QhkQ_h^k, and VhkV_h^k remain fixed during execution. New observations update the statistics for episode k+1k+1. The estimates can be maintained using visit counts, transition counts, and sums of rewards, costs, and squared rewards. In particular, σ^R,h2,k(s,a)=1nhk(s,a)∑ℓ<k(Rhℓ)2(shℓ,ahℓ)=(s,a)−(r^hk(s,a))2. σ_R,h^2,k(s,a)= 1n_h^k(s,a) _ <k(R_h )^21\(s_h ,a_h )=(s,a)\- ( r_h^k(s,a) )^2. Each observation updates these stored quantities in constant time. With dense transition arrays, checking observed successors and computing transition means and variances take (S)O(S) operations for each (s,a,h)(s,a,h), while all action maximizations take (SAH)O(SAH) operations. Each episode therefore requires (S2AH)O(S^2AH) arithmetic operations, including its H observation updates. The total is (KS2AH)O(KS^2AH) operations with (S2AH)O(S^2AH) memory. Let ℱhkF_h^k be the σ-field generated by the history just before the reward, cost, and next state at step h of episode k are observed. Thus shks_h^k and ahka_h^k are ℱhkF_h^k-measurable, while πkπ^k, QhkQ_h^k, and VhkV_h^k are fixed given ℱ1kF_1^k. Conditional on ℱhkF_h^k, RhkR_h^k and ChkC_h^k have means rh(shk,ahk)r_h(s_h^k,a_h^k) and ch(shk,ahk)c_h(s_h^k,a_h^k), respectively, and the next state has distribution Ph(⋅∣shk,ahk)P_h(· s_h^k,a_h^k). We order these histories by episode and step, and let ℱH+1kF_H+1^k include the final observations of episode k. B.2 Optimal Safe Policy The Bellman comparisons below use a policy that is optimal at every viable state. The next lemma supplies such a policy. We take it as π⋆π in Section 2 and retain this choice in V⋆V , ΣV_ , and S⋆S . Lemma B.1. Under Assumption 1, there exists a deterministic policy π⋆∈Πsafeπ ∈ _safe that selects a safe action at every viable state. With VH+1⋆≡0V_H+1 ≡ 0, it satisfies Vh⋆(s)=maxa∈safe,h(s)rh(s,a)+PhVh+1⋆(s,a)V_h (s)= _a _safe,h(s) \r_h(s,a)+P_hV_h+1 (s,a) \ (B.3) for every h∈[H]h∈[H] and s∈safe,hs _safe,h. For every policy π∈Ππ∈ that selects safe actions at all viable states, Vhπ(s)≤Vh⋆(s)V_h^π(s)≤ V_h (s) for all h∈[H]h∈[H] and s∈safe,hs _safe,h. In particular, π⋆π maximizes V1π(s1)V_1^π(s_1) over π∈Πsafeπ∈ _safe. Proof. Set VH+1⋆=0V_H+1 =0 and define Vh⋆V_h recursively by the right-hand side of (B.3). Because the maximizing set is finite and nonempty at every viable state, choose one maximizer as πh⋆(s) _h (s), and define the policy arbitrarily at states outside safe,hV_safe,h. Every selected safe action has all successors in safe,h+1V_safe,h+1. Thus the recursion determines the value of π⋆π at every viable state, independently of its actions elsewhere. Assumption 1 therefore gives π⋆∈Πsafeπ ∈ _safe. Let π select a safe action at every viable state. If Vh+1π≤Vh+1⋆V_h+1^π≤ V_h+1 on safe,h+1V_safe,h+1, then Vhπ(s) V_h^π(s) =rh(s,πh(s))+PhVh+1π(s,πh(s)) =r_h(s, _h(s))+P_hV_h+1^π(s, _h(s)) ≤rh(s,πh(s))+PhVh+1⋆(s,πh(s))≤Vh⋆(s). ≤ r_h(s, _h(s))+P_hV_h+1 (s, _h(s))≤ V_h (s). Backward induction proves the comparison. For any π∈Πsafeπ∈ _safe, choose an arbitrary safe action at each viable state that π does not reach from s1s_1. This completes π to a policy selecting safe actions at all viable states without changing its trajectory distribution or value from s1s_1. It follows that V1π(s1)≤V1⋆(s1)V_1^π(s_1)≤ V_1 (s_1) for every π∈Πsafeπ∈ _safe. ∎ B.3 Confidence Events The cost and support bounds below preserve the safe action sets. The reward and transition bounds control optimism and Bellman residuals. All intersections below range over s,s′∈s,s , a∈a , h∈[H]h∈[H], and k∈[K]k∈[K]. Define ℰc _c :=⋂s,a,h,k|c^hk(s,a)−ch(s,a)|≤2ιnhk(s,a), := _s,a,h,k \| c_h^k(s,a)-c_h(s,a)|≤ 2 n_h^k(s,a) \, ℰP _P :=⋂s,s′,a,h,kNhk(s,a)≥1|P^hk(s′∣s,a)−Ph(s′∣s,a)|≤2Ph(s′∣s,a)ιnhk(s,a)+Ph(s′∣s,a)>0ιnhk(s,a), := _s,s ,a,h,k \ aligned &1\N_h^k(s,a)≥ 1\| P_h^k(s s,a)-P_h(s s,a)|\\ & ≤ 2P_h(s s,a) n_h^k(s,a)+ 1\P_h(s s,a)>0\ n_h^k(s,a) aligned \, ℰsupp _supp :=⋂s,a,h,ksupp^hk(s,a)⊆supp(Ph(⋅∣s,a)). := _s,a,h,k \ supp_h^k(s,a) (P_h(· s,a)) \. For N:=Nhk(s,a)≥2N:=N_h^k(s,a)≥ 2, consider the three empirical Bernstein bounds |r^hk(s,a)−rh(s,a)| | r_h^k(s,a)-r_h(s,a)| ≤2σ^R,h2,k(s,a)ιN+5ιN, ≤ 2 σ_R,h^2,k(s,a) N+ 5 N, (B.4) |(P^hk−Ph)Vh+1⋆(s,a)| |( P_h^k-P_h)V_h+1 (s,a)| ≤2(P^hk(⋅∣s,a),Vh+1⋆)ιN+5(H−h)ιN, ≤ 2 V( P_h^k(· s,a),V_h+1 ) N+ 5(H-h) N, (B.5) σ^R,h2,k(s,a) σ_R,h^2,k(s,a) ≤2(Rh(s,a))+2ιN. ≤ 2V(R_h(s,a))+ 2 N. (B.6) Define ℰEBE_EB as the event that (B.4)–(B.6) hold for every s,a,h,ks,a,h,k with Nhk(s,a)≥2N_h^k(s,a)≥ 2. Set ℰcs:=ℰc∩ℰsuppE_cs:=E_c _supp and ℰest:=ℰcs∩ℰP∩ℰEBE_est:=E_cs _P _EB. Lemma B.2. The events satisfy ℙ(ℰcs)≥1−δ/8P(E_cs)≥ 1-δ/8 and ℙ(ℰest)≥1−9δ/16P(E_est)≥ 1-9δ/16. Proof. For each (s,a,h)(s,a,h), generate an infinite sequence of independent copies of its reward, cost, and next-state observations. Revealing the next unused copy at each visit gives the same interaction distribution as the observation model. We apply concentration bounds to the first n copies for every deterministic n∈[K]n∈[K], then take a union bound over these counts before substituting the realized count Nhk(s,a)N_h^k(s,a). For the cost and transition estimates, fix (s,a,h)(s,a,h) and s′∈s . Write CiC_i for the iith cost sample and let ZiZ_i indicate that the iith next state is s′s . With p=Ph(s′∣s,a)p=P_h(s s,a), Hoeffding’s and Bernstein’s inequalities give, for each n∈[K]n∈[K], ℙ(|1n∑i=1nCi−ch(s,a)|>2ιn) \! ( | 1n _i=1^nC_i-c_h(s,a) |> 2 n ) ≤2e−ι, ≤ 2e^- , ℙ(|1n∑i=1nZi−p|>2pιn+2ι3n) \! ( | 1n _i=1^nZ_i-p |> 2p n+ 2 3n ) ≤2e−ι. ≤ 2e^- . If p=0p=0, all ZiZ_i are zero almost surely. At zero count, the cost bound holds because ch(s,a)≤1≤2ιc_h(s,a)≤ 1≤ 2 . Every observed successor belongs to the true support almost surely, so ℙ(ℰsupp)=1P(E_supp)=1. For the reward and value estimates, consider independent, identically distributed X1,…,Xn∈[0,B]X_1,…,X_n∈[0,B]. Let X¯n X_n and v^n=n−1∑i(Xi−X¯n)2 v_n=n^-1 _i(X_i- X_n)^2 be the sample mean and variance. Applying Maurer and Pontil [2009, Theorem 4] to Xi/BX_i/B and 1−Xi/B1-X_i/B gives, for B>0B>0 and n≥2n≥ 2, |X¯n−[X1]|≤2v^nιn−1+7Bι3(n−1)≤2v^nιn+5Bιn| X_n-E[X_1]|≤ 2 v_n n-1+ 7B 3(n-1)≤ 2 v_n n+ 5B n with failure probability at most 4e−ι4e^- . The case B=0B=0 is immediate. Apply this bound to the reward samples with B=1B=1 and to Vh+1⋆V_h+1 evaluated at the sampled next states with B=H−hB=H-h. The latter function is fixed by Lemma B.1. For the reward variance, write RiR_i for the samples. The sample variance is at most the average squared deviation from rh(s,a)r_h(s,a). Bernstein’s inequality therefore gives, with failure probability at most e−ιe^- , v^n v_n ≤1n∑i=1n(Ri−rh(s,a))2 ≤ 1n _i=1^n(R_i-r_h(s,a))^2 ≤(Rh(s,a))+2(Rh(s,a))ιn+2ι3n≤2(Rh(s,a))+2ιn. (R_h(s,a))+ 2V(R_h(s,a)) n+ 2 3n≤ 2V(R_h(s,a))+ 2 n. Here (Ri−rh(s,a))2∈[0,1](R_i-r_h(s,a))^2∈[0,1] has mean (Rh(s,a))V(R_h(s,a)) and variance at most that mean. For each fixed triple and sample count, the three Bernstein bounds thus have total failure probability at most (4+4+1)e−ι=9e−ι(4+4+1)e^- =9e^- . Taking a union bound over the deterministic sample counts, states, actions, and steps gives ℙ(ℰcsc) (E_cs^c) ≤2SAHKe−ι≤δ/8, ≤ 2SAHKe^- ≤δ/8, ℙ(ℰestc) (E_est^c) ≤[2(S+1)+9]SAHKe−ι≤13δ/32≤9δ/16.∎ ≤ [2(S+1)+9 ]SAHKe^- ≤ 13δ/32≤ 9δ/16. B.4 Proof of Lemma 1 Proof. We establish both inclusions on ℰcsE_cs, including the state-set inclusion at step H+1H+1. On ℰcsE_cs, the cost bound gives c¯hk(s,a)≤ch(s,a) c_h^k(s,a)≤ c_h(s,a) for every s,a,h,ks,a,h,k. Fix k and argue backward from safe,H+1=^safe,H+1k=V_safe,H+1= V_safe,H+1^k=S. If a∈safe,h(s)a _safe,h(s), then c¯hk(s,a)≤τ c_h^k(s,a)≤τ and the induction hypothesis gives supp^hk(s,a)⊆supp(Ph(⋅∣s,a))⊆safe,h+1⊆^safe,h+1k. supp_h^k(s,a) (P_h(· s,a)) _safe,h+1 V_safe,h+1^k. Thus a∈^safe,hk(s)a∈ A_safe,h^k(s). A nonempty true safe action set therefore implies a nonempty candidate set, completing the induction. By Lemma B.2, ℙ(ℰcs)≥1−δ/8P(E_cs)≥ 1-δ/8, which proves the claim. ∎ B.5 Optimism The following consequence of Zhou et al. [2023b, Lemma 22] handles the dependence of the transition bonus on the optimistic value vector. For real vectors p,zp,z on the same finite index set, write pz:=∑ipizipz:= _ip_iz_i. Lemma B.3. Let p be a distribution on [S][S], B≥0B≥ 0, x>0x>0, and v,w∈[0,B]Sv,w∈[0,B]^S with v≤wv≤ w on supp(p)supp(p). Then pw+max4(p,w)x,16Bx≥pv+2(p,v)x+8Bx.pw+ \4 V(p,w)x,16Bx\≥ pv+2 V(p,v)x+8Bx. (B.7) Proof. For B>0B>0, apply Zhou et al. [2023b, Lemma 22] on supp(p)supp(p) with c1=4c_1=4, c2=16c_2=16, and ι/n=x /n=x. Its monotonicity property applies because c12=c2c_1^2=c_2. Combining it with max4a,16b≥2a+8b \4a,16b\≥ 2a+8b for a,b≥0a,b≥ 0 proves the claim. For B=0B=0, both sides are zero. ∎ Combining candidate-set preservation with the monotone backup gives optimism on the viable states. Lemma B.4 (Optimism). On ℰestE_est, Vhk(s)≥Vh⋆(s)V_h^k(s)≥ V_h (s) for every k∈[K]k∈[K], h∈[H+1]h∈[H+1], and s∈safe,hs _safe,h. Proof. Fix k and use backward induction from h=H+1h=H+1. For a viable state s, let a⋆=πh⋆(s)a = _h (s). By the inclusions proved in Appendix B.4, a⋆a is a candidate. Write N:=Nhk(s,a⋆)N:=N_h^k(s,a ) and suppress (s,a⋆,h,k)(s,a ,h,k) from the remaining empirical quantities. If N≤1N≤ 1, the linear bonus gives Qhk(s,a⋆)=H−h+1≥Vh⋆(s)Q_h^k(s,a )=H-h+1≥ V_h (s). If N≥2N≥ 2, set x=ι/Nx= /N and q=P^hk(⋅∣s,a⋆)q= P_h^k(· s,a ). Since supp(q)⊆safe,h+1supp(q) _safe,h+1, the induction hypothesis holds there. Lemma B.3 and (B.5) yield qVh+1k+4(q,Vh+1k)x+16(H−h)x qV_h+1^k+4 V(q,V_h+1^k)x+16(H-h)x ≥qVh+1⋆+2(q,Vh+1⋆)x+8(H−h)x ≥ qV_h+1 +2 V(q,V_h+1 )x+8(H-h)x ≥PhVh+1⋆. ≥ P_hV_h+1 . Also, (B.4) gives r^hk+2σ^R,h2,kx+5x≥rh r_h^k+2 σ_R,h^2,kx+5x≥ r_h. The unclipped backup is therefore at least rh+PhVh+1⋆=Vh⋆(s)r_h+P_hV_h+1 =V_h (s). Clipping at H−h+1H-h+1 and maximizing over candidates preserve this inequality. ∎ Appendix C Regret Analysis We prove Theorem 2 under Assumption 1. The analysis separates each episode at its first action outside the true safe set. Before that action, an auxiliary safe policy relates the Bellman residuals to the safe-policy variance. We bound the number of episodes containing such an action in terms of C and use a general residual bound for their remaining steps. C.1 Martingale Bounds We use the following consequence of Freedman’s inequality [Freedman, 1975, Howard et al., 2020]. Lemma C.1 (Martingale concentration). Let T≥1T≥ 1 be an integer, let (ℋt)t=0T(H_t)_t=0^T be a filtration, and let (ξt)t=1T( _t)_t=1^T be martingale differences with respect to this filtration. Suppose |ξt|≤b| _t|≤ b almost surely for every t∈[T]t∈[T], where b≥0b≥ 0 is fixed. Then, for every η∈(0,1)η∈(0,1), with probability at least 1−η1-η, ∑t=1Tξt≤((∑t=1T[ξt2∣ℋt−1])logT+1η+blogT+1η). _t=1^T _t \! ( ( _t=1^TE[ _t^2 _t-1] ) T+1η+b T+1η ). For the following consequences, let B≥0B≥ 0 be fixed and, for each t∈[T]t∈[T], let YtY_t be ℋtH_t-measurable with 0≤Yt≤B0≤ Y_t≤ B almost surely. Set μt:=[Yt∣ℋt−1] _t:=E[Y_t _t-1]. For every η∈(0,1)η∈(0,1), each of the following inequalities holds with probability at least 1−η1-η: ∑t=1TYt _t=1^TY_t ≤2∑t=1Tμt+(BlogT+1η), ≤ 2 _t=1^T _t+O\! (B T+1η ), (C.1) ∑t=1Tμt _t=1^T _t ≤2∑t=1TYt+(BlogT+1η). ≤ 2 _t=1^TY_t+O\! (B T+1η ). (C.2) Proof. The case b=0b=0 is immediate. Otherwise, apply Freedman’s inequality at variance thresholds b2,2b2,…,2⌈log2T⌉b2b^2,2b^2,…,2 _2T b^2, with failure probability η/(T+1)η/(T+1) at each threshold. The conditional variance sum is at most Tb2Tb^2, so these at most T+1T+1 thresholds cover all its values. A union bound yields the first inequality, with the lowest interval absorbed by the term blog((T+1)/η)b ((T+1)/η). For the first consequence, apply it to ξt=Yt−μt _t=Y_t- _t and use [ξt2∣ℋt−1]≤[Yt2∣ℋt−1]≤BμtE[ _t^2 _t-1] [Y_t^2 _t-1]≤ B _t. Young’s inequality absorbs the resulting term (B(∑tμt)log((T+1)/η))O( B( _t _t) ((T+1)/η)). Applying the same argument to ξt=μt−Yt _t= _t-Y_t proves the second consequence. ∎ For the applications below, t≤KHt≤ KH and η=δ/16η=δ/16 imply log((t+1)/η)≤log(32KH/δ)≤2ι ((t+1)/η)≤ (32KH/δ)≤ 2 . C.2 Safety Identification We use κh(s,a) _h(s,a) and C from Section 3.3 to bound the number of selections of unsafe actions in the candidate sets and, in turn, the number of episodes containing an unsafe action. The recursion for κh _h ends at an action with a positive cost gap. Otherwise, it selects a non-viable successor and sums the sample requirements for ruling out all actions there. The next lemma expands this recursion into paths ending at positive-gap actions. Each leaf contributes its sample requirement Δℓ−2 _ ^-2 divided by its path probability qℓq_ . Lemma C.2 (Witness-tree representation). Fix h∈[H]h∈[H], s∈s , and a∉safe,h(s)a _safe,h(s). There is a finite witness tree rooted at (s,a,h)(s,a,h) with a nonempty leaf set ℒL. For each leaf ℓ , let qℓ∈(0,1]q_ ∈(0,1] be the product of the transition probabilities on its path and Δℓ∈(0,1] _ ∈(0,1] the cost gap of its terminal action. Then κh(s,a)=∑ℓ∈ℒ1qℓΔℓ2. _h(s,a)= _ 1q_ _ ^2. (C.3) For SVAE, each execution of (s,a,h)(s,a,h) as a candidate action is assigned to the leaf determined by its episode policy, before the transitions on that path are observed. Across the K episodes, let NℓN_ count the executions assigned to leaf ℓ for which every transition on that path occurs. On ℰcE_c, the following bound holds for all ℓ∈ℒ : Nℓ≤2+8ιΔℓ2≤10ιΔℓ2.N_ ≤ 2+ 8 _ ^2≤ 10 _ ^2. (C.4) Proof. We prove (C.3) by backward induction. For the direct-cost branch, take one leaf with qℓ=1q_ =1 and Δℓ=ch(s,a)−τ _ =c_h(s,a)-τ. Then κh(s,a)=1qℓΔℓ2 _h(s,a)= 1q_ _ ^2. Suppose now that the recursive branch applies. The minimizing set in (7) is nonempty because a∉safe,h(s)a _safe,h(s) and ch(s,a)≤τc_h(s,a)≤τ. Choose a minimizing successor y. Since y∉safe,h+1y _safe,h+1, safe,h+1(y)=∅A_safe,h+1(y)= . By the induction hypothesis, each κh+1(y,b) _h+1(y,b), b∈b , has a finite witness representation. Taking the union of these representations and multiplying every path probability by Ph(y∣s,a)P_h(y s,a) gives κh(s,a)=κh+1(y)Ph(y∣s,a)=∑ℓ∈ℒ1qℓΔℓ2. _h(s,a)= _h+1(y)P_h(y s,a)= _ 1q_ _ ^2. The construction terminates after at most H−h+1H-h+1 layers. Each internal action has the selected successor y, whose children are indexed by all actions at y. A fixed episode policy selects the child πh+1k(y) _h+1^k(y) at each such successor and hence determines a unique leaf before any transition on the path is observed. The product of these transition probabilities is qℓq_ . Fix ℓ∈ℒ and write c=τ+Δℓc=τ+ _ for the mean cost of its terminal action. After n≥1n≥ 1 visits, its lower confidence bound c¯ c satisfies c¯≥c−22ι/n c≥ c-2 2 /n on ℰcE_c. Thus the terminal action is permanently removed by the cost test once n>8ι/Δℓ2n>8 / _ ^2. Before it is removed, it can be executed at most 1+8ι/Δℓ21+8 / _ ^2 times. It remains to account for paths whose transitions have not all been observed. After the terminal action is permanently rejected, a selected path to it can be completed at most once more. The first such completion records every transition on the path. In any later episode selecting the same leaf, suppose the root action is a candidate. Its recorded successor must then have a nonempty candidate set, so the algorithm selects a candidate action there. Repeating this argument along the recorded path would make the permanently rejected terminal action a candidate, a contradiction. Recorded supports only grow, and the terminal cost bound holds at all later sample counts. Adding this possible completion to the visits before removal proves (C.4). ∎ We now convert completed leaf paths into a bound on root executions. Weighting a completed path by 1/qℓ1/q_ makes its conditional mean equal to the indicator that the root is executed as a candidate. Lemma C.3. For SVAE, there exists an event ℰcertE_cert with ℙ(ℰcert)≥1−δ/16P(E_cert)≥ 1-δ/16 such that, on ℰest∩ℰcertE_est _cert, the following bound holds simultaneously for all h∈[H]h∈[H], s∈s , and a∉safe,h(s)a _safe,h(s): ∑k=1Kshk=s,ahk=a,a∈^safe,hk(s)≤(ικh(s,a)). _k=1^K1\! \s_h^k=s,\ a_h^k=a,\ a∈ A_safe,h^k(s) \ ( _h(s,a)). (C.5) Proof. Fix (s,a,h)(s,a,h) and the representation in Lemma C.2. Let IkI_k denote the indicator in (C.5). If Ik=1I_k=1, let ℓk _k be the leaf determined by πkπ^k, and let ZkZ_k indicate that all transitions along its path occur. Set Xk=Zk/qℓkX_k=Z_k/q_ _k when Ik=1I_k=1 and Xk=0X_k=0 otherwise. Since πkπ^k is ℱ1kF_1^k-measurable, ℓk _k and qℓkq_ _k are ℱhkF_h^k-measurable. The Markov property and (C.3) give [Xk∣ℱhk]=IkE[X_k _h^k]=I_k, and 0≤Xk≤κh(s,a)0≤ X_k≤ _h(s,a), where the second bound also uses Δℓk≤1 _ _k≤ 1. On ℰcE_c, (C.4) gives ∑k=1KXk=∑ℓ∈ℒNℓqℓ≤10ι∑ℓ∈ℒ1qℓΔℓ2=10ικh(s,a). _k=1^KX_k= _ N_ q_ ≤ 10 _ 1q_ _ ^2=10 _h(s,a). Apply (C.2) in episode order, conditioning the kkth increment on ℱhkF_h^k. The variable XkX_k is known by the end of episode k, before ℱhk+1F_h^k+1 for k<Kk<K. For the final increment, use the terminal history ℱH+1KF_H+1^K. Take B=κh(s,a)B= _h(s,a) and failure probability δ/(16SAH)δ/(16SAH). Let ℰcertE_cert be the intersection of the events supplied by these applications over all unsafe (s,a,h)(s,a,h). A union bound gives ℙ(ℰcert)≥1−δ/16P(E_cert)≥ 1-δ/16. On ℰcertE_cert, ∑k=1KIk≤2∑k=1KXk+(κh(s,a)log16SAH(K+1)δ) _k=1^KI_k≤ 2 _k=1^KX_k+O\! ( _h(s,a) 16SAH(K+1)δ ) for every such triple. Since log(16SAH(K+1)/δ)≤2ι (16SAH(K+1)/δ)≤ 2 , the bound on ∑kXk _kX_k above yields, on ℰest∩ℰcertE_est _cert, ∑kIk≤(ικh(s,a)) _kI_k ( _h(s,a)), as required. ∎ We now apply this count to the first unsafe action in each episode. For episode k, define τk:=minh∈[H]:ahk∉safe,h(shk),min∅:=H+1. _k:= \h∈[H]:a_h^k _safe,h(s_h^k) \, :=H+1. The event τk≤h\ _k≤ h\ belongs to ℱhkF_h^k, so τk _k is a stopping time for the within-episode history. All actions before τk _k are safe, so the state at step τk _k is reachable under a safe policy. The bound on unsafe candidate selections therefore controls the number of episodes with τk≤H _k≤ H. Proposition C.1. On ℰest∩ℰcertE_est _cert, ∑k=1Kτk≤H≤(ιminK,). _k=1^K1\ _k≤ H\ \! ( \! \K,C \ ). (C.6) Proof. If τk≤H _k≤ H, the preceding safe actions reach (sτk,τk)(s_ _k^k, _k) with positive probability. Complete those actions with arbitrary safe actions at other viable states. The resulting policy is safe, so this vertex is included in the definition of C. Its true safe action set is nonempty and, by the inclusions proved in Appendix B.4, so is its candidate set. Thus aτkka_ _k^k is an unsafe candidate action. Apply Lemma C.3 to each unsafe action at a vertex reachable under a safe policy and sum the bounds. Each episode with τk≤H _k≤ H contributes one such execution, giving ∑k=1Kτk≤H≤(ι∑(s,h)∈⋃π∈Πsafeπκh(s))=(ι). _k=1^K1\ _k≤ H\ \! ( _(s,h)∈ _π∈ _safeV^π _h(s) )=O( ). (C.7) The count is also at most K. Combining these bounds and using ι≥1 ≥ 1 proves the claim. ∎ C.3 Bellman Residual Bounds We first control the transition estimation error, then derive the two Bellman residual bounds used before and after the first unsafe action. The next lemma converts coordinatewise transition bounds into mean and variance bounds for every bounded value vector, including the data-dependent value estimates used below. Lemma C.4. Let B≥0B≥ 0, x>0x>0, and let p,qp,q be distributions on [S][S] satisfying |qi−pi|≤2pix+pi>0x(i∈[S]).|q_i-p_i|≤ 2p_ix+1\p_i>0\x (i∈[S]). (C.8) Then, for every z∈[0,B]Sz∈[0,B]^S, |(q−p)z| |(q-p)z| ≤2S(p,z)x+3SBx, ≤ 2 SV(p,z)x+3SBx, (C.9) (q,z) (q,z) ≤2(p,z)+4SB2x. ≤ 2V(p,z)+4SB^2x. (C.10) Proof. Let di=zi−pzd_i=z_i-pz. Since (q−p)=0(q-p)1=0 and |di|≤B|d_i|≤ B, |(q−p)z| |(q-p)z| ≤2x∑ipi|di|+x∑i:pi>0|di| ≤ 2x _i p_i|d_i|+x _i:p_i>0|d_i| ≤2S(p,z)x+SBx, ≤ 2SV(p,z)x+SBx, which implies (C.9). Also, (q,z) (q,z) ≤∑i=1Sqidi2 ≤ _i=1^Sq_id_i^2 ≤(p,z)+2x∑ipidi2+x∑i:pi>0di2 (p,z)+ 2x _i p_id_i^2+x _i:p_i>0d_i^2 ≤(p,z)+B2S(p,z)x+SB2x≤2(p,z)+2SB2x. (p,z)+B 2SV(p,z)x+SB^2x≤ 2V(p,z)+2SB^2x. The last two inequalities use Cauchy–Schwarz and Young’s inequality. This proves (C.10). ∎ Before the first unsafe action, we bound the Bellman residual using V⋆V . For the remaining steps, we use a bound that applies to every action. For h∈[H+1]h∈[H+1], define Dhk(s):=Vhk(s)−Vh⋆(s)D_h^k(s):=V_h^k(s)-V_h (s) for s∈safe,hs _safe,h and Dhk(s):=0D_h^k(s):=0 otherwise. On ℰestE_est, Lemma B.4 gives 0≤Dhk≤H−h+10≤ D_h^k≤ H-h+1. Fix a sufficiently large universal constant C0C_0. Define βhk(s,a):= _h^k(s,a):= C0[(Rh(s,a))+(Ph(⋅∣s,a),Vh+1⋆)ιnhk(s,a) C_0 [ \V(R_h(s,a))+V(P_h(· s,a),V_h+1 )\ n_h^k(s,a) +S(Ph(⋅∣s,a),Dh+1k)ιnhk(s,a)+SHιnhk(s,a)], + SV(P_h(· s,a),D_h+1^k) n_h^k(s,a)+ SH n_h^k(s,a) ], (C.11) and β~hk(s,a):=C0[(Rh(s,a))+S(Ph(⋅∣s,a),Vh+1k)ιnhk(s,a)+SHιnhk(s,a)]. β_h^k(s,a):=C_0 [ \V(R_h(s,a))+SV(P_h(· s,a),V_h+1^k)\ n_h^k(s,a)+ SH n_h^k(s,a) ]. (C.12) The same C0C_0 is used in both definitions. The three terms in βhk _h^k account for the reward and optimal-value variances, the next-state variance of Dh+1kD_h+1^k, and the linear concentration terms. The bound β~hk β_h^k uses Vh+1kV_h+1^k directly. Lemma C.5 (Bellman residual bounds). On ℰestE_est, for every k∈[K]k∈[K], h∈[H]h∈[H], and s∈s , the following two bounds hold. For every a∈safe,h(s)a _safe,h(s), Qhk(s,a)−rh(s,a)−PhVh+1k(s,a)≤βhk(s,a).Q_h^k(s,a)-r_h(s,a)-P_hV_h+1^k(s,a)≤ _h^k(s,a). (C.13) For every a∈a , Qhk(s,a)−rh(s,a)−PhVh+1k(s,a)≤β~hk(s,a).Q_h^k(s,a)-r_h(s,a)-P_hV_h+1^k(s,a)≤ β_h^k(s,a). (C.14) Proof. Fix (s,a,h,k)(s,a,h,k) and suppress these indices when unambiguous. Let N=Nhk(s,a)N=N_h^k(s,a) and B=H−hB=H-h. If N≤1N≤ 1, the residual is at most H by clipping and nonnegative rewards. The linear term in either bound covers this case. Suppose N≥2N≥ 2, and set x=ι/Nx= /N, p=Ph(⋅∣s,a)p=P_h(· s,a), and q=P^hk(⋅∣s,a)q= P_h^k(· s,a). The reward terms satisfy 2σ^R,h2,kx+5x+|r^hk−rh| 2 σ_R,h^2,kx+5x+| r_h^k-r_h| ≤4σ^R,h2,kx+10x ≤ 4 σ_R,h^2,kx+10x ≤((Rh(s,a))x+x) \! ( V(R_h(s,a))x+x ) (C.15) by (B.4) and (B.6). For a safe action a∈safe,h(s)a _safe,h(s), write V=Vh+1⋆V=V_h+1 and D=Dh+1kD=D_h+1^k. On the true support, Vh+1k=V+DV_h+1^k=V+D and V,D∈[0,B]V,D∈[0,B]. The empirical support is contained in the true support. Clipping gives Qhk−rh−pVh+1k≤bhk+(r^hk−rh)+(q−p)V+(q−p)D.Q_h^k-r_h-pV_h+1^k≤ b_h^k+( r_h^k-r_h)+(q-p)V+(q-p)D. (C.16) By (C.10), for z=V,Dz=V,D, (q,z)x≤2(p,z)x+2SBx V(q,z)x≤ 2V(p,z)x+2 S\,Bx. Using (q,V+D)≤2(q,V)+2(q,D)V(q,V+D)≤ 2V(q,V)+2V(q,D), we obtain 4(q,V+D)x+16Bx+|(q−p)V|+|(q−p)D| 4 V(q,V+D)x+16Bx+|(q-p)V|+|(q-p)D| ≤(42+2)(q,V)x+42(q,D)x+2S(p,D)x+(21+3S)Bx ≤(4 2+2) V(q,V)x+4 2 V(q,D)x+2 SV(p,D)x+(21+3S)Bx ≤((p,V)x+S(p,D)x+SBx). \! ( V(p,V)x+ SV(p,D)x+SBx ). (C.17) The first inequality uses (B.5) for the fixed function V and (C.9) for D. The second uses the two variance comparisons above. Combining (C.16), (C.15), and (C.17) proves (C.13). Now let a be arbitrary and write V=Vh+1kV=V_h+1^k. Lemma C.4 applies directly to this data-dependent function and gives 4(q,V)x+16Bx+|(q−p)V|≤(S(p,V)x+SBx).4 V(q,V)x+16Bx+|(q-p)V| \! ( SV(p,V)x+SBx ). Together with (C.15) and the clipped backup, this proves (C.14). A sufficiently large C0C_0 makes both residual bounds hold. ∎ C.4 Regret Decomposition At viable states, we replace each unsafe action of πkπ^k by the corresponding action of π⋆π . This gives a safe policy that agrees with πkπ^k before the first unsafe action and allows us to use the safe-policy variance. For h∈[H]h∈[H] and s∈safe,hs _safe,h, define π¯hk(s):=πhk(s),πhk(s)∈safe,h(s),πh⋆(s),πhk(s)∉safe,h(s), π_h^k(s):= cases _h^k(s),& _h^k(s) _safe,h(s),\\ _h (s),& _h^k(s) _safe,h(s), cases (C.18) with arbitrary actions at states outside safe,hV_safe,h. For h∈[H+1]h∈[H+1], define Ehk(s):=Vhk(s)−Vhπ¯k(s)E_h^k(s):=V_h^k(s)-V_h π^k(s) for s∈safe,hs _safe,h and Ehk(s):=0E_h^k(s):=0 otherwise. Thus DhkD_h^k compares with the optimal safe value, whereas EhkE_h^k compares with the value of π¯k π^k. For every h∈[H]h∈[H], define the Bellman residual at the executed pair fhk:=Vhk(shk)−rh(shk,ahk)−PhVh+1k(shk,ahk).f_h^k:=V_h^k(s_h^k)-r_h(s_h^k,a_h^k)-P_hV_h+1^k(s_h^k,a_h^k). Lemma C.6. For every k∈[K]k∈[K], the policy π¯k π^k is ℱ1kF_1^k-measurable and belongs to Πsafe _safe. Couple πkπ^k and π¯k π^k using the same transition randomness. Their states then agree through step τk _k, and their actions agree for all h∈[H]h∈[H] with h<τkh< _k. For every k∈[K]k∈[K] and h∈[H]h∈[H] with h<τkh< _k, Dhk(shk)−PhDh+1k(shk,ahk) D_h^k(s_h^k)-P_hD_h+1^k(s_h^k,a_h^k) ≤fhk, ≤ f_h^k, (C.19) Ehk(shk)−PhEh+1k(shk,ahk) E_h^k(s_h^k)-P_hE_h+1^k(s_h^k,a_h^k) =fhk. =f_h^k. On ℰestE_est, 0≤Dhk(s)≤Ehk(s)≤H−h+10≤ D_h^k(s)≤ E_h^k(s)≤ H-h+1 for every k∈[K]k∈[K], h∈[H+1]h∈[H+1], and s∈safe,hs _safe,h. Proof. At every viable state, both cases in (C.18) select an action in safe,h(s)A_safe,h(s). The support condition therefore makes π¯k π^k safe, and its definition makes it ℱ1kF_1^k-measurable. For h<τkh< _k, its action agrees with the executed action, so the coupled trajectories agree through the state at step τk _k. Applying (B.3) to the safe action ahka_h^k gives the inequality for DhkD_h^k in (C.19). The Bellman equation for π¯k π^k gives the equality for EhkE_h^k. On ℰestE_est, Lemmas B.4 and B.1 give Vhk≥Vh⋆≥Vhπ¯kV_h^k≥ V_h ≥ V_h π^k on safe,hV_safe,h. Clipping and nonnegative rewards give the upper bound. ∎ Define BK B_K :=∑k=1K∑h<τkminβhk(shk,ahk),H, := _k=1^K _h< _k \ _h^k(s_h^k,a_h^k),H\, B~K B_K :=∑k=1K∑h=τkHminβ~hk(shk,ahk),H. := _k=1^K _h= _k^H \ β_h^k(s_h^k,a_h^k),H\. The second inner sum is empty when τk=H+1 _k=H+1. To pass from expected residuals to these realized sums, define the episode contribution Yk:=∑h<τkminβhk(shk,ahk),H+∑h=τkHminβ~hk(shk,ahk),H,0≤Yk≤H2.Y_k:= _h< _k \ _h^k(s_h^k,a_h^k),H\+ _h= _k^H \ β_h^k(s_h^k,a_h^k),H\, 0≤ Y_k≤ H^2. Proposition C.2. On ℰestE_est, the reward regret satisfies ℛ(K)≤∑k=1K[Yk∣ℱ1k]R(K)≤ _k=1^KE[Y_k _1^k]. Proof. Fix the history at the start of episode k. The Bellman equations for πkπ^k, with VH+1k=VH+1πk=0V_H+1^k=V_H+1^π^k=0, give V1k(s1)−V1πk(s1)=[∑h=1Hfhk|ℱ1k].V_1^k(s_1)-V_1^π^k(s_1)=E\! [ _h=1^Hf_h^k\, |\,F_1^k ]. (C.20) If the episode’s estimates satisfy the inequalities defining ℰestE_est, Lemma C.5 bounds the residual at every state and action. Hence, for every continuation trajectory, ∑hfhk≤Yk _hf_h^k≤ Y_k: use βhk _h^k before τk _k, β~hk β_h^k from τk _k onward, and fhk≤Hf_h^k≤ H throughout. On ℰestE_est, optimism therefore yields V1⋆(s1)−V1πk(s1)≤V1k(s1)−V1πk(s1)≤[Yk∣ℱ1k].V_1 (s_1)-V_1^π^k(s_1)≤ V_1^k(s_1)-V_1^π^k(s_1) [Y_k _1^k]. Summing over k proves the result. ∎ C.5 Variance Bounds Proposition C.2 reduces regret to conditional expectations of residual sums. We first control the visit-count and variance terms in these sums, then collect the concentration bounds that relate them to their conditional expectations. We write ∑k,h _k,h for ∑k=1K∑h=1H _k=1^K _h=1^H; a restriction such as h<τkh< _k is applied within each episode. The reward and optimal-value variances are fixed for each state, action, and step, whereas the value-error variances can change between episodes. The next lemma gives visit-count bounds for both types of weights. Lemma C.7 (Visit-count sums). Fix (s,a,h)(s,a,h) and enumerate its visits during the K episodes. Set nj:=maxj−1,1n_j:= \j-1,1\, the visit count before visit j. For any subset J of these visit indices, write m:=|J|m:=|J|. Then ∑j∈Jnj−1/2≤2m _j∈ Jn_j^-1/2≤ 2 m and ∑j∈Jnj−1≤LK _j∈ Jn_j^-1≤ L_K. Consequently, for any nonnegative weights vh(s,a)v_h(s,a) fixed across episodes and any nonnegative weights zhk(s,a)z_h^k(s,a), the following bounds hold for every realized interaction sequence: ∑k,h<τkvh(shk,ahk)nhk(shk,ahk) _k,h< _k v_h(s_h^k,a_h^k)n_h^k(s_h^k,a_h^k) ≤2SAH∑k,h<τkvh(shk,ahk), ≤ 2 SAH _k,h< _kv_h(s_h^k,a_h^k), ∑k,h<τkzhk(shk,ahk)nhk(shk,ahk) _k,h< _k z_h^k(s_h^k,a_h^k)n_h^k(s_h^k,a_h^k) ≤SAHLK∑k,h<τkzhk(shk,ahk), ≤ SAHL_K _k,h< _kz_h^k(s_h^k,a_h^k), ∑k,h<τk1nhk(shk,ahk) _k,h< _k 1n_h^k(s_h^k,a_h^k) ≤SAHLK. ≤ SAHL_K. The same bounds hold with h≥τkh≥ _k. Proof. Both reciprocal sequences are nonincreasing, so the sum over a subset of size m is maximized by the first m visits. For m≥2m≥ 2, 2+∑q=2m−1q−1/2≤2+∫1m−1x−1/2dx=2m−1≤2m.2+ _q=2^m-1q^-1/2≤ 2+ _1^m-1x^-1/2\,dx=2 m-1≤ 2 m. Similarly, m≤Km≤ K gives 2+∑q=2m−1q−1≤2+logK=LK2+ _q=2^m-1q^-1≤ 2+ K=L_K. The case m≤1m≤ 1 is immediate. For the fixed weights vh(s,a)v_h(s,a), first apply the bound 2m2 m at each (s,a,h)(s,a,h), and then apply Cauchy–Schwarz over the SAHSAH choices. For the varying weights, apply Cauchy–Schwarz to all visited terms and use ∑k,h<τk1/nhk(shk,ahk)≤SAHLK _k,h< _k1/n_h^k(s_h^k,a_h^k)≤ SAHL_K. This proves all three bounds and also applies to h≥τkh≥ _k. ∎ After summing the visit-count factors, we need bounds on the next-state variances of DkD^k and EkE^k. The next lemma applies to bounded nonnegative functions. Telescoping their squares before τk _k leaves a drift term and a boundary term at τk _k. We will apply it to the positive parts of DkD^k and EkE^k. Lemma C.8. For each k∈[K]k∈[K], let ghk:→[0,H]g_h^k:S→[0,H], h∈[H+1]h∈[H+1], be ℱ1kF_1^k-measurable functions. Assume gH+1k≡0g_H+1^k≡ 0 and ghk(s)=0g_h^k(s)=0 outside safe,hV_safe,h. Let uhku_h^k, k∈[K]k∈[K] and h∈[H]h∈[H], be random variables. Suppose that, almost surely, for every k∈[K]k∈[K] and h∈[H]h∈[H] with h<τkh< _k, 0≤uhk≤H0≤ u_h^k≤ H and ghk(shk)−Phgh+1k(shk,ahk)≤uhk.g_h^k(s_h^k)-P_hg_h+1^k(s_h^k,a_h^k)≤ u_h^k. Then, for every η∈(0,1)η∈(0,1), with probability at least 1−η1-η, ∑k,h<τk(Ph(⋅∣shk,ahk),gh+1k)≤(H∑k,h<τkuhk+H2∑k=1Kτk≤H+H2logKH+1η). _k,h< _kV(P_h(· s_h^k,a_h^k),g_h+1^k) \! (H _k,h< _ku_h^k+H^2 _k=1^K1\ _k≤ H\+H^2 KH+1η ). (C.21) Proof. Set Ihk=h<τkI_h^k=1\h< _k\ and qhk=Phgh+1k(shk,ahk)q_h^k=P_hg_h+1^k(s_h^k,a_h^k). The indicator IhkI_h^k is measurable after the step-h action is chosen and before the successor is generated. In episode and step order, define the martingale differences ξhk:=IhkPh[(gh+1k)2](shk,ahk)−(gh+1k(sh+1k))2. _h^k:=I_h^k \P_h[(g_h+1^k)^2](s_h^k,a_h^k)-(g_h+1^k(s_h+1^k))^2 \. Within episode k, telescoping gives ∑h<τk(gh+1k(sh+1k))2−(qhk)2 _h< _k \(g_h+1^k(s_h+1^k))^2-(q_h^k)^2 \ =∑h<τk(ghk(shk))2−(qhk)2−(g1k(s1))2+(gτk(sτk))2 = _h< _k \(g_h^k(s_h^k))^2-(q_h^k)^2 \-(g_1^k(s_1))^2+(g_ _k^k(s_ _k^k))^2 ≤2H∑h<τkuhk+H2τk≤H. ≤ 2H _h< _ku_h^k+H^21\ _k≤ H\. Indeed, (ghk)2−(qhk)2≤2H[ghk−qhk]+≤2Huhk(g_h^k)^2-(q_h^k)^2≤ 2H[g_h^k-q_h^k]_+≤ 2Hu_h^k. The terminal square is zero when τk=H+1 _k=H+1 and at most H2H^2 otherwise. When τk=1 _k=1, both sums are empty and the two boundary squares cancel. Let Zg:=∑k,h<τk(Ph(⋅∣shk,ahk),gh+1k).Z_g:= _k,h< _kV(P_h(· s_h^k,a_h^k),g_h+1^k). Adding the martingale differences to the deterministic sum above gives Zg≤∑k,hξhk+2H∑k,h<τkuhk+H2∑kτk≤H.Z_g≤ _k,h _h^k+2H _k,h< _ku_h^k+H^2 _k1\ _k≤ H\. The increments have absolute value at most H2H^2. For any G∈[0,H]G∈[0,H] and an independent copy G′G , the variance identity gives (G2)=12[(G2−(G′)2)2]≤2H2[(G−G′)2]=4H2(G).V(G^2)= 12E[(G^2-(G )^2)^2]≤ 2H^2E[(G-G )^2]=4H^2V(G). Apply this conditionally to G=gh+1k(sh+1k)G=g_h+1^k(s_h+1^k). The predictable quadratic variation of the martingale is therefore at most 4H2Zg4H^2Z_g. Lemma C.1 yields ∑k,hξhk≤(HZglogKH+1η+H2logKH+1η). _k,h _h^k \! (H Z_g KH+1η+H^2 KH+1η ). Young’s inequality absorbs the square-root term into Zg/2Z_g/2 and proves (C.21). ∎ For the steps from τk _k onward, we telescope the squares of VkV^k up to step H+1H+1. The terminal value is zero, and the square at τk _k enters with a negative sign, so no positive boundary term remains. Lemma C.9. There exists an event ℰsufE_suf with ℙ(ℰsuf)≥1−δ/16P(E_suf)≥ 1-δ/16. On ℰest∩ℰsufE_est _suf, the accumulated variance satisfies ∑k=1K∑h=τkH(Ph(⋅∣shk,ahk),Vh+1k)≤(HB~K+H2∑k=1Kτk≤H+H2ι). _k=1^K _h= _k^HV(P_h(· s_h^k,a_h^k),V_h+1^k) \! (H B_K+H^2 _k=1^K1\ _k≤ H\+H^2 ). (C.22) Proof. Set Jhk:=τk≤hJ_h^k:=1\ _k≤ h\, qhk:=PhVh+1k(shk,ahk)q_h^k:=P_hV_h+1^k(s_h^k,a_h^k), and uhk:=minH,1+minβ~hk(shk,ahk),H.u_h^k:= \! \H,1+ \ β_h^k(s_h^k,a_h^k),H\ \. The indicators JhkJ_h^k are predictable, and VkV^k is fixed before episode k. In episode and step order, define the martingale differences ξhk:=JhkPh[(Vh+1k)2](shk,ahk)−(Vh+1k(sh+1k))2 _h^k:=J_h^k \P_h[(V_h+1^k)^2](s_h^k,a_h^k)-(V_h+1^k(s_h+1^k))^2 \. Let Z denote the left-hand side of (C.22). The increments are bounded by H2H^2. As in the proof of Lemma C.8, their conditional variance sum is at most 4H2Z4H^2Z. Apply Lemma C.1 with failure probability δ/16δ/16, and let ℰsufE_suf be the resulting event. Since log(16(KH+1)/δ)≤2ι (16(KH+1)/δ)≤ 2 , on ℰsufE_suf we have ∑k,hξhk≤(HZι+H2ι). _k,h _h^k \! (H Z +H^2 ). We now bound the drift on ℰestE_est. The residual bound (C.14), rh≤1r_h≤ 1, and clipping give Vhk(shk)−qhk≤uhkV_h^k(s_h^k)-q_h^k≤ u_h^k. By the definition of uhku_h^k, ∑k,hJhkuhk≤B~K+H∑k=1Kτk≤H. _k,hJ_h^ku_h^k≤ B_K+H _k=1^K1\ _k≤ H\. (C.23) If τk≤H _k≤ H, telescoping gives ∑h=τkH(Vh+1k(sh+1k))2−(qhk)2 _h= _k^H \(V_h+1^k(s_h+1^k))^2-(q_h^k)^2 \ =∑h=τkH(Vhk(shk))2−(qhk)2−(Vτk(sτk))2+(VH+1k(sH+1k))2 = _h= _k^H \(V_h^k(s_h^k))^2-(q_h^k)^2 \-(V_ _k^k(s_ _k^k))^2+(V_H+1^k(s_H+1^k))^2 ≤2H∑h=τkHuhk. ≤ 2H _h= _k^Hu_h^k. The inequality follows from (Vhk)2−(qhk)2≤2H[Vhk−qhk]+≤2Huhk(V_h^k)^2-(q_h^k)^2≤ 2H[V_h^k-q_h^k]_+≤ 2Hu_h^k and VH+1k≡0V_H+1^k≡ 0. For τk=H+1 _k=H+1, the sum is empty. Adding the martingale differences and summing over episodes gives Z≤∑k,hξhk+2H∑k,hJhkuhkZ≤ _k,h _h^k+2H _k,hJ_h^ku_h^k. On ℰest∩ℰsufE_est _suf, Young’s inequality absorbs the term containing Z Z into Z/2Z/2 and gives Z≤(H∑k,hJhkuhk+H2ι).Z \! (H _k,hJ_h^ku_h^k+H^2 ). Substituting (C.23) proves the claim. ∎ We next apply the preceding bounds to the residual sums and the auxiliary safe policy. Define the accumulated next-state variances of the two value differences by ZD Z_D :=∑k,h<τk(Ph(⋅∣shk,ahk),Dh+1k), := _k,h< _kV(P_h(· s_h^k,a_h^k),D_h+1^k), ZE Z_E :=∑k,h<τk(Ph(⋅∣shk,ahk),Eh+1k). := _k,h< _kV(P_h(· s_h^k,a_h^k),E_h+1^k). The auxiliary policy relates the variance accumulated before τk _k to a safe-policy return variance. For each episode, define Ak:=∑h<τk(Rh(shk,ahk))+(Ph(⋅∣shk,ahk),Vh+1π¯k).A_k:= _h< _k \V(R_h(s_h^k,a_h^k))+V(P_h(· s_h^k,a_h^k),V_h+1 π^k) \. (C.24) The next lemma converts the expected residuals to realized sums and bounds the accumulated variances needed in the regret proof. Lemma C.10. There exists an event ℰmartE_mart with ℙ(ℰmart)≥1−5δ/16P(E_mart)≥ 1-5δ/16 such that both of the following bounds hold on ℰmartE_mart: ∑k=1K[Yk∣ℱ1k] _k=1^KE[Y_k _1^k] ≤2(BK+B~K)+(H2ι), ≤ 2(B_K+ B_K)+O(H^2 ), (C.25) ∑k=1KAk _k=1^KA_k ≤2KVar⋆+(H3ι). ≤ 2KVar +O(H^3 ). (C.26) On ℰest∩ℰmartE_est _mart, the value-error variances also satisfy ZD+ZE≤(HBK+H2∑k=1Kτk≤H+H2ι),Z_D+Z_E \! (HB_K+H^2 _k=1^K1\ _k≤ H\+H^2 ), (C.27) and (C.22) holds for the steps h≥τkh≥ _k. Proof. For the expected residual sum, apply (C.2) to YkY_k with B=H2B=H^2 and failure probability δ/16δ/16, and let ℰYE_Y be the resulting event. Since ∑kYk=BK+B~K _kY_k=B_K+ B_K, (C.25) holds on ℰYE_Y, with ℙ(ℰY)≥1−δ/16P(E_Y)≥ 1-δ/16. To control the safe-policy variance, condition on ℱ1kF_1^k and couple πkπ^k with π¯k π^k using the same transition randomness. Both policies are fixed given this history. Their states and actions agree for h<τkh< _k. Since the summands in (C.24) are nonnegative, AkA_k is at most the full variance sum along the trajectory of π¯k π^k. Hence [Ak∣ℱ1k]≤π¯k[∑h=1H(Rh(sh,ah))+(Ph(⋅∣sh,ah),Vh+1π¯k)|s1]≤Var⋆.E[A_k _1^k] π^k\! [ _h=1^H \V(R_h(s_h,a_h))+V(P_h(· s_h,a_h),V_h+1 π^k) \\, |\,s_1 ] . Iterating the Bellman variance decomposition identifies the middle expectation with the return variance of π¯k π^k. The decomposition uses the conditional independence of the reward and successor state. Each reward variance is at most 1/41/4, and each step-h next-state value variance is at most (H−h)2/4(H-h)^2/4. Thus 0≤Ak≤14(H+∑j=0H−1j2)≤H3/30≤ A_k≤ 14(H+ _j=0^H-1j^2)≤ H^3/3. Apply (C.1) with B=H3/3B=H^3/3 and failure probability δ/16δ/16, and let ℰAE_A be the resulting event. On ℰAE_A, ∑k=1KAk≤2∑k=1K[Ak∣ℱ1k]+(H3ι)≤2KVar⋆+(H3ι). _k=1^KA_k≤ 2 _k=1^KE[A_k _1^k]+O(H^3 )≤ 2KVar +O(H^3 ). Thus ℙ(ℰA)≥1−δ/16P(E_A)≥ 1-δ/16. For the value-error variances, first consider [Dhk]+[D_h^k]_+ and [Ehk]+[E_h^k]_+. These functions are ℱ1kF_1^k-measurable, lie in [0,H][0,H] on every sample path, and vanish at step H+1H+1. The drift relations in Lemma C.6, together with [x]+−[y]+≤[x−y]+[x]_+-[y]_+≤[x-y]_+ and Ph[gh+1]+≥[Phgh+1]+P_h[g_h+1]_+≥[P_hg_h+1]_+, give, for h<τkh< _k, [Dhk(shk)]+−Ph[Dh+1k]+(shk,ahk) [D_h^k(s_h^k)]_+-P_h[D_h+1^k]_+(s_h^k,a_h^k) ≤[fhk]+, ≤[f_h^k]_+, [Ehk(shk)]+−Ph[Eh+1k]+(shk,ahk) [E_h^k(s_h^k)]_+-P_h[E_h+1^k]_+(s_h^k,a_h^k) ≤[fhk]+. ≤[f_h^k]_+. Since 0≤[fhk]+≤H0≤[f_h^k]_+≤ H, the assumptions of Lemma C.8 hold with uhk=[fhk]+u_h^k=[f_h^k]_+ on every sample path. Apply Lemma C.8 with ghk=[Dhk]+g_h^k=[D_h^k]_+ and ghk=[Ehk]+g_h^k=[E_h^k]_+, using this uhku_h^k and η=δ/16η=δ/16. Let ℰDE_D and ℰEE_E be the respective events. Each has probability at least 1−δ/161-δ/16. On ℰestE_est, Lemma C.6 gives Dk,Ek≥0D^k,E^k≥ 0, and Lemma C.5 gives [fhk]+≤minβhk(shk,ahk),H[f_h^k]_+≤ \ _h^k(s_h^k,a_h^k),H\. Hence (C.27) holds on ℰest∩ℰD∩ℰEE_est _D _E. Set ℰmart:=ℰY∩ℰA∩ℰD∩ℰE∩ℰsufE_mart:=E_Y _A _D _E _suf, where ℰsufE_suf is supplied by Lemma C.9. A union bound gives ℙ(ℰmart)≥1−5δ/16P(E_mart)≥ 1-5δ/16. ∎ C.6 Proof of Theorem 2 The preceding bounds reduce the proof to controlling BKB_K and B~K B_K. We bound BKB_K using each of the two variance quantities and take the smaller bound. The number of episodes containing an unsafe action controls the remaining sum B~K B_K. Define ℰmain:=ℰest∩ℰcert∩ℰmartE_main:=E_est _cert _mart. Lemmas B.2, C.3, and C.10 give ℙ(ℰmain)≥1−9+1+516δ≥1−δ.P(E_main)≥ 1- 9+1+516δ≥ 1-δ. (C.28) We work on ℰmainE_main throughout this subsection. Proposition C.2 and (C.25) give ℛ(K)≤2(BK+B~K)+(H2ι).R(K)≤ 2(B_K+ B_K)+O(H^2 ). (C.29) Bounding BKB_K Combining (C.27) with (C.6) yields ZD+ZE≤(HBK+H2ι[minK,+1]).Z_D+Z_E \! (HB_K+H^2 [ \K,C\+1 ] ). (C.30) For the steps h<τkh< _k, Vh+1⋆=Vh+1π¯k+Eh+1k−Dh+1kV_h+1 =V_h+1 π^k+E_h+1^k-D_h+1^k. The successor belongs to safe,h+1V_safe,h+1, so this identity holds on the support of the executed transition. Applying (X+Y+Z)≤3(X)+(Y)+(Z)V(X+Y+Z)≤ 3\V(X)+V(Y)+V(Z)\ and including the nonnegative reward variances gives Σ≤3(∑k=1KAk+ZD+ZE).V_ ≤ 3 ( _k=1^KA_k+Z_D+Z_E ). (C.31) Lemma C.7 and (C.11) give BK≤(SAHιΣ+S2AHιLKZD+S2AH2ιLK).B_K \! ( SAH \,V_ + S^2AH L_KZ_D+S^2AH^2 L_K ). (C.32) For the bound in terms of ΣV_ , substitute (C.30) into (C.32) to obtain BK≤(CLOSE B_K \! ( SAHιΣ+SAH2ιLKBK SAH \,V_ +S AH^2 L_KB_K OPEN+SAH3minK,ιLK+S2AH2ιLK). +S AH^3 \K,C\\, L_K+S^2AH^2 L_K ). Young’s inequality bounds the term containing BK B_K by BK/2+(S2AH2ιLK)B_K/2+O(S^2AH^2 L_K). Moving BK/2B_K/2 to the left yields BK≤(CLOSE B_K \! ( OPENSAHιΣ+SAH3minK,ιLK+S2AH2ιLK). SAH \,V_ +S AH^3 \K,C\\, L_K+S^2AH^2 L_K ). (C.33) For the bound in terms of Var⋆Var , (C.31) and (C.26) give SAHιΣ≤(SAHKVar⋆ι+SAHι(ZD+ZE)+H2ιSA). SAH \,V_ \! ( SAHKVar \, + SAH (Z_D+Z_E)+H^2 SA ). Substitute this inequality into (C.32) and use (C.30) for ZD+ZEZ_D+Z_E. Since S,LK≥1S,L_K≥ 1, the resulting terms involving BKB_K and minK, \K,C\ are bounded by the corresponding terms above. Also, H2ιSA≤S2AH2ιLKH^2 SA≤ S^2AH^2 L_K. Applying the same absorption step gives BK≤(CLOSE B_K \! ( OPENSAHKVar⋆ι+SAH3minK,ιLK+S2AH2ιLK). SAHKVar \, +S AH^3 \K,C\\, L_K+S^2AH^2 L_K ). (C.34) Both bounds hold on ℰmainE_main. Taking their minimum gives BK≤(CLOSE B_K \! ( OPENSAHιminΣ,KVar⋆+SAH3minK,ιLK+S2AH2ιLK). SAH \, \V_ ,KVar \+S AH^3 \K,C\\, L_K+S^2AH^2 L_K ). (C.35) Bounding B~K B_K The remaining steps occur only in episodes with τk≤H _k≤ H. Since each reward variance is at most 1/41/4, ∑k=1K∑h=τkH(Rh(shk,ahk))≤H4∑k=1Kτk≤H. _k=1^K _h= _k^HV(R_h(s_h^k,a_h^k))≤ H4 _k=1^K1\ _k≤ H\. Apply Lemma C.7 to (C.12) over the visits with h≥τkh≥ _k: B~K B_K ≤(SAHι∑k=1K∑h=τkH(Rh(shk,ahk))CLOSE \! ( SAH _k=1^K _h= _k^HV(R_h(s_h^k,a_h^k)) OPEN+SAHιLK∑k=1K∑h=τkH(Ph(⋅∣shk,ahk),Vh+1k)+S2AH2ιLK). +S AH L_K _k=1^K _h= _k^HV(P_h(· s_h^k,a_h^k),V_h+1^k)+S^2AH^2 L_K ). The reward-variance bound above and (C.22) then give, using S,A,H,LK≥1S,A,H,L_K≥ 1, B~K≤(SAH3ιLK∑k=1Kτk≤H+SAH2ιLKB~K+S2AH2ιLK). B_K \! (S AH^3 L_K _k=1^K1\ _k≤ H\+S AH^2 L_K\, B_K+S^2AH^2 L_K ). Young’s inequality bounds the term containing B~K B_K by B~K/2+(S2AH2ιLK) B_K/2+O(S^2AH^2 L_K). Move B~K/2 B_K/2 to the left and use (C.6) to obtain B~K≤(SAH3minK,ιLK+S2AH2ιLK). B_K \! (S AH^3 \K,C\\, L_K+S^2AH^2 L_K ). (C.36) Proof of Theorem 2. Substitute (C.35) and (C.36) into (C.29). Since H2ι≤S2AH2ιLKH^2 ≤ S^2AH^2 L_K, this gives ℛ(K)≤(CLOSE (K) \! ( OPENSAHιminΣ,KVar⋆+SAH3minK,ιLK+S2AH2ιLK). SAH \, \V_ ,KVar \+S AH^3 \K,C\\, L_K+S^2AH^2 L_K ). (C.37) The probability statement follows from (C.28). Suppressing the logarithmic factors in ι and LKL_K proves Theorem 2. ∎ C.7 A Special Case with Direct Cost Violations Suppose Assumptions 1 and 2 hold, and every unsafe action at a vertex reachable under a safe policy has cost exceeding τ. Then ≤SAH/Δc2C≤ SAH/ _c^2, and SVAE satisfies, with probability at least 1−δ1-δ, ℛ(K)≤~(SAHminΣ,KVar⋆+SAH3minK,SAH/Δc2+S2AH2).R(K)≤ O\! ( SAH \V_ ,KVar \+S AH^3 \K,SAH/ _c^2\+S^2AH^2 ). (C.38) Proof. For every action contributing to C, the direct-cost branch of (7) gives κh(s,a)=(ch(s,a)−τ)−2≤Δc−2 _h(s,a)=(c_h(s,a)-τ)^-2≤ _c^-2. There are at most SAHSAH such actions, so ≤SAH/Δc2C≤ SAH/ _c^2. Substitution into Theorem 2 yields (C.38) on the same event. ∎ Appendix D Constraint Violation We prove Theorem 3 on ℰcs=ℰc∩ℰsuppE_cs=E_c _supp, which has probability at least 1−δ/81-δ/8 by Lemma B.2. We separate steps with nonempty candidate sets from those with empty candidate sets. The cost bound controls the first contribution, and newly observed transitions control the second. Let nempnemp and empemp denote nonempty and empty candidate sets, respectively, and define Violnemp(K) _nemp(K) :=∑k=1K∑h=1H[ch(shk,ahk)−τ]+^safe,hk(shk)≠∅, := _k=1^K _h=1^H [c_h(s_h^k,a_h^k)-τ ]_+1\! \ A_safe,h^k(s_h^k)≠ \, (D.1) Violemp(K) _emp(K) :=∑k=1K∑h=1H[ch(shk,ahk)−τ]+^safe,hk(shk)=∅. := _k=1^K _h=1^H [c_h(s_h^k,a_h^k)-τ ]_+1\! \ A_safe,h^k(s_h^k)= \. Then, deterministically, Viol(K)=Violnemp(K)+Violemp(K).Viol(K)=Viol_nemp(K)+Viol_emp(K). (D.2) Nonempty candidate sets We first bound Violnemp(K)Viol_nemp(K). Every selected candidate action passes the cost test. This controls both its one-step violation and the number of times it can be selected with a positive cost gap. Lemma D.1. On ℰcE_c, both Violnemp(K)≤42HSAKιViol_nemp(K)≤ 4 2\,H SAK and the following gap-dependent bound hold: Violnemp(K)≤∑ch(s,a)>τch(s,a)−τ+8ιch(s,a)−τ.Viol_nemp(K)≤ _c_h(s,a)>τ \c_h(s,a)-τ+ 8 c_h(s,a)-τ \. (D.3) The sum ranges over (s,a,h)∈×[H](s,a,h) ×A×[H] with a positive cost gap. Proof. When the candidate set is nonempty, Algorithm 1 selects a∈^safe,hk(s)a∈ A_safe,h^k(s), so c¯hk(s,a)≤τ c_h^k(s,a)≤τ. On ℰcE_c, this implies ch(s,a)−τ c_h(s,a)-τ ≤ch(s,a)−c^hk(s,a)+2ιnhk(s,a)≤22ιnhk(s,a). ≤ c_h(s,a)- c_h^k(s,a)+ 2 n_h^k(s,a)≤ 2 2 n_h^k(s,a). Since nhk=maxNhk,1n_h^k= \N_h^k,1\, this also covers the zero-count case. Hence [ch(s,a)−τ]+≤22ιnhk(s,a).[c_h(s,a)-τ]_+≤ 2 2 n_h^k(s,a). (D.4) Let Mh(s,a)M_h(s,a) count executions of (s,a)(s,a) at step h with a nonempty candidate set. The reciprocal-count bound in Lemma C.7 applies to this subset of visits. Summing (D.4) and using ∑s,a,hMh(s,a)≤KH _s,a,hM_h(s,a)≤ KH gives Violnemp(K) _nemp(K) ≤42ι∑s,a,hMh(s,a) ≤ 4 2 _s,a,h M_h(s,a) ≤42SAHι∑s,a,hMh(s,a) ≤ 4 2SAH _s,a,hM_h(s,a) ≤42HSAKι. ≤ 4 2\,H SAK . For the second bound, fix (s,a,h)(s,a,h) with Δ:=ch(s,a)−τ>0 :=c_h(s,a)-τ>0. If Mh(s,a)≥2M_h(s,a)≥ 2, the last counted execution has at least Mh(s,a)−1M_h(s,a)-1 prior visits. Applying (D.4) there gives Δ≤22ι/(Mh(s,a)−1) ≤ 2 2 /(M_h(s,a)-1). Therefore, including the cases Mh(s,a)≤1M_h(s,a)≤ 1, Mh(s,a)≤1+8ιΔ2.M_h(s,a)≤ 1+ 8 ^2. (D.5) Each counted execution contributes Δ . Multiplying by Δ and summing over positive-gap triples proves (D.3). ∎ Empty candidate sets It remains to bound Violemp(K)Viol_emp(K). An empty candidate set can follow a candidate action only through a newly observed transition. We associate each block of empty candidate sets with this transition and bound its length by the remaining horizon. Lemma D.2. Suppose Assumption 1 holds. Then, on ℰcsE_cs, Violemp(K)≤S2AH(H−1)/2Viol_emp(K)≤ S^2AH(H-1)/2. Proof. In each episode k, partition the steps with empty candidate sets into maximal contiguous blocks. A block ℓ,…,r\ ,…,r\ has ℓ≥2 ≥ 2: Assumption 1 and the inclusions proved in Appendix B.4 guarantee a nonempty candidate set at s1s_1. By maximality, the preceding action is a candidate, so supp^ℓ−1k(sℓ−1k,aℓ−1k)⊆^safe,ℓk. supp_ -1^k(s_ -1^k,a_ -1^k) V_safe, ^k. (D.6) The state sℓks_ ^k has no candidate actions. Consequently, sℓk∉^safe,ℓk,sℓk∉supp^ℓ−1k(sℓ−1k,aℓ−1k).s_ ^k∉ V_safe, ^k, s_ ^k∉ supp_ -1^k(s_ -1^k,a_ -1^k). (D.7) Thus (sℓ−1k,aℓ−1k,sℓk,ℓ−1)(s_ -1^k,a_ -1^k,s_ ^k, -1) is a newly observed transition. Associate the block with this transition. Each transition is associated with at most one block. A given layer is visited once per episode. In later episodes, the successor remains in the observed support, so a candidate predecessor action forces it to have a nonempty candidate set by (D.6). It therefore cannot start another empty block through that action. There are at most S2AS^2A transitions at each parent layer h, and an associated block has length at most H−hH-h. Since violation per step is at most one, Violemp(K)≤S2A∑h=1H−1(H−h)=S2AH(H−1)2.∎Viol_emp(K)≤ S^2A _h=1^H-1(H-h)= S^2AH(H-1)2. Proof of Theorem 3. Substituting Lemmas D.1 and D.2 into (D.2) gives, on ℰcsE_cs, Viol(K)≤42HSAKι+S2AH(H−1)2.Viol(K)≤ 4 2\,H SAK + S^2AH(H-1)2. If Assumption 2 also holds, every positive cost gap is at least Δc _c. The second bound in Lemma D.1 then gives, on the same event, Viol(K)≤SAH(1+8ιΔc)+S2AH(H−1)2.Viol(K)≤ SAH (1+ 8 _c )+ S^2AH(H-1)2. The event has probability at least 1−δ/81-δ/8. Suppressing logarithmic factors proves both claims. ∎ Appendix E Cost Confidence Bounds at Zero Empirical Variance A sample with zero empirical variance may come from a cost distribution whose mean exceeds the safety threshold. We compare two distributions that can produce the same constant sample to obtain a necessary additive term in the confidence bound. We then apply this comparison to the lower confidence test used for action removal in SVAE. Fix τ∈(0,1)τ∈(0,1) and δ∈(0,1/2)δ∈(0,1/2). A certification rule observes independent samples X1,X2,…X_1,X_2,… from a common distribution ν on [0,1][0,1], may use independent auxiliary randomness, and returns a stopping time T∈ℕ∪∞T ∪\∞\ at which it declares that the mean is at most τ. Here ℕ=1,2,…N=\1,2,…\, and T≤n\T≤ n\ depends only on the first n observations and the auxiliary randomness. Call the rule δ-safe if ℙν(T<∞)≤δP_ν(T<∞)≤δ for every such distribution with ν[X]>τE_ν[X]>τ. The probability includes both sources of randomness. Set Δmax:=minτ,1−τ _ := \τ,1-τ\. For each Δ∈(0,Δmax) ∈(0, _ ), let pΔ:=2Δ/(1−τ+Δ)p_ :=2 /(1-τ+ ). Under ν0 _0, each sample equals τ−Δτ- with probability one. Under ν1 _1, it equals 11 with probability pΔp_ and τ−Δτ- otherwise. Both distributions are supported on [0,1][0,1], with ν0[X]=τ−ΔE_ _0[X]=τ- and ν1[X]=τ+ΔE_ _1[X]=τ+ . Proposition E.1. Fix Δ∈(0,Δmax) ∈(0, _ ) and let ν0,ν1 _0, _1 be the distributions defined above. For every δ-safe certification rule T and every n∈ℕn , we have ℙν0(T≤n)≤δ(1−pΔ)n.P_ _0(T≤ n)≤ δ(1-p_ )^n. (E.1) Proof. Since pΔ∈(0,1)p_ ∈(0,1), under ν1 _1 the first n observations all equal τ−Δτ- with probability (1−pΔ)n(1-p_ )^n. On that event, the rule sees exactly the observations under ν0 _0, and its auxiliary randomness has the same distribution. Thus δ≥ℙν1(T≤n)≥(1−pΔ)nℙν0(T≤n),δ _ _1(T≤ n)≥(1-p_ )^nP_ _0(T≤ n), which proves (E.1). ∎ We now apply this comparison to confidence bounds based on empirical variance. For t∈ℕt , define X¯t:=t−1∑i=1tXi X_t:=t^-1 _i=1^tX_i and v^t:=t−1∑i=1t(Xi−X¯t)2 v_t:=t^-1 _i=1^t(X_i- X_t)^2. Let (ρt)t∈ℕ( _t)_t be deterministic functions from [0,∞)×(0,1/2)[0,∞)×(0,1/2) to [0,∞)[0,∞), and define the stopping rule T:=inft∈ℕ:X¯t+ρt(v^t,δ)≤τ,T:= \t : X_t+ _t( v_t,δ)≤τ \, (E.2) with the convention inf∅=+∞ =+∞. Corollary E.1. Suppose the stopping rule in (E.2) is δ-safe. Then, for every n∈ℕn , ρn(0,δ)≥minΔmax,(1−τ)(1−δ1/n)1+δ1/n. _n(0,δ)≥ \ _ , (1-τ)(1-δ^1/n)1+δ^1/n \. (E.3) In particular, for every n∈ℕn satisfying log(1/δ)/n≤Δmax (1/δ)/n≤ _ , ρn(0,δ)≥(1−τ)log(1/δ)4n _n(0,δ)≥ (1-τ) (1/δ)4n. Proof. Suppose (E.3) fails at some n, and choose ρn(0,δ)<Δ<minΔmax,(1−τ)(1−δ1/n)1+δ1/n. _n(0,δ)< < \ _ , (1-τ)(1-δ^1/n)1+δ^1/n \. Under ν0 _0, all observations equal τ−Δτ- , so X¯n=τ−Δ X_n=τ- , v^n=0 v_n=0, and T≤nT≤ n almost surely. Proposition E.1 gives (1−pΔ)n≤δ(1-p_ )^n≤δ. However, the chosen upper bound on Δ is equivalent to pΔ<1−δ1/np_ <1-δ^1/n, a contradiction. For the second claim, set x=log(1/δ)/n≤Δmax≤1/2x= (1/δ)/n≤ _ ≤ 1/2. The inequalities 1−e−x≥x/21-e^-x≥ x/2 and 1+e−x≤21+e^-x≤ 2 give (1−τ)(1−e−x)/(1+e−x)≥(1−τ)x/4(1-τ)(1-e^-x)/(1+e^-x)≥(1-τ)x/4. Also, Δmax≥(1−τ)x/4 _ ≥(1-τ)x/4. Substituting into (E.3) proves the claim. ∎ For the lower confidence test, consider T=inft∈ℕ:X¯t−ρt(v^t,δ)>τT= \t : X_t- _t( v_t,δ)>τ\ and suppose ℙν(T<∞)≤δP_ν(T<∞)≤δ for every distribution on [0,1][0,1] with ν[X]≤τE_ν[X]≤τ. Reflect the observations to 1−X1-X and the threshold to 1−τ1-τ. The empirical variance is unchanged. The same constant-sample argument applies, since ρn(0,δ)<Δ _n(0,δ)< ensures that the strict test fires. It gives ρn(0,δ)≥minΔmax,τ(1−δ1/n)1+δ1/n. _n(0,δ)≥ \ _ , τ(1-δ^1/n)1+δ^1/n \. (E.4) In particular, ρn(0,δ)≥τlog(1/δ)/(4n) _n(0,δ)≥τ (1/δ)/(4n) under the same conditions on n as in the corollary. Thus uniformly valid action removal requires a positive radius at zero empirical variance. Appendix F Safe-Subgraph Variance Throughout this section, Assumption 1 holds. We use the spans SπS^π and S⋆S from Section 3.2 to bound the transition variances of safe-policy values and optimal safe values, respectively. The branching depth bounds the number of nonzero terms along a safe path. We then apply the resulting variance bounds to regret and provide matching cost constructions showing that the bounds are tight. F.1 Proof of Theorem 1 Proof. Fix π∈Πsafeπ∈ _safe. Its trajectory is almost surely a safe path in safeG_safe, and every visited vertex belongs to πV^π. For a distribution q and a bounded function f, let m:=minx∈supp(q)f(x)m:= _x (q)f(x) and M:=maxx∈supp(q)f(x)M:= _x (q)f(x). Since (f−m)(M−f)≥0(f-m)(M-f)≥ 0 on supp(q)supp(q), (q,f)≤(M−qf)(qf−m)≤14(M−m)2.V(q,f)≤(M-qf)(qf-m)≤ 14(M-m)^2. (F.1) Apply (F.1) with q=Ph(⋅∣sh,ah)q=P_h(· s_h,a_h) and f=Vh+1πf=V_h+1^π. A deterministic transition has zero variance. Otherwise, the definition of SπS^π bounds the successor-value span by SπS^π. Hence, almost surely, (Ph(⋅∣sh,ah),Vh+1π)≤14(Sπ)2|supp(Ph(⋅∣sh,ah))|>1.V(P_h(· s_h,a_h),V_h+1^π)≤ 14(S^π)^21\! \|supp(P_h(· s_h,a_h))|>1 \. (F.2) A safe path contains at most B(safe)B(G_safe) stochastic transitions. Summing (F.2) along the path and taking expectation gives π[∑h=1H(Ph(⋅∣sh,ah),Vh+1π)|s1]≤14(Sπ)2B(safe).E^π\! [ _h=1^HV(P_h(· s_h,a_h),V_h+1^π)\, |\,s_1 ]≤ 14(S^π)^2B(G_safe). (F.3) For the second claim, fix a safe path γ=(s1,a1,…,sH,aH,sH+1)γ=(s_1,a_1,…,s_H,a_H,s_H+1) and a step h∈[H]h∈[H]. All successors of aha_h are viable, so Vh+1⋆V_h+1 gives their optimal safe continuation values by Lemma B.1. Its span on supp(Ph(⋅∣sh,ah))supp(P_h(· s_h,a_h)) is at most S⋆S by definition. A deterministic transition has zero variance. Thus (F.1) gives (Ph(⋅∣sh,ah),Vh+1⋆)≤14(S⋆)2|supp(Ph(⋅∣sh,ah))|>1.V(P_h(· s_h,a_h),V_h+1 )≤ 14(S )^21\! \|supp(P_h(· s_h,a_h))|>1 \. (F.4) The steps before τk _k can be completed to a full safe path because all successors of a safe action are viable. Each episode therefore contains at most B(safe)B(G_safe) stochastic transitions before τk _k. Summing (F.4) gives ∑k=1K∑h<τk(Ph(⋅∣shk,ahk),Vh+1⋆)≤K4(S⋆)2B(safe), _k=1^K _h< _kV(P_h(· s_h^k,a_h^k),V_h+1 )≤ K4(S )^2B(G_safe), (F.5) which proves the second claim. ∎ F.2 Proof of Corollary 1 Proof. For deterministic rewards, the reward-variance terms in (5) vanish, so (F.5) gives Σ≤K4(S⋆)2B(safe)V_ ≤ K4(S )^2B(G_safe). The total reward of every safe policy lies in [0,H][0,H], so its variance is at most H2/4H^2/4. Hence Var⋆≤H2/4Var ≤ H^2/4 by (4). Combining these two bounds yields minΣ,KVar⋆≤K4minH2,(S⋆)2B(safe). \V_ ,KVar \≤ K4 \H^2,(S )^2B(G_safe)\. Substituting this inequality into Theorem 2 proves the corollary on the same event, with probability at least 1−δ1-δ. ∎ F.3 Proof of Proposition 1 To attain the variance bound, we keep the transition kernel and rewards fixed and vary the costs that determine which gadget transitions are safe. We first give the construction, then compute its branching depth, successor-value span, and return variance. Figure 2 shows the construction for n=3n=3 with zero, one, two, and three open gadgets. Example 1 (Gadget chain). Fix an integer n≥1n≥ 1 and set H=2nH=2n. Gadget i∈[n]i∈[n] starts at sis_i in layer hi:=2i−1h_i:=2i-1, and sn+1:=ts_n+1:=t is the terminal state. The transition kernel and deterministic rewards are fixed as follows. At sis_i, action adet,ia_det,i transitions deterministically to sA,i′s _A,i, while ast,ia_st,i transitions uniformly to sA,i′s _A,i and sB,i′s _B,i. Both actions have reward zero. At the next layer, action αi _i at sA,i′s _A,i has reward one, and actions β1,i,β2,i _1,i, _2,i at sB,i′s _B,i have rewards one and zero, respectively. All three actions transition deterministically to si+1s_i+1. Take τ=1/2τ=1/2, set chi+1(sA,i′,αi)=0c_h_i+1(s _A,i, _i)=0, and define (chi(si,adet,i),chi(si,ast,i),chi+1(sB,i′,β1,i),chi+1(sB,i′,β2,i)) (c_h_i(s_i,a_det,i),c_h_i(s_i,a_st,i),c_h_i+1(s _B,i, _1,i),c_h_i+1(s _B,i, _2,i) ) (F.6) =(0,0,1,1),if gadget i is closed,(1,0,1,0),if gadget i is open. = cases(0,0,1,1),&if gadget $i$ is closed,\\ (1,0,1,0),&if gadget $i$ is open. cases Every other state–action pair has cost one, reward zero, and a fixed deterministic transition to the next layer. For a cost configuration c, let b(c)∈0,…,nb(c)∈\0,…,n\ denote the number of open gadgets. (a)s1s_1sA1′s _\!A1sB1′s _\!B1s2s_2adeta_detr=1r\!=\!1sA2′s _\!A2sB2′s _\!B2s3s_3adeta_detr=1r\!=\!1sA3′s _\!A3sB3′s _\!B3ttadeta_detr=1r\!=\!1Var⋆=0Var =0(b)s1s_1sA1′s _\!A1sB1′s _\!B1s2s_2adeta_detasta_str=1r\!=\!1β1 _1r=0r\!=\!0sA2′s _\!A2sB2′s _\!B2s3s_3adeta_detr=1r\!=\!1sA3′s _\!A3sB3′s _\!B3ttadeta_detr=1r\!=\!1Var⋆=14Var = 14(c)s1s_1sA1′s _\!A1sB1′s _\!B1s2s_2adeta_detasta_str=1r\!=\!1β1 _1r=0r\!=\!0sA2′s _\!A2sB2′s _\!B2s3s_3adeta_detasta_str=1r\!=\!1β1 _1r=0r\!=\!0sA3′s _\!A3sB3′s _\!B3ttadeta_detr=1r\!=\!1Var⋆=12Var = 12(d)s1s_1sA1′s _\!A1sB1′s _\!B1s2s_2adeta_detasta_str=1r\!=\!1β1 _1r=0r\!=\!0sA2′s _\!A2sB2′s _\!B2s3s_3adeta_detasta_str=1r\!=\!1β1 _1r=0r\!=\!0sA3′s _\!A3sB3′s _\!B3ttadeta_detasta_str=1r\!=\!1β1 _1r=0r\!=\!0Var⋆=34Var = 34 Figure 2: Four safe subgraph topologies on the same H=6H=6 gadget-chain MDP (Example 1). Each row shows the safe subgraph under a different cost function. Black solid edges are safe. Red dashed edges are unsafe. In a closed gadget, both actions at sB,i′s _B,i are unsafe, so ast,ia_st,i fails the successor-viability condition and only adet,ia_det,i remains. In an open gadget, adet,ia_det,i and β1,i _1,i are unsafe, leaving a successor-value gap of one by (F.10). Dotted black edges show the branch of asta_st to sA,i′s _A,i. Gadget indices are omitted from the action labels. Proof of Proposition 1. A backward induction from sn+1=ts_n+1=t using (F.6) gives, for every i∈[n]i∈[n], safe,hi(si)=ast,i,if gadget i is open,adet,i,if gadget i is closed,A_safe,h_i(s_i)= cases\a_st,i\,&if gadget $i$ is open,\\ \a_det,i\,&if gadget $i$ is closed, cases (F.7) and safe,hi+1(sA,i′)=αi,safe,hi+1(sB,i′)=β2,i,if gadget i is open,∅,if gadget i is closed.A_safe,h_i+1(s _A,i)=\ _i\, _safe,h_i+1(s _B,i)= cases\ _2,i\,&if gadget $i$ is open,\\ ,&if gadget $i$ is closed. cases (F.8) In a closed gadget, the state sB,i′s _B,i is not viable. The action ast,ia_st,i satisfies the immediate cost constraint but fails the successor-viability condition. In an open gadget, both successors of ast,ia_st,i are viable, while adet,ia_det,i and β1,i _1,i violate the cost threshold. It follows from (F.7)–(F.8) that all policies in Πsafe _safe select the same action at every state and step reachable from s1s_1 under a safe policy. Since both reward-layer branches merge at the next choice state, ℙπ(shi=si∣s1)=1,i∈[n].P^π(s_h_i=s_i s_1)=1, i∈[n]. (F.9) The stochastic choice (si,ast,i,hi)(s_i,a_st,i,h_i) is safe exactly when gadget i is open. These are the only stochastic safe transitions, and every safe path visits all n choice states. Hence B(safe)=b(c)B(G_safe)=b(c). We next compute the successor-value spans and variances. If gadget i is closed, its safe choice action and its reward-layer transition are deterministic, so its next-state value variance is zero. If gadget i is open, then Vhi+1π(sA,i′)=1+Vhi+2π(si+1),Vhi+1π(sB,i′)=Vhi+2π(si+1).V_h_i+1^π(s _A,i)=1+V_h_i+2^π(s_i+1), V_h_i+1^π(s _B,i)=V_h_i+2^π(s_i+1). (F.10) The two successor values differ by one. All deterministic transitions have successor-value span zero, so Sπ=b(c)>0S^π=1\b(c)>0\. At each open gadget, (Phi(⋅∣si,ast,i),Vhi+1π) \! (P_h_i(· s_i,a_st,i),V_h_i+1^π ) =14(Vhi+1π(sA,i′)−Vhi+1π(sB,i′))2=14. = 14 (V_h_i+1^π(s _A,i)-V_h_i+1^π(s _B,i) )^2= 14. All rewards are deterministic. Using (F.9) and summing these next-state variances over the open gadgets gives π[∑h=1H(Ph(⋅∣sh,ah),Vh+1π)|s1]=∑i:gadget i is open14=b(c)4.E^π\! [ _h=1^HV(P_h(· s_h,a_h),V_h+1^π)\, |\,s_1 ]= _i:\,gadget $i$ is open 14= b(c)4. These identities hold for every π∈Πsafeπ∈ _safe. Taking the supremum over this class gives Var⋆=b(c)/4Var =b(c)/4. The unique safe actions in (F.7)–(F.8) imply that these successor values coincide with V⋆V . Thus S⋆=b(c)>0S =1\b(c)>0\ by definition. Substitution into (F.3) proves equality. For every b∈0,…,nb∈\0,…,n\, choosing exactly b open gadgets gives the instance required by Proposition 1. ∎ Appendix G Lower Bounds Appendix G.1 proves the regret lower bound in Theorem 4. Appendix G.2 studies the sample requirements for action elimination under additional conditions on the transition structure and observations. G.1 Proof of Theorem 4 Assume the parameter conditions of Theorem 4. We use two families of CMDPs with the prescribed variance and safety identification complexity. The first requires learning which action has the better transition probability. The second requires identifying a safe action at each of several state–step pairs. We prove a regret lower bound for each family and then choose the instance giving the larger bound. Learning algorithms follow the protocol in Section 2, with their policies chosen before each episode. For a fixed instance ℳM, the expectation ℳE_M includes the algorithm’s randomness and its observations. Common construction Set n:=S−3n:=S-3 and use the states x,g,b,c1,…,cn\x,g,b,c_1,…,c_n\, action set [A][A], initial state x, and threshold τ=1/2τ=1/2. Use d:=⌊H/16⌋d:= H/16 three-step gadgets in the first 3d3d steps, each of which starts at x and returns to x. The two families differ in these gadgets and in the costs and transitions at a set of state–step pairs after them. The last R:=⌊H/8⌋R:= H/8 steps provide the reward lost by an incorrect choice in the second family. Since 4d+R+1≤H4d+R+1≤ H, these parts fit within the horizon. Let M:=⌊Γ/[8(A−1)]⌋M:= /[8(A-1)] . The parameter assumptions give Γ/16≤M(A−1)≤Γ/8 /16≤ M(A-1)≤ /8 and 2≤M≤nd2≤ M≤ nd, so we can choose ⊆3d+2,…,4d+1×[n]J \3d+2,…,4d+1\×[n] with ||=M|J|=M. Here (h,s)∈(h,s) denotes context state csc_s at step h. We specify the transitions so that exactly one pair in J is reached in each episode, uniformly over the M pairs. For h∈3d+2,…,4d+1h∈\3d+2,…,4d+1\, let Mh:=|(t,s)∈:t≥h|M_h:=|\(t,s) :t≥ h\| and set M4d+2:=0M_4d+2:=0. Whenever Mh>0M_h>0, every action at x at step h−1h-1 satisfies Ph−1(cs∣x,a)=(h,s)∈Mh,Ph−1(x∣x,a)=Mh+1Mh.P_h-1(c_s x,a)= 1\(h,s) \M_h, P_h-1(x x,a)= M_h+1M_h. Every action at a pair in J moves to g or b, as specified below, and the process then remains in that state until the episode ends. Since μ3d+1π(x)=1=M3d+2/M _3d+1^π(x)=1=M_3d+2/M, induction gives μh−1π(x)=MhM,μhπ(cs)=1M,(h,s)∈. _h-1^π(x)= M_hM, _h^π(c_s)= 1M, (h,s) . (G.1) Thus the reached pair is uniform on J, conditional on the past and independent of the chosen actions. All rewards and costs are deterministic. Unspecified rewards and costs are zero, and unspecified transitions are self-loops. Write D:=nd(A−1)D:=nd(A-1) and m:=minK,Γm:= \K, \. We will use the bounds n≥5S/8n≥ 5S/8, d≥H/20d≥ H/20, and SAH/64≤D≤SAH/16SAH/64≤ D≤ SAH/16, which follow from the parameter assumptions. Variance term The first family places an unknown best action at each context state in each gadget. These actions determine the probabilities of receiving the gadget rewards; the costs at the pairs in J determine the safety identification complexity. Lemma G.1. Assume the parameter conditions of Theorem 4. For every learning algorithm following the protocol in Section 2, there exists a CMDP ℳvM_v with S states, A actions, and horizon H satisfying Assumption 1, 3v4≤Var⋆(ℳv)≤v 3v4 (M_v)≤ v, and Γ4≤(ℳv)≤Γ2 4 (M_v)≤ 2. On this instance, every realized interaction sequence satisfies 31Kv32≤Σ≤Kv. 31Kv32 _ ≤ Kv. (G.2) The algorithm’s expected regret on ℳvM_v satisfies ℳv[ℛ(K)]≥3322nAdKv.E_M_v[R(K)]≥ 332 2 nAdKv. (G.3) Proof. Construction. Set ε:=182nA/K := 18 2 nA/K and ρ:=2v/dρ:=2 v/d. Since K≥nAK≥ nA and v≤d/4v≤ d/4, we have 0<ε≤1/(82)0< ≤ 1/(8 2) and 0≤ρ≤10≤ρ≤ 1. Choose (ωi,s)(i,s)∈[d]×[n]( _i,s)_(i,s)∈[d]×[n] independently and uniformly from [A][A]. In gadget i, at step 3i−23i-2, every action at x transitions uniformly to one of c1,…,cnc_1,…,c_n. At step 3i−13i-1, P3i−1(g∣cs,a)=12+εa=ωi,s,P3i−1(b∣cs,a)=1−P3i−1(g∣cs,a).P_3i-1(g c_s,a)= 12+ 1\a= _i,s\, P_3i-1(b c_s,a)=1-P_3i-1(g c_s,a). At step 3i3i, every action yields reward ρ at g and zero at b, and both states return to x. All costs in these gadgets are zero. At every pair in J, action 11 has cost zero and all other actions have cost one. Every action there moves to g, and all subsequent rewards are zero. A policy choosing action 11 at every such pair is safe, so Assumption 1 holds. The transition probabilities and rewards lie in [0,1][0,1] by the bounds on ε and ρ. Instance properties. Fix π∈Πsafeπ∈ _safe and gadget i, and let αi:=n−1∑s=1nπ3i−1(cs)=ωi,s _i:=n^-1 _s=1^n1\ _3i-1(c_s)= _i,s\. Each gadget returns to x, so its contribution to the return variance is the next-state value variance at x plus the average over its context states. These two terms satisfy (P3i−2(⋅∣x,π3i−2(x)),V3i−1π)+1n∑s=1n(P3i−1(⋅∣cs,π3i−1(cs)),V3iπ) \! (P_3i-2(· x, _3i-2(x)),V_3i-1^π )+ 1n _s=1^nV\! (P_3i-1(· c_s, _3i-1(c_s)),V_3i^π ) =ε2ρ2αi(1−αi)+ρ24−ε2ρ2αi = ^2ρ^2 _i(1- _i)+ ρ^24- ^2ρ^2 _i =ρ24−ε2ρ2αi2∈[3ρ216,ρ24]. = ρ^24- ^2ρ^2 _i^2∈ [ 3ρ^216, ρ^24 ]. (G.4) The first equality is the variance decomposition across the two transitions. The last inclusion uses ε2≤1/128 ^2≤ 1/128. Summing (G.4) over i and using dρ2/4=vdρ^2/4=v gives 3v/4≤Var⋆(ℳv)≤v3v/4 (M_v)≤ v. The later steps contribute no variance because their rewards are zero. The only unsafe actions are the M(A−1)M(A-1) actions with cost one at pairs in J. All these pairs are reachable under a safe policy, and each such action has cost gap 1/21/2. Therefore, (ℳv)=4M(A−1)∈[Γ/4,Γ/2]C(M_v)=4M(A-1)∈[ /4, /2]. We next compute ΣV_ . Under the optimal safe value function, V3i−1⋆(cs)=(1/2+ε)ρ+V3i+1⋆(x)V_3i-1 (c_s)=(1/2+ )ρ+V_3i+1 (x) for every s∈[n]s∈[n], so the transition from x to the context states has zero next-state value variance. In episode k, let si,ks_i,k be the visited context index and ai,ka_i,k the selected action. Write pi,k:=1/2+εai,k=ωi,si,kp_i,k:=1/2+ 1\a_i,k= _i,s_i,k\. The two successor values differ by ρ, so the context transition contributes pi,k(1−pi,k)ρ2p_i,k(1-p_i,k)ρ^2. These gadgets are safe and occur before any pair in J is reached, so their contributions are included in ΣV_ . All rewards are deterministic, and the remaining transitions before τk _k are deterministic or connect states with the same optimal safe value. Hence, pathwise, Σ=∑k=1K∑i=1dpi,k(1−pi,k)ρ2.V_ = _k=1^K _i=1^dp_i,k(1-p_i,k)ρ^2. Since pi,k∈1/2,1/2+εp_i,k∈\1/2,1/2+ \, (1−4ε2)Kv≤Σ≤Kv(1-4 ^2)Kv _ ≤ Kv. The bound ε2≤1/128 ^2≤ 1/128 proves (G.2). Regret. Each choice different from ωi,s _i,s loses ερ ρ in expected reward. Since every gadget returns to x, these losses add over gadgets and episodes. We lower bound the number of such choices by averaging over the hidden actions. Fix (i,s)(i,s) and fix all hidden actions except ωi,s _i,s. Let ℙaP_a be the interaction distribution when ωi,s=a _i,s=a, and let ℙ0P_0 be the reference distribution in which every action at this coordinate reaches g with probability 1/21/2. All other transition, reward, and cost distributions are unchanged. Write aE_a and 0E_0 for the corresponding expectations, and define Na(k):=∑ℓ=1ks3i−1ℓ=cs,a3i−1ℓ=a.N_a(k):= _ =1^k1\s_3i-1 =c_s,\ a_3i-1 =a\. Let ℙak−1P_a^k-1 and ℙ0k−1P_0^k-1 denote the distributions of the history through episode k−1k-1, including the algorithm’s random choices. Write KLKL for the Kullback–Leibler divergence. The two instances differ only in the transition following action a at the fixed coordinate, and the KL divergence of one such observation is −12log(1−4ε2)≤4ε2- 12 (1-4 ^2)≤ 4 ^2. The adaptive chain rule gives KL(ℙ0k−1∥ℙak−1)≤4ε20[Na(k−1)].KL(P_0^k-1\|P_a^k-1)≤ 4 ^2E_0[N_a(k-1)]. Conditional on the history before episode k, the probability of choosing a at csc_s is determined by the algorithm’s policy distribution. The probability of reaching csc_s is 1/n1/n, independently of this choice. Applying Pinsker’s inequality to the history distributions therefore gives ℙas3i−1k=cs,a3i−1k=a≤ℙ0s3i−1k=cs,a3i−1k=a+2εn0[Na(k−1)].P_a\s_3i-1^k=c_s,\ a_3i-1^k=a\ _0\s_3i-1^k=c_s,\ a_3i-1^k=a\+ 2 n E_0[N_a(k-1)]. Summing over k and averaging over a yields 1A∑a=1Aa[Na(K)] 1A _a=1^AE_a[N_a(K)] ≤KnA+K2εnA∑a=1A0[Na(K)] ≤ KnA+ K 2 nA _a=1^A E_0[N_a(K)] ≤KnA+K2εnKnA≤5K8n. ≤ KnA+ K 2 n KnA≤ 5K8n. (G.5) The second inequality uses Cauchy–Schwarz and ∑a0[Na(K)]=K/n _aE_0[N_a(K)]=K/n. The last inequality uses the definition of ε and A≥2A≥ 2. By (G.5), averaging over all hidden actions and summing over the ndnd coordinates gives at least 3dK/83dK/8 incorrect choices in expectation. Multiplying by the loss ερ ρ gives [ℛ(K)]≥3dK8ερ=3322nAdKv.E[R(K)]≥ 3dK8 ρ= 332 2 nAdKv. The expectation here also averages over the hidden actions. Some fixed choice therefore satisfies (G.3). The variance and safety identification complexity bounds hold for every such choice. ∎ Safety identification term The second family uses the same state–step pairs, but the unknown action at each pair now determines safety. The initial gadgets supply the target variance without contributing regret. An incorrect choice at a pair in J loses the reward from the last R steps. Lemma G.2. Assume the parameter conditions of Theorem 4. For every learning algorithm following the protocol in Section 2, there exists a CMDP ℳwM_w with S states, A actions, and horizon H satisfying Assumption 1, Var⋆(ℳw)=vVar (M_w)=v, and Γ4≤(ℳw)≤Γ2 4 (M_w)≤ 2. On this instance, Σ=KvV_ =Kv for every realized interaction sequence. The algorithm’s expected regret on ℳwM_w satisfies ℳw[ℛ(K)]≥1512Dm.E_M_w[R(K)]≥ 1512 Dm. (G.6) Proof. Construction. Use d action-independent gadgets in the first 3d3d steps. In gadget i, every action at x moves to c1c_1 at step 3i−23i-2, and every action at c1c_1 moves to g or b, each with probability 1/21/2, at step 3i−13i-1. At step 3i3i, the rewards are ρ:=2v/dρ:=2 v/d at g and zero at b, and both states return to x. These rewards lie in [0,1][0,1] because v≤d/4v≤ d/4. Choose (θj)j∈( _j)_j independently and uniformly from [A][A]. At pair j, action θj _j has cost zero and moves to g. Every other action has cost one and moves to b. Both states have zero reward until the last R steps. At each of those steps, the reward is Δr/R _r/R at g and zero at b, where Δr:=D/m _r:= D/m. The bounds R≥H/10R≥ H/10, m≥16SA/Hm≥ 16SA/H, and D≤SAH/16D≤ SAH/16 imply D≤R2mD≤ R^2m, so Δr/R≤1 _r/R≤ 1. A policy choosing θj _j at every pair j is safe, which proves Assumption 1. Instance properties. The initial gadgets contribute dρ2/4=vdρ^2/4=v to the return variance of every policy. Under every safe policy, the value is Δr _r at each pair in J and at x whenever x is reached after the gadgets. The action chosen at each pair moves deterministically to g. Thus the later steps contribute zero variance, and Var⋆(ℳw)=vVar (M_w)=v. The only unsafe actions are the M(A−1)M(A-1) incorrect actions at these pairs. Every pair is reachable under a safe policy, and each incorrect action has cost gap 1/21/2, so (ℳw)=4M(A−1)∈[Γ/4,Γ/2]C(M_w)=4M(A-1)∈[ /4, /2]. The initial gadgets lie in the true safe graph and occur before every pair in J. Each contributes ρ2/4=v/dρ^2/4=v/d to ΣV_ in every episode. All rewards are deterministic. Under V⋆V , every pair in J has continuation value Δr _r, while safe actions at these pairs and all subsequent transitions are deterministic. Hence Σ=KvV_ =Kv for every realized interaction sequence. Regret. An incorrect action at a pair in J loses Δr _r in reward. We bound the number of incorrect choices, first averaging over the hidden actions. Let Tj(t)T_j(t) count visits to pair j in the first t episodes, set Tj:=Tj(K)T_j:=T_j(K), and let WjW_j count choices different from θj _j over the K episodes. Fix the sequence of reached pairs, all other hidden actions, the algorithm’s random seed, and the transition randomness in the initial gadgets. Consider the actions tested at j along the hypothetical history in which each test there has cost one and moves to b. List the distinct actions in the order in which they are first tested, stopping once all A actions have been listed or the visits end. Append any untested actions in a fixed order. This ordering is independent of θj _j, and the actual history agrees with the hypothetical one until θj _j is first tested. Also, TjT_j depends only on the sequence of reached pairs. Conditional on Tj=qT_j=q, the rank of θj _j is therefore uniform on [A][A]. If that rank is r, at least minq,r−1 \q,r-1\ choices are incorrect; repeated tests cannot reduce this number. Averaging over the rank gives [Wj∣Tj=q]≥1A∑r=1Aminq,r−1≥14minq,A−1.E[W_j T_j=q]≥ 1A _r=1^A \q,r-1\≥ 14 \q,A-1\. (G.7) It remains to bound the total number of visits before individual counts reach A−1A-1. Let JkJ_k be the pair reached in episode k. Pathwise, ∑j∈minTj,A−1=∑k=1KTJk(k−1)<A−1. _j \T_j,A-1\= _k=1^K1\T_J_k(k-1)<A-1\. By (G.1), JkJ_k is uniform on J conditional on the past. Since ∑jTj(k−1)=k−1 _jT_j(k-1)=k-1, we have [TJk(k−1)]=(k−1)/ME[T_J_k(k-1)]=(k-1)/M. For k≤minK,⌊M(A−1)/2⌋k≤ \K, M(A-1)/2 \, Markov’s inequality therefore bounds the expectation of each corresponding indicator from below by 1/21/2. Since M(A−1)≥2M(A-1)≥ 2, ⌊M(A−1)/2⌋≥M(A−1)/4 M(A-1)/2 ≥ M(A-1)/4, and hence [∑j∈minTj,A−1]≥18minK,M(A−1)≥m128.E\! [ _j \T_j,A-1\ ]≥ 18 \K,M(A-1)\≥ m128. (G.8) The last inequality uses M(A−1)≥Γ/16M(A-1)≥ /16 and minK,M(A−1)≥m/16 \K,M(A-1)\≥ m/16. Combining (G.7) and (G.8) with the loss Δr _r per incorrect choice gives [ℛ(K)]=Δr∑j∈[Wj]≥Δrm512=1512Dm.E[R(K)]= _r _j E[W_j]≥ _rm512= 1512 Dm. The expectation also averages over the hidden actions, so some fixed choice satisfies (G.6). The variance and safety identification complexity bounds hold for every such choice. ∎ Proof of Theorem 4. By Lemmas G.1 and G.2, both instances lie in the required ranges of Var⋆Var and C. The instance ℳvM_v satisfies 31Kv/32≤Σ≤Kv31Kv/32 _ ≤ Kv for every realized interaction sequence, while ℳwM_w satisfies Σ=KvV_ =Kv. Thus either instance satisfies the stated range for ΣV_ . Choose ℳ=ℳvM=M_v when the right-hand side of (G.3) is at least that of (G.6), and choose ℳ=ℳwM=M_w otherwise. Then ℳ[ℛ(K)] _M[R(K)] ≥max3322nAdKv,1512Dm ≥ \! \ 332 2 nAdKv, 1512 Dm \ =Ω(SAHKv+SAHminK,Γ). = \! ( SAHKv+ SAH \K, \ ). The assumptions of Theorem 4 give n≥5S/8n≥ 5S/8, d≥H/20d≥ H/20, and D≥SAH/64D≥ SAH/64. Substituting these bounds and using maxx,y≥(x+y)/2 \x,y\≥(x+y)/2 gives the final line. ∎ G.2 Lower Bounds for Action Elimination We next prove the elimination lower bound discussed in Section 3.3. The learner must distinguish an unsafe root from alternatives in which changing one leaf makes it safe. This gives a lower bound on the required leaf observations, which we convert into root executions. Instances and alternatives Fix δ∈(0,1/4]δ∈(0,1/4] and τ=1/2τ=1/2, and consider an instance ℳM with an unsafe root u=(s,a,h)u=(s,a,h). Use the witness-tree representation in Lemma C.2. Let ℒuL_u be its leaves and, for ℓ∈ℒu _u, let Δℓ _ be its cost gap and qℓ>0q_ >0 the product of the transition probabilities on its path. Assume the following conditions on the tree and its observations. (i) Every nonterminal action satisfies the immediate cost constraint and has exactly one non-viable successor. All its other successors are viable. The root state has another action in safe,h(s)A_safe,h(s). (i) Each nonroot state–step pair in the tree can be reached only through its designated parent action. Different branches use disjoint state–action pairs at each step. (i) At every leaf ℓ , 0<Δℓ≤1/40< _ ≤ 1/4, all successors are viable, and the cost has distribution Bernoulli(1/2+Δℓ)Bernoulli(1/2+ _ ). Define ℳℓM by replacing this cost distribution with Bernoulli(1/2−Δℓ)Bernoulli(1/2- _ ) and leaving all other observations unchanged. (iv) In ℳM and ℳℓM , conditional on the leaf state–action pair, the cost is independent of the pair consisting of the reward and next state. The reward and next state have the same joint distribution in both instances. By Lemma C.2, κh(s,a)=∑ℓ∈ℒu1qℓΔℓ2. _h(s,a)= _ _u 1q_ _ ^2. (G.9) The leaf action is safe in ℳℓM . At its parent, this provides a safe action at the previously non-viable successor, while all other successors were already viable. Repeating this argument makes every ancestor action, including u, safe. Elimination rules The learner chooses its policy before each episode, as in Section 2. An elimination rule removes u at an episode boundary and never executes it afterward. Let σu∈0,1,…∪∞ _u∈\0,1,…\∪\∞\ be the number of completed episodes when it is removed, and let Nu(t)N_u(t) count its executions through the end of episode t. Thus σu≥k\ _u≥ k\ is known before episode k begins. Write kl(p,q):=plog(p/q)+(1−p)log((1−p)/(1−q))kl(p,q):=p (p/q)+(1-p) ((1-p)/(1-q)). Terms with zero numerator are zero, and a positive numerator divided by zero contributes +∞+∞. The rule is δ-valid at u if ℙℳ(σu<∞) _M( _u<∞) ≥1−δ, ≥ 1-δ, (G.10) ℙℳℓ(σu<∞) _M ( _u<∞) ≤δ(ℓ∈ℒu). ≤δ ( _u). Lemma G.3 (Elimination lower bound). Consider the instance ℳM and alternatives ℳℓM , ℓ∈ℒu _u, satisfying conditions (i)–(iv) above. Every δ-valid elimination rule at u, as defined in (G.10), satisfies ℳ[Nu(σu)]≥132κh(s,a)log12δ.E_M[N_u( _u)]≥ 132 _h(s,a) 12δ. (G.11) Proof. Leaf observations. Fix ℓ∈ℒu _u, and let Nℓ(t)N_ (t) count observations of its cost through episode t. By condition (iv), the KL divergence of the full observation at this leaf equals that of its Bernoulli cost. For 0<Δℓ≤1/40< _ ≤ 1/4, kl(1/2+Δℓ,1/2−Δℓ)=2Δℓlog1+2Δℓ1−2Δℓ≤16Δℓ2,kl(1/2+ _ ,1/2- _ )=2 _ 1+2 _ 1-2 _ ≤ 16 _ ^2, where the inequality uses log((1+x)/(1−x))≤4x ((1+x)/(1-x))≤ 4x for x∈[0,1/2]x∈[0,1/2]. Let En:=σu≤nE_n:=\ _u≤ n\, and stop the interaction history at the end of episode σu∧n _u n. The stopped history, including the elimination decision, determines EnE_n. Since only the cost at leaf ℓ differs between the instances, the chain rule expresses the KL divergence of the stopped histories as the expected leaf count times the single-observation divergence. Data processing then gives 16Δℓ2ℳ[Nℓ(σu∧n)]≥kl(ℙℳ(En),ℙℳℓ(En)).16 _ ^2E_M[N_ ( _u n)] \! (P_M(E_n),P_M (E_n) ). Set p:=ℙℳ(σu<∞)p:=P_M( _u<∞) and q:=ℙℳℓ(σu<∞)q:=P_M ( _u<∞). Letting n tend to infinity, monotone convergence and lower semicontinuity give 16Δℓ2ℳ[Nℓ(σu)]≥kl(p,q)≥kl(1−δ,δ),16 _ ^2E_M[N_ ( _u)] (p,q) (1-δ,δ), (G.12) where the last inequality uses p≥1−δ>δ≥qp≥ 1-δ>δ≥ q and the monotonicity of binary KL. Root executions. For each execution of u, the fixed episode policy determines a path through the witness tree before any transition along that path is observed. For ℓ∈ℒu _u, let Tℓ(t)T_ (t) count executions assigned to the path ending at ℓ through episode t. For every n, ℳ[Nℓ(σu∧n)] _M[N_ ( _u n)] =qℓℳ[Tℓ(σu∧n)], =q_ E_M[T_ ( _u n)], Nu(σu∧n) N_u( _u n) =∑ℓ∈ℒuTℓ(σu∧n). = _ _uT_ ( _u n). To obtain the first identity, include episode k exactly when σu≥k _u≥ k, an event known before that episode. Conditional on an execution assigned to leaf ℓ , all transitions on its path occur with probability qℓq_ . Condition (i) ensures that every observation at the leaf comes from this path. The second identity holds because each root execution is assigned to exactly one leaf. Letting n tend to infinity and applying monotone convergence yields ℳ[Nu(σu)] _M[N_u( _u)] =∑ℓ∈ℒuℳ[Nℓ(σu)]qℓ = _ _u E_M[N_ ( _u)]q_ ≥116kl(1−δ,δ)∑ℓ∈ℒu1qℓΔℓ2 ≥ 116kl(1-δ,δ) _ _u 1q_ _ ^2 =116κh(s,a)kl(1−δ,δ). = 116 _h(s,a)kl(1-δ,δ). The inequality uses (G.12), and the last equality uses (G.9). Finally, since δ≤1/4δ≤ 1/4, kl(1−δ,δ)=(1−2δ)log1−δ≥12log12δ.kl(1-δ,δ)=(1-2δ) 1-δ≥ 12 12δ. Substitution proves (G.11). ∎ Corollary G.1. Let U consist of all triples (s,a,h)(s,a,h) with h∈[H]h∈[H], a∉safe,h(s)a _safe,h(s), and (s,h)(s,h) reachable under a safe policy, as indexed in (8). Suppose these triples are the roots of pairwise-disjoint witness trees satisfying conditions (i)–(iv) above. For u∈u and ℓ∈ℒu _u, let ℳu,ℓM^u, be the corresponding single-leaf alternative. For a learner using the elimination rules defined above at all roots, suppose ℙℳ(⋂u∈σu<∞)≥1−δP_M\! ( _u \ _u<∞\ )≥ 1-δ, and ℙℳu,ℓ(σu<∞)≤δ(u∈,ℓ∈ℒu)P_M^u, ( _u<∞)≤δ (u , _u). Then ℳ[∑u∈Nu(σu)]≥132(ℳ)log12δ.E_M\! [ _u N_u( _u) ]≥ 132C(M) 12δ. Proof. The probability conditions imply the hypotheses of Lemma G.3 for every root. Applying (G.11) to every root and summing over u∈u proves the claim because ∑u=(s,a,h)∈κh(s,a)=(ℳ) _u=(s,a,h) _h(s,a)=C(M). ∎ Appendix H Experiments In this section, we conduct experiments to illustrate our theoretical findings and evaluate the performance of our algorithm. We focus on the following four questions: Q1: How does SVAE compare with baselines in regret and step-wise violation? Q2: Can SVAE exploit low return variance induced by safety constraints? Q3: Can safety identification remain difficult when safe-policy return variance is zero? Q4: Does recursive elimination exclude unsafe branches while preserving safe continuations? Appendix H.1 describes the experimental setup and baselines. We evaluate regret and step-wise violation on stochastic navigation tasks in Appendix H.2 (Q1). We then study variance adaptation, safety identification complexity, and recursive elimination using controlled CMDPs in Appendices H.3–H.5 (Q2–Q4). Hyperparameter selection and implementation details are given in Appendix H.6. H.1 Experimental Setup Learning setting The reward means, mean costs, and transition probabilities are unknown. All algorithms learn from online interaction without a known safe policy. Rewards are Bernoulli in Q1 and deterministic in Q2–Q4, where we study the safe subgraph and safety identification without reward noise. The reward means remain fixed throughout learning. Costs are Bernoulli with mean ch(s,a)c_h(s,a), and next states follow the transition kernel. Estimates are maintained separately for each (h,s,a)(h,s,a). We set τ=0.6τ=0.6, δ=0.05δ=0.05, and run each algorithm for K=10,000K=10,000 episodes. Baselines For navigation (Q1), we compare SVAE with SUCBVI [Xiong et al., 2023]. Both methods use the same recursive safety filter, so the comparison focuses on their planning rules. Our SUCBVI implementation estimates unknown rewards and costs separately for each (h,s,a)(h,s,a). We also include MVP-V [Zhou et al., 2023b] and a variant with the recursive safety filter applied at every episode, denoted by MVP-V + filter. Ablations We consider two variants of SVAE with Hoeffding-type bonuses. SVAE (Hoeffding) replaces the empirical reward and transition variances in (10) with 1/41/4 and (H−h)2/4(H-h)^2/4, respectively. SVAE (Hoeffding-P) replaces only the transition variance, with P denoting the transition component. Both retain the finite-sample correction and recursive safety filter. We also consider SVAE w/o propagation, which retains variance-adaptive planning but eliminates actions only through their own cost lower confidence bounds. Q2 compares SVAE with both bonus variants, and Q4 compares it with the variant without propagation. Q3 evaluates SVAE as the environment parameters vary. Metrics We evaluate regret using exact policy values and the optimal safe value. Step-wise violation is the cumulative positive excess of mean costs over the threshold along sampled trajectories, as defined in Section 2. The true model and safe sets are used only for offline tuning and evaluation. For navigation, we also report the strong regret [Stradi et al., 2025b] ℛ+(K):=∑k=1K[V1⋆(s1)−V1πk(s1)]+R_+(K):= _k=1^K[V_1 (s_1)-V_1^π^k(s_1)]_+, which does not allow cancellation across episodes. We track policy value and expected violation per episode using a moving average over up to 500 episodes. We use the same observation streams and state/action relabelings to pair methods. For navigation (Q1), we average five paired seeds within each of eight independent environments, then average across environments. Each condition in Q2–Q4 uses 20 seeds. We report means with sample standard deviations (SDs) in parentheses. SDs are computed across environment means for Q1 and across seeds for Q2–Q4. Shading indicates one SD around the mean, with lower bounds clipped at zero for nonnegative metrics. We tune all navigation methods with the same search budget on separate development and validation environments, then fix their hyperparameters before testing. SVAE and its ablations use the same planning and cost-confidence multipliers in the controlled experiments. Appendix H.6 gives the tuning procedure and selected values. H.2 Stochastic Navigation We first compare the regret and step-wise violation of SVAE and the baselines in a 5×55× 5 gridworld with four movement actions and horizon 2020. The agent starts at the middle-left cell, and the middle-right cell is an absorbing goal. At each step, rewards are sampled independently from a Bernoulli distribution with mean 0.90.9 at the goal and 0.10.1 elsewhere. Reward noise is independent of costs and transitions. Each episode lasts H steps, with the agent remaining at the goal after reaching it. For each state–action pair, we sample the probability of the intended move uniformly from [0.8,0.95][0.8,0.95] when generating the environment. With the remaining probability, the agent moves in either perpendicular direction with equal probability. Attempts to move outside the grid leave the agent in the same cell. An action has mean cost in [0.7,0.85][0.7,0.85] if it can cross the boundary between columns 3 and 4 in rows 2–4. All other non-goal actions have mean costs in [0.15,0.3][0.15,0.3], and the cost at the goal is zero. Figure 3: Regret and safety in stochastic navigation. Panels (a) and (b) show strong regret and cumulative step-wise violation. Panels (c) and (d) show policy value and expected violation per episode, using a moving average over up to 500 episodes. At k=0k=0, we evaluate the initial policy. Curves show means across eight environments after averaging five paired seeds per environment. Shaded areas show one SD across environment means. The horizontal line in (c) marks the mean optimal safe value. Results Compared with SUCBVI, SVAE reduces final strong regret by 44.9%44.9\% and cumulative step-wise violation by 7.7%7.7\% (Table 1). The mean (SD) paired differences, computed as SVAE minus SUCBVI, are −1,162.23-1,162.23 (947.46947.46) for ℛ+R_+ and −119.70-119.70 (45.1045.10) for violation. Table 1: Regret and step-wise violation in stochastic navigation. We report cumulative regret, strong regret, and step-wise violation at K=10,000K=10,000. Entries are means (SDs) across eight environments after averaging five paired seeds per environment. Bold numbers mark the lowest mean in each column, including ties at the displayed precision. Method ℛ(K)/103R(K)/10^3 ℛ+(K)/103R_+(K)/10^3 Viol(K)/103Viol(K)/10^3 SVAE -2.406 (0.947) 1.428 (0.112) 1.426 (0.132) SUCBVI 0.150 (1.707) 2.590 (1.037) 1.546 (0.121) MVP-V + filter 45.989 (1.973) 46.756 (1.776) 3.005 (0.124) MVP-V 31.238 (9.735) 34.020 (9.161) 2.816 (0.246) SVAE’s expected violation per episode decreases from 0.3830.383 in the first 500 episodes to 0.04740.0474 in the last 500 (Figure 3). Over the last 500 episodes, its mean policy value is 10.55310.553, above the average optimal safe value of 10.47610.476 while some constraint violation remains. Unconstrained MVP-V reaches a higher mean policy value of 11.20611.206 over the last 500 episodes, with greater expected violation of 0.29610.2961 per episode. H.3 Variance Adaptation To study whether SVAE can exploit low return variance in an unknown safe subgraph, we use a two-step CMDP with eight states and four actions. The reward at the root is zero. Each of three root actions leads to two possible second-step states with probability 1/21/2 each. The corresponding reward pairs are (0.4,0.4)(0.4,0.4), (0.25,0.55)(0.25,0.55), and (0.1,0.7)(0.1,0.7). The fourth root action gives a deterministic return of 0.50.5. All three branching actions are available in every instance. We keep rewards and transitions fixed and vary costs to select the safe branch. The selected branching action and the deterministic action have mean cost 0.20.2, while the other two root actions have mean cost 0.80.8. All second-step mean costs are 0.20.2. Thus, the optimal safe value is 0.50.5, the expected-return gap between the two safe root actions is 0.10.1, and =50C=50 in every instance. Let u∈0,0.15,0.30u∈\0,0.15,0.30\ denote half the reward difference on the safe branch. Then S⋆=2uS =2u, Var⋆=u2Var =u^2, and B(safe)=1B(G_safe)=1. The safe branching policy attains the variance bound in Theorem 1. When u=0u=0, both successor states have the same value, so the transition variance is zero despite the random next state. This is the zero-span case of Corollary 1. Figure 4: Regret under different safe-policy return variances. The three panels compare SVAE with its Hoeffding-type variants as Var⋆Var varies. Curves show means over 20 paired seeds, with shading indicating one SD. The episode axes use a logarithmic scale. Results SVAE has lower final regret on average than both Hoeffding-type variants in all three conditions (Figure 4 and Table 2). Compared with SVAE (Hoeffding-P), SVAE selects suboptimal branching actions 1.101.10–1.201.20 fewer times on average. This comparison isolates the effect of using empirical next-state value variance in the transition bonus, as both methods share the reward-variance estimates and safety filter. Table 2: Accumulated variance and regret differences. We report SVAE’s accumulated variance ΣV_ and paired regret differences at K=10,000K=10,000 as means (SDs) over 20 seeds. Each difference Δℛ(K) (K) is SVAE’s regret minus the regret of the indicated Hoeffding-type variant. Δℛ(K) (K) Var⋆Var KVar⋆KVar ΣV_ Hoeffding-P Hoeffding 0 0 0.000 (0.000) −0.110-0.110 (0.031) −0.460-0.460 (0.268) 0.0225 225 0.739 (0.263) −0.115-0.115 (0.198) −0.560-0.560 (0.376) 0.09 900 2.691 (1.078) −0.120-0.120 (0.202) −0.495-0.495 (0.386) The optimal safe action gives a deterministic return even when another safe action has positive return variance. As SVAE increasingly selects the optimal action, the variance it accumulates can therefore be much smaller than KVar⋆KVar . Let a⋆a and aba_b denote the deterministic optimal and safe branching root actions, respectively. Following Appendix B.1, N1K+1(s1,a)N_1^K+1(s_1,a) is the number of times action a is taken at the root in the first K episodes. Each branching action has an expected return 0.10.1 below that of a⋆a . Only aba_b contributes to ΣV_ , since this sum ends before the first unsafe action. Hence, ℛ(K)=0.1∑a≠a⋆N1K+1(s1,a),Σ=u2N1K+1(s1,ab).R(K)=0.1 _a≠ a N_1^K+1(s_1,a), _ =u^2N_1^K+1(s_1,a_b). SVAE’s mean ΣV_ is about 0.3%0.3\% of KVar⋆KVar in both conditions with positive variance (Table 2). In these instances, the term minΣ,KVar⋆ \V_ ,KVar \ in Theorem 2 reflects the smaller variance along the learning trajectory. H.4 Safety Identification Complexity We study safety identification in a two-step CMDP with four states and two actions. At the root, one action is safe and gives a return of 0.40.4. The other gives a return of 0.50.5 but reaches a state with no safe action with probability p. Both actions at this successor have mean cost τ+Δcτ+ _c, while all other mean costs are 0.20.2. The root action with the higher return is therefore unsafe because it can reach a state with no safe continuation. Every safe policy has a deterministic return, so Var⋆=0Var =0. By (7), the identification complexity is =2/(pΔc2)C=2/(p _c^2). We vary p with Δc=0.2 _c=0.2 fixed, then vary Δc _c with p=0.2p=0.2 fixed. We measure how often the unsafe root action is taken and how often its non-viable successor is visited. Figure 5: Effect of transition probability on safety identification. Panel (a) shows the mean cumulative number of times the unsafe root action is taken, with shading indicating one SD. Panel (b) shows the fraction of runs in which this action has not yet been excluded. For each p, we use 20 paired seeds and fix Δc=0.2 _c=0.2. Both episode axes use a logarithmic scale. Results As p decreases from 0.400.40 to 0.050.05, the mean number of times the unsafe root action is taken increases from 117.1117.1 to 931.9931.9 (Figure 5). The mean number of visits to the successor remains 46.546.5, and cumulative violation remains 9.299.29 (Table 3). For each paired seed, all four conditions require the same number of cost observations at the successor. A smaller transition probability increases the number of interactions needed to collect these observations, as reflected by the reachability factor in (7). Table 3: Effect of transition probability and cost gap on safety identification. We report executions of the unsafe root action, visits to its non-viable successor, and cumulative step-wise violation at K=10,000K=10,000. Entries are means (SDs) over 20 seeds. The two parameter sweeps use separate seed sets. Bold rows mark the lowest identification complexity C in each sweep. p Δc _c C Root executions Successor visits Viol(K)Viol(K) Varying the successor probability (Δc=0.20 _c=0.20) 0.40 0.20 125.0 117.1 (57.8) 46.5 (21.3) 9.29 (4.27) 0.20 0.20 250.0 230.1 (112.1) 46.5 (21.3) 9.29 (4.27) 0.10 0.20 500.0 471.0 (231.5) 46.5 (21.3) 9.29 (4.27) 0.05 0.20 1,000.0 931.9 (535.4) 46.5 (21.3) 9.29 (4.27) Varying the cost gap (p=0.20p=0.20) 0.20 0.10 1,000.0 1,056.9 (599.7) 214.1 (126.0) 21.41 (12.60) 0.20 0.15 444.4 591.7 (391.5) 118.7 (82.5) 17.81 (12.37) 0.20 0.20 250.0 296.2 (123.0) 59.3 (26.4) 11.85 (5.28) 0.20 0.30 111.1 126.7 (40.6) 26.0 (6.9) 7.79 (2.07) Reducing the cost gap increases the number of observations needed at the successor. With p=0.2p=0.2 fixed, decreasing Δc _c from 0.300.30 to 0.100.10 increases the mean number of successor visits from 26.026.0 to 214.1214.1. Root-action executions and cumulative violation also increase. Together, the two sweeps show how rare successors and small cost gaps increase C at zero safe-policy return variance, illustrating the separate safety identification term in Theorem 2. In every tested condition, SVAE excludes the unsafe root action within the episode budget and never takes it afterward. Cumulative violation then remains constant, consistent with the positive-gap bound in Theorem 3. H.5 Recursive Elimination We study recursive elimination by comparing SVAE with SVAE w/o propagation in a five-step CMDP with three states, two actions, and deterministic transitions. The two branches give returns of 0.40.4 and 11. On the branch with the higher return, the state reached after d=3d=3 transitions has two actions with mean cost 0.80.8. All other costs are zero. An otherwise identical instance sets one of these two costs to zero, leaving a safe continuation. Both instances have Var⋆=0Var =0. We define detection as the first time the cost lower confidence bounds of both actions at the later state exceed τ. We count entries into the branch with the higher return after detection. Figure 6: Recursive elimination at propagation distance d=3d=3. Panel (a) shows cumulative entries into the unsafe branch after detection. Panel (b) shows cumulative regret when the branch has a safe continuation, with a logarithmic episode axis. Curves show means over 20 paired seeds, with shading indicating one SD. The two methods have identical regret in (b) for every paired seed. Results At d=3d=3, SVAE excludes the root action in the same backward pass that detects the absence of a safe continuation. It never enters the branch after detection in any of the 20 runs (Figure 6a). The variant without propagation continues to enter the branch, with 9,910.059,910.05 entries after detection on average. SVAE incurs cumulative violation of 11.9911.99, compared with 1,994.001,994.00 for the ablation. The d=1d=1 condition gives the same result: zero entries after detection for SVAE and 9,921.959,921.95 for the ablation. Recursive elimination uses evidence from the later state to exclude the root action, illustrating the control of unsafe candidate selections in Lemma C.3. When one action at the later state remains safe, SVAE retains the branch. SVAE and the ablation follow the same trajectories, with final regret 18.0018.00 and zero violation over the last 500 episodes (Figure 6b). SVAE’s recursive update excludes the branch only when both downstream actions have been ruled out. H.6 Additional Experimental Details Hyperparameter selection We scale the planning bonus by α and the cost-confidence radius by β. For navigation, each method is evaluated with 18 configurations. Methods with safety filtering use six planning multipliers combined with three cost-confidence multipliers, while unconstrained MVP-V uses 18 planning multipliers. To be eligible, configurations with safety filtering must have mean expected violation of at most 0.020.02 per step. They must also retain all truly safe actions and keep a nonempty candidate set at every visited state that admits a safe continuation. Eligible configurations are ranked by increasing strong regret ℛ+R_+, and unconstrained MVP-V configurations by decreasing policy value. We first evaluate all configurations on two development environments with two seeds per environment. The best three are then evaluated on two separate validation environments, again with two seeds per environment. Both stages use K=10,000K=10,000 episodes. After validation, we select the best configuration and fix its hyperparameters before testing. For navigation, (α,β)(α,β) is (0.0003,0.30)(0.0003,0.30) for SVAE and (0.001,0.30)(0.001,0.30) for SUCBVI. MVP-V + filter uses (3×10−6,0.30)(3× 10^-6,0.30), and unconstrained MVP-V uses α≃2.405×10−6α 2.405× 10^-6. In Q2–Q4, SVAE and its ablations use the same empirically chosen coefficients, (α,β)=(0.003,0.17)(α,β)=(0.003,0.17). The complete search grids, coefficients, and random seeds are included with the code. Implementation For MVP-V, we treat each state–step pair as a separate state and normalize rewards by H. The empirical model is updated whenever a visit count doubles. We report results on the original reward scale. For paired comparisons, we compute the difference between the two methods’ results for each paired seed. For navigation, we average these differences over the five seeds within each environment, then report the mean (SD) across the eight environments.