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.
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)=Dtraj, reducing the joint (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), 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.