PaperlayerView exact revision on arXiv

Source-linked AI summary

Instance-Dependent Regret for CMDPs with Step-Wise Constraints

Qian Zuo, Francesco Emanuele Stradi, Leyang Xue, Sattar Vakili

arXiv:2610.02520v1cs.LGcs.AI

TL;DR

Under step-wise safety constraints, it remains open whether learning can achieve variance-dependent regret with sublinear violation and how the induced safe subgraph shapes learning complexity. The paper characterizes this structure and proposes SVAE, which learns candidate safe actions and plans with variance-adaptive bonuses. Its guarantees include polylogarithmic dependence on K in specified low-variance and positive-cost-gap cases.

  • Problem

    The paper asks whether efficient variance-dependent regret with sublinear step-wise violation is possible, and how the safe subgraph shapes learning complexity.

    Source: §1 · p. 2

  • Method

    SVAE learns candidate safe actions using cost lower confidence bounds and observed successors, then plans optimistically with empirical reward and transition variances.

    Source: §1 · p. 2

  • Results

    Regret is polylogarithmic in K when Var⋆ = 0, while step-wise violation is polylogarithmic in K for a fixed positive cost gap.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The analysis separates safe-policy return variance from reward-independent safety-identification complexity as instance-specific contributors to regret.

    Source: §1 · p. 2, §3.3 · p. 7

    The gap-dependent violation guarantee assumes a positive cost gap separating every above-threshold cost from the threshold.

    Source: §5.1 · p. 9

Abstract

from arXiv · show

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.

1 Introduction

The paper asks whether variance-dependent learning can be retained under step-wise safety constraints, where unknown costs make exploration unsafe and the safe subgraph shapes learning difficulty. It characterizes that structure, proposes SVAE, and reports instance-dependent guarantees.

1 Introduction

  • Step-wise safety motivates online learning guarantees that adapt to safe-policy variance while controlling cumulative positive cost excesses.The paper asks whether efficient variance-dependent regret and sublinear cumulative step-wise violation are achievable, and how the safe subgraph shapes learning complexity.Source: §1 · pp. 1–2
  • SVAE learns candidate safe actions with cost lower confidence bounds and observed successors, then plans optimistically using empirical reward and transition variances.Its candidate sets retain all safe actions with high probability, enabling variance-adaptive exploration without prior knowledge of a safe policy.Source: §1 · p. 2
  • The paper defines Var⋆ as maximum total-return variance over safe policies and VΣ as reward and transition variance accumulated before the first unsafe action.It also bounds transition variance using stochastic branching depth and differences in expected cumulative rewards across safe-subgraph successor states.Source: §1 · p. 2
  • C measures the reward-independent difficulty of ruling out unsafe actions at states reachable under safe policies, and valid-elimination lower bounds establish its necessity.The safe subgraph can remove stochastic branches or reduce successor-value differences, while small cost gaps and rare unsafe-state transitions can hinder safety identification.Source: §1 · p. 2
  • Regret is polylogarithmic in K when Var⋆ = 0, and step-wise violation is polylogarithmic in K for a fixed positive cost gap.The paper also reports worst-case dependence for regret and cumulative step-wise violation.Source: §1 · p. 2
  • The paper’s regret lower bound shows that dependence on both return variance and safety-identification difficulty is unavoidable.These are distinct instance-specific sources of learning difficulty.Source: §1 · p. 2

1.1 Related Work

  • Prior safe-RL work differs in constraint setting and assumptions: this paper studies unknown state-action costs and requires only an initial safe policy.Related variance-dependent CMDP work addresses episode-level constraints; graph-structured work has used known transition supports and a known seed safe subgraph.Source: §1.1 · p. 3

2 Problem Formulation

The formulation is an episodic tabular CMDP with a known safety threshold and potentially unknown rewards, costs, and transitions. It defines safe policies through a backward-recursive safe subgraph and evaluates regret against the optimal safe policy alongside cumulative step-wise violation.

2 Problem Formulation

  • An episodic CMDP has state and action spaces of sizes S and A, horizon H, transition kernel P, reward r, cost c, and safety threshold τ.Rewards and costs are bounded in [0, 1]; the threshold is known, while transitions and costs are unknown.Source: §2 · pp. 3–4
  • The learner chooses a policy before each of K episodes, each starting from the fixed initial state, and then observes rewards, costs, and transitions along its trajectory.The optimal safe policy is the comparator for cumulative regret.Source: §2 · pp. 3–4
  • The safe subgraph is built backward: an action is safe when its mean cost is at most τ and every possible successor vertex is safe.A policy is safe when its positive-probability trajectory subgraph lies within the safe subgraph.Source: §2 · p. 4
  • Cumulative step-wise violation sums positive mean-cost excesses without allowing excess at one step to be offset by lower costs at another.Violations during exploration are allowed but their cumulative magnitude is controlled.Source: §2 · p. 4
  • The general feasibility condition is that the initial state admits a safe policy, which need not be known to the learner.The goal is high-probability sublinear regret and violation, with regret adapting to safe-policy variance and the difficulty of identifying unsafe actions.Source: §2 · p. 4

3 Safety-Induced Variance and Identification Complexity

Step-wise safety shapes both reward uncertainty within the safe subgraph and the difficulty of identifying that subgraph. The section separates these effects into variance measures, structural controls on transition variance, and safety-identification complexity.

3.1 Variance under Step-Wise Safety

  • Safe-policy return variance measures the largest total-return variance among safe policies, while trajectory-based total variance sums variances encountered before the learner first selects an unsafe action.The trajectory-based measure depends on realized interaction and captures local reward and transition uncertainty; the two measures capture different aspects and neither generally subsumes the other.Source: §3.1 · p. 5

3.2 Structure of the Safe Subgraph and Transition Variance

  • Transition variance is controlled by stochastic branching depth and successor-value spans: fewer stochastic transitions and smaller continuation-value differences limit its contribution.The bound is tight for a family of CMDPs that share rewards and transitions but differ in costs.Source: §3.2 · pp. 5–6

3.3 Safety Identification Complexity

  • Even when a safe subgraph has low transition variance, a rare non-viable branch can make it difficult to identify, and valid elimination rules incur unavoidable sample costs.For pairwise-disjoint trees, the required expected executions add to Ω(C log(1/δ)).Source: §3.3 · pp. 6–7
  • Safety identification complexity captures the effort required to rule out unsafe actions at reachable safe-subgraph boundaries, independently of reward uncertainty.An unsafe action can be excluded through a cost gap or a non-viable successor; rare successors increase the executions needed to discover non-viability.Source: §3.3 · p. 7

4 Safe Variance-Adaptive Exploration

SVAE learns an optimistic candidate safe subgraph and performs optimistic planning with bonuses adapted to empirical reward and transition variance. Its design uses variance-independent cost bounds for safety learning and variance-adaptive bonuses for reward exploration.

4 Safe Variance-Adaptive Exploration

  • SVAE combines variance-independent cost lower confidence bounds for safe-subgraph learning with variance-adaptive bonuses for reward exploration.The asymmetric design addresses the possibility that empirical cost variance remains zero until a rare high-cost outcome is observed.Source: §4 · p. 7
  • With probability at least 1 − δ/8, the candidate action and state sets retain all truly safe actions and states across episodes, steps, and states.SVAE constructs these sets by backward recursion using optimistic cost estimates and observed successors.Source: §4 · pp. 7–8
  • The empirical-Bernstein exploration bonus accounts for transition and reward uncertainty through empirical variances and includes a finite-sample correction when those variances vanish.The transition term uses empirical variance in estimated next-state values, alongside empirical reward variance.Source: §4 · p. 8
  • SVAE performs optimistic Bellman updates over the learned candidate safe action sets, then executes the resulting policy and updates its statistics from observed rewards, costs, and successors.Because continuation values are planned over candidate sets learned online, the transition-variance bonus adapts to the evolving safety-induced graph.Source: §4 · p. 8

5 Learning Guarantees

SVAE’s learning guarantees make regret depend on variance and safety-identification difficulty, with cumulative step-wise constraint violation bounded separately. A lower bound shows that variance and safety identification can both contribute to regret.

5.1 Regret and Constraint Violation

  • Theorem 2 separates safety-identification cost from a variance-dependent term and can yield polylogarithmic regret on fixed instances with Var⋆ = 0.Taking the minimum of VΣ and KVar⋆ can reduce the variance-dependent term when the learner encounters low-variance trajectories.Source: §5.1 · p. 9
  • With a fixed positive cost gap, SVAE's cumulative constraint-violation bound is polylogarithmic in K.The theorem also gives a general violation bound; under Assumption 2, it states eO(SAH/∆c + S²AH²).Source: §5.1 · p. 9

5.2 Regret Lower Bounds

  • The lower bound shows that safe-policy return variance and safety-identification complexity both contribute to learning difficulty; zero variance does not eliminate regret from identifying safe actions.The construction sets Var⋆ in [3v/4, v] and C = Θ(Γ), and establishes a lower bound on expected regret.Source: §5.2 · p. 10

A Additional Related Work

  • Unlike sample-complexity analyses based on feasibility margins, long-run dynamics, or occupancy-measure structure, safety-identification complexity measures ruling out unsafe actions using local costs and successor evidence.Source: A Additional Related Work · p. 15

B Preliminaries

  • A state is viable at step h when it belongs to Vsafe,h; the appendix fixes this terminology before describing its estimates and proof.Source: B Preliminaries · p. 16

B.1 Empirical Estimates

  • SVAE uses observations from earlier episodes to compute candidate sets, bonuses, values, and a policy before each episode; a backward pass computes the updates, and new observations update the next episode’s statistics.The stated implementation uses O(KS²AH) total arithmetic operations and O(S²AH) memory.Source: §B.1 · pp. 16–17

B.2 Optimal Safe Policy

  • A deterministic policy selecting a safe action at every viable state is optimal there, and its value from the initial state is at least that of any safe policy.Source: §B.2 · p. 17

B.3 Confidence Events

  • The confidence analysis preserves safe action sets with cost and support bounds, while reward and transition bounds control optimism and Bellman residuals.The stated events satisfy P(Ecs) ≥ 1 − δ/8 and P(Eest) ≥ 1 − 9δ/16.Source: §B.3 · pp. 17–18

B.4 Proof of Lemma 1

This section develops proof tools for SVAE’s regret analysis, including candidate-set preservation and optimism, safety-identification counts, Bellman-residual bounds, and visit-count and variance bounds. These tools support a regret decomposition around the first unsafe action, reduce regret to residual sums, and relate pre-unsafe variance to safe-policy return variance.

B.4 Proof of Lemma 1

  • On Ecs, the proof establishes the safe-set inclusions and that a nonempty true safe action set implies a nonempty candidate set; the claim holds with probability at least 1 − δ/8.The argument uses the cost bound and backward induction, including the state-set inclusion at step H + 1.Source: §B.4 · p. 19

B.5 Optimism

  • On Eest, SVAE’s optimistic value is at least the safe value at every viable state, episode, and step.The proof uses backward induction, candidate-set preservation, and a transition-bonus bound that handles the optimistic value vector’s dependence.Source: §B.5 · p. 19

C Regret Analysis

  • The regret analysis separates each episode at its first action outside the true safe set, using safe-policy variance before that action and a general residual bound afterward.It also bounds episodes containing such an action using the safety-identification complexity C.Source: C Regret Analysis · p. 19

C.1 Martingale Bounds

  • Freedman-based martingale bounds provide high-probability concentration for bounded martingale differences and bounded nonnegative adapted variables.The proof applies the bounds to centered variables Y_t − μ_t and μ_t − Y_t, with conditional variance controlled by Bμ_t.Source: §C.1 · pp. 19–20

C.2 Safety Identification

  • For each unsafe candidate action, a witness tree expands its recursive safety-identification requirement into paths ending at positive cost gaps.On the stated high-probability events, the number of unsafe candidate selections is O(ικ_h(s, a)); summing these counts bounds episodes with a first unsafe action, also capped by K.Source: §C.2 · pp. 20–22

C.3 Bellman Residual Bounds

  • The residual analysis establishes separate bounds for safe actions and arbitrary actions, enabling variance-sensitive control before the first unsafe action and general control afterward.Its transition-estimation lemma converts coordinatewise transition bounds into mean and variance bounds for bounded value vectors, including data-dependent estimates.Source: §C.3 · pp. 22–24

C.4 Regret Decomposition

  • At viable states, replacing each unsafe action of the episode policy with the corresponding optimal-safe-policy action constructs a safe policy that agrees with the executed policy before its first unsafe action.The coupled trajectories agree through the state at that first unsafe step, supporting the variance-based regret decomposition.Source: §C.4 · p. 24
  • Proposition C.2 reduces reward regret on Eest to conditional expectations of residual sums.The subsequent variance analysis controls these sums and relates them to realized quantities.Source: §C.4 · p. 24, §C.5 · p. 25

C.5 Variance Bounds

  • Lemma C.7 bounds visit-count sums for fixed and episode-varying weights over realized interaction sequences.Its bounds also apply to steps h ≥ τk.Source: §C.5 · p. 25
  • The auxiliary safe policy links variance accumulated before τk to its return variance, with each episode’s variance at most H^3/3.The bound uses reward variances at most 1/4 and step-h next-state value variances at most (H − h)^2/4.Source: §C.5 · pp. 27–28
  • Lemma C.10 converts expected residuals to realized sums and bounds accumulated variances on an event of probability at least 1 − 5δ/16.The event also includes the accumulated-variance bound for steps h ≥ τk.Source: §C.5 · pp. 27–28

C.6 Proof of Theorem 2

Theorem 2's proof combines bounds based on two variance quantities and controls the remaining term through episodes containing unsafe actions. A direct-cost gap condition also bounds the safety-identification complexity in a special case.

C.6 Proof of Theorem 2

  • Episodes containing unsafe actions control the remaining eBK sum, and Young's inequality absorbs terms involving eBK or √BK.The proof moves half of the relevant term to the left and bounds the residual by an O(S^2AH^2ιLK) term.Source: §C.6 · pp. 29–30
  • Taking the minimum of the two variance-based bounds yields the regret bound on the main event.The proof bounds the variance contribution using either variance quantity, then takes the smaller bound.Source: §C.6 · p. 29

C.7 A Special Case with Direct Cost Violations

  • Under Assumptions 1 and 2, a direct cost gap Δc gives C ≤ SAH/Δc^2 when every unsafe action at a safely reachable vertex exceeds the threshold.Substituting this complexity bound into Theorem 2 yields the stated special-case result with probability at least 1 − δ.Source: §C.7 · p. 30

D Constraint Violation

The section bounds step-wise constraint violation by separating steps with nonempty candidate sets from those with empty sets. It also gives a gap-dependent bound and controls empty-set blocks through newly observed transitions.

D Constraint Violation

  • SVAE's constraint-violation analysis separates steps with nonempty candidate sets from those with empty candidate sets.The cost bound controls the first contribution, while newly observed transitions control the second.Source: D Constraint Violation · pp. 30, 32
  • For nonempty candidate sets, selected actions pass the cost test, controlling one-step violation and how often positive-gap actions are selected.The analysis also states a general and a gap-dependent violation bound; each counted execution contributes its positive cost gap.Source: D Constraint Violation · p. 31
  • The gap-dependent bound uses the positive cost gaps of state-action-step triples; a lower bound on those gaps is treated separately.The proof sums each positive gap over its counted executions.Source: D Constraint Violation · pp. 31–32
  • Empty candidate sets contribute at most S^2AH(H − 1)/2 violation on the stated event.Each empty block follows a newly observed transition, and its length is bounded by the remaining horizon.Source: D Constraint Violation · pp. 31–32

E Cost Confidence Bounds at Zero Empirical Variance

The section shows that uniformly valid cost certification needs a positive confidence radius even at zero empirical variance. It also develops safe-subgraph variance bounds and a deterministic-reward corollary.

E Cost Confidence Bounds at Zero Empirical Variance

  • At zero empirical variance, uniformly valid action removal requires a positive radius: ρn(0, δ) ≥ τ log(1/δ)/(4n) under the stated conditions.The lower bound follows from comparing cost distributions that can produce the same constant sample.Source: E Cost Confidence Bounds at Zero… · pp. 32–33

F Safe-Subgraph Variance

  • The section bounds safe-policy transition variance using successor-value spans and the safe subgraph's branching depth.It uses spans Sπ and S⋆ and counts nonzero variance terms along safe paths.Source: F Safe-Subgraph Variance · p. 33, §F.1 · p. 34

F.1 Proof of Theorem 1

  • A safe path has at most B(Gsafe) stochastic transitions, which lets the proof sum transition-variance bounds along the path.The proof also applies this path argument to steps before the first unsafe action.Source: §F.1 · p. 34

F.2 Proof of Corollary 1

  • With deterministic rewards, VΣ is bounded by K times one quarter of (S⋆)^2 B(Gsafe), while Var⋆ is at most H^2/4.The corollary combines these bounds and substitutes them into Theorem 2.Source: §F.2 · p. 34

F.3 Proof of Proposition 1

The proposition's construction varies costs while holding transitions and rewards fixed, changing which gadget transitions are safe. It demonstrates matching safe-subgraph variance quantities for instances with differing numbers of open gadgets.

F.3 Proof of Proposition 1

  • The construction varies costs on a fixed gadget-chain transition and reward structure to produce different safe subgraphs.Figure 2 depicts four cost configurations for the H = 6 example.Source: §F.3 · p. 34, Figure 2 · p. 35
  • An open gadget makes its stochastic choice transition safe, while a closed gadget leaves only a deterministic safe choice.The safe choice action in a closed gadget fails successor viability; in an open gadget, both successors are viable.Source: §F.3 · pp. 35–36
  • With b(c) open gadgets, the construction has B(Gsafe) = b(c), Sπ = 1 when b(c) > 0, and Var⋆ = b(c)/4.Choosing any number of open gadgets from zero through n gives the instances used to attain the variance bound.Source: §F.3 · p. 36

G Lower Bounds

  • The lower-bounds appendix proves the regret lower bound and studies action-elimination sample requirements under additional transition and observation conditions.Source: G Lower Bounds · p. 36

G.1 Proof of Theorem 4

The proof builds two CMDP families that make either variance learning or safety identification difficult while controlling their instance-specific quantities. It then selects the family with the larger regret lower bound.

Construction

  • Both constructions fit within the horizon using three-step gadgets, selected state–step pairs, and, for the safety family, a final reward segment.The common construction sets n = S−3 and uses d = floor(H/16) gadgets; the second family also uses R = floor(H/8) final steps.Source: §G.1 · p. 36

Variance term

  • The variance family hides a best action at each context state in each gadget, while separate cost choices at reachable pairs set safety-identification complexity.Incorrect gadget actions lose ερ in expected reward; the proof bounds the number of such choices by averaging over hidden actions.Source: §G.1 · pp. 37–38

Safety identification term

  • The safety-identification family makes an unknown action determine safety at each selected pair, with incorrect choices losing reward from the final R steps.Its initial gadgets provide target variance without adding regret; the selected pairs have M(A−1) unsafe actions with cost gap 1/2.Source: §G.1 · p. 39

Proof of Theorem 4

  • Theorem 4 chooses between two constructed CMDP families, each with controlled safe-policy variance, safety-identification complexity, and trajectory variance, to obtain the larger lower bound.The Mv family has 3v/4 ≤ Var⋆ ≤ v and 31Kv/32 ≤ VΣ ≤ Kv; Mw has Var⋆ = v and VΣ = Kv.Source: §G.1 · pp. 37, 39, 40

G.2 Lower Bounds for Action Elimination

This section lower-bounds the observations needed to eliminate an unsafe action by comparing the instance with alternatives where changing one leaf makes that action safe. It then converts leaf observations into root executions and aggregates the bound across disjoint witness trees.

Instances and alternatives

  • The lower bound compares an instance with alternatives that differ only in a leaf cost, where changing that cost makes the root action safe.The witness-tree conditions ensure leaf observations identify the relevant cost difference and that each nonroot pair is reached only through its designated parent action.Source: §G.2 · p. 40

Elimination lower bound

  • A δ-valid elimination rule must collect enough observations at a differing leaf to distinguish the instance from its single-leaf alternative.The proof relates the stopped-history KL divergence to the expected leaf count, then applies data processing to the elimination decision.Source: §G.2 · p. 41

Root executions

  • The proof converts leaf observations into root executions by assigning each execution to a witness-tree path and accounting for its probability of reaching the leaf.Each root execution is assigned to one leaf; the path probability links assigned executions to observed leaf costs.Source: §G.2 · p. 41

Corollary

  • For pairwise-disjoint witness trees rooted at reachable unsafe actions, the corollary sums the individual elimination lower bounds across roots.The corollary applies when each root and its single-leaf alternatives meet the lemma’s probability conditions.Source: §G.2 · p. 42

H Experiments

The experiments illustrate the theoretical findings and evaluate SVAE through four questions. They examine baseline performance, variance adaptation, safety identification when safe-policy variance is zero, and recursive elimination.

Experimental questions

  • The experiments ask whether SVAE improves regret and step-wise violation relative to baselines and exploits low return variance induced by safety constraints.These are Q1 and Q2.Source: H Experiments · p. 42
  • A separate question tests whether safety identification can remain difficult when safe-policy return variance is zero.This is Q3.Source: H Experiments · p. 42
  • The final question tests whether recursive elimination excludes unsafe branches while preserving safe continuations.The evaluation uses controlled CMDPs for Q2–Q4 and stochastic navigation for Q1.Source: H Experiments · p. 42

H.1 Experimental Setup

The setup compares SVAE with navigation baselines and controlled-experiment variants under online learning with unknown model quantities. In stochastic navigation, SVAE lowers final strong regret and cumulative step-wise violation relative to SUCBVI, while its later policy value exceeds the average optimal safe value with some violation remaining.

H.1 Experimental Setup

  • The learning setup leaves reward means, mean costs, and transitions unknown; algorithms learn online without a known safe policy, with Bernoulli rewards in Q1 and deterministic rewards in Q2–Q4.Each algorithm runs for 10,000 episodes, with estimates maintained separately for each (h, s, a).Source: §H.1 · p. 42
  • Navigation compares SVAE with SUCBVI using the same recursive safety filter, plus MVP-V and MVP-V with that filter applied every episode.For controlled experiments, the ablations replace variance bonuses with Hoeffding-type bonuses or remove propagation from action elimination.Source: §H.1 · pp. 42–43
  • Evaluation uses exact policy values and optimal safe value; navigation additionally reports strong regret, which does not allow cancellation across episodes.Step-wise violation is cumulative positive excess of mean costs over the threshold along sampled trajectories; the true model and safe sets are reserved for offline tuning and evaluation.Source: §H.1 · p. 43

H.2 Stochastic Navigation

  • The navigation task is a 5 × 5 gridworld with four movement actions and horizon 20, Bernoulli rewards favoring an absorbing goal, and elevated costs for actions crossing a specified boundary.Mean intended-move probabilities are sampled from [0.8, 0.95]; boundary-crossing actions in rows 2–4 have mean costs in [0.7, 0.85].Source: §H.2 · p. 43
  • 44.9% lower final strong regret and 7.7% lower cumulative step-wise violation: SVAE versus SUCBVI in stochastic navigation.Table 1 reports cumulative regret, strong regret, and step-wise violation at K = 10,000; the mean paired differences are −1,162.23 (947.46) for R+ and −119.70 (45.10) for violation.Source: §H.2 · p. 43, Table 1 · p. 44
  • SVAE’s mean policy value over the last 500 episodes is 10.553, above the average optimal safe value of 10.476, while some constraint violation remains.Its expected violation per episode falls from 0.383 in the first 500 episodes to 0.0474 in the last 500.Source: §H.2 · p. 44

H.3 Variance Adaptation

SVAE adapts exploration to return variance within the safe subgraph, while learning which actions are safe. The experiments examine variance adaptation, safety identification, recursive elimination, and experimental configuration.

H.3 Variance Adaptation

  • 0.3% of KVar⋆ was SVAE’s mean accumulated VΣ in both positive-variance conditions; its final regret was lower on average than both Hoeffding variants in all three conditions.SVAE also selected suboptimal branching actions 1.10–1.20 fewer times on average than SVAE (Hoeffding-P).Source: §H.3 · pp. 45–46

H.4 Safety Identification Complexity

  • As p falls from 0.40 to 0.05, unsafe-root plays rise from 117.1 to 931.9, while successor visits remain 46.5 and cumulative violation remains 9.29.With p fixed at 0.2, reducing Δc from 0.30 to 0.10 raises mean successor visits from 26.0 to 214.1; SVAE excludes the unsafe action within the episode budget in every tested condition.Source: §H.4 · pp. 46–47

H.5 Recursive Elimination

  • At d = 3, propagation prevents post-detection branch entries in all 20 runs, versus 9,910.05 entries on average without propagation; with a safe continuation, both methods have identical regret.SVAE’s cumulative violation was 11.99 versus 1,994.00 for the ablation; with safe continuation, the methods followed the same trajectories and had final regret 18.00.Source: §H.5 · p. 47, Figure 6 · p. 48

H.6 Additional Experimental Details

  • Navigation hyperparameters were selected through two-seed development and validation stages at K = 10,000, with safety-filtered configurations required to meet violation and safe-action criteria.After validation, the best configuration was fixed before testing.Source: §H.6 · p. 48

Related papers

Loading 2610.02520v1…