Turning One Bit of 'Stop!' Into a Dense Cost Signal

Paper: 2608.12306 Authors: Ebenezer Gelo, Geraud Nangue Tasse, Steven James, Benjamin Rosman Categories: cs.LG, cs.AI

The Gap

Nearly every safe offline RL method you can name — CPQ, COptiDICE, constrained versions of BCQ/IQL, Constrained Decision Transformer — is built on top of a CMDP where the dataset ships with a per-step cost c(s,a). That assumption is load-bearing: the cost critic Q_c is trained by TD on those per-step labels, and the Lagrangian multiplier is tuned against the resulting cost return estimate.

The assumption is also fiction in most deployments. What a human supervisor actually produces is stop-feedback: they watch the robot or the car, and at the moment something goes wrong they hit the button. One bit, one timestamp, for a trajectory that might be 200 steps long. No attribution to the lane change eight seconds earlier that made the collision unavoidable.

Two existing workarounds, both unsatisfying. Use the sparse cost as-is: now Q_c has to bootstrap a single nonzero target backwards across the whole episode, which is the classic long-horizon credit assignment pathology — high variance, slow propagation, and a critic that is badly conditioned exactly where you need it to be sharp. Train a classifier to label unsafe states: but your only positive labels sit at the violation step, so every precursor state gets labeled safe, and the classifier learns “unsafe = already crashed,” which is useless for avoidance and sensitive to how much unsafe data the dataset happens to contain.

[PROBLEM] supervisor emits one bit per trajectory
   z = 1 stamped at the FIRST unsafe transition
        |
        v
[STATE OF ART] safe offline RL assumes dense c(s a)
   CPQ / COptiDICE / CDT / Lagrangian variants
        |
        +--> workaround A: keep the sparse spike
        |      .. Q_c bootstraps one bit over T steps
        |      .. near-zero TD targets = ill conditioned
        |
        +--> workaround B: unsafe-state classifier
        |      .. positives only at the crash step
        |      .. precursors labeled safe = false negatives
        |      .. biased by dataset composition
        |
        v
[ASSUMPTION] the CMDP constraint only ever reads the
   cost RETURN of a trajectory. not its shape in time
        |
        v
[METHOD] RCI = return decomposition on the cost signal
   then any off-the-shelf constrained offline solver
        |
        v
[EVIDENCE] highway driving + robotic manipulation
   violation rate well below sparse and classifier
   baselines. holds under mixed data and noisy labels
        |
        v
[CONCLUSION] redistribution is lossless (same feasible
   set. same optimal Lagrangian) yet better conditioned

The Increment

One sentence: Before, “we only have trajectory-level safety labels” meant you either accepted a crippled cost critic or hand-rolled a heuristic cost function; after, it is a *credit assignment problem with a principled fix — redistribute the trajectory’s cost return across its steps, and the CMDP does not notice the difference while the optimizer notices a lot.

Core Mechanism

RCI is two stages bolted together, and the bolt is what makes it work. Stage one takes each trajectory tau = (s_0, a_0, ..., s_T) with its binary stop-feedback z, and runs a sequence model over it that emits a per-step cost c^_t. The model is trained under a return-equivalence constraint: sum_t c^_t must equal z. So for a safe trajectory every step gets zero, and for an unsafe trajectory the model has one unit of blame to distribute — it must decide how much belongs to the final swerve versus the tailgating that preceded it. This is exactly the RUDDER / return-decomposition setup, transplanted from reward to cost.

Stage two is deliberately boring: the redistributed costs are written back into the dataset as if a human had annotated every step, and you run whatever constrained offline RL algorithm you already trust — Lagrangian actor-critic with a reward critic Q_r, a cost critic Q_c now trained on dense targets, and dual ascent on the multiplier.

The theoretical claim is the glue. Because the CMDP constraint is J_C(pi) <= b and J_C is an expectation of sums of costs, any redistribution that preserves the per-trajectory sum leaves J_C(pi) unchanged for every policy. Hence: identical feasible set, identical Lagrangian saddle point, identical optimal policy. Nothing is gained in information and nothing is lost — what changes is purely the conditioning of the learning problem. The paper is honest that this is where the win lives: same problem, vastly shorter credit-assignment chains for Q_c.

   offline dataset D
   +-------------------------------------+
   | tau = (s0 a0 s1 a1 ... sT)   z in \{0,1\} |
   +-------------------------------------+
                  |
                  v
   [ STAGE 1 . return decomposition on cost ]
   sequence model g( tau ) -> c^_0 c^_1 ... c^_T
        hard/soft constraint: sum_t c^_t == z
        loss = return prediction + redistribution reg
                  |
                  v
   +-------------------------------------+
   | D+ = \{ (s a s' r c^) \} dense per step |
   +-------------------------------------+
                  |
                  v
   [ STAGE 2 . constrained offline RL ]
       Q_r  <-- TD on r
       Q_c  <-- TD on c^      (dense. local. stable)
       lambda <-- dual ascent on ( J_C - b )
       pi  = argmax  Q_r - lambda * Q_c
                  |
                  v
            safe policy pi*

The metaphor: this is an insurance adjuster apportioning fault after a crash.

The police report is the stop-feedback: “collision at 14

.” One bit, one timestamp, legally sufficient and practically useless for prevention. The redistribution network is the adjuster who pulls the dashcam footage and writes a liability breakdown: 40% the unsignalled lane change eight seconds out, 30% the following distance, 20% the speed, 10% the final swerve. The return-equivalence constraint is the accounting rule that the percentages must sum to exactly one crash — the adjuster reapportions blame but cannot invent or destroy liability, which is why the insurer’s total payout (the CMDP constraint value) is untouched no matter how they slice it. The cost critic is the actuary setting premiums per driving behaviour: given only “crash at 14” it has to reverse-engineer which habits are dangerous from thousands of reports; given the apportionment it reads the answer off the page. And the Lagrangian policy update is the driving school, adjusting habits in proportion to the premium.

The metaphor also predicts the failure mode. If the adjuster is wrong — blames the swerve instead of the lane change — the payout total is still correct, the books still balance, and the actuary confidently prices the wrong behaviour. Return-equivalence guarantees the accounting, not the attribution.

Key Concepts

• Stop-feedback: Imagine supervising a warehouse robot with one big red button. You do not fill in a spreadsheet rating every joint command; you watch, and when the arm is about to hit the shelf you slam the button. What the logs record is: this episode ended badly, at step 137. That is stop-feedback — binary, trajectory-level, timestamped at the *first violation and silent about everything before it. It is the cheapest safety annotation a human can produce, which is why it is what you actually get.

• Return-equivalent redistribution: Two cost functions are return-equivalent if, for every trajectory, they sum to the same number. Picture a bag with one marble in it at the end of a row of 200 cups. Redistribution grinds that marble into dust and sprinkles it across the cups. Weigh the whole row: identical. But now every cup has something in it, so a machine that can only sense one cup at a time can still tell you where the mass is concentrated. The CMDP is the scale that weighs the whole row — it cannot tell the difference. The TD learner is the one-cup-at-a-time sensor — it cares enormously.

• Why a “lossless” transform helps at all: This trips people up. If no information is added, why does anything improve? Because TD learning does not consume information, it consumes *gradients. A cost critic facing a single terminal spike must chain 137 bootstrapped updates to move value into the state that actually mattered, and each link in that chain injects bias and variance. Dense targets replace the chain with direct regression. Same statistical content, radically different optimization landscape — the same reason reward shaping helps even when it provably preserves the optimal policy.

Framework Shift

Before (mainstream):                  After (RCI):

cost signal along tau                 cost signal along tau
0 0 0 0 0 0 0 0 0 1                   . . : : + + * # # #
^                 ^                   ^               ^
t=0           violation               t=0         violation

        |                                     |
        v                                     v
Q_c must bootstrap one                Q_c regresses on a
bit backwards T steps                 dense local target
        |                                     |
        v                                     v
high variance. slow.                  well conditioned.
ill conditioned                       short credit paths
        |                                     |
   or bolt on a                        and by construction
   classifier that                     sum == original
   calls precursors safe                cost return
        |                                     |
        v                                     v
[ cost model is the             ]     [ cost model is the       ]
[ bottleneck. you fight it      ]     [ preprocessing step.     ]
[ inside the RL loop            ]     [ RL loop stays unchanged ]

One sentence: From “sparse cost is a data limitation you must design your RL algorithm around” to “sparse cost is a temporal credit assignment problem you solve *before the RL algorithm sees the data” — the core shift is relocating the difficulty out of the constrained optimizer and into a supervised preprocessing stage where it is much better behaved.

Expert Assessment

Caveat up front: I am working from the abstract, so the numbers and ablations below are what I would go looking for, not what I have verified.

Problem choice: Real gap, and a slightly embarrassing one for the field. The safe-offline-RL literature has spent several years optimizing against benchmark suites that hand you per-step costs, and almost nobody asked where those costs come from. Anyone who has actually collected safety data knows they come from a button. The framing — stop-feedback as the realistic annotation protocol — is the most valuable contribution here, arguably more than the method. It sits at the point in the field’s trajectory where benchmark-driven progress starts to be checked against deployment reality.

Method maturity: Clever recombination rather than new machinery. Return decomposition is well-trodden (RUDDER, IRCR, randomized return decomposition), and the move is to notice that the cost channel of a CMDP is exactly where it should have been applied all along. The theory is a sanity check, not an engine: “sum-preserving relabeling preserves the constraint” is nearly immediate once stated, and I would be suspicious of a paper that dressed it up as deep. Two simpler approaches deserve to be in the running: uniform smearing of the cost over the trajectory (IRCR-style, essentially free, and historically a brutally strong baseline), and a fixed exponential backward decay from the violation step, which encodes “blame recent actions more” with zero learned parameters. If the learned decomposer does not clearly beat both, most of the paper’s value collapses to the framing.

Experimental integrity: The domain choice is sensible — highway driving gives you long causal chains before a collision, manipulation gives you contact-driven violations — and the robustness axes (heterogeneous dataset composition, label noise) are exactly the right stress tests, which suggests the authors know where the weak point is. Things I would scrutinize: whether the reported baselines include uniform redistribution rather than only “sparse” and “classifier”; whether violation rate is reported alongside return, since driving the cost critic to be conservative buys safety by doing nothing; and how the constraint threshold b is even interpreted when trajectory cost is binary, since b becomes a violation *probability and the Lagrangian is quite sensitive to it. Also worth checking whether the discount factor is handled honestly — return-equivalence holds for undiscounted sums, and with gamma < 1 moving cost mass earlier in time strictly increases the discounted cost return. That is not fatal (it makes the method more conservative, which is arguably fine for safety) but if the paper claims exact losslessness under discounting, something is being swept away.

Writing quality: The likely corner-cut, judging by the abstract’s balance, is the decomposition stage itself — “converts sparse stop-feedback into dense per-step costs via return decomposition” is doing a lot of work in one clause, and the identifiability question (many redistributions are return-equivalent; which one does the training objective actually select, and why is it the causally sensible one?) is where a reader’s trust is won or lost. Rewriting that into an explicit account of the inductive biases, plus a qualitative figure showing *where on a highway trajectory the model places blame, would elevate the whole paper from “sensible pipeline” to “we understand what our model learned.”

Verdict: weak accept — the reframing of sparse safety feedback as credit assignment is genuinely useful and the pipeline is clean, but the theory is a formality and the empirical case stands or falls on ablations against trivial redistribution baselines that the abstract does not mention.

Takeaways

• The transferable trick: any constraint that only reads a *sum over a trajectory is indifferent to how you distribute that sum in time. That licenses free relabeling — not just for safety cost, but for budget constraints, energy consumption, fairness metrics accumulated over an episode, anything expressible as a return. If your critic is struggling with a sparse constrained signal, redistribution is a legal move and you do not need to prove anything new.
• Put the hard part in supervised land: the structural lesson is to move an ill-conditioned subproblem out of the RL loop and into a preprocessing stage where you have full trajectories, offline compute, and stable losses. The RL algorithm downstream stays untouched, which means this composes with whatever constrained solver you have already tuned.
• Design for the annotation you can actually get: “one binary label at the first violation” is a better model of human safety supervision than per-step cost, and worth adopting as a default assumption in your own problem formulations. Benchmarks that hand you dense costs are quietly measuring the wrong thing.
• Cheap baseline to steal immediately: before training any decomposer, try uniform or exponentially-decayed smearing of the trajectory cost backwards from the violation. It takes an afternoon, requires no new model, and in the reward-decomposition literature it has repeatedly matched learned approaches. If it works, you are done; if it does not, you now have a meaningful baseline for the learned version.

[PROBLEM] 监督者每条轨迹只给一个比特
   z = 1 打在第一个不安全 transition 上
        |
        v
[STATE OF ART] 安全离线 RL 假设稠密 c(s a)
   CPQ / COptiDICE / CDT / 各类拉格朗日变体
        |
        +--> 绕路 A: 硬用稀疏尖峰
        |      .. Q_c 要把一个比特回传 T 步
        |      .. TD 目标近乎全零 = 条件数极差
        |
        +--> 绕路 B: 不安全状态分类器
        |      .. 正样本只在撞车那一步
        |      .. 前兆状态被标成安全 = 假阴性
        |      .. 结果被数据集构成绑架
        |
        v
[ASSUMPTION] CMDP 约束只读轨迹的代价 RETURN
   它从来不看代价在时间上的形状
        |
        v
[METHOD] RCI = 对代价信号做 return decomposition
   然后接任意现成的约束离线求解器
        |
        v
[EVIDENCE] 高速驾驶 + 机器人操作
   违规率显著低于 sparse 与 classifier 基线
   在混合数据与噪声标签下依然稳
        |
        v
[CONCLUSION] 重分配是无损的(可行集不变 最优
   拉格朗日不变) 但优化条件好得多

   离线数据集 D
   +-------------------------------------+
   | tau = (s0 a0 s1 a1 ... sT)   z in \{0,1\} |
   +-------------------------------------+
                  |
                  v
   [ 阶段一 . 对代价做 return decomposition ]
   序列模型 g( tau ) -> c^_0 c^_1 ... c^_T
        硬/软约束:  sum_t c^_t == z
        loss = 回报预测 + 重分配正则
                  |
                  v
   +-------------------------------------+
   | D+ = \{ (s a s' r c^) \}  逐步稠密    |
   +-------------------------------------+
                  |
                  v
   [ 阶段二 . 约束离线 RL ]
       Q_r  <-- 对 r 做 TD
       Q_c  <-- 对 c^ 做 TD  (稠密 局部 稳定)
       lambda <-- 对 ( J_C - b ) 对偶上升
       pi  = argmax  Q_r - lambda * Q_c
                  |
                  v
            安全策略 pi*

之前(主流):                            之后(RCI):

沿 tau 的代价信号                      沿 tau 的代价信号
0 0 0 0 0 0 0 0 0 1                   . . : : + + * # # #
^                 ^                   ^               ^
t=0             违规                  t=0           违规

        |                                     |
        v                                     v
Q_c 必须把一个比特                     Q_c 直接在稠密局部
往回 bootstrap T 步                    目标上做回归
        |                                     |
        v                                     v
方差大 速度慢                          条件数良好
条件数差                               信用路径短
        |                                     |
   或者外挂一个                         而且由构造保证
   把前兆判成安全的                     sum == 原始
   分类器                               代价回报
        |                                     |
        v                                     v
[ 代价模型是瓶颈          ]           [ 代价模型退化成预处理 ]
[ 你在 RL 循环里跟它搏斗  ]           [ RL 循环原封不动      ]