Technical Summary: TraCeS

Problem Statement

Ensuring safe behavior in Reinforcement Learning (RL) is challenging when safety constraints are implicit, unmeasured, or unavailable during training. In many safety-critical domains (e.g., robotics, autonomous driving), hard-coded constraints and hand-shaped cost functions are often brittle and fail to generalize across context-dependent scenarios. Furthermore, dense per-timestep supervision is frequently unavailable; instead, supervision is limited to coarse, sparse binary labels indicating whether an entire trajectory (or a prefix of it) remained within an unknown safety threshold.

The core difficulty lies in the credit assignment problem: a trajectory-level label (e.g., "rejected") indicates a violation occurred but does not specify when or which specific behaviors caused it. Standard Constrained Markov Decision Process (CMDP) methods assume access to a known per-step cost function and a threshold, which is not the case here. The paper addresses the setting where the agent must learn a safe policy from sparse trajectory-level accept/reject labels without knowledge of the underlying cost function $C$ or the constraint threshold $b$.

Methodology: TraCeS

The authors propose TraCeS (Trajectory-based Constraint Estimation for Safety), a framework that learns per-timestep violation credits from sparse trajectory-level labels. The method operates through an iterative loop involving three main components:

1. Sequential Violation Estimator

TraCeS trains a sequential estimator to decompose sparse binary feedback into dense, per-timestep violation credits.

• Monotone Violation Abstraction: The method assumes a monotone violation structure (Assumption 3.1): once a trajectory violates a constraint, it remains violated thereafter. This implies the probability of "not yet violated" is non-increasing over time.
• Factorization: The estimator predicts the probability that a trajectory prefix $\tau_{0:t}$ has not yet violated the constraint, denoted as $\hat{P}(\psi_{0:t}=1 | \tau_{0:t})$. This probability is factorized into per-step multiplicative credits:
  $$\hat{P}(\psi_{0:T-1}=1 | \tau_{0:T-1}) = \prod_{t=0}^{T-1} \hat{P}^\Delta_t$$
  Here, $\hat{P}^\Delta_t$ represents the change in the non-violation probability when extending the prefix by one step. A value significantly less than 1 indicates a step that induces a sharp drop in safety probability, effectively localizing the violation credit.
• Architecture: The estimator uses a shared encoder $f_w$ to maintain a summary vector $h_t$ of the prefix and a decoder $g_w$ to output parameters for a log-normal distribution. The sampled log-credit is constrained to be non-positive ($\log \hat{P}^\Delta_t \le 0$), ensuring the cumulative probability does not increase.
• Training: The estimator is trained using Binary Cross-Entropy loss on the sparse binary labels (accept/reject) of trajectories or prefixes, treating the problem as a maximum-likelihood estimation of the unknown labeling rule $\Psi(\cdot)$.

2. Constrained Policy Optimization

Once the estimator learns the per-step credits, TraCeS integrates them into a standard CMDP solver.

• Surrogate Cost: The estimated log-credit is transformed into a surrogate cost: $\tilde{C}_t = -\log \hat{P}^\Delta_t \ge 0$.
• Constraint Reformulation: The original chance constraint (requiring the probability of an acceptable trajectory to be at least $d$) is approximated. Using Jensen's inequality, the authors derive a tractable lower bound that converts the multiplicative constraint into an additive form:
  $$\mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t} \tilde{C}_t \right] \le -\log d$$
  This reformulation allows the use of standard constrained RL algorithms (e.g., PPO-Lagrangian) with the learned surrogate costs, even though the true cost function is unknown.
• Theoretical Guarantee: The paper provides a bound on the approximation gap introduced by Jensen's inequality, showing that the gap shrinks as the estimator becomes more stable and the variance of the predicted non-violation probabilities decreases.

3. Active Trajectory Selection

To reduce the annotation burden, TraCeS employs an uncertainty-based strategy to select which trajectories to label.

• Coefficient of Variation (CV): The method calculates the CV of the trajectory-level surrogate cost under the estimator's sampling noise. Trajectories with high CV (indicating high dispersion or uncertainty in the estimator's prediction) are prioritized for labeling. This focuses human or automated annotation efforts on rollouts where the estimator is most uncertain, improving data efficiency.

Key Contributions

1. Problem Formulation: The paper formalizes the problem of safe policy learning from sparse trajectory-level labels under a monotone violation abstraction, addressing the gap where neither the cost function nor the threshold is known.
2. Method (TraCeS): A novel sequential estimator that factorizes trajectory-level acceptability into per-timestep violation credits. This enables the transformation of coarse binary feedback into a dense surrogate cost signal compatible with standard CMDP solvers.
3. Theory and Evaluation:
   • Theoretical analysis of the approximation gap introduced by the Jensen's inequality lower bound.
   • Empirical validation across 12 continuous-control tasks (Safety Gymnasium, MuJoCo, Bullet Safety Gym).
   • Demonstration of robustness in low-data regimes, under noisy labels, and in settings with human feedback.

Experimental Results

The authors evaluate TraCeS against several baselines:

• Oracle Methods: PPO-Lagrangian and CPPO-PID (assume known cost and threshold).
• Partial Knowledge: RLSF (learns costs but assumes known threshold).
• Zero-Knowledge Baselines: A Cost-Threshold (C-T) baseline that attempts to learn both cost and threshold from scratch.

Key Findings:

• Constraint Satisfaction: TraCeS reliably learns policies that satisfy the safety constraints (cost $\le$ threshold) across most tasks, despite having zero knowledge of the cost or threshold.
• Label Efficiency: TraCeS is substantially more label-efficient than the zero-knowledge C-T baseline, requiring significantly fewer labeled trajectories to converge to safe policies.
• Performance: TraCeS achieves competitive reward-safety tradeoffs compared to partial-knowledge methods (RLSF) and approaches the performance of oracle methods on several tasks.
• Localization: Qualitative analysis shows that the learned per-step credits accurately localize violation events, peaking near the timestep where the oracle cumulative cost crosses the threshold, rather than spreading cost uniformly.
• Robustness: The method remains effective under moderate label noise (up to 10-20%) and in low-data regimes (e.g., 1000 labeled trajectories). It also performs well with human feedback in a small-scale study on HalfCheetah.

Significance and Claims

The paper claims that TraCeS provides a practical path toward aligning RL agents with implicit and context-dependent constraints when formal specifications are unavailable. By transforming coarse accept/reject supervision into per-timestep violation credits, TraCeS enables the use of standard constrained optimization machinery without requiring hand-designed cost functions or known thresholds.

The authors emphasize that the learned credits serve as control-relevant safety surrogates rather than identifiably recovering hidden ground-truth costs. The method is particularly significant for settings where safety is defined by complex, dynamic factors (e.g., avoiding a pothole might require temporary lane deviation) that are difficult to encode as fixed cost functions but can be judged by a human or monitor as "acceptable" or "unacceptable" for a trajectory.

The work suggests that sparse trajectory-level feedback, when processed through a sequential estimator with active selection, can effectively bridge the gap between high-level safety judgments and low-level policy optimization.