acceptodds
Under review as a conference paper at ICLR 2027

FoSeRL: Formal Sequential Robustness Certification for Reinforcement Learning Policies

15 views

Abstract

Even a few action perturbations can substantially degrade the performance of a deployed decision policy. Certifying the resulting return loss is challenging in stochastic environments, where returns vary even without an attack. We introduce FoSeRL, a framework for certifying deployed RL policies against precommitted, temporally sparse action attacks. The deployed policy is unchanged, with no smoothing or retraining. Certification requires a resettable simulator supporting shared randomness and independent one-step successor queries, but no analytical dynamics model. FoSeRL certifies that an attacked episode loses no more than a prescribed amount of return relative to the same episode unattacked, with at least a target probability and at a user-specified confidence level. Both runs share the initial state and randomness, so the measured loss reflects the attack, not the episode; carrying the running return gap as a state coordinate makes it the terminal value, reducing trajectory-level certification to terminal safety. Time-dependent barrier conditions on the augmented state bound the terminal failure probability: satisfied exactly, they certify every admissible precommitted attack; learned from sampled trajectories and verified on held-out data, they certify the same guarantee under a specified attack-episode setting. Across six stochastic continuous-control environments and three RL policy families (TD3, SAC, and PPO), FoSeRL certifies non-trivial cardinality–magnitude robustness frontiers, achieves substantially larger certified budgets than policy smoothing, and reveals marked robustness differences among policies with comparable nominal performance.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning, Certified robustness, Sequential decision making, Barrier certificates, Conformal calibration, Formal verification

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_4UceOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers a form of perturbation attack on RL systems. The authors introduce FOSERL, a system certifying fixed deployed policies against temporally sparse action perturbations

Critical strengths

Really nice paper. Very well written and rigorous.

Critical weaknesses

Many papers like this exist in the DLT and control literature. Also in optimization. Could the authors comment on these links.

Questions for authors

Many papers like this exist in the DLT and control literature. Also in optimization. Could the authors comment on these links.

3 comments
AuthorsOpenReview ↗

Response to the reviewer 4Uce

We thank the reviewer for the positive assessment and for raising this important point. We will address it in the revision by adding a dedicated discussion in the appendix that clarifies these connections and the corresponding technical distinctions.

W1/Q1. FoSeRL is closely related to these areas but certifies a different object: trajectory-level return degradation of a fixed deployed policy under temporally sparse action attacks. Synchronous nominal/attacked coupling and the running return-gap state make z(T)=Dtrajz(T)=D_{\rm traj}, reducing the joint (K,b)(K,b) robustness problem to terminal safety while retaining a state–time witness.

Control. Secure and denial-of-service control studies resilience, estimation, or stability under structured models [1,2]; robust MDPs optimize policies under transition uncertainty [3,4]; and neural barriers certify state-safety properties [5,6]. FoSeRL instead provides a post-hoc robustness certificate for an unchanged deployed policy under temporally sparse action perturbations. It certifies trajectory-level return degradation with prescribed reliability under a declared attack distribution, jointly accounting for attack frequency and magnitude, without requiring an analytical dynamics model.

Optimization and finite-sample verification. FoSeRL is related to scenario and randomized optimization [7,8], but its validity does not come from the non-convex neural synthesis problem. The candidate is synthesized, frozen, and independently verified on fresh data; the resulting finite-sample validity does not depend on the network parameter count. Episode-level calibration and first-exact-violation transfer further handle temporal dependence without a horizon-wise union bound.

Certified robustness in deep learning. Randomized and policy-smoothing methods certify different perturbation geometries and robustness objects [9–11]. FoSeRL instead targets sparse action-channel perturbations over complete episodes, keeps the deployed policy unchanged, separates attack frequency from magnitude through (K,b)(K,b), and returns both a certified robustness frontier and a dynamical state–time witness. Its threat model is motivated by sparse sequential attacks in deep RL [12,13], while the certification framework applies from low-dimensional stochastic control systems to long-horizon MuJoCo tasks.

The technical contribution is therefore not the isolated use of barriers or finite-sample calibration, but the sequential certification construction that makes them applicable to this paired degradation objective. The nominal/attacked coupling and return-gap augmentation convert trajectory-level robustness into a terminal-safety problem, while the verification procedure is specifically designed to transfer finite-sample episode-level information into an end-to-end certificate without a horizon-wise union bound. Together, these elements yield a post-hoc certificate for an unchanged deployed policy, with both a frequency–magnitude robustness frontier and a state–time diagnostic witness. We will make these distinctions more explicit in the revision.

References.

[1] H. Fawzi, P. Tabuada, and S. Diggavi, "Secure Estimation and Control for Cyber-Physical Systems Under Adversarial Attacks," IEEE TAC, 2014.

[2] C. De Persis and P. Tesi, "Input-to-State Stabilizing Control Under Denial-of-Service," IEEE TAC, 2015.

[3] G. Iyengar, "Robust Dynamic Programming," Mathematics of Operations Research, 2005.

[4] A. Nilim and L. El Ghaoui, "Robust Control of Markov Decision Processes with Uncertain Transition Matrices," Operations Research, 2005.

[5] A. Abate et al., "FOSSIL: A Software Tool for the Formal Synthesis of Lyapunov Functions and Barrier Certificates Using Neural Networks," HSCC, 2021.

[6] M. Anand and M. Zamani, "Formally Verified Neural Network Control Barrier Certificates for Unknown Systems," IFAC-PapersOnLine, 2023.

[7] G. Calafiore and M. Campi, "The Scenario Approach to Robust Control Design," IEEE TAC, 2006.

[8] M. Campi and S. Garatti, "The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs," SIAM Journal on Optimization, 2008.

[9] J. Cohen, E. Rosenfeld, and J. Z. Kolter, "Certified Adversarial Robustness via Randomized Smoothing," ICML, 2019.

[10] A. Kumar, A. Levine, and S. Feizi, "Policy Smoothing for Provably Robust Reinforcement Learning," ICLR, 2022.

[11] F. Wu et al., "CROP: Certifying Robust Policies for Reinforcement Learning Through Functional Smoothing," ICLR, 2022.

[12] Y.-C. Lin et al., "Tactics of Adversarial Attack on Deep Reinforcement Learning Agents," IJCAI, 2017.

[13] X. Y. Lee et al., "Spatiotemporally Constrained Action Space Attacks on Deep Reinforcement Learning Agents," AAAI, 2020.

Thank you for the response

Thank you for reading the response and for supporting our paper.

Reviewer_5oikOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a framework for certifying a fixed RL policy against precommitted, temporally sparse action attacks. It measures robustness in terms of cumulative return degradation and turns it into a terminal variable. The authors obtain the certificate by first learning a barrier certificate from synthesized paired rollouts, including safe and unsafe episodes, and then performing conformal calibration using independent rollouts. The experimental results demonstrate nontrivial certified robustness frontiers.

Critical strengths
  1. The paper targets a certificate setting that has received relatively limited attention. Unlike works based on smoothing, retraining, robust action, or expected return bounds, it certifies the paired trajectory-level degradation of the fixed deployed policy against action attacks, by adapting barrier certificates and episode-level conformal calibration to this setting.

  2. The attack budget combines attack cardinality with perturbation magnitude, which gives a more informative robustness profile than considering only per-step magnitude or only the number of attacked steps. The empirical results support the claims, and the comparison against baselines shows the advantages of the proposed method.

Critical weaknesses
  1. It is not very clear how this paper differs from previous work that combines barrier certificates and conformal calibration, beyond the different attack setting and target model.

  2. The scope and the coverage of failure cases are limited. The paper assumes precommitted attacks, and it is unclear whether the work extends to online or state-adaptive attackers. The frequency and causes of inconclusive cases are underreported, and the behavior beyond the tested tolerances (20% for HalfCheetah and Ant, 5% for the other environments) is unclear.

Questions for authors
  1. What is the precise technical novelty compared to prior work that combines conformal calibration with barrier-based certification and data-driven certificate synthesis?
  2. Can the framework handle online or state-adaptive attackers? If so, which parts of the augmented dynamics, barrier conditions, and proof would need to change?
  3. How many specifications were attempted in total, and what fraction ended inconclusive? If inconclusive outcomes are rare, what explains the high acceptance rate?
  4. How does the gap between the empirical and the certified frontiers change as the degradation tolerance grows beyond the tested range (20% for HalfCheetah and Ant, 5% for the other environments)?

Misc.:

  • Please report the input features of the barrier network and the loss weights in Eq. (7), and state whether the attack generator used to produce synthesis rollouts differs from the operational attack law.
  • The comparison with policy smoothing should explain how attack budgets are mapped across the different perturbation geometries, and how worst-case and distributional guarantees are put on a common scale.
2 comments
AuthorsOpenReview ↗

Response to reviewer 5oik (1/2)

We thank the reviewer for the thoughtful and constructive review. The questions raised helped us clarify the technical contributions, scope, and experimental results in the revised manuscript.

W1/Q1. FoSeRL's novelty goes beyond applying existing barriers or finite-sample calibration to a new attack setting. It introduces sequential robustness certification of an unchanged deployed policy under temporally sparse executed-action attacks, jointly capturing attack frequency and magnitude through (K,b)(K,b). Synchronous coupling measures degradation relative to the same episode unattacked, while the running return-gap state satisfies z(T)=Dtrajz(T)=D_{\rm traj}, reducing trajectory-level robustness to terminal safety and enabling a time-dependent barrier witness. To our knowledge, prior certificates do not jointly address this certification objective and (K,b)(K,b) trade-off for the policy as deployed. Moreover, episode-level scoring, hard terminal separation, simultaneous conformal-rank validity, and first-exact-violation transfer provide a high-confidence operational tail guarantee without a horizon-wise union bound. Unlike the closest parent framework, which certifies stochastic training under data perturbations, FoSeRL certifies deployment-time performance robustness and provides both certified robustness profiles and state–time diagnostics. These distinctions are clarified in the revised Introduction, Related Work, and Appendices E.1 and F.1.

Q2. The current theorems address precommitted attacks, but the ideal barrier construction can be extended to non-anticipative state-adaptive attacks under strengthened conditions. Such an attacker selects perturbations based on the observed state and history before fresh one-step randomness is realized, subject to the same (K,b)(K,b) budgets. The augmented state additionally tracks the remaining attack budget and any necessary history, while the return-gap recursion and z(T)=Dtrajz(T)=D_{\rm traj} remain unchanged. The initial and terminal barrier conditions retain their form on the expanded state; the key change is that the drift condition must hold uniformly over all admissible current attack decisions. Under these conditions, the same conditional-expectation argument yields an ideal guarantee over non-anticipative strategies. Finite-data certification for a fixed adaptive strategy can be formulated using its induced episode law, independent calibration, and strategy-consistent successor sampling. Uniform finite-data certification over all adaptive strategies requires additional robust verification and is not claimed here. This extension is discussed in the revised Appendix E.5.

Q3. Across 256 frontier specifications at ρ=0.90\rho=0.90, 241 (94.1%) yielded positive certified budgets, while 15 (5.9%) were inconclusive: 11 in Ant, three in HalfCheetah–TD3, and one in Hopper–PPO. The high acceptance rate reflects the frontier-search procedure, not relaxed verification: attack magnitudes are explored during design, and each reported positive certificate is independently verified using a frozen candidate and fresh calibration data. A setting is inconclusive when no tested positive magnitude passes verification, which does not establish non-robustness. The inconclusive cases concentrate in the more computationally demanding locomotion environments, consistent with increased difficulty in barrier synthesis and finite-sample certification, although these factors have not been isolated causally. We have clarified the outcome counts and their interpretation in the revised Experiments section, with complete profiles in Appendix D.9.

AuthorsOpenReview ↗

Response to reviewer 5oik (2/2)

Q4. The reported degradation-tolerance ranges are application-dependent experimental choices, not framework limitations. To examine behavior beyond these ranges, we extended the normalized tolerance α\alpha% for ACC–TD3 and HalfCheetah–TD3 at K/T=30K/T=30% retaining the original-grid endpoints for comparison:

Environmentα\alphabempb_{\rm emp}bcertb_{\rm cert}Gap (%)
ACC–TD35%1.540.8942.2
ACC–TD310%2.271.9414.5
ACC–TD320%5.824.6220.6
HalfCheetah–TD320%0.620.4527.4
HalfCheetah–TD330%0.920.6529.3
HalfCheetah–TD350%1.461.1124.0

The results show that increasing the degradation tolerance leads to larger empirical and certified attack budgets for both policies. However, the relative gap varies non-monotonically with tolerance, consistent with the setting-dependent conservatism observed in the original robustness profiles. Thus, these experiments extend the certified frontiers beyond the original tolerance ranges (revised Appendix D.10, Extended degradation-tolerance experiments).

M1. Barrier inputs include the nominal and attacked states, their discrepancy, running degradation zz, and normalized time. For example, ACC uses 18 features covering normalized states and differences, headway and relative-speed errors, crash indicators, transformed degradation, and time. In Eq. (7), the primary loss coefficients are set to cρ=cI=cU=cf=1c_\rho=c_I=c_U=c_f=1, with sample-dependent penalties normalized by their respective sample counts. Auxiliary drift contributions from full-episode and terminal-unsafe trajectories are down-weighted to 0.10 for Inverted Pendulum, ACC, and Unicycle, 0.15 for Hopper, and 0.25 for HalfCheetah and Ant. These empirical, synthesis-only weights balance auxiliary training signals against the primary loss terms; formal validity is established independently after freezing the candidate. Further synthesis and implementation details are provided in the revised Appendices D.4 and D.5.

M2. To our knowledge, no existing formal baseline exactly matches the full FoSeRL setting. We therefore use Policy Smoothing (PS) as the closest comparison, aligning the action channel, horizon, paired terminal-degradation event, (K,α,ρ,β)(K,\alpha,\rho,\beta) targets, and per-step magnitude bb, while retaining PS's native ℓ2\ell_2 geometry. For native ℓ2\ell_2 threats, stacking at most KK perturbations with ∥Δt∥2≤b\lVert\Delta_t\rVert_2\leq b yields ∥δ∥2≤bK\lVert\delta\rVert_2\leq b\sqrt{K}. For ℓ∞\ell_\infty threats, the enclosing ℓ2\ell_2 ball gives ∥δ∥2≤bnaK\lVert\delta\rVert_2\leq b\sqrt{n_aK}. We thus compare the largest per-step bb certified for the matched event and targets. The guarantees differ in scope and certified policy: under the action-channel adaptation used in our comparison, PS provides a worst-case-over-perturbations probabilistic guarantee for a smoothed policy, whereas finite-data FoSeRL certifies the unchanged deployed policy under the declared attack–episode law QK,b\mathbb{Q}_{K,b}. Both are evaluated at the same target reliability ρ\rho, making this a trade-off between attack coverage and policy preservation rather than an equivalence. FoSeRL further requires no robustness-specific policy modification, policy differentiability, analytical dynamics model, or prescribed smoothing-noise structure. These are now explicit in the revised Appendices D.11 and F.2.

Reviewer_8o78OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents FoSeRL, a framework for certifying fixed reinforcement-learning policies against precommitted, temporally sparse action perturbations. It couples nominal and attacked trajectories using the same initial state and randomness, augments the state with cumulative return degradation, and reduces trajectory-level certification to a terminal-safety problem. Neural stochastic barriers are synthesized from sampled trajectories and independently verified using finite-sample successor bounds and episode-level conformal calibration. Experiments cover six continuous-control environments and TD3, SAC, and PPO policies.

Critical strengths

1.The joint cardinality–magnitude threat model is practically meaningful and directly captures trajectory-level return degradation. 2.The reduction to terminal safety, combined with stochastic barriers and independent calibration, is technically rigorous. 3.The experiments cover six continuous-control environments, three RL algorithms, and horizons of up to 1,000 steps.

Critical weaknesses
  1. The data-driven certificate holds under a specified attack distribution, rather than against every admissible attack in the worst case.
  2. Important details of the PGD, LAS, and DE attack distributions and hyperparameters are insufficiently specified, limiting reproducibility.
  3. Direct terminal-event certification is generally cheaper and tighter, while the practical benefit of the barrier witness is not demonstrated convincingly.
Questions for authors
  1. Could the authors provide a complete definition of the operational attack distribution UK,b, including attack-time sampling, perturbation directions, mixture weights, and optimization hyperparameters?
  2. How are different termination times between the nominal and attacked branches handled within the fixed-horizon formulation?
  3. Could the authors demonstrate a case where barrier residual diagnostics lead to a concrete improvement in certificate quality?
  4. How are the very large successor-sampling budgets implemented within the reported runtimes?
1 comment
AuthorsOpenReview ↗

Response to reviewer 8o78

We thank the reviewer for the careful and constructive review. The comments helped us identify where the guarantee scope, experimental specification, and practical role of the barrier witness needed further clarification. These points have now been addressed in the revised manuscript.

W1. The reviewer's concern applies to the finite-data certificate, not to the ideal FoSeRL result: Definition 6 and Theorem 1 provide a uniform guarantee over all admissible precommitted attacks when the barrier conditions hold uniformly. The practical finite-data procedure instead certifies reliability under a declared operational attack law. This reflects a verification trade-off rather than a limitation of the underlying formulation. Enforcing uniform conditions over the continuous reachable state–attack–time domain would require global verification, typically involving additional model access or structural regularity assumptions. FoSeRL avoids such global verification requirements while retaining a formal high-confidence operational guarantee. This distinction and trade-off are now clarified in the revised Methodology and Discussion.

W2/Q1. In all formal experiments, each attack scenario is precommitted before the evaluated episode: exactly (K) distinct attack times are sampled uniformly without replacement, independently of the initial state and episode randomness. Each certification setting uses a single benchmark-specific attack generator under the prescribed per-step norm budget. The main quantitative experiments use DE for ACC (50 candidates, 20 generations), PGD for Inverted Pendulum (15 iterations, step size 0.01) and HalfCheetah (10 iterations, step size 0.01), LAS for Unicycle and Hopper (5 optimization steps, step size 0.01), and Uniform sampling for Ant. The slash notation in Table 2 denotes separate experimental settings, not a mixture; each experiment uses one attack generator for both synthesis and verification. Further implementation details and hyperparameters are provided in the revised Appendix D.5.

Q2. Both the nominal and attacked rollouts are evaluated over the same fixed horizon TT, even if they terminate at different times. When a branch terminates, its final transition reward is included, and all subsequent rewards for that branch are set to zero, while the other branch continues under its own termination rules. This preserves the exact identity z(T)=Rnom−Rattz(T)=R_{\rm nom}-R_{\rm att}. The attack schedule is fixed before the episode; if the attacked branch terminates early, any remaining scheduled perturbations are simply not executed. Thus, the number of effective attacks never exceeds KK. This convention is clarified in the revised Appendix D.1 (Benchmark formulation).

W3/Q3. When only a scalar terminal guarantee is required, Direct certification can be cheaper and tighter. FoSeRL provides additional value through its state–time barrier witness, which identifies the certifying conditions (initial, drift, or terminal separation) and sampled trajectory phases that limit the certificate. Its Base–Margin–Bridge decomposition further distinguishes witness-related and calibration-related conservatism, enabling targeted certificate refinement. These diagnostics concern certificate limitations, not certified local failure probabilities. All reported results are the final certified values, with some certificates already refined using these diagnostics. For ACC–TD3 (K/T=10K/T=10%, α=0.5\alpha=0.5%), witness refinement increased bcertb_{\rm cert} from approximately 0.380.38 to 0.550.55. For Ant–PPO (K/T=20K/T=20%, α=20\alpha=20%), increasing the calibration budget alongside modest synthesis refinement increased bcertb_{\rm cert} from approximately 0.220.22 to 0.440.44. Both were independently re-verified. Thus, FoSeRL offers structured, condition-specific diagnostics beyond Direct's scalar guarantee, with demonstrated value for certificate refinement (revised Appendices D.7 and E.4).

Q4. RT measures wall-clock certificate computation on pre-generated data, including the applicable method-specific synthesis, verification, and budget-search steps. The revised manuscript clarifies this definition for the FoSeRL, Direct, and Policy Smoothing results in the main comparison table. We have additionally reported FoSeRL end-to-end runtimes, accounting for successor-sample generation, for all twelve representative FoSeRL specifications (revised Appendix D.8). For example, in the reported Ant–PPO configuration, Direct and FoSeRL require approximately 53 s and 96 s of RT, respectively, while FoSeRL's reported E2E runtime is 82.5 min. These measures distinguish certificate computation on pre-generated data from the additional successor-generation cost.

Comments on the paper

1 comment

Dear Area Chair and Reviewers,

We sincerely thank you for your thoughtful and constructive feedback, which has helped us improve the clarity and presentation of our work.

We have now uploaded the revised manuscript, with all changes highlighted in blue. The revisions address the reviewers' comments and include additional clarifications and improvements identified during our own review. Most of the extended discussions and experimental details are provided in the appendix. We hope these revisions adequately address your concerns and would be happy to discuss any further questions, comments, or suggestions to further strengthen our work.

Thank you again for your time and consideration.

Best regards,

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.