Local-to-Global Safe Curricula for Linear MDPs

A reinforcement learning agent that must never do something dangerous, not even once during training, has to explore cautiously. The best-understood way to do this assumes the reward and the "danger score" (the safety cost) of each action are linear functions of known features. The agent then keeps a confidence region around the unknown cost weights and only takes actions that are safe even under the worst weights in that region. This works, with zero violations and provable regret, but it is slow in exactly the tasks we care about. When the safe region of the target task is narrow, the pessimistic agent can barely move, so it learns little about where the boundary lies and stays stuck. We propose to learn the danger model somewhere else first. The agent trains on a short sequence of easier tasks that share the target's hazards. Each easy task exposes only a few hazards, so the safe region is wide there and the agent can gather cost data quickly. Throughout, every step in every task keeps the same zero-violation guarantee.

The design principle comes from an unlikely place: the variational quantum circuit literature. There, an objective defined over the whole system gives almost no gradient signal, while a sum of objectives over small subsystems gives a usable one. That literature also warns that the local objectives can all be satisfied while the global one is not. Our analogue: the target task's safety cost is a sum of hazard-specific local terms. The curriculum is chosen to shrink uncertainty on those local terms along exactly the feature directions that matter at the target's safety boundary. A final, short phase in the target checks for interactions between hazards that the local terms miss.

Core Claim

In a linear MDP, the transition probabilities, rewards and costs are all linear in a known $d$-dimensional feature map $\phi(s,a)$. In this setting, estimating the cost weights is ordinary regression on observed costs. It does not depend on the dynamics. So cost data collected under different dynamics, rewards or start states transfers directly between tasks, provided they share features and hazards. We write the safety cost as a sum over hazard blocks,

$$c(s,a) = \sum_{j=1}^{J} \langle \phi_j(s,a), \theta_c^{j} \rangle + \langle \phi_{\times}(s,a), \theta_c^{\times} \rangle,$$

where $\phi_j$ are the features tied to hazard $j$ and $\theta_c^j$ its unknown weights. The last term, with features $\phi_\times$ and weights $\theta_c^\times$, captures interactions between hazards. The source tasks show only subsets of hazards, and the interaction term is assumed small there.

The claim has three parts. First, an adaptive curriculum over source tasks, each run with pessimistic safe action sets built from pooled per-block confidence ellipsoids, keeps zero violations with high probability across the whole curriculum. Second, it reaches a target safe set wide enough to contain near-optimal actions using fewer total environment steps than running the safe learner on the target alone. Third, the curriculum's stopping rule replaces the hand-tuned length of the "pure safe exploration" phase in NCS-LSVI with a data-driven criterion.

The scheduling objective is local. At each stage we pick the source task $m$ that most reduces

$$W(m) = \sum_{j} \; \max_{(s,a) \in \mathcal{B}} \|\phi_j(s,a)\|_{V_j^{-1}},$$

where $\mathcal{B}$ is a set of candidate boundary state-action pairs of the target, and $V_j$ is the regularized Gram matrix of block $j$'s features collected so far. The norm $\|\cdot\|_{V_j^{-1}}$ is the usual ellipsoid width, i.e. how uncertain the cost estimate for block $j$ is in that feature direction. We use this local score instead of target return because target return is nearly flat early on: a pessimistic agent in a narrow target earns almost nothing. The curriculum stops when every block's width at $\mathcal{B}$ falls below a margin tied to the threshold $\tau$.

Relation to Prior Work

Two papers supply the safe-learning machinery we reuse. Safe Reinforcement Learning with Linear Function Approximation introduced SLUCB-QVI, which is optimistic about reward and pessimistic about cost. It achieves zero instantaneous violations and regret $\tilde{\mathcal{O}}(\kappa\sqrt{d^3H^3T})$ on a single static task, and it needs a star-convex action space and a known safe seed action. Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spaces removes star-convexity with NCS-LSVI. Its first phase explores randomly near a known safe policy, and it leaves the length of that phase open. Both work on one task.

Our contribution is to move the boundary-learning phase into other, easier tasks and to decide its length adaptively. We keep their pessimistic safe sets unchanged inside each task.

Two curriculum papers motivate the problem but differ in the guarantee. Safe Reinforcement Learning via Curriculum Induction learns a schedule of teacher resets with Bayesian optimization across generations of students. Safety-Prioritizing Curricula for Constrained Reinforcement Learning shows that reward-driven curricula push agents into hazards, and proposes SCG, which moves the task distribution toward the target with optimal transport. Both are empirical deep-RL methods with no zero-violation guarantee. Our scheduler instead targets uncertainty in cost weights, which has a direct meaning under linear structure.

A negative result also constrains the design. On Reward-Free Reinforcement Learning with Linear Function Approximation shows that exploration becomes exponentially hard when the dynamics are not linear. We therefore transfer only cost estimates, which need no dynamics model, and never transfer value functions across tasks with different dynamics.

The locality principle comes from Barren Plateaus in Variational Quantum Computing and F-Divergences and Cost Function Locality in Generative Modelling with Quantum Circuits. The first shows that objectives over the whole system give exponentially vanishing signal. The second shows that objectives over small marginals restore trainability, but can admit solutions that look aligned locally while being misaligned globally. We borrow the principle and its known failure mode, not the quantum hardware. Our interaction block $\theta_c^\times$ and its dedicated target check exist precisely to catch that failure mode.

Research Program

The theory side has three pieces.

First, we prove that pooling cost data across tasks with shared $\phi$ and $\theta_c$ keeps the SLUCB-QVI confidence sets valid. This should follow from self-normalized concentration applied to a single regression over all tasks. The consequence is that the zero-violation guarantee holds jointly across the curriculum and target, under one union bound.

Second, we bound the target's regret in terms of the residual widths $W$ at hand-off. The form we expect is the static bound with $\kappa$ replaced by a quantity that shrinks as $W$ does. This rests on the intuition that $\kappa$ measures how much pessimism restricts exploration. It is a hypothesis to be proved, not a result we can yet claim.

Third, we treat the interaction term honestly. If $\theta_c^\times$ is non-zero, the source tasks tell us nothing about it. The target phase then keeps a separate, initially wide ellipsoid for the interaction block and stays pessimistic in those directions. The regret bound must pay for $\dim(\phi_\times)$ and not for the full $d$.

On the algorithmic side, the curriculum needs a safe seed action for each source task. Source tasks with few hazards often have a trivially safe seed. We will test whether seeds learned in source tasks can be certified safe for the target using the pooled ellipsoid. That would partially address the "known seed" assumption common to both linear safe-RL papers.

Baselines

The naive reference point is SLUCB-QVI run directly on the target, with no source tasks. Its total sample budget matches ours, counting every source-task step against us. This is the question a practitioner will ask first. To beat it, our method must reach the same target return in fewer total steps with zero violations, measured over at least 100 seeds following the sample-complexity protocol of Benchmarking Quantum Reinforcement Learning. Amani et al. report a 100% safety record for SLUCB-QVI on Frozen Lake. No reported result for its regret or steps-to-optimal was found on Lacuna, so we will generate these numbers ourselves.

The strongest existing linear competitor is NCS-LSVI with its first phase tuned by grid search over its length. We give it the same tuning budget we spend on our margin hyperparameter. Roknilamouki et al. report that NCS-LSVI "converged to the optimal policy while maintaining 100% safety" on the merging task, but give no step counts. Beating it means matching its safety while needing fewer total steps than its best-tuned phase length, without per-environment tuning.

The strongest curriculum competitor is SCG. We run it with its own deep-RL learner, and, to be fair, also with SLUCB-QVI as the inner learner. Its only reported figures are qualitative: "lowest constraint violation regret across all benchmarks" and 100% final success. For the intervention curriculum CISR, Turchetta et al. report fewer than 3 training failures against over 1,200 for baselines on Lunar Lander, with 88–92% success. We use those figures only as a reference point for what "near-zero" means empirically.

PPO-Lagrangian from the SafePO library stands in for Lagrangian methods. Safety Gymnasium reports a 98% reduction in violations relative to PPO, with a 45% reward drop, on velocity tasks.

Two ablations isolate the key ingredient. The first swaps the local width score $W$ for target-return improvement as the task-selection signal. The second removes the per-block decomposition and pools a single undivided cost ellipsoid.

Why not just…?

Why not just lengthen the safe exploration phase in the target? This is the most serious threat. Random safe sampling near the seed in the target might collect the same boundary information that source tasks do. Our argument is geometric. In a narrow target, a safe neighborhood around the seed spans few feature directions. Source tasks with fewer hazards let the agent reach states whose features point along the target's boundary directions. The NCS-LSVI comparison at equal total budget settles this directly. If NCS-LSVI with the best phase length matches us on the merging task and the Frozen Lake variants, our contribution reduces to the stopping rule, and we will report it that way.

Why not just use SCG's curriculum on top of a provably safe learner? SCG picks tasks by reward and safety performance, not by information about cost weights. It may choose tasks that are safe but uninformative about the target boundary. The SCG-plus-SLUCB-QVI baseline tests this. If it matches our method, the local width score is unnecessary.

Why not just pool data from all source tasks in random order? Random multi-task pooling already gains from transferring cost data, and it needs no scheduler. The random-order ablation at equal budget measures how much the adaptive schedule adds beyond pooling alone.

Why not just use Lagrangian deep RL? Its violations are bounded only asymptotically. Amani et al. observe that Lagrangian methods frequently violate constraints early in learning. It remains in the comparison as the reference for what giving up the guarantee buys in return.

Proposed Experiments

The environments are Frozen Lake with parameterized hole layouts, the autonomous merging task, and the grid version of SCG's Safety-maze. Each has linear features, one block per hazard. In each, the source tasks are generated by masking subsets of hazards and moving the start state.

We measure four things: training violations counted across source and target tasks together, total environment steps to reach 90% of optimal target return, target regret, and the residual width $W$ at hand-off.

Four decisive checks follow.

The first is zero violations across all seeds. The second is a statistically significant step reduction against tuned NCS-LSVI at equal budget. The third is a positive correlation, across curriculum lengths, between the width $W$ at hand-off and target regret, which tests the hypothesized bound.

The fourth is a planted-interaction variant, in which two hazards are harmless separately but costly together. Here the method must still record zero violations, relying on the interaction ellipsoid. It is the direct test of the "locally aligned, globally wrong" failure mode inherited from the local-cost literature.

As a stress test for misspecification, we run Safety Gymnasium PointGoal with random Fourier features. There we report how often the violation guarantee breaks once the costs are no longer exactly linear.