betaFeedback

WorksComputer Science

Beyond L∞L_\infty-Norm Sets: Synthesizing Interpretable Non-Uniform Uncertainty Sets for Evaluation-Time State-Adversarial Robustness

Abstract

Deep reinforcement learning (DRL) agents are vulnerable to perturbations of their observed state inputs. Prior works often constrain state adversaries with LpL_p-norm uncertainty sets and evaluate policy performance under the resulting perturbations. However, in continuous control tasks like robotics control, different state dimensions have distinct physical meanings and influence policy behavior to different degrees, which LpL_p-norm sets fail to capture or explain. Moreover, it is important to identify when and along which state dimensions a policy is vulnerable, independently of the algorithm used to train it. In this paper, we focus on evaluation-time attacks applied to pretrained policies. We propose Performance-Degradation Non-Uniform Uncertainty Set (\method{}), an interpretable formulation of uncertainty sets for state perturbations. \method{} is state-dependent, dimension-wise non-uniform, and can be synthesized online during policy evaluation. We first formulate an ideal constrained optimization problem for \method{} computation, then introduce a surrogate constraint to make the problem tractable. Experiments across multiple continuous-control environments, policy algorithms, and state attacks show that \method{} reveals variation in policy sensitivity across states and dimensions, while its performance degradation is moderately controlled.

Introduction

Deep reinforcement learning (DRL) has achieved remarkable success in complex control problems, including robotics and autonomous driving. However, even well-trained policies may remain vulnerable to perturbations in observed states, transition dynamics, or action execution, which substantially degrade policy performance and cause unsafe behavior. Improving policy robustness against these perturbations is therefore essential when deploying DRL policies.

In this work, we focus on policy robustness against observed state perturbations in continuous control tasks. While some studies consider more structured formulations (Mandlekar et al. [12]; Everett, Lütjens, and How [5]), prior methods commonly constrain perturbations using an L∞L_{\infty}-norm uncertainty set which assumes a fixed perturbation budget across all states and state dimensions, and then evaluate or optimize the resulting performance degradation (Zhang et al. [29]; Oikarinen et al. [16]; Zhang et al. [28]; Liang et al. [11]). Although convenient, the L∞L_{\infty}-norm formulation has two important limitations that hinder its interpretability. First, a fixed perturbation budget does not account for variations in policy sensitivity across states and state dimensions. State features can differ substantially in their physical meanings and contributions to policy behavior (see a toy experiment in Table 1). Even perturbations along the same dimension have different effects depending on the current state; for example, a robot is more sensitive to perturbations when it is about to fall than when it is stable. Therefore, L∞L_{\infty}-norm produces insufficiently realistic perturbations that are restrictive in some scenarios but damaging in others. Second, in prior work the perturbation budget is often selected empirically and lacks a direct interpretation in terms of performance degradation. An appropriate budget for one environment or policy-learning algorithm can be unsuitable for another. While some works (Zhang et al. [29, 28]) show how to design adversarial perturbations within a specified uncertainty set, they rarely explore how to design a policy-specific uncertainty set which controls the resulting performance degradation.

Noise (δ\delta)Hopper HeightTorso AngleJoint Angles: ThighJoint Angles: LegJoint Angles: FootTorso Linear Velocities: X-AxisTorso Linear Velocities: Z-AxisTorso Angular VelocityJoint Velocities: ThighJoint Velocities: LegJoint Velocities: Foot
03547.9
0.13282.53580.53486.33497.93499.93490.93435.43475.63579.63561.03580.4
0.22169.23575.73440.73540.53294.43245.63035.13395.53484.23472.82966.1
0.31501.03468.92918.63153.62632.23217.51967.71627.03373.23342.92523.7
0.41093.83583.82172.63098.32539.12399.4994.7<u>414.6</u>2895.72896.61744.4

Table 1. A toy experiment in which each state dimension is perturbed for a PPO (Schulman et al. [20]) policy trained on Hopper environment. To perturb the ii-th state dimension, we apply constant noise, i.e. si←si+δs_i \leftarrow s_i + \delta. We report the mean total reward over 20 episodes. For each value of noise δ\delta, the most and least robust dimensions are shown in bold and <u>underlined</u>, respectively.

The limitations motivate an interpretable formulation of uncertainty sets. We aim to answer the following question:

Given a policy, what is the largest uncertainty set whose admissible perturbations remain consistent with a predefined tolerance on performance degradation?

Our main contributions are summarized as follows:

  • We propose Performance-Degradation Non-Uniform Uncertainty Set (PD-NUUS), a state-dependent and non-uniform uncertainty set for observed state perturbations. Unlike L∞L_{\infty}-norm, PD-NUUS relates local perturbations to a predefined tolerance on degradation in discounted return, providing a performance-based interpretation of the admissible perturbations.

  • We formulate the synthesis of PD-NUUS as a constrained optimization problem, and derive a tractable surrogate constraint that mitigates occupancy shift with a policy divergence regularizer. The resulting closed-form solution can be directly applied to pretrained policies for robustness evaluation without changing the policy update rule.

  • Extensive experiments across multiple policy-learning algorithms, environments, and state-adversarial attacks demonstrate that PD-NUUS provides generally reliable performance-level control over the degradation in discounted return.

Related Work

LpL_p-Norm Uncertainty Set in Robust RL

Robust reinforcement learning (robust RL) studies how policies maintain reliable performance under perturbations to different components of a Markov Decision Process (MDP), including observed states and transition dynamics ([6, 29]). A single type of LpL_p-norm uncertainty set is most widely used to model perturbations. For example, [29, 16, 28, 11] improve policy robustness against state perturbations constrained within a predefined L∞L_\infty-norm set. Pattanaik et al. [17] constrain adversarial state noise using an L2L_2-norm set. Kuang et al. [9] propose an L∞L_\infty-norm based method to handle dynamics perturbations. Randomized smoothing approaches provide certified policy robustness under L2L_2-norm perturbations, although the certification is for a smoothed policy rather than the original policy ([10] (Mu et al. 2024)).

Non-Uniform Perturbations

Erdemir et al. [4] introduce non-uniform perturbations for classification and prediction problems, and Wong and Kolter [25] propose to learn a non-uniform perturbation set with conditional variational autoencoders (CVAEs). For vision-based RL, Sun et al. [22] employ diffusion models to generate realistic perturbations semantically distinct from the original images. In robust MDPs where transition dynamics are perturbed, Petrik and Russel [18]; Zhang, Wang, and Boedecker [30] optimize the shape of the uncertainty set using value functions, while Behzadian et al. [3] leverage a percentile-performance criterion. For observed state perturbations, Mandlekar et al. [12] use the fast gradient method to create adversarial perturbations, and Everett, Lutjens, and How [5] certify the robustness of action-value function. Additionally, Korkmaz and Brown-Cohen [8] identify adversarial directions through local quadratic approximations of policy loss, Shen et al. [21] improve robustness through policy smoothness regularization, and Wu et al. (2021) certify action and cumulative-reward robustness through functional smoothing. However, we instead aim to explore how to attack a pretrained policy in a controlled way, and our method constrains the degradation directly in return rather than value functions, motivated by the observation from Beechey, Smith, and Şimşek [2] that contributions of state features to the value function do not necessarily provide faithful insight into contributions to policy performance.

Preliminaries

MDP and SA-MDP

We consider tasks with continuous state and action spaces. An MDP is specified by a tuple (S,A,P,ρ,R,γ)(\mathcal{S}, \mathcal{A}, P, \rho, R, \gamma), where S⊆Rm\mathcal{S} \subseteq\mathbb{R}^{m} and A⊆Rn\mathcal{A} \subseteq\mathbb{R}^{n} denote state and action spaces respectively, P:S×A→ΔSP:\mathcal{S}\times\mathcal{A}\to\Delta_{\mathcal{S}} is the transition kernel with Δ(⋅)\Delta_{(\cdot)} denoting the set of probability distributions over the given space, ρ∈ΔS\rho\in\Delta_{\mathcal{S}} is the initial state distribution, R:S×A→RR:\mathcal{S}\times\mathcal{A}\to\mathbb{R} is the reward function, and γ∈(0,1)\gamma\in(0,1) is the discount factor. A policy π:S→ΔA\pi:\mathcal{S}\to\Delta_{\mathcal{A}} maps each state to a distribution over actions. The discounted return of π\pi is defined as

J(π)≜Es0∼ρ,at∼π(⋅∣st),st+1∼P(⋅∣st,at)[∑t=0∞γtR(st,at)].(1)J(\pi) \triangleq\mathbb{E}_{s_0\sim\rho,a_t\sim\pi(\cdot\mid s_t),s_{t+1}\sim P(\cdot\mid s_t,a_t)}\left[\sum_{t=0}^{\infty}\gamma^t R(s_t,a_t)\right]. \tag*{(1)}

The advantage function Aπ(s,a)A^\pi(s,a) quantifies how much better a specific action is compared to the average action in that state. The normalized discounted future state distribution dπd^\pi induced by π\pi, also called the occupancy distribution, is defined as

dπ(s)≜(1−γ)∑t=0∞γtPr⁡(st=s;π,ρ).(2)d^\pi(s) \triangleq(1-\gamma)\sum_{t=0}^{\infty}\gamma^t\Pr(s_t=s;\pi,\rho). \tag*{(2)}

In this work, we focus on the scenarios in which the policy observes perturbed states. The State-Adversarial Markov Decision Process (SA-MDP) ([29]) augments the standard MDP with a state adversary ν:S→S\nu:\mathcal{S}\to\mathcal{S} only for the observed states. The action is predicted by a perturbed policy, while the environment still transitions from the true state ss to the next state. Although SA-MDP shows the influence of a state adversary on the Bellman operator during policy training, we only consider policy evaluation.

LpL_p-Norm Uncertainty Set of State Adversary

The state adversary ν\nu is typically constrained to make the problem well-posed. A common choice is an LpL_p-norm ball around each state s∈Ss \in S: That is, ν(s)∈B(s)\nu(s) \in B(s), where B(s)≜{s^∈S∣∥s−s^∥p≤ϵ}B(s) \triangleq\{\hat{s} \in S \mid\|s-\hat{s}\|_p \le\epsilon\}, and ϵ>0\epsilon> 0 controls the perturbation budget. Different choices of pp-norm correspond to different assumptions on the perturbation geometry. A policy observes a perturbed state ν(s)\nu(s) sampled from B(s)B(s) and uses ν(s)\nu(s) as the basis for selecting an action, though the actual state transition proceeds from the true state ss.

Methodology

Problem Formulation of PD-NUUS

We consider the scenario where a policy is evaluated under observed state perturbations. At each time step, if the policy reaches a state ss, then a PD-NUUS is synthesized online around ss after which a perturbation is sampled. Given a continuous state space S⊆RmS \subseteq\mathbb{R}^{m}, we define PD-NUUS with a state-dependent budget function r:S→[0,rmax⁡]mr:S \to[0,r_{\max}]^{m}

Br(s)≜{s^∈S∣∣si−s^i∣≤ri(s), i=1,…,m}.(3)B_r(s) \triangleq\{\hat{s} \in S \mid|s_i-\hat{s}_i| \le r_i(s),\ i=1,\ldots,m\}. \tag*{(3)}

In other words, a PD-NUUS Br(s)B_r(s) augments an L∞L_{\infty}-norm ball with anisotropic scaling. We leave the correlation of state dimensions for future work. The class of admissible state adversaries induced by a PD-NUUS is denoted as

Vr≜{ν:S→S∣ν(s)∈Br(s), ∀s∈S}.(4)\mathcal{V}_r \triangleq\{\nu:S \to S \mid\nu(s) \in B_r(s),\ \forall s \in S\}. \tag*{(4)}

and attacking the observed state of a clean policy π\pi with a state adversary ν∈Vr\nu\in\mathcal{V}_r induces a new policy πν(⋅∣s)=π(⋅∣ν(s))\pi_\nu(\cdot\mid s)=\pi(\cdot\mid\nu(s)). The synthesis of PD-NUUS is then formulated as a constrained functional optimization problem over r(⋅)r(\cdot).

Uncertainty Set Size as Objective. Since ri(s)≥0r_i(s) \ge0 for all state dimensions, we define the objective Φ(π,r)\Phi(\pi,r) as the expected 1-norm of r(s)r(s) over states visited by the policy π\pi:

Φ(π,r)=Es∼dπ[∥r(s)∥1]=Es∼dπ[1Tr(s)].(5)\Phi(\pi,r)=\mathbb{E}_{s\sim d^\pi}[\|r(s)\|_1]=\mathbb{E}_{s\sim d^\pi}[\mathbf{1}^{\mathsf{T}}r(s)]. \tag*{(5)}

Performance Degradation as Constraint. We constrain the worst-case performance degradation in the expected discounted return. Given a tolerance β>0\beta> 0, all admissible adversaries are required to satisfy

sup⁡ν∈Vr[J(π)−J(πν)]≤β.(6)\sup_{\nu\in\mathcal{V}_r}[J(\pi)-J(\pi_\nu)] \le\beta. \tag*{(6)}

We apply the following performance difference equation which is obtained immediately by setting π′=πν\pi'=\pi_\nu in Lemma 6.1 of Kakade and Langford [7]:

J(π)−J(πν)=−11−γEs∼dπν,a∼πν[Aπ(s,a)].(7)J(\pi)-J(\pi_\nu)=-\frac{1}{1-\gamma}\mathbb{E}_{s\sim d^{\pi_\nu},a\sim\pi_\nu}[A^\pi(s,a)]. \tag*{(7)}

Therefore, the constraint is equivalent to

sup⁡ν∈Vr−Es∼dπν,a∼πν[Aπ(s,a)]≤(1−γ)β.(8)\sup_{\nu\in\mathcal{V}_r}-\mathbb{E}_{s\sim d^{\pi_\nu},a\sim\pi_\nu}[A^\pi(s,a)] \le(1-\gamma)\beta. \tag*{(8)}

Ideal Problem Formulation. Combining objective and constraint, the formal PD-NUUS synthesis problem is:

max⁡rEs∼dπ[1Tr(s)],(9)\max_r\quad\mathbb{E}_{s\sim d^\pi}[\mathbf{1}^{\mathsf{T}}r(s)], \tag*{(9)}
s.t.sup⁡ν∈Vr−Es∼dπν,a∼πν[Aπ(s,a)]≤(1−γ)β.(10)\mathrm{s.t.}\quad\sup_{\nu\in\mathcal{V}_r}-\mathbb{E}_{s\sim d^{\pi_\nu},a\sim\pi_\nu}[A^\pi(s,a)] \le(1-\gamma)\beta. \tag*{(10)}

Ideally, after specifying the hyperparameter β\beta, the optimal solution r∗(s)r^*(s) defines PD-NUUS over the visited states such that the worst-case degradation in discounted total return does not exceed β\beta. However, directly solving this problem is generally intractable. This is because the constraint contains a state adversary ν\nu, which has no explicit expression but is only known to be constrained. Although πν\pi_\nu can be approximated through a Taylor expansion, accurately computing dπνd^{\pi_\nu} generally requires both knowledge of the environment dynamics and an explicitly specified πν\pi_\nu. Alternatively, dπνd^{\pi_\nu} may be estimated from trajectories sampled by πν\pi_\nu, but repeating this process throughout the optimization is computationally expensive. Moreover, unlike prior works on policy optimization ([19, 1, 20]) which typically assume dπν≈dπd^{\pi_\nu} \approx d^\pi to guarantee policy improvement within constrained policy change, our formulation admits substantially perturbed policies, especially when β\beta is large. This implies dπνd^{\pi_\nu} may differ considerably from dπd^\pi.

Approximate Closed-Form Solution

Surrogate Constraint for Intractable dπνd^{\pi_\nu}. Inspired by the divergence regularizer in offline RL (Wu, Tucker, and Nachum 2019), we replace the LHS of Eq. (10) by a surrogate

sup⁡ν∈Vr−Es∼dπ[Ea∼πν[Aπ(s,a)]−αDKL(πν∥π)[s]],(11)\sup_{\nu\in\mathcal{V}_r}-\mathbb{E}_{s\sim d^\pi}\left[\mathbb{E}_{a\sim\pi_\nu}[A^\pi(s,a)]-\alpha D_{\mathrm{KL}}(\pi_\nu\|\pi)[s]\right], \tag*{(11)}

where a constant α>0\alpha> 0 controls the strength of the Kullback–Leibler (KL) divergence penalty. In offline RL, such regularization handles occupancy shift by encouraging the learned policy to locally stay close to the behavior policy. In our setting, we use this approach to penalize state adversaries that induce large deviations between πν\pi_\nu and π\pi. The following lemma motivates the calibration of α\alpha.

Lemma 1 (Proof in Appendix A.1). Assume that a transition kernel is LPL_P-Lipschitz continuous w.r.t the action: ∥P(⋅∣s,a1)−P(⋅∣s,a2)∥1≤LP∥a1−a2∥1\|P(\cdot|s,a_1)-P(\cdot|s,a_2)\|_1 \le L_P\|a_1-a_2\|_1 for all s∈Ss \in S and for all a1,a2∈Aa_1,a_2 \in A, and a stochastic policy π\pi is LπL_\pi-Lipschitz continuous from states to action distributions: W1(π(⋅∣s1),π(⋅∣s2))≤Lπ∥s1−s2∥∞W_1(\pi(\cdot|s_1),\pi(\cdot|s_2)) \le L_\pi\|s_1-s_2\|_\infty for all s1,s2∈Swheres_1,s_2 \in S whereW_1$ is the 1-Wasserstein distance induced by the L1L_1-norm on the action space AA. Then for any state adversary ν∈Vr\nu\in\mathcal{V}_r,

DTV(dπ,dπν)≤γLPLπrmax⁡2(1−γ).(12)D_{\mathrm{TV}}(d^\pi,d^{\pi_\nu}) \le\frac{\gamma L_P L_\pi r_{\max}}{2(1-\gamma)}. \tag*{(12)}

Although DTV(dπ,dπν)D_{\mathrm{TV}}(d^\pi,d^{\pi_\nu}) is over the entire state space and the Lipschitz assumption on transition dynamics is often violated in continuous control tasks, Lemma 1 indicates that the occupancy shift can depend on both the policy sensitivity and environment dynamics. This observation motivates calibrating α\alpha separately for each environment and policy algorithm. In practice, we determine α\alpha empirically according to diagnostics obtained from trajectories sampled by π\pi, and keep it fixed throughout the synthesis and evaluation of PD-NUUS. We also provide an O(α−1)O(\alpha^{-1}) upper bound on the possible violation of the prescribed degradation tolerance β\beta. Increasing α\alpha reduces this upper bound, although it does not necessarily make the actual degradation decrease monotonically.

Lemma 2 (Proof in Appendix A.2). Consider a fixed policy π\pi, γ∈(0,1)\gamma\in(0, 1), and α,β>0\alpha, \beta> 0. After using the surrogate constraint in Eq. (11), the supremum degradation of discounted return satisfies the following upper bound

sup⁡ν∈Vr[J(π)−J(πν)]−β≤γ2(max⁡s,a∣Aπ(s,a)∣)22α(1−γ)3.(13)\sup_{\nu\in\mathcal{V}_r} [J(\pi) - J(\pi_\nu)] - \beta\le\frac{\gamma^2(\max_{s,a} |A^\pi(s,a)|)^2}{2\alpha(1-\gamma)^3}. \tag*{(13)}

Reformulation with a Convex Quadratic Constraint

The detailed derivation is provided in Appendix § 10. To express Eq. (11) more directly in terms of r(s)r(s), we approximate the perturbed policy πν\pi_\nu using a second-order Taylor expansion, and approximate the local KL divergence DKL(πν∥π)[s]D_{\mathrm{KL}}(\pi_\nu\|\pi)[s] using the state Fisher information matrix. Letting δ(s)=ν(s)−s\delta(s) = \nu(s) - s, the resulting supremum over ν∈Vr\nu\in\mathcal{V}_r becomes

sup⁡δ:∣δi(s)∣≤ri(s){12δ(s)⊤Hπ,α(s)δ(s)−gπ(s)⊤δ(s)}.(14)\sup_{\delta:|\delta_i(s)|\le r_i(s)} \left\{ \frac{1}{2}\delta(s)^\top H_{\pi,\alpha}(s)\delta(s) - g_\pi(s)^\top\delta(s) \right\}. \tag*{(14)}

where

Hπ,α(s)=αEa∼π[∇slog⁡π(a∣s)∇slog⁡π(a∣s)⊤−Ea∼π[Aπ(s,a)(∇slog⁡π(a∣s)∇slog⁡π(a∣s)⊤+∇s2log⁡π(a∣s))]],(15)H_{\pi,\alpha}(s) = \alpha\mathbb{E}_{a\sim\pi}\left[\nabla_s\log\pi(a|s)\nabla_s\log\pi(a|s)^\top- \mathbb{E}_{a\sim\pi}\left[A^\pi(s,a)\left(\nabla_s\log\pi(a|s)\nabla_s\log\pi(a|s)^\top+\nabla_s^2\log\pi(a|s)\right)\right]\right], \tag*{(15)}

and

gπ(s)=Ea∼π[Aπ(s,a)∇slog⁡π(a∣s)].(16)g_\pi(s) = \mathbb{E}_{a\sim\pi}\left[A^\pi(s,a)\nabla_s\log\pi(a|s)\right]. \tag*{(16)}

The matrix Hπ,α(s)H_{\pi,\alpha}(s) is symmetric but not necessarily positive semidefinite. Consequently, Eq. (14) does not generally admit a simple analytical solution. To obtain a closed-form solution, we construct a diagonal positive-definite matrix Mπ,α(s)M_{\pi,\alpha}(s) which upper bounds Hπ,α(s)H_{\pi,\alpha}(s) in the Loewner order, meaning Mπ,α(s)⪰Hπ,α(s)M_{\pi,\alpha}(s) \succeq H_{\pi,\alpha}(s). This indicates that δ(s)⊤Mπ,α(s)δ(s)≥δ(s)⊤Hπ,α(s)δ(s)\delta(s)^\top M_{\pi,\alpha}(s)\delta(s) \ge\delta(s)^\top H_{\pi,\alpha}(s)\delta(s) holds for every δ(s)\delta(s). We implement Mπ,α(s)M_{\pi,\alpha}(s) as a separable quadratic surrogate (SQS) majorization [14]:

Mπ,α(s)=diag⁡j[∑i=1m∣[Hπ,α(s)]ij∣]+τI,(17)M_{\pi,\alpha}(s) = \operatorname{diag}_j\left[\sum_{i=1}^{m}|[H_{\pi,\alpha}(s)]_{ij}|\right] + \tau I, \tag*{(17)}

where τ>0\tau> 0 is a small offset. Since Mπ,α(s)M_{\pi,\alpha}(s) is diagonal with positive diagonal entries, the majorized supremum is separable across dimensions and can be evaluated exactly:

sup⁡δ:∣δi(s)∣≤ri(s){12δ(s)⊤Hπ,α(s)δ(s)−gπ(s)⊤δ(s)}≤12r(s)⊤Mπ,α(s)r(s)+∣gπ(s)∣⊤r(s).(18)\sup_{\delta:|\delta_i(s)|\le r_i(s)} \left\{ \frac{1}{2}\delta(s)^\top H_{\pi,\alpha}(s)\delta(s) - g_\pi(s)^\top\delta(s) \right\} \le\frac{1}{2}r(s)^\top M_{\pi,\alpha}(s)r(s) + |g_\pi(s)|^\top r(s). \tag*{(18)}

We replace the supremum in the surrogate constraint with the upper bound in Eq. (18). Although the majorization induces a more conservative solution for r(⋅)r(\cdot), it renders the constraint convex and analytically tractable. Finally, we obtain a tractable optimization problem for PD-NUUS with β>0\beta> 0:

max⁡rEs∼dπ[1⊤r(s)],(19)\max_r\quad\mathbb{E}_{s\sim d^\pi}[\mathbf{1}^\top r(s)], \tag*{(19)}
s.t.Es∼dπ[12r(s)⊤Mπ,α(s)r(s)+∣gπ(s)∣⊤r(s)]≤(1−γ)β,(20)\text{s.t.}\quad\mathbb{E}_{s\sim d^\pi}\left[\frac{1}{2}r(s)^\top M_{\pi,\alpha}(s)r(s)+|g_\pi(s)|^\top r(s)\right]\le(1-\gamma)\beta, \tag*{(20)}
0≤ri(s)≤rmax⁡,∀s∈S, i=1,…,m.(21)0\le r_i(s)\le r_{\max},\quad\forall s\in\mathcal{S},\ i=1,\ldots,m. \tag*{(21)}

Algorithm 1: Evaluate a policy with PD-NUUS.

Input: Policy π\pi, PD-NUUS hyperparameters α,β\alpha,\beta, observation attacker ν\nu.

Output: Trajectories with PD-NUUS synthesized based on each visited state.

  1. Pre-sample trajectories with π\pi and estimate κ\kappa in Eq. (86).

  2. for each episode do

  3. &nbsp;&nbsp;&nbsp;&nbsp;for time step t=1…Tt=1\ldots T do

  4. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Observe the current true state sts_t.

  5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Calculate r∗(st)r^*(s_t) with Eq. (85).

  6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Create a PD-NUUS Br(st)B_r(s_t) in Eq. (58) via r∗(st)r^*(s_t).

  7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Use attacker ν\nu to sample a perturbed observed state s^t∼Br(st)\hat{s}_t\sim B_r(s_t).

  8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Predict an action: at∼π(⋅∣s^t)a_t\sim\pi(\cdot|\hat{s}_t).

  9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Step forward with ata_t.

  10. &nbsp;&nbsp;&nbsp;&nbsp;end for

  11. end for

When the optimal solution ri∗(s)r_i^*(s) satisfies 0<ri∗(s)<rmax⁡0<r_i^*(s)<r_{\max} for every state dimension ii, the box constraints are inactive. By complementary slackness, their associate Karush–Kuhn–Tucker (KKT) multipliers vanish and the stationarity condition yields a closed-form solution for β>0\beta>0

r∗(s)=Mπ,α(s)−1(κ1−∣gπ(s)∣),(22)r^*(s)=M_{\pi,\alpha}(s)^{-1}\left(\kappa\mathbf{1}-|g_\pi(s)|\right), \tag*{(22)}

where

κ=2(1−γ)β+Es′∼dπ[∣gπ(s′)∣⊤Mπ,α(s′)−1∣gπ(s′)∣]Es′∼dπ[1⊤Mπ,α(s′)−1].(23)\kappa=\sqrt{\frac{2(1-\gamma)\beta+\mathbb{E}_{s'\sim d^\pi}\left[|g_\pi(s')|^\top M_{\pi,\alpha}(s')^{-1}|g_\pi(s')|\right]}{\mathbb{E}_{s'\sim d^\pi}\left[\mathbf{1}^\top M_{\pi,\alpha}(s')^{-1}\right]}}. \tag*{(23)}

κ\kappa is a global scalar estimated from trajectories collected under the clean policy π\pi, and gπ(s)g_\pi(s) and Mπ,α(s)M_{\pi,\alpha}(s) are defined in Eq. (16) and Eq. (17), respectively. We empirically observe that the interior condition is generally satisfied if α\alpha is appropriately calibrated. However, when a non-negligible portion of ri(s)r_i(s) reaches rmax⁡r_{\max}, the closed-form solution becomes unreliable. We analyze the failures in Appendix D. The closed-form solution leads us to a simple evaluation procedure with PD-NUUS: We first sample trajectories to estimate κ\kappa, then evaluate the policy while synthesizing PD-NUUS online at each visited state. Algorithm 1 presents the pseudocode.

Experimental Results

In this section, we aim to answer the following questions:

  • Does PD-NUUS produce different perturbation scales for different policy algorithms?

  • Is β\beta correlated with the empirical worst-case performance degradation, and how does this relationship compare with that of an L∞L_{\infty}-norm uncertainty set?

  • Does addressing the discrepancy between dTVπd^{\pi}_{\mathrm{TV}} and dπd^{\pi} with non-zero α\alpha improve the quality of PD-NUUS?

Experiment Setup

Algorithms and Environments. We choose PPO (Schulman et al. [20]), SA-PPO-SGLD (Zhang et al. [29]), ATLA-PPO (Zhang et al. [28]), and WocaR-PPO (Liang et al. [11]) for policy training. Except for PPO, all algorithms incorporate dedicated mechanisms for improving robustness against state perturbations. We conduct experiments on Hopper, HalfCheetah, and Walker2d environments from MuJoCo (Todorov, Erez, and Tassa [24]). For each environment and algorithm, we train policies using four random seeds and report the average results. Since synthesizing PD-NUUS requires estimates of the advantage function Aπ(s,a)A^{\pi}(s,a), we train an auxiliary advantage network alongside each policy without changing the underlying policy update rule. The discount factor is fixed at γ=0.99\gamma= 0.99 throughout the experiments.

State Attackers. We consider four attackers that perturb the observed states within a given uncertainty set:

  • Random: Uniformly samples from the uncertainty set.

  • Critic (Zhang et al. [29]): Uses projected gradient descent (PGD) to search for an adversarial state that minimizes the state-value function.

  • Maximal Action Difference (MAD) (Zhang et al. [29]): A critic-free attack that searches for an adversarial state s^\hat{s} by maximizing the KL divergence DKL(π(⋅∣s)∥π(⋅∣s^))D_{\mathrm{KL}}(\pi(\cdot|s)\|\pi(\cdot|\hat{s})).

  • PA-AD (Sun et al. [23]): Formulates state perturbations

as a Policy Adversary MDP (PAMDP), where a director learns to select an adversarial action, and an actor finds a feasible state perturbation that induces the desired policy change. An optimal policy of the PAMDP theoretically induces a state adversary that minimizes the clean policy’s expected discounted return.

According to Zhang et al. [29]; Liang et al. [11], Random and Critic are weaker than PA-AD and MAD. All four attacks were originally formulated for L∞L_\infty-norm uncertainty sets (Zhang et al. [29, 28]; Sun et al. [23]; Liang et al. [11]). To adapt them to PD-NUUS, we replace the budget ϵ\epsilon with ri(s)r_i(s) for every state dimension ii.

Implementation Details. For PD-NUUS, Table 2 reports the value of α\alpha for each environment and algorithm, and we clip the solution r(s)r(s) to [0.001,2.5][0.001, 2.5]. We parameterize the policy π\pi with a Gaussian distribution N(μθ(s),Σ)\mathcal{N}(\mu_\theta(s), \Sigma), where μθ\mu_\theta is a multilayer perceptron for predicting the mean and Σ=diag⁡(σ12,…,σn2)\Sigma= \operatorname{diag}(\sigma_1^2,\ldots,\sigma_n^2) is a diagonal covariance matrix. We exploit this Gaussian policy structure to compute the state Fisher information matrix and approximate the Hessian term in Hπ,α(s)H_{\pi,\alpha}(s) in Eq. (68), using a Gauss-Newton approximation. More implementation details are provided in Appendix C.

PPOSA-PPO-SGLDATLA-PPOWocaR-PPO
Hopper0.150.250.00750.2
HalfCheetah0.060.20.020.075
Walker2d0.0250.0750.050.15

Table 2. The coefficient α\alpha of the KL divergence regularizer in Eq. (11) for each environment and algorithm during policy evaluation with PD-NUUS.

Empirical Results

L∞L_\infty-Norm vs. PD-NUUS. We report the empirical κ\kappa values for synthesizing PD-NUUS in Appendix D. Table 3 compares the empirical degradation in discounted return on HalfCheetah under L∞L_\infty-norm uncertainty sets with ϵ∈{0.05,0.1,0.15,0.2}\epsilon\in\{0.05, 0.1, 0.15, 0.2\} and PD-NUUS with β∈{5,10,20,40}\beta\in\{5, 10, 20, 40\}. Results for Hopper and Walker2d are provided in Appendix D. We use the maximum degradation observed among all attackers as an empirical approximation of the worst-case degradation. As expected, increasing ϵ\epsilon enlarges the L∞L_\infty-norm uncertainty set and generally admits stronger perturbations. However, the relationship between ϵ\epsilon and return degradation is highly algorithm-dependent: SA-PPO-SGLD and WocaR-PPO experience substantially smaller degradation than PPO and ATLA-PPO under the same ϵ\epsilon. In contrast, the tolerance β\beta of PD-NUUS is specified in units of discounted return. The maximum degradation across attackers is better aligned with β\beta than with ϵ\epsilon, and generally remains below or moderately above the tolerance β\beta.

SetParameterAttackerPPOSA-PPO-SGLDATLA-PPOWocaR-PPO
No Attack——421.5 ± 57.5349.4 ± 40.3345.7 ± 24.9331.4 ± 10.4
L∞L_{\infty}-Normϵ=0.05\epsilon= 0.05Random415.0 ± 46.7 (6.5)350.5 ± 40.7 (-1.1)342.9 ± 21.0 (2.8)331.3 ± 10.1 (0.1)
L∞L_{\infty}-Normϵ=0.05\epsilon= 0.05Critic404.7 ± 72.6 (16.8)350.4 ± 39.3 (-1.0)344.3 ± 18.8 (1.4)331.6 ± 10.7 (-0.2)
L∞L_{\infty}-Normϵ=0.05\epsilon= 0.05MAD336.7 ± 47.7 (84.8)349.9 ± 37.5 (-0.5)339.1 ± 21.4 (6.6)328.4 ± 9.3 (3.0)
L∞L_{\infty}-Normϵ=0.05\epsilon= 0.05PA-AD338.3 ± 67.0 (83.2)348.8 ± 38.6 (0.6)313.1 ± 38.0 (32.6)324.8 ± 7.1 (6.6)
L∞L_{\infty}-Normϵ=0.10\epsilon= 0.10Random382.9 ± 44.2 (38.6)350.6 ± 37.9 (-1.2)345.2 ± 19.7 (0.5)328.2 ± 9.0 (3.2)
L∞L_{\infty}-Normϵ=0.10\epsilon= 0.10Critic367.3 ± 98.8 (54.2)350.5 ± 41.5 (-1.1)334.1 ± 17.5 (11.6)329.5 ± 8.1 (1.9)
L∞L_{\infty}-Normϵ=0.10\epsilon= 0.10MAD224.6 ± 58.6 (196.9)348.2 ± 40.0 (1.2)293.0 ± 42.8 (52.7)322.6 ± 7.0 (8.8)
L∞L_{\infty}-Normϵ=0.10\epsilon= 0.10PA-AD168.0 ± 59.8 (253.5)348.0 ± 42.6 (1.4)243.7 ± 44.2 (102.0)328.4 ± 8.0 (3.0)
L∞L_{\infty}-Normϵ=0.15\epsilon= 0.15Random368.3 ± 36.5 (53.2)351.2 ± 38.2 (-1.8)339.6 ± 24.5 (6.1)326.7 ± 9.8 (4.7)
L∞L_{\infty}-Normϵ=0.15\epsilon= 0.15Critic332.2 ± 92.5 (89.3)351.1 ± 39.7 (-1.7)321.5 ± 15.7 (24.2)329.5 ± 10.1 (1.9)
L∞L_{\infty}-Normϵ=0.15\epsilon= 0.15MAD162.1 ± 55.2 (259.4)344.6 ± 37.6 (4.8)232.8 ± 39.9 (112.9)315.3 ± 8.4 (16.1)
L∞L_{\infty}-Normϵ=0.15\epsilon= 0.15PA-AD100.3 ± 47.7 (321.2)339.7 ± 27.3 (9.7)173.8 ± 53.7 (171.9)300.9 ± 17.2 (30.5)
L∞L_{\infty}-Normϵ=0.20\epsilon= 0.20Random321.8 ± 38.5 (99.7)348.5 ± 40.1 (0.9)328.3 ± 26.3 (17.4)324.3 ± 8.5 (7.1)
L∞L_{\infty}-Normϵ=0.20\epsilon= 0.20Critic280.5 ± 100.5 (141.0)347.2 ± 42.7 (2.2)295.5 ± 16.0 (50.2)324.7 ± 12.2 (6.7)
L∞L_{\infty}-Normϵ=0.20\epsilon= 0.20MAD117.1 ± 42.6 (304.4)342.5 ± 38.2 (6.9)164.5 ± 36.9 (181.2)303.2 ± 6.8 (28.2)
L∞L_{\infty}-Normϵ=0.20\epsilon= 0.20PA-AD22.3 ± 33.6 (399.2)337.8 ± 42.7 (11.6)86.6 ± 55.7 (259.1)287.0 ± 12.2 (44.4)
PD-NUUSβ=5\beta= 5Random421.2 ± 60.9 (0.3)350.0 ± 39.9 (-0.6)349.8 ± 22.7 (-4.1)330.1 ± 11.9 (1.3)
PD-NUUSβ=5\beta= 5Critic418.1 ± 56.6 (3.4)350.4 ± 41.3 (-1.0)350.2 ± 20.1 (-4.5)332.1 ± 9.4 (-0.7)
PD-NUUSβ=5\beta= 5MAD409.2 ± 65.3 (12.3)349.6 ± 41.4 (-0.2)349.4 ± 20.0 (-3.7)329.6 ± 9.2 (1.8)
PD-NUUSβ=5\beta= 5PA-AD418.2 ± 60.8 (3.3)346.2 ± 41.2 (3.2)347.9 ± 21.7 (-2.2)329.9 ± 8.9 (1.5)
PD-NUUSβ=10\beta= 10Random417.6 ± 58.1 (3.9)348.3 ± 41.2 (1.1)350.1 ± 19.2 (-4.4)330.4 ± 9.6 (1.0)
PD-NUUSβ=10\beta= 10Critic417.9 ± 59.9 (3.6)351.5 ± 40.4 (-2.1)351.4 ± 18.3 (-5.7)333.4 ± 10.3 (-2.0)
PD-NUUSβ=10\beta= 10MAD422.4 ± 60.0 (-0.9)348.1 ± 38.8 (1.3)346.3 ± 23.8 (-0.6)329.2 ± 11.4 (2.2)
PD-NUUSβ=10\beta= 10PA-AD424.4 ± 58.1 (-2.9)348.6 ± 38.8 (0.8)344.2 ± 21.2 (1.5)325.6 ± 8.6 (5.8)
PD-NUUSβ=20\beta= 20Random409.3 ± 59.1 (12.2)347.7 ± 39.3 (1.7)350.3 ± 21.2 (-4.6)329.8 ± 10.2 (1.6)
PD-NUUSβ=20\beta= 20Critic414.8 ± 65.6 (6.7)350.5 ± 40.4 (-1.1)346.1 ± 20.4 (-0.4)331.4 ± 11.2 (0.0)
PD-NUUSβ=20\beta= 20MAD413.9 ± 68.6 (7.6)346.5 ± 36.8 (2.9)344.1 ± 24.5 (1.6)326.8 ± 12.2 (4.6)
PD-NUUSβ=20\beta= 20PA-AD404.3 ± 54.5 (17.2)345.2 ± 38.7 (4.2)332.3 ± 19.0 (13.4)311.5 ± 13.6 (19.9)
PD-NUUSβ=40\beta= 40Random416.7 ± 59.0 (4.8)347.1 ± 38.1 (2.3)349.6 ± 20.7 (-3.9)321.3 ± 12.8 (10.1)
PD-NUUSβ=40\beta= 40Critic413.6 ± 60.6 (7.9)340.4 ± 36.2 (9.0)335.2 ± 23.4 (10.5)324.0 ± 9.1 (7.4)
PD-NUUSβ=40\beta= 40MAD405.4 ± 61.6 (16.1)330.2 ± 29.4 (19.2)335.8 ± 24.6 (9.9)310.0 ± 11.9 (21.2)
PD-NUUSβ=40\beta= 40PA-AD387.3 ± 68.3 (34.2)327.0 ± 44.3 (22.4)319.6 ± 19.1 (26.1)287.0 ± 24.8 (44.4)

Table 3. Comparison of L∞L_{\infty}-norm uncertainty sets and PD-NUUS on HalfCheetah. Each entry reports the discounted return, with degradation in parentheses. The largest degradation across attackers is in bold. The episode rewards of clean policies are 5275.1 ± 1586.0 (PPO), 4320.3 ± 611.3 (SA-PPO-SGLD), 4267.1 ± 854.5 (ATLA-PPO) and 3952.2 ± 566.3 (WocaR-PPO).

Tolerance Calibration. Table 4 summarizes the empirical maximum degradation in discounted return among all attackers. Although several failure cases occur when β=40\beta= 40, PD-NUUS generally provides more reliable control of empirical degradation for different algorithms. We next quantitatively evaluate whether the tolerance β\beta controls the maximum degradation in Table 4. Requiring the maximum degradation to stay strictly below β\beta as in Eq. (6) is too restrictive, because the surrogate constraint, local approximation errors, SQS majorization and finite-horizon trajectories can introduce discrepancies between the predefined and observed degradations. Therefore, we define the relaxed-tolerance frequency

EnvironmentAlgorithmL∞L_\infty-Norm, ϵ=0.05\epsilon= 0.05ϵ=0.10\epsilon= 0.10ϵ=0.15\epsilon= 0.15ϵ=0.20\epsilon= 0.20PD-NUUS, β=5\beta= 5β=10\beta= 10β=20\beta= 20β=40\beta= 40
HopperPPO52.0162.3168.9198.51.710.02.721.0
SA-PPO-SGLD0.60.60.628.43.95.814.630.8
ATLA-PPO17.378.7103.0136.81.02.524.5127.7
WocaR-PPO1.210.625.7151.72.72.49.321.7
HalfCheetahPPO84.8253.5321.2399.212.33.917.234.2
SA-PPO-SGLD0.61.49.711.63.21.34.222.4
ATLA-PPO32.6102.0171.9259.1-2.21.513.426.1
WocaR-PPO6.68.830.544.41.85.819.944.4
Walker2dPPO50.3139.0162.3205.32.87.760.5105.6
SA-PPO-SGLD1.023.050.3128.916.014.915.4128.3
ATLA-PPO49.0125.7165.1191.50.13.27.912.3
WocaR-PPO2.942.3135.2139.05.61.716.750.0

Table 4. Maximum empirical degradation in discounted return, observed among all state attackers for each environment, algorithm and uncertainty set parameter.

C(τ)=1N∑j=1NI[ΔJmax⁡,j≤(1+τ)β],τ≥0(24)C(\tau) = \frac{1}{N}\sum_{j=1}^{N}\mathbb{I}[\Delta J_{\max,j} \leq(1+\tau)\beta], \quad\tau\geq0 \tag*{(24)}

where N=48N = 48 is the total number of evaluations with PD-NUUS, ΔJmax⁡,j\Delta J_{\max,j} is the empirical maximum degradation in setting jj, and I[X]=1\mathbb{I}[X] = 1 if XX is true and 00 otherwise. Thus, C(τ)C(\tau) denotes the fraction of settings in which the empirical maximum degradation exceeds the tolerance β\beta by no more than a relative margin τ\tau. Table 5 indicates that β\beta provides informative control over the scale of empirical degradation.

τ\tau00.10.20.25
C(τ)C(\tau)77.08%77.08%81.25%85.42%

Table 5. C(τ)C(\tau) values calculated across all PD-NUUS tests.

Ablation Study of the KL Divergence Regularizer. We conduct an ablation study to evaluate the role of the KL divergence regularizer in Eq. (11). Omitting the regularizer induces a solution that completely ignores the occupancy shift for any β\beta value (assuming dπν≈dπd^{\pi_\nu} \approx d^\pi). Table 6 shows that the policy performance degrades substantially without the KL divergence regularizer for both β\beta values and all algorithms.

EnvironmentAlgorithmβ=20\beta= 20β=40\beta= 40
w/w/ow/w/o
HopperPPO2.7228.721.0241.4
HopperSA-PPO-SGLD14.655.030.872.4
HopperATLA-PPO24.5128.1127.7176.7
HopperWocaR-PPO9.3134.521.7183.2
HalfCheetahPPO17.2285.334.2341.7
HalfCheetahSA-PPO-SGLD4.2112.822.4151.5
HalfCheetahATLA-PPO13.4245.126.1284.3
HalfCheetahWocaR-PPO19.9129.444.4157.5
Walker2dPPO60.5256.0105.6273.4
Walker2dSA-PPO-SGLD15.4252.9128.3251.9
Walker2dATLA-PPO7.9211.512.3232.5
Walker2dWocaR-PPO16.7218.750.0203.4

Table 6. Empirical degradation J(π)−J(πν)J(\pi) - J(\pi_\nu) in discounted total returns using PD-NUUS with (w/) and without (w/o) the KL divergence regularizer. With regularization, we report the maximum empirical degradation across four attackers; without regularization (α=0\alpha= 0), we report degradation under PA-AD. Even under this conservative comparison, degradation without regularization substantially exceeds β\beta.

PD-NUUS Visualization Results. In Figure 1, we visualize the synthesized PD-NUUS budgets ri(s)r_i(s) for four algorithms under PA-AD attack. As β\beta increases, the budgets generally increase for all algorithms. SA-PPO-SGLD admits larger perturbations than other algorithms nearly for all dimensions. Under PA-AD attack, PD-NUUS at β=40\beta= 40 reduces episode rewards from 3471.7 ±\pm 391.7 to 2489.8 ±\pm 1287.3 for PPO, from 3203.0 ±\pm 378.5 to 1198.2 ±\pm 1085.3 for SA-PPO-SGLD, from 3227.5 ±\pm 634.9 to 924.3 ±\pm 1323.3 for ATLA-PPO, and from 3358.3 ±\pm 452.8 to 1663.1 ±\pm 1081.5 for WocaR-PPO compared with no attack.

Figure 1. We report the mean and confidence range of the calculated budget function ri(s)r_i(s) for each state dimension across four algorithms and β∈{20,40}\beta\in\{20, 40\} on Hopper under PA-AD attack. The statistics are computed over 200 sampled trajectories.

Limitations and Conclusion

We discuss several limitations of our work here. First, PD-NUUS selects the degradation in expected discounted return as the criterion. However, the discount factor significantly underweight rewards at later time steps. To address this issue, we may extend PD-NUUS to average-return scenarios. In addition, while the surrogate constraint makes the problem tractable, it introduces additional approximations. Finally, in this work we only use PD-NUUS for policy evaluation, and the effects of PD-NUUS on policy training remain unknown. Meanwhile for training, the pre-sampling phase at early training stages may result in unreliable PD-NUUS. Future work should address these concerns for robust policy training.

In summary, we introduce PD-NUUS, an interpretable uncertainty set formulation for observed state perturbations. By formulating its synthesis as a constrained optimization problem, we derive an efficient closed-form solution for analyzing policy robustness. In empirical results, PD-NUUS provides anisotropic uncertainty sets with generally constrained performance degradation.

Proofs

Proof of Lemma 1

Lemma 1. Assume that a transition kernel is LPL_P-Lipschitz continuous w.r.t. the action: ∥P(⋅∣s,a1)−P(⋅∣s,a2)∥1≤LP∥a1−a2∥1\lVert P(\cdot|s,a_1)-P(\cdot|s,a_2)\rVert_1 \le L_P\lVert a_1-a_2\rVert_1 for all s∈Ss \in\mathcal{S} and for all a1,a2∈Aa_1,a_2 \in\mathcal{A}, and a stochastic policy π\pi is LπL_\pi-Lipschitz continuous from states to action distributions: W1(π(⋅∣s1),π(⋅∣s2))≤Lπ∥s1−s2∥∞W_1(\pi(\cdot|s_1),\pi(\cdot|s_2)) \le L_\pi\lVert s_1-s_2\rVert_\infty for all s1,s2∈Ss_1,s_2 \in\mathcal{S} where W1W_1 is the 11-Wasserstein distance induced by the L1L_1-norm on the action space A\mathcal{A}. Then for any state adversary ν∈Vr\nu\in\mathcal{V}_r,

DTV(dπ,dπν)≤γLPLπrmax⁡2(1−γ).(25)D_{\mathrm{TV}}(d^\pi,d^{\pi_\nu}) \le\frac{\gamma L_P L_\pi r_{\max}}{2(1-\gamma)}. \tag*{(25)}

Proof. The proof is motivated by Achiam et al. [1]; Mao et al. [13]. Define

Pπ(s′∣s)≜∫a∈AP(s′∣s,a)π(a∣s) da.(26)P^\pi(s'|s) \triangleq\int_{a\in\mathcal{A}}P(s'|s,a)\pi(a|s)\,da. \tag*{(26)}

The 11-Wasserstein induced by L1L_1-norm on the action space A\mathcal{A} is expressed as

W1(ξ1,ξ2)≜inf⁡ζ∈Γ(ξ1,ξ2)∫∥a−a′∥1ζ(da,da′),(27)W_1(\xi_1,\xi_2) \triangleq\inf_{\zeta\in\Gamma(\xi_1,\xi_2)}\int\lVert a-a'\rVert_1\zeta(da,da'), \tag*{(27)}

where Γ(ξ1,ξ2)\Gamma(\xi_1,\xi_2) denotes the set of couplings whose marginals are ξ1\xi_1 and ξ2\xi_2. Then, for any coupling ζs∈Γ(π(⋅∣s),πν(⋅∣s))\zeta_s\in\Gamma(\pi(\cdot|s),\pi_\nu(\cdot|s)) we upper bound the 11-norm distance

∥Pπ(⋅∣s)−Pπν(⋅∣s)∥1(28)\lVert P^\pi(\cdot|s)-P^{\pi_\nu}(\cdot|s)\rVert_1 \tag*{(28)}
=∥∫AP(s′∣s,a)π(da∣s)−∫AP(s′∣s,a′)πν(da′∣s)∥1(29)= \left\lVert\int_{\mathcal{A}}P(s'|s,a)\pi(da|s)-\int_{\mathcal{A}}P(s'|s,a')\pi_\nu(da'|s)\right\rVert_1 \tag*{(29)}
=∥∫A×A[P(⋅∣s,a)−P(⋅∣s,a′)]ζs(da,da′)∥1(30)= \left\lVert\int_{\mathcal{A}\times\mathcal{A}}[P(\cdot|s,a)-P(\cdot|s,a')]\zeta_s(da,da')\right\rVert_1 \tag*{(30)}
≤∫A×A∥P(⋅∣s,a)−P(⋅∣s,a′)∥1ζs(da,da′)(31)\le\int_{\mathcal{A}\times\mathcal{A}}\lVert P(\cdot|s,a)-P(\cdot|s,a')\rVert_1\zeta_s(da,da') \tag*{(31)}
≤LP∫A×A∥a−a′∥1ζs(da,da′),(32)\le L_P\int_{\mathcal{A}\times\mathcal{A}}\lVert a-a'\rVert_1\zeta_s(da,da'), \tag*{(32)}

which holds for every coupling ζs\zeta_s. Besides, for ν∈Vr\nu\in\mathcal{V}_r we have ∥s−ν(s)∥∞≤∥r(s)∥∞≤rmax⁡\lVert s-\nu(s)\rVert_\infty\le\lVert r(s)\rVert_\infty\le r_{\max} for ∀s∈S\forall s\in\mathcal{S}. Taking the infimum over all couplings yields

DTV(Pπ(⋅∣s),Pπν(⋅∣s))≤LPW1(π(⋅∣s),πν(⋅∣s))(33)D_{\mathrm{TV}}(P^\pi(\cdot|s),P^{\pi_\nu}(\cdot|s))\le L_PW_1(\pi(\cdot|s),\pi_\nu(\cdot|s)) \tag*{(33)}
≤LPLπ∥s−ν(s)∥∞(34)\le L_PL_\pi\lVert s-\nu(s)\rVert_\infty \tag*{(34)}
≤LPLπrmax⁡.(35)\le L_PL_\pi r_{\max}. \tag*{(35)}

The occupancy dπd^\pi is also expressed as:

dπ(s)=(1−γ)ρ+γ∫s′∈SPπ(s∣s′)dπ(s′) ds.(36)d^\pi(s)=(1-\gamma)\rho+\gamma\int_{s'\in\mathcal{S}}P^\pi(s|s')d^\pi(s')\,ds. \tag*{(36)}

Then

dπ(s)−dπν(s)=γ∫s′[Pπ(s∣s′)dπ(s′)−Pπν(s∣s′)dπν(s′)] ds′=γ∫s′Pπ(s∣s′)[dπ(s′)−dπν(s′)] ds′+γ∫s′[Pπ(s∣s′)−Pπν(s∣s′)]dπν(s′) ds′.\begin{aligned} d^\pi(s)-d^{\pi_\nu}(s)=\gamma\int_{s'}[P^\pi(s|s')d^\pi(s')-P^{\pi_\nu}(s|s')d^{\pi_\nu}(s')]\,ds' \\ &=\gamma\int_{s'}P^\pi(s|s')[d^\pi(s')-d^{\pi_\nu}(s')]\,ds' +\gamma\int_{s'}[P^\pi(s|s')-P^{\pi_\nu}(s|s')]d^{\pi_\nu}(s')\,ds'. \end{aligned}

Let Δ(s)≜dπ(s)−dπν(s)\Delta(s)\triangleq d^\pi(s)-d^{\pi_\nu}(s) then use the triangle inequality

∥Δ∥1:=∫s∣Δ(s)∣ ds(37)\lVert\Delta\rVert_1:=\int_s|\Delta(s)|\,ds \tag*{(37)}
≤γ∫s∫s′Pπ(s∣s′)∣dπ(s′)−dπν(s′)∣ ds′ ds+γ∫s∫s′∣Pπ(s∣s′)−Pπν(s∣s′)∣dπν(s′) ds′ ds(38)\le\gamma\int_s\int_{s'}P^\pi(s|s')|d^\pi(s')-d^{\pi_\nu}(s')|\,ds'\,ds +\gamma\int_s\int_{s'}|P^\pi(s|s')-P^{\pi_\nu}(s|s')|d^{\pi_\nu}(s')\,ds'\,ds \tag*{(38)}
=γ∫s′∣Δ(s′)∣[∫sPπ(s∣s′) ds]ds′+γ∫s′dπν(s′)[∫s∣Pπ(s∣s′)−Pπν(s∣s′)∣ ds]ds′(39)=\gamma\int_{s'}|\Delta(s')|\left[\int_sP^\pi(s|s')\,ds\right]ds' +\gamma\int_{s'}d^{\pi_\nu}(s')\left[\int_s|P^\pi(s|s')-P^{\pi_\nu}(s|s')|\,ds\right]ds' \tag*{(39)}
≤γ∥Δ∥1+γ∫s′dπν(s′)∥Pπ(⋅∣s′)−Pπν(⋅∣s′)∥1 ds′(40)\le\gamma\lVert\Delta\rVert_1+\gamma\int_{s'}d^{\pi_\nu}(s')\lVert P^\pi(\cdot|s')-P^{\pi_\nu}(\cdot|s')\rVert_1\,ds' \tag*{(40)}
≤γ∥Δ∥1+γsup⁡s′∈S∥Pπ(⋅∣s′)−Pπν(⋅∣s′)∥1.(41)\le\gamma\lVert\Delta\rVert_1+\gamma\sup_{s'\in\mathcal{S}}\lVert P^\pi(\cdot|s')-P^{\pi_\nu}(\cdot|s')\rVert_1. \tag*{(41)}

This indicates

∥Δ∥1≤γ1−γsup⁡s′∈S∥Pπ(⋅∣s′)−Pπν(⋅∣s′)∥1.(42)\lVert\Delta\rVert_1\le\frac{\gamma}{1-\gamma}\sup_{s'\in\mathcal{S}}\lVert P^\pi(\cdot|s')-P^{\pi_\nu}(\cdot|s')\rVert_1. \tag*{(42)}

Since DTV(dπ,dπν)=12∥Δ∥1D_{\mathrm{TV}}(d^\pi,d^{\pi_\nu})=\frac{1}{2}\lVert\Delta\rVert_1, from Eq. (35) we get

DTV(dπ,dπν)≤γ2(1−γ)sup⁡s′∈S∥Pπ(⋅∣s′)−Pπν(⋅∣s′)∥1(43)D_{\mathrm{TV}}(d^\pi,d^{\pi_\nu})\le\frac{\gamma}{2(1-\gamma)}\sup_{s'\in\mathcal{S}}\lVert P^\pi(\cdot|s')-P^{\pi_\nu}(\cdot|s')\rVert_1 \tag*{(43)}
≤γLPLπrmax⁡2(1−γ).(44)\le\frac{\gamma L_PL_\pi r_{\max}}{2(1-\gamma)}. \tag*{(44)}

This completes the proof.

Proof of Lemma 2

Lemma 2. Consider a fixed policy π\pi, γ∈(0,1)\gamma\in(0,1), and α,β>0\alpha,\beta>0. After using the surrogate constraint in Eq. (11), the supremum degradation of discounted return satisfies the following upper bound

sup⁡ν∈Vr[J(π)−J(πν)]−β≤γ2(max⁡s,a∣Aπ(s,a)∣)22α(1−γ)3.(45)\sup_{\nu\in\mathcal{V}_r}[J(\pi)-J(\pi_\nu)]-\beta\le\frac{\gamma^2(\max_{s,a}|A^\pi(s,a)|)^2}{2\alpha(1-\gamma)^3}. \tag*{(45)}

Proof. Fix an arbitrary adversary ν∈Vr\nu\in\mathcal{V}_r and denote

ℓν(s)=−Ea∼πν(⋅∣s)[Aπ(s,a)],(46)\ell_\nu(s)=-\mathbb{E}_{a\sim\pi_\nu(\cdot|s)}[A^\pi(s,a)], \tag*{(46)}
Kν=Es∼dπ[DKL(πν(⋅∣s)∥π(⋅∣s))],(47)K_\nu=\mathbb{E}_{s\sim d^\pi}\left[D_{\mathrm{KL}}(\pi_\nu(\cdot|s)\Vert\pi(\cdot|s))\right], \tag*{(47)}
Sα(ν)=Es∼dπ[ℓν(s)]+αKν.(48)S_\alpha(\nu)=\mathbb{E}_{s\sim d^\pi}[\ell_\nu(s)]+\alpha K_\nu. \tag*{(48)}

Surrogate feasibility implies

Sα(ν)≤(1−γ)β,∀ν∈Vr.(49)S_\alpha(\nu)\le(1-\gamma)\beta,\quad\forall\nu\in\mathcal{V}_r. \tag*{(49)}

By the performance difference lemma,

J(π)−J(πν)=11−γEs∼dπν[ℓν(s)].(50)J(\pi)-J(\pi_\nu)=\frac{1}{1-\gamma}\mathbb{E}_{s\sim d^{\pi_\nu}}[\ell_\nu(s)]. \tag*{(50)}

::: Denote G=max⁡s,a∣Aπ(s,a)∣G = \max_{s,a} |A^\pi(s,a)|, for every ν∈Vr\nu\in\mathcal{V}_r,

max⁡s∣Ea∼πν(⋅∣s)[Aπ(s,a)]∣≤max⁡sEa∼πν(⋅∣s)[∣Aπ(s,a)∣]≤max⁡s,a∣Aπ(s,a)∣=G.(51)\max_s \left|\mathbb{E}_{a\sim\pi_\nu(\cdot|s)}[A^\pi(s,a)]\right| \le\max_s \mathbb{E}_{a\sim\pi_\nu(\cdot|s)}[|A^\pi(s,a)|] \le\max_{s,a}|A^\pi(s,a)| = G. \tag*{(51)}

Applying Corollary 1 and 3 of Achiam et al. [1] with π′=πν\pi'=\pi_\nu, together with GG, gives

Es∼dπν[ℓν(s)]≤Es∼dπ[ℓν(s)]+CKν,(52)\mathbb{E}_{s\sim d^{\pi_\nu}}[\ell_\nu(s)] \le\mathbb{E}_{s\sim d^\pi}[\ell_\nu(s)] + C\sqrt{K_\nu}, \tag*{(52)}

where

C=2γG1−γ.(53)C = \frac{\sqrt{2\gamma}G}{1-\gamma}. \tag*{(53)}

For α>0\alpha> 0, Young’s inequality yields

CKν≤αKν+C24α.(54)C\sqrt{K_\nu} \le\alpha K_\nu+ \frac{C^2}{4\alpha}. \tag*{(54)}

Equivalently, this follows by expanding (αKν−C/(2α))2≥0(\sqrt{\alpha K_\nu} - C/(2\sqrt{\alpha}))^2 \ge0. Then

(1−γ)[J(π)−J(πν)]≤Es∼dπ[ℓν(s)]+CKν=Es∼dπ[ℓν(s)]+αKν+C24α≤Sα(ν)+C24α≤(1−γ)β+C24α.(55)\begin{aligned} (1-\gamma)[J(\pi)-J(\pi_\nu)] &\le\mathbb{E}_{s\sim d^\pi}[\ell_\nu(s)] + C\sqrt{K_\nu}\\ &= \mathbb{E}_{s\sim d^\pi}[\ell_\nu(s)] + \alpha K_\nu+ \frac{C^2}{4\alpha}\\ &\le S_\alpha(\nu) + \frac{C^2}{4\alpha}\\ &\le(1-\gamma)\beta+ \frac{C^2}{4\alpha}. \tag*{(55)} \end{aligned}

Dividing by 1−γ1-\gamma and substituting the definition of CC gives

J(π)−J(πν)−β≤γ2G22α(1−γ)3.(56)J(\pi)-J(\pi_\nu)-\beta\le\frac{\gamma^2G^2}{2\alpha(1-\gamma)^3}. \tag*{(56)}

Since ν\nu was arbitrary and GG is independent of the adversary class Vr\mathcal{V}_r, taking the supremum over ν∈Vr\nu\in\mathcal{V}_r proves the lemma.

Derivation of a Closed-Form Solution

Reformulate the Surrogate Constraint

The original constrained optimization problem is intractable because it relies on dπνd^{\pi_\nu} which requires the knowledge of both the transition dynamics and the perturbed policy πν\pi_\nu, while the exact πν\pi_\nu is unknown but only known to be constrained by a PD-NUUS Br(s)B_r(s) and an admissible set Vr\mathcal{V}_r of state adversary

Vr≜{ν:S→S∣ν(s)∈Br(s), ∀s∈S},(57)\mathcal{V}_r \triangleq\{\nu:\mathcal{S}\to\mathcal{S}\mid\nu(s)\in B_r(s),\ \forall s\in\mathcal{S}\}, \tag*{(57)}
Br(s)≜{s^∈S∣∣si−s^i∣≤ri(s), i=1,…,m}.(58)B_r(s) \triangleq\{\hat{s}\in\mathcal{S}\mid|s_i-\hat{s}_i|\le r_i(s),\ i=1,\ldots,m\}. \tag*{(58)}

We propose a surrogate constraint

sup⁡ν∈Vr−Es∼dπ[Ea∼πν[Aπ(s,a)]−αDKL(πν∥π)[s]](59)\sup_{\nu\in\mathcal{V}_r} -\mathbb{E}_{s\sim d^\pi}\left[\mathbb{E}_{a\sim\pi_\nu}[A^\pi(s,a)]-\alpha D_{\mathrm{KL}}(\pi_\nu\Vert\pi)[s]\right] \tag*{(59)}

to make the problem tractable. This constraint is still dependent on ν\nu, and we express it as a function of r(s)r(s).

Let δ(s)=ν(s)−s\delta(s)=\nu(s)-s, then the perturbed policy πν\pi_\nu is approximated by a second-order Taylor expansion

πν(a∣s)(60)\pi_\nu(a|s) \tag*{(60)}
=π(a∣s)+∇sπ(a∣s)⊤δ(s)+12δ(s)⊤∇s2π(a∣s)δ(s)+o(∥δ∥22)(61)= \pi(a|s) + \nabla_s\pi(a|s)^\top\delta(s) + \frac{1}{2}\delta(s)^\top\nabla_s^2\pi(a|s)\delta(s) + o(\|\delta\|_2^2) \tag*{(61)}
≈π(a∣s)[1+∇slog⁡π(a∣s)⊤δ(s)+12δ(s)⊤(∇slog⁡π(a∣s)∇slog⁡π(a∣s)⊤+∇s2log⁡π(a∣s))δ(s)].(62)\approx\pi(a|s)\left[1+\nabla_s\log\pi(a|s)^\top\delta(s) +\frac{1}{2}\delta(s)^\top\left(\nabla_s\log\pi(a|s)\nabla_s\log\pi(a|s)^\top+\nabla_s^2\log\pi(a|s)\right)\delta(s)\right]. \tag*{(62)}

The KL divergence is approximated by using the state Fisher information matrix Fπ(s)F_\pi(s)

DKL(πν∥π)[s]≈12δ(s)⊤Fπ(s)δ(s),(63)D_{\mathrm{KL}}(\pi_\nu\Vert\pi)[s]\approx\frac{1}{2}\delta(s)^\top F_\pi(s)\delta(s), \tag*{(63)}
Fπ(s)≜Ea∼π[∇slog⁡π(a∣s)∇slog⁡π(a∣s)⊤].(64)F_\pi(s)\triangleq\mathbb{E}_{a\sim\pi}[\nabla_s\log\pi(a|s)\nabla_s\log\pi(a|s)^\top]. \tag*{(64)}

Since Ea∼π[Aπ(s,a)]=0\mathbb{E}_{a\sim\pi}[A^\pi(s,a)]=0, we get that

Ea∼πν[Aπ(s,a)]−αDKL(πν∥π)[s]=Ea∼π[πν(a∣s)π(a∣s)Aπ(s,a)]−αDKL(πν∥π)[s](65)\mathbb{E}_{a\sim\pi_\nu}[A^\pi(s,a)]-\alpha D_{\mathrm{KL}}(\pi_\nu\Vert\pi)[s] = \mathbb{E}_{a\sim\pi}\left[\frac{\pi_\nu(a|s)}{\pi(a|s)}A^\pi(s,a)\right]-\alpha D_{\mathrm{KL}}(\pi_\nu\Vert\pi)[s] \tag*{(65)}
≈Ea∼π[Aπ(s,a)∇slog⁡π(a∣s)⊤δ(s)+Aπ(s,a)2δ(s)⊤(∇slog⁡π(a∣s)∇slog⁡π(a∣s)⊤+∇s2log⁡π(a∣s))δ(s)]−α2δ(s)⊤Fπ(s)δ(s)(66)\begin{aligned} &\approx\mathbb{E}_{a\sim\pi}\left[A^\pi(s,a)\nabla_s\log\pi(a|s)^\top\delta(s)\right.\\ &\quad\left.+\frac{A^\pi(s,a)}{2}\delta(s)^\top\left(\nabla_s\log\pi(a|s)\nabla_s\log\pi(a|s)^\top+\nabla_s^2\log\pi(a|s)\right)\delta(s)\right]\\ &\quad-\frac{\alpha}{2}\delta(s)^\top F_\pi(s)\delta(s) \tag*{(66)} \end{aligned}
=−12δ(s)⊤Hπ,α(s)δ(s)+gπ(s)⊤δ(s),(67)= -\frac{1}{2}\delta(s)^\top H_{\pi,\alpha}(s)\delta(s)+g_\pi(s)^\top\delta(s), \tag*{(67)}

where

Hπ,α(s)=αFπ(s)−Ea∼π[Aπ(s,a)(∇slog⁡π(a∣s)∇slog⁡π(a∣s)⊤+∇s2log⁡π(a∣s))],(68)H_{\pi,\alpha}(s)=\alpha F_\pi(s)-\mathbb{E}_{a\sim\pi}\left[A^\pi(s,a)\left(\nabla_s\log\pi(a|s)\nabla_s\log\pi(a|s)^\top+\nabla_s^2\log\pi(a|s)\right)\right], \tag*{(68)}

and

gπ(s)=Ea∼π[Aπ(s,a)∇slog⁡π(a∣s)].(69)g_\pi(s)=\mathbb{E}_{a\sim\pi}[A^\pi(s,a)\nabla_s\log\pi(a|s)]. \tag*{(69)}

Then the surrogate constraint is equivalent to

Es∼dπ[sup⁡δ(s){12δ(s)⊤Hπ,α(s)δ(s)−gπ(s)⊤δ(s)}](70)\mathbb{E}_{s\sim d^\pi}\left[\sup_{\delta(s)}\left\{\frac{1}{2}\delta(s)^\top H_{\pi,\alpha}(s)\delta(s)-g_\pi(s)^\top\delta(s)\right\}\right] \tag*{(70)}

where ∣δi(s)∣≤ri(s)|\delta_i(s)|\le r_i(s) holds for each state dimension ii. However, Hπ,α(s)H_{\pi,\alpha}(s) is not necessarily positive semidefinite, and if this happens then the problem generally does not have a closed-form solution. To derive a closed-form solution, we construct a positive definite matrix Mπ,α(s)M_{\pi,\alpha}(s), satisfying both Mπ,α(s)≻0M_{\pi,\alpha}(s)\succ0 and Mπ,α(s)⪰Hπ,α(s)M_{\pi,\alpha}(s)\succeq H_{\pi,\alpha}(s). This indicates that δ(s)⊤Mπ,α(s)δ(s)≥δ(s)⊤Hπ,α(s)δ(s)\delta(s)^\top M_{\pi,\alpha}(s)\delta(s)\ge\delta(s)^\top H_{\pi,\alpha}(s)\delta(s) holds for every δ(s)\delta(s). We implement Mπ,α(s)M_{\pi,\alpha}(s) using SQP majorization as in Section 4.2. Then we obtain a convex constraint by:

sup⁡δ(s){12δ(s)THπ,α(s)δ(s)−gπ(s)Tδ(s)}(71)\sup_{\delta(s)} \left\{ \frac{1}{2}\delta(s)^{\mathsf{T}}H_{\pi,\alpha}(s)\delta(s)-g_{\pi}(s)^{\mathsf{T}}\delta(s) \right\} \tag*{(71)}
≤sup⁡δ(s){12δ(s)TMπ,α(s)δ(s)−gπ(s)Tδ(s)}(72)\le\sup_{\delta(s)} \left\{ \frac{1}{2}\delta(s)^{\mathsf{T}}M_{\pi,\alpha}(s)\delta(s)-g_{\pi}(s)^{\mathsf{T}}\delta(s) \right\} \tag*{(72)}
=12r(s)TMπ,α(s)r(s)+∣gπ(s)∣Tr(s).(73)= \frac{1}{2}r(s)^{\mathsf{T}}M_{\pi,\alpha}(s)r(s)+\lvert g_{\pi}(s)\rvert^{\mathsf{T}}r(s). \tag*{(73)}

Finally, the problem of PD-NUUS is reformulated as a tractable constrained problem:

max⁡r Es∼dπ[1Tr(s)],(74)\max_{r}\ \mathbb{E}_{s\sim d^{\pi}}\left[\mathbf{1}^{\mathsf{T}}r(s)\right], \tag*{(74)}
s.t.Es∼dπ[12r(s)TMπ,α(s)r(s)+∣gπ(s)∣Tr(s)]≤(1−γ)β,0≤ri(s)≤rmax⁡,∀s∈S, i=1,…,m.(75)\begin{aligned} \mathrm{s.t.}\quad&\mathbb{E}_{s\sim d^{\pi}}\left[\frac{1}{2}r(s)^{\mathsf{T}}M_{\pi,\alpha}(s)r(s) + \lvert g_{\pi}(s)\rvert^{\mathsf{T}}r(s)\right] \le(1-\gamma)\beta,\\ &0\le r_i(s)\le r_{\max},\quad\forall s\in\mathcal{S},\ i=1,\ldots,m. \tag*{(75)} \end{aligned}
0≤ri(s)≤rmax⁡,∀s∈S, i=1,…,m.(76)0\le r_i(s)\le r_{\max},\quad\forall s\in\mathcal{S},\ i=1,\ldots,m. \tag*{(76)}

Derive a Closed-Form Solution

The Lagrangian is constructed with λ≥0\lambda\ge0, η(s)⪰0\eta(s)\succeq0 and ξ(s)⪰0\xi(s)\succeq0.

L(r,λ,η,ξ)=−Es∼dπ[1Tr(s)]+λ(Es∼dπ[12r(s)TMπ,α(s)r(s)+∣gπ(s)∣Tr(s)]−(1−γ)β)−Es∼dπ[η(s)Tr(s)]+Es∼dπ[ξ(s)T(r(s)−rmax⁡)].(77)\begin{aligned} \mathcal{L}(r,\lambda,\eta,\xi)={}&-\mathbb{E}_{s\sim d^{\pi}}\left[\mathbf{1}^{\mathsf{T}}r(s)\right]\\ &+\lambda\left(\mathbb{E}_{s\sim d^{\pi}}\left[\frac{1}{2}r(s)^{\mathsf{T}}M_{\pi,\alpha}(s)r(s)+\lvert g_{\pi}(s)\rvert^{\mathsf{T}}r(s)\right]-(1-\gamma)\beta\right)\\ &-\mathbb{E}_{s\sim d^{\pi}}\left[\eta(s)^{\mathsf{T}}r(s)\right]+\mathbb{E}_{s\sim d^{\pi}}\left[\xi(s)^{\mathsf{T}}(r(s)-r_{\max})\right]. \tag*{(77)} \end{aligned}

When the optimal solution r∗(s)r^{*}(s) satisfies 0<ri∗(s)<rmax⁡0<r_i^{*}(s)<r_{\max} for every state dimension ii, by complementary slackness we have

η(s)Tr∗(s)=0(78)\eta(s)^{\mathsf{T}}r^{*}(s)=0 \tag*{(78)}
ξ(s)T(r∗(s)−rmax⁡)=0(79)\xi(s)^{\mathsf{T}}(r^{*}(s)-r_{\max})=0 \tag*{(79)}
λ(Es∼dπ[12r∗(s)TMπ,α(s)r∗(s)+∣gπ(s)∣Tr∗(s)]−(1−γ)β)=0(80)\lambda\left(\mathbb{E}_{s\sim d^{\pi}}\left[\frac{1}{2}r^{*}(s)^{\mathsf{T}}M_{\pi,\alpha}(s)r^{*}(s)+\lvert g_{\pi}(s)\rvert^{\mathsf{T}}r^{*}(s)\right]-(1-\gamma)\beta\right)=0 \tag*{(80)}

for all sampled states and each state dimension ii. Since 0<ri∗(s)<rmax⁡0<r_i^{*}(s)<r_{\max}, the only solution is that η(s)=ξ(s)=0\eta(s)=\xi(s)=0. Then we differentiate with respect to r(s)r(s)

∂L∂r(s)=−1+λ(Mπ,α(s)r(s)+∣gπ(s)∣).(81)\frac{\partial\mathcal{L}}{\partial r(s)}=-\mathbf{1}+\lambda\left(M_{\pi,\alpha}(s)r(s)+\lvert g_{\pi}(s)\rvert\right). \tag*{(81)}

For the optimal solution r∗(s)r^{*}(s) we have this gradient equals 0, meaning

−1+λ(Mπ,α(s)r∗(s)+∣gπ(s)∣)=0(82)-\mathbf{1}+\lambda\left(M_{\pi,\alpha}(s)r^{*}(s)+\lvert g_{\pi}(s)\rvert\right)=0 \tag*{(82)}

Since Mπ,α(s)≻0M_{\pi,\alpha}(s)\succ0, r∗(s)>0r^{*}(s)>0 and ∣gπ(s)∣⪰0\lvert g_{\pi}(s)\rvert\succeq0, λ=0\lambda=0 does not allow this to happen. Therefore, λ>0\lambda>0 holds and we

r∗(s)=Mπ,α(s)−1(1λ1−∣gπ(s)∣),(83)r^{*}(s)=M_{\pi,\alpha}(s)^{-1}\left(\frac{1}{\lambda}\mathbf{1}-\lvert g_{\pi}(s)\rvert\right), \tag*{(83)}

and Eq. (80) is equivalent to

Es∼dπ[12r∗(s)TMπ,α(s)r∗(s)+∣gπ(s)∣Tr∗(s)]=(1−γ)β.(84)\mathbb{E}_{s\sim d^{\pi}}\left[\frac{1}{2}r^{*}(s)^{\mathsf{T}}M_{\pi,\alpha}(s)r^{*}(s)+\lvert g_{\pi}(s)\rvert^{\mathsf{T}}r^{*}(s)\right]=(1-\gamma)\beta. \tag*{(84)}

Solving r∗(s)r^{*}(s) in Eq. (83) and (84) derives our closed-form solution

r∗(s)=Mπ,α(s)−1(κ1−∣gπ(s)∣),(85)r^{*}(s)=M_{\pi,\alpha}(s)^{-1}\left(\kappa\mathbf{1}-\lvert g_{\pi}(s)\rvert\right), \tag*{(85)}

where

κ=2(1−γ)β+Es′∼dπ[∣gπ(s′)∣TMπ,α(s′)−1∣gπ(s′)∣]Es′∼dπ[1TMπ,α(s′)−11].(86)\kappa=\sqrt{\frac{2(1-\gamma)\beta+\mathbb{E}_{s'\sim d^{\pi}}\left[\lvert g_{\pi}(s')\rvert^{\mathsf{T}}M_{\pi,\alpha}(s')^{-1}\lvert g_{\pi}(s')\rvert\right]}{\mathbb{E}_{s'\sim d^{\pi}}\left[\mathbf{1}^{\mathsf{T}}M_{\pi,\alpha}(s')^{-1}\mathbf{1}\right]}}. \tag*{(86)}

However, the closed-form solution is based on 0<ri(s)<rmax⁡0<r_i(s)<r_{\max}, and we have to calibrate α\alpha to guarantee that

0<Mπ,α(s)−1(κ1−∣gπ(s)∣)<rmax⁡.(87)0<M_{\pi,\alpha}(s)^{-1}\left(\kappa\mathbf{1}-\lvert g_{\pi}(s)\rvert\right)<r_{\max}. \tag*{(87)}

Additional Implementation Details

Exploit Gaussian Policy for PD-NUUS

In our experiments, the policy is parameterized as a Gaussian distribution π(⋅∣s)=N(μ(s),Σ)\pi(\cdot\mid s)=\mathcal{N}(\mu(s),\Sigma) where μ(s)\mu(s) is a neural network for predicting the mean, and Σ=diag⁡(σ12,…,σd2)\Sigma=\operatorname{diag}(\sigma_1^2,\ldots,\sigma_d^2) is a learnable but state-independent diagonal covariance matrix. The terms Hπ,α(s)H_{\pi,\alpha}(s) and gπ(s)g_{\pi}(s) in Eq. (68) and (69) involve ∇slog⁡π(a∣s)\nabla_s\log\pi(a\mid s), ∇s2log⁡π(a∣s)\nabla_s^2\log\pi(a\mid s), and Aπ(s,a)A^{\pi}(s,a) in the expectation terms. We leverage the structure of Gaussian policy to avoid explicitly estimating ∇slog⁡π(a∣s)\nabla_s\log\pi(a\mid s) and ∇s2log⁡π(a∣s)\nabla_s^2\log\pi(a\mid s). Let Jμ(s)=∂μ(s)∂sJ_{\mu}(s)=\frac{\partial\mu(s)}{\partial s} denote the Jacobian matrix of the policy mean w.r.t. the state, our implementation uses

gπ(s)=Jμ(s)TEa∼π[∇aAπ(s,a)](88)g_{\pi}(s)=J_{\mu}(s)^{\mathsf{T}}\mathbb{E}_{a\sim\pi}\left[\nabla_a A^{\pi}(s,a)\right] \tag*{(88)}

and

Hπ,α(s)≈αJμ(s)TΣ−1Jμ(s)−Jμ(s)TEa∼π[∇a2Aπ(s,a)]Jμ(s)(89)H_{\pi,\alpha}(s)\approx\alpha J_{\mu}(s)^{\mathsf{T}}\Sigma^{-1}J_{\mu}(s)-J_{\mu}(s)^{\mathsf{T}}\mathbb{E}_{a\sim\pi}\left[\nabla^2_a A^{\pi}(s,a)\right]J_{\mu}(s) \tag*{(89)}

Experiment Setup

All experiments were conducted on Quadro RTX 6000 GPU. We build on the official implementation of SA-PPO, ATLA-PPO and Wocar-PPO. For all methods, the actor and critic are parameterized by multilayer perceptrons with hidden layers [64, 64], and each policy is trained for 2×1062\times10^6 environment steps. We made two changes compared to the official implementation. First, we train an auxiliary advantage network Aπ(s,a)A^{\pi}(s,a) of hidden layers [64, 64] alongside the policy. Second, while the official implementation enables reward normalization, we disable it because naively reversing reward normalization on the learned advantage network does not provide reliable advantage estimates. We train each algorithm using four random seeds.

We train each PA-AD attacker for 1×1061\times10^6 environment steps. Its actor and critic use the same MLP architecture, with hidden layers [64, 64], and are both optimized with a learning rate of 3×10−43\times10^{-4}.

Additional Experimental Results

Table 7, Table 8 and Table 9 present the discounted total return and the degradation compared to the clean policy under Random, Critic, MAD and PA-AD attackers on Hopper, HalfCheetah and Walker2d environments, respectively. We use these results to generate Table 4 in the main paper by taking the largest degradation across all state attackers.

SetParameterAttackerPPOSA-PPO-SGLDATLA-PPOWocaR-PPO
No Attack––269.2 ± 10.0256.4 ± 6.5257.5 ± 6.2267.9 ± 4.5
L∞L_{\infty}-Normϵ=0.05\epsilon= 0.05Random268.2 ± 9.1 (1.0)256.1 ± 6.3 (0.3)257.2 ± 5.8 (0.3)268.0 ± 4.3 (-0.1)
L∞L_{\infty}-Normϵ=0.05\epsilon= 0.05Critic269.0 ± 11.0 (0.2)255.9 ± 6.2 (0.5)258.3 ± 5.7 (-0.8)268.4 ± 5.7 (-0.5)
L∞L_{\infty}-Normϵ=0.05\epsilon= 0.05MAD265.9 ± 9.1 (3.3)256.1 ± 5.5 (0.3)254.8 ± 6.5 (2.7)267.4 ± 4.3 (0.5)
L∞L_{\infty}-Normϵ=0.05\epsilon= 0.05PA-AD217.2 ± 29.3 (52.0)255.8 ± 4.8 (0.6)240.2 ± 17.7 (17.3)266.7 ± 2.1 (1.2)
L∞L_{\infty}-Normϵ=0.10\epsilon= 0.10Random267.5 ± 8.8 (1.7)256.0 ± 6.3 (0.4)256.3 ± 6.5 (1.2)267.8 ± 4.3 (0.1)
L∞L_{\infty}-Normϵ=0.10\epsilon= 0.10Critic266.0 ± 11.2 (3.2)255.9 ± 5.7 (0.5)252.7 ± 8.3 (4.8)270.7 ± 3.5 (-2.8)
L∞L_{\infty}-Normϵ=0.10\epsilon= 0.10MAD241.4 ± 14.9 (27.8)255.8 ± 5.5 (0.6)243.5 ± 9.7 (14.0)265.4 ± 4.2 (2.5)
L∞L_{\infty}-Normϵ=0.10\epsilon= 0.10PA-AD106.9 ± 64.9 (162.3)260.4 ± 7.4 (-4.0)178.8 ± 60.7 (78.7)257.3 ± 8.1 (10.6)
L∞L_{\infty}-Normϵ=0.15\epsilon= 0.15Random264.0 ± 8.3 (5.2)256.1 ± 5.8 (0.3)256.4 ± 6.3 (1.1)267.6 ± 4.0 (0.3)
L∞L_{\infty}-Normϵ=0.15\epsilon= 0.15Critic260.9 ± 11.6 (8.3)255.8 ± 5.8 (0.6)237.5 ± 28.0 (20.0)270.7 ± 3.4 (-2.8)
L∞L_{\infty}-Normϵ=0.15\epsilon= 0.15MAD186.0 ± 46.0 (83.2)257.0 ± 4.9 (-0.6)230.8 ± 15.9 (26.7)262.6 ± 3.4 (5.3)
L∞L_{\infty}-Normϵ=0.15\epsilon= 0.15PA-AD100.3 ± 66.5 (168.9)256.2 ± 13.1 (0.2)154.5 ± 69.2 (103.0)242.2 ± 16.2 (25.7)
L∞L_{\infty}-Normϵ=0.20\epsilon= 0.20Random263.7 ± 7.8 (5.5)255.7 ± 6.4 (0.7)252.6 ± 7.4 (4.9)266.6 ± 4.5 (1.3)
L∞L_{\infty}-Normϵ=0.20\epsilon= 0.20Critic242.5 ± 25.8 (26.7)255.0 ± 6.6 (1.4)233.5 ± 26.3 (24.0)270.0 ± 3.5 (-2.1)
L∞L_{\infty}-Normϵ=0.20\epsilon= 0.20MAD162.8 ± 54.2 (106.4)255.2 ± 3.0 (1.2)223.1 ± 15.1 (34.4)258.0 ± 6.4 (9.9)
L∞L_{\infty}-Normϵ=0.20\epsilon= 0.20PA-AD70.7 ± 34.0 (198.5)228.0 ± 29.4 (28.4)120.7 ± 64.8 (136.8)116.2 ± 43.2 (151.7)
PD-NUUSβ=5\beta= 5Random268.9 ± 10.3 (0.3)255.5 ± 5.6 (0.9)257.3 ± 5.8 (0.2)268.0 ± 4.2 (-0.1)
PD-NUUSβ=5\beta= 5Critic268.6 ± 11.2 (0.6)253.6 ± 6.3 (2.8)257.3 ± 5.4 (0.2)265.2 ± 7.5 (2.7)
PD-NUUSβ=5\beta= 5MAD267.5 ± 10.3 (1.7)252.5 ± 8.8 (3.9)256.5 ± 5.6 (1.0)267.4 ± 4.6 (0.5)
PD-NUUSβ=5\beta= 5PA-AD268.5 ± 10.8 (0.7)257.4 ± 6.6 (-1.0)256.6 ± 6.3 (0.9)266.5 ± 5.9 (1.4)
PD-NUUSβ=10\beta= 10Random268.9 ± 10.3 (0.3)256.1 ± 5.5 (0.3)257.3 ± 6.0 (0.2)267.3 ± 4.8 (0.6)
PD-NUUSβ=10\beta= 10Critic268.3 ± 11.6 (0.9)252.3 ± 7.4 (4.1)256.7 ± 6.1 (0.8)265.5 ± 6.0 (2.4)
PD-NUUSβ=10\beta= 10MAD267.2 ± 9.5 (2.0)250.6 ± 12.0 (5.8)255.0 ± 6.0 (2.5)267.1 ± 4.6 (0.8)
PD-NUUSβ=10\beta= 10PA-AD259.2 ± 17.5 (10.0)251.5 ± 5.6 (4.9)257.1 ± 5.6 (0.4)266.0 ± 6.5 (1.9)
PD-NUUSβ=20\beta= 20Random268.5 ± 9.5 (0.7)255.6 ± 6.4 (0.8)256.1 ± 6.7 (1.4)267.3 ± 4.6 (0.6)
PD-NUUSβ=20\beta= 20Critic269.0 ± 11.6 (0.2)250.6 ± 8.3 (5.8)257.2 ± 6.0 (0.3)262.7 ± 10.9 (5.2)
PD-NUUSβ=20\beta= 20MAD266.5 ± 9.4 (2.7)241.8 ± 20.3 (14.6)249.7 ± 9.4 (7.8)259.1 ± 16.1 (8.8)
PD-NUUSβ=20\beta= 20PA-AD268.4 ± 11.9 (0.8)249.2 ± 11.5 (7.2)233.0 ± 23.6 (24.5)258.6 ± 13.7 (9.3)
PD-NUUSβ=40\beta= 40Random268.4 ± 9.5 (0.8)254.5 ± 6.1 (1.9)257.2 ± 5.3 (0.3)266.6 ± 4.7 (1.3)
PD-NUUSβ=40\beta= 40Critic267.6 ± 12.2 (1.6)248.2 ± 5.8 (8.2)252.4 ± 7.5 (5.1)261.4 ± 11.9 (6.5)
PD-NUUSβ=40\beta= 40MAD261.3 ± 12.9 (7.9)225.6 ± 27.0 (30.8)238.8 ± 17.3 (18.7)253.5 ± 22.8 (14.4)
PD-NUUSβ=40\beta= 40PA-AD248.2 ± 16.6 (21.0)226.7 ± 12.4 (29.7)129.8 ± 95.9 (127.7)246.2 ± 8.6 (21.7)

Table 7. Discounted returns (γ=0.99\gamma= 0.99) under state attackers on Hopper environment. When using PD-NUUS, the values of α\alpha for PPO, SA-PPO-SGLD, ATLA-PPO and WocaR-PPO are 0.15, 0.25, 0.0075 and 0.2, respectively. The values in parentheses represent degradation compared to no attack.

SetParameterAttackerPPOSA-PPO-SGLDATLA-PPOWocaR-PPO
No Attack––421.5 ± 57.5349.4 ± 40.3345.7 ± 24.9331.4 ± 10.4
L∞L_\infty-Normϵ=0.05\epsilon= 0.05Random415.0 ± 46.7 (6.5)350.5 ± 40.7 (-1.1)342.9 ± 21.0 (2.8)331.3 ± 10.1 (0.1)
L∞L_\infty-Normϵ=0.05\epsilon= 0.05Critic404.7 ± 72.6 (16.8)350.4 ± 39.3 (-1.0)344.3 ± 18.8 (1.4)331.6 ± 10.7 (-0.2)
L∞L_\infty-Normϵ=0.05\epsilon= 0.05MAD336.7 ± 47.7 (84.8)349.9 ± 37.5 (-0.5)339.1 ± 21.4 (6.6)328.4 ± 9.3 (3.0)
L∞L_\infty-Normϵ=0.05\epsilon= 0.05PA-AD338.3 ± 67.0 (83.2)348.8 ± 38.6 (0.6)313.1 ± 38.0 (32.6)324.8 ± 7.1 (6.6)
L∞L_\infty-Normϵ=0.10\epsilon= 0.10Random382.9 ± 44.2 (38.6)350.6 ± 37.9 (-1.2)345.2 ± 19.7 (0.5)328.2 ± 9.0 (3.2)
L∞L_\infty-Normϵ=0.10\epsilon= 0.10Critic367.3 ± 98.8 (54.2)350.5 ± 41.5 (-1.1)334.1 ± 17.5 (11.6)329.5 ± 8.1 (1.9)
L∞L_\infty-Normϵ=0.10\epsilon= 0.10MAD224.6 ± 58.6 (196.9)348.2 ± 40.0 (1.2)293.0 ± 42.8 (52.7)322.6 ± 7.0 (8.8)
L∞L_\infty-Normϵ=0.10\epsilon= 0.10PA-AD168.0 ± 59.8 (253.5)348.0 ± 42.6 (1.4)243.7 ± 44.2 (102.0)328.4 ± 8.0 (3.0)
L∞L_\infty-Normϵ=0.15\epsilon= 0.15Random368.3 ± 36.5 (53.2)351.2 ± 38.2 (-1.8)339.6 ± 24.5 (6.1)326.7 ± 9.8 (4.7)
L∞L_\infty-Normϵ=0.15\epsilon= 0.15Critic332.2 ± 92.5 (89.3)351.1 ± 39.7 (-1.7)321.5 ± 15.7 (24.2)329.5 ± 10.1 (1.9)
L∞L_\infty-Normϵ=0.15\epsilon= 0.15MAD162.1 ± 55.2 (259.4)344.6 ± 37.6 (4.8)232.8 ± 39.9 (112.9)315.3 ± 8.4 (16.1)
L∞L_\infty-Normϵ=0.15\epsilon= 0.15PA-AD100.3 ± 47.7 (321.2)339.7 ± 27.3 (9.7)173.8 ± 53.7 (171.9)300.9 ± 17.2 (30.5)
L∞L_\infty-Normϵ=0.20\epsilon= 0.20Random321.8 ± 38.5 (99.7)348.5 ± 40.1 (0.9)328.3 ± 26.3 (17.4)324.3 ± 8.5 (7.1)
L∞L_\infty-Normϵ=0.20\epsilon= 0.20Critic280.5 ± 100.5 (141.0)347.2 ± 42.7 (2.2)295.5 ± 16.0 (50.2)324.7 ± 12.2 (6.7)
L∞L_\infty-Normϵ=0.20\epsilon= 0.20MAD117.1 ± 42.6 (304.4)342.5 ± 38.2 (6.9)164.5 ± 36.9 (181.2)303.2 ± 6.8 (28.2)
L∞L_\infty-Normϵ=0.20\epsilon= 0.20PA-AD22.3 ± 33.6 (399.2)337.8 ± 42.7 (11.6)86.6 ± 55.7 (259.1)287.0 ± 12.2 (44.4)
PD-NUUSβ=5\beta= 5Random421.2 ± 60.9 (0.3)350.0 ± 39.9 (-0.6)349.8 ± 22.7 (-4.1)330.1 ± 11.9 (1.3)
PD-NUUSβ=5\beta= 5Critic418.1 ± 56.6 (3.4)350.4 ± 41.3 (-1.0)350.2 ± 20.1 (-4.5)332.1 ± 9.4 (-0.7)
PD-NUUSβ=5\beta= 5MAD409.2 ± 65.3 (12.3)349.6 ± 41.4 (-0.2)349.4 ± 20.0 (-3.7)329.6 ± 9.2 (1.8)
PD-NUUSβ=5\beta= 5PA-AD418.2 ± 60.8 (3.3)346.2 ± 41.2 (3.2)347.9 ± 21.7 (-2.2)329.9 ± 8.9 (1.5)
PD-NUUSβ=10\beta= 10Random417.6 ± 58.1 (3.9)348.3 ± 41.2 (1.1)350.1 ± 19.2 (-4.4)330.4 ± 9.6 (1.0)
PD-NUUSβ=10\beta= 10Critic417.9 ± 59.9 (3.6)351.5 ± 40.4 (-2.1)351.4 ± 18.3 (-5.7)333.4 ± 10.3 (-2.0)
PD-NUUSβ=10\beta= 10MAD422.4 ± 60.0 (-0.9)348.1 ± 38.8 (1.3)346.3 ± 23.8 (-0.6)329.2 ± 11.4 (2.2)
PD-NUUSβ=10\beta= 10PA-AD424.4 ± 58.1 (-2.9)348.6 ± 38.8 (0.8)344.2 ± 21.2 (1.5)325.6 ± 8.6 (5.8)
PD-NUUSβ=20\beta= 20Random409.3 ± 59.1 (12.2)347.7 ± 39.3 (1.7)350.3 ± 21.2 (-4.6)329.8 ± 10.2 (1.6)
PD-NUUSβ=20\beta= 20Critic414.8 ± 65.6 (6.7)350.5 ± 40.4 (-1.1)346.1 ± 20.4 (-0.4)331.4 ± 11.2 (0.0)
PD-NUUSβ=20\beta= 20MAD413.9 ± 68.6 (7.6)346.5 ± 36.8 (2.9)344.1 ± 24.5 (1.6)326.8 ± 12.2 (4.6)
PD-NUUSβ=20\beta= 20PA-AD404.3 ± 54.5 (17.2)345.2 ± 38.7 (4.2)332.3 ± 19.0 (13.4)311.5 ± 13.6 (19.9)
PD-NUUSβ=40\beta= 40Random416.7 ± 59.0 (4.8)347.1 ± 38.1 (2.3)349.6 ± 20.7 (-3.9)321.3 ± 12.8 (10.1)
PD-NUUSβ=40\beta= 40Critic413.6 ± 60.6 (7.9)340.4 ± 36.2 (9.0)335.2 ± 23.4 (10.5)324.0 ± 9.1 (7.4)
PD-NUUSβ=40\beta= 40MAD405.4 ± 61.6 (16.1)330.2 ± 29.4 (19.2)335.8 ± 24.6 (9.9)310.2 ± 11.9 (21.2)
PD-NUUSβ=40\beta= 40PA-AD387.3 ± 68.3 (34.2)327.0 ± 44.3 (22.4)319.6 ± 19.1 (26.1)287.0 ± 24.8 (44.4)

Table 8. Discounted returns (γ=0.99\gamma= 0.99) under state attackers on HalfCheetah environment. When using PD-NUUS, the value of α\alpha for PPO, SA-PPO-SGLD, ATLA-PPO and WocaR-PPO are 0.06, 0.2, 0.02 and 0.075, respectively. The values in parentheses represent degradation compared to no attack.

SetParameterAttackerPPOSA-PPO-SGLDATLA-PPOWocaR-PPO
No Attack––278.5 ±\pm 8.5298.3 ±\pm 12.6276.7 ±\pm 14.0287.9 ±\pm 17.6
L∞L_{\infty}-Normϵ=0.05\epsilon= 0.05Random278.2 ±\pm 9.6 (0.3)299.0 ±\pm 12.7 (-0.7)278.6 ±\pm 11.5 (-1.9)287.6 ±\pm 17.8 (0.3)
L∞L_{\infty}-Normϵ=0.05\epsilon= 0.05Critic275.9 ±\pm 9.4 (2.6)302.6 ±\pm 10.8 (-4.3)275.6 ±\pm 16.3 (1.1)289.5 ±\pm 19.0 (-1.6)
L∞L_{\infty}-Normϵ=0.05\epsilon= 0.05MAD265.1 ±\pm 14.5 (13.4)299.6 ±\pm 10.4 (-1.3)260.3 ±\pm 10.4 (16.4)286.9 ±\pm 17.6 (1.0)
L∞L_{\infty}-Normϵ=0.05\epsilon= 0.05PA-AD228.2 ±\pm 44.6 (50.3)297.3 ±\pm 14.4 (1.0)227.7 ±\pm 35.1 (49.0)285.0 ±\pm 19.0 (2.9)
L∞L_{\infty}-Normϵ=0.10\epsilon= 0.10Random277.7 ±\pm 9.7 (0.8)298.2 ±\pm 12.8 (0.1)274.8 ±\pm 12.2 (1.9)287.6 ±\pm 17.8 (0.3)
L∞L_{\infty}-Normϵ=0.10\epsilon= 0.10Critic260.5 ±\pm 21.8 (18.0)296.6 ±\pm 9.7 (1.7)255.0 ±\pm 23.7 (21.7)292.3 ±\pm 18.8 (-4.4)
L∞L_{\infty}-Normϵ=0.10\epsilon= 0.10MAD229.9 ±\pm 29.4 (48.6)295.3 ±\pm 11.1 (3.0)222.1 ±\pm 14.4 (54.6)282.8 ±\pm 17.3 (5.1)
L∞L_{\infty}-Normϵ=0.10\epsilon= 0.10PA-AD139.5 ±\pm 16.5 (139.0)275.3 ±\pm 42.0 (23.0)151.0 ±\pm 17.6 (125.7)245.6 ±\pm 38.1 (42.3)
L∞L_{\infty}-Normϵ=0.15\epsilon= 0.15Random268.5 ±\pm 13.3 (10.0)298.1 ±\pm 11.7 (0.2)268.9 ±\pm 11.7 (7.8)286.7 ±\pm 18.4 (1.2)
L∞L_{\infty}-Normϵ=0.15\epsilon= 0.15Critic246.6 ±\pm 25.1 (31.9)287.1 ±\pm 28.2 (11.2)232.9 ±\pm 29.7 (43.8)294.5 ±\pm 17.8 (-6.6)
L∞L_{\infty}-Normϵ=0.15\epsilon= 0.15MAD197.4 ±\pm 23.0 (81.1)290.8 ±\pm 8.6 (7.5)186.4 ±\pm 19.4 (90.3)275.3 ±\pm 17.2 (12.6)
L∞L_{\infty}-Normϵ=0.15\epsilon= 0.15PA-AD116.2 ±\pm 31.7 (162.3)248.0 ±\pm 17.9 (50.3)111.6 ±\pm 23.0 (165.1)152.7 ±\pm 60.8 (135.2)
L∞L_{\infty}-Normϵ=0.20\epsilon= 0.20Random267.1 ±\pm 13.0 (11.4)297.9 ±\pm 10.4 (0.4)264.0 ±\pm 11.4 (12.7)286.9 ±\pm 17.9 (1.0)
L∞L_{\infty}-Normϵ=0.20\epsilon= 0.20Critic227.1 ±\pm 40.0 (51.4)271.8 ±\pm 40.7 (26.5)221.1 ±\pm 27.2 (55.6)297.7 ±\pm 13.8 (-9.8)
L∞L_{\infty}-Normϵ=0.20\epsilon= 0.20MAD178.5 ±\pm 17.6 (100.0)278.5 ±\pm 10.1 (19.8)162.7 ±\pm 21.9 (114.0)272.0 ±\pm 19.9 (15.9)
L∞L_{\infty}-Normϵ=0.20\epsilon= 0.20PA-AD73.2 ±\pm 33.5 (205.3)169.4 ±\pm 23.7 (128.9)85.2 ±\pm 41.7 (191.5)148.9 ±\pm 57.7 (139.0)
PD-NUUSβ=5\beta= 5Random279.2 ±\pm 7.6 (-0.7)298.0 ±\pm 14.5 (0.3)276.8 ±\pm 14.2 (-0.1)287.6 ±\pm 17.9 (0.3)
PD-NUUSβ=5\beta= 5Critic276.5 ±\pm 8.0 (2.0)305.3 ±\pm 9.8 (-7.0)276.6 ±\pm 15.5 (0.1)289.3 ±\pm 18.4 (-1.4)
PD-NUUSβ=5\beta= 5MAD279.3 ±\pm 8.5 (-0.8)296.4 ±\pm 14.4 (1.9)276.8 ±\pm 11.9 (-0.1)287.9 ±\pm 17.3 (0.0)
PD-NUUSβ=5\beta= 5PA-AD275.7 ±\pm 6.4 (2.8)282.3 ±\pm 17.3 (16.0)277.8 ±\pm 10.0 (-1.1)282.3 ±\pm 19.8 (5.6)
PD-NUUSβ=10\beta= 10Random278.0 ±\pm 8.9 (0.5)297.6 ±\pm 14.8 (0.7)277.6 ±\pm 13.7 (-0.9)288.0 ±\pm 17.3 (-0.1)
PD-NUUSβ=10\beta= 10Critic274.8 ±\pm 10.6 (3.7)304.1 ±\pm 7.1 (-5.8)276.1 ±\pm 14.7 (0.6)289.7 ±\pm 18.3 (-1.8)
PD-NUUSβ=10\beta= 10MAD276.2 ±\pm 7.7 (2.3)297.0 ±\pm 12.8 (1.3)276.0 ±\pm 12.8 (0.7)287.7 ±\pm 17.3 (0.2)
PD-NUUSβ=10\beta= 10PA-AD270.8 ±\pm 11.9 (7.7)283.4 ±\pm 16.2 (14.9)273.5 ±\pm 15.5 (3.2)286.2 ±\pm 20.7 (1.7)
PD-NUUSβ=20\beta= 20Random277.9 ±\pm 10.1 (0.6)297.6 ±\pm 12.5 (0.7)278.2 ±\pm 11.7 (-1.5)288.0 ±\pm 17.8 (-0.1)
PD-NUUSβ=20\beta= 20Critic268.9 ±\pm 13.7 (9.6)296.1 ±\pm 12.4 (2.2)276.2 ±\pm 14.0 (0.5)289.9 ±\pm 18.9 (-2.0)
PD-NUUSβ=20\beta= 20MAD269.8 ±\pm 10.2 (8.7)296.6 ±\pm 6.1 (1.7)277.7 ±\pm 13.2 (-1.0)286.6 ±\pm 18.3 (1.3)
PD-NUUSβ=20\beta= 20PA-AD218.0 ±\pm 40.7 (60.5)282.9 ±\pm 15.6 (15.4)268.8 ±\pm 11.3 (7.9)271.1 ±\pm 26.6 (16.7)
PD-NUUSβ=40\beta= 40Random277.2 ±\pm 10.0 (1.3)296.3 ±\pm 8.4 (2.0)275.2 ±\pm 11.8 (1.5)287.4 ±\pm 17.8 (0.5)
PD-NUUSβ=40\beta= 40Critic263.7 ±\pm 18.3 (14.8)288.0 ±\pm 8.8 (10.3)274.0 ±\pm 16.1 (2.7)292.2 ±\pm 17.3 (-4.3)
PD-NUUSβ=40\beta= 40MAD255.6 ±\pm 8.3 (22.9)280.5 ±\pm 10.1 (17.8)272.1 ±\pm 11.8 (4.6)282.6 ±\pm 17.8 (5.3)
PD-NUUSβ=40\beta= 40PA-AD172.9 ±\pm 44.8 (105.6)170.0 ±\pm 81.1 (128.3)264.4 ±\pm 22.6 (12.3)237.9 ±\pm 50.4 (50.0)

Table 9. Discounted returns (γ=0.99\gamma= 0.99) under state attackers on Walker2d environment. When using PD-NUUS, the value of α\alpha for PPO, SA-PPO-SGLD, ATLA-PPO and WocaR-PPO are 0.025, 0.075, 0.05 and 0.15, respectively. The values in parentheses represent degradation compared to no attack.

In Table 10 we present the degradation in discounted return caused by different α\alpha values, and the percentage of perturbation budget r(s)r(s) reaching the upper bound rmax⁡r_{\max}.

EnvironmentPolicyα\alphaBudget r(s)r(s) at rmax⁡r_{\max} (%)Degradation in Discounted Return
HopperPPO036.219241.4
HopperPPO0.0154.855234.7
HopperPPO0.15∗0.15^{*}0.13721.0
HopperSA-PPO-SGLD018.34372.3
HopperSA-PPO-SGLD0.25∗0.25^{*}7.51529.6
HopperSA-PPO-SGLD0.38.75822.4
HopperATLA-PPO015.982176.7
HopperATLA-PPO0.0075∗0.0075^{*}0.325127.7
HopperATLA-PPO0.020.03317.7
HopperWocaR-PPO018.400183.2
HopperWocaR-PPO0.154.021189.0
HopperWocaR-PPO0.2∗0.2^{*}1.14521.7

Table 10. Percentage of perturbation budgets r(s)r(s) that reach the upper bound rmax⁡r_{\max} under PA-AD attacks with PD-NUUS at β=40\beta= 40. We compare the selected value (with *) of α\alpha with other α\alpha values. An inappropriate choice of α\alpha yields degradation in discounted total return substantially greater than β\beta and cause a larger fraction of the learned budgets to saturate at rmax⁡r_{\max}.

Table 11 reports the empirical values of global multiplier κ\kappa for PD-NUUS.

Environmentβ\betaPPOSA-PPO-SGLDATLA-PPOWocaR-PPO
Hopper50.458±0.0770.458 \pm0.0770.026±0.0010.026 \pm0.0010.136±0.0240.136 \pm0.0240.063±0.0030.063 \pm0.003
Hopper100.643±0.1090.643 \pm0.1090.034±0.0020.034 \pm0.0020.182±0.0360.182 \pm0.0360.086±0.0040.086 \pm0.004
Hopper200.906±0.1540.906 \pm0.1540.045±0.0020.045 \pm0.0020.249±0.0520.249 \pm0.0520.118±0.0050.118 \pm0.005
Hopper401.279±0.2181.279 \pm0.2180.062±0.0030.062 \pm0.0030.347±0.0750.347 \pm0.0750.166±0.0070.166 \pm0.007
HalfCheetah50.155±0.0290.155 \pm0.0290.021±0.0060.021 \pm0.0060.130±0.0290.130 \pm0.0290.015±0.0030.015 \pm0.003
HalfCheetah100.216±0.0410.216 \pm0.0410.028±0.0070.028 \pm0.0070.180±0.0410.180 \pm0.0410.019±0.0040.019 \pm0.004
HalfCheetah200.304±0.0580.304 \pm0.0580.038±0.0100.038 \pm0.0100.251±0.0580.251 \pm0.0580.026±0.0050.026 \pm0.005
HalfCheetah400.429±0.0820.429 \pm0.0820.053±0.0140.053 \pm0.0140.353±0.0820.353 \pm0.0820.035±0.0070.035 \pm0.007
Walker2d50.210±0.0260.210 \pm0.0260.051±0.0020.051 \pm0.0020.338±0.0450.338 \pm0.0450.072±0.0060.072 \pm0.006
Walker2d100.282±0.0370.282 \pm0.0370.064±0.0030.064 \pm0.0030.467±0.0640.467 \pm0.0640.095±0.0080.095 \pm0.008
Walker2d200.388±0.0520.388 \pm0.0520.085±0.0040.085 \pm0.0040.653±0.0920.653 \pm0.0920.129±0.0110.129 \pm0.011
Walker2d400.541±0.0740.541 \pm0.0740.116±0.0060.116 \pm0.0060.917±0.1300.917 \pm0.1300.178±0.0140.178 \pm0.014

Table 11. The mean and standard deviation of κ\kappa values estimated from sampled trajectories, when synthesizing PD-NUUS.

Table 12 reports the episode rewards of clean policies and policies perturbed by PD-NUUS (β∈{20,40}\beta\in\{20, 40\}) and PA-AD attacker.

EnvironmentAttackerβ\betaPPOSA-PPO-SGLDATLA-PPOWocaR-PPO
Hopper––3471.7±391.73471.7 \pm391.73203.0±378.53203.0 \pm378.53227.5±634.93227.5 \pm634.93358.3±452.83358.3 \pm452.8
HopperPD-NUUS203112.9±757.83112.9 \pm757.81802.7±1311.81802.7 \pm1311.81573.8±1111.01573.8 \pm1111.02501.1±1173.02501.1 \pm1173.0
HopperPD-NUUS402489.8±1287.32489.8 \pm1287.31198.2±1085.31198.2 \pm1085.3924.3±1323.3924.3 \pm1323.31663.1±1081.51663.1 \pm1081.5
HalfCheetah––5275.1±1586.05275.1 \pm1586.04320.3±611.34320.3 \pm611.34267.1±854.54267.1 \pm854.53952.2±566.33952.2 \pm566.3
HalfCheetahPD-NUUS204793.0±1810.34793.0 \pm1810.34241.0±561.74241.0 \pm561.73930.9±954.03930.9 \pm954.02339.6±1389.22339.6 \pm1389.2
HalfCheetahPD-NUUS404356.1±1986.74356.1 \pm1986.73952.1±751.83952.1 \pm751.83730.3±971.53730.3 \pm971.52165.6±1193.52165.6 \pm1193.5
Walker2d––3887.0±1290.83887.0 \pm1290.83858.3±1244.03858.3 \pm1244.03647.7±1241.33647.7 \pm1241.34271.3±681.94271.3 \pm681.9
Walker2dPD-NUUS201713.6±1704.01713.6 \pm1704.03426.0±1421.23426.0 \pm1421.22872.9±1388.82872.9 \pm1388.83213.1±1562.43213.1 \pm1562.4
Walker2dPD-NUUS40921.1±1333.2921.1 \pm1333.21347.8±1251.31347.8 \pm1251.32992.0±1453.82992.0 \pm1453.82526.1±1526.72526.1 \pm1526.7

Table 12. Episode rewards E[∑t=0TR(st,at)]\mathbb{E}[\sum_{t=0}^{T} R(s_t, a_t)] without attack and under PA-AD attack with PD-NUUS (β∈{20,40}\beta\in\{20, 40\}).

In Figure 2 we show the visualized budgets of PD-NUUS for PPO, SA-PPO-SGLD, ATLA-PPO and WocaR-PPO policies when β∈{5,10,20,40}\beta\in\{5, 10, 20, 40\}.

Image not extracted

Figure 2. The mean and confidence range of calculated budget ri(s)r_i(s) of policies under PA-AD attack sampled from PD-NUUS with β∈{5,10,20,40}\beta\in\{5, 10, 20, 40\} on Hopper. SA-PPO-SGLD, ATLA-PPO and WocaR-PPO admit higher perturbation tolerance than PPO in nearly all state dimensions.

References

  1. [1]Achiam, J.; Held, D.; Tamar, A.; and Abbeel, P. 2017. Constrained policy optimization. In International conference on machine learning, 22–31. PMLR.arxiv.org/abs/1705.10528
  2. [2]Beechey, D.; Smith, T. M.; and Şimşek, Ö. 2023. Explaining reinforcement learning with shapley values. In International Conference on Machine Learning, 2003–2014. PMLR.
  3. [3]Behzadian, B.; Russel, R. H.; Petrik, M.; and Ho, C. P. 2021. Optimizing percentile criterion using robust MDPs. In International Conference on Artificial Intelligence and Statistics, 1009–1017. PMLR.
  4. [4]Erdemir, E.; Bickford, J.; Melis, L.; and Aydore, S. 2021. Adversarial robustness with non-uniform perturbations. Advances in Neural Information Processing Systems, 34: 19147–19159.
  5. [5]Everett, M.; Lütjens, B.; and How, J. P. 2021. Certifiable robustness to adversarial state uncertainty in deep reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, 33(9): 4184–4198.
  6. [6]Iyengar, G. N. 2005. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257–280.
  7. [7]Kakade, S.; and Langford, J. 2002. Approximately optimal approximate reinforcement learning. In Proceedings of the nineteenth international conference on machine learning, 267–274.
  8. [8]Korkmaz, E.; and Brown-Cohen, J. 2023. Detecting adversarial directions in deep reinforcement learning to make robust decisions. In International Conference on Machine Learning, 17534–17543. PMLR.
  9. [9]Kuang, Y.; Lu, M.; Wang, J.; Zhou, Q.; Li, B.; and Li, H. 2022. Learning robust policy against disturbance in transition dynamics via state-conservative policy optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, 7247–7254.
  10. [10]Kumar, A.; Levine, A.; and Feizi, S. 2022. Policy Smoothing for Provably Robust Reinforcement Learning. In International Conference on Learning Representations (ICLR).
  11. [11]Liang, Y.; Sun, Y.; Zheng, R.; and Huang, F. 2022. Efficient adversarial training without attacking: Worst-case-aware robust reinforcement learning. Advances in neural information processing systems, 35: 22547–22561.
  12. [12]Mandlekar, A.; Zhu, Y.; Garg, A.; Fei-Fei, L.; and Savarese, S. 2017. Adversarially robust policy learning: Active construction of physically-plausible perturbations. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 3932–3939. IEEE.
  13. [13]Mao, Y.; Qu, Y.; Wang, Q.; and Ji, X. 2026. Adaptive neighborhood-constrained q learning for offline reinforcement learning. Advances in Neural Information Processing Systems, 38: 26008–26041.arxiv.org/abs/2511.02567
  14. [14]McGaffin, M. G.; and Fessler, J. A. 2015. Algorithmic design of majorizers for large-scale inverse problems. arXiv preprint arXiv:1508.02958.arxiv.org/abs/1508.02958
  15. [16]Oikarinen, T.; Zhang, W.; Megretski, A.; Daniel, L.; and Weng, T.-W. 2021. Robust deep reinforcement learning through adversarial loss. Advances in Neural Information Processing Systems, 34: 26156–26167.
  16. [17]Pattanaik, A.; Tang, Z.; Liu, S.; Bommanna, G.; and Chowdhary, G. 2017. Robust deep reinforcement learning with adversarial attacks. arXiv preprint arXiv:1712.03632.arxiv.org/abs/1712.03632
  17. [18]Petrik, M.; and Russel, R. H. 2019. Beyond confidence regions: Tight bayesian ambiguity sets for robust mdps. Advances in neural information processing systems, 32.
  18. [19]Schulman, J.; Levine, S.; Abbeel, P.; Jordan, M.; and Moritz, P. 2015. Trust region policy optimization. In International conference on machine learning, 1889–1897. PMLR.
  19. [20]Schulman, J.; Wolski, F.; Dhariwal, P.; Radford, A.; and Klimov, O. 2017. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347.arxiv.org/abs/1707.06347
  20. [21]Shen, Q.; Li, Y.; Jiang, H.; Wang, Z.; and Zhao, T. 2020. Deep reinforcement learning with robust and smooth policy. In International Conference on Machine Learning, 8707–8718. PMLR.
  21. [22]Sun, X.; Liu, F.; Ding, Z.; and Zheng, Z. 2026. Diffusion Guided Adversarial State Perturbations in Reinforcement Learning. Advances in Neural Information Processing Systems, 38: 43780–43815.
  22. [23]Sun, Y.; Zheng, R.; Liang, Y.; and Huang, F. 2022. Who Is the Strongest Enemy? Towards Optimal and Efficient Evasion Attacks in Deep RL. In International Conference on Learning Representations.
  23. [24]Todorov, E.; Erez, T.; and Tassa, Y. 2012. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ international conference on intelligent robots and systems, 5026–5033. IEEE.
  24. [25]Wong, E.; and Kolter, J. Z. 2020. Learning perturbation sets for robust machine learning. arXiv preprint arXiv:2007.08450.arxiv.org/abs/2007.08450
  25. [28]Zhang, H.; Chen, H.; Boning, D. S.; and Hsieh, C.-J. 2021. Robust Reinforcement Learning on State Observations with Learned Optimal Adversary. In International Conference on Learning Representations.
  26. [29]Zhang, H.; Chen, H.; Xiao, C.; Li, B.; Liu, M.; Boning, D.; and Hsieh, C.-J. 2020. Robust deep reinforcement learning against adversarial perturbations on state observations. Advances in Neural Information Processing Systems, 33: 21024–21037.
  27. [30]Zhang, Y.; Wang, J.; and Boedecker, J. 2023. Robust reinforcement learning in continuous control tasks with uncertainty set regularization. In Conference on Robot Learning, 1400–1424. PMLR.

Paper details

vlnc:W_avqkpw37
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 6

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents