Introduction
Despite the impressive success of reinforcement learning (RL) across a wide range of domains [27 , 28 , 29 , 26 , 108 , 109 , 110 ] , deploying RL in real-world systems remains challenging. A central bottleneck is reward misspecification: the reward function used for training is often an imperfect proxy for the desired objective due to limited data, human biases, modeling errors, or distribution shift [1 , 84 , 93 ] . Therefore, in safety and reliability critical settings, we would like policies that continue to perform well under plausible reward perturbations. This motivates reward-robust RL, which models misspecification by assuming all plausible rewards lie within a given uncertainty set and solves a max-min objective that maximizes worst-case performance. Equivalently, it can also be viewed as a dynamic zero-sum game: an adversary selects the worst-case reward within the uncertainty set, while the agent seeks a policy that maximizes the resulting worst-case return [30 , 31 , 32 , 8 ] .
Existing reward-robust RL frameworks typically construct uncertainty sets by measuring the expected divergence of plausible rewards from a base reward [34 , 6 ] . However, a key weakness that has been largely overlooked in the robust RL literature is that controlling such divergences in reward space does not necessarily correspond to differences in decision-making. In particular, potential-based reward shaping (PBRS), which encompasses a general and widely adopted family of shaping transformations [7 , 33 , 86 ] , shows that certain shaping rewards leave the optimal policy invariant and, more generally, preserve policy ordering. As a consequence, a divergence-based uncertainty set can contain many behaviorally equivalent rewards: they differ under the chosen divergence measure but induce identical policy rankings. This redundancy can be harmful in robust optimization. In particular, it can waste adversary iterations on rewards that provide no new behavioral distinctions rather than finding genuinely more adverse rewards (as theoretically justified and empirically shown in § 3.1 and Figure 2 ), ultimately weakening the adversary and degrading robust training.
In this work, we make the first step towards behavior-discriminative robust RL by proposing Shaping-Aware Reward-Robust RL. Our framework addresses the above issues by constructing a shaping-aware projected uncertainty set in which each PBRS-equivalent reward class is represented by a canonical reward. Intuitively, this removes rewards that provably do not affect policy ranking and yields an uncertainty set that better reflects behaviorally distinct objectives. We show that this reduction does not change the optimal robust value of the original reward-robust RL problem, while substantially simplifying the adversary’s search space. Empirically, we find that optimization on the projected uncertainty set makes adversary updates more identifiable and improves both performance and convergence.
However, directly solving the max-min robust RL problem with projected rewards requires projecting every candidate reward considered by the adversary to its canonical representative, which is computationally expensive. To address this, we first show that optimizing a suitably regularized objective with a projected base reward provides a conservative lower bound for the shaping-aware robust objective. This gives a tractable surrogate that only requires projecting the base reward, thereby avoiding repeated projections during the inner max-min optimization. We further show that, for certain uncertainty sets, such as entropy- and KL-induced uncertainty sets, this lower bound becomes exact in our projected setting. We further choose the canonical representative by minimizing the discrepancy induced by the uncertainty set within each PBRS equivalence class. This projection selects a representative that is consistent across equivalence classes and conservative with respect to the robust objective. Putting these together, we derive a practical algorithm that alternates between learning the canonical form of the base reward and optimizing the corresponding regularized RL objective. Since our approach only introduces a lightweight projection-learning step prior to standard policy updates, it can be integrated with a wide range of existing RL optimizers. Moreover, under standard assumptions, we establish convergence guarantees for the overall algorithm.
We empirically evaluate our method on benchmarks spanning diverse task domains and levels of complexity, comparing against representative robust RL baselines. Across all environments, our method consistently achieves higher returns and reaches strong performance in fewer training steps. We further assess robustness under reward perturbations and observe that our method exhibits smaller performance degradation than standard baselines when rewards are shifted. Overall, these results support the view that removing PBRS-induced redundancy leads to more effective robust policy learning under reward uncertainty.
To summarize, the key contribution of this work is: 1) To the best of our knowledge, we are the first to incorporate PBRS equivalence into the reward-robust RL and to construct uncertainty sets based on behavioral distinctions, rather than raw reward discrepancies, yielding stronger robust learning performance. 2) We derive a practical shaping-aware reward-robust RL algorithm that trains policies against this behaviorally distinct uncertainty set, and we provide convergence guarantees under standard assumptions. 3) We empirically validate the method across diverse environments, showing higher returns, faster convergence, and improved robustness to reward perturbations compared to representative baselines.
Preliminary
Z \mathcal{Z} Z R Z \mathbb{R}^{\mathcal{Z}} R Z Z \mathcal{Z} Z Δ Z \Delta_{\mathcal{Z}} Δ Z Z \mathcal{Z} Z X \mathcal{X} X Δ Z X \Delta_{\mathcal{Z}}^{\mathcal{X}} Δ Z X X \mathcal{X} X Δ Z \Delta_{\mathcal{Z}} Δ Z a , b ∈ R Z a,b \in \mathbb{R}^{\mathcal{Z}} a , b ∈ R Z ⟨ a , b ⟩ : = ∑ z ∈ Z a ( z ) b ( z ) \langle a,b\rangle := \sum_{z\in\mathcal{Z}} a(z)\,b(z) ⟨ a , b ⟩ := ∑ z ∈ Z a ( z ) b ( z ) C ⊂ R Z C \subset \mathbb{R}^{\mathcal{Z}} C ⊂ R Z Ω : C → R \Omega : C \to \mathbb{R} Ω : C → R Ω \Omega Ω Ω ∗ ( y ) = max a ∈ C { ⟨ a , y ⟩ − Ω ( a ) } , ∀ y ∈ R Z \Omega^{*}(y)
= \max_{a\in C} \bigl\{\langle a,y\rangle - \Omega(a)\bigr\}, \forall\, y \in \mathbb{R}^{\mathcal{Z}} Ω ∗ ( y ) = max a ∈ C { ⟨ a , y ⟩ − Ω ( a ) } , ∀ y ∈ R Z C C C
Standard RL. Consider an infinite-horizon Markov decision process (MDP) ( S , A , μ 0 , γ , P , r ) (\mathcal{S},\mathcal{A},\mu_0,\gamma,P,r) ( S , A , μ 0 , γ , P , r ) S \mathcal{S} S A \mathcal{A} A 0 < μ 0 ∈ Δ S 0 < \mu_0 \in \Delta_{\mathcal{S}} 0 < μ 0 ∈ Δ S γ ∈ ( 0 , 1 ) \gamma \in (0,1) γ ∈ ( 0 , 1 ) X : = S × A \mathcal{X} := \mathcal{S}\times\mathcal{A} X := S × A X ′ : = S × A × S \mathcal{X'} := \mathcal{S}\times\mathcal{A}\times\mathcal{S} X ′ := S × A × S P ∈ Δ S X P \in \Delta_{\mathcal{S}}^{\mathcal{X}} P ∈ Δ S X ( s , a ) ∈ X (s,a)\in \mathcal{X} ( s , a ) ∈ X S \mathcal{S} S r ∈ R X ′ r \in \mathbb{R}^{\mathcal{X'}} r ∈ R X ′ ( s , a , s ′ ) ∈ X ′ (s,a,s')\in \mathcal{X'} ( s , a , s ′ ) ∈ X ′ s ′ s' s ′ P ( ⋅ ∣ s , a ) P(\cdot|s,a) P ( ⋅ ∣ s , a ) a a a s s s π ∈ Δ A S \pi \in \Delta_{\mathcal{A}}^{\mathcal{S}} π ∈ Δ A S s ∈ S s \in \mathcal{S} s ∈ S μ 0 , π \mu_0,\pi μ 0 , π P P P r r r J ( π , r ) : = E [ ∑ t = 0 ∞ γ t r ( s t , a t , s t + 1 ) ∣ μ 0 , π , P ] . J(\pi,r)
:= \mathbb{E}\!\left[\sum_{t=0}^{\infty} \gamma^{t} r(s_t,a_t,s_{t+1})
\,\Big|\, \mu_0,\pi,P \right]. J ( π , r ) := E [ ∑ t = 0 ∞ γ t r ( s t , a t , s t + 1 ) μ 0 , π , P ] . π \pi π
Potential-Based Reward Shaping (PBRS). PBRS [7 ] augments the environment reward via a potential function Φ ∈ R S \Phi\in \mathbb{R}^{\mathcal{S}} Φ ∈ R S Φ \Phi Φ F F F ( s , a , s ′ ) ∈ X ′ (s,a,s')\in\mathcal{X'} ( s , a , s ′ ) ∈ X ′ F ( s , a , s ′ ) = γ Φ ( s ′ ) − Φ ( s ) , F(s,a,s') = \gamma \Phi(s') - \Phi(s), F ( s , a , s ′ ) = γ Φ ( s ′ ) − Φ ( s ) , r ′ ∈ R X ′ r'\in \mathbb{R}^{\mathcal{X'}} r ′ ∈ R X ′ r ′ ( s , a , s ′ ) = r ( s , a , s ′ ) + F ( s , a , s ′ ) . r'(s,a,s') = r(s,a,s') + F(s,a,s'). r ′ ( s , a , s ′ ) = r ( s , a , s ′ ) + F ( s , a , s ′ ) . r r r r ′ r' r ′ [7 ] ).
Reward-Robust RL. A reward-robust MDP is given by ( S , A , μ 0 , γ , P , U ) (\mathcal{S},\mathcal{A},\mu_0,\gamma,P,\mathcal{U}) ( S , A , μ 0 , γ , P , U ) U ⊆ R X ′ \mathcal{U}\subseteq \mathbb{R}^{\mathcal{X'}} U ⊆ R X ′ U \mathcal{U} U r ∈ R X ′ r\in\mathbb{R}^{\mathcal{X'}} r ∈ R X ′ U = { r ~ ∈ R X ′ : Ω ∗ ( r − r ~ ) ≤ ϵ } , \mathcal{U}=\{\tilde r\in \mathbb{R}^{\mathcal{X'}} : \Omega^*(r-\tilde r)\le \epsilon\}, U = { r ~ ∈ R X ′ : Ω ∗ ( r − r ~ ) ≤ ϵ } , Ω ∗ \Omega^* Ω ∗ ϵ > 0 \epsilon>0 ϵ > 0 π \pi π
max π ∈ Δ A S min r ~ ∈ U J ( π , r ~ ) . \begin{equation}
\max_{\pi \in \Delta_{\mathcal{A}}^{\mathcal{S}}}\,\min_{\tilde r\in\mathcal{U}} J(\pi,\tilde r). \tag*{(1)}
\end{equation} π ∈ Δ A S max r ~ ∈ U min J ( π , r ~ ) . (1) The uncertainty sets studied in the literature typically arise from specific choices of Ω ∗ \Omega^* Ω ∗ u ( s , a , s ′ ) = r ( s , a , s ′ ) − r ~ ( s , a , s ′ ) u(s,a,s')=r(s,a,s')-\tilde r(s,a,s') u ( s , a , s ′ ) = r ( s , a , s ′ ) − r ~ ( s , a , s ′ ) l p l_p l p Ω ∗ ( u ) = ∥ u ∥ p \Omega^*(u)=\|u\|_{p} Ω ∗ ( u ) = ∥ u ∥ p [94 , 58 , 95 ] . In addition, [6 ] consider an Ω ∗ \Omega^* Ω ∗ Ω ∗ ( u ) = E [ ∑ t γ t log ∑ a exp ( u ( s t , a , s t + 1 ) ) ∣ μ 0 , π , P ] \Omega^*(u)= \mathbb{E}\left[
\sum_{t} \gamma^{t}
\log \sum_{a }
\exp(u(s_t,a,s_{t+1}))\Big| \mu_0, \pi, P \right] Ω ∗ ( u ) = E [ ∑ t γ t log ∑ a exp ( u ( s t , a , s t + 1 )) μ 0 , π , P ] [5 ] define a reference policy weighted variant: Ω ∗ ( u ) = E [ ∑ t γ t log ∑ a ∈ A π r e f ( a ∣ s t ) exp ( u ( s t , a , s t + 1 ) ) ∣ μ 0 , π , P ] \Omega^*(u) = \mathbb{E}\left[
\sum_{t} \gamma^{t}
\log \sum_{a\in\mathcal{A}}\pi_{\mathrm{ref}}(a|s_t)
\exp(u(s_t, a,s_{t+1}))\Big| \mu_0, \pi, P\right] Ω ∗ ( u ) = E [ ∑ t γ t log ∑ a ∈ A π ref ( a ∣ s t ) exp ( u ( s t , a , s t + 1 )) μ 0 , π , P ] π r e f \pi_{\mathrm{ref}} π ref Ω ∗ \Omega^* Ω ∗ Ω \Omega Ω Ω ∗ \Omega^* Ω ∗
Regularized RL. A regularized MDP is a tuple ( S , A , μ 0 , γ , P , r , Ω ) (\mathcal{S},\mathcal{A},\mu_0,\gamma,P,r,\Omega) ( S , A , μ 0 , γ , P , r , Ω ) Ω \Omega Ω
max π ∈ Δ A S J ( π , r ) + Ω ( π ) , \begin{equation}
\max_{\pi \in \Delta_{\mathcal{A}}^{\mathcal{S}}} \; J(\pi,r)+\Omega(\pi), \tag*{(2)}
\end{equation} π ∈ Δ A S max J ( π , r ) + Ω ( π ) , (2) A widely used choice is policy-entropy regularization [37 , 6 ] : Ω E n t ( π ) = − E [ ∑ t γ t ∑ a π ( a ∣ s t ) log π ( a ∣ s t ) ∣ μ 0 , π , P ] . \Omega_{\mathrm{Ent}}(\pi)= - \mathbb{E}\!\left[\sum_{t}\gamma^t
\sum_{a}\pi(a\mid s_t)\log\pi(a\mid s_t)
\Big| \mu_0,\pi,P\right]. Ω Ent ( π ) = − E [ ∑ t γ t ∑ a π ( a ∣ s t ) log π ( a ∣ s t ) μ 0 , π , P ] . [5 , 85 ] : Ω K L ( π ) = − E [ ∑ t γ t ∑ a π ( a ∣ s t ) log π ( a ∣ s t ) π r e f ( a ∣ s t ) ∣ μ 0 , π , P ] . \Omega_{\mathrm{KL}}(\pi)= - \mathbb{E}\left[\sum_{t}\gamma^t
\sum_{a}\pi(a\mid s_t)\log
\frac{\pi(a\mid s_t)}{\pi_{\mathrm{ref}}(a\mid s_t)}
\Big|\mu_0,\pi,P\right]. Ω KL ( π ) = − E [ ∑ t γ t ∑ a π ( a ∣ s t ) log π ref ( a ∣ s t ) π ( a ∣ s t ) μ 0 , π , P ] . Ω \Omega Ω Ω ∗ \Omega^* Ω ∗ [6 , 5 , 14 ] . In particular, entropy-regularized and KL-regularized RL objectives can be interpreted as reward-robust RL problems, with corresponding discrepancies given by the log-sum-exp penalty [6 ] and a reference policy weighted variant [5 ] . For simplicity, in the remainder of the paper, we refer to these reward-robust formulations by the name of their corresponding regularizer (e.g., “entropy” or “KL”) whenever the meaning is clear. A detailed related work on PBRS, reward-robust RL, and regularized RL is in Appendix § 8 .
Shaping-Aware Reward-Robust RL
Solving the inner minimization in the reward-robust RL objective (1) requires an adversary to search for the worst-case reward within the uncertainty set. However, when the uncertainty set is defined directly in reward space, it can contain many PBRS-equivalent rewards that induce identical policy behavior, leading to redundant adversary search. In § 3.1 , we illustrate this issue on a toy MDP and discuss its impact on optimization behavior. In § 3.2 , we introduce Shaping-Aware Reward-Robust RL, which removes this redundancy by projecting the uncertainty set onto PBRS equivalence classes so that each element corresponds to a behaviorally distinct objective. We show that this projection preserves the optimal robust value while yielding a smaller and more identifiable uncertainty set.
Why PBRS Redundancy Harm Optimization?
[>=stealth, node distance=3cm, scale=0.8]
% States
\node[draw,circle,minimum size=18pt] (s1) {$s_1$};
\node[draw,circle,minimum size=18pt, right=2.0cm of s1] (s2) {$s_2$};
% Transitions
\draw[->] (s1) edge[bend left=20] node[above]{$a_1$} (s2);
\draw[->] (s1) edge[bend right=20] node[below]{$a_2$} (s2);(a)
(b)
Figure 1. (a) A two-state toy MDP. The agent starts in s 1 s_1 s 1 a 1 a_1 a 1 a 2 a_2 a 2 s 1 s_1 s 1 s 2 s_2 s 2 [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 ( r 1 , r 2 ) (r_1, r_2) ( r 1 , r 2 ) r , r ′ , r ′ ′ r,r',r'' r , r ′ , r ′′ r core , r core ′ , r core ′ ′ r_{\text{core}},r'_{\text{core}},r''_{\text{core}} r core , r core ′ , r core ′′
In this section, we illustrate PBRS-induced redundancy and its optimization implications via the toy MDP in Figure 1a . This MDP has two states s 1 , s 2 s_1,s_2 s 1 , s 2 a 1 , a 2 a_1,a_2 a 1 , a 2 s 1 s_1 s 1 s 2 s_2 s 2 r 1 : = r ( s 1 , a 1 , s 2 ) r_1 := r(s_1,a_1,s_2) r 1 := r ( s 1 , a 1 , s 2 ) r 2 : = r ( s 1 , a 2 , s 2 ) r_2 := r(s_1,a_2,s_2) r 2 := r ( s 1 , a 2 , s 2 ) Figure 1b (left), where U : = { ( r 1 , r 2 ) : r 1 ∈ [ 0 , 1 ] , r 2 ∈ [ 0 , 1 ] } . \mathcal{U}:=\{(r_1,r_2): r_1\in[0,1],\, r_2\in[0,1]\}. U := {( r 1 , r 2 ) : r 1 ∈ [ 0 , 1 ] , r 2 ∈ [ 0 , 1 ]} . U \mathcal{U} U sec:preliminary , a potential function takes the form F ( s , a , s ′ ) = γ Φ ( s ′ ) − Φ ( s ) F(s,a,s')=\gamma\Phi(s')-\Phi(s) F ( s , a , s ′ ) = γ Φ ( s ′ ) − Φ ( s ) s 1 → s 2 s_1\!\to\! s_2 s 1 → s 2 F 1 = F 2 = γ Φ ( s 2 ) − Φ ( s 1 ) = : F . F_1 = F_2 = \gamma\Phi(s_2)-\Phi(s_1)=:F. F 1 = F 2 = γ Φ ( s 2 ) − Φ ( s 1 ) =: F . ( r ~ 1 , r ~ 2 ) = ( r 1 , r 2 ) + F ⋅ ( 1 , 1 ) , (\tilde r_1,\tilde r_2)=(r_1,r_2)+F\cdot(1,1), ( r ~ 1 , r ~ 2 ) = ( r 1 , r 2 ) + F ⋅ ( 1 , 1 ) , Δ : = r 1 − r 2 \Delta := r_1-r_2 Δ := r 1 − r 2 1 1 1 ( r 1 , r 2 ) (r_1,r_2) ( r 1 , r 2 ) Figure 1b (left), all rewards lying on the same dashed diagonal are behaviorally equivalent. As a result, U \mathcal{U} U r core r^{\text{core}} r core r 2 core = 0 r_2^{\text{core}}=0 r 2 core = 0 r 1 core = Δ r_1^{\text{core}}=\Delta r 1 core = Δ { ( Δ , 0 ) : Δ ∈ [ − 1 , 1 ] } \{(\Delta,0):\Delta\in[-1,1]\} {( Δ , 0 ) : Δ ∈ [ − 1 , 1 ]} Figure 1b (middle)). Alternatively, we may center rewards by enforcing zero mean, e.g., r 1 core = Δ 2 r_1^{\text{core}}=\tfrac{\Delta}{2} r 1 core = 2 Δ r 2 core = − Δ 2 r_2^{\text{core}}=-\tfrac{\Delta}{2} r 2 core = − 2 Δ Figure 1b (right)).
The PBRS-induced redundancy can lead to inefficient and sometimes misleading worst-case optimization. Consider the adversary’s update over r ~ ∈ U \tilde r \in \mathcal{U} r ~ ∈ U § 5 (MiniGrid experiment) and Appendix § 11.1 in non-convex uncertainty sets.
Robust Objective Invariance Under Shaping
In this section, we make the redundancy phenomenon precise and introduce our shaping-aware reward-robust RL framework to address it. We first define behaviorally equivalent rewards under PBRS: rewards that differ only by a PBRS term shift the return of every policy by the same constant, and therefore induce identical behavior in the sense of decision-making (i.e., leave policy ranking unchanged) [7 ] .
Lemma 3.1. Let Φ ∈ R S \Phi\in\mathbb{R}^{\mathcal{S}} Φ ∈ R S F ( s , a , s ′ ) = γ Φ ( s ′ ) − Φ ( s ) F(s,a,s')=\gamma\Phi(s')-\Phi(s) F ( s , a , s ′ ) = γ Φ ( s ′ ) − Φ ( s ) r ′ ( s , a , s ′ ) = r ( s , a , s ′ ) + F ( s , a , s ′ ) r'(s,a,s')=r(s,a,s')+F(s,a,s') r ′ ( s , a , s ′ ) = r ( s , a , s ′ ) + F ( s , a , s ′ ) π \pi π J ( π , r ′ ) = J ( π , r ) + C ( Φ , μ 0 ) , J(\pi,r') = J(\pi,r) + C(\Phi,\mu_0), J ( π , r ′ ) = J ( π , r ) + C ( Φ , μ 0 ) , C ( Φ , μ 0 ) = − E s 0 ∼ μ 0 [ Φ ( s 0 ) ] C(\Phi,\mu_0)=-\mathbb{E}_{s_0\sim\mu_0}[\Phi(s_0)] C ( Φ , μ 0 ) = − E s 0 ∼ μ 0 [ Φ ( s 0 )] Φ \Phi Φ μ 0 \mu_0 μ 0 π \pi π r ′ r' r ′ r r r
Lemma 3.1 is a well-known property of PBRS, and we include the proof in Appendix § 9.1 for completeness. Notice that the additive term C ( Φ , μ 0 ) C(\Phi,\mu_0) C ( Φ , μ 0 ) s 0 s_0 s 0 Φ ( s 0 ) = 0 \Phi(s_0)=0 Φ ( s 0 ) = 0 C = 0 C=0 C = 0 § 10.2 . Next, we show that the standard uncertainty sets considered in the literature include rewards that are behaviorally indistinguishable under PBRS.
Proposition 3.2. Let U \mathcal{U} U sec:preliminary , of the form U = { r ~ : Ω ∗ ( r − r ~ ) ≤ ϵ } \mathcal{U}=\{\tilde r: \Omega^*(r-\tilde r) \le \epsilon\} U = { r ~ : Ω ∗ ( r − r ~ ) ≤ ϵ } U \mathcal{U} U r ~ \tilde r r ~ U \mathcal{U} U r ~ \tilde r r ~ F ≠ 0 F\neq 0 F = 0 Φ ∈ R S \Phi\in\mathbb{R}^{\mathcal{S}} Φ ∈ R S δ > 0 \delta>0 δ > 0 r ~ + α F ∈ U , for all ∣ α ∣ ≤ δ . \tilde r + \alpha F \in \mathcal{U},\text{ for all }|\alpha|\le \delta. r ~ + α F ∈ U , for all ∣ α ∣ ≤ δ . { r ~ + α F : ∣ α ∣ ≤ δ } \{\tilde r+\alpha F:|\alpha|\le\delta\} { r ~ + α F : ∣ α ∣ ≤ δ }
The proof is provided in Appendix § 9.2 . Proposition 3.2 highlights that, because U \mathcal{U} U R ⊆ R X ′ \mathcal{R}\subseteq \mathbb{R}^{\mathcal{X'}} R ⊆ R X ′ S shape : = { F Φ : Φ ∈ R S } , \mathcal{S}_{\text{shape}} := \{F_{\Phi} : \Phi \in \mathbb{R}^{\mathcal{S}}\}, S shape := { F Φ : Φ ∈ R S } , R core : = R / S shape , \mathcal{R}_{\text{core}} := \mathcal{R} / \mathcal{S}_{\text{shape}}, R core := R / S shape , [ r ] = { r + F Φ : F Φ ∈ S shape } [r]=\{r+F_\Phi: F_\Phi \in \mathcal{S}_{\text{shape}}\} [ r ] = { r + F Φ : F Φ ∈ S shape } Proj : R → R \text{Proj} :\mathcal{R} \to \mathcal{R} Proj : R → R r ∈ R r\in\mathcal{R} r ∈ R Proj ( r ) ∈ [ r ] \text{Proj}(r)\in[r] Proj ( r ) ∈ [ r ] Proj ( r + F Φ ) = Proj ( r ) \text{Proj}(r+F_\Phi)=\text{Proj}(r) Proj ( r + F Φ ) = Proj ( r ) F Φ ∈ S shape F_\Phi\in\mathcal{S}_{\text{shape}} F Φ ∈ S shape U ⊆ R \mathcal{U}\subseteq\mathcal{R} U ⊆ R U core : = Proj ( U ) = { Proj ( r ) : r ∈ U } ⊆ R , \mathcal{U}_{\text{core}} := \text{Proj}(\mathcal{U})
= \{\,\text{Proj}(r) : r \in \mathcal{U}\,\}\subseteq \mathcal{R}, U core := Proj ( U ) = { Proj ( r ) : r ∈ U } ⊆ R , U \mathcal{U} U Proj \text{Proj} Proj U core \mathcal{U}_{\text{core}} U core
Theorem 3.3. Let U core \mathcal{U}_{\text{core}} U core U \mathcal{U} U min r ~ ∈ U J ( π , r ~ ) = min r ~ core ∈ U core J ( π , r ~ core ) , ∀ π .
\min_{\tilde r \in \mathcal{U}} J(\pi, \tilde r)
\;=\;
\min_{\tilde r_{\text{core}} \in \mathcal{U}_{\text{core}}}
J(\pi, \tilde r_{\text{core}}), \qquad \forall \pi.
min r ~ ∈ U J ( π , r ~ ) = min r ~ core ∈ U core J ( π , r ~ core ) , ∀ π . U core \mathcal{U}_{\text{core}} U core
The proof of Theorem 3.3 is provided in Appendix § 9.3 . It follows directly from the definition of U core \mathcal{U}_{\text{core}} U core 3.1 . Theorem 3.3 implies that one can directly solve the robust objective over U c o r e \mathcal U_{\mathrm{core}} U core U \mathcal U U § 5 , where the projected uncertainty set is explicit and can be optimized over efficiently. We quantify how projection reduces the adversary’s effective search space in Appendix § 9.4 , where the extent of the reduction scales with the number of independent shaping directions present in U \mathcal{U} U § 9.5 shows that under mild assumptions, U core \mathcal{U}_{\text{core}} U core U \mathcal{U} U U core \mathcal{U}_{\text{core}} U core
Shaping-Aware Reward-Robust Algorithm
A direct optimization of (3) requires solving the inner minimization over U c o r e \mathcal{U}_{\mathrm{core}} U core U c o r e \mathcal{U}_{\mathrm{core}} U core § 4.1 , we address the issue by leveraging the connection between robustness and regularization. And then we specify a concrete canonicalization rule. We present the overall algorithm in § 4.2 .
Robustness-Regularization Duality Under Shaping
We first show that the regularized objective is a conservative surrogate to (3) .
Theorem 4.1. Fix ϵ ≥ 0 \epsilon\ge 0 ϵ ≥ 0 λ > 0 \lambda>0 λ > 0 Ω \Omega Ω Ω ∗ \Omega^* Ω ∗ U : = { r ~ : Ω ∗ ( r − r ~ λ ) ≤ ϵ } \mathcal{U}
:=\Bigl\{\tilde r:
\Omega^*\left(\frac{r-\tilde r}{\lambda}\right)\le \epsilon
\Bigr\} U := { r ~ : Ω ∗ ( λ r − r ~ ) ≤ ϵ } U c o r e = Proj ( U ) \mathcal{U}_{\mathrm{core}}=\text{Proj}(\mathcal U) U core = Proj ( U ) r c o r e : = Proj ( r ) r_{\mathrm{core}}:=\text{Proj}(r) r core := Proj ( r ) r r r min r ~ c o r e ∈ U c o r e J ( π , r ~ c o r e ) ≥ J ( π , r c o r e ) − λ Ω ( π ) − λ ϵ , ∀ π . \min_{\tilde r_{\mathrm{core}}\in\mathcal U_{\mathrm{core}}}
J(\pi,\tilde r_{\mathrm{core}})
\ge
J(\pi,r_{\mathrm{core}})-\lambda\Omega(\pi)
-\lambda\epsilon, \qquad \forall \pi . min r ~ core ∈ U core J ( π , r ~ core ) ≥ J ( π , r core ) − λ Ω ( π ) − λ ϵ , ∀ π .
The proof is deferred to Appendix § 9.6 , where we first prove the inequality for the original uncertainty set and then show that the same inequality carries over to the projected uncertainty set using Lemma 3.1 and Theorem 3.3 , as projection preserves the robust objective. Theorem 4.1 shows that the regularized objective with the projected base reward r c o r e r_{\mathrm{core}} r core (3) and maximizing this lower bound gives a tractable surrogate. Instead of repeatedly solving the inner minimization over projected rewards, it suffices to compute r c o r e r_{\mathrm{core}} r core
Theorem 4.2. Fix ϵ ≥ 0 \epsilon\ge 0 ϵ ≥ 0 λ > 0 \lambda>0 λ > 0 U = { r ~ : Ω ∗ ( r − r ~ λ ) ≤ ϵ λ } \mathcal U=\left\{
\tilde r: \Omega^*\!\left(\frac{r-\tilde r}{\lambda}\right)
\le \frac{\epsilon}{\lambda}
\right\} U = { r ~ : Ω ∗ ( λ r − r ~ ) ≤ λ ϵ } U c o r e = P r o j ( U ) \mathcal U_{\mathrm{core}}=\mathrm{Proj}(\mathcal U) U core = Proj ( U ) r c o r e : = P r o j ( r ) r_{\mathrm{core}}:=\mathrm{Proj}(r) r core := Proj ( r ) Ω ∗ \Omega^* Ω ∗ sec:preliminary , the following exact correspondence holds: min r ~ c o r e ∈ U c o r e J ( π , r ~ c o r e ) = J ( π , r c o r e ) + λ Ω ( π ) − ϵ , ∀ π , \min_{\tilde r_{\mathrm{core}}\in\mathcal U_{\mathrm{core}}}
J(\pi,\tilde r_{\mathrm{core}})
=J(\pi,r_{\mathrm{core}})
+
\lambda\Omega(\pi)
-
\epsilon,\qquad \forall \pi, min r ~ core ∈ U core J ( π , r ~ core ) = J ( π , r core ) + λ Ω ( π ) − ϵ , ∀ π , Ω = Ω E n t \Omega=\Omega_{\mathrm{Ent}} Ω = Ω Ent Ω = Ω K L \Omega=\Omega_{\mathrm{KL}} Ω = Ω KL
The proof is deferred to Appendix § 9.7 . We first establish the exact correspondence for the original uncertainty sets, following prior work [9 ] , and then extend it to the projected uncertainty set similar to Theorem 4.1 . Theorem 4.2 shows that, for these uncertainty sets, maximizing the regularized objective with r c o r e r_{\mathrm{core}} r core
It remains to specify the projection operator P r o j \mathrm{Proj} Proj Ω ∗ \Omega^* Ω ∗ [ r ] [r] [ r ] Ω ∗ \Omega^* Ω ∗ Proj ( r ) = arg min r ′ ∈ [ r ] Ω ∗ ( r ′ ) . \operatorname{Proj}(r)=\arg\min_{r'\in[r]} \Omega^*(r'). Proj ( r ) = arg min r ′ ∈ [ r ] Ω ∗ ( r ′ ) . Ω ∗ \Omega^* Ω ∗ § 9.8 . In particular, we show that the projection is well-defined by establishing existence and uniqueness. We also show that, from a max-min viewpoint, this projection can tighten convergence bounds for certain optimization methods.
To implement Proj ( r ) \operatorname{Proj}(r) Proj ( r ) r ′ ∈ [ r ] r'\in[r] r ′ ∈ [ r ] r r r r ′ r' r ′ r = r ′ + F Φ r = r'+F_{\Phi} r = r ′ + F Φ F Φ ( s , a , s ′ ) = γ Φ ( s ′ ) − Φ ( s ) F_{\Phi}(s,a,s') = \gamma \Phi(s') - \Phi(s) F Φ ( s , a , s ′ ) = γ Φ ( s ′ ) − Φ ( s ) Φ \Phi Φ Φ φ \Phi_{\varphi} Φ φ φ \varphi φ φ \varphi φ φ ∗ = arg min φ Ω ∗ ( r − F Φ φ ) . \varphi^{*}
= \arg\min_{\varphi}
\Omega^*\Bigl(
r - F_{\Phi_{\varphi}}
\Bigr). φ ∗ = arg min φ Ω ∗ ( r − F Φ φ ) . φ ∗ \varphi^{*} φ ∗ F Φ φ ∗ , F_{\Phi_{\varphi^*}}, F Φ φ ∗ , r ′ = r − F Φ φ ∗ . r' = r - F_{\Phi_{\varphi^*}}. r ′ = r − F Φ φ ∗ .
Shaping-Aware Reward-Robust Policy Gradient
We summarize the overall training procedure to solve our shaping-aware reward-robust RL problem in Algorithm alg:projected-ppo . At each iteration, we first learn the projected reward by estimating the projection loss l ( φ i , k , θ i ; D π θ i ) l(\varphi_{i,k}, \theta_i; \mathcal{D}_{\pi_{\theta_i}}) l ( φ i , k , θ i ; D π θ i ) Ω D π θ i ∗ \Omega^*_{\mathcal{D}_{\pi_{\theta_i}}} Ω D π θ i ∗ Ω ∗ \Omega^* Ω ∗ D π θ i \mathcal{D}_{\pi_{\theta_i}} D π θ i φ \varphi φ § 9.9 that such on-policy projection-learning design is data-efficient and supports online adaptation. Although Algorithm alg:projected-ppo updates the policy via policy gradients, in principle, our projection simply replaces the environment reward with its canonicalized version, so it is compatible with any RL algorithm that optimizes expected return (e.g., SAC [37 ] or PPO [49 ] ). In Appendix § 9.9 , we prove convergence under standard conditions by first analyzing the projection-learning updates and then applying a two-time scale argument [48 , 34 ] to establish convergence of the overall algorithm. Notice that our convergence guarantee relies on a strong convexity assumption for the projection loss (Assumption C.12 ), which does not directly apply to the neural-network setting. We discuss this further in Appendix § 7 . Algorithm alg:projected-ppo learns the projector approximately from a finite rollout batch, so the learned projection may deviate from the exact projector. We show that such projection error does not affect the structure of Theorem 4.1 and 4.2 (Appendix § 9.9 , Theorem (?) and (?) ). It only introduces an approximation error that scales with O ( 1 1 − γ ( log N + log ( 1 / δ ) N ) 1 / 4 ) \mathcal O\left(
\frac{1}{1-\gamma}
\left(
\frac{\log N+\log(1/\delta)}{N}
\right)^{1/4}
\right) O ( 1 − γ 1 ( N l o g N + l o g ( 1/ δ ) ) 1/4 ) N N N
\caption{Shaping-Aware Policy Gradient}
\label{alg:projected-ppo}
\small
\begin{algorithmic}[1]
\STATE \textbf{Hyperparameters:} Iteration number $I$, $K$, Step size $\{\beta_i\}_{i=0}^{I-1}$ for $\theta$, Step size $\{\alpha_{i,k}\}_{i=0,\dots,I-1;\,k=0,\dots,K-1}$ for $\varphi$.
\STATE \textbf{Initialize: } $\theta_0 \in \Theta, \varphi_0 \in \Psi$
\FOR{iteration $i = 0, \dots, I-1$}
\STATE Collect a batch dataset $\mathcal{D}_{\pi_{\theta_i}}$ from the current policy $\pi_{\theta_i}$.
\STATE Initialize $\varphi_{i,0}=\varphi_i$
\FOR{iteration $k = 0, \dots, K$}
\STATE Update $\varphi$:
\(
\varphi_{i,k+1}=\varphi_{i,k}-\alpha_{i,k}\nabla_\varphi l(\varphi_{i,k},\theta_i;\mathcal{D}_{\pi_{\theta_i}})
\)
where \(l(\varphi_{i,k},\theta_i;\mathcal{D}_{\pi_{\theta_i}})= \Omega^*_{\mathcal{D}_{\pi_{\theta_i}}}\bigl(r - F_{\Phi_{\varphi_{i,k}}}\bigr)
\)
\ENDFOR
\STATE Set $\varphi_{i+1}:=\varphi_{i,K}$
\STATE Transform $\mathcal{D}_{\pi_{\theta_i}}$ to $\mathcal{D}'_{\pi_{\theta_i}}$ by replacing the rewards with \(
r'
= r-F_{\Phi_{\varphi_{i+1}}}.
\)
\STATE Update $\theta$ via \(
\theta_{i+1}=\theta_i+\beta_i \nabla_\theta\bar J(\theta_i,\varphi_{i+1};\mathcal{D}'_{\pi_{\theta_i}})
\)
where \(
\bar J(\theta_i,\varphi_{i+1};\mathcal{D}'_{\pi_{\theta_i}}) = J_{\mathcal{D}'_{\pi_{\theta_i}}}(\pi_{\theta_i},r_{\varphi_{i+1}})-\Omega_{\mathcal{D}'_{\pi_{\theta_i}}}(\pi_{\theta_i})
\)
\ENDFOR
\end{algorithmic}
Experiment
We evaluate the performance and robustness of our shaping-aware reward-robust RL framework across benchmarks that span different task domains, and levels of complexity. Our goal is to test whether our method improves (i) nominal performance during robust training and (ii) robustness to reward misspecification, relative to standard reward-robust RL baselines.
Experiment setup. We use a MiniGrid environment [51 ] as a controlled discrete benchmark for directly studying the max-min robust objective. In this setting, we adopt an l 2 l_2 l 2 sec:preliminary . In each case, we compare a standard PPO baseline against our approach, which uses the same PPO but augments training with the proposed projection step. We evaluate continuous-control performance on five OpenAI Gym MuJoCo environments [22 , 23 ] : Hopper-v4, Walker2d-v4, HalfCheetah-v4, Humanoid-v4, and Reacher-v4. These environments cover a meaningful range of state-action dimensions, where Hopper and Reacher represent smaller-scale settings, Walker2d and HalfCheetah represent mid-scale locomotion tasks, and Humanoid is substantially higher-dimensional. To evaluate generalization beyond continuous-control domains, we extend the evaluation to Atari [96 ] . Specifically, we consider Seaquest and Pong, which have discrete action spaces and high-dimensional visual observations of size 210 × 160 × 3 210\times160\times3 210 × 160 × 3 [97 ] as a more challenging simulated robotics benchmark. This task has a high-dimensional action space (23), allowing us to assess whether our method remains effective in higher-dimensional robotic manipulation. Additional implementation details are provided in Appendix § 10 . Additional results, including learning curves showing faster convergence of our method, computational overhead, an ablation study on the sensitivity to data coverage for the projection learning, are presented in Appendix § 11 .
Figure 2. MiniGrid evaluation comparing the standard max-min baseline and our shaping-aware method. (a) Grid-world task: the agent starts in the top-left cell and must reach the goal in the bottom-right cell. (b) Worst-case return as a function of training iteration. (c) Fraction of each adversary update that lies in PBRS-invariant directions.
Figure 3. Mean ± \pm ±
MiniGrid max-min robust training. The evaluation result in the MiniGrid environment can be seen in Figure 2 . Specifically, Figure 2a reports the worst-case return J ( π , r worst ) J(\pi, r_{\text{worst}}) J ( π , r worst ) Figure 2b quantifies, at each outer iteration, what fraction of the adversary’s update lies in PBRS-invariant directions. For the standard baseline, a persistent and significant fraction of adversary updates moves along shaping directions that do not alter policy orderings. This arises because the inner minimization is solved only approximately (via limited gradient descent), and the stochastic estimation noise (soft-max policies) together with inner-loop hyperparameter choices (stepsize) can induce drift along PBRS-invariant directions. Such updates are effectively wasted from the perspective of identifying more adverse behaviors and lead to premature stabilization at some PBRS-equivalent rewards that provide little genuine progress in lowering the worst-case value. In contrast, our method operates directly in the projected reward space, where PBRS-invariant directions are removed. As a result, the PBRS-invariant component of the adversary update is near zero, and each update is identifiable in the sense that it can meaningfully affect the worst-case objective. Together, these results support our motivating claim: removing PBRS redundancy makes adversary updates behaviorally identifiable, which translates into more effective robust training and better final worst-case performance.
Comparison on MuJoCo, Atari, and Gymnasium-Robotics tasks. To evaluate how well each method performs under the nominal environments, we report the results in Table tab:nominal_result . Across all cases, our shaping-aware variant consistently outperforms the corresponding robust RL baseline. In the MuJoCo environment, the gains are especially pronounced in mid-scale environments, e.g., 107.7% on HalfCheetah in the KL setting. For the relatively smaller and larger environments, the improvements are moderate but still consistent. Notably, even on the highest-complexity Humanoid task, our method still achieves a 12.2% improvement in the KL setting, suggesting that the benefit of our method persists beyond low-dimensional problems. The additional results from Atari and Gymnasium-Robotics further support this trend. On the visual Atari tasks, our method improves both Seaquest and Pong, while on the more challenging Adroit Pen manipulation task, it achieves substantial gains of 37.3% in the KL setting, indicating that the benefits extend to high-dimensional visual and robotic manipulation domains. Overall, these results show that our method consistently improves robust policy learning and yields higher worst-case returns, thereby supporting the framework’s broader applicability across different dimensions and task domains.
Testing for reward robustness. To assess robustness to reward uncertainty, we evaluate all methods under structured reward perturbations that change the task incentives. We focus the evaluation on MuJoCo as its reward components are easily perturbable, and such structured reward-shift protocols have been widely used in prior work [14 , 9 ] . For the locomotion tasks (HalfCheetah, Hopper, Walker2d, and Humanoid), the nominal reward primarily encourages forward progress, and moving backward typically yields a non-positive reward. Following the protocol of [14 ] , during training, we flip this incentive by adding random reward shifts, so that backward motion can also be beneficial under the perturbed rewards. We report performance under the original reward during evaluation. For Reacher, where the objective is to reach a target position, we adopt the evaluation protocol of [9 ] . All policies are trained on the nominal environment. At test time, we relocate the target to a random position at varying distances from the nominal location and evaluate performance with respect to the reward induced by this relocated target. Implementation details for constructing the perturbed rewards are provided in Appendix § 10.3 . Overall, these perturbations introduce systematic and interpretable reward misspecification across domains, allowing us to compare how well each method maintains performance when the reward deviates from the nominal specification.
Figure 8 reports robustness under reward perturbations for the entropy-based problem, and we include the results for KL-based problem in Appendix § 11.3 . Overall, the shaping-aware method exhibits smaller performance degradation than the robust RL baseline as the reward shift radius increases, indicating improved stability to reward misspecification. The perturbations affect HalfCheetah and Walker2d most strongly, where returns drop sharply for both methods as the shift radius grows, suggesting these locomotion tasks are particularly sensitive to reward changes. In contrast, Hopper, Humanoid, and Reacher show more moderate changes with increasing shift radius, and the shaping-aware method consistently maintains higher returns than the baseline across perturbation levels.
To provide a more direct evaluation of whether the observed improvement specifically arises from removing PBRS redundancy rather than from generic reward shaping, we define the actual PBRS component learned by our method as F Φ ⋆ = r − r c o r e F_{\Phi^\star}=r- r_{\mathrm{core}} F Φ ⋆ = r − r core r α = r c o r e + α F Φ ⋆ r_{\alpha}=r_{\mathrm{core}}+\alpha F_{\Phi^\star} r α = r core + α F Φ ⋆ α = 0 , 0.25 , 0.5 , 0.75 , 1 \alpha=0,0.25,0.5, 0.75, 1 α = 0 , 0.25 , 0.5 , 0.75 , 1 α = 0 \alpha=0 α = 0 α = 1 \alpha=1 α = 1 tab:shaping_coefficient shows that, under the same PPO training budget, the canonical reward with α = 0 \alpha=0 α = 0 α \alpha α
Ablation on projection choices. To isolate the contribution of our Ω ∗ \Omega^* Ω ∗ tab:ablation_canon_walker2d_entropy compares several projection choices under reward perturbations. Implementation details are provided in Appendix § 10.4 , and full results for all environments are reported in Appendix § 11.5 . First, we include a random Φ \Phi Φ L 2 L^2 L 2 Ω ∗ \Omega^* Ω ∗
Conclusion
In this paper, we propose Shaping-Aware Reward-Robust RL, which constructs behavior discriminative uncertainty sets over PBRS equivalence classes and enables practical training via a projection-learning module compatible with standard RL optimizers. Across diverse tasks, our method consistently improves robust performance over representative baselines. These results support our central claim that eliminating behaviorally equivalent rewards leads to more effective robust policy learning under reward uncertainty. We discuss limitations and future directions in Appendix § 7 .
Acknowledgments
This work was supported in part by NSF grant CNS-2146548, a grant from the Louisiana Board of Regents, a gift from Coefficient Giving, and funding from Tulane University Jurist Center for Artificial Intelligence. We thank the anonymous reviewers for their insightful and constructive feedback.
Limitations
Despite the effectiveness of our framework, several limitations remain. First, our current convergence guarantee relies on a strong convexity assumption for the projection objective, which does not directly apply to the neural-network setting and remains a limitation of the current work. Theoretically, this assumption is used to ensure a well-behaved projection and support convergence to the desired optimum over the projection parameters φ \varphi φ λ 2 ∣ φ ∣ 2 \frac{\lambda}{2}|\varphi|^2 2 λ ∣ φ ∣ 2 § 10.2 . Although the projection is still learned only approximately in this deep setting, this regularization helps stabilize the projection-learning process in practice [100 ] and leads to promising empirical performance in our experiments. We also emphasize that, even without strong convexity, one can still analyze convergence under weaker conditions such as Hölderian error bounds [101 ] or the Polyak-Łojasiewicz inequality [102 ] , which are widely used in the nonconvex optimization literature and are more realistic for neural networks. However, pursuing such an extension is beyond the scope of the current paper. We believe it is common in RL research to present theory under stronger, more tractable assumptions than those satisfied by the neural-network implementation used in experiments. In particular, much of RL theory is still built around tabular, linear, or otherwise structured function classes, while practical success often relies on deep neural networks, for which comparable end-to-end guarantees are much harder to obtain. For example, [106 ] derives a two time-scale convergence result under Assumptions 6-7, which do not hold for the deep neural network used in their experiments, but are introduced to illustrate the behavior of the proposed algorithm (page 12). Overall, we view our current theory as a simplified analysis that highlights the main idea, and the lack of strong convexity for neural networks remains a limitation.
Second, our theory builds on PBRS equivalence relations, and thus, the benefit of the method may be limited when reward misspecification is not PBRS-type redundant. In fact, many widely used uncertainty sets in reward-robust RL literature, including ℓ p \ell_p ℓ p [103 ] shows that reward learning and policy optimization can exhibit additional forms of reward non-identifiability beyond PBRS: rewards that differ on unreachable transitions, differ only by next-state redistribution, differ by positive linear scaling, or belong to broader optimality-preserving classes may induce the same downstream object or policy behavior. Extending our framework to handle such forms of redundancy, or more general behavior-discriminative uncertainty sets beyond PBRS, is not covered in the current paper and is an important direction for future work.
Reward-Robust RL and Regularization RL
Reward-robust RL studies how to learn policies that remain effective when the reward signal is perturbed in an adversarial manner [1 ] , and has been explored in a broad range of settings [30 , 53 , 54 , 52 , 107 ] . A common view is to think of the problem as a dynamic zero-sum game: the agent selects a policy to maximize return, while an adversary selects a reward within a prescribed uncertainty set to minimize it [2 , 3 ] . This leads to a max-min optimization problem that is often expensive to solve, creating practical bottlenecks for large-scale applications [59 ] . To improve tractability, recent work has pursued several directions. Some approaches exploit structured uncertainty sets that admit more efficient optimization [55 , 4 , 56 ] . In contrast, a larger body of work adopts rectangular uncertainty across states or state-action pairs to derive scalable solvers [57 , 58 , 12 , 13 ] . In parallel, the strong empirical performance of regularized policy optimization has motivated many methods that use explicit regularizers to encourage desirable behavior, such as better exploration [60 , 61 , 35 , 36 ] , improved training stability [62 , 37 ] , and improved sample efficiency [39 ] .
More recently, there is growing recognition that certain robust RL objectives are closely connected to regularized RL formulations. Such robustness-regularization duality typically relies on the Legendre-Fenchel transform, which has been well established in statistical learning [63 , 64 , 65 , 66 ] . In the RL setting, [5 ] formally proves that policy regularization methods solve a particular instance of robust MDPs with uncertain rewards. A representative example is [6 ] , which shows that maximum policy entropy regularized RL maximizes a lower bound on a reward-robust RL objective, and thus can be used to learn policies that are robust to some disturbances in the reward function. Subsequent work has expanded this perspective beyond policy regularization to state- and state-action-based regularizer, which induce robustness against adversaries that depend on global patterns rather than only local information [38 , 39 , 40 , 42 , 41 ] . In particular, [14 ] studies a broad family of regularized RL objectives and derives the corresponding adversarial-reward dual problems, and [9 ] analyzes the special case of state-entropy regularization, demonstrating improved robustness to structured, spatially correlated perturbations.
In this work, we build on the same Legendre-Fenchel duality and show that the regularization-robustness correspondence can be extended to our shaping-aware reward-robust objective. This equivalence enables us to avoid solving the inner minimization on the projected uncertainty set directly and instead optimize an associated regularized objective, substantially reducing the computational overhead of our approach.
Potential-Based Reward Shaping
Potential-based reward shaping (PBRS) was introduced by [7 ] as a principled way to modify rewards without changing the optimal policy. The key idea is to add a shaping term defined by the difference of a potential function evaluated at two states, which can be canceled out in the Bellman equation, thus preserving the optimal policy [67 , 68 ] . PBRS is generally used to incorporate heuristics or task-agnostic metrics that encourage broader state exploration [69 ] . Accordingly, much of the literature focuses on how to construct effective potential functions. In some large-scale practical RL tasks, the potential functions are heavily handcrafted based on prior knowledge [70 , 71 , 72 ] . Besides reward engineering, a distinct line of work applies exploration bonuses to reward novel or infrequently visited states [73 , 74 , 75 , 76 ] . For example, count-based reward shaping tracks visitation counts and assigns higher rewards to less frequently visited states [77 , 78 , 79 ] . However, in continuous spaces, exact state counting is typically infeasible, and prior work mainly relies on approximations. For example, [80 ] uses hashing to discretize the state space and enable count-style bonuses, while [81 ] proposes pseudo-counts derived from recording probabilities. Beyond count-based reward shaping, several works incorporate structured domain knowledge into shaping to guide exploration more directly, for example, by using heuristic shaping to reduce the effective horizon [82 ] or by exploiting shaping to narrow the portion of the state space that must be searched [83 ] . Recent approaches also consider alternative feedback signals, such as success rates derived from historical experience as the shaped rewards, to balance exploration and exploitation in a more adaptive way [69 ] .
Beyond exploration, PBRS has also been used as a general mechanism for integrating task structure and prior knowledge into RL objectives. For instance, [87 ] proposes a reachability-based shaping signal for hierarchical RL to alleviate the negative interference of suboptimal demonstrations, where shaped rewards encode progress toward subgoals, enabling efficient skill learning. In addition, reward shaping has been adopted in deep RL practice as a way to mitigate sparse reward problems. [88 ] introduces a predictive coding-based shaping objective that understands the structure and dynamics of the environment and emphasize on features most useful for learning, improving learning stability under sparse rewards. More recently, reward shaping has been revisited through the lens of foundation models. Text2Reward [89 ] uses language models to generate reward signals from natural-language task descriptions, reflecting an emerging direction where shaping is produced from semantic feedback rather than hand-designed potentials.
Our paper is also related to a broader line of work on reward design and reward optimization as a method of shaping agent behavior. For instance, behavior alignment via reward optimization directly treats the reward as a design variable to induce desired behaviors [92 ] , while online reward selection methods intertwine reward selection with policy optimization to improve sample efficiency in reward design loops [90 ] . In RLHF, recent work studies how to improve the discriminative power of learned reward models (e.g., via contrastive objectives), which are conceptually adjacent to our emphasis on behavior-discriminative reward representations [91 ] .
In contrast to prior work, which primarily designs shaped rewards to improve exploration or induce desired behaviors, we use reward shaping as a tool for robustness modeling. To the best of our knowledge, we are the first to bring PBRS into reward-robust RL to construct uncertainty sets over behaviorally meaningful variations rather than variations in raw reward values. Leveraging PBRS’s policy invariance property, we identify and remove shaping-induced redundancies in standard uncertainty sets, yielding a reduced set in which each remaining reward corresponds to a behaviorally distinct objective.
Proofs
Proof of Lemma 3.1
Proof. Fix any policy π \pi π s 0 = s s_0=s s 0 = s s ∈ S s \in \mathcal{S} s ∈ S v r π ( s ) = E [ ∑ t = 0 ∞ γ t r ( s t , a t , s t + 1 ) ∣ s 0 = s , π , P ] v^{\pi}_{r}(s)
= \mathbb{E}\!\left[\sum_{t=0}^{\infty} \gamma^{t} r(s_t,a_t,s_{t+1})
\,\Big|\, s_0 = s,\pi,P \right] v r π ( s ) = E [ ∑ t = 0 ∞ γ t r ( s t , a t , s t + 1 ) s 0 = s , π , P ] s s s r ′ r' r ′
v r ′ π ( s ) = E [ ∑ t = 0 ∞ γ t ( r ( s t , a t , s t + 1 ) + ( γ Φ ( s t + 1 ) − Φ ( s t ) ) ) ∣ s 0 = s , π , P ] = v r π ( s ) + E [ ∑ t = 0 ∞ γ t + 1 Φ ( s t + 1 ) − ∑ t = 0 ∞ γ t Φ ( s t ) ∣ s 0 = s , π , P ] . \begin{align*}
v^{\pi}_{r'}(s)
&= \mathbb{E}\!\left[\sum_{t=0}^{\infty}\gamma^t\bigl(r(s_t,a_t,s_{t+1})+(\gamma\Phi(s_{t+1})-\Phi(s_t))\bigr)\,\Big|\,s_0=s,\pi,P\right] \\
&= v^{\pi}_{r}(s)
\;+\;\,\mathbb{E}\!\left[\sum_{t=0}^{\infty}\gamma^{t+1}\Phi(s_{t+1 })-\sum_{t=0}^{\infty}\gamma^t\Phi(s_t)\,\Big|\,s_0=s,\pi,P\right].
\end{align*} v r ′ π ( s ) = E [ t = 0 ∑ ∞ γ t ( r ( s t , a t , s t + 1 ) + ( γ Φ ( s t + 1 ) − Φ ( s t )) ) s 0 = s , π , P ] = v r π ( s ) + E [ t = 0 ∑ ∞ γ t + 1 Φ ( s t + 1 ) − t = 0 ∑ ∞ γ t Φ ( s t ) s 0 = s , π , P ] . The first sum can be re-indexed as ∑ t = 0 ∞ γ t + 1 Φ ( s t + 1 ) = ∑ t = 1 ∞ γ t Φ ( s t ) \sum_{t=0}^{\infty}\gamma^{t+1}\Phi(s_{t+1})=\sum_{t=1}^{\infty}\gamma^t\Phi(s_t) ∑ t = 0 ∞ γ t + 1 Φ ( s t + 1 ) = ∑ t = 1 ∞ γ t Φ ( s t )
∑ t = 1 ∞ γ t Φ ( s t ) − ∑ t = 0 ∞ γ t Φ ( s t ) = − Φ ( s 0 ) . \sum_{t=1}^{\infty}\gamma^t\Phi(s_t)-\sum_{t=0}^{\infty}\gamma^t\Phi(s_t)
= -\Phi(s_0). t = 1 ∑ ∞ γ t Φ ( s t ) − t = 0 ∑ ∞ γ t Φ ( s t ) = − Φ ( s 0 ) . Hence
v r ′ π ( s ) = v r π ( s ) − Φ ( s 0 ) , v^{\pi}_{r'}(s)=v^{\pi}_{r}(s)-\Phi(s_0), v r ′ π ( s ) = v r π ( s ) − Φ ( s 0 ) , and consequently
J ( π , r ′ ) = E s 0 ∼ μ 0 [ v r π ( s 0 ) ] = J ( π , r ) − E s 0 ∼ μ 0 [ Φ ( s 0 ) ] . J(\pi,r')
=\mathbb{E}_{s_0\sim\mu_0}\!\bigl[v^{\pi}_{r}(s_0)\bigr]
=J(\pi,r)-\mathbb{E}_{s_0\sim\mu_0}[\Phi(s_0)]. J ( π , r ′ ) = E s 0 ∼ μ 0 [ v r π ( s 0 ) ] = J ( π , r ) − E s 0 ∼ μ 0 [ Φ ( s 0 )] . The shift − E s 0 ∼ μ 0 [ Φ ( s 0 ) ] -\mathbb{E}_{s_0\sim\mu_0}[\Phi(s_0)] − E s 0 ∼ μ 0 [ Φ ( s 0 )] π \pi π
Proof of Proposition 3.2
Proof. Fix ( μ 0 , π , P ) (\mu_0,\pi,P) ( μ 0 , π , P ) R X ′ \mathbb{R}^{\mathcal{X'}} R X ′ U \mathcal{U} U r ~ \tilde r r ~ ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ R X ′ \mathbb{R}^{\mathcal{X'}} R X ′ ρ > 0 \rho>0 ρ > 0
B ( r ~ , ρ ) : = { u ∈ R X ′ : ∥ u − r ~ ∥ < ρ } ⊆ U . B(\tilde r,\rho)\;:=\;\{u\in \mathbb{R}^{\mathcal{X'}}:\|u-\tilde r\|<\rho\}
\subseteq \mathcal{U}. B ( r ~ , ρ ) := { u ∈ R X ′ : ∥ u − r ~ ∥ < ρ } ⊆ U . Next, choose any potential function Φ ∈ R S \Phi\in\mathbb{R}^{\mathcal{S}} Φ ∈ R S s 1 ≠ s 2 s_1\neq s_2 s 1 = s 2 Φ ( s 1 ) = 1 , Φ ( s 2 ) = 0 \Phi(s_1)=1,\Phi(s_2)=0 Φ ( s 1 ) = 1 , Φ ( s 2 ) = 0 Φ = 0 \Phi=0 Φ = 0 F ∈ R X ′ F\in \mathbb{R}^{\mathcal{X'}} F ∈ R X ′ F ( s , a , s ′ ) = γ Φ ( s ′ ) − Φ ( s ) F(s,a,s')=\gamma\Phi(s')-\Phi(s) F ( s , a , s ′ ) = γ Φ ( s ′ ) − Φ ( s ) Φ \Phi Φ F ≠ 0 F\neq 0 F = 0 ∥ F ∥ > 0 \|F\|>0 ∥ F ∥ > 0 δ : = ρ / ∥ F ∥ \delta := \rho/\|F\| δ := ρ /∥ F ∥ α ∈ R \alpha\in\mathbb{R} α ∈ R ∣ α ∣ ≤ δ |\alpha|\le \delta ∣ α ∣ ≤ δ
∥ r ~ + α F − r ~ ∥ = ∥ α F ∥ ≤ ∣ α ∣ ∥ F ∥ ≤ δ ∥ F ∥ = ρ , \|\tilde r+\alpha F-\tilde r\| = \|\alpha F\| \le |\alpha|\,\|F\| \le \delta \|F\|=\rho, ∥ r ~ + α F − r ~ ∥ = ∥ α F ∥ ≤ ∣ α ∣ ∥ F ∥ ≤ δ ∥ F ∥ = ρ , which implies r ~ + α F ∈ B ( r ~ , ρ ) ⊆ U \tilde r+\alpha F \in B(\tilde r,\rho)\subseteq \mathcal{U} r ~ + α F ∈ B ( r ~ , ρ ) ⊆ U
It remains to show PBRS equivalence. Fix any policy π \pi π s 0 = s s_0=s s 0 = s s ∈ S s \in \mathcal{S} s ∈ S v r π ( s ) = E [ ∑ t = 0 ∞ γ t r ( s t , a t , s t + 1 ) ∣ s 0 = s , π , P ] v^{\pi}_{r}(s)
= \mathbb{E}\!\left[\sum_{t=0}^{\infty} \gamma^{t} r(s_t,a_t,s_{t+1})
\,\Big|\, s_0 = s,\pi,P \right] v r π ( s ) = E [ ∑ t = 0 ∞ γ t r ( s t , a t , s t + 1 ) s 0 = s , π , P ] s s s r ~ + α F \tilde r+\alpha F r ~ + α F
v r ~ + α F π ( s ) = E [ ∑ t = 0 ∞ γ t ( r ~ ( s t , a t , s t + 1 ) + α ( γ Φ ( s t + 1 ) − Φ ( s t ) ) ) ∣ s 0 = s , π , P ] = v r ~ π ( s ) + α E [ ∑ t = 0 ∞ γ t + 1 Φ ( s t + 1 ) − ∑ t = 0 ∞ γ t Φ ( s t ) ∣ s 0 = s , π , P ] . \begin{align*}
v^{\pi}_{\tilde r+\alpha F}(s)
&= \mathbb{E}\!\left[\sum_{t=0}^{\infty}\gamma^t\bigl(\tilde r(s_t,a_t,s_{t+1})+\alpha(\gamma\Phi(s_{t+1})-\Phi(s_t))\bigr)\,\Big|\,s_0=s,\pi,P\right] \\
&= v^{\pi}_{\tilde r}(s)
\;+\;\alpha\,\mathbb{E}\!\left[\sum_{t=0}^{\infty}\gamma^{t+1}\Phi(s_{t+1 })-\sum_{t=0}^{\infty}\gamma^t\Phi(s_t)\,\Big|\,s_0=s,\pi,P\right].
\end{align*} v r ~ + α F π ( s ) = E [ t = 0 ∑ ∞ γ t ( r ~ ( s t , a t , s t + 1 ) + α ( γ Φ ( s t + 1 ) − Φ ( s t )) ) s 0 = s , π , P ] = v r ~ π ( s ) + α E [ t = 0 ∑ ∞ γ t + 1 Φ ( s t + 1 ) − t = 0 ∑ ∞ γ t Φ ( s t ) s 0 = s , π , P ] . The first sum can be re-indexed as ∑ t = 0 ∞ γ t + 1 Φ ( s t + 1 ) = ∑ t = 1 ∞ γ t Φ ( s t ) \sum_{t=0}^{\infty}\gamma^{t+1}\Phi(s_{t+1})=\sum_{t=1}^{\infty}\gamma^t\Phi(s_t) ∑ t = 0 ∞ γ t + 1 Φ ( s t + 1 ) = ∑ t = 1 ∞ γ t Φ ( s t )
∑ t = 1 ∞ γ t Φ ( s t ) − ∑ t = 0 ∞ γ t Φ ( s t ) = − Φ ( s 0 ) . \sum_{t=1}^{\infty}\gamma^t\Phi(s_t)-\sum_{t=0}^{\infty}\gamma^t\Phi(s_t)
= -\Phi(s_0). t = 1 ∑ ∞ γ t Φ ( s t ) − t = 0 ∑ ∞ γ t Φ ( s t ) = − Φ ( s 0 ) . Hence
v r ~ + α F π ( s ) = v r ~ π ( s ) − α Φ ( s 0 ) , v^{\pi}_{\tilde r+\alpha F}(s)=v^{\pi}_{\tilde r}(s)-\alpha\,\Phi(s_0), v r ~ + α F π ( s ) = v r ~ π ( s ) − α Φ ( s 0 ) , and consequently
J ( π , r ~ + α F ) = E s 0 ∼ μ 0 [ v r ~ + α F π ( s 0 ) ] = J ( π , r ~ ) − α E s 0 ∼ μ 0 [ Φ ( s 0 ) ] . J(\pi,\tilde r+\alpha F)
=\mathbb{E}_{s_0\sim\mu_0}\!\bigl[v^{\pi}_{\tilde r+\alpha F}(s_0)\bigr]
=J(\pi,\tilde r)-\alpha\,\mathbb{E}_{s_0\sim\mu_0}[\Phi(s_0)]. J ( π , r ~ + α F ) = E s 0 ∼ μ 0 [ v r ~ + α F π ( s 0 ) ] = J ( π , r ~ ) − α E s 0 ∼ μ 0 [ Φ ( s 0 )] . The shift − α E s 0 ∼ μ 0 [ Φ ( s 0 ) ] -\alpha\,\mathbb{E}_{s_0\sim\mu_0}[\Phi(s_0)] − α E s 0 ∼ μ 0 [ Φ ( s 0 )] π \pi π π 1 , π 2 \pi_1,\pi_2 π 1 , π 2
J ( π 1 , r ~ + α F ) − J ( π 2 , r ~ + α F ) = J ( π 1 , r ~ ) − J ( π 2 , r ~ ) . J(\pi_1,\tilde r+\alpha F)-J(\pi_2,\tilde r+\alpha F)
=J(\pi_1,\tilde r)-J(\pi_2,\tilde r). J ( π 1 , r ~ + α F ) − J ( π 2 , r ~ + α F ) = J ( π 1 , r ~ ) − J ( π 2 , r ~ ) . Thus all rewards in { r ~ + α F : ∣ α ∣ ≤ δ } \{\tilde r+\alpha F:|\alpha|\le\delta\} { r ~ + α F : ∣ α ∣ ≤ δ }
Proof of Theorem 3.3
Proof. Take any r ~ ∈ R \tilde r \in \mathcal{R} r ~ ∈ R Proj \text{Proj} Proj Proj ( r ~ ) = r ~ + F Φ \text{Proj}(\tilde r) = \tilde r + F_\Phi Proj ( r ~ ) = r ~ + F Φ F Φ ∈ S shape F_\Phi \in \mathcal{S}_{\text{shape}} F Φ ∈ S shape 3.1 , we have
J ( π , Proj ( r ~ ) ) = J ( π , r ~ + F Φ ) = J ( π , r ~ ) ∀ π . \begin{equation}
J(\pi, \text{Proj}(\tilde r))
= J(\pi, \tilde r + F_\Phi)
= J(\pi, \tilde r)
\qquad \forall\, \pi. \tag*{(4)}
\end{equation} J ( π , Proj ( r ~ )) = J ( π , r ~ + F Φ ) = J ( π , r ~ ) ∀ π . (4) So for each reward, its value is exactly the same as its projected version.
Let
m : = min r ~ ∈ U J ( π , r ~ ) , m core : = min r ~ core ∈ U core J ( π , r ~ core ) . m := \min_{\tilde r\in\mathcal{U}} J(\pi,\tilde r),
\qquad
m_{\text{core}} := \min_{\tilde r_{\text{core}}\in\mathcal{U}_{\text{core}}}
J(\pi,\tilde r_{\text{core}}). m := r ~ ∈ U min J ( π , r ~ ) , m core := r ~ core ∈ U core min J ( π , r ~ core ) . Take any r ~ ∈ U \tilde r \in \mathcal{U} r ~ ∈ U (4) , we have
J ( π , r ~ ) = J ( π , Proj ( r ~ ) ) ≥ m core , J(\pi,\tilde r) = J(\pi,\text{Proj}(\tilde r)) \ge m_{\text{core}}, J ( π , r ~ ) = J ( π , Proj ( r ~ )) ≥ m core , because Proj ( r ~ ) ∈ U core \text{Proj}(\tilde r) \in \mathcal{U}_{\text{core}} Proj ( r ~ ) ∈ U core m core m_{\text{core}} m core
Since this holds for every r ~ ∈ U \tilde r \in \mathcal{U} r ~ ∈ U r ~ ∈ U \tilde r\in\mathcal{U} r ~ ∈ U
m = min r ~ ∈ U J ( π , r ~ ) ≥ m core . \begin{equation}
m = \min_{\tilde r\in\mathcal{U}} J(\pi,\tilde r) \ge m_{\text{core}}. \tag*{(5)}
\end{equation} m = r ~ ∈ U min J ( π , r ~ ) ≥ m core . (5) Now take any r ~ core ∈ U core \tilde r_{\text{core}} \in \mathcal{U}_{\text{core}} r ~ core ∈ U core U core \mathcal{U}_{\text{core}} U core r ~ ∈ U \tilde r \in \mathcal{U} r ~ ∈ U
r ~ core = Proj ( r ~ ) . \tilde r_{\text{core}} = \text{Proj}(\tilde r). r ~ core = Proj ( r ~ ) . Using Lemma 3.1 again,
J ( π , r ~ core ) = J ( π , r ~ ) . J(\pi, \tilde r_{\text{core}}) = J(\pi, \tilde r). J ( π , r ~ core ) = J ( π , r ~ ) . By definition of m m m
m : = min r ~ ∈ U J ( π , r ~ ) ≤ J ( π , r ~ ) = J ( π , r ~ core ) . m := \min_{\tilde r\in\mathcal{U}} J(\pi,\tilde r)
\;\le\; J(\pi,\tilde r) = J(\pi,\tilde r_{\text{core}}). m := r ~ ∈ U min J ( π , r ~ ) ≤ J ( π , r ~ ) = J ( π , r ~ core ) . Since this holds for every r ~ core ∈ U core \tilde r_{\text{core}} \in \mathcal{U}_{\text{core}} r ~ core ∈ U core r ~ core ∈ U core \tilde r_{\text{core}} \in \mathcal{U}_{\text{core}} r ~ core ∈ U core
m ≤ min r ~ core ∈ U core J ( π , r ~ core ) = m core . \begin{equation}
m \;\le\; \min_{\tilde r_{\text{core}}\in\mathcal{U}_{\text{core}}} J(\pi,\tilde r_{\text{core}})
= m_{\text{core}}. \tag*{(6)}
\end{equation} m ≤ r ~ core ∈ U core min J ( π , r ~ core ) = m core . (6) From Equation (5) and Equation (6) , we have
m ≥ m core and m ≤ m core ⇒ m = m core . m \ge m_{\text{core}}
\quad\text{and}\quad
m \le m_{\text{core}}
\;\;\Rightarrow\;\;
m = m_{\text{core}}. m ≥ m core and m ≤ m core ⇒ m = m core . Thus, for any policy π \pi π
min r ~ ∈ U J ( π , r ~ ) = min r ~ core ∈ U core J ( π , r ~ core ) . \min_{\tilde r\in\mathcal{U}} J(\pi,\tilde r)
=
\min_{\tilde r_{\text{core}}\in\mathcal{U}_{\text{core}}} J(\pi,\tilde r_{\text{core}}). r ~ ∈ U min J ( π , r ~ ) = r ~ core ∈ U core min J ( π , r ~ core ) . Now take the max over policies:
max π min r ~ ∈ U J ( π , r ~ ) = max π min r ~ core ∈ U core J ( π , r ~ core ) . \max_{\pi} \min_{\tilde r\in\mathcal{U}} J(\pi,\tilde r)
=
\max_{\pi} \min_{\tilde r_{\text{core}}\in\mathcal{U}_{\text{core}}} J(\pi,\tilde r_{\text{core}}). π max r ~ ∈ U min J ( π , r ~ ) = π max r ~ core ∈ U core min J ( π , r ~ core ) . Because the inner quantities are identical for each π \pi π arg max π \arg\max_{\pi} arg max π U \mathcal{U} U U core \mathcal{U}_{\text{core}} U core
Dimension Drop for Shaping-Aware Projected Uncertainty Set
In this section, we quantify how projection reduces the adversary’s effective search space. Since U core \mathcal{U}_{\text{core}} U core
Proposition C.1. Assume a linear parameterization of the reward function: r θ ( s , a , s ′ ) = ϕ ( s , a , s ′ ) ⊤ θ , θ ∈ Θ , r_\theta(s,a,s') = \phi(s,a,s')^\top \theta,\theta \in \Theta, r θ ( s , a , s ′ ) = ϕ ( s , a , s ′ ) ⊤ θ , θ ∈ Θ , Θ ⊆ R d \Theta \subseteq \mathbb{R}^d Θ ⊆ R d U \mathcal{U} U U = { r θ : θ ∈ Θ } \mathcal{U}=\{r_\theta:\theta \in \Theta\} U = { r θ : θ ∈ Θ } S shape ⊆ R d \mathcal{S}_{\text{shape}} \subseteq \mathbb{R}^d S shape ⊆ R d aff ( Θ ) \operatorname{aff}(\Theta) aff ( Θ ) Θ \Theta Θ Θ c o r e = { Proj ( θ ) : θ ∈ Θ } \Theta_{\mathrm{core}} =\{\text{Proj}(\theta):\theta\in \Theta\} Θ core = { Proj ( θ ) : θ ∈ Θ } dim ( Θ c o r e ) ≤ dim ( Θ ) − dim ( S shape ∩ aff ( Θ ) ) . \dim(\Theta_{\mathrm{core}})
\;\le\;
\dim(\Theta) - \dim\bigl(\mathcal{S}_{\text{shape}} \cap \operatorname{aff}(\Theta)\bigr). dim ( Θ core ) ≤ dim ( Θ ) − dim ( S shape ∩ aff ( Θ ) ) . S shape \mathcal{S}_{\text{shape}} S shape Θ \Theta Θ
Proof. Let A : = aff ( Θ ) A := \operatorname{aff}(\Theta) A := aff ( Θ ) Θ \Theta Θ k : = dim ( A ) = dim ( Θ ) , k := \dim(A) = \dim(\Theta), k := dim ( A ) = dim ( Θ ) , Θ \Theta Θ θ 0 ∈ Θ \theta_0 \in \Theta θ 0 ∈ Θ
V : = A − θ 0 = { θ − θ 0 : θ ∈ A } ⊆ R d . V := A - \theta_0
= \{ \theta - \theta_0 : \theta \in A \}
\subseteq \mathbb{R}^d. V := A − θ 0 = { θ − θ 0 : θ ∈ A } ⊆ R d . Then V V V k k k dim ( V ) = k . \dim(V) = k. dim ( V ) = k . S ′ : = S shape ∩ A . S' := \mathcal{S}_{\text{shape}} \cap A. S ′ := S shape ∩ A . V V V
S : = S ′ − θ 0 = S shape ∩ V . S := S' - \theta_0
= \mathcal{S}_{\text{shape}} \cap V. S := S ′ − θ 0 = S shape ∩ V . where dim ( S ) = dim ( S shape ∩ A ) . \dim(S) = \dim(\mathcal{S}_{\text{shape}} \cap A). dim ( S ) = dim ( S shape ∩ A ) . P r o j \mathrm{Proj} Proj V V V
T : V → R d , T ( v ) : = P r o j ( θ 0 + v ) − P r o j ( θ 0 ) . T : V \to \mathbb{R}^d, \qquad
T(v) := \mathrm{Proj}(\theta_0 + v) - \mathrm{Proj}(\theta_0). T : V → R d , T ( v ) := Proj ( θ 0 + v ) − Proj ( θ 0 ) . Intuitively, T T T P r o j \mathrm{Proj} Proj θ 0 \theta_0 θ 0 v ∈ V v \in V v ∈ V u ∈ S u \in S u ∈ S u ∈ S shape ∩ V u \in \mathcal{S}_{\text{shape}} \cap V u ∈ S shape ∩ V θ 0 + v + u ∈ A \theta_0 + v + u \in A θ 0 + v + u ∈ A u ∈ V u\in V u ∈ V u u u V V V v + u ∈ V v+u\in V v + u ∈ V θ 0 + ( v + u ) ∈ θ 0 + V = A \theta_0+(v+u)\in \theta_0+V=A θ 0 + ( v + u ) ∈ θ 0 + V = A V V V P r o j ( θ 0 + v + u ) = P r o j ( θ 0 + v ) . \mathrm{Proj}(\theta_0 + v + u) = \mathrm{Proj}(\theta_0 + v). Proj ( θ 0 + v + u ) = Proj ( θ 0 + v ) .
T ( v + u ) = P r o j ( θ 0 + v + u ) − P r o j ( θ 0 ) = P r o j ( θ 0 + v ) − P r o j ( θ 0 ) = T ( v ) . T(v+u)
= \mathrm{Proj}(\theta_0 + v + u) - \mathrm{Proj}(\theta_0)
= \mathrm{Proj}(\theta_0 + v) - \mathrm{Proj}(\theta_0)
= T(v). T ( v + u ) = Proj ( θ 0 + v + u ) − Proj ( θ 0 ) = Proj ( θ 0 + v ) − Proj ( θ 0 ) = T ( v ) . So T T T S S S S S S T T T T T T V / S V/S V / S C : V → V / S , C ( v ) : = [ v ] C: V\to V/S, C(v):=[v] C : V → V / S , C ( v ) := [ v ] v ∈ V v\in V v ∈ V [ v ] [v] [ v ] T ( v + u ) = T ( v ) T(v+u) = T(v) T ( v + u ) = T ( v ) u ∈ S u \in S u ∈ S v ′ ∼ v v' \sim v v ′ ∼ v v ′ = v + u , u ∈ S ⟹ T ( v ′ ) = T ( v ) . v' = v + u,\; u \in S
\;\;\Longrightarrow\;\;
T(v') = T(v). v ′ = v + u , u ∈ S ⟹ T ( v ′ ) = T ( v ) . T T T [ v ] [v] [ v ]
T ~ : V / S → R d , T ~ ( [ v ] ) : = T ( v ) . \tilde T : V/S \to \mathbb{R}^d, \qquad
\tilde T([v]) := T(v). T ~ : V / S → R d , T ~ ([ v ]) := T ( v ) . And we can write:
T = T ~ ∘ C , T = \tilde T \circ C, T = T ~ ∘ C , because for any v ∈ V v \in V v ∈ V
( T ~ ∘ C ) ( v ) = T ~ ( [ v ] ) = T ( v ) . (\tilde T \circ C)(v) = \tilde T([v]) = T(v). ( T ~ ∘ C ) ( v ) = T ~ ([ v ]) = T ( v ) . By construction, T ~ \tilde T T ~ T ( V ) T(V) T ( V )
Im ( T ~ ) = span ( T ( V ) ) . \operatorname{Im}(\tilde T) = \operatorname{span}(T(V)). Im ( T ~ ) = span ( T ( V )) . The dimension of the quotient space is
dim ( V / S ) = dim ( V ) − dim ( S ) = k − dim ( S shape ∩ A ) . \dim(V/S) = \dim(V) - \dim(S) = k - \dim(\mathcal{S}_{\text{shape}} \cap A). dim ( V / S ) = dim ( V ) − dim ( S ) = k − dim ( S shape ∩ A ) . Since T ~ \tilde T T ~ V / S V/S V / S R d \mathbb{R}^d R d
rank ( T ~ ) ≤ dim ( V / S ) = k − dim ( S shape ∩ A ) . \operatorname{rank}(\tilde T)
\;\le\;
\dim(V/S)
= k - \dim(\mathcal{S}_{\text{shape}} \cap A). rank ( T ~ ) ≤ dim ( V / S ) = k − dim ( S shape ∩ A ) . And notice that rank ( T ~ ) = dim ( Im ( T ~ ) ) = dim ( span ( T ( V ) ) ) \operatorname{rank}(\tilde T) = \dim(\operatorname{Im}(\tilde T))
= \dim(\operatorname{span}(T(V))) rank ( T ~ ) = dim ( Im ( T ~ )) = dim ( span ( T ( V ))) Θ core = { P r o j ( θ ) : θ ∈ Θ } . \Theta_{\text{core}} = \{\mathrm{Proj}(\theta) : \theta \in \Theta\}. Θ core = { Proj ( θ ) : θ ∈ Θ } . θ ∈ Θ \theta \in \Theta θ ∈ Θ θ = θ 0 + v \theta = \theta_0 + v θ = θ 0 + v v ∈ V v \in V v ∈ V
P r o j ( θ ) = P r o j ( θ 0 + v ) = P r o j ( θ 0 ) + T ( v ) . \mathrm{Proj}(\theta)
= \mathrm{Proj}(\theta_0 + v)
= \mathrm{Proj}(\theta_0) + T(v). Proj ( θ ) = Proj ( θ 0 + v ) = Proj ( θ 0 ) + T ( v ) . Therefore
Θ core ⊆ P r o j ( θ 0 ) + T ( V ) , \Theta_{\text{core}} \subseteq \mathrm{Proj}(\theta_0) + T(V), Θ core ⊆ Proj ( θ 0 ) + T ( V ) , and consequently,
aff ( Θ core ) ⊆ P r o j ( θ 0 ) + span ( T ( V ) ) . \operatorname{aff}(\Theta_{\text{core}})
\subseteq
\mathrm{Proj}(\theta_0) + \operatorname{span}(T(V)). aff ( Θ core ) ⊆ Proj ( θ 0 ) + span ( T ( V )) . Thus the affine dimension of Θ core \Theta_{\text{core}} Θ core
dim ( Θ core ) = dim ( aff ( Θ core ) ) ≤ dim ( span ( T ( V ) ) ) = rank ( T ~ ) ≤ k − dim ( S shape ∩ A ) . \dim(\Theta_{\text{core}})
= \dim\bigl(\operatorname{aff}(\Theta_{\text{core}})\bigr)
\le
\dim\bigl(\operatorname{span}(T(V))\bigr)
= \operatorname{rank}(\tilde T)
\le
k - \dim(\mathcal{S}_{\text{shape}} \cap A). dim ( Θ core ) = dim ( aff ( Θ core ) ) ≤ dim ( span ( T ( V )) ) = rank ( T ~ ) ≤ k − dim ( S shape ∩ A ) . Recall k = dim ( A ) = dim ( Θ ) k = \dim(A) = \dim(\Theta) k = dim ( A ) = dim ( Θ )
dim ( Θ c o r e ) ≤ dim ( Θ ) − dim ( S shape ∩ aff ( Θ ) ) . \dim(\Theta_{\mathrm{core}})
\;\le\;
\dim(\Theta) - \dim\bigl(\mathcal{S}_{\text{shape}} \cap \operatorname{aff}(\Theta)\bigr). dim ( Θ core ) ≤ dim ( Θ ) − dim ( S shape ∩ aff ( Θ ) ) . which completes the proof. If S shape ∩ aff ( Θ ) \mathcal{S}_{\text{shape}} \cap \operatorname{aff}(\Theta) S shape ∩ aff ( Θ )
dim ( S shape ∩ aff ( Θ ) ) > 0 , \dim\bigl(\mathcal{S}_{\text{shape}} \cap \operatorname{aff}(\Theta)\bigr) > 0, dim ( S shape ∩ aff ( Θ ) ) > 0 , so
dim ( Θ core ) ≤ dim ( Θ ) − dim ( S shape ∩ aff ( Θ ) ) ⏟ > 0 < dim ( Θ ) , \dim(\Theta_{\text{core}})
\;\le\;
\dim(\Theta)
-
\underbrace{\dim\bigl(\mathcal{S}_{\text{shape}} \cap \operatorname{aff}(\Theta)\bigr)}_{>0}
\;<\;
\dim(\Theta), dim ( Θ core ) ≤ dim ( Θ ) − > 0 dim ( S shape ∩ aff ( Θ ) ) < dim ( Θ ) , i.e., the affine dimension of the projected ambiguity set is strictly smaller than that of the original ambiguity set. ◻
In general, replacing U \mathcal{U} U U core \mathcal{U}_{\text{core}} U core U \mathcal{U} U Figure 1 is a concrete illustration: here dim ( U ) = 2 \dim(\mathcal{U})=2 dim ( U ) = 2 S shape = s p a n { ( 1 , 1 ) } \mathcal{S}_{\text{shape}}=\mathrm{span}\{(1,1)\} S shape = span {( 1 , 1 )} 1 1 1 U core \mathcal{U}_{\text{core}} U core U \mathcal{U} U U core \mathcal{U}_{\text{core}} U core
Proposition C.2. Consider a discounted multi-armed bandit with a single state s s s A \mathcal{A} A R = R A \mathcal{R}=\mathbb{R}^{\mathcal{A}} R = R A S s h a p e \mathcal{S}_{\mathrm{shape}} S shape R c o r e = R / S s h a p e \mathcal{R}_{\mathrm{core}}=\mathcal{R}/\mathcal{S}_{\mathrm{shape}} R core = R / S shape ∣ A ∣ − 1 |\mathcal{A}|-1 ∣ A ∣ − 1
Proof. PBRS shaping is
F ( s , a , s ′ ) = γ Φ ( s ′ ) − Φ ( s ) . F(s,a,s') \;=\; \gamma \Phi(s') - \Phi(s). F ( s , a , s ′ ) = γ Φ ( s ′ ) − Φ ( s ) . For multi-armed bandit MPD, there is only one state, so s ′ = s s' = s s ′ = s
F ( s , a , s ) = γ Φ ( s ) − Φ ( s ) = ( γ − 1 ) Φ ( s ) = : F F(s,a,s) \;=\; \gamma \Phi(s) - \Phi(s)
\;=\; (\gamma - 1)\Phi(s)
\;=:\; F F ( s , a , s ) = γ Φ ( s ) − Φ ( s ) = ( γ − 1 ) Φ ( s ) =: F is a constant independent of the action. Thus, shaping can only add the same constant F F F r , r ′ ∈ R ∣ A ∣ r, r' \in \mathbb{R}^{|\mathcal{A}|} r , r ′ ∈ R ∣ A ∣
r ′ = r + F ⋅ 1 , r' \;=\; r + F \cdot \mathbf{1}, r ′ = r + F ⋅ 1 , i.e., they differ by the all-ones direction. Then the shaping subspace is
S shape = { F ⋅ 1 : F ∈ R } = span { 1 } , \mathcal{S}_{\text{shape}}
\;=\;
\{ F\cdot \mathbf{1} : F \in \mathbb{R} \}
\;=\;
\operatorname{span}\{\mathbf{1}\}, S shape = { F ⋅ 1 : F ∈ R } = span { 1 } , which has dimension 1 1 1
dim ( R / S shape ) = ∣ A ∣ − 1. \dim\bigl(\mathcal{R} / \mathcal{S}_{\text{shape}}\bigr)
\;=\;
|\mathcal{A}| - 1. dim ( R / S shape ) = ∣ A ∣ − 1. This completes the proof. ◻
Additional Properties of Shaping-aware Projected Uncertainty Set
In this section, we propose additional properties of the projected uncertainty set.
Proposition C.3. Let U ⊆ R \mathcal{U} \subseteq \mathcal{R} U ⊆ R U core : = P r o j ( U ) = { P r o j ( r ) : r ∈ U } \mathcal{U}_{\text{core}} := \mathrm{Proj}(\mathcal{U})=\{\mathrm{Proj}(r): r\in \mathcal{U}\} U core := Proj ( U ) = { Proj ( r ) : r ∈ U } P r o j : R → R \mathrm{Proj}:\mathcal{R}\to\mathcal{R} Proj : R → R U core \mathcal{U}_{\text{core}} U core
Proof. Since P r o j \mathrm{Proj} Proj U core \mathcal{U}_{\text{core}} U core
Proposition C.4. Let U ⊆ R \mathcal{U} \subseteq \mathcal{R} U ⊆ R U core : = P r o j ( U ) = { P r o j ( r ) : r ∈ U } \mathcal{U}_{\text{core}} := \mathrm{Proj}(\mathcal{U})=\{\mathrm{Proj}(r): r\in \mathcal{U}\} U core := Proj ( U ) = { Proj ( r ) : r ∈ U } P r o j : R → R \mathrm{Proj}:\mathcal{R}\to\mathcal{R} Proj : R → R r 1 , r 2 ∈ R r_1,r_2\in\mathcal{R} r 1 , r 2 ∈ R λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] P r o j ( ( 1 − λ ) r 1 + λ r 2 ) = ( 1 − λ ) P r o j ( r 1 ) + λ P r o j ( r 2 ) , \mathrm{Proj}((1-\lambda)r_1+\lambda r_2)
=(1-\lambda)\mathrm{Proj}(r_1)+\lambda\,\mathrm{Proj}(r_2), Proj (( 1 − λ ) r 1 + λ r 2 ) = ( 1 − λ ) Proj ( r 1 ) + λ Proj ( r 2 ) , U core \mathcal{U}_{\text{core}} U core
Proof. Take any u 1 ′ , u 2 ′ ∈ U core u'_1,u'_2\in \mathcal{U}_{\text{core}} u 1 ′ , u 2 ′ ∈ U core u 1 , u 2 ∈ U u_1,u_2\in \mathcal{U} u 1 , u 2 ∈ U u i ′ = P r o j ( u i ) u'_i=\mathrm{Proj}(u_i) u i ′ = Proj ( u i ) i ∈ { 1 , 2 } i\in\{1,2\} i ∈ { 1 , 2 } λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] U \mathcal{U} U ( 1 − λ ) u 1 + λ u 2 ∈ U (1-\lambda)u_1+\lambda u_2\in \mathcal{U} ( 1 − λ ) u 1 + λ u 2 ∈ U P r o j \mathrm{Proj} Proj
( 1 − λ ) u 1 ′ + λ u 2 ′ = ( 1 − λ ) P r o j ( u 1 ) + λ P r o j ( u 2 ) = P r o j ( ( 1 − λ ) u 1 + λ u 2 ) ∈ U core . (1-\lambda)u'_1+\lambda u'_2
=(1-\lambda)\mathrm{Proj}(u_1)+\lambda\mathrm{Proj}(u_2)
=\mathrm{Proj}((1-\lambda)u_1+\lambda u_2)\in \mathcal{U}_{\text{core}}. ( 1 − λ ) u 1 ′ + λ u 2 ′ = ( 1 − λ ) Proj ( u 1 ) + λ Proj ( u 2 ) = Proj (( 1 − λ ) u 1 + λ u 2 ) ∈ U core . Thus U core \mathcal{U}_{\text{core}} U core
Proof of Theorem 4.1
To prove Theorem 4.1 , we first recall a standard connection between regularization and robustness with penalty. The statement below is adapted from Theorem 1 of [14 ] to match our notation.
Theorem C.5. Let Ω \Omega Ω Ω ∗ \Omega^* Ω ∗ π \pi π J ( π , r ) − Ω ( π ) = min r ~ ∈ R X ′ { J ( π , r ~ ) + Ω ∗ ( r − r ~ ) } . J(\pi,r) - \Omega(\pi)
=
\min_{\tilde r \in \mathbb{R}^{\mathcal{X'}}}
\Bigl\{
J(\pi,\tilde r) + \Omega^*(r-\tilde r)
\Bigr\}. J ( π , r ) − Ω ( π ) = min r ~ ∈ R X ′ { J ( π , r ~ ) + Ω ∗ ( r − r ~ ) } .
Proof. (Sketch) The key part of the proof is to rewrite Ω \Omega Ω − Ω -\Omega − Ω Ω \Omega Ω [14 ] . ◻
We now turn to budgeted uncertainty sets. For ϵ ≥ 0 \epsilon\ge 0 ϵ ≥ 0 λ > 0 \lambda>0 λ > 0
U : = { r ~ ∈ R X ′ : Ω ∗ ( r − r ~ λ ) ≤ ϵ } . \mathcal{U}
:=\Bigl\{\tilde r \in \mathbb{R}^{\mathcal{X'}}:\;
\Omega^*\!\left(\frac{r-\tilde r}{\lambda}\right)\le \epsilon
\Bigr\}. U := { r ~ ∈ R X ′ : Ω ∗ ( λ r − r ~ ) ≤ ϵ } . Theorem C.6. Fix any policy π \pi π ϵ ≥ 0 \epsilon \ge 0 ϵ ≥ 0 λ > 0 \lambda > 0 λ > 0 min r ~ ∈ U J ( π , r ~ ) ≥ J ( π , r ) − λ Ω ( π ) − λ ϵ . \min_{\tilde r\in\mathcal U}J(\pi,\tilde r)
\ge
J(\pi,r)-\lambda\Omega(\pi)-\lambda\epsilon. min r ~ ∈ U J ( π , r ~ ) ≥ J ( π , r ) − λ Ω ( π ) − λ ϵ .
Proof. Consider the inner problem
min r ~ ∈ U J ( π , r ~ ) . \min_{\tilde r\in\mathcal U}J(\pi,\tilde r). r ~ ∈ U min J ( π , r ~ ) . For every feasible r ~ ∈ U \tilde r\in\mathcal U r ~ ∈ U
Ω ∗ ( r − r ~ λ ) ≤ ϵ . \Omega^*\left(\frac{r-\tilde r}{\lambda}\right)\le \epsilon. Ω ∗ ( λ r − r ~ ) ≤ ϵ . Therefore,
λ Ω ∗ ( r − r ~ λ ) − λ ϵ ≤ 0. \lambda\Omega^*\left(\frac{r-\tilde r}{\lambda}\right)-\lambda\epsilon
\le 0. λ Ω ∗ ( λ r − r ~ ) − λ ϵ ≤ 0. Hence, for every r ~ ∈ U \tilde r\in\mathcal U r ~ ∈ U
J ( π , r ~ ) ≥ J ( π , r ~ ) + λ Ω ∗ ( r − r ~ λ ) − λ ϵ . J(\pi,\tilde r)
\ge
J(\pi,\tilde r)
+
\lambda\Omega^*\left(\frac{r-\tilde r}{\lambda}\right)
-
\lambda\epsilon. J ( π , r ~ ) ≥ J ( π , r ~ ) + λ Ω ∗ ( λ r − r ~ ) − λ ϵ . Taking the minimum over r ~ ∈ U \tilde r\in\mathcal U r ~ ∈ U
min r ~ ∈ U J ( π , r ~ ) ≥ min r ~ ∈ U { J ( π , r ~ ) + λ Ω ∗ ( r − r ~ λ ) − λ ϵ } . \min_{\tilde r\in\mathcal U}J(\pi,\tilde r)
\ge
\min_{\tilde r\in\mathcal U}
\left\{
J(\pi,\tilde r)
+
\lambda\Omega^*\left(\frac{r-\tilde r}{\lambda}\right)
-
\lambda\epsilon
\right\}. r ~ ∈ U min J ( π , r ~ ) ≥ r ~ ∈ U min { J ( π , r ~ ) + λ Ω ∗ ( λ r − r ~ ) − λ ϵ } . Since minimizing over the feasible set is no smaller than minimizing over the entire reward space, we further have
min r ~ ∈ U { J ( π , r ~ ) + λ Ω ∗ ( r − r ~ λ ) − λ ϵ } ≥ min r ~ ∈ R X ′ { J ( π , r ~ ) + λ Ω ∗ ( r − r ~ λ ) − λ ϵ } . \min_{\tilde r\in\mathcal U}
\left\{
J(\pi,\tilde r)
+
\lambda\Omega^*\left(\frac{r-\tilde r}{\lambda}\right)
-
\lambda\epsilon
\right\}
\ge
\min_{\tilde r\in\mathbb R^{\mathcal X'}}
\left\{
J(\pi,\tilde r)
+
\lambda\Omega^*\left(\frac{r-\tilde r}{\lambda}\right)
-
\lambda\epsilon
\right\}. r ~ ∈ U min { J ( π , r ~ ) + λ Ω ∗ ( λ r − r ~ ) − λ ϵ } ≥ r ~ ∈ R X ′ min { J ( π , r ~ ) + λ Ω ∗ ( λ r − r ~ ) − λ ϵ } . By the scaling property of convex conjugates [10 , 11 , 48 ] , for any λ > 0 \lambda>0 λ > 0 λ Ω \lambda\Omega λ Ω
( λ Ω ) ∗ ( y ) = λ Ω ∗ ( y λ ) . (\lambda\Omega)^*(y)
=
\lambda\Omega^*\left(\frac{y}{\lambda}\right). ( λ Ω ) ∗ ( y ) = λ Ω ∗ ( λ y ) . Applying Theorem C.5 to the scaled regularizer λ Ω \lambda\Omega λ Ω
J ( π , r ) − λ Ω ( π ) = min r ~ ∈ R X ′ { J ( π , r ~ ) + ( λ Ω ) ∗ ( r − r ~ ) } . J(\pi,r)-\lambda\Omega(\pi)
=
\min_{\tilde r\in\mathbb R^{\mathcal X'}}
\left\{
J(\pi,\tilde r)
+
(\lambda\Omega)^*(r-\tilde r)
\right\}. J ( π , r ) − λ Ω ( π ) = r ~ ∈ R X ′ min { J ( π , r ~ ) + ( λ Ω ) ∗ ( r − r ~ ) } . Using the scaling property, this becomes
J ( π , r ) − λ Ω ( π ) = min r ~ ∈ R X ′ { J ( π , r ~ ) + λ Ω ∗ ( r − r ~ λ ) } . J(\pi,r)-\lambda\Omega(\pi)
=
\min_{\tilde r\in\mathbb R^{\mathcal X'}}
\left\{
J(\pi,\tilde r)
+
\lambda\Omega^*\left(\frac{r-\tilde r}{\lambda}\right)
\right\}. J ( π , r ) − λ Ω ( π ) = r ~ ∈ R X ′ min { J ( π , r ~ ) + λ Ω ∗ ( λ r − r ~ ) } . Therefore,
min r ~ ∈ R X ′ { J ( π , r ~ ) + λ Ω ∗ ( r − r ~ λ ) − λ ϵ } = J ( π , r ) − λ Ω ( π ) − λ ϵ . \begin{aligned}
&\min_{\tilde r\in\mathbb R^{\mathcal X'}}
\left\{
J(\pi,\tilde r)
+
\lambda\Omega^*\left(\frac{r-\tilde r}{\lambda}\right)
-
\lambda\epsilon
\right\} =
J(\pi,r)-\lambda\Omega(\pi)-\lambda\epsilon.
\end{aligned} r ~ ∈ R X ′ min { J ( π , r ~ ) + λ Ω ∗ ( λ r − r ~ ) − λ ϵ } = J ( π , r ) − λ Ω ( π ) − λ ϵ . Combining this with the previous inequalities yields
min r ~ ∈ U J ( π , r ~ ) ≥ J ( π , r ) − λ Ω ( π ) − λ ϵ . \min_{\tilde r\in\mathcal U}J(\pi,\tilde r)
\ge
J(\pi,r)-\lambda\Omega(\pi)-\lambda\epsilon. r ~ ∈ U min J ( π , r ~ ) ≥ J ( π , r ) − λ Ω ( π ) − λ ϵ . This completes the proof. ◻
Theorem 4.1 holds because the inequality above is agnostic to the particular reward domain. It only requires that the inner problem optimizes over an uncertainty set defined through Ω ∗ \Omega^* Ω ∗ P r o j \mathrm{Proj} Proj P r o j ( r + F Φ ) = P r o j ( r ) \mathrm{Proj}(r+F_\Phi)=\mathrm{Proj}(r) Proj ( r + F Φ ) = Proj ( r ) U c o r e = P r o j ( U ) \mathcal{U}_{\mathrm{core}}=\mathrm{Proj}(\mathcal{U}) U core = Proj ( U ) U c o r e \mathcal{U}_{\mathrm{core}} U core π \pi π 3.3 gives
min r ~ c o r e ∈ U c o r e J ( π , r ~ c o r e ) = min r ~ ∈ U J ( π , r ~ ) . \min_{\tilde r_{\mathrm{core}}\in\mathcal U_{\mathrm{core}}}
J(\pi,\tilde r_{\mathrm{core}})
=
\min_{\tilde r\in\mathcal U}
J(\pi,\tilde r). r ~ core ∈ U core min J ( π , r ~ core ) = r ~ ∈ U min J ( π , r ~ ) . Moreover, Lemma 3.1 shows
J ( π , r c o r e ) = J ( π , r ) . J(\pi,r_{\mathrm{core}})=J(\pi,r). J ( π , r core ) = J ( π , r ) . Applying Theorem C.6 to the right-hand side yields
min r ~ c o r e ∈ U c o r e J ( π , r ~ c o r e ) = min r ~ ∈ U J ( π , r ~ ) ≥ J ( π , r ) − λ Ω ( π ) − λ ϵ . \min_{\tilde r_{\mathrm{core}}\in\mathcal U_{\mathrm{core}}}
J(\pi,\tilde r_{\mathrm{core}})=\min_{\tilde r\in\mathcal U}
J(\pi,\tilde r)
\ge
J(\pi,r)-\lambda\Omega(\pi)-\lambda\epsilon. r ~ core ∈ U core min J ( π , r ~ core ) = r ~ ∈ U min J ( π , r ~ ) ≥ J ( π , r ) − λ Ω ( π ) − λ ϵ . Using J ( π , r ) = J ( π , r c o r e ) J(\pi,r)=J(\pi,r_{\mathrm{core}}) J ( π , r ) = J ( π , r core )
min r ~ c o r e ∈ U c o r e J ( π , r ~ c o r e ) ≥ J ( π , r c o r e ) − λ Ω ( π ) − λ ϵ . \min_{\tilde r_{\mathrm{core}}\in\mathcal U_{\mathrm{core}}}
J(\pi,\tilde r_{\mathrm{core}})
\ge
J(\pi,r_{\mathrm{core}})-\lambda\Omega(\pi)-\lambda\epsilon. r ~ core ∈ U core min J ( π , r ~ core ) ≥ J ( π , r core ) − λ Ω ( π ) − λ ϵ . Finally, taking the maximum over π \pi π
max π min r ~ c o r e ∈ U c o r e J ( π , r ~ c o r e ) ≥ max π [ J ( π , r c o r e ) − λ Ω ( π ) ] − λ ϵ . \max_{\pi}
\min_{\tilde r_{\mathrm{core}}\in\mathcal U_{\mathrm{core}}}
J(\pi,\tilde r_{\mathrm{core}})
\ge
\max_{\pi}
\left[
J(\pi,r_{\mathrm{core}})-\lambda\Omega(\pi)
\right]
-\lambda\epsilon. π max r ~ core ∈ U core min J ( π , r ~ core ) ≥ π max [ J ( π , r core ) − λ Ω ( π ) ] − λ ϵ . This completes the proof.
Proof of Theorem 4.2
Proof. Following a similar idea used in the proof of Theorem 4.1 , it suffices to prove the result for the unprojected uncertainty set and then replace U \mathcal U U U c o r e \mathcal{U_{\mathrm{core}}} U core r r r r c o r e r_{\mathrm{core}} r core
Fix a policy π \pi π
u = r − r ~ λ . u=\frac{r-\tilde r}{\lambda}. u = λ r − r ~ . Then r ~ = r − λ u \tilde r=r-\lambda u r ~ = r − λ u Ω ∗ ( ( r − r ~ ) / λ ) ≤ ϵ / λ \Omega^*((r-\tilde r)/\lambda)\le \epsilon/\lambda Ω ∗ (( r − r ~ ) / λ ) ≤ ϵ / λ
Ω ∗ ( u ) ≤ ϵ λ . \Omega^*(u)\le \frac{\epsilon}{\lambda}. Ω ∗ ( u ) ≤ λ ϵ . Therefore,
min r ~ ∈ U J ( π , r ~ ) = min u : Ω ∗ ( u ) ≤ ϵ / λ J ( π , r − λ u ) = J ( π , r ) − λ sup u : Ω ∗ ( u ) ≤ ϵ / λ E [ ∑ t γ t u ( s t , a t ) ∣ μ 0 , π , P ] . \begin{aligned}
\min_{\tilde r\in\mathcal U}J(\pi,\tilde r)
&=
\min_{u:\Omega^*(u)\le \epsilon/\lambda}
J(\pi,r-\lambda u)\\
&=
J(\pi,r)
-
\lambda
\sup_{u:\Omega^*(u)\le \epsilon/\lambda}
\mathbb E\!\left[
\sum_t\gamma^t u(s_t,a_t)
\Bigm|\mu_0,\pi,P
\right].
\end{aligned} r ~ ∈ U min J ( π , r ~ ) = u : Ω ∗ ( u ) ≤ ϵ / λ min J ( π , r − λ u ) = J ( π , r ) − λ u : Ω ∗ ( u ) ≤ ϵ / λ sup E [ t ∑ γ t u ( s t , a t ) μ 0 , π , P ] . Define
d π ( s , a ) : = E [ ∑ t = 0 ∞ γ t 1 { s t = s , a t = a } ∣ μ 0 , π , P ] , d π ( s ) : = ∑ a d π ( s , a ) . d_\pi(s,a)
:=
\mathbb E\!\left[
\sum_{t=0}^{\infty}\gamma^t
\mathbf 1\{s_t=s,a_t=a\}
\Bigm|\mu_0,\pi,P
\right],
\qquad
d_\pi(s):=\sum_a d_\pi(s,a). d π ( s , a ) := E [ t = 0 ∑ ∞ γ t 1 { s t = s , a t = a } μ 0 , π , P ] , d π ( s ) := a ∑ d π ( s , a ) . Then
d π ( s , a ) = d π ( s ) π ( a ∣ s ) , d_\pi(s,a)=d_\pi(s)\pi(a|s), d π ( s , a ) = d π ( s ) π ( a ∣ s ) , and the objective in the inner maximization can be written as
E [ ∑ t γ t u ( s t , a t ) ∣ μ 0 , π , P ] = ∑ s ∑ a d π ( s , a ) u ( s , a ) . \mathbb E\!\left[
\sum_t\gamma^t u(s_t,a_t)
\Bigm|\mu_0,\pi,P
\right]
=
\sum_s\sum_a d_\pi(s,a)u(s,a). E [ t ∑ γ t u ( s t , a t ) μ 0 , π , P ] = s ∑ a ∑ d π ( s , a ) u ( s , a ) . For the entropy-based uncertainty set,
Ω ∗ ( u ) = E [ ∑ t γ t log ∑ a exp ( u ( s t , a t ) ) ∣ μ 0 , π , P ] , \Omega^*(u)= \mathbb{E}\left[
\sum_{t} \gamma^{t}
\log \sum_{a }
\exp(u(s_t,a_t))\Big| \mu_0, \pi, P \right], Ω ∗ ( u ) = E [ t ∑ γ t log a ∑ exp ( u ( s t , a t )) μ 0 , π , P ] , Equivalently,
Ω ∗ ( u ) = ∑ s d π ( s ) log ∑ a exp ( u ( s , a ) ) . \Omega^*(u)
=
\sum_s d_\pi(s)\log\sum_a \exp(u(s,a)). Ω ∗ ( u ) = s ∑ d π ( s ) log a ∑ exp ( u ( s , a )) . Therefore, the constrained maximization is
sup u : Ω ∗ ( u ) ≤ ϵ / λ ∑ s ∑ a d π ( s , a ) u ( s , a ) . \sup_{u:\Omega^*(u)\le \epsilon/\lambda}
\sum_s\sum_a d_\pi(s,a)u(s,a). u : Ω ∗ ( u ) ≤ ϵ / λ sup s ∑ a ∑ d π ( s , a ) u ( s , a ) . Equivalently, we minimize the negative objective:
min u − ∑ s ∑ a d π ( s , a ) u ( s , a ) s.t. Ω ∗ ( u ) ≤ ϵ λ . \min_u
-\sum_s\sum_a d_\pi(s,a)u(s,a)
\quad
\text{s.t.}
\quad
\Omega^*(u)\le \frac{\epsilon}{\lambda}. u min − s ∑ a ∑ d π ( s , a ) u ( s , a ) s.t. Ω ∗ ( u ) ≤ λ ϵ . The Lagrangian is
L ( u , η ) = − ∑ s ∑ a d π ( s , a ) u ( s , a ) + η ( ∑ s d π ( s ) log ∑ a exp ( u ( s , a ) ) − ϵ λ ) . \mathcal L(u,\eta)
=
-\sum_s\sum_a d_\pi(s,a)u(s,a)
+
\eta\left(
\sum_s d_\pi(s)\log\sum_a \exp(u(s,a))
-
\frac{\epsilon}{\lambda}
\right). L ( u , η ) = − s ∑ a ∑ d π ( s , a ) u ( s , a ) + η ( s ∑ d π ( s ) log a ∑ exp ( u ( s , a )) − λ ϵ ) . The KKT conditions are
∑ s d π ( s ) log ∑ a exp ( u ( s , a ) ) ≤ ϵ λ , \sum_s d_\pi(s)\log\sum_a \exp(u(s,a))
\le \frac{\epsilon}{\lambda}, s ∑ d π ( s ) log a ∑ exp ( u ( s , a )) ≤ λ ϵ , η ( ∑ s d π ( s ) log ∑ a exp ( u ( s , a ) ) − ϵ λ ) = 0 , \eta\left(
\sum_s d_\pi(s)\log\sum_a \exp(u(s,a))
-
\frac{\epsilon}{\lambda}
\right)=0, η ( s ∑ d π ( s ) log a ∑ exp ( u ( s , a )) − λ ϵ ) = 0 , and, for every ( s , a ) (s,a) ( s , a )
∂ L ∂ u ( s , a ) = − d π ( s , a ) + η d π ( s ) exp ( u ( s , a ) ) ∑ a ′ exp ( u ( s , a ′ ) ) = 0. \frac{\partial \mathcal L}{\partial u(s,a)}
=
-d_\pi(s,a)
+
\eta d_\pi(s)
\frac{\exp(u(s,a))}{\sum_{a'}\exp(u(s,a'))}
=0. ∂ u ( s , a ) ∂ L = − d π ( s , a ) + η d π ( s ) ∑ a ′ exp ( u ( s , a ′ )) exp ( u ( s , a )) = 0. Using d π ( s , a ) = d π ( s ) π ( a ∣ s ) d_\pi(s,a)=d_\pi(s)\pi(a|s) d π ( s , a ) = d π ( s ) π ( a ∣ s )
− d π ( s ) π ( a ∣ s ) + η d π ( s ) exp ( u ( s , a ) ) ∑ a ′ exp ( u ( s , a ′ ) ) = 0. -d_\pi(s)\pi(a|s)
+
\eta d_\pi(s)
\frac{\exp(u(s,a))}{\sum_{a'}\exp(u(s,a'))}
=0. − d π ( s ) π ( a ∣ s ) + η d π ( s ) ∑ a ′ exp ( u ( s , a ′ )) exp ( u ( s , a )) = 0. For every visited state with d π ( s ) > 0 d_\pi(s)>0 d π ( s ) > 0 d π ( s ) d_\pi(s) d π ( s )
π ( a ∣ s ) = η exp ( u ( s , a ) ) ∑ a ′ exp ( u ( s , a ′ ) ) . \pi(a|s)
=
\eta
\frac{\exp(u(s,a))}{\sum_{a'}\exp(u(s,a'))}. π ( a ∣ s ) = η ∑ a ′ exp ( u ( s , a ′ )) exp ( u ( s , a )) . Summing both sides over a a a η = 1 \eta=1 η = 1
π ( a ∣ s ) = exp ( u ( s , a ) ) ∑ a ′ exp ( u ( s , a ′ ) ) . \pi(a|s)
=
\frac{\exp(u(s,a))}{\sum_{a'}\exp(u(s,a'))}. π ( a ∣ s ) = ∑ a ′ exp ( u ( s , a ′ )) exp ( u ( s , a )) . Equivalently,
u ( s , a ) = log π ( a ∣ s ) + c ( s ) , u(s,a)=\log\pi(a|s)+c(s), u ( s , a ) = log π ( a ∣ s ) + c ( s ) , where c ( s ) c(s) c ( s ) a a a u u u
Ω ∗ ( u ) < ϵ λ . \Omega^*(u)<\frac{\epsilon}{\lambda}. Ω ∗ ( u ) < λ ϵ . For any scalar c > 0 c>0 c > 0
u c ( s , a ) = u ( s , a ) + c . u_c(s,a)=u(s,a)+c . u c ( s , a ) = u ( s , a ) + c . Then
log ∑ a exp ( u c ( s , a ) ) = log ∑ a exp ( u ( s , a ) + c ) = c + log ∑ a exp ( u ( s , a ) ) . \log\sum_a \exp(u_c(s,a))
=
\log\sum_a \exp(u(s,a)+c)
=
c+\log\sum_a \exp(u(s,a)). log a ∑ exp ( u c ( s , a )) = log a ∑ exp ( u ( s , a ) + c ) = c + log a ∑ exp ( u ( s , a )) . Therefore,
Ω ∗ ( u c ) = Ω ∗ ( u ) + c ∑ s d π ( s ) . \Omega^*(u_c)
=
\Omega^*(u)
+
c\sum_s d_\pi(s). Ω ∗ ( u c ) = Ω ∗ ( u ) + c s ∑ d π ( s ) . For sufficiently small c > 0 c>0 c > 0
Ω ∗ ( u c ) ≤ ϵ λ . \Omega^*(u_c)\le \frac{\epsilon}{\lambda}. Ω ∗ ( u c ) ≤ λ ϵ . However, the objective strictly increases:
∑ s ∑ a d π ( s , a ) u c ( s , a ) = ∑ s ∑ a d π ( s , a ) u ( s , a ) + c ∑ s ∑ a d π ( s , a ) > ∑ s ∑ a d π ( s , a ) u ( s , a ) . \sum_s\sum_a d_\pi(s,a)u_c(s,a)
=
\sum_s\sum_a d_\pi(s,a)u(s,a)
+
c\sum_s\sum_a d_\pi(s,a)
>
\sum_s\sum_a d_\pi(s,a)u(s,a). s ∑ a ∑ d π ( s , a ) u c ( s , a ) = s ∑ a ∑ d π ( s , a ) u ( s , a ) + c s ∑ a ∑ d π ( s , a ) > s ∑ a ∑ d π ( s , a ) u ( s , a ) . This contradicts the optimality of u u u
Ω ∗ ( u ) = ϵ λ . \Omega^*(u)=\frac{\epsilon}{\lambda}. Ω ∗ ( u ) = λ ϵ . Substituting u ( s , a ) = log π ( a ∣ s ) + c ( s ) u(s,a)=\log\pi(a|s)+c(s) u ( s , a ) = log π ( a ∣ s ) + c ( s ) Ω ∗ ( u ) \Omega^*(u) Ω ∗ ( u )
∑ s d π ( s ) log ∑ a exp ( u ( s , a ) ) = ∑ s d π ( s ) log ∑ a exp ( log π ( a ∣ s ) + c ( s ) ) = ∑ s d π ( s ) c ( s ) , \sum_s d_\pi(s)\log\sum_a \exp(u(s,a))
=
\sum_s d_\pi(s)\log\sum_a \exp(\log\pi(a|s)+c(s))
=
\sum_s d_\pi(s)c(s), s ∑ d π ( s ) log a ∑ exp ( u ( s , a )) = s ∑ d π ( s ) log a ∑ exp ( log π ( a ∣ s ) + c ( s )) = s ∑ d π ( s ) c ( s ) , because ∑ a π ( a ∣ s ) = 1 \sum_a\pi(a|s)=1 ∑ a π ( a ∣ s ) = 1
∑ s d π ( s ) c ( s ) = ϵ λ . \sum_s d_\pi(s)c(s)
=
\frac{\epsilon}{\lambda}. s ∑ d π ( s ) c ( s ) = λ ϵ . Therefore,
sup u : Ω ∗ ( u ) ≤ ϵ / λ E [ ∑ t γ t u ( s t , a t ) ∣ μ 0 , π , P ] = ∑ s ∑ a d π ( s , a ) ( log π ( a ∣ s ) + c ( s ) ) = ∑ s d π ( s ) ∑ a π ( a ∣ s ) log π ( a ∣ s ) + ∑ s d π ( s ) c ( s ) = − Ω E n t ( π ) + ϵ λ . \begin{aligned}
&\sup_{u:\Omega^*(u)\le \epsilon/\lambda}
\mathbb E\!\left[
\sum_t\gamma^t u(s_t,a_t)
\Bigm|\mu_0,\pi,P
\right] \\
&=
\sum_s\sum_a d_\pi(s,a)
\bigl(\log\pi(a|s)+c(s)\bigr)\\
&=
\sum_s d_\pi(s)\sum_a\pi(a|s)\log\pi(a|s)
+
\sum_s d_\pi(s)c(s)\\
&=
-\Omega_{\mathrm{Ent}}(\pi)+\frac{\epsilon}{\lambda}.
\end{aligned} u : Ω ∗ ( u ) ≤ ϵ / λ sup E [ t ∑ γ t u ( s t , a t ) μ 0 , π , P ] = s ∑ a ∑ d π ( s , a ) ( log π ( a ∣ s ) + c ( s ) ) = s ∑ d π ( s ) a ∑ π ( a ∣ s ) log π ( a ∣ s ) + s ∑ d π ( s ) c ( s ) = − Ω Ent ( π ) + λ ϵ . For the KL-based uncertainty set, write
Ω ∗ ( u ) = ∑ s d π ( s ) log ∑ a π r e f ( a ∣ s ) exp ( u ( s , a ) ) . \Omega^*(u)
=
\sum_s d_\pi(s)
\log\sum_a \pi_{\mathrm{ref}}(a|s)\exp(u(s,a)). Ω ∗ ( u ) = s ∑ d π ( s ) log a ∑ π ref ( a ∣ s ) exp ( u ( s , a )) . The Lagrangian is
L ( u , η ) = − ∑ s ∑ a d π ( s , a ) u ( s , a ) + η ( ∑ s d π ( s ) log ∑ a π r e f ( a ∣ s ) exp ( u ( s , a ) ) − ϵ λ ) . \mathcal L(u,\eta)
=
-\sum_s\sum_a d_\pi(s,a)u(s,a)
+
\eta\left(
\sum_s d_\pi(s)
\log\sum_a \pi_{\mathrm{ref}}(a|s)\exp(u(s,a))
-
\frac{\epsilon}{\lambda}
\right). L ( u , η ) = − s ∑ a ∑ d π ( s , a ) u ( s , a ) + η ( s ∑ d π ( s ) log a ∑ π ref ( a ∣ s ) exp ( u ( s , a )) − λ ϵ ) . The stationarity condition is
− d π ( s , a ) + η d π ( s ) π r e f ( a ∣ s ) exp ( u ( s , a ) ) ∑ a ′ π r e f ( a ′ ∣ s ) exp ( u ( s , a ′ ) ) = 0. -d_\pi(s,a)
+
\eta d_\pi(s)
\frac{\pi_{\mathrm{ref}}(a|s)\exp(u(s,a))}
{\sum_{a'}\pi_{\mathrm{ref}}(a'|s)\exp(u(s,a'))}
=0. − d π ( s , a ) + η d π ( s ) ∑ a ′ π ref ( a ′ ∣ s ) exp ( u ( s , a ′ )) π ref ( a ∣ s ) exp ( u ( s , a )) = 0. Using d π ( s , a ) = d π ( s ) π ( a ∣ s ) d_\pi(s,a)=d_\pi(s)\pi(a|s) d π ( s , a ) = d π ( s ) π ( a ∣ s ) a a a η = 1 \eta=1 η = 1
π ( a ∣ s ) = π r e f ( a ∣ s ) exp ( u ( s , a ) ) ∑ a ′ π r e f ( a ′ ∣ s ) exp ( u ( s , a ′ ) ) . \pi(a|s)
=
\frac{\pi_{\mathrm{ref}}(a|s)\exp(u(s,a))}
{\sum_{a'}\pi_{\mathrm{ref}}(a'|s)\exp(u(s,a'))}. π ( a ∣ s ) = ∑ a ′ π ref ( a ′ ∣ s ) exp ( u ( s , a ′ )) π ref ( a ∣ s ) exp ( u ( s , a )) . Equivalently,
u ( s , a ) = log π ( a ∣ s ) π r e f ( a ∣ s ) + c ( s ) . u(s,a)
=
\log\frac{\pi(a|s)}{\pi_{\mathrm{ref}}(a|s)}
+
c(s). u ( s , a ) = log π ref ( a ∣ s ) π ( a ∣ s ) + c ( s ) . Since the constraint is active,
∑ s d π ( s ) c ( s ) = ϵ λ . \sum_s d_\pi(s)c(s)=\frac{\epsilon}{\lambda}. s ∑ d π ( s ) c ( s ) = λ ϵ . Thus
sup u : Ω ∗ ( u ) ≤ ϵ / λ E [ ∑ t γ t u ( s t , a t ) ∣ μ 0 , π , P ] = ∑ s d π ( s ) ∑ a π ( a ∣ s ) log π ( a ∣ s ) π r e f ( a ∣ s ) + ϵ λ = − Ω K L ( π ) + ϵ λ . \begin{aligned}
&\sup_{u:\Omega^*(u)\le \epsilon/\lambda}
\mathbb E\!\left[
\sum_t\gamma^t u(s_t,a_t)
\Bigm|\mu_0,\pi,P
\right]\\
&=
\sum_s d_\pi(s)
\sum_a\pi(a|s)
\log\frac{\pi(a|s)}{\pi_{\mathrm{ref}}(a|s)}
+
\frac{\epsilon}{\lambda}\\
&=
-\Omega_{\mathrm{KL}}(\pi)+\frac{\epsilon}{\lambda}.
\end{aligned} u : Ω ∗ ( u ) ≤ ϵ / λ sup E [ t ∑ γ t u ( s t , a t ) μ 0 , π , P ] = s ∑ d π ( s ) a ∑ π ( a ∣ s ) log π ref ( a ∣ s ) π ( a ∣ s ) + λ ϵ = − Ω KL ( π ) + λ ϵ . Substituting either identity into
min r ~ ∈ U J ( π , r ~ ) = J ( π , r ) − λ sup u : Ω ∗ ( u ) ≤ ϵ / λ E [ ∑ t γ t u ( s t , a t ) ∣ μ 0 , π , P ] \min_{\tilde r\in\mathcal U}J(\pi,\tilde r)
=
J(\pi,r)
-
\lambda
\sup_{u:\Omega^*(u)\le \epsilon/\lambda}
\mathbb E\!\left[
\sum_t\gamma^t u(s_t,a_t)
\Bigm|\mu_0,\pi,P
\right] r ~ ∈ U min J ( π , r ~ ) = J ( π , r ) − λ u : Ω ∗ ( u ) ≤ ϵ / λ sup E [ t ∑ γ t u ( s t , a t ) μ 0 , π , P ] gives
min r ~ ∈ U J ( π , r ~ ) = J ( π , r ) + λ Ω ( π ) − ϵ , \min_{\tilde r\in\mathcal U}J(\pi,\tilde r)
=
J(\pi,r)+\lambda\Omega(\pi)-\epsilon, r ~ ∈ U min J ( π , r ~ ) = J ( π , r ) + λ Ω ( π ) − ϵ , where Ω = Ω E n t \Omega=\Omega_{\mathrm{Ent}} Ω = Ω Ent Ω = Ω K L \Omega=\Omega_{\mathrm{KL}} Ω = Ω KL
Properties of Ω ∗ \Omega^* Ω ∗
Recall that we estimate the projection using
Proj ( r ) = arg min Φ Ω ∗ ( r ( s , a , s ′ ) − ( γ Φ ( s ′ ) − Φ ( s ) ) ) . \operatorname{Proj}(r)=\arg\min_{\Phi}
\Omega^*\Bigl(
r(s, a, s') - \bigl(\gamma \Phi(s') - \Phi(s)\bigr)
\Bigr). Proj ( r ) = arg Φ min Ω ∗ ( r ( s , a , s ′ ) − ( γ Φ ( s ′ ) − Φ ( s ) ) ) . Next, we establish conditions under which the projection is well-defined, i.e., the minimizer exists and is unique. We begin with a technical lemma that will be used in the proof.
Lemma C.7. S shape \mathcal{S}_{\text{shape}} S shape
Proof. Recall that PBRS shaping terms are of the form
F Φ ( s , a , s ′ ) = γ Φ ( s ′ ) − Φ ( s ) . F_{\Phi}(s,a,s') \;=\; \gamma \Phi(s') - \Phi(s). F Φ ( s , a , s ′ ) = γ Φ ( s ′ ) − Φ ( s ) . Then we define the shaping set as
S shape : = { F Φ : Φ ∈ R S } . S_{\text{shape}} := \{ F_{\Phi} : \Phi \in \mathbb{R}^{\mathcal{S}}\}. S shape := { F Φ : Φ ∈ R S } . Now take any Φ 1 , Φ 2 \Phi_1, \Phi_2 Φ 1 , Φ 2 a , b a,b a , b Φ ↦ F Φ \Phi \mapsto F_{\Phi} Φ ↦ F Φ
F a Φ 1 + b Φ 2 ( s , a , s ′ ) = γ ( a Φ 1 + b Φ 2 ) ( s ′ ) − ( a Φ 1 + b Φ 2 ) ( s ) = a F Φ 1 ( s , a , s ′ ) + b F Φ 2 ( s , a , s ′ ) . F_{a\Phi_1 + b\Phi_2}(s,a,s')
= \gamma (a\Phi_1 + b\Phi_2)(s') - (a\Phi_1 + b\Phi_2)(s)
= a F_{\Phi_1}(s,a,s') + b F_{\Phi_2}(s,a,s'). F a Φ 1 + b Φ 2 ( s , a , s ′ ) = γ ( a Φ 1 + b Φ 2 ) ( s ′ ) − ( a Φ 1 + b Φ 2 ) ( s ) = a F Φ 1 ( s , a , s ′ ) + b F Φ 2 ( s , a , s ′ ) . So:
F Φ 1 + F Φ 2 = F Φ 1 + Φ 2 ∈ S shape F_{\Phi_1} + F_{\Phi_2} = F_{\Phi_1 + \Phi_2} \in S_{\text{shape}} F Φ 1 + F Φ 2 = F Φ 1 + Φ 2 ∈ S shape
a F Φ 1 = F a Φ 1 ∈ S shape a F_{\Phi_1} = F_{a\Phi_1} \in S_{\text{shape}} a F Φ 1 = F a Φ 1 ∈ S shape
This completes the proof. ◻
Theorem C.8. Assume S \mathcal S S X ′ \mathcal X' X ′ Ω ∗ \Omega^* Ω ∗ [ r ] : = { r + F Φ : Φ ∈ R S } [r]:=\{r+F_{\Phi}:\Phi\in\mathbb R^{\mathcal S}\} [ r ] := { r + F Φ : Φ ∈ R S } r r r Ω ∗ \Omega^* Ω ∗ [ r ] [r] [ r ] c ∈ R c\in\mathbb R c ∈ R { r ′ ∈ [ r ] : Ω ∗ ( r ′ ) ≤ c } is bounded. \{\,r'\in [r]: \Omega^*(r')\le c\,\}
\quad \text{is bounded.} { r ′ ∈ [ r ] : Ω ∗ ( r ′ ) ≤ c } is bounded. min r ′ ∈ [ r ] Ω ∗ ( r ′ ) \min_{r'\in[r]} \Omega^*(r') min r ′ ∈ [ r ] Ω ∗ ( r ′ ) Proj ( r ) \operatorname{Proj}(r) Proj ( r )
If additionally Ω ∗ \Omega^* Ω ∗ Proj ( r ) \operatorname{Proj}(r) Proj ( r )
Proof. Since Ω ∗ \Omega^* Ω ∗ R X ′ \mathbb R^{\mathcal X'} R X ′ [ r ] = r + S s h a p e [r]=r+\mathcal S_{\mathrm{shape}} [ r ] = r + S shape r r r S s h a p e \mathcal S_{\mathrm{shape}} S shape C.7 . By the assumed level-boundedness on [ r ] [r] [ r ]
L c : = { r ′ ∈ [ r ] : Ω ∗ ( r ′ ) ≤ c } L_c := \{\,r'\in[r]: \Omega^*(r')\le c\,\} L c := { r ′ ∈ [ r ] : Ω ∗ ( r ′ ) ≤ c } is bounded. Since Ω ∗ \Omega^* Ω ∗ [ r ] [r] [ r ] L c L_c L c Ω ∗ \Omega^* Ω ∗ [ r ] [r] [ r ] L c L_c L c c c c arg min r ′ ∈ [ r ] Ω ∗ ( r ′ ) \arg\min_{r'\in[r]}\Omega^*(r') arg min r ′ ∈ [ r ] Ω ∗ ( r ′ )
If Ω ∗ \Omega^* Ω ∗ [ r ] [r] [ r ] [ r ] [r] [ r ] Proj ( r ) \operatorname{Proj}(r) Proj ( r )
Beyond the conceptual motivation in the main paper, namely that the Ω ∗ \Omega^* Ω ∗ [16 , 17 , 18 ] . For these methods, iteration complexity typically depends on the size of the feasible set. In our setting, the projection selects, within each PBRS equivalence class, the representative that is smallest under the Ω ∗ \Omega^* Ω ∗ Ω ∗ \Omega^* Ω ∗ Ω ∗ \Omega^* Ω ∗
Proposition C.9. Assume Ω ∗ : R → R \Omega^*:\mathcal R\to\mathbb R Ω ∗ : R → R R a d Ω ∗ ( U ) : = sup r ∈ U Ω ∗ ( r ) \mathrm{Rad}_{\Omega^*}(\mathcal U):=\sup_{r\in\mathcal U}\ \Omega^*(r) Rad Ω ∗ ( U ) := sup r ∈ U Ω ∗ ( r ) U ⊆ R \mathcal U\subseteq\mathcal R U ⊆ R R a d Ω ∗ ( P r o j ( U ) ) ≤ R a d Ω ∗ ( U ) . \mathrm{Rad}_{\Omega^*}(\mathrm{Proj}(\mathcal U))
\;\le\;
\mathrm{Rad}_{\Omega^*}(\mathcal U). Rad Ω ∗ ( Proj ( U )) ≤ Rad Ω ∗ ( U ) .
Proof. Fix any r ∈ R r\in\mathcal R r ∈ R
P r o j ( r ) ∈ arg min Φ Ω ∗ ( r − ( γ Φ ( s ′ ) − Φ ( s ) ) ) . \mathrm{Proj}(r)\in\arg\min_{\Phi}\ \Omega^*\!\bigl(r-(\gamma\Phi(s')-\Phi(s))\bigr). Proj ( r ) ∈ arg Φ min Ω ∗ ( r − ( γ Φ ( s ′ ) − Φ ( s )) ) . Since Φ ≡ 0 \Phi\equiv 0 Φ ≡ 0 Ω ∗ ( P r o j ( r ) ) ≤ Ω ∗ ( r ) \Omega^*(\mathrm{Proj}(r))\le \Omega^*(r) Ω ∗ ( Proj ( r )) ≤ Ω ∗ ( r ) r ∈ U r\in\mathcal U r ∈ U
sup r ~ ∈ P r o j ( U ) Ω ∗ ( r ~ ) = sup r ∈ U Ω ∗ ( P r o j ( r ) ) ≤ sup r ∈ U Ω ∗ ( r ) . \sup_{\tilde r\in \mathrm{Proj}(\mathcal U)}\Omega^*(\tilde r)
=
\sup_{r\in\mathcal U}\Omega^*(\mathrm{Proj}(r))
\le
\sup_{r\in\mathcal U}\Omega^*(r). r ~ ∈ Proj ( U ) sup Ω ∗ ( r ~ ) = r ∈ U sup Ω ∗ ( Proj ( r )) ≤ r ∈ U sup Ω ∗ ( r ) . This completes the proof. ◻
Since standard mirror-descent bounds scale with a geometry-dependent size term of the feasible set (e.g., a Bregman radius under the mirror map), reducing R a d Ω ∗ \mathrm{Rad}_{\Omega^*} Rad Ω ∗ f f f K \mathcal K K Ψ \Psi Ψ ρ \rho ρ ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ ∥ g t ∥ ∗ ≤ L \|g_t\|_* \le L ∥ g t ∥ ∗ ≤ L [15 ] ) states that with a suitable step size,
f ( x ˉ t ) − f ( x ⋆ ) ≤ L 2 D ρ t , D : = sup x ∈ K D Ψ ( x , x 1 ) , f(\bar x_t)-f(x^\star)\ \le\ L\sqrt{\frac{2D}{\rho\,t}},
\qquad
D:=\sup_{x\in\mathcal K} D_{\Psi}(x,x_1), f ( x ˉ t ) − f ( x ⋆ ) ≤ L ρ t 2 D , D := x ∈ K sup D Ψ ( x , x 1 ) , where D Ψ D_{\Psi} D Ψ Ψ \Psi Ψ x 1 x_1 x 1 f ( x ˉ t ) − f ( x ⋆ ) ≤ δ f(\bar x_t)-f(x^\star)\le \delta f ( x ˉ t ) − f ( x ⋆ ) ≤ δ
t ≥ 2 L 2 ρ δ 2 D . t\ \ge\ \frac{2L^2}{\rho\,\delta^2}\,D . t ≥ ρ δ 2 2 L 2 D . In our setting, we take Ψ = Ω ∗ \Psi=\Omega^* Ψ = Ω ∗ Ω ∗ \Omega^* Ω ∗ ρ \rho ρ x 1 = 0 x_1=0 x 1 = 0 1
D = sup x ∈ K D Ω ∗ ( x , 0 ) = sup x ∈ K Ω ∗ ( x ) = : R a d Ω ∗ ( K ) . D \;=\; \sup_{x\in\mathcal K} D_{\Omega^*}(x,0)
\;=\; \sup_{x\in\mathcal K} \Omega^*(x)
\;=:\; \mathrm{Rad}_{\Omega^*}(\mathcal K). D = x ∈ K sup D Ω ∗ ( x , 0 ) = x ∈ K sup Ω ∗ ( x ) =: Rad Ω ∗ ( K ) . Therefore, the mirror-descent iteration complexity scales linearly with R a d Ω ∗ ( K ) \mathrm{Rad}_{\Omega^*}(\mathcal K) Rad Ω ∗ ( K )
t ( δ ) ≥ 2 L 2 ρ δ 2 R a d Ω ∗ ( K ) . t(\delta)\ \ge\ \frac{2L^2}{\rho\,\delta^2}\,\mathrm{Rad}_{\Omega^*}(\mathcal K). t ( δ ) ≥ ρ δ 2 2 L 2 Rad Ω ∗ ( K ) . As proved in Proposition C.9 , for any feasible set K ⊆ R \mathcal K \subseteq \mathcal R K ⊆ R Ω ∗ \Omega^* Ω ∗
R a d Ω ∗ ( Proj ( K ) ) ≤ R a d Ω ∗ ( K ) . \mathrm{Rad}_{\Omega^*}(\operatorname{Proj}(\mathcal K))
\;\le\;
\mathrm{Rad}_{\Omega^*}(\mathcal K). Rad Ω ∗ ( Proj ( K )) ≤ Rad Ω ∗ ( K ) . Combining with the bound above, optimizing the inner problem over the projected set tightens the worst-case mirror-descent complexity guarantee, implying that fewer inner-loop iterations suffice to reach a target accuracy.
Since the Ω ∗ \Omega^* Ω ∗ Ω ∗ \Omega^* Ω ∗ L 2 L^2 L 2 Φ φ \Phi_\varphi Φ φ
φ ∗ = arg min φ ( r ( s , a , s ′ ) − ( γ Φ φ ( s ′ ) − Φ φ ( s ) ) ) 2 . \varphi^{*}
= \arg\min_{\varphi}
\Bigl(
r(s, a, s') - \bigl(\gamma \Phi_{\varphi}(s') - \Phi_{\varphi}(s)\bigr)
\Bigr)^{2}. φ ∗ = arg φ min ( r ( s , a , s ′ ) − ( γ Φ φ ( s ′ ) − Φ φ ( s ) ) ) 2 . To further understand this, we will continue to use the simple MDP defined in Figure 1 as an example. Here, every transition from s 1 s_1 s 1 s 2 s_2 s 2 F F F F F F r 1 = r ( s 1 , a 1 , s 2 ) r_1 = r(s_1,a_1,s_2) r 1 = r ( s 1 , a 1 , s 2 ) r 2 = r ( s 1 , a 2 , s 2 ) r_2 = r(s_1,a_2,s_2) r 2 = r ( s 1 , a 2 , s 2 )
min F ( r 1 − F ) 2 + ( r 2 − F ) 2 . \min_{F} \ (r_1 - F)^2 + (r_2 - F)^2 . F min ( r 1 − F ) 2 + ( r 2 − F ) 2 . This has a unique solution
F ∗ = r 1 + r 2 2 . F^{\ast} = \frac{r_1 + r_2}{2}. F ∗ = 2 r 1 + r 2 . And then the projected rewards:
r 1 ′ = r 1 − F ∗ = r 1 − r 2 2 , r 2 ′ = r 2 − F ∗ = r 2 − r 1 2 , r_1' = r_1 - F^{\ast} = \frac{r_1 - r_2}{2},
\qquad
r_2' = r_2 - F^{\ast} = \frac{r_2 - r_1}{2}, r 1 ′ = r 1 − F ∗ = 2 r 1 − r 2 , r 2 ′ = r 2 − F ∗ = 2 r 2 − r 1 , which is exactly the reward example in Figure 1b (right).
In this section, we justify our key design choices and provide an overall analysis of Algorithm alg:projected-ppo .
Pre-computing vs. on-policy learning of the projection.
Theoretically, Theorem 4.1 is stated for an ideal canonicalized base reward r c o r e = P r o j ( r ) r_{\mathrm{core}}=\mathrm{Proj}(r) r core = Proj ( r ) r c o r e r_{\mathrm{core}} r core Ω ∗ \Omega^* Ω ∗ ℓ p \ell_p ℓ p
However, offline pre-computation can be undesirable for two reasons. First, it can be data-inefficient, since obtaining an accurate projection may require a large coverage dataset that is collected solely for canonicalization. Second, our framework allows general choices of Ω ∗ \Omega^* Ω ∗ Ω ∗ \Omega^* Ω ∗
To obtain an algorithm that is both data-efficient and applicable to both policy-independent and policy-dependent Ω ∗ \Omega^* Ω ∗ alg:projected-ppo . The same rollouts are used to update the projection estimate and perform the policy update, so no additional data collection is required. Importantly, if Ω ∗ \Omega^* Ω ∗ π \pi π
Convergence Analysis.
Algorithm 1 can be shown to converge asymptotically using standard two-timescale stochastic approximation arguments [50 , 34 ] . We place the projection update on the fast timescale and the policy update on the slow timescale. Intuitively, the projection parameters track their near-optimal values for the current policy, so the policy updates evolve as if they were computed using an almost-converged projection. Under standard conditions, this separation of timescales yields convergence to a stationary point of the target objective. Next, we outlined the detailed analysis. We begin by stating the assumptions used throughout this section.
Assumption C.10. The iterates { θ i } \{\theta_i\} { θ i } sup i ∥ θ i ∥ < ∞ a.s. \sup_i \|\theta_i\| < \infty \qquad \text{a.s.} sup i ∥ θ i ∥ < ∞ a.s.
This is a standard boundedness assumption used to ensure that the parameter iterates remain in a compact region, thereby enabling the convergence analysis.
Assumption C.11. For each fixed θ ∈ Θ \theta \in \Theta θ ∈ Θ ( μ 0 , π θ , P ) (\mu_0, \pi_\theta, P) ( μ 0 , π θ , P ) alg:projected-ppo are sampled from the stationary regime (or from sufficiently long rollouts).
This assumption typically holds when the environment is a continuous task where every state remains reachable, and the policy continues to explore. Sampling from the stationary regime ensures unbiased stochastic gradients.
Assumption C.12. Let l ( φ , θ ) : = Ω π θ ∗ ( r − F Φ φ ) l(\varphi,\theta) := \Omega^*_{\pi_\theta}\!\bigl(r - F_{\Phi_\varphi}\bigr) l ( φ , θ ) := Ω π θ ∗ ( r − F Φ φ ) alg:projected-ppo , and let ℓ ( φ , θ ; D π θ ) \ell(\varphi,\theta;\mathcal{D}_{\pi_\theta}) ℓ ( φ , θ ; D π θ ) D π θ \mathcal{D}_{\pi_\theta} D π θ L ( φ , θ ) : = E [ l ( φ , θ ) ∣ θ ] L(\varphi,\theta):=\mathbb{E}[l(\varphi,\theta)|\theta] L ( φ , θ ) := E [ l ( φ , θ ) ∣ θ ] l l l π θ \pi_\theta π θ μ \mu μ L φ L_\varphi L φ φ \varphi φ θ ∈ Θ \theta \in \Theta θ ∈ Θ L θ L_\theta L θ θ \theta θ φ ∈ Ψ \varphi \in \Psi φ ∈ Ψ φ ∗ ( θ ) : = arg min φ ∈ Ψ L ( φ , θ ) . \varphi^*(\theta):=\arg\min_{\varphi \in \Psi} L(\varphi, \theta). φ ∗ ( θ ) := arg min φ ∈ Ψ L ( φ , θ ) . E [ ∥ ∇ φ ℓ ( φ , θ ; D π θ ) − ∇ φ L ( φ , θ ) ∥ 2 ∣ φ , θ ] ≤ σ 2 . \mathbb{E}\!\left[ \left\| \nabla_{\varphi} \ell(\varphi,\theta; \mathcal D_{\pi_\theta})
- \nabla_{\varphi} L(\varphi,\theta) \right\|^{2}
\,\big|\, \varphi,\theta \right] \le \sigma^{2}. E [ ∥ ∇ φ ℓ ( φ , θ ; D π θ ) − ∇ φ L ( φ , θ ) ∥ 2 φ , θ ] ≤ σ 2 .
This assumption holds when Φ φ \Phi_\varphi Φ φ Φ φ = ϕ ( s ) ⊤ φ \Phi_\varphi=\phi(s)^\top\varphi Φ φ = ϕ ( s ) ⊤ φ ϕ ( s ) \phi(s) ϕ ( s ) L ( φ , θ ) L(\varphi,\theta) L ( φ , θ ) φ ∗ \varphi^* φ ∗ Φ \Phi Φ
Assumption C.13. The policy class π θ \pi_\theta π θ θ \theta θ ∇ θ J ˉ ( θ , φ ) : = J ( π θ , r φ ) − Ω ( π θ ) \nabla_\theta \bar J(\theta, \varphi):=J(\pi_{\theta},r_{\varphi})-\Omega(\pi_{\theta}) ∇ θ J ˉ ( θ , φ ) := J ( π θ , r φ ) − Ω ( π θ ) ( θ , φ ) (\theta,\varphi) ( θ , φ )
This usually holds for smooth policy-gradient surrogates, and PPO is one practical instantiation.
Assumption C.14. Let t t t φ \varphi φ θ \theta θ { α t } \{\alpha_t\} { α t } ϕ \phi ϕ { β t } \{\beta_t\} { β t } θ \theta θ ∑ t α t = ∞ , ∑ t α t 2 < ∞ , ∑ t β t = ∞ , ∑ t β t 2 < ∞ , β t α t → 0. \sum_t \alpha_t = \infty, \qquad \sum_t \alpha_t^2 < \infty, \qquad
\sum_t \beta_t = \infty, \qquad \sum_t \beta_t^2 < \infty, \qquad
\frac{\beta_t}{\alpha_t} \to 0. ∑ t α t = ∞ , ∑ t α t 2 < ∞ , ∑ t β t = ∞ , ∑ t β t 2 < ∞ , α t β t → 0.
This assumption make sure that Algorithm alg:projected-ppo satisfies a two timescale argument where we update φ \varphi φ l ( φ , θ ) l(\varphi, \theta) l ( φ , θ ) θ \theta θ J ˉ ( θ , φ ) \bar J(\theta,\varphi) J ˉ ( θ , φ ) φ \varphi φ φ ∗ ( π θ ) \varphi^*(\pi_\theta) φ ∗ ( π θ ) π θ → π θ ∗ \pi_\theta \rightarrow \pi_{\theta^*} π θ → π θ ∗ φ → φ ∗ ( π θ ∗ ) \varphi \rightarrow \varphi^*(\pi_{\theta^*}) φ → φ ∗ ( π θ ∗ )
Next, before presenting the convergence proof, we first establish several supporting lemmas.
Lemma C.15. ∥ a − b ∥ 2 ≤ ( 1 + η ) ∥ a ∥ 2 + ( 1 + 1 η ) ∥ b ∥ 2 , ∀ η > 0. \|a - b\|^{2} \;\le\; (1 + \eta)\,\|a\|^{2}
+ \left(1 + \frac{1}{\eta}\right)\|b\|^{2},
\qquad \forall\, \eta > 0. ∥ a − b ∥ 2 ≤ ( 1 + η ) ∥ a ∥ 2 + ( 1 + η 1 ) ∥ b ∥ 2 , ∀ η > 0.
Proof. Notice that
∥ a − b ∥ 2 = ∥ a ∥ 2 + ∥ b ∥ 2 − 2 ⟨ a , b ⟩ ≤ ∥ a ∥ 2 + ∥ b ∥ 2 + 2 ∣ ⟨ a , b ⟩ ∣ ≤ ∥ a ∥ 2 + ∥ b ∥ 2 + 2 ∥ a ∥ ∥ b ∥ . \|a-b\|^{2}
= \|a\|^{2} + \|b\|^{2} - 2\langle a,b\rangle
\le \|a\|^{2} + \|b\|^{2} + 2|\langle a,b\rangle|
\le \|a\|^{2} + \|b\|^{2} + 2\|a\|\,\|b\|. ∥ a − b ∥ 2 = ∥ a ∥ 2 + ∥ b ∥ 2 − 2 ⟨ a , b ⟩ ≤ ∥ a ∥ 2 + ∥ b ∥ 2 + 2∣ ⟨ a , b ⟩ ∣ ≤ ∥ a ∥ 2 + ∥ b ∥ 2 + 2∥ a ∥ ∥ b ∥. Consider the nonnegative square
( η u − 1 η v ) 2 ≥ 0. \Bigl(\sqrt{\eta}\,u - \frac{1}{\sqrt{\eta}}\,v\Bigr)^{2} \;\ge\; 0. ( η u − η 1 v ) 2 ≥ 0. Expanding gives
η u 2 + 1 η v 2 − 2 u v ≥ 0 ⟹ 2 u v ≤ η u 2 + 1 η v 2 . \eta u^{2} + \frac{1}{\eta} v^{2} - 2uv \;\ge\; 0
\quad\Longrightarrow\quad
2uv \;\le\; \eta u^{2} + \frac{1}{\eta} v^{2}. η u 2 + η 1 v 2 − 2 uv ≥ 0 ⟹ 2 uv ≤ η u 2 + η 1 v 2 . Let u = ∥ a ∥ , v = ∥ b ∥ u=\|a\|, v=\|b\| u = ∥ a ∥ , v = ∥ b ∥
2 ∥ a ∥ ∥ b ∥ ≤ η ∥ a ∥ 2 + 1 η ∥ b ∥ 2 . 2\|a\|\,\|b\| \le \eta \|a\|^{2} + \frac{1}{\eta}\|b\|^{2}. 2∥ a ∥ ∥ b ∥ ≤ η ∥ a ∥ 2 + η 1 ∥ b ∥ 2 . Hence
∥ a − b ∥ 2 ≤ ( 1 + η ) ∥ a ∥ 2 + ( 1 + 1 η ) ∥ b ∥ 2 . \|a-b\|^{2}
\le (1+\eta)\|a\|^{2}
+ \left(1+\frac{1}{\eta}\right)\|b\|^{2}. ∥ a − b ∥ 2 ≤ ( 1 + η ) ∥ a ∥ 2 + ( 1 + η 1 ) ∥ b ∥ 2 . This completes the proof. ◻
Lemma C.16. Under Assumption C.12 , there exists some constant K K K ∥ φ ⋆ ( θ 1 ) − φ ⋆ ( θ 2 ) ∥ ≤ K ∥ θ 1 − θ 2 ∥ , ∀ θ 1 , θ 2 . \bigl\|\varphi^{\star}(\theta_1)-\varphi^{\star}(\theta_2)\bigr\|
\;\le\; K\,\bigl\|\theta_1-\theta_2\bigr\|,
\qquad \forall\,\theta_1,\theta_2 . φ ⋆ ( θ 1 ) − φ ⋆ ( θ 2 ) ≤ K θ 1 − θ 2 , ∀ θ 1 , θ 2 .
Proof. Under Assumption C.12 ,there exists μ > 0 \mu > 0 μ > 0 θ \theta θ φ 1 , φ 2 \varphi_1,\varphi_2 φ 1 , φ 2
⟨ ∇ φ L ( φ 1 , θ ) − ∇ φ L ( φ 2 , θ ) , φ 1 − φ 2 ⟩ ≥ μ ∥ φ 1 − φ 2 ∥ 2 . \big\langle
\nabla_\varphi L(\varphi_1,\theta) - \nabla_\varphi L(\varphi_2,\theta),
\,\varphi_1 - \varphi_2
\big\rangle
\;\ge\;
\mu \,\|\varphi_1 - \varphi_2\|^2 . ⟨ ∇ φ L ( φ 1 , θ ) − ∇ φ L ( φ 2 , θ ) , φ 1 − φ 2 ⟩ ≥ μ ∥ φ 1 − φ 2 ∥ 2 . And there exists L θ > 0 L_{\theta} > 0 L θ > 0 φ \varphi φ θ 1 , θ 2 \theta_1,\theta_2 θ 1 , θ 2
∥ ∇ φ L ( φ , θ 1 ) − ∇ φ L ( φ , θ 2 ) ∥ ≤ L θ ∥ θ 1 − θ 2 ∥ . \big\|
\nabla_\varphi L(\varphi,\theta_1)
- \nabla_\varphi L(\varphi,\theta_2)
\big\|
\;\le\;
L_{\theta}\,\|\theta_1 - \theta_2\| . ∇ φ L ( φ , θ 1 ) − ∇ φ L ( φ , θ 2 ) ≤ L θ ∥ θ 1 − θ 2 ∥. Fix any θ 1 , θ 2 \theta_1,\theta_2 θ 1 , θ 2
φ 1 : = φ ⋆ ( θ 1 ) , φ 2 : = φ ⋆ ( θ 2 ) . \varphi_1 := \varphi^{\star}(\theta_1),
\qquad
\varphi_2 := \varphi^{\star}(\theta_2). φ 1 := φ ⋆ ( θ 1 ) , φ 2 := φ ⋆ ( θ 2 ) . Because φ 1 \varphi_1 φ 1 φ 2 \varphi_2 φ 2 L ( ⋅ , θ 1 ) L(\cdot,\theta_1) L ( ⋅ , θ 1 ) L ( ⋅ , θ 2 ) L(\cdot,\theta_2) L ( ⋅ , θ 2 )
∇ φ L ( φ 1 , θ 1 ) = 0 , ∇ φ L ( φ 2 , θ 2 ) = 0. \nabla_{\varphi} L(\varphi_1,\theta_1) = 0,
\qquad
\nabla_{\varphi} L(\varphi_2,\theta_2) = 0. ∇ φ L ( φ 1 , θ 1 ) = 0 , ∇ φ L ( φ 2 , θ 2 ) = 0. Consider
0 = ∇ φ L ( φ 1 , θ 1 ) − ∇ φ L ( φ 2 , θ 2 ) = ( ∇ φ L ( φ 1 , θ 1 ) − ∇ φ L ( φ 2 , θ 1 ) ) ⏟ ( 1 ) + ( ∇ φ L ( φ 2 , θ 1 ) − ∇ φ L ( φ 2 , θ 2 ) ) ⏟ ( 2 ) . \begin{align*}
0
&= \nabla_{\varphi} L(\varphi_1,\theta_1) - \nabla_{\varphi} L(\varphi_2,\theta_2) \\
&= \underbrace{\bigl(\nabla_{\varphi} L(\varphi_1,\theta_1)
- \nabla_{\varphi} L(\varphi_2,\theta_1)\bigr)}_{(1)}
\;+\;
\underbrace{\bigl(\nabla_{\varphi} L(\varphi_2,\theta_1)
- \nabla_{\varphi} L(\varphi_2,\theta_2)\bigr)}_{(2)} .
\end{align*} 0 = ∇ φ L ( φ 1 , θ 1 ) − ∇ φ L ( φ 2 , θ 2 ) = ( 1 ) ( ∇ φ L ( φ 1 , θ 1 ) − ∇ φ L ( φ 2 , θ 1 ) ) + ( 2 ) ( ∇ φ L ( φ 2 , θ 1 ) − ∇ φ L ( φ 2 , θ 2 ) ) . Take the inner product of both sides with φ 1 − φ 2 \varphi_1-\varphi_2 φ 1 − φ 2
⟨ ( 1 ) , φ 1 − φ 2 ⟩ = − ⟨ ( 2 ) , φ 1 − φ 2 ⟩ . \bigl\langle(1),\varphi_1-\varphi_2\bigr\rangle
\;=\;
-\bigl\langle(2),\varphi_1-\varphi_2\bigr\rangle . ⟨ ( 1 ) , φ 1 − φ 2 ⟩ = − ⟨ ( 2 ) , φ 1 − φ 2 ⟩ . Lower bound the left-hand side:
⟨ ( 1 ) , φ 1 − φ 2 ⟩ = ⟨ ∇ φ L ( φ 1 , θ 1 ) − ∇ φ L ( φ 2 , θ 1 ) , φ 1 − φ 2 ⟩ ≥ μ ∥ φ 1 − φ 2 ∥ 2 . \bigl\langle(1),\varphi_1-\varphi_2\bigr\rangle
= \bigl\langle
\nabla_{\varphi} L(\varphi_1,\theta_1)
- \nabla_{\varphi} L(\varphi_2,\theta_1),
\,\varphi_1-\varphi_2
\bigr\rangle
\;\ge\; \mu \|\varphi_1-\varphi_2\|^2 . ⟨ ( 1 ) , φ 1 − φ 2 ⟩ = ⟨ ∇ φ L ( φ 1 , θ 1 ) − ∇ φ L ( φ 2 , θ 1 ) , φ 1 − φ 2 ⟩ ≥ μ ∥ φ 1 − φ 2 ∥ 2 . Upper bound the right-hand side:
∣ ⟨ ( 2 ) , φ 1 − φ 2 ⟩ ∣ ≤ ∥ ( 2 ) ∥ ∥ φ 1 − φ 2 ∥ = ∥ ∇ φ L ( φ 2 , θ 1 ) − ∇ φ L ( φ 2 , θ 2 ) ∥ ∥ φ 1 − φ 2 ∥ ≤ L θ ∥ θ 1 − θ 2 ∥ ∥ φ 1 − φ 2 ∥ . \begin{align*}
\bigl|\langle(2),\varphi_1-\varphi_2\rangle\bigr|
&\le \|(2)\|\,\|\varphi_1-\varphi_2\| \\
&= \bigl\|
\nabla_{\varphi} L(\varphi_2,\theta_1)
- \nabla_{\varphi} L(\varphi_2,\theta_2)
\bigr\|\,\|\varphi_1-\varphi_2\| \\
&\le L_{\theta}\,\|\theta_1-\theta_2\|\,\|\varphi_1-\varphi_2\| .
\end{align*} ⟨( 2 ) , φ 1 − φ 2 ⟩ ≤ ∥ ( 2 ) ∥ ∥ φ 1 − φ 2 ∥ = ∇ φ L ( φ 2 , θ 1 ) − ∇ φ L ( φ 2 , θ 2 ) ∥ φ 1 − φ 2 ∥ ≤ L θ ∥ θ 1 − θ 2 ∥ ∥ φ 1 − φ 2 ∥. Combining above gives
μ ∥ φ 1 − φ 2 ∥ 2 ≤ L θ ∥ θ 1 − θ 2 ∥ ∥ φ 1 − φ 2 ∥ . \mu \|\varphi_1-\varphi_2\|^2
\;\le\;
L_{\theta}\,\|\theta_1-\theta_2\|\,\|\varphi_1-\varphi_2\| . μ ∥ φ 1 − φ 2 ∥ 2 ≤ L θ ∥ θ 1 − θ 2 ∥ ∥ φ 1 − φ 2 ∥. If φ 1 = φ 2 \varphi_1=\varphi_2 φ 1 = φ 2 ∥ φ 1 − φ 2 ∥ \|\varphi_1-\varphi_2\| ∥ φ 1 − φ 2 ∥
∥ φ 1 − φ 2 ∥ ≤ L θ μ ∥ θ 1 − θ 2 ∥ = K ∥ θ 1 − θ 2 ∥ . \|\varphi_1-\varphi_2\|
\;\le\;
\frac{L_{\theta}}{\mu}\,\|\theta_1-\theta_2\| =K\|\theta_1-\theta_2\|. ∥ φ 1 − φ 2 ∥ ≤ μ L θ ∥ θ 1 − θ 2 ∥ = K ∥ θ 1 − θ 2 ∥. This completes the proof. ◻
Theorem C.17. Consider Algorithm alg:projected-ppo and suppose Assumptions C.10 , C.11 , C.12 , C.13 and C.14 hold. Then, the iterates ( θ i , φ i ) (\theta_i, \varphi_i) ( θ i , φ i ) alg:projected-ppo satisfy, almost surely:
The iterate for φ \varphi φ ∥ φ i − φ ∗ ( θ i ) ∥ → 0 , φ ∗ ( θ ) : = arg min φ L ( φ , θ ) . \|\varphi_i-\varphi^*(\theta_i)\|\to 0,
\qquad
\varphi^*(\theta):=\arg\min_\varphi L(\varphi,\theta). ∥ φ i − φ ∗ ( θ i ) ∥ → 0 , φ ∗ ( θ ) := arg min φ L ( φ , θ ) .
Define the mean drift as h ( θ , φ ) : = E [ ∇ θ J ˉ ( θ , φ ) ∣ θ , φ ] h(\theta,\varphi):=\mathbb{E}[\nabla_\theta \bar J\big(\theta,\varphi\big)|\theta,\varphi] h ( θ , φ ) := E [ ∇ θ J ˉ ( θ , φ ) ∣ θ , φ ] { θ i } \{\theta_i\} { θ i } θ ˙ = h ( θ , φ ∗ ( θ ) ) , \dot\theta =h\big(\theta,\varphi^*(\theta)\big), θ ˙ = h ( θ , φ ∗ ( θ ) ) , { θ i } \{\theta_i\} { θ i }
If the mean θ \theta θ h ( θ , φ ) h(\theta,\varphi) h ( θ , φ ) ∇ θ J ˉ ( θ , φ ) \nabla_\theta \bar J(\theta,\varphi) ∇ θ J ˉ ( θ , φ ) θ ∞ \theta_\infty θ ∞ ∇ θ J ˉ ( θ ∞ , φ ∗ ( θ ∞ ) ) = 0. \nabla_\theta \bar J\big(\theta_\infty,\varphi^*(\theta_\infty)\big)=0. ∇ θ J ˉ ( θ ∞ , φ ∗ ( θ ∞ ) ) = 0.
Proof. 1. For fixed outer index i i i k k k
M i , k + 1 : = ∇ φ ℓ ( φ i , k , θ i ; D π θ i ) − ∇ φ L ( φ i , k , θ i ) . M_{i,k+1}
:= \nabla_\varphi \ell(\varphi_{i,k},\theta_i; D_{\pi_{\theta_i}})
- \nabla_\varphi L(\varphi_{i,k},\theta_i). M i , k + 1 := ∇ φ ℓ ( φ i , k , θ i ; D π θ i ) − ∇ φ L ( φ i , k , θ i ) . By Assumption C.12 , we have E [ ∥ M i , k + 1 ∥ 2 ∣ φ i , k , θ i ] ≤ σ 2 . \mathbb{E}\bigl[\|M_{i,k+1}\|^2 \mid \varphi_{i,k},\theta_i\bigr] \le \sigma^2. E [ ∥ M i , k + 1 ∥ 2 ∣ φ i , k , θ i ] ≤ σ 2 .
φ i , k + 1 = φ i , k − α i , k ( ∇ φ L ( φ i , k , θ i ) + M i , k + 1 ) , \varphi_{i,k+1}
= \varphi_{i,k}
- \alpha_{i,k}\bigl(\nabla_\varphi L(\varphi_{i,k},\theta_i) + M_{i,k+1}\bigr), φ i , k + 1 = φ i , k − α i , k ( ∇ φ L ( φ i , k , θ i ) + M i , k + 1 ) , which is standard SGD on L ( ⋅ , θ i ) L(\cdot,\theta_i) L ( ⋅ , θ i ) e i , k : = φ i , k − φ ∗ ( θ i ) . e_{i,k} := \varphi_{i,k} - \varphi^*(\theta_i). e i , k := φ i , k − φ ∗ ( θ i ) . φ ∗ ( θ i ) \varphi^*(\theta_i) φ ∗ ( θ i ) L ( ⋅ , θ i ) L(\cdot,\theta_i) L ( ⋅ , θ i ) ∇ φ L ( φ ∗ ( θ i ) , θ i ) = 0. \nabla_\varphi L\bigl(\varphi^*(\theta_i),\theta_i\bigr) = 0. ∇ φ L ( φ ∗ ( θ i ) , θ i ) = 0.
∥ e i , k + 1 ∥ 2 = ∥ φ i , k + 1 − φ ∗ ( θ i ) ∥ 2 = ∥ φ i , k − φ ∗ ( θ i ) − α i , k ( ∇ φ L ( φ i , k , θ i ) + M i , k + 1 ) ∥ 2 = ∥ e i , k − α i , k ( ∇ φ L ( φ i , k , θ i ) + M i , k + 1 ) ∥ 2 \begin{align*}
\|e_{i,k+1}\|^2
&= \bigl\| \varphi_{i,k+1} - \varphi^*(\theta_i) \bigr\|^2 \\
&= \bigl\| \varphi_{i,k}- \varphi^*(\theta_i)
- \alpha_{i,k}\bigl(\nabla_\varphi L(\varphi_{i,k},\theta_i) + M_{i,k+1}\bigr) \bigr\|^2 \\
&= \bigl\|e_{i,k} - \alpha_{i,k}\bigl(\nabla_\varphi L(\varphi_{i,k},\theta_i)
+ M_{i,k+1}\bigr)\bigr\|^2
\end{align*} ∥ e i , k + 1 ∥ 2 = φ i , k + 1 − φ ∗ ( θ i ) 2 = φ i , k − φ ∗ ( θ i ) − α i , k ( ∇ φ L ( φ i , k , θ i ) + M i , k + 1 ) 2 = e i , k − α i , k ( ∇ φ L ( φ i , k , θ i ) + M i , k + 1 ) 2 Take the conditional expectation given F i , k : = σ ( θ i , φ i , 0 , … , φ i , k , D π θ i ) . \mathcal{F}_{i,k}
:= \sigma\bigl(\theta_i,\varphi_{i,0},\ldots,\varphi_{i,k},D_{\pi_{\theta_i}}\bigr). F i , k := σ ( θ i , φ i , 0 , … , φ i , k , D π θ i ) .
E [ ∥ e i , k + 1 ∥ 2 ∣ F i , k ] = ∥ e i , k ∥ 2 − 2 α i , k ⟨ e i , k , ∇ φ L ( φ i , k , θ i ) ⟩ − 2 α i , k ⟨ e i , k , E [ M i , k + 1 ∣ F i , k ] ⟩ + α i , k 2 ∥ ∇ φ L ( φ i , k , θ i ) ∥ 2 + α i , k 2 E [ ∥ M i , k + 1 ∥ 2 ∣ F i , k ] . = ( i ) ∥ e i , k ∥ 2 − 2 α i , k ⟨ e i , k , ∇ φ L ( φ i , k , θ i ) ⟩ + α i , k 2 ∥ ∇ φ L ( φ i , k , θ i ) ∥ 2 + α i , k 2 E [ ∥ M i , k + 1 ∥ 2 ∣ F i , k ] . ≤ ( i i ) ( 1 − 2 μ α i , k + L φ 2 α i , k 2 ) ∥ e i , k ∥ 2 + σ 2 α i , k 2 \begin{align*}
\mathbb{E}\bigl[\|e_{i,k+1}\|^2 \mid \mathcal{F}_{i,k}\bigr]
&= \|e_{i,k}\|^2
- 2\alpha_{i,k} \bigl\langle e_{i,k},
\nabla_\varphi L(\varphi_{i,k},\theta_i) \bigr\rangle - 2\alpha_{i,k} \bigl\langle e_{i,k},
\mathbb{E}\bigl[M_{i,k+1} \mid \mathcal{F}_{i,k}\bigr] \bigr\rangle\\
&\quad + \alpha_{i,k}^2
\bigl\|\nabla_\varphi L(\varphi_{i,k},\theta_i)\bigr\|^2
+ \alpha_{i,k}^2 \,
\mathbb{E}\bigl[\|M_{i,k+1}\|^2 \mid \mathcal{F}_{i,k}\bigr]. \\
&\overset{(i)}{=} \|e_{i,k}\|^2
- 2\alpha_{i,k} \bigl\langle e_{i,k},\nabla_\varphi L(\varphi_{i,k},\theta_i) \bigr\rangle \\
&\quad + \alpha_{i,k}^2
\bigl\|\nabla_\varphi L(\varphi_{i,k},\theta_i)\bigr\|^2
+ \alpha_{i,k}^2 \,
\mathbb{E}\bigl[\|M_{i,k+1}\|^2 \mid \mathcal{F}_{i,k}\bigr]. \\
&\overset{(ii)}{\le} \bigl(1 - 2\mu\alpha_{i,k} + L_\varphi^2 \alpha_{i,k}^2\bigr)\|e_{i,k}\|^2
+ \sigma^2 \alpha_{i,k}^2
\end{align*} E [ ∥ e i , k + 1 ∥ 2 ∣ F i , k ] = ∥ e i , k ∥ 2 − 2 α i , k ⟨ e i , k , ∇ φ L ( φ i , k , θ i ) ⟩ − 2 α i , k ⟨ e i , k , E [ M i , k + 1 ∣ F i , k ] ⟩ + α i , k 2 ∇ φ L ( φ i , k , θ i ) 2 + α i , k 2 E [ ∥ M i , k + 1 ∥ 2 ∣ F i , k ] . = ( i ) ∥ e i , k ∥ 2 − 2 α i , k ⟨ e i , k , ∇ φ L ( φ i , k , θ i ) ⟩ + α i , k 2 ∇ φ L ( φ i , k , θ i ) 2 + α i , k 2 E [ ∥ M i , k + 1 ∥ 2 ∣ F i , k ] . ≤ ( ii ) ( 1 − 2 μ α i , k + L φ 2 α i , k 2 ) ∥ e i , k ∥ 2 + σ 2 α i , k 2 (i) uses E [ M i , k + 1 ∣ F i , k ] = 0 \mathbb{E}[M_{i,k+1} \mid \mathcal{F}_{i,k}] = 0 E [ M i , k + 1 ∣ F i , k ] = 0 C.11 ); (ii) use the μ \mu μ L φ L_\varphi L φ C.12
⟨ e i , k , ∇ φ L ( φ i , k , θ i ) ⟩ = ⟨ e i , k , ∇ φ L ( φ i , k , θ i ) − ∇ φ L ( φ ∗ ( θ i ) , θ i ) ⟩ ≥ μ ∥ e i , k ∥ 2 , \bigl\langle e_{i,k}, \nabla_\varphi L(\varphi_{i,k},\theta_i) \bigr\rangle
= \bigl\langle e_{i,k}, \nabla_\varphi L(\varphi_{i,k},\theta_i) -\nabla_\varphi L(\varphi^*(\theta_i),\theta_i)\bigr\rangle \ge \mu \|e_{i,k}\|^2, ⟨ e i , k , ∇ φ L ( φ i , k , θ i ) ⟩ = ⟨ e i , k , ∇ φ L ( φ i , k , θ i ) − ∇ φ L ( φ ∗ ( θ i ) , θ i ) ⟩ ≥ μ ∥ e i , k ∥ 2 , ∥ ∇ φ L ( φ i , k , θ i ) ∥ = ∥ ∇ φ L ( φ i , k , θ i ) − ∇ φ L ( φ ∗ ( θ i ) , θ i ) ∥ ≤ L φ ∥ e i , k ∥ . \bigl\|\nabla_\varphi L(\varphi_{i,k},\theta_i)\bigr\|
= \bigl\|\nabla_\varphi L(\varphi_{i,k},\theta_i)-\nabla_\varphi L(\varphi^*(\theta_i),\theta_i)\bigr\| \le L_\varphi \|e_{i,k}\|. ∇ φ L ( φ i , k , θ i ) = ∇ φ L ( φ i , k , θ i ) − ∇ φ L ( φ ∗ ( θ i ) , θ i ) ≤ L φ ∥ e i , k ∥. Because ∑ k α i , k 2 < ∞ \sum_k \alpha_{i,k}^2 < \infty ∑ k α i , k 2 < ∞ C.14 ) and ∑ k α i , k = ∞ \sum_k \alpha_{i,k} = \infty ∑ k α i , k = ∞ [21 ] implies
∥ e i , k ∥ 2 ⟶ 0 a.s. as k → ∞ ( for fixed θ i ) . \|e_{i,k}\|^2 \longrightarrow 0
\qquad \text{a.s.\ as } k \to \infty
\quad (\text{for fixed } \theta_i). ∥ e i , k ∥ 2 ⟶ 0 a.s. as k → ∞ ( for fixed θ i ) . Next, according to Assumption C.14 , when we use t t t β t α t → 0 \frac{\beta_t}{\alpha_t}\rightarrow 0 α t β t → 0 θ \theta θ φ \varphi φ θ \theta θ e t : = φ t − φ ∗ ( θ t ) e_t := \varphi_t - \varphi^*(\theta_t) e t := φ t − φ ∗ ( θ t ) θ \theta θ φ \varphi φ t t t e t + 1 = φ t + 1 − φ ∗ ( θ t + 1 ) = ( φ t + 1 − φ ∗ ( θ t ) ) + ( φ ∗ ( θ t ) − φ ∗ ( θ t + 1 ) ) . e_{t+1} = \varphi_{t+1} - \varphi^*(\theta_{t+1}) =(\varphi_{t+1}-\varphi^*(\theta_{t}))+(\varphi^*(\theta_{t})-\varphi^*(\theta_{t+1})). e t + 1 = φ t + 1 − φ ∗ ( θ t + 1 ) = ( φ t + 1 − φ ∗ ( θ t )) + ( φ ∗ ( θ t ) − φ ∗ ( θ t + 1 )) . C.15 :
∥ a − b ∥ 2 ≤ ( 1 + η ) ∥ a ∥ 2 + ( 1 + 1 η ) ∥ b ∥ 2 , ∀ η > 0. \|a - b\|^{2} \;\le\; (1 + \eta)\,\|a\|^{2}
+ \left(1 + \frac{1}{\eta}\right)\|b\|^{2},
\qquad \forall\, \eta > 0. ∥ a − b ∥ 2 ≤ ( 1 + η ) ∥ a ∥ 2 + ( 1 + η 1 ) ∥ b ∥ 2 , ∀ η > 0. Apply this with a = φ t + 1 − φ ∗ ( θ t ) a = \varphi_{t+1}-\varphi^*(\theta_{t}) a = φ t + 1 − φ ∗ ( θ t ) b = φ ∗ ( θ t ) − φ ∗ ( θ t + 1 ) ) b = \varphi^*(\theta_{t})-\varphi^*(\theta_{t+1})) b = φ ∗ ( θ t ) − φ ∗ ( θ t + 1 ))
∥ e t + 1 ∥ 2 ≤ ( 1 + η ) ∥ φ t + 1 − φ ∗ ( θ t ) ∥ 2 + ( 1 + 1 η ) ∥ φ ∗ ( θ t ) − φ ∗ ( θ t + 1 ) ) ∥ 2 . \|e_{t+1}\|^{2}
\;\le\; (1 + \eta)\,\|\varphi_{t+1}-\varphi^*(\theta_{t})\|^{2}
+ \left(1 + \frac{1}{\eta}\right)\|\varphi^*(\theta_{t})-\varphi^*(\theta_{t+1}))\|^{2}. ∥ e t + 1 ∥ 2 ≤ ( 1 + η ) ∥ φ t + 1 − φ ∗ ( θ t ) ∥ 2 + ( 1 + η 1 ) ∥ φ ∗ ( θ t ) − φ ∗ ( θ t + 1 )) ∥ 2 . Take conditional expectation given F t \mathcal{F}_t F t
E [ ∥ e t + 1 ∥ 2 ∣ F t ] ≤ ( 1 + η ) E [ ∥ φ t + 1 − φ ∗ ( θ t ) ∥ 2 ∣ F t ] + ( 1 + 1 η ) ∥ φ ∗ ( θ t ) − φ ∗ ( θ t + 1 ) ) ∥ 2 . \mathbb{E}\bigl[\|e_{t+1}\|^{2} \mid \mathcal{F}_t\bigr]
\;\le\; (1 + \eta)\,\mathbb{E}\bigl[\|\varphi_{t+1}-\varphi^*(\theta_{t})\|^{2} \mid \mathcal{F}_t\bigr]
+ \left(1 + \frac{1}{\eta}\right)\|\varphi^*(\theta_{t})-\varphi^*(\theta_{t+1}))\|^{2}. E [ ∥ e t + 1 ∥ 2 ∣ F t ] ≤ ( 1 + η ) E [ ∥ φ t + 1 − φ ∗ ( θ t ) ∥ 2 ∣ F t ] + ( 1 + η 1 ) ∥ φ ∗ ( θ t ) − φ ∗ ( θ t + 1 )) ∥ 2 . As for bounding E [ ∥ φ t + 1 − φ ∗ ( θ t ) ∥ 2 ∣ F t ] \mathbb{E}\bigl[\|\varphi_{t+1}-\varphi^*(\theta_{t})\|^{2}\mid \mathcal{F}_t\bigr] E [ ∥ φ t + 1 − φ ∗ ( θ t ) ∥ 2 ∣ F t ] φ ∗ ( θ t ) \varphi^*(\theta_t) φ ∗ ( θ t ) e i , k + 1 e_{i,k+1} e i , k + 1 c 1 , c 2 , c 3 > 0 c_1,c_2,c_3>0 c 1 , c 2 , c 3 > 0
E [ ∥ φ t + 1 − φ ∗ ( θ t ) ∥ 2 ∣ F t ] ≤ ( 1 − c 1 α t + c 2 α t 2 ) ∥ e t ∥ 2 + c 3 α t 2 \mathbb{E}\bigl[\|\varphi_{t+1}-\varphi^*(\theta_{t})\|^{2}\mid \mathcal{F}_t\bigr] \le \bigl(1 - c_1\alpha_{t} + c_2 \alpha_{t}^2\bigr)\|e_{t}\|^2
+ c_3 \alpha_{t}^2 E [ ∥ φ t + 1 − φ ∗ ( θ t ) ∥ 2 ∣ F t ] ≤ ( 1 − c 1 α t + c 2 α t 2 ) ∥ e t ∥ 2 + c 3 α t 2 Next, we bound ∥ φ ∗ ( θ t ) − φ ∗ ( θ t + 1 ) ) ∥ 2 \|\varphi^*(\theta_{t})-\varphi^*(\theta_{t+1}))\|^{2} ∥ φ ∗ ( θ t ) − φ ∗ ( θ t + 1 )) ∥ 2 C.16 , φ ∗ ( θ ) \varphi^*(\theta) φ ∗ ( θ )
∥ φ ∗ ( θ ′ ) − φ ∗ ( θ ) ∥ ≤ K ∥ θ ′ − θ ∥ for some K > 0. \|\varphi^*(\theta') - \varphi^*(\theta)\|
\;\le\; K \,\|\theta' - \theta\| \quad \text{for some } K>0. ∥ φ ∗ ( θ ′ ) − φ ∗ ( θ ) ∥ ≤ K ∥ θ ′ − θ ∥ for some K > 0. So
∥ φ ∗ ( θ t ) − φ ∗ ( θ t + 1 ) ) ∥ ≤ K ∥ θ t + 1 − θ t ∥ . \|\varphi^*(\theta_{t})-\varphi^*(\theta_{t+1}))\| \;\le\; K \,\|\theta_{t+1} - \theta_t\|. ∥ φ ∗ ( θ t ) − φ ∗ ( θ t + 1 )) ∥ ≤ K ∥ θ t + 1 − θ t ∥. But θ \theta θ β t \beta_t β t
∥ θ t + 1 − θ t ∥ = O ( β t ) . \|\theta_{t+1} - \theta_t\| = O(\beta_t). ∥ θ t + 1 − θ t ∥ = O ( β t ) . Hence we have:
∥ φ ∗ ( θ t ) − φ ∗ ( θ t + 1 ) ) ∥ 2 ≤ c 4 β t 2 , for some c 4 > 0. \|\varphi^*(\theta_{t})-\varphi^*(\theta_{t+1}))\|^{2}\le c_4 \beta_t^2, \qquad \text{for some } c_4>0. ∥ φ ∗ ( θ t ) − φ ∗ ( θ t + 1 )) ∥ 2 ≤ c 4 β t 2 , for some c 4 > 0. Now apply Robbins-Siegmund again. Since ∑ t α t 2 < ∞ \sum_t \alpha_t^2 < \infty ∑ t α t 2 < ∞ ∑ t β t 2 < ∞ \sum_t \beta_t^2 < \infty ∑ t β t 2 < ∞ ∑ t α t = ∞ \sum_t \alpha_t = \infty ∑ t α t = ∞
∥ e t + 1 ∥ ⟶ 0 a.s. \|e_{t+1}\| \longrightarrow 0 \quad \text{a.s.} ∥ e t + 1 ∥ ⟶ 0 a.s. Once we have ∥ e t + 1 ∥ → 0 \|e_{t+1}\| \to 0 ∥ e t + 1 ∥ → 0 t t t φ i + 1 = φ i , K i \varphi_{i+1} = \varphi_{i,K_i} φ i + 1 = φ i , K i
∥ φ i − φ ∗ ( θ i ) ∥ ⟶ 0 a.s. \|\varphi_i - \varphi^*(\theta_i)\| \longrightarrow 0 \quad \text{a.s.} ∥ φ i − φ ∗ ( θ i ) ∥ ⟶ 0 a.s. 2. The θ \theta θ
θ i + 1 = θ i + β i ( h ( θ i , φ i + 1 ) + ξ i + 1 ) , \theta_{i+1}
= \theta_i + \beta_i \bigl( h(\theta_i, \varphi_{i+1}) + \xi_{i+1} \bigr), θ i + 1 = θ i + β i ( h ( θ i , φ i + 1 ) + ξ i + 1 ) , where { ξ i + 1 } \{\xi_{i+1}\} { ξ i + 1 }
ξ i + 1 : = ∇ θ J ˉ ( θ i , φ i + 1 ; D π θ i ′ ) − h ( θ i , φ i + 1 ) . \xi_{i+1}
:= \nabla_\theta \bar J(\theta_i, \varphi_{i+1}; D'_{\pi_{\theta_i}})
- h(\theta_i, \varphi_{i+1}) . ξ i + 1 := ∇ θ J ˉ ( θ i , φ i + 1 ; D π θ i ′ ) − h ( θ i , φ i + 1 ) . The Lipschitz assumption on ∇ θ J ˉ ( θ , φ ) \nabla_\theta \bar J(\theta, \varphi) ∇ θ J ˉ ( θ , φ ) C.13 ) implies that h h h ( θ , φ ) (\theta,\varphi) ( θ , φ ) { θ i } \{\theta_i\} { θ i } C.10 and also ∑ i β i 2 < ∞ \sum_i \beta_i^2 < \infty ∑ i β i 2 < ∞ C.14 ) ensures that the accumulated noise is controlled in the ODE method. Now use ∥ φ i + 1 − φ ∗ ( θ i ) ∥ → 0 \|\varphi_{i+1} - \varphi^*(\theta_i)\| \to 0 ∥ φ i + 1 − φ ∗ ( θ i ) ∥ → 0 h h h
∥ h ( θ i , φ i + 1 ) − h ( θ i , φ ∗ ( θ i ) ) ∥ ≤ L h ∥ φ i + 1 − φ ∗ ( θ i ) ∥ ⟶ 0 a.s. \bigl\| h(\theta_i, \varphi_{i+1}) - h(\theta_i, \varphi^*(\theta_i)) \bigr\|
\;\le\; L_h \bigl\|\varphi_{i+1} - \varphi^*(\theta_i)\bigr\|
\;\longrightarrow\; 0
\quad \text{a.s.} h ( θ i , φ i + 1 ) − h ( θ i , φ ∗ ( θ i )) ≤ L h φ i + 1 − φ ∗ ( θ i ) ⟶ 0 a.s. Hence the θ \theta θ
θ i + 1 = θ i + β i ( h ( θ i , φ ∗ ( θ i ) ) + o ( 1 ) + ξ i + 1 ) . \theta_{i+1}
= \theta_i
+ \beta_i \Bigl( h(\theta_i, \varphi^*(\theta_i))
+ o(1)
+ \xi_{i+1} \Bigr). θ i + 1 = θ i + β i ( h ( θ i , φ ∗ ( θ i )) + o ( 1 ) + ξ i + 1 ) . Standard ODE-method conclusions (Kushner-Clark two-timescale SA [19 , 20 ] ) then imply that the continuous-time interpolation of { θ i } \{\theta_i\} { θ i }
θ ˙ = h ( θ , φ ∗ ( θ ) ) . \dot{\theta} = h\bigl(\theta, \varphi^*(\theta)\bigr). θ ˙ = h ( θ , φ ∗ ( θ ) ) . 3. If we assume h ( θ , φ ∗ ( θ ) ) = ∇ θ J ˉ ( θ , φ ) h\bigl(\theta, \varphi^*(\theta)\bigr)=\nabla_\theta \bar J(\theta,\varphi) h ( θ , φ ∗ ( θ ) ) = ∇ θ J ˉ ( θ , φ )
θ ˙ = ∇ θ J ˉ ( θ , φ ∗ ( θ ) ) . \dot{\theta} = \nabla_\theta \bar J\bigl(\theta, \varphi^*(\theta)\bigr). θ ˙ = ∇ θ J ˉ ( θ , φ ∗ ( θ ) ) . Use J ˉ ( θ ) \bar J(\theta) J ˉ ( θ ) J ( θ , φ ∗ ( θ ) ) J\bigl(\theta, \varphi^*(\theta)\bigr) J ( θ , φ ∗ ( θ ) ) θ ( t ) \theta(t) θ ( t )
d d t J ˉ ( θ ( t ) ) = ⟨ ∇ J ˉ ( θ ( t ) ) , θ ˙ ( t ) ⟩ . \frac{d}{dt}\,\bar J(\theta(t))
\;=\;
\big\langle \nabla \bar J(\theta(t)),\, \dot\theta(t) \big\rangle. d t d J ˉ ( θ ( t )) = ⟨ ∇ J ˉ ( θ ( t )) , θ ˙ ( t ) ⟩ . Substituting θ ˙ ( t ) = ∇ J ˉ ( θ ( t ) ) \dot\theta(t) = \nabla \bar J(\theta(t)) θ ˙ ( t ) = ∇ J ˉ ( θ ( t ))
d d t J ˉ ( θ ( t ) ) = ⟨ ∇ J ˉ ( θ ( t ) ) , ∇ J ˉ ( θ ( t ) ) ⟩ = ∥ ∇ J ˉ ( θ ( t ) ) ∥ 2 ≥ 0. \frac{d}{dt}\,\bar J(\theta(t))
\;=\;
\big\langle \nabla \bar J(\theta(t)),\, \nabla \bar J(\theta(t)) \big\rangle
\;=\;
\big\|\nabla \bar J(\theta(t))\big\|^2
\;\ge\; 0. d t d J ˉ ( θ ( t )) = ⟨ ∇ J ˉ ( θ ( t )) , ∇ J ˉ ( θ ( t )) ⟩ = ∇ J ˉ ( θ ( t )) 2 ≥ 0. Therefore J ˉ ( θ ( t ) ) \bar J(\theta(t)) J ˉ ( θ ( t )) J ˉ \bar J J ˉ ∇ J ˉ ( θ ) = 0 \nabla \bar J(\theta) = 0 ∇ J ˉ ( θ ) = 0
{ θ : ∇ J ˉ ( θ ) = 0 } . \{\theta : \nabla \bar J(\theta) = 0\}. { θ : ∇ J ˉ ( θ ) = 0 } . Since the stochastic iterates { θ i } \{\theta_i\} { θ i }
∇ J ˉ ( θ ∞ ) = 0. \nabla \bar J(\theta_\infty) = 0. ∇ J ˉ ( θ ∞ ) = 0. Equivalently,
∇ θ J ˉ ( θ ∞ , φ ∗ ( θ ∞ ) ) = 0 , \nabla_\theta \bar J\bigl(\theta_\infty, \varphi^*(\theta_\infty)\bigr) = 0, ∇ θ J ˉ ( θ ∞ , φ ∗ ( θ ∞ ) ) = 0 , This completes the proof. ◻
Projection Error Analysis.
In Algorithm alg:projected-ppo , the projection objective is estimated from a finite batch of rollout samples, and the projector is learned approximately using a neural network. As a result, the learned projection may deviate from the exact population projector. We next quantify this approximation error. Fix the policy parameter θ \theta θ l ( φ , θ ) : = Ω π θ ∗ ( r − F Φ φ ) l(\varphi,\theta) := \Omega^*_{\pi_\theta}\!\bigl(r - F_{\Phi_\varphi}\bigr) l ( φ , θ ) := Ω π θ ∗ ( r − F Φ φ ) alg:projected-ppo , and Let l ( φ , θ ; τ ) l(\varphi,\theta;\tau) l ( φ , θ ; τ ) τ \tau τ
L ( φ , θ ) : = E [ l ( φ , θ ; τ ) ∣ θ ] , τ ∼ D π θ . L(\varphi,\theta)
:=
\mathbb E\!\left[
l(\varphi,\theta;\tau)\mid \theta
\right],
\qquad
\tau\sim\mathcal D_{\pi_\theta}. L ( φ , θ ) := E [ l ( φ , θ ; τ ) ∣ θ ] , τ ∼ D π θ . Given N N N τ 1 , … , τ N ∼ D π θ \tau_1,\ldots,\tau_N\sim\mathcal D_{\pi_\theta} τ 1 , … , τ N ∼ D π θ
L ^ ( φ , θ ) : = 1 N ∑ n = 1 N l ( φ , θ ; τ n ) . \hat L(\varphi,\theta)
:=
\frac{1}{N}\sum_{n=1}^{N}l(\varphi,\theta;\tau_n). L ^ ( φ , θ ) := N 1 n = 1 ∑ N l ( φ , θ ; τ n ) . We make the following standard assumptions:
Assumption C.18. The projection parameters φ \varphi φ Ψ ⊂ R p \Psi\subset\mathbb R^p Ψ ⊂ R p p p p R > 0 R>0 R > 0 ∥ φ ∥ 2 ≤ R , ∀ φ ∈ Ψ , \|\varphi\|_2\le R,\qquad \forall \varphi\in\Psi, ∥ φ ∥ 2 ≤ R , ∀ φ ∈ Ψ ,
This is similar to Assumption C.10 . Here, we assume that the projection parameter φ \varphi φ
Assumption C.19. For fixed θ \theta θ B ℓ > 0 B_\ell>0 B ℓ > 0 φ ∈ Ψ \varphi\in\Psi φ ∈ Ψ τ \tau τ ∣ l ( φ , θ ; τ ) ∣ ≤ B ℓ . |l(\varphi,\theta;\tau)|\le B_\ell . ∣ l ( φ , θ ; τ ) ∣ ≤ B ℓ .
This is a standard bounded-loss assumption, which allows us to control the finite-sample estimation error of the projection objective.
Assumption C.20. For fixed θ \theta θ L ^ ( ⋅ , θ ) \hat L(\cdot,\theta) L ^ ( ⋅ , θ ) Ψ \Psi Ψ G φ > 0 G_\varphi>0 G φ > 0 φ , φ ′ ∈ Ψ \varphi,\varphi'\in\Psi φ , φ ′ ∈ Ψ ∣ L ^ ( φ , θ ) − L ^ ( φ ′ , θ ) ∣ ≤ G φ ∥ φ − φ ′ ∥ 2 . |\hat L(\varphi,\theta)-\hat L(\varphi',\theta)|
\le
G_\varphi\|\varphi-\varphi'\|_2 . ∣ L ^ ( φ , θ ) − L ^ ( φ ′ , θ ) ∣ ≤ G φ ∥ φ − φ ′ ∥ 2 .
This is the empirical-objective counterpart of Assumption C.12 , which imposes regularity on the population projection objective. Here, we similarly assume that the empirical projection objective is Lipschitz.
Theorem C.21. Under Assumption C.18 , C.19 , C.20 and C.12 , let φ ⋆ ∈ arg min φ ∈ Ψ L ( φ , θ ) , φ ^ ∈ arg min φ ∈ Ψ L ^ ( φ , θ ) . \varphi^\star\in\arg\min_{\varphi\in\Psi}L(\varphi,\theta),
\qquad
\hat\varphi\in\arg\min_{\varphi\in\Psi}\hat L(\varphi,\theta). φ ⋆ ∈ arg min φ ∈ Ψ L ( φ , θ ) , φ ^ ∈ arg min φ ∈ Ψ L ^ ( φ , θ ) . θ \theta θ 1 − δ 1-\delta 1 − δ L ( φ ^ , θ ) − L ( φ ⋆ , θ ) = O ( p log N + log ( 1 / δ ) N ) . L(\hat\varphi,\theta)-L(\varphi^\star,\theta)
=
\mathcal O\left(
\sqrt{
\frac{
p\log N+\log(1/\delta)
}{N}
}
\right). L ( φ ^ , θ ) − L ( φ ⋆ , θ ) = O ( N p l o g N + l o g ( 1/ δ ) ) .
Proof. Fix θ \theta θ φ ∈ Ψ \varphi\in\Psi φ ∈ Ψ
l ( φ , θ ; τ 1 ) , … , l ( φ , θ ; τ N ) l(\varphi,\theta;\tau_1),\ldots,l(\varphi,\theta;\tau_N) l ( φ , θ ; τ 1 ) , … , l ( φ , θ ; τ N ) are i.i.d. under the rollout distribution D π θ \mathcal D_{\pi_\theta} D π θ C.19 , each of them is bounded in [ − B l , B l ] [-B_l,B_l] [ − B l , B l ] [98 ] says that if l ( φ , θ ; τ n ) ∈ [ a n , b n ] l(\varphi,\theta;\tau_n) \in [a_n, b_n] l ( φ , θ ; τ n ) ∈ [ a n , b n ]
Pr ( ∣ ∑ n = 1 N l ( φ , θ ; τ n ) − E ∑ n = 1 N l ( φ , θ ; τ n ) ∣ ≥ t ) ≤ 2 exp ( − 2 t 2 ∑ n = 1 N ( b n − a n ) 2 ) . \Pr\!\left(\left|\sum_{n=1}^{N} l(\varphi,\theta;\tau_n)-\mathbb{E}\sum_{n=1}^{N}l(\varphi,\theta;\tau_n)\right|\ge t\right)
\le
2\exp\!\left(
-\frac{2t^2}{\sum_{n=1}^{N}(b_n-a_n)^2}
\right). Pr ( n = 1 ∑ N l ( φ , θ ; τ n ) − E n = 1 ∑ N l ( φ , θ ; τ n ) ≥ t ) ≤ 2 exp ( − ∑ n = 1 N ( b n − a n ) 2 2 t 2 ) . Here a n = − B ℓ a_n=-B_\ell a n = − B ℓ b n = B ℓ b_n=B_\ell b n = B ℓ b n − a n = 2 B ℓ b_n-a_n=2B_\ell b n − a n = 2 B ℓ
∑ n = 1 N ( b n − a n ) 2 = 4 N B ℓ 2 . \sum_{n=1}^{N}(b_n-a_n)^2 = 4N B_\ell^2. n = 1 ∑ N ( b n − a n ) 2 = 4 N B ℓ 2 . Thus,
Pr ( ∣ ∑ n = 1 N l ( φ , θ ; τ n ) − E ∑ n = 1 N l ( φ , θ ; τ n ) ∣ ≥ t ) ≤ 2 exp ( − t 2 2 N B ℓ 2 ) . \Pr\!\left(\left|\sum_{n=1}^{N} l(\varphi,\theta;\tau_n)-\mathbb{E}\sum_{n=1}^{N}l(\varphi,\theta;\tau_n)\right|\ge t\right)
\le
2\exp\!\left(-\frac{t^2}{2N B_\ell^2}\right). Pr ( n = 1 ∑ N l ( φ , θ ; τ n ) − E n = 1 ∑ N l ( φ , θ ; τ n ) ≥ t ) ≤ 2 exp ( − 2 N B ℓ 2 t 2 ) . Now divide by N N N
L ^ ( φ , θ ) = 1 N ∑ n = 1 N l ( φ , θ ; τ n ) , L ( φ , θ ) = E [ l ( φ , θ ; τ n ) ] , \hat L(\varphi,\theta)=\frac{1}{N}\sum_{n=1}^{N}l(\varphi,\theta;\tau_n),
\qquad
L(\varphi,\theta)=\mathbb{E}[l(\varphi,\theta;\tau_n)], L ^ ( φ , θ ) = N 1 n = 1 ∑ N l ( φ , θ ; τ n ) , L ( φ , θ ) = E [ l ( φ , θ ; τ n )] , we have
∣ L ^ ( φ , θ ) − L ( φ , θ ) ∣ = 1 N ∣ ∑ n = 1 N l ( φ , θ ; τ n ) − E ∑ n = 1 N l ( φ , θ ; τ n ) ∣ . \bigl|\hat L(\varphi,\theta)-L(\varphi,\theta)\bigr|
=
\frac{1}{N}\left|\sum_{n=1}^{N}l(\varphi,\theta;\tau_n)-\mathbb{E}\sum_{n=1}^{N}l(\varphi,\theta;\tau_n)\right|. L ^ ( φ , θ ) − L ( φ , θ ) = N 1 n = 1 ∑ N l ( φ , θ ; τ n ) − E n = 1 ∑ N l ( φ , θ ; τ n ) . Setting t = N ε t=N\varepsilon t = N ε
Pr ( ∣ L ^ ( φ , θ ) − L ( φ , θ ) ∣ ≥ ε ) ≤ 2 exp ( − N ε 2 2 B ℓ 2 ) . \Pr\!\left(\bigl|\hat L(\varphi,\theta)-L(\varphi,\theta)\bigr|\ge \varepsilon\right)
\le
2\exp\!\left(-\frac{N\varepsilon^2}{2B_\ell^2}\right). Pr ( L ^ ( φ , θ ) − L ( φ , θ ) ≥ ε ) ≤ 2 exp ( − 2 B ℓ 2 N ε 2 ) . Now set the right-hand side equal to δ \delta δ
2 exp ( − N ε 2 2 B ℓ 2 ) = δ . 2\exp\!\left(-\frac{N\varepsilon^2}{2B_\ell^2}\right)=\delta. 2 exp ( − 2 B ℓ 2 N ε 2 ) = δ . Solving for ε \varepsilon ε
ε = B ℓ 2 log ( 2 / δ ) N . \varepsilon
=
B_\ell\sqrt{\frac{2\log(2/\delta)}{N}}. ε = B ℓ N 2 log ( 2/ δ ) . Therefore, for any fixed φ \varphi φ 1 − δ 1-\delta 1 − δ
∣ L ^ ( φ , θ ) − L ( φ , θ ) ∣ ≤ B ℓ 2 log ( 2 / δ ) N . \bigl|\hat L(\varphi,\theta)-L(\varphi,\theta)\bigr|
\le
B_\ell\sqrt{\frac{2\log(2/\delta)}{N}}. L ^ ( φ , θ ) − L ( φ , θ ) ≤ B ℓ N 2 log ( 2/ δ ) . Notice that this is a pointwise concentration bound, as it holds for one fixed value of φ \varphi φ φ ∈ Ψ \varphi\in\Psi φ ∈ Ψ [99 ] . Let N ρ ⊂ Ψ \mathcal N_\rho\subset\Psi N ρ ⊂ Ψ ρ \rho ρ Ψ \Psi Ψ φ ∈ Ψ \varphi\in\Psi φ ∈ Ψ φ ρ ∈ N ρ \varphi_\rho\in\mathcal N_\rho φ ρ ∈ N ρ
∥ φ − φ ρ ∥ 2 ≤ ρ . \|\varphi-\varphi_\rho\|_2\le \rho . ∥ φ − φ ρ ∥ 2 ≤ ρ . Since Ψ ⊂ R p \Psi\subset\mathbb R^p Ψ ⊂ R p R R R C.18 , every φ ∈ Ψ \varphi\in\Psi φ ∈ Ψ
B 2 ( R ) = { φ ∈ R p : ∥ φ ∥ 2 ≤ R } . B_2(R)=\{\varphi\in\mathbb{R}^p:\ \|\varphi\|_2\le R\}. B 2 ( R ) = { φ ∈ R p : ∥ φ ∥ 2 ≤ R } . So it is enough to cover the larger set B 2 ( R ) B_2(R) B 2 ( R ) B 2 ( R ) B_2(R) B 2 ( R ) Ψ \Psi Ψ [99 ] ), the radius-R R R R p \mathbb R^p R p ρ \rho ρ
( 1 + 2 R ρ ) p . \left(1+\frac{2R}{\rho}\right)^p . ( 1 + ρ 2 R ) p . For ρ ≤ R \rho\le R ρ ≤ R
( 3 R ρ ) p . \left(\frac{3R}{\rho}\right)^p . ( ρ 3 R ) p . Thus we may choose N ρ \mathcal N_\rho N ρ
∣ N ρ ∣ ≤ ( 3 R ρ ) p . |\mathcal N_\rho|
\le
\left(\frac{3R}{\rho}\right)^p . ∣ N ρ ∣ ≤ ( ρ 3 R ) p . Intuitively, the factor R / ρ R/\rho R / ρ p p p p p p
Now apply the pointwise concentration bound to each element of N ρ \mathcal N_\rho N ρ φ ∈ N ρ \varphi\in\mathcal N_\rho φ ∈ N ρ
Pr ( ∣ L ^ ( φ , θ ) − L ( φ , θ ) ∣ ≥ ε ) ≤ 2 exp ( − N ε 2 2 B ℓ 2 ) . \Pr\!\left(
\bigl|\hat L(\varphi,\theta)-L(\varphi,\theta)\bigr|
\ge \varepsilon
\right)
\le
2\exp\!\left(-\frac{N\varepsilon^2}{2B_\ell^2}\right). Pr ( L ^ ( φ , θ ) − L ( φ , θ ) ≥ ε ) ≤ 2 exp ( − 2 B ℓ 2 N ε 2 ) . Therefore,
Pr ( sup φ ∈ N ρ ∣ L ^ ( φ , θ ) − L ( φ , θ ) ∣ ≥ ε ) ≤ ∑ φ ∈ N ρ Pr ( ∣ L ^ ( φ , θ ) − L ( φ , θ ) ∣ ≥ ε ) ≤ 2 ∣ N ρ ∣ exp ( − N ε 2 2 B ℓ 2 ) . \begin{aligned}
&\Pr\!\left(
\sup_{\varphi\in\mathcal N_\rho}
\bigl|\hat L(\varphi,\theta)-L(\varphi,\theta)\bigr|
\ge \varepsilon
\right) \\
&\le
\sum_{\varphi\in\mathcal N_\rho}
\Pr\!\left(
\bigl|\hat L(\varphi,\theta)-L(\varphi,\theta)\bigr|
\ge \varepsilon
\right) \\
&\le
2|\mathcal N_\rho|
\exp\!\left(-\frac{N\varepsilon^2}{2B_\ell^2}\right).
\end{aligned} Pr ( φ ∈ N ρ sup L ^ ( φ , θ ) − L ( φ , θ ) ≥ ε ) ≤ φ ∈ N ρ ∑ Pr ( L ^ ( φ , θ ) − L ( φ , θ ) ≥ ε ) ≤ 2∣ N ρ ∣ exp ( − 2 B ℓ 2 N ε 2 ) . Using
∣ N ρ ∣ ≤ ( 3 R ρ ) p , |\mathcal N_\rho|
\le
\left(\frac{3R}{\rho}\right)^p, ∣ N ρ ∣ ≤ ( ρ 3 R ) p , we obtain
Pr ( sup φ ∈ N ρ ∣ L ^ ( φ , θ ) − L ( φ , θ ) ∣ ≥ ε ) ≤ 2 exp ( p log ( 3 R / ρ ) − N ε 2 2 B ℓ 2 ) . \Pr\!\left(
\sup_{\varphi\in\mathcal N_\rho}
\bigl|\hat L(\varphi,\theta)-L(\varphi,\theta)\bigr|
\ge \varepsilon
\right)
\le
2
\exp\!\left(
p\log(3R/\rho)
-
\frac{N\varepsilon^2}{2B_\ell^2}
\right). Pr ( φ ∈ N ρ sup L ^ ( φ , θ ) − L ( φ , θ ) ≥ ε ) ≤ 2 exp ( p log ( 3 R / ρ ) − 2 B ℓ 2 N ε 2 ) . Set the right-hand side equal to δ \delta δ
2 exp ( p log ( 3 R / ρ ) − N ε 2 2 B ℓ 2 ) = δ . 2
\exp\!\left(
p\log(3R/\rho)
-
\frac{N\varepsilon^2}{2B_\ell^2}
\right)
=
\delta. 2 exp ( p log ( 3 R / ρ ) − 2 B ℓ 2 N ε 2 ) = δ . Solving for ε \varepsilon ε
ε = B ℓ 2 ( p log ( 3 R / ρ ) + log ( 2 / δ ) ) N . \varepsilon
=
B_\ell
\sqrt{
\frac{
2\left(p\log(3R/\rho)+\log(2/\delta)\right)
}{N}
}. ε = B ℓ N 2 ( p log ( 3 R / ρ ) + log ( 2/ δ ) ) . Thus, with probability at least 1 − δ 1-\delta 1 − δ
sup φ ∈ N ρ ∣ L ^ ( φ , θ ) − L ( φ , θ ) ∣ ≤ B ℓ 2 ( p log ( 3 R / ρ ) + log ( 2 / δ ) ) N . \sup_{\varphi\in\mathcal N_\rho}
\bigl|
\hat L(\varphi,\theta)-L(\varphi,\theta)
\bigr|
\le
B_\ell
\sqrt{
\frac{
2\left(p\log(3R/\rho)+\log(2/\delta)\right)
}{N}
}. φ ∈ N ρ sup L ^ ( φ , θ ) − L ( φ , θ ) ≤ B ℓ N 2 ( p log ( 3 R / ρ ) + log ( 2/ δ ) ) . It remains to extend the bound from the finite cover N ρ \mathcal N_\rho N ρ Ψ \Psi Ψ C.12 , L ( ⋅ , θ ) L(\cdot,\theta) L ( ⋅ , θ ) L φ L_\varphi L φ φ \varphi φ Ψ \Psi Ψ C.20 , L ^ ( ⋅ , θ ) \hat L(\cdot,\theta) L ^ ( ⋅ , θ ) G φ G_\varphi G φ φ \varphi φ Ψ \Psi Ψ
L ˉ φ : = max { L φ , G φ } . \bar L_\varphi := \max\{L_\varphi,G_\varphi\}. L ˉ φ := max { L φ , G φ } . Then, for any φ ∈ Ψ \varphi\in\Psi φ ∈ Ψ φ ρ ∈ N ρ \varphi_\rho\in\mathcal N_\rho φ ρ ∈ N ρ
∥ φ − φ ρ ∥ 2 ≤ ρ . \|\varphi-\varphi_\rho\|_2\le \rho . ∥ φ − φ ρ ∥ 2 ≤ ρ . We have
∣ L ( φ , θ ) − L ( φ ρ , θ ) ∣ ≤ L φ ρ ≤ L ˉ φ ρ , \left|
L(\varphi,\theta)-L(\varphi_\rho,\theta)
\right|
\le
L_\varphi\rho
\le
\bar L_\varphi\rho, ∣ L ( φ , θ ) − L ( φ ρ , θ ) ∣ ≤ L φ ρ ≤ L ˉ φ ρ , and
∣ L ^ ( φ , θ ) − L ^ ( φ ρ , θ ) ∣ ≤ G φ ρ ≤ L ˉ φ ρ . \left|
\hat L(\varphi,\theta)-\hat L(\varphi_\rho,\theta)
\right|
\le
G_\varphi\rho
\le
\bar L_\varphi\rho. L ^ ( φ , θ ) − L ^ ( φ ρ , θ ) ≤ G φ ρ ≤ L ˉ φ ρ . Therefore,
∣ L ^ ( φ , θ ) − L ( φ , θ ) ∣ ≤ ∣ L ^ ( φ ρ , θ ) − L ( φ ρ , θ ) ∣ + ∣ L ^ ( φ , θ ) − L ^ ( φ ρ , θ ) ∣ + ∣ L ( φ , θ ) − L ( φ ρ , θ ) ∣ ≤ sup φ ′ ∈ N ρ ∣ L ^ ( φ ′ , θ ) − L ( φ ′ , θ ) ∣ + 2 L ˉ φ ρ . \begin{aligned}
\left|
\hat L(\varphi,\theta)-L(\varphi,\theta)
\right|
&\le
\left|
\hat L(\varphi_\rho,\theta)-L(\varphi_\rho,\theta)
\right|\\
&\quad+
\left|
\hat L(\varphi,\theta)-\hat L(\varphi_\rho,\theta)
\right|
+
\left|
L(\varphi,\theta)-L(\varphi_\rho,\theta)
\right|\\
&\le
\sup_{\varphi'\in\mathcal N_\rho}
\left|
\hat L(\varphi',\theta)-L(\varphi',\theta)
\right|
+
2\bar L_\varphi\rho .
\end{aligned} L ^ ( φ , θ ) − L ( φ , θ ) ≤ L ^ ( φ ρ , θ ) − L ( φ ρ , θ ) + L ^ ( φ , θ ) − L ^ ( φ ρ , θ ) + ∣ L ( φ , θ ) − L ( φ ρ , θ ) ∣ ≤ φ ′ ∈ N ρ sup L ^ ( φ ′ , θ ) − L ( φ ′ , θ ) + 2 L ˉ φ ρ . Taking the supremum over φ ∈ Ψ \varphi\in\Psi φ ∈ Ψ 1 − δ 1-\delta 1 − δ
sup φ ∈ Ψ ∣ L ^ ( φ , θ ) − L ( φ , θ ) ∣ ≤ B ℓ 2 ( p log ( 3 R / ρ ) + log ( 2 / δ ) ) N + 2 L ˉ φ ρ . \sup_{\varphi\in\Psi}
\left|
\hat L(\varphi,\theta)-L(\varphi,\theta)
\right|
\le
B_\ell
\sqrt{
\frac{
2\left(p\log(3R/\rho)+\log(2/\delta)\right)
}{N}
}
+
2\bar L_\varphi\rho . φ ∈ Ψ sup L ^ ( φ , θ ) − L ( φ , θ ) ≤ B ℓ N 2 ( p log ( 3 R / ρ ) + log ( 2/ δ ) ) + 2 L ˉ φ ρ . Now choose
ρ = N − 1 / 2 . \rho=N^{-1/2}. ρ = N − 1/2 . Then
p log ( 3 R / ρ ) = p log ( 3 R N ) = p log ( 3 R ) + p 2 log N = O ( p log N ) . p\log(3R/\rho)
=
p\log(3R\sqrt N)
=
p\log(3R)+\frac{p}{2}\log N
=
\mathcal O(p\log N). p log ( 3 R / ρ ) = p log ( 3 R N ) = p log ( 3 R ) + 2 p log N = O ( p log N ) . Moreover,
2 L ˉ φ ρ = 2 L ˉ φ N = O ( 1 N ) ≤ O ( p log N + log ( 1 / δ ) N ) , 2\bar L_\varphi\rho
=
\frac{2\bar L_\varphi}{\sqrt N}
=
\mathcal O\left(\sqrt{\frac{1}{N}}\right)
\le
\mathcal O\left(
\sqrt{
\frac{
p\log N+\log(1/\delta)
}{N}
}
\right), 2 L ˉ φ ρ = N 2 L ˉ φ = O ( N 1 ) ≤ O ( N p log N + log ( 1/ δ ) ) , for p ≥ 1 p\ge 1 p ≥ 1 N ≥ 2 N\ge 2 N ≥ 2 δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 )
sup φ ∈ Ψ ∣ L ^ ( φ , θ ) − L ( φ , θ ) ∣ = O ( p log N + log ( 1 / δ ) N ) . \sup_{\varphi\in\Psi}
\left|
\hat L(\varphi,\theta)-L(\varphi,\theta)
\right|
=
\mathcal O\left(
\sqrt{
\frac{
p\log N+\log(1/\delta)
}{N}
}
\right). φ ∈ Ψ sup L ^ ( φ , θ ) − L ( φ , θ ) = O ( N p log N + log ( 1/ δ ) ) . Since absolute value is symmetric, this is equivalent to
sup φ ∈ Ψ ∣ L ( φ , θ ) − L ^ ( φ , θ ) ∣ = O ( p log N + log ( 1 / δ ) N ) . \sup_{\varphi\in\Psi}
\left|
L(\varphi,\theta)-\hat L(\varphi,\theta)
\right|
=
\mathcal O\left(
\sqrt{
\frac{
p\log N+\log(1/\delta)
}{N}
}
\right). φ ∈ Ψ sup L ( φ , θ ) − L ^ ( φ , θ ) = O ( N p log N + log ( 1/ δ ) ) . Since
φ ⋆ ∈ arg min φ ∈ Ψ L ( φ , θ ) , φ ^ ∈ arg min φ ∈ Ψ L ^ ( φ , θ ) , \varphi^\star\in\arg\min_{\varphi\in\Psi}L(\varphi,\theta),
\qquad
\hat\varphi\in\arg\min_{\varphi\in\Psi}\hat L(\varphi,\theta), φ ⋆ ∈ arg φ ∈ Ψ min L ( φ , θ ) , φ ^ ∈ arg φ ∈ Ψ min L ^ ( φ , θ ) , we have
L ( φ ^ , θ ) − L ( φ ⋆ , θ ) = [ L ( φ ^ , θ ) − L ^ ( φ ^ , θ ) ] + [ L ^ ( φ ^ , θ ) − L ^ ( φ ⋆ , θ ) ] + [ L ^ ( φ ⋆ , θ ) − L ( φ ⋆ , θ ) ] . \begin{aligned}
L(\hat\varphi,\theta)-L(\varphi^\star,\theta)
&=
\bigl[L(\hat\varphi,\theta)-\hat L(\hat\varphi,\theta)\bigr]
+
\bigl[\hat L(\hat\varphi,\theta)-\hat L(\varphi^\star,\theta)\bigr] \\
&\quad+
\bigl[\hat L(\varphi^\star,\theta)-L(\varphi^\star,\theta)\bigr].
\end{aligned} L ( φ ^ , θ ) − L ( φ ⋆ , θ ) = [ L ( φ ^ , θ ) − L ^ ( φ ^ , θ ) ] + [ L ^ ( φ ^ , θ ) − L ^ ( φ ⋆ , θ ) ] + [ L ^ ( φ ⋆ , θ ) − L ( φ ⋆ , θ ) ] . Because φ ^ \hat\varphi φ ^ L ^ ( ⋅ , θ ) \hat L(\cdot,\theta) L ^ ( ⋅ , θ )
L ^ ( φ ^ , θ ) − L ^ ( φ ⋆ , θ ) ≤ 0. \hat L(\hat\varphi,\theta)-\hat L(\varphi^\star,\theta)\le 0. L ^ ( φ ^ , θ ) − L ^ ( φ ⋆ , θ ) ≤ 0. Therefore,
L ( φ ^ , θ ) − L ( φ ⋆ , θ ) ≤ 2 sup φ ∈ Ψ ∣ L ( φ , θ ) − L ^ ( φ , θ ) ∣ . L(\hat\varphi,\theta)-L(\varphi^\star,\theta)
\le
2\sup_{\varphi\in\Psi}
\left|
L(\varphi,\theta)-\hat L(\varphi,\theta)
\right|. L ( φ ^ , θ ) − L ( φ ⋆ , θ ) ≤ 2 φ ∈ Ψ sup L ( φ , θ ) − L ^ ( φ , θ ) . Combining this with the previous uniform convergence bound gives, with probability at least 1 − δ 1-\delta 1 − δ
L ( φ ^ , θ ) − L ( φ ⋆ , θ ) = O ( p log N + log ( 1 / δ ) N ) . L(\hat\varphi,\theta)-L(\varphi^\star,\theta)
=
\mathcal O\left(
\sqrt{
\frac{
p\log N+\log(1/\delta)
}{N}
}
\right). L ( φ ^ , θ ) − L ( φ ⋆ , θ ) = O ( N p log N + log ( 1/ δ ) ) . This completes the proof. ◻
Notice that the proof does not require the strong convexity part of Assumption C.12 . It only uses the Lipschitz regularity of the projection objectives. Theorem C.21 shows that the statistical complexity of projection learning does not scale directly with the size of the state-action space, but instead with the dimension p p p N N N N N N 1 / N 1/\sqrt{N} 1/ N log ( 1 / δ ) \log(1/\delta) log ( 1/ δ )
Next, we translate the projection-objective error into a bound on the distance between the exact projected reward and its empirical approximation. We use the following regularity assumption:
Assumption C.22. There exists L F > 0 L_F>0 L F > 0 φ , φ ′ ∈ Ψ \varphi,\varphi'\in\Psi φ , φ ′ ∈ Ψ ∥ F Φ φ − F Φ φ ′ ∥ ≤ L F ∥ φ − φ ′ ∥ 2 . \left\|
F_{\Phi_\varphi}-F_{\Phi_{\varphi'}}
\right\|
\le
L_F\|\varphi-\varphi'\|_2 . F Φ φ − F Φ φ ′ ≤ L F ∥ φ − φ ′ ∥ 2 .
This is a standard assumption ensuring that the potential function is Lipschitz in the projection parameter.
Theorem C.23. Fix θ \theta θ r c o r e : = r − F Φ φ ⋆ , r ^ c o r e : = r − F Φ φ ^ . r_{\mathrm{core}}
:=
r-F_{\Phi_{\varphi^\star}},
\qquad
\hat r_{\mathrm{core}}
:=
r-F_{\Phi_{\hat\varphi}}. r core := r − F Φ φ ⋆ , r ^ core := r − F Φ φ ^ . C.18 , C.19 , C.20 , C.12 , and C.22 , with probability at least 1 − δ 1-\delta 1 − δ ∥ r ^ c o r e − r c o r e ∥ = O ( ( p log N + log ( 1 / δ ) N ) 1 / 4 ) . \left\|
\hat r_{\mathrm{core}}-r_{\mathrm{core}}
\right\|
=
\mathcal O\!\left(
\left(
\frac{
p\log N+\log(1/\delta)
}{N}
\right)^{1/4}
\right). ∥ r ^ core − r core ∥ = O ( ( N p l o g N + l o g ( 1/ δ ) ) 1/4 ) .
Proof. By Theorem C.21 , with probability at least 1 − δ 1-\delta 1 − δ
L ( φ ^ , θ ) − L ( φ ⋆ , θ ) = O ( p log N + log ( 1 / δ ) N ) . L(\hat\varphi,\theta)-L(\varphi^\star,\theta)
=
\mathcal O\!\left(
\sqrt{
\frac{
p\log N+\log(1/\delta)
}{N}
}
\right). L ( φ ^ , θ ) − L ( φ ⋆ , θ ) = O ( N p log N + log ( 1/ δ ) ) . Since L ( ⋅ , θ ) L(\cdot,\theta) L ( ⋅ , θ ) μ \mu μ φ \varphi φ C.12 , and φ ⋆ \varphi^\star φ ⋆ L ( ⋅ , θ ) L(\cdot,\theta) L ( ⋅ , θ )
L ( φ ^ , θ ) − L ( φ ⋆ , θ ) ≥ μ 2 ∥ φ ^ − φ ⋆ ∥ 2 2 . L(\hat\varphi,\theta)-L(\varphi^\star,\theta)
\ge
\frac{\mu}{2}
\|\hat\varphi-\varphi^\star\|_2^2 . L ( φ ^ , θ ) − L ( φ ⋆ , θ ) ≥ 2 μ ∥ φ ^ − φ ⋆ ∥ 2 2 . Therefore,
∥ φ ^ − φ ⋆ ∥ 2 ≤ 2 μ ( L ( φ ^ , θ ) − L ( φ ⋆ , θ ) ) . \|\hat\varphi-\varphi^\star\|_2
\le
\sqrt{
\frac{2}{\mu}
\left(
L(\hat\varphi,\theta)-L(\varphi^\star,\theta)
\right)
}. ∥ φ ^ − φ ⋆ ∥ 2 ≤ μ 2 ( L ( φ ^ , θ ) − L ( φ ⋆ , θ ) ) . Combining this with Theorem C.21 gives
∥ φ ^ − φ ⋆ ∥ 2 = O ( ( p log N + log ( 1 / δ ) N ) 1 / 4 ) . \|\hat\varphi-\varphi^\star\|_2
=
\mathcal O\!\left(
\left(
\frac{
p\log N+\log(1/\delta)
}{N}
\right)^{1/4}
\right). ∥ φ ^ − φ ⋆ ∥ 2 = O ( ( N p log N + log ( 1/ δ ) ) 1/4 ) . Finally, by the Lipschitzness of the potential function in Assumption C.22 ,
∥ r ^ c o r e − r c o r e ∥ = ∥ ( r − F Φ φ ^ ) − ( r − F Φ φ ⋆ ) ∥ = ∥ F Φ φ ⋆ − F Φ φ ^ ∥ ≤ L F ∥ φ ^ − φ ⋆ ∥ 2 . \begin{aligned}
\left\|
\hat r_{\mathrm{core}}-r_{\mathrm{core}}
\right\|
&=
\left\|
\bigl(r-F_{\Phi_{\hat\varphi}}\bigr)
-
\bigl(r-F_{\Phi_{\varphi^\star}}\bigr)
\right\| \\
&=
\left\|
F_{\Phi_{\varphi^\star}}-F_{\Phi_{\hat\varphi}}
\right\| \\
&\le
L_F\|\hat\varphi-\varphi^\star\|_2 .
\end{aligned} ∥ r ^ core − r core ∥ = ( r − F Φ φ ^ ) − ( r − F Φ φ ⋆ ) = F Φ φ ⋆ − F Φ φ ^ ≤ L F ∥ φ ^ − φ ⋆ ∥ 2 . Thus,
∥ r ^ c o r e − r c o r e ∥ = O ( ( p log N + log ( 1 / δ ) N ) 1 / 4 ) . \left\|
\hat r_{\mathrm{core}}-r_{\mathrm{core}}
\right\|
=
\mathcal O\!\left(
\left(
\frac{
p\log N+\log(1/\delta)
}{N}
\right)^{1/4}
\right). ∥ r ^ core − r core ∥ = O ( ( N p log N + log ( 1/ δ ) ) 1/4 ) . This completes the proof. ◻
Finally, we quantify how the empirical projection error propagates to the robust objectives in Theorems 4.1 and 4.2 . We begin with a widely used lemma [104 , 105 ] , which will be useful for the analysis.
Lemma C.24. Let r c o r e r_{\mathrm{core}} r core r ^ c o r e \hat r_{\mathrm{core}} r ^ core Δ r : = ∥ r c o r e − r ^ c o r e ∥ . \Delta_r
:=
\|r_{\mathrm{core}}-\hat r_{\mathrm{core}}\| . Δ r := ∥ r core − r ^ core ∥. π \pi π ∣ J ( π , r c o r e ) − J ( π , r ^ c o r e ) ∣ ≤ Δ r 1 − γ . \left|
J(\pi,r_{\mathrm{core}})
-
J(\pi,\hat r_{\mathrm{core}})
\right|
\le
\frac{\Delta_r}{1-\gamma}. ∣ J ( π , r core ) − J ( π , r ^ core ) ∣ ≤ 1 − γ Δ r .
Proof. Define the discounted occupancy measure
d π ( s , a , s ′ ) : = E [ ∑ t = 0 ∞ γ t 1 { s t = s , a t = a , s t + 1 = s ′ } ∣ μ 0 , π , P ] . d_\pi(s,a,s')
:=
\mathbb E\left[
\sum_{t=0}^{\infty}
\gamma^t
\mathbf 1\{s_t=s,a_t=a,s_{t+1}=s'\}
\Bigm|\mu_0,\pi,P
\right]. d π ( s , a , s ′ ) := E [ t = 0 ∑ ∞ γ t 1 { s t = s , a t = a , s t + 1 = s ′ } μ 0 , π , P ] . Then, for any reward r r r
J ( π , r ) = ⟨ d π , r ⟩ . J(\pi,r)=\langle d_\pi,r\rangle. J ( π , r ) = ⟨ d π , r ⟩ . Therefore,
∣ J ( π , r c o r e ) − J ( π , r ^ c o r e ) ∣ = ∣ ⟨ d π , r c o r e − r ^ c o r e ⟩ ∣ ≤ ∥ d π ∥ ∥ r c o r e − r ^ c o r e ∥ . \begin{aligned}
\left|
J(\pi,r_{\mathrm{core}})
-
J(\pi,\hat r_{\mathrm{core}})
\right|
&=
\left|
\left\langle
d_\pi,
r_{\mathrm{core}}-\hat r_{\mathrm{core}}
\right\rangle
\right|\\
&\le
\|d_\pi\|
\,
\|r_{\mathrm{core}}-\hat r_{\mathrm{core}}\| .
\end{aligned} ∣ J ( π , r core ) − J ( π , r ^ core ) ∣ = ∣ ⟨ d π , r core − r ^ core ⟩ ∣ ≤ ∥ d π ∥ ∥ r core − r ^ core ∥. Moreover,
∥ d π ∥ ≤ ∥ d π ∥ 1 = ∑ s , a , s ′ d π ( s , a , s ′ ) = ∑ t = 0 ∞ γ t = 1 1 − γ . \|d_\pi\|
\le
\|d_\pi\|_1
=
\sum_{s,a,s'}d_\pi(s,a,s')
=
\sum_{t=0}^{\infty}\gamma^t
=
\frac{1}{1-\gamma}. ∥ d π ∥ ≤ ∥ d π ∥ 1 = s , a , s ′ ∑ d π ( s , a , s ′ ) = t = 0 ∑ ∞ γ t = 1 − γ 1 . Thus,
∣ J ( π , r c o r e ) − J ( π , r ^ c o r e ) ∣ ≤ ∥ r c o r e − r ^ c o r e ∥ 1 − γ . \left|
J(\pi,r_{\mathrm{core}})
-
J(\pi,\hat r_{\mathrm{core}})
\right|
\le
\frac{
\|r_{\mathrm{core}}-\hat r_{\mathrm{core}}\|
}{1-\gamma}. ∣ J ( π , r core ) − J ( π , r ^ core ) ∣ ≤ 1 − γ ∥ r core − r ^ core ∥ . This completes the proof. ◻
Next, we bound the return difference between the exact projected reward and its empirical approximation.
Lemma C.25. Under the assumptions of Theorem C.23 , with probability at least 1 − δ 1-\delta 1 − δ π \pi π ∣ J ( π , r c o r e ) − J ( π , r ^ c o r e ) ∣ = O ( 1 1 − γ ( p log N + log ( 1 / δ ) N ) 1 / 4 ) . \left|
J(\pi,r_{\mathrm{core}})
-
J(\pi,\hat r_{\mathrm{core}})
\right|
=
\mathcal O\left(
\frac{1}{1-\gamma}
\left(
\frac{
p\log N+\log(1/\delta)
}{N}
\right)^{1/4}
\right). ∣ J ( π , r core ) − J ( π , r ^ core ) ∣ = O ( 1 − γ 1 ( N p l o g N + l o g ( 1/ δ ) ) 1/4 ) .
Proof. By Theorem C.23 , with probability at least 1 − δ 1-\delta 1 − δ
∥ r c o r e − r ^ c o r e ∥ 2 = O ( ( p log N + log ( 1 / δ ) N ) 1 / 4 ) . \|r_{\mathrm{core}}-\hat r_{\mathrm{core}}\|_2
=
\mathcal O\left(
\left(
\frac{
p\log N+\log(1/\delta)
}{N}
\right)^{1/4}
\right). ∥ r core − r ^ core ∥ 2 = O ( ( N p log N + log ( 1/ δ ) ) 1/4 ) . Combining this with Lemma C.24 gives
∣ J ( π , r c o r e ) − J ( π , r ^ c o r e ) ∣ = O ( 1 1 − γ ( p log N + log ( 1 / δ ) N ) 1 / 4 ) . \left|
J(\pi,r_{\mathrm{core}})
-
J(\pi,\hat r_{\mathrm{core}})
\right|
=
\mathcal O\left(
\frac{1}{1-\gamma}
\left(
\frac{
p\log N+\log(1/\delta)
}{N}
\right)^{1/4}
\right). ∣ J ( π , r core ) − J ( π , r ^ core ) ∣ = O ( 1 − γ 1 ( N p log N + log ( 1/ δ ) ) 1/4 ) . ◻
Theorem. Under the assumptions of Lemma C.25 , with probability at least 1 − δ 1-\delta 1 − δ π \pi π min r ~ c o r e ∈ U c o r e J ( π , r ~ c o r e ) ≥ J ( π , r ^ c o r e ) − λ Ω ( π ) − λ ϵ − α N , \min_{\tilde r_{\mathrm{core}}\in\mathcal U_{\mathrm{core}}}
J(\pi,\tilde r_{\mathrm{core}})
\ge
J(\pi,\hat r_{\mathrm{core}})
-
\lambda\Omega(\pi)
-
\lambda\epsilon
-
\alpha_N, min r ~ core ∈ U core J ( π , r ~ core ) ≥ J ( π , r ^ core ) − λ Ω ( π ) − λ ϵ − α N , α N : = O ( 1 1 − γ ( p log N + log ( 1 / δ ) N ) 1 / 4 ) . \alpha_N
:=
\mathcal O\left(
\frac{1}{1-\gamma}
\left(
\frac{
p\log N+\log(1/\delta)
}{N}
\right)^{1/4}
\right). α N := O ( 1 − γ 1 ( N p l o g N + l o g ( 1/ δ ) ) 1/4 ) .
Proof. By Theorem 4.1 , for any policy π \pi π
min r ~ c o r e ∈ U c o r e J ( π , r ~ c o r e ) ≥ J ( π , r c o r e ) − λ Ω ( π ) − λ ϵ . \min_{\tilde r_{\mathrm{core}}\in\mathcal U_{\mathrm{core}}}
J(\pi,\tilde r_{\mathrm{core}})
\ge
J(\pi,r_{\mathrm{core}})
-
\lambda\Omega(\pi)
-
\lambda\epsilon. r ~ core ∈ U core min J ( π , r ~ core ) ≥ J ( π , r core ) − λ Ω ( π ) − λ ϵ . By Lemma C.25 ,
J ( π , r c o r e ) ≥ J ( π , r ^ c o r e ) − α N . J(\pi,r_{\mathrm{core}})
\ge
J(\pi,\hat r_{\mathrm{core}})-\alpha_N. J ( π , r core ) ≥ J ( π , r ^ core ) − α N . Substituting this into the previous inequality gives
min r ~ c o r e ∈ U c o r e J ( π , r ~ c o r e ) ≥ J ( π , r ^ c o r e ) − λ Ω ( π ) − λ ϵ − α N . \min_{\tilde r_{\mathrm{core}}\in\mathcal U_{\mathrm{core}}}
J(\pi,\tilde r_{\mathrm{core}})
\ge
J(\pi,\hat r_{\mathrm{core}})
-
\lambda\Omega(\pi)
-
\lambda\epsilon
-
\alpha_N. r ~ core ∈ U core min J ( π , r ~ core ) ≥ J ( π , r ^ core ) − λ Ω ( π ) − λ ϵ − α N . This completes the proof. ◻
Theorem (?) shows that using the empirical projected reward r ^ c o r e \hat r_{\mathrm{core}} r ^ core 4.1 . It only introduces an additional finite-sample error term α N \alpha_N α N N N N r ^ c o r e \hat r_{\mathrm{core}} r ^ core
Theorem. Under the assumptions of Lemma C.25 , for the entropy- and KL-induced uncertainty sets in Theorem 4.2 , with probability at least 1 − δ 1-\delta 1 − δ π \pi π ∣ min r ~ c o r e ∈ U c o r e J ( π , r ~ c o r e ) − [ J ( π , r ^ c o r e ) + λ Ω ( π ) − ϵ ] ∣ ≤ O ( 1 1 − γ ( p log N + log ( 1 / δ ) N ) 1 / 4 ) . \left|
\min_{\tilde r_{\mathrm{core}}\in\mathcal U_{\mathrm{core}}}
J(\pi,\tilde r_{\mathrm{core}})
-
\left[
J(\pi,\hat r_{\mathrm{core}})
+
\lambda\Omega(\pi)
-
\epsilon
\right]
\right|
\le
\mathcal O\left(
\frac{1}{1-\gamma}
\left(
\frac{
p\log N+\log(1/\delta)
}{N}
\right)^{1/4}
\right). ∣ min r ~ core ∈ U core J ( π , r ~ core ) − [ J ( π , r ^ core ) + λ Ω ( π ) − ϵ ] ∣ ≤ O ( 1 − γ 1 ( N p l o g N + l o g ( 1/ δ ) ) 1/4 ) .
Proof. By Theorem 4.2 ,
min r ~ c o r e ∈ U c o r e J ( π , r ~ c o r e ) = J ( π , r c o r e ) + λ Ω ( π ) − ϵ . \min_{\tilde r_{\mathrm{core}}\in\mathcal U_{\mathrm{core}}}
J(\pi,\tilde r_{\mathrm{core}})
=
J(\pi,r_{\mathrm{core}})
+
\lambda\Omega(\pi)
-
\epsilon. r ~ core ∈ U core min J ( π , r ~ core ) = J ( π , r core ) + λ Ω ( π ) − ϵ . Therefore,
∣ min r ~ c o r e ∈ U c o r e J ( π , r ~ c o r e ) − [ J ( π , r ^ c o r e ) + λ Ω ( π ) − ϵ ] ∣ = ∣ J ( π , r c o r e ) − J ( π , r ^ c o r e ) ∣ . \begin{aligned}
&\left|
\min_{\tilde r_{\mathrm{core}}\in\mathcal U_{\mathrm{core}}}
J(\pi,\tilde r_{\mathrm{core}})
-
\left[
J(\pi,\hat r_{\mathrm{core}})
+
\lambda\Omega(\pi)
-
\epsilon
\right]
\right|\\
&=
\left|
J(\pi,r_{\mathrm{core}})
-
J(\pi,\hat r_{\mathrm{core}})
\right|.
\end{aligned} r ~ core ∈ U core min J ( π , r ~ core ) − [ J ( π , r ^ core ) + λ Ω ( π ) − ϵ ] = ∣ J ( π , r core ) − J ( π , r ^ core ) ∣ . Applying Lemma C.25 gives the claim. ◻
Theorem (?) shows that, when the projection is learned from finite rollout data, the regularized objective with the empirical projected reward r ^ c o r e \hat r_{\mathrm{core}} r ^ core O ( 1 1 − γ ( p log N + log ( 1 / δ ) N ) 1 / 4 ) . \mathcal O\left(
\frac{1}{1-\gamma}
\left(
\frac{p\log N+\log(1/\delta)}{N}
\right)^{1/4}
\right). O ( 1 − γ 1 ( N p l o g N + l o g ( 1/ δ ) ) 1/4 ) . N N N 4.2 in the large-sample limit. It only introduces a finite-sample approximation error.
Additional Implementation Details
All experiments were conducted on a single NVIDIA RTX 4090 GPU (24GB memory) and a 13th Gen Intel Core i9-13900KF CPU (32 threads). We implemented all methods in Python 3.9 using PyTorch 2.6.0 [24 ] , and SB3 [25 ] .
Implementation Details for MiniGrid
We use a simple deterministic N × N N\times N N × N [9 , 51 ] . As shown in Figure 2 , the agent starts in the top-left cell and aims to reach a fixed goal in the bottom-right cell. The action space consists of four deterministic moves: up, down, left, and right. Attempting to move outside the grid leaves the agent in the same cell. The goal state is terminal and absorbing. Rewards are defined on deterministic transitions. Each non-terminal step incurs a constant step cost of − 0.01 -0.01 − 0.01 1 1 1 γ = 0.99 \gamma=0.99 γ = 0.99
For the robust training, we consider an l 2 l_2 l 2 r r r δ \delta δ
U = { r + δ : ∥ δ ∥ 2 ≤ ε } ⊂ R X ′ . \mathcal{U}=\{r+\delta: \|\delta\|_2\le \varepsilon\} \subset \mathbb{R}^{\mathcal{X'}}. U = { r + δ : ∥ δ ∥ 2 ≤ ε } ⊂ R X ′ . Then the reward-robust objective is the standard max-min problem:
max π min r ~ ∈ U J ( π , r ~ ) \max_{\pi} \min_{\tilde r \in \mathcal{U}} J(\pi, \tilde r) π max r ~ ∈ U min J ( π , r ~ ) To optimize this objective, we use a standard game-style procedure. At each outer iteration i i i π i \pi_i π i δ \delta δ J ( π i , r + δ ) J(\pi_i, r + \delta) J ( π i , r + δ ) { δ : ∥ δ ∥ 2 ≤ ε } \{\delta : \|\delta\|_2 \le \varepsilon\} { δ : ∥ δ ∥ 2 ≤ ε } r ~ i ∈ U \tilde r_i \in \mathcal{U} r ~ i ∈ U J ( π , r ~ i ) J(\pi, \tilde r_i) J ( π , r ~ i ) π i + 1 \pi_{i+1} π i + 1
As for implementing our shaping-aware method, recall that the shaping-aware uncertainty set is defined as the image of the original uncertainty set under the PBRS canonicalization map:
U core : = Proj ( U ) = { Proj ( r + δ ) : ∥ δ ∥ 2 ≤ ε } . \mathcal{U}_{\text{core}}
:= \operatorname{Proj}(\mathcal{U})
= \bigl\{ \operatorname{Proj}(r + \delta) : \|\delta\|_2 \le \varepsilon \bigr\}. U core := Proj ( U ) = { Proj ( r + δ ) : ∥ δ ∥ 2 ≤ ε } . In our grid-world, transitions are deterministic, so the rewards can be represented as a state-action vector r ∈ R X r \in \mathbb{R}^{\mathcal{X}} r ∈ R X l 2 l_2 l 2 Proj \operatorname{Proj} Proj
Let Φ ∈ R S \Phi \in \mathbb{R}^\mathcal{S} Φ ∈ R S B ∈ R S A × S B\in \mathbb{R}^{\mathcal{SA}\times \mathcal{S}} B ∈ R S A × S
( B Φ ) ( s , a , s ′ ) : = γ Φ ( s ′ ) − Φ ( s ) , (B\Phi)(s,a,s') \;:=\; \gamma \Phi(s') - \Phi(s), ( B Φ ) ( s , a , s ′ ) := γ Φ ( s ′ ) − Φ ( s ) , where s ′ s' s ′ a a a s s s S shape = range ( B ) . \mathcal{S}_{\text{shape}} = \operatorname{range}(B). S shape = range ( B ) . Φ ( s 0 ) = 0 \Phi(s_{0}) = 0 Φ ( s 0 ) = 0 r r r
Proj ( r ) = r − B Φ ∗ ( r ) , Φ ∗ ( r ) ∈ arg min Φ : Φ ( s 0 ) = 0 ∥ r − B Φ ∥ 2 2 . \operatorname{Proj}(r) = r - B\Phi^*(r),
\qquad
\Phi^*(r) \in \arg\min_{\Phi :\, \Phi(s_{0})=0}
\bigl\| r - B\Phi \bigr\|_2^2. Proj ( r ) = r − B Φ ∗ ( r ) , Φ ∗ ( r ) ∈ arg Φ : Φ ( s 0 ) = 0 min r − B Φ 2 2 . Equivalently, Proj ( r ) \operatorname{Proj}(r) Proj ( r ) Proj ( r ) = P r \operatorname{Proj}(r) = P r Proj ( r ) = P r P ∈ R S A × S A P\in \mathbb{R}^{\mathcal{SA}\times \mathcal{SA}} P ∈ R S A × S A range ( B ) \operatorname{range}(B) range ( B )
r core : = Proj ( r ) = P r . r_{\text{core}} := \operatorname{Proj}(r) = P r. r core := Proj ( r ) = P r . A direct characterization of U core \mathcal{U}_{\text{core}} U core
U core = { r core + P δ : ∥ δ ∥ 2 ≤ ε } , \mathcal{U}_{\text{core}}
= \bigl\{ r_{\text{core}} + P\delta : \|\delta\|_2 \le \varepsilon\bigr\}, U core = { r core + P δ : ∥ δ ∥ 2 ≤ ε } , Thus, the original ℓ 2 \ell_2 ℓ 2 P P P r a n g e ( B ) \mathrm{range}(B) range ( B )
In practice, rather than explicitly parameterizing δ \delta δ P P P Q ∈ R S A × d Q \in \mathbb{R}^{SA \times d} Q ∈ R S A × d P = Q Q ⊤ P = QQ^\top P = Q Q ⊤ r core = Q z r_{\text{core}} = Qz r core = Q z z ∈ R d z \in \mathbb{R}^d z ∈ R d z ~ \tilde z z ~ ℓ 2 \ell_2 ℓ 2
min z ~ : ∥ z ~ − z ∥ 2 ≤ ε J ( π , Q z ~ ) , z : = Q ⊤ r , \min_{\tilde z : \lVert \tilde z - z \rVert_2 \le \varepsilon}
J(\pi, Q \tilde z),
\qquad
z := Q^\top r, z ~ : ∥ z ~ − z ∥ 2 ≤ ε min J ( π , Q z ~ ) , z := Q ⊤ r , using projected gradient descent in z ~ \tilde z z ~ Q z Qz Q z
For the numerical simulation, we use a softmax policy and set the uncertainty budget ε = 5.0 \varepsilon=5.0 ε = 5.0 r a n g e ( B ) \mathrm{range}(B) range ( B )
P shape : = I − P . P_{\text{shape}} := I - P. P shape := I − P . At outer iteration i i i r ( i , j ) r^{(i,j)} r ( i , j ) j j j j = 0 , … , J j = 0,\ldots,J j = 0 , … , J
Δ r ( i , j ) : = r ( i , j + 1 ) − r ( i , j ) . \Delta r^{(i,j)} := r^{(i,j+1)} - r^{(i,j)}. Δ r ( i , j ) := r ( i , j + 1 ) − r ( i , j ) . We then compute the PBRS-invariant update fraction for that step as
α ( i , j ) : = ∥ P shape Δ r ( i , j ) ∥ 2 ∥ Δ r ( i , j ) ∥ 2 + ϵ , \alpha^{(i,j)}
:= \frac{\bigl\|P_{\text{shape}} \Delta r^{(i,j)}\bigr\|_2}
{\bigl\|\Delta r^{(i,j)}\bigr\|_2 + \epsilon}, α ( i , j ) := Δ r ( i , j ) 2 + ϵ P shape Δ r ( i , j ) 2 , where ϵ > 0 \epsilon > 0 ϵ > 0 J J J i i i
F r a c ( i ) : = 1 J ∑ j = 0 J − 1 α ( i , j ) . \mathrm{Frac}(i)
:= \frac{1}{J} \sum_{j=0}^{J-1} \alpha^{(i,j)}. Frac ( i ) := J 1 j = 0 ∑ J − 1 α ( i , j ) . By construction, values F r a c ( i ) ≈ 1 \mathrm{Frac}(i) \approx 1 Frac ( i ) ≈ 1 0 0 0
Implementation Details for MuJoCo, Atari, and Gymnasium-Robotics
For the MuJoCo, Atari, and Gymnasium-Robotics experiments, we consider two reward-robust formulations introduced in Section sec:preliminary . In both cases, we report results under the corresponding reward-robust objective
max π min r ~ ∈ U J ( π , r ~ ) , \max_{\pi} \; \min_{\tilde r \in \mathcal{U}} J(\pi, \tilde r), π max r ~ ∈ U min J ( π , r ~ ) , and implement training via the equivalent regularized RL objective. We optimize this objective using PPO [49 ] , where the regularization term is included as an intrinsic reward. Notice that in all environments considered in our experiments, the per-step reward depends on the current state and action. We therefore write reward as r ( s , a ) r(s,a) r ( s , a )
Entropy-based robust objective.
We first consider the entropy-induced uncertainty set
U = { r ~ : E [ ∑ t = 0 ∞ γ t log ∫ A exp ( r ( s t , a ) − r ~ ( s t , a ) ) d a ∣ μ 0 , π , P ] ≤ ϵ } , \mathcal{U}
=
\left\{\tilde r :
\mathbb{E}\!\left[
\sum_{t=0}^{\infty} \gamma^{t}
\log \int_{\mathcal A}
\exp\bigl(
r(s_t,a)
- \tilde r(s_t,a)
\bigr)
\,da\Big|\, \mu_0, \pi, P
\right]
\le \epsilon
\right\}, U = { r ~ : E [ t = 0 ∑ ∞ γ t log ∫ A exp ( r ( s t , a ) − r ~ ( s t , a ) ) d a μ 0 , π , P ] ≤ ϵ } , which is well known to be equivalent to optimizing an entropy-regularized RL objective:
max π J ( π , r ) − E [ ∑ t = 0 ∞ γ t ∫ A π ( a ∣ s t ) log π ( a ∣ s t ) d a ∣ μ 0 , π , P ] , \max_{\pi}\;
J(\pi, r)
\;-\;
\mathbb{E}\!\left[
\sum_{t=0}^{\infty} \gamma^t
\int_{\mathcal A}
\pi(a \mid s_t)\,\log \pi(a \mid s_t)
\,da\Bigg|\, \mu_0, \pi, P
\right], π max J ( π , r ) − E [ t = 0 ∑ ∞ γ t ∫ A π ( a ∣ s t ) log π ( a ∣ s t ) d a μ 0 , π , P ] , following prior work [37 , 6 ] .
For our shaping-aware variant, we add a projection step that learns the shaping potential function Φ φ \Phi_{\varphi} Φ φ
φ ∗ ∈ arg min φ l ( φ ) = arg min φ E D [ ∑ t = 0 ∞ γ t log ∫ A exp ( r ( s t , a ) − ( γ Φ φ ( s t + 1 ) − Φ φ ( s t ) ) ) d a ] . \varphi^{*}\in \arg\min_{\varphi} l(\varphi)=\arg\min_{\varphi}\;
\mathbb{E}_{\mathcal D}\Biggl[\sum_{t=0}^{\infty}\gamma^t\;
\log \int_{\mathcal A}
\exp\Bigl(
r(s_t,a)
-\bigl(\gamma \Phi_{\varphi}(s_{t+1})-\Phi_{\varphi}(s_t)\bigr)
\Bigr)\,da\Biggr]. φ ∗ ∈ arg φ min l ( φ ) = arg φ min E D [ t = 0 ∑ ∞ γ t log ∫ A exp ( r ( s t , a ) − ( γ Φ φ ( s t + 1 ) − Φ φ ( s t ) ) ) d a ] . We estimate the objective using a batch dataset D \mathcal D D N N N log ∫ A exp ( ⋅ ) d a \log \int_{\mathcal A}\exp(\cdot)\,da log ∫ A exp ( ⋅ ) d a q ( ⋅ ∣ s ) q(\cdot\mid s) q ( ⋅ ∣ s ) q ( ⋅ ∣ s ) = π ( ⋅ ∣ s ) q(\cdot\mid s)=\pi(\cdot\mid s) q ( ⋅ ∣ s ) = π ( ⋅ ∣ s ) K K K a ( 1 ) , … , a ( K ) ∼ π ( ⋅ ∣ s t ) a^{(1)},\ldots,a^{(K)}\sim \pi(\cdot\mid s_t) a ( 1 ) , … , a ( K ) ∼ π ( ⋅ ∣ s t )
log ∫ A exp ( u t ( a ) ) d a ≈ log ( 1 K ∑ k = 1 K exp ( u t ( a ( k ) ) ) π ( a ( k ) ∣ s t ) ) , \log \int_{\mathcal A} \exp(u_t(a))\,da
\;\approx\;
\log\!\left(\frac{1}{K}\sum_{k=1}^K
\frac{\exp(u_t(a^{(k)}))}{\pi(a^{(k)}\mid s_t)}\right), log ∫ A exp ( u t ( a )) d a ≈ log ( K 1 k = 1 ∑ K π ( a ( k ) ∣ s t ) exp ( u t ( a ( k ) )) ) , where u t ( a ) = r ( s t , a ) − ( γ Φ φ ( s t + 1 ) − Φ φ ( s t ) ) u_t(a)=r(s_t,a)-(\gamma\Phi_\varphi(s_{t+1})-\Phi_\varphi(s_t)) u t ( a ) = r ( s t , a ) − ( γ Φ φ ( s t + 1 ) − Φ φ ( s t ))
l ^ ( φ ; D ) : = 1 N ∑ i = 1 N ∑ t = 0 T i − 1 γ t log ( 1 K ∑ k = 1 K exp ( u t ( i ) ( a ( i , k ) ) ) π ( a ( i , k ) ∣ s t ( i ) ) ) , φ ∗ ∈ arg min φ l ^ ( φ ; D ) . \widehat{l}(\varphi;\mathcal D)
:=
\frac{1}{N}\sum_{i=1}^{N}\sum_{t=0}^{T_i-1}\gamma^{t}\;
\log\!\left(\frac{1}{K}\sum_{k=1}^{K}
\frac{\exp\!\bigl(u^{(i)}_t(a^{(i,k)})\bigr)}{\pi(a^{(i,k)}\mid s^{(i)}_t)}\right),
\qquad
\varphi^{*}\in\arg\min_{\varphi}\ \widehat{l}(\varphi;\mathcal D). l ( φ ; D ) := N 1 i = 1 ∑ N t = 0 ∑ T i − 1 γ t log ( K 1 k = 1 ∑ K π ( a ( i , k ) ∣ s t ( i ) ) exp ( u t ( i ) ( a ( i , k ) ) ) ) , φ ∗ ∈ arg φ min l ( φ ; D ) . KL-based robust objective.
Next, we consider the KL-induced uncertainty set
U = { r ~ : E [ ∑ t = 0 ∞ τ γ t log ∫ A π r e f ( a ∣ s t ) exp ( r ( s t , a ) − r ~ ( s t , a ) τ ) d a | μ 0 , π , P ] ≤ ε } , \mathcal U
= \Biggl\{
\tilde r:\;
\mathbb{E}\!\left[
\sum_{t=0}^{\infty} \tau\gamma^t
\log \int_{\mathcal A}
\pi_{\mathrm{ref}}(a \mid s_t)
\exp\!\left(
\frac{ r(s_t,a) - \tilde r(s_t,a)}{\tau}
\right)
\;da\middle|\;
\mu_0,\pi,P
\right] \le \varepsilon
\Biggr\}, U = { r ~ : E [ t = 0 ∑ ∞ τ γ t log ∫ A π ref ( a ∣ s t ) exp ( τ r ( s t , a ) − r ~ ( s t , a ) ) d a μ 0 , π , P ] ≤ ε } , where τ > 0 \tau>0 τ > 0 π r e f \pi_{\mathrm{ref}} π ref [5 ] ):
max π J ( π , r ) − τ E [ ∑ t = 0 ∞ γ t K L ( π ( ⋅ ∣ s t ) ∥ π r e f ( ⋅ ∣ s t ) ) | μ 0 , π , P ] . \max_{\pi}
\; J(\pi,r)
\;-\;
\tau \,
\mathbb{E}\!\left[
\sum_{t=0}^{\infty} \gamma^t
\mathrm{KL}\bigl(\pi(\cdot \mid s_t)\,\big\|\,\pi_{\mathrm{ref}}(\cdot \mid s_t)\bigr)
\;\middle|\;
\mu_0,\pi,P
\right]. π max J ( π , r ) − τ E [ t = 0 ∑ ∞ γ t KL ( π ( ⋅ ∣ s t ) π ref ( ⋅ ∣ s t ) ) μ 0 , π , P ] . For our shaping-aware variant, the projection loss becomes
φ ∗ ∈ arg min φ l ( φ ) = arg min φ E D [ ∑ t = 0 ∞ γ t log ∫ A π r e f ( a ∣ s t ) exp ( r ( s t , a ) − ( γ Φ φ ( s t + 1 ) − Φ φ ( s t ) ) τ ) d a ] . \varphi^*
\in \arg\min_{\varphi} l(\varphi)=
\arg \min_{\varphi}
\mathbb{E}_{\mathcal D}\Biggl[\sum_{t=0}^{\infty} \gamma^t
\log
\int_{\mathcal A}
\pi_{\mathrm{ref}}(a \mid s_t)
\exp\!\left(
\frac{
r(s_t,a) -
\bigl(\gamma \Phi_{\varphi}(s_{t+1}) - \Phi_{\varphi}(s_t)\bigr)
}{\tau}
\right)da
\Biggr]. φ ∗ ∈ arg φ min l ( φ ) = arg φ min E D [ t = 0 ∑ ∞ γ t log ∫ A π ref ( a ∣ s t ) exp ( τ r ( s t , a ) − ( γ Φ φ ( s t + 1 ) − Φ φ ( s t ) ) ) d a ] . Similarly, we estimate the expectation using a batch dataset D \mathcal D D N N N
u t ( a ) : = r ( s t , a ) − ( γ Φ φ ( s t + 1 ) − Φ φ ( s t ) ) τ . u_t(a)
:= \frac{ r(s_t,a) - \bigl(\gamma \Phi_{\varphi}(s_{t+1}) - \Phi_{\varphi}(s_t)\bigr)}{\tau}. u t ( a ) := τ r ( s t , a ) − ( γ Φ φ ( s t + 1 ) − Φ φ ( s t ) ) . We approximate the inner log term by Monte Carlo using a proposal density q ( ⋅ ∣ s ) q(\cdot\mid s) q ( ⋅ ∣ s ) q ( ⋅ ∣ s ) = π r e f ( ⋅ ∣ s ) q(\cdot\mid s)=\pi_{\mathrm{ref}}(\cdot \mid s) q ( ⋅ ∣ s ) = π ref ( ⋅ ∣ s ) K K K a ( 1 ) , … , a ( K ) ∼ π r e f ( ⋅ ∣ s t ) a^{(1)},\ldots,a^{(K)}\sim \pi_{\mathrm{ref}}(\cdot\mid s_t) a ( 1 ) , … , a ( K ) ∼ π ref ( ⋅ ∣ s t )
log ∫ A π r e f ( a ∣ s t ) exp ( u t ( a ) ) d a ≈ log ( 1 K ∑ k = 1 K exp ( u t ( a ( k ) ) ) ) . \log
\int_{\mathcal A}
\pi_{\mathrm{ref}}(a \mid s_t)\exp\!\bigl(u_t(a)\bigr)\,da
\;\approx\;
\log\!\left(\frac{1}{K}\sum_{k=1}^{K} \exp\!\bigl(u_t(a^{(k)})\bigr)\right). log ∫ A π ref ( a ∣ s t ) exp ( u t ( a ) ) d a ≈ log ( K 1 k = 1 ∑ K exp ( u t ( a ( k ) ) ) ) . Substituting this estimator yields the empirical minibatch loss
l ^ ( φ ; D ) : = 1 N ∑ i = 1 N ∑ t = 0 T i − 1 γ t log ( 1 K ∑ k = 1 K exp ( u t ( i ) ( a ( i , k ) ) ) ) , φ ∗ ∈ arg min φ l ^ ( φ ; D ) . \widehat{l}(\varphi;\mathcal D)
:=
\frac{1}{N}\sum_{i=1}^{N}\sum_{t=0}^{T_i-1}\gamma^{t}\;
\log\!\left(\frac{1}{K}\sum_{k=1}^{K}
\exp\!\Bigl(
u^{(i)}_t(a^{(i,k)})
\Bigr)\right),
\qquad
\varphi^{*}\in\arg\min_{\varphi}\ \widehat{l}(\varphi;\mathcal D). l ( φ ; D ) := N 1 i = 1 ∑ N t = 0 ∑ T i − 1 γ t log ( K 1 k = 1 ∑ K exp ( u t ( i ) ( a ( i , k ) ) ) ) , φ ∗ ∈ arg φ min l ( φ ; D ) . Finally, to satisfy the technical conditions required by our convergence analysis (Assumption C.12 ), we add a small ridge term to the shaping loss,
ℓ λ , β ( φ ) : = ℓ ( φ ) + λ 2 ∥ φ ∥ 2 + β E s 0 ∼ D [ Φ φ ( s 0 ) 2 ] , λ > 0 , β > 0 , \ell_{\lambda,\beta}(\varphi)
\;:=\;
\ell(\varphi)
\;+\;
\frac{\lambda}{2}\,\|\varphi\|^2
\;+\;
\beta\,
\mathbb{E}_{s_0 \sim \mathcal D}\!\bigl[\Phi_{\varphi}(s_0)^2\bigr],
\qquad
\lambda>0,\;\beta>0, ℓ λ , β ( φ ) := ℓ ( φ ) + 2 λ ∥ φ ∥ 2 + β E s 0 ∼ D [ Φ φ ( s 0 ) 2 ] , λ > 0 , β > 0 , where the β \beta β C ( Φ ) = 0 C(\Phi)=0 C ( Φ ) = 0 Φ φ \Phi_{\varphi} Φ φ π ref \pi_{\text{ref}} π ref tab:hyperparameter_ppo and Table tab:hyperparameter_projection .
Implementation Details for Reward Perturbation
Figure 4. Example goal shift in Reacher. Left: the original environment. Right: the perturbed environment with a shifted goal.
For the locomotion tasks (HalfCheetah, Hopper, Walker2d, and Humanoid), during training, we construct the adversarial reward r adv r_{\text{adv}} r adv [14 ] :
r adv = { r ( s , a ) + δ , if r ( s , a ) ≤ 0 , r ( s , a ) , otherwise . r_{\text{adv}} =
\begin{cases}
r(s,a) + \delta, & \text{if } r(s,a) \le 0,\\
r(s,a), & \text{otherwise}.
\end{cases} r adv = { r ( s , a ) + δ , r ( s , a ) , if r ( s , a ) ≤ 0 , otherwise . where δ \delta δ 0.1 0.1 0.1
For Reacher, we relocate the goal to a random position at varying distances from its nominal location during evaluation [9 ] . Figure 4 illustrates the original Reacher environment and an example perturbed setting with a shifted goal.
Implementation Details for Ablation Study
To isolate the contribution of our Ω ∗ \Omega^* Ω ∗ Φ \Phi Φ Φ φ \Phi_\varphi Φ φ φ \varphi φ L 2 L^2 L 2 Ω ∗ \Omega^* Ω ∗ ℓ 2 \ell_2 ℓ 2 Φ φ \Phi_\varphi Φ φ
φ ∗ ∈ arg min φ l ( φ ) : = E D [ ∑ t = 0 ∞ γ t ( r ( s t , a t , s t + 1 ) − ( γ Φ φ ( s t + 1 ) − Φ φ ( s t ) ) ) 2 ] . \varphi^* \in \arg\min_{\varphi}\; l(\varphi)
\;:=\;
\mathbb{E}_{\mathcal D}\Biggl[\sum_{t=0}^{\infty}\gamma^t\;
\Bigl(
r(s_t,a_t,s_{t+1})
-\bigl(\gamma \Phi_{\varphi}(s_{t+1})-\Phi_{\varphi}(s_t)\bigr)
\Bigr)^2\Biggr]. φ ∗ ∈ arg φ min l ( φ ) := E D [ t = 0 ∑ ∞ γ t ( r ( s t , a t , s t + 1 ) − ( γ Φ φ ( s t + 1 ) − Φ φ ( s t ) ) ) 2 ] . We estimate the objective using a batch dataset D \mathcal D D N N N
l ^ ( φ ; D ) = 1 N ∑ i = 1 N ∑ t = 0 T i − 1 γ t ( r ( i ) ( s t , a t , s t + 1 ) − ( γ Φ φ ( s t + 1 ( i ) ) − Φ φ ( s t ( i ) ) ) ) 2 , \widehat l(\varphi;\mathcal D)
=
\frac{1}{N}\sum_{i=1}^{N}\sum_{t=0}^{T_i-1}\gamma^t
\Bigl(
r^{(i)}(s_t,a_t,s_{t+1})
-\bigl(\gamma \Phi_{\varphi}(s_{t+1}^{(i)})-\Phi_{\varphi}(s_t^{(i)})\bigr)
\Bigr)^2, l ( φ ; D ) = N 1 i = 1 ∑ N t = 0 ∑ T i − 1 γ t ( r ( i ) ( s t , a t , s t + 1 ) − ( γ Φ φ ( s t + 1 ( i ) ) − Φ φ ( s t ( i ) ) ) ) 2 , Additional Experiment Results
Analysis on Non-convex Uncertainty Set
Figure 5. Illustration of a nonconvex uncertainty set.
As discussed in the main text, when the adversary searches for a worst-case reward directly in the original reward space, it may spend many iterations moving along PBRS-invariant directions that do not change policy ranking. This issue is particularly acute for non-convex uncertainty sets (e.g., unions of scenarios) or implicitly specified feasible sets, where there may be no efficient dedicated solver for the optimization, and one must resort to black-box procedures (random search, Bayesian optimization, etc.) [43 , 44 , 45 , 46 , 47 ] . Such methods typically suffer from sample complexity that scales badly with the dimension. Our shaping-aware projection reduces the intrinsic search dimension by removing PBRS-invariant directions, which can substantially improve the efficiency of black-box adversary search.
To illustrate, consider the same toy setting as in the main text in Figure 1 and define a non-convex uncertainty set as the union of K K K
U = ⋃ k = 1 K { ( r 1 , r 2 ) ∈ [ 0 , 1 ] 2 : ∣ ( r 1 − r 2 ) − δ k ∣ ≤ η } . \mathcal{U} \;=\; \bigcup_{k=1}^K
\left\{
(r_1,r_2) \in [0,1]^2 \;:\;
\bigl|(r_1 - r_2) - \delta_k\bigr| \le \eta
\right\}. U = k = 1 ⋃ K { ( r 1 , r 2 ) ∈ [ 0 , 1 ] 2 : ( r 1 − r 2 ) − δ k ≤ η } . When η \eta η U \mathcal{U} U K K K ( 1 , 1 ) (1,1) ( 1 , 1 ) Figure 5 ). The union of several scenarios makes the feasible set highly non-convex. Under the projection that fixes one coordinate (e.g., r 2 core = 0 r_2^{\text{core}}=0 r 2 core = 0
U core = ⋃ k = 1 K [ δ k − η , δ k + η ] ⊂ [ − 1 , 1 ] . \mathcal{U}_{\text{core}}
\;=\; \bigcup_{k=1}^K [\delta_k - \eta,\; \delta_k + \eta]
\;\subset\; [-1,1]. U core = k = 1 ⋃ K [ δ k − η , δ k + η ] ⊂ [ − 1 , 1 ] . Thus, projection removes the long PBRS-invariant direction, retaining only the behaviorally relevant coordinate.
Now suppose the adversary can only query feasible rewards. In the original two-dimensional set U \mathcal{U} U U core \mathcal{U}_{\text{core}} U core
A simple scaling argument makes this difference explicit. Consider a single strip of width 2 η 2\eta 2 η U core \mathcal{U}_{\text{core}} U core ε \varepsilon ε
N U core ≈ 2 η ε N_{\mathcal{U}_{\text{core}}} \;\approx\; \frac{2\eta}{\varepsilon} N U core ≈ ε 2 η feasible evaluations. In the original reward space, the corresponding strip has area approximately
A ≈ ( 2 η ) L , L ≈ 1 − ∣ δ k ∣ A \;\approx\; (2\eta)\,L,
\qquad
L \approx 1-|\delta_k| A ≈ ( 2 η ) L , L ≈ 1 − ∣ δ k ∣ where L L L [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 N N N h ≈ A / N h \approx \sqrt{A/N} h ≈ A / N ε \varepsilon ε
N U ≈ A ε 2 ≈ 2 η L ε 2 . N_{\mathcal{U}}
\;\approx\; \frac{A}{\varepsilon^2}
\;\approx\; \frac{2\eta L}{\varepsilon^2}. N U ≈ ε 2 A ≈ ε 2 2 η L . Therefore, black-box search scales as O ( 1 / ε ) \mathcal{O}(1/\varepsilon) O ( 1/ ε ) U core \mathcal{U}_{\text{core}} U core O ( 1 / ε 2 ) \mathcal{O}(1/\varepsilon^2) O ( 1/ ε 2 ) U \mathcal{U} U
For a numerical illustration, let η = 0.01 \eta=0.01 η = 0.01 δ k = 0.2 \delta_k=0.2 δ k = 0.2 L ≈ 0.8 L\approx 0.8 L ≈ 0.8 ε = 10 − 3 \varepsilon=10^{-3} ε = 1 0 − 3
N U core ≈ 0.02 0.001 = 20 , N U ≈ 2 η L ε 2 = 0.02 × 0.8 10 − 6 = 16,000. N_{\mathcal{U}_{\text{core}}} \approx \frac{0.02}{0.001}=20,
\qquad
N_{\mathcal{U}} \approx \frac{2\eta L}{\varepsilon^2}
= \frac{0.02\times 0.8}{10^{-6}}=16{,}000. N U core ≈ 0.001 0.02 = 20 , N U ≈ ε 2 2 η L = 1 0 − 6 0.02 × 0.8 = 16 , 000. In the original space, the overwhelming majority of evaluations are effectively spent spreading points along a behaviorally irrelevant direction. After projection, essentially every evaluation contributes to identifying a more adverse reward.
Learning Curves on MuJoCo, Atari, and Gymnasium-Robotics Tasks.
Figure 6. Mean and standard deviation return of the evaluation policy over 10 rollouts and 5 seeds, reported every 20k environment steps for MuJoCo environment. The return is in terms of the environment’s original reward. Top row: Entropy-based reward-robust problem, bottom row: KL-based reward-robust problem.
Figure 7. Mean and standard deviation return of the evaluation policy over 10 rollouts and 5 seeds, reported every 20k environment steps for Atari and Gymnasium-Robotics environment. The return is in terms of the environment’s original reward. Top row: Entropy-based reward-robust problem, bottom row: KL-based reward-robust problem.
Figure 6 and Figure 7 compares learning curves for both methods. Overall, our method achieves higher returns throughout training and typically exhibits more stable optimization dynamics. The improvement is especially clear on HalfCheetah, Pong, and Adroit Pen, where the shaping-aware policy stays above the baseline at essentially every timestep and continues to improve late in training, while the baseline progresses more slowly and plateaus earlier. We observe a similar trend on Walker2d and Seaquest: although both methods reach comparable performance in the mid-training regime, the baseline becomes noticeably more volatile later on, whereas our method maintains a higher and more stable return trajectory. Beyond final performance, the curves also show a consistent sample-efficiency advantage. On Reacher, our method reaches near-solved performance almost immediately, while the baseline requires substantially more interaction (on the order of 2 × 10 5 2\times 10^5 2 × 1 0 5
Reward Robustness Results
Figure 8. Mean ± \pm ±
Figure 8 shows the robustness under reward perturbations for both reward-robust problems. Overall, the shaping-aware method exhibits smaller performance degradation than the robust RL baseline as the reward shift radius increases, indicating improved stability to reward misspecification.
Analysis on Training Time
Table 1. Approximate training time for each algorithm across different environments.
Table 1 reports the approximate training time for the standard reward-robust baseline and our shaping-aware variant. Across all tasks, the shaping-aware method incurs a small additional cost (typically around 10–30 minutes), which is attributable to the extra projection step that fits the potential function. Importantly, this overhead is modest relative to the overall training time (on the order of around 10–25% depending on the environment) and remains practical in the same computational setting. Given the consistent gains in final return and faster convergence observed in § 5 , the added computation is a affordable trade-off for improved robustness and performance.
Additional Ablation Study
Figure 9. Ablations on sampled actions for projection learning in MuJoCo environment. We evaluate each policy for 100 episodes and show 95% confidence interval across 5 seeds.
Sensitivity to data coverage in the projection estimate.
As detailed in Appendix § 10 , the Ω ∗ \Omega^* Ω ∗ K K K K K K K K K Figure 9 shows a clear dependence on action-sample coverage. With a very small K K K K = 4 K=4 K = 4 K K K
Ablation on canonicalization choices
To isolate the contribution of our Ω ∗ \Omega^* Ω ∗ tab:ablation_canon compares several projection choices under reward perturbations. First, we include a random Φ \Phi Φ L 2 L^2 L 2 Ω ∗ \Omega^* Ω ∗ L 2 L^2 L 2
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction state the core contributions, which is shaping-aware reward-robust RL framework.
Guidelines:
The answer [N/A] means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A [No] or [N/A] answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations of the work is discussed in Appendix § 7 .
Guidelines:
The answer [N/A] means that the paper has no limitation while the answer [No] means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate “Limitations” section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All the assumptions and proof can be found in the Appendix.
Guidelines:
The answer [N/A] means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All training hyperparameters are specified in Appendix § 10 .
Guidelines:
The answer [N/A] means that the paper does not include experiments.
If the paper includes experiments, a [No] answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code is included in the supplementary. All data is open accessible.
Guidelines:
The answer [N/A] means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy ) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so [No] is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy ) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results?
Answer: [Yes]
Justification: All details can be found in Appendix § 10 .
Guidelines:
The answer [N/A] means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report mean ± \pm ±
Guidelines:
The answer [N/A] means that the paper does not include experiments.
The authors should answer [Yes] if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates).
If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: All details can be found in Appendix § 10 .
Guidelines:
The answer [N/A] means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper).
Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines ?
Answer: [Yes]
Justification: The research conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer [N/A] means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer [No], they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [N/A]
Justification: This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted.
Guidelines:
The answer [N/A] means that there is no societal impact of the work performed.
If the authors answer [N/A] or [No], they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate Deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)?
Answer: [N/A]
Justification: The paper poses no such risks.
Guidelines:
The answer [N/A] means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All assets have been cited.
Guidelines:
The answer [N/A] means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset’s creators.
New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [N/A]
Justification: The paper does not release new assets.
Guidelines:
The answer [N/A] means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [N/A]
Justification: This work does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [N/A]
Justification: This work does not involve human subjects research.
Guidelines:
The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required.
Answer: [N/A]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer [N/A] means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy in the NeurIPS handbook for what should or should not be described.
