Observational Robustness and Invariances in Reinforcement Learning via Lexicographic Objectives
Authors: Daniel Jarne Ornia
Licio Romao
Lewis Hammond
Manuel Mazo Jr
Alessandro Abate
Venue: Submitted to ICLR 2023 (2023)
Keywords: Robust Reinforcement Learning
Safe Reinforcement Learning
Lexicographic Optimization

Abstract: Policy robustness in Reinforcement Learning (RL) may not be desirable at any price; the alterations caused by robustness requirements from otherwise optimal policies should be explainable and quantifiable. Policy gradient algorithms that have strong convergence guarantees are usually modified to obtain robust policies in ways that do not preserve algorithm guarantees, which defeats the purpose of formal robustness requirements. In this work we study a notion of robustness in partially observable MDPs where state observations are perturbed by a noise-induced stochastic kernel. We characterize the set of policies that are maximally robust by analysing how the policies are altered by this kernel. We then establish a connection between such robust policies and certain properties of the noise kernel, as well as with structural properties of the underlying MDPs, constructing sufficient conditions for policy robustness. We use these notions to propose a robustness-inducing scheme, applicable to any policy gradient algorithm, to formally trade off the reward achieved by a policy with its robustness level through lexicographic optimization, which preserves convergence properties of the original algorithm. We test the the proposed approach through numerical experiments on safety-critical RL environments, and show how the proposed method helps achieve high robustness when state errors are introduced in the policy roll-out.

Under review as a conference paper at ICLR 2023
OBSERVATIONAL ROBUSTNESS AND INVARIANCES IN REINFORCEMENT LEARNING VIA LEXICOGRAPHIC OBJECTIVES
Anonymous authors Paper under double-bling brindd review
ABSTRACT
Policy robustness in Reinforcement Learning (RL. may not be desirable at any price; the alterations caused by robustness requirements from otherwise optimal policies should be explainable and quantifiable. Policy gradient algorithms that have strong convergence guarantees are usually modified to obtain robust poli- cies in ways that do not preserve algorithm guarantees, which defeats the purpose formal robustness requirements. In this work we study a notion of robustness in partially observable MDPs where state observations are perturbed by noise- induced stochastic kernel. We characterise the set of policies that are maximally robust by analysing how the policies are altered by this kernel. We then estab- lish connection between such robust policies and certain properties of the noise kernel, as well with structural properties of the underlying MDPs. construct- ing sufficient conditions for policy robustness. We use these notions to propose a aabustnessinnducing scheme, applicable to any policy gradient algorithm, to for- mally trade off the reward achieved by policy with its robustness level through lexicographic optimisation, which preserves convergence properties of the orig- inal algorithm. We test the the proposed approach on safety-critical RL envi- ronments, and show how the proposed method helps achieve high robustness in observational noise problems.
INTRODUCTION
Robustness in Reinforcement Learning (RL) (Morimoto & Doya 2005) can be looked from dif- ferent perspectives: (1) distributional shifts in the training data with respect to the deployment stage
Satia & Lave Jr (1973); Heger (1994); NNilim & El Ghaoui (2005); Xu & Mannor (2006); (2) uncer- lainty in the model or observations (Pinto et |001 Everett et al. 2021); I); (3) adversarial attacks against actions (Pattanaik et al. 2017: Fischer et al.) 2019): and (4) sensitivity of neural networks
(used as policy or value function approximators) towards input disturbances (Kos & Song 2017] HHuagg et al., (017). Robustness does not naturally emerge in most RL settings, since agents are typically only trained in a single, unchanging environment: There is trade-off between how ro- bust a policy is and how close it is to the set of optimal policies its training environment, and in safety-critical applications we may need to provide formal guarantees for this trade-off.
Motivation Consider a complex dynamical system where we need to synthesise a controller (pol- icy) through a model-free approach. When using a simulator for training we expect the deployment of the controller in the real system to be affected by different sources of noise, possibly not pre- dictable or modelled (e.g. for networked components we may have sensor faults, communication delays, etc). In safety-critical systems, robustness (in terms of successfully controlling the system under disturbances) should preserve formal guarantees, and plenty of effort has been put on devel- oping formal convergence guarantees on policy gradient algorithms (Agarwal et al. 2021 Bhandari & Russo 2019) which vanish when "robustifying" policies through regularisation or adversarial approaches. Therefore, for such applications one would need a scheme regulate the robustness- utility trade-off in RL policies that preserves the formal guarantees of original algorithms and retains sub-optimality conditions for the original problem.

---

Under review as a conference paper at ICLR 2023
Lexicographic Reinforcement Learning Recently, lexicographic optimisation (Isermann 1982 Rentmeesters et al. (996) has been applied to the multi-objective RL setting (Skalse et al. 2022b) In an LRL setting with different reward roward-maximising objective functions ( some objec- tives may he more important than others, and so we may want to obtain policies that solve the multi-objective problem in lexicographically prioritised way, L.e,, "find the policies that optimise objective i (reasonably well), and from those the ones that optimise objective i + 1 (reasonably well), and so on". There exist both value- and policy-based algorithms for LRL, and the approach is broadly applicable to (most) state of the art RL algorithms (Skalse et al. 20226
Previous Work In robustness against model uncertainry, the MDP may have noisy or uncertain reward signals or transition probabilities, as well as possible resulting distributional shifts in the
training data (Heger 1994 Xu & Mannori 2006 Fu et al., 2018 Pattanaik et al. [0188] Pirotta iet al. [013 Abdullah et al. 2019). which connects to ideas on distributionally robust optimisation
(Wiesemann et 2014 Van Parys et al., 2015). One of the first examples is Heeer (1994), where the author proposes using minimax approaches to learn Q functions that minimise the worst case total discounted cost in a general MDP setting. [ermmn et al. (2020) propose a Bayesian approach to deal with uncertainty in the transitions. Another robustness sub-problem is studied in the form of adversarial attacks or disturbances by considering adversarial attacks on policies or action selection
in RL agents (Gleave et al. 2020; Lin et al. 2017; Tessler et al.) 2019: Pan et al.) 2019 Tan et al.) 2020 Klima et al.] 2019). Recently, Gleave et al. (2020) propose the idea that instead of modifying observations, one could attack RL agents by swapping the policy for adversarial one at given times. For a detailed review on Robust RL see Moos et al. (2022). Our work focuses in the study of robustness versus observational disturbances, where agents observe a disturbed state measurement and use it as input for the policy (Kos & Song 2017 Huang et al. 2017 [Behzadan & Munir 2017] Mandlekar al. 2017. Zhang al.) 20.00 (021). In particular Mandlekar al. (2017) consider both random and adversarial state perturbations, and introduce physically plausible generation of disturbances in the training of RL agents that make the resulting policy robust towards realistic dis- turbances. Zhang et al. (2020) propose a adversaave MDP framework, and utilise adversarial regularising terms that can be added different deep RL algorithms to make the resulting policies more robust to observational disturbances, minimising the distance bound between disturbed and undisturbed policies through convex relaxations of neural networks to obtain robustness guarantees. Zhang al. (2021) study how LSTM increases robustness with optimal state-per adversaries.
1.1
MAIN CONTRIBUTIONS
Most existing work on RL with observational disturbances proposes modifying RL algorithms (learning deal with perturbations through linear combinations of regularising loss terms or ad- versarial terms) that come at the cost of explainability (in terms of sub-optimality bounds) and ver- ifiability, since the induced changes in the new policies result in loss of convergence guarantees. Our main contributions are summarised in the following points.
Structure of Robust Policy Sets [e consider general unknown stochastic disturbances and for- mulate a quantitative definition of observational robustness that allows us to characterise the sets of robust policies for any MDP in the form of operator-invariant sets. We analyse how the structure of these sets depends on the MDP and noise kernel, and obtain an inclusion relation (i.e. Inclusion Theorem, Section providing intuition into how we can search for robust policies more effectively.
Verifiable Robustness through LRL While LRL is developed for reward maximising objectives, through the proposed observational robustness definition can cast robustness lexicographic objective, allowing us to retain policy optimality up to a specified tolerance while maximising ro- bustness and yielding a mechanism to formally control the serformancc-robusttee trade-off. This preserves convergence guarantees of the original algorithm and yields formal bounds on policy sub- optimality. We provide numerical examples how this logic is applied to existing policy gradient
We claim novelty on the application of such concepts to the understanding and improvement of robustness in disturbed observation RL. Although we have not found our results in previous work, there are strong connec-
tions between Sections 2 3 in this paper and the literature planning for POMDPs (Spaan & Vlassis 2004
Spaan 2012 and MDP invariances (Ng 1999 van der Pol al. 2020
Skalse (202a
2

---

Under review as a conference paper at ICLR 2023
II
1l
I
(a) PG algorithms when robustness terms are added to the cost function indiscriminately.
(b) In LRPG, the policy is guaranteed (up the original algorithm used) converge to ball of III, and from those, most robust ones.
Figure 1: Qualitative representation of the proposed LRPG algorithm, compared usual robustness- inducing algorithms. The sets in blue are the maximally robust policies to be defined in the coming sections. Through LRPG we guarantee that the policies will only deviate bounded distance from the original objective, and induce a search for robustness in the resulting valid policy set.
algorithms, compare with existing algorithms in previous work, and verify how the previously men- tioned Inclusion Theorem helps to induce more robust policies while retaining algorithm optimality. Figure represents qualitative interpretation of the results in this work (the structure of the robust sets will become clear in following sections).
1.2 PRELIMINARIES
Notation We use calligraphic letters A for collections of sets and ((A) the space of probability measures over A. For two elements of a vector space we use (---) as the inner product. We use 1, as column-vector of size that has all entries equal to 1. We say that MDP is ergodic if for any policy the resulting Markov Chain (MC) is ergodic. We say that S is a n x n row-stochastic matrix if Sūy 2 0 and each row of S sums to 1. We use a, B. n7 for learning rates, μ for probability distributions and
for parameters.
Lexicographic Reinforcement Learning We propose using policy-based LRL (PB-LRL) to en- code the idea that, when learning how solve an RL task, robustness important but not any price, ie., we would like to solve the original objective reasonably well, and from those policies effi- ciently find the most robust o Consider a parameterised policy н, with 0 E O, and two objective functions K2 and Kg. PB-LRI uses a multi-timescal optimisation scheme to optimise 0 faster for higher-priorite objectives, iteratively updating the constraints induced by these priorities and encod- ing them via Lagrangian relaxation techniques (Bertsckas) 1997 Let 0' arg max K₁ (0). Then, PB-LRL can be used to find parameters:
arg max K2(0) such that K2 Ki(0) c
0
This is done by computing the (estimated) gradient ascent update:
+ proje [0 (o)( A proje [A + ma(ki E; Ki(O)),
(I)
where K(0) (3) + + K2 (0) + + K2),,, A Langrange multiplier, B3 88 m7 are learning rates, and b is an estimate of K2 (0'). Typically, we set + O, though we can use other tolerances too, e.g., 0.9 k1 For more detail the convergence proofs and particularities of PB-LRL refer the reader to Skalse et al. (002bb).
"The advantage of LRL is that we need not know in advance how to define "reasonably well" for each new task. Additionally, robustness through LRL provides us with parameer that directly controls the trade-off between robustness and optimality: the optimality tolerance By selecting values of we determine how far allow resulting policy he from optimal policy favour of being more robust.

---

Under review as a conference paper at ICLR 2023
2 OBSERVATIONALLY ROBUST REINFORCEMENT LEARNING
We restrict the robustness problem considered in this work to the following version of noise- induced partially observable Markov Decision Process (Spaan 2012).
Definition 1. An observationall--iisubbell MDP (DOMDP) is (a POMDP) defined by the tuple (X,U, P. 7) where X is a finite set of states, U is set of actions, P U x X A(X) is a probability measure of the transitions between states and R : X x U x X + R is reward function. The map T X + ((X) is a stochastic kernel induced by some unknown noise signal, such that Tyy z) is the probability of measuring while the true state is I, and acts only on the state observations. At last y E [0, 1] is reward discount factor.
In a DOMDF agents can measure the full state, but the measurement will be disturbed by some unknown random signal in the policy roll-out phase. Unlike the POMDP setting the agent has access to the true state x during learning of the policies (the simulator noise-free), and no information about the noise kernel T' or way to estimate it. The difficulty of acting in such DOMDP is that the transitions are actually undisturbed and a function of the true state z, but agents will have to act based on disturbed states ã ~ T- | z). We then need to construct policies that will be robust as possible against noise without being able to construct noise estimates. This is a setting that reflects many control problems; we design controller for ideal noise-less conditions, and we know that at deployment there will likely be noise, data corruption, adversarial perturbations, etc., but we do not have certainty on the disturbance structure.
In Sections 2 and we reason about the influence of T in the characterisation of ro- bustness and robust policies. However, when trying to learn robust policies we will to introduce uncertainty in the training phase. How to add this uncertainty will become clear in further sections.
Remark 1.
A (memoryless) policy for the agent is a stochastic kernel क : X + A(U). For simplicity, we overload notation on æ. denoting by πT (2z u) as the probability of taking action u at state æ under the stochastic policy π in the MDP, i.e. π (I, u) = Pr(u x). The value function of a policy m, bo
V= X + IR is given by VT (2x) ı (Q-function) is given by Q" u) = Σ veX P(x, u, y) u, y) + +VV* (v)). It is well known that, under mild conditions (Sutton & Barto 2018). the optimal value function can be obtained by means of the Bellman equation V (xx) == max, Σ Eyex P(r, u, (R(z, u. y) + yV* (v)), and an optimal policy is guaranteed to exist such that n (a)) == arg max, V*(x) Vo E X. We then define the objective function as (TT) == Eno-wol [V (x=o] with pio being a distribution of initial states, and we use J max, J (T).. If a policy parameterised by 0 E O we write my and J()).
E _ to 7 R(x,, (Tx)), 2441]]. The action-value function of
Assumption 1. For any DOMDP and policy n. the resulting MC irreducible and aperiodic.
Assumption D ensures that for any DOMDP and policy ग, there exists a stationary probability distri- bution of states μr E A(X), and for every policy and state this probability is larger than zero. We now formalise a notion of observational robustness. Firstly, due to the presence of the stochastic kernel T. the policy we are applying is altered as are applying collection of actions in possibly wrong state. This behaviour can be formally captured by:
Pr(ul x, T} = (T, (I, = Σ ETwy x)T(y. u).
(2)
BEX
where (I. X A(U) is the disturbed policy, which averages the current policy given the error induced by the presence of the stochastic kernel. Notice that (x) II + A(U) is an averaging operator yielding the alteration of the policy due to noise. We can then define the robusiness regret:
p(T, T) = ((T) - ((m,T))
Definition 2 (Policy Robustness). We say that a policy π is rs-robust against a stochastic kernel T p(T, T) < If is O-robust we say it is maximally robust. We define the sets of k-robust policies, II, = E II: (( S Ri,, with Hg being the set of maximally robust policies.
Definition is generalised form of the State-Adversarial MDP used by Zhang al. (2020): the adversarial case is particular form of DOMDP where T is prohability measure that assigns probahility 1 one state.
4

---

Under review as a conference paper at ICLR 2023
One can motivate the characterisation and models above from control perspective, where poli- cies use as input discretised state measurements with possible sensor measurement errors. Formally ensuring robustness properties when learning RL policies will, in general, force the resulting poli- cies to deviate from optimality in the undisturbed MDP. With this motivation, we propose solving the problem of increasing robustness of RL policies through hierarchical lexicographic approach, which naturally incorporates trade-off's during the policy design. The first objective is to minimise the distance J - (TT) up to some tolerance. Then, from the policies that satisfy this constraint, we want to steer the learning algorithm towards a maximally robust policy according to the metric defined in Definition This can be formulated the following problem, be solved by means of LRL casting robustness as a valid lexicographic objective.
Problem 1. For a DOMDP and a given tolerance level derive a policy ne that satisfies J J(x') S c as a prioritised objective and is as robust as possible according Definition 2
CHARACTERISATION OF ROBUST POLICIES
An important question to addressed, before trying to synthesise robust policies through LRI., what these robust policies look like, and how they are related to DOMDP properties. The robustness notion in Definition 2 is intuitive and allows us to classify policies. We begin by exploring what are the types of policies that are maximally robust, starting with the set of constant policies and set of fix point of the operator (:, T), whose formal descriptions are now provided.
Definition 3. A policy : -x+ + (U) is said to be constant if (T()) = π tly) for all x. E X, and the collection of all constant policies is denoted by II. A policy π X + A(U) is called fixed point of the operator (.,T)) (x) = (T,, (x)) for all x E X. The collection of all fixed points will be denoted by II..
In other words, a constant policy is any policy that yields the same action distribution for any state, and fixed point policy is any policy whose action distributions are un- un-altered by the noise kernel. Observe furthermore that IT only depends on the kernel T and the se(* X. We now present proposition that links the two sets of policies in Definition 3 with our notion of robustness.
Proposition Consider a DOMDP as in Definition and the concepts in Definition 3 then we have that
? the robustness notion given in Definition
I Il C Il.-
The importance of Proposition 1 is that it allows us to produce (approximately) maximally robust policies by computing the distance of policy to either the set of constant policies to the fix point of the operator (. T), and this is at the core of the construction in Section 4 However, before this, let us introduce another set that is sandwiched between II and Ily. Let assume we have a policy iteration algorithm that employs an action-valle function Q and policy т. The advantage function maximisation objective
for is defined A" u) Q" (x. u) (xr and be used
to learn optimal policies (as in, e.g., A2C (Sutton et al. 1999). A3C (Mnih et al., (2016). We can similarly define the noise disadvantage (a form of negative advantage) of policy и as:
(4) which measures the difference of applying at state x action according to the policy и with that of playing an action according to (T, T)) and then continuing playing an action according to т. Our intuition says that if it happens to be the case that D (xx T") 0 for all states in the DOMDP, then such a policy is maximally robust. And this is indeed the case, as shown in the next proposition.
D² := (*))) (x 1Q u)].
Proposition 2. Consider DOMDP as Definition Nand the robustness notion as in Definition 2 If a policy is such that D (x, T' = 0 for all X, then is maximally robust, i.e., let
1Ip = { E II: Ma (x) (x, OV.
then we have that Up Coo
'There is a (natural) bijection between the set of constant policies and the space A(U). The set of tixed points of the operator T) also has algehraic characterisation in terms of the null space of the operator Id(-) - (: T). We not exploiting the later characterisation in this paper.
5

---

Under review as a conference paper at ICLR 2023
So far have shown that both the set of fixed points II and the set of policies for which the disadvantage function is equal to zero D are contained in the set of maximally robust policies. More interesting is the fact that the inclusion established in Proposition| land the one in Proposition 2 can be linked in a natural way. We call this connection, which is the main result of this section, the Inclusion Theorem.
Theorem (Inclusion Theorem). For a DOMDP with noise kernel T,, consider the sets II, 117, lpp and No. Then, the following inclusion relation holds:
I 11 S
II S lll..
Additionally, the sets II, UrT are convex for all MDPs and kernels T, but p., To may not be.
Let us reflect on the inclusion relations of Theorem | The inclusions are in general not strict, and in fact the geometry of the sets (as well as whether some of the relations are in fact equalities) is highly dependent on the reward function, and in particular on the complexity (from an information- theoretic perspective) of the reward function. As an intuition, less complex reward functions (more uniform) will make the inclusions above expand to the entire policy set, and more complex reward functions will make the relations collapse to equalities. The following Corollary illustrates this.
Corollary 1. For any ergodic DOMDP there exist reward functions R and R such that the resulting DOMDP satisfies: (i) d To IT (any policy max. robust) if R R, (ii) IT I TT (only fixed point policies are maximally robust) if R = R.
We can now summarise the insights from Theorem and Corollary I in the following conclusions: (I) The II is maximally robust, convex and independent of the DOMDP, (2) The 1l7 is maximally robust, convex, includes II, and its properties only depend on T, (3) The set Hp includes Ir and is maximally robust, but its properties depend on the DOMDP.
4 ROBUSTNESS THROUGH LEXICOGRAPHIC OBJECTIVES
We have now characterised robustness DOMDP and explored the relation between the sets of policies that are robust according to the definition proposed. We have seen in the Inclusion Theorem that several classes of policies are maximally robust, and our goal now is to connect these results with lexicographic optimisation. To be able to apply LRL results to our robustness problem need to first cast robustness as a valid objective to be maximised, and then show that a stochastic gradient descent approach would indeed find global maximum of the objective, therefore yielding a maximally robust policy. Then, this robustness objective can be combined with a primary reward- maximising objective Ki Ki(0) Exg-Ho! (xo)] and any algorithm with certified convergence to produce a solution to Problem
We do not know T In the introduction, emphasised the motivation for this work came partially from the fact that we may not know T in reality, or have a way to estimate it. However, the theoretical results until now depend on T. Our proposed solution this lies in the results of Theorem [ If an assumed generator / with the smallest possible fixed point (i.e. the constant policy set), the robustness lexicographic objective will drive the policy towards the set of fixed points of T, which will be included in the fixed points of T (from Theorem D. We argue that this is reasonable since we expect that it will improve robustness for any noise structure. If do have information about the noise generator, may be sensible to pick different 7. For details on how T may relate í see Appendix B.3 A reasonable choice for the stochastic kernel T' discussed in the above paragraph is the uniform kernel, following the Principle of Maximum Entropy (when no information about T is available, consider the maximum entropy distribution). In specific problems, other priors, adversarial noise, etc., may be more appropriate.
We propose now a valid lexicographic objective for which a minimising solution yields a maximally robust policy. One of the messages of the Inclusion Theorem is the fact that fixed points and constant policies are maximally robust, the latter being completely oblivious to the choice of T, relevant
'The above inclusions equalities for some MDPs. See Appendix A for examples.

---

Under review as a conference paper at ICLR 2023
feature to the design of robust policies. Consider the optimisation problem minimise Kx =
Σ Mom (4To()) 1 (0)) - (To, (x)) x
(5)
where we recall that my is given parameterisation of the set of policies. Notice that the optimisation problem 5 projects the current policy onto the set of fixed points of the operator {-, T), and due to Assumption I which requires Uno (z) > 0 for all E X, the optimal solution is equal to zero if and only if there exists a value of the parameter / for which the corresponding xy is fixed point
of T) In practice, the objectives are computed for batch of trajectory sampled states X, C CX, and averaged over [X,] we denote these approximations with hat. By applying standard stochastic approximation arguments,
prove that convergence is guaranteed for SGD iteration using (0) (xe(2²) (T)))) Vo oo y T(. x:) (which is unbiased estimator for the objective) to the optimal solution of problem []] For details and proof, see Appendix B
Remark 2. The gradient approximation Vo (z) is not the true gradient of K However, this approximation is sufficient to ensure convergence of the policy Tg to a fixed point of the operator (, provided we have a fully parameterised policy. Such an approximation is also easy to compute from sampled points E X both on- and off-polliy. Other types of policy parameterisation. may also yield a fixed point of (-TT) it it is such that we can make the policy state independent, i.e., if there is a parameter 0 for which (o(x)) = wo (y) for all x, y E X. This the case, for example, when considering general neural network architectures if we set the weights to zero (but not the bias).
Assumption 2 (Learning Rates), We assume all learning rates arlzz u) E [0, 1] satisfy the condi- tions Σ (1 u) 0o and Ee= ar(2, u)? C0.
Now, the convergence of PB-LRL algorithms is guaranteed as long as the original policy gradi-
Algorithm LRPG
I: input Simulator, T,E
ent algorithm (such as PPO (Liu et al. 2019)
2: initialise 8, critic (if using), A, (B,,, n)
or A2C (Konda & Tsitsiklis 2000 Bhatnagar
3: set = 0, 22 ~ Pgg
jet al.] 2009)) for each single objective con-
4: while < max mnaxxiterations do
verges Skalse et al. (2022b). We can then com-
5: perform u,, T0(2))
bine Lemma | with these results to guarantee that Lexicographically Robust Policy Gradient
6: observe Tt. 2x.1, sample y ~ T(. x))
7:
(())) not converged then hn < K1 (1)
(LRPG), Algorithm [ that maximise robustness while remaining (ap-
converges
a policy
update critic (if using)
9: update @ and À using equation I
proximately) optimal with respect to R.
10:
output 8
Theorem 2. Consider a DOMDP as in Defi- D and let xo be a parameterised policy. Take (0) = BE [V (20)) to be computed through chosen algorithi (c.g.. A2C, PPO) that optimises (0))), and let K2(0) (0). Given an e > O, if the iteration 8 + proje [ + Voki] is guaranteed to converge to a parame- ter set 0* that maximises Ki, and hence J (locally or globally), then LRPG converges a.s. under PB-LRL conditions to parameters Of that satisfy:
nition
0 E arg min (0) such that Bg0'
KJ (())))
(6)
where O' θ 0f is globally optimal and a compact local neighbourhood o otherwise.
We reflect again on Figure [ The main idea behind LRPG is that by formally expanding the set of acceptable policies with respect to Kj, we may find robust policies more effectively while guaran- teeing a minimum performance in terms of expected rewards.
5 EXPERIMENTS
We verify the theoretical results of LRPG in series of experiments on discrete state/action safety- related environments (Chevalier-Boisvert et al. 2018). safe exploration tasks where the agent needs navigate environment with cliff-like regions and receives a reward of when it finds a target. Minigrid-DynamicOhal DynanicObstaccles is a dynamic obstacle- avoidance environment where the agent is penalised for hitting obstacle, and gets positive
Minigrid-Lavvarostee LavaCrossing
7

---

Under review as a conference paper at ICLR 2023
(a) MiniGrid- Lap
(b) MiniGriddLavaarssseete LavaCrossing
(c) MiniGriid-Dynamii
Figure 2: Screenshots of the environments used.
reward when finding target. Minigrid-LavaGap small enough be fully observable, and the other two environments are partially observable. In all cases observations consist of 7 x field of view in front of the agent, with 3 channels encoding the color and state of objects in the environment. We use A2C (Sutton & Barto 2018) and PPO (Schulman et al. (017) for our implementations of LRPG which we denote by LR-PPO and LR-A2C, respectively.
all cases, the lexicographic tolerance was set to e = 0.99k; to deviate as little as possible from the primary objective.
Sampling T To simulate π we disturb as 5 S ~ U[-b0)] (7") with 2 (1.5 for LavaCrossing) and (2) and Gaussian noise (79) such that E (0, We test the resulting policies against noiseless environment (0), kernel T₃ 7 and kernel T2 Tv. The main point of these combinations to also test the policies when the true noise 7 is similar to T.
for (1) uniform bounded noise signal
General Robustness Results. Firstly, we investigate the robustness of four algorithms where we do not have Q function. we do not have an estimator for the critic Q", Proposition [ suggests that minimising the distance between and (T, 7) can serve as a proxy to minimise the robustness regret. We consider the algorithms:
1. Vanilla PPO (noiseless).
3. LR-PPO with Gaussian noise kernel (KT) SA-PPO from Zhang et (2020).
LR-PPO with a uniform noise kernel (KY).
In these experiments, we use PPO with a neural policies and value functions; the architectures and hyper-paramettrs used in each case can be found Appendix C The results are summarised in the left-hand side of Table Each entry is the median of 10 independent training processes, with reward values measured as the mean of 100 independent trajectories.
Robustness through Disadvantage Objectives. If we have an estimator for the critic Q we can obtain robustness without inducing regularity the policy using D yielding a larger policy sub- space to steer towards, and hopefully achieving policies closer to optimal. With the goal of diving deeper into the results of Theorem we consider the objective:
KD(0) = Σ Mao
(Ro (x) 1T
1TT (x, (2,1
ZEX
We aim test the hypothesis introduced through this work: by setting K₂ KD and thus aiming to minimise the disadvantage D, we may obtain policies that yield better robustness with similar expected rewards. Observe that TD II following algorithms on the same environments:
KD(TD) 0. To test this, compare the
1. Vanilla A2C (noiseless).
3. IR-A2C with K
2. IR-A2C with Ky.
4. I.R-2C with K₂ = Kp-
We use A2C in this case since the structure of the original cost functions are simpler than PPO, and hence easier to compare between the scenarios above, and we modified A2C to retain a Q function as critic. With each objective function resulting in gradient descent steps that pull the policy towards different maximally robust sets (Ky + II, and Kp + II respectively). we would expect to obtain increasing robustness for Kp. The results are presented in the right-hand side of Table
8

---

Under review as a conference paper at ICLR 2023
PPO on MiniGrid Environments
A2C on MiniGrid Environments
Noise
Vanilla (K))
SA-PPO
Vanilla
LRaac (K.))
(K))
LavaGap
0.95=0.003
0,95-00075
0,95-00101
0.9440.068
0.94400004
0.94::00005
0.94=00003
0.94=0.006
T1
0.80=000441
0,95=00078
0,93+00124
0.89
0.83+00.661
0,93-20.019
0.89=00.032
0.910
T2
0.92::0.015
0.05::00052
0.959400094
0.93::00000
0.89:000099
0,94:10.008
0.93:10.011
0.93-00021
LavaCrossing
0.95=00023
0,93400.000
0,9540.018
0.88:40.011
0.91:000024
0.91-000033
0.90=000177
0.92-0.034
Ti
0,50=0.110
0.92=000033
0.89=000229
0064
0.66=00071
0.78+-0.111
0.72=00073
0.76=0.098
T2
0.84::0.661
0.92-:0.050
0.92::0.021
0.85::00044
0.78:10.054
0.83::0.105
0.86::0.029
0.87=0.03
Dynomic Obstaallsss
0.91=
0.90
0.911:0.007
0,11
0.911:0.011
0.88:100000
0.89::0:009
0.013
Ti
0.23110,201
0.102
0.6111.119
0.851..188
0.27 0.27110.104
0.43
0.461.0.162
0.26_0.277
T2
0.50+0.1117
0.75=10.075
0.70::0.022
0.68::0490
0.54000066
0.53:00109
0.52:0.161
0.67=0.203
Table I: Reward values gained by LRPG and baselines.
6 DISCUSSION
Experiments. We applied LRPG on PPO and A2C algorithms, for a set of discrete action, dis- crete state grid environments. These environments are particularly sensitive to robustness problems; the rewards are sparse, and applying a sub-optimal action at any step of the trajectory often leads to terminal states with zero (or negative) reward. LRPG successfully induces lower robustness re- grets in the tested scenarios, and the use of KD as an objective (even though we did not prove the convergence of a gradient based method with such objective) yields a better compromise between robustness and rewards. When compared to recent observational robustness methods, LRPG obtains similar robustness results while preserving the original guarantees of the chosen algorithm (it even outperforms in some cases, although this is probably highly problem dependent, so we do not claim an improvement for every DOMDP).
Further Considerations on LRPG. The characterisation of robustness policy being invari- ant to a stochastic operator may be useful for other versions of robustness RL. For example, in robustness against transition probability disturbances (or distributional shifts), one may consider distribution ambiguity sets and exploit distributionally robust optimisation ideas to investigate pol- icy invariances. In this case, investigating the structure of maximally robust policies may yield mechanism to design RL algorithms that are generally robust to model uncertainties.
Shortcomings The motivation for LRPG comes partially from the situation where, when deploy- ing model free controller in a complex dynamical system, we may not have feasible way of estimating the noise generator. There is an alternative approach for robust RL (exploited most of the literature), which consists on taking a disturbance structure (e.g. adversarial noise) and training directly to optimise the rewards in the disturbed MDP. Apart from LRPG preserving formal guaran- tees, there is no clear answer over what approach is more rational, more effective in general. The choice would depend on the problem at hand, the possible existence of an adversary, the requirement (or lack thereof) for formal guarantees, etc. We cannot claim that our approach is better in every way; we simply show through this work that it is a useful approach for learning policies in specific problems where, for example, we need control dynamical system where the noise sources are unknown and we need to retain certain formal guarantees of the algorithms used.
Robustness, Complexity and Invariances. Sections Sections@aand33 diicuuss at large the structure, shape and dependence of the maximally robust policy sets. These insights help derive optimisation objectives to use in LRPG, but there is more to be said about how policy robustness affected by the underlying MDP properties. We hint at this in the proof of Corollary [ More regular (less complex in entropy terms, or more symmetric) reward functions (e.g., reward functions with smaller variance across the actions R(I, ", 2)) seem to induce larger robust policy sets. In other words, for a fixed policy, more complex reward function yields larger robustness regrets as soon as any noise is introduced in the system. This raises questions on how to use these principles to derive more robust policies in comprehensive way, but we leave these questions for future work. Additionally, one could extend these ideas use LRL to obtain policies that generalise a subelass of reward functions.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Mohammed Amin Abdullah, Hang Ren, Haitham Bou Ammar, Vladimir Milenkovic, Rui Luo, Mingtian Zhang, and Jun Wang. Wasserstein robust reinforcement learning. arXiv preprint arXiv:/907.13: 13.00..../96.. 2019.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. J. Mach. Learn. Res., 22 (98):1-76, 2021.
Vahid Behzadan and Arslan Munir. Vulnerability deep reinforcement learning to policy induction attacks. In International Conference on Machine Learning and Data Mining in Pattern Recogni- tion, pp. 262-275. Springer, 2017.
A. Ben-Israel and B. Mond. What is invexity? The Journal of the Australian Mathematical Society. Series Applied Mathematics, 28(1):1-9, 1986a.
Adi Ben-Isracl and Bertram Mond. What invexity? The ANZIAM Journal, 28(1):1-9, 1986b.
Dimitri Bertsekas. Nonlinear Progranming. Athena Scientific, 1999.
Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3): 334-334, 1997.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint FrrXiv:1906.07760 2019.
Shalabh Bhatnagar, Richard S. Sutton, Mohammad Ghavamzadeh, and Mark Lee. Natural actor-critic algorithms. Automatica, 45(11):2471-2482, November 2009. doi: 10.1016/j.
automatica.2009.07 .008.
Vivek S. Borkar. Stochastic Approximation. Hindustan Book Agency, 2008.
V.S. Borkar and K. Soumyanatha. An analog scheme for fixed point computation. i. theory. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 44(4):351-355, 1997. doi: 10.1 109//115636222
Maxime Chevalier-Boisvert, Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. https://gitthut com/ max mecb/ wiw.o//ggymmmmmimm...o giriiiiiiiiiiiiiii.. 2018.
Esther Derman, Daniel Mankowitz, Timothy Mann, and Shie Mannor. A bayesian approach robust reinforcement learning. In Uncertainty in Artificial Intelligence, pp. 648 188-658.77 PMLR, 2020.
Michael Everett, Björn Lütjens, and Jonathan P How. Certifiable robustness adversarial state uncertainty in deep reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, 2021.
Mare Fischer, Matthew Mirman, Steven Stalder, and Martin Vechev. Online robustness training for deep reinforcement learning. arXiv preprint arXiv:1911.0000 2019.
Justin Fu, Katie Luo, and Sergey Levine. Learning robust rewards with adverserial inverse rein- forcement learning. In International Conference Learning Representations, 2018.
Adam Gleave, Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell. Adver- sarial policies: Attacking deep reinforcement learning. In International Conference on Learning Representations, 2020.
Morgan Hanson. On sufficiency of the kuhn-tucker conditions. Journal of Mathematical Analysis and Applications, 50(2):545-550 1981.
Matthias Heger. Consideration of risk in reinforcement learning. In Machine Learning Proceedings 1994, pp. 105-111. Elsevier, 1994.
Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
10

---

Under review as a conference paper at ICLR 2023
Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks on neural network policies. arXiv preprint arXiv:1702.02284, 2017.
H Isermann. Linear lexicographic optimization. Operations-RReserch-SPpoe Research-Spektrum, 4(4):223-22) 1982.
Richard Klima, Daan Bloembergen, Michael Kaisers, and Karl Tuyls. Robust temporal difference learning for critical domains. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '19, pp. 350-358, Richland, SC, 2019. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 978 1500663999
Vijay R. Konda and John N. Tsitsiklis, Actor-critic algorithms. In S. A. Solla, T. K. Leen, and K. Müller (eds.), Advances in Neural Information Processing Systems 12, pp. 1008-1014, MIT Press, 2000.
Jernej Kos and Dawn Song. arXiv:1705.0660 06452.. 2017.
Delving into adversarial attacks on deep policies. arXiv preprint
Yen-Chen Lin, Zhang- Wei Hong, Yuan-Hong Liao, Meng-Li Shih, Ming- Yu Liu, and Min Sun. Tacties of adversarial attack deep reinforcement learning agents. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pp. 3756-3762, 2017.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural trust region/proximal policy opti- mization attains globally optimal policy. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Ajay Mandlekar, Yuke Zhu, Animesh Garg, Li Fei-Fei, and Silvio Savarese. Adversarially robust policy learning: Active construction of physically-paasible perturbations. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3932-3939 IEEE, 2017.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pp. 1928-1937. PMLR, 2016
Janosch Moos, Kay Hansel, Hany Abdulsamad, Svenja Stark, Debora Clever, and Jan Peters. Robust reinforcement learning: A review of foundations and recent advances. Machine Learning and Knowledge Extraction, 4(1):276-315, 2022.
Jun Morimoto and Kenji Doya. reinforccee learning. Neural computation, 17(2):335-359, 2005.
Andrew Y Ng. Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In Proc. of the Sixteenth International Conference on Machine Learming, 1999, 1999.
Arnab Nilim and Laurent EI Ghaoui. Robust control of markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-798, 2005.
Xinlei Pan, Daniel Seita, Yang Gao, and John Canny. Risk averse robust adversarial reinforcement learning. In 2019 International Conference on Robotics and Automation (ICRA), pp. 8522-8528. IEEE, 2019.
Santiago Paternain, Luiz F. O. Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained reinforcement learning has zero duality gap. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 7553-7563, 2019.
Anay Pattanaik, Zhenyi Tang, Shuijing Liu, Gautham Bommannan, and Girish Chowdhary. Robust deep reinforcement learning with adversarial attacks. arXiv preprint arXiv:1712.03632, 2017.
Anay Pattanaik, Zhenyi Tang, Shuijing Liu, Gautham Bommannan, and Girish Chowdhary. Robust deep reinforcement learning with adversarial attacks. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '18 pp. 2040-2042 Rich- land, SC, 2018. International Foundation for Autonomous Agents and Multiagent Systems.

---

Under review as a conference paper at ICLR 2023
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforce- ment learning. In International Conference on Machine Learning, pp. 2817-2826. PMLR, 2017.
Matteo Pirotta, Marcello Restelli, Alessio Pecorino, and Daniele Calandriello. Safe policy iteration. In International Conference on Machine Learning, pp. 307-315. PMLR, 2013.
Mark J Rentmeesters, Wei K Tsai, and Kwei-Jay Lin. A theory of lexicographic multi-criteria optimization. In Proceedings of ICECCS 96: 2nd IEEE International Conference on Engineering of Complex Computer Systems (held jointly with 6th CSESAW and 4th IEEE RTAW), pp. 76-79. IEEE, 1996.
Jay K Satia and Roy E Lave Jr. Markovian decision processes with uncertain transition probabilities. Operations Research, 21(3)2288-740, 1973.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.06347, 2017.
Joar Skalse, Matthew Farrugia-Roberts Stuart Russell, Alessandro Abate, and Adam Gleave. In- variance in policy optimisation and partial identifiability in reward learning. arXiv preprint arXiv:2203.07475. 2022a.
Joar Skalse, Lewis Hammond, Charlie Griffin, and Alessandro Abate. Lexicographic multi-objective reinforcement learning. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, pp. 3430-3436, jul 2022b. doi: 0.224963/jjcai222224776
Morton Slater. Lagrange multipliers revisited. Cowles Commission Discussion Paper No. 403, 1950.
Matthijs Spaan. Partially observable markov decision processes. Reinforcement Learning, pp. 387-414. Springer, 2012.
Matthijs TJ Spaan and N Vlassis. A point-based pomdp algorithm for robot planning. In IEEE Inter- national Conference on Robotics and Automation, 2004. Proceedings. ICRA '04. 2004, volume 3, pp. 2399-24004 IEEE, 2004.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Proceedings of the 12th International Conference on Neural Information Processing Systems, NIPS'99, 99, pp. 1057-1063, Cambridge, MA, USA, 1999. MIT Press.
Kai Liang Tan, Yasaman Esfandiari, Xian Yeow Lee, Soumik Sarkar, et al. Robustifying reinforce- ment learning agents via action space adversarial training. In 2020 American control conference (ACC), pp. 3959-3964. IEEE, 2020.
Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and appli- cations in continuous control. In International Conference on Machine Learning, pp. 6215-6224. PMLR, 2019,
Elise van der Pol, Thomas Kipf, Frans A. Oliehock, and Max Welling. Plannable approximations to mdp homomorphisms: Equivariance under actions. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 200 pp. 1431-1439, Rich- land, SC, 2020. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 978 97844503551
Bart PG Van Parys, Daniel Kuhn, Paul Goulart, and Manfred Morari. Distributionally robust control of constrained stochastic systems. IEEE Transactions on Automatic Control, 61(2):430- 442, 2015.
Wolfram Wiesemann, Daniel Kuhn, and Melvyn Sim. Distributionally robust convex optimization. Operations Research, 128 2014.
12

---

Under review as a conference paper at ICLR 2023
Huan Xu and Shie Mannor. The cauustesss-prffrmmaae tradeoff in markov decision processes. Advances in Neural Information Processing Systems, 19, 2006.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Mingyan Liu, Duane Boning, and Cho-Jui Hsieh. Robust deep reinforcement learning against adversarial perturbations state observations. Ad- vances in Neural Information Processing Systems, 33:21024-21037, 2020.
Huan Zhang, Hongge Chen, Duane Boning, and Cho-Jui Hsieh. Robust reinforcement learning on state observations with learned optimal adversary. In International Conference on Learning Representation (ICLR), 2021.
Shangtong Zhang. Modularized implementation of deep algorithms in pytorch. github.cmmm hat./////co///aggooooogoaa//eeee 2018.
https://
13

---

Under review as a conference paper at ICLR 2023
A EXAMPLES AND FURTHER CONSIDERATIONS
We provide here two examples to show how we can obtain limit scenarios Hy II (any policy is maximally robust) or IIn IIr (Example 1), and how for some MDPs the third inclusion in Theorem is strict (Example 2).
Example Consider the simple MDP in Figure First, consider the reward function R1 (2 10, Ri (22, = O. This produces "dummy" MDP where all policies have the same reward sum. Then, VT, n, V(a.T) = V*, and therefore we have 1In = Il = Il.
{ +)
( +)
T2
( 5)
(
Figure 3: Example MDP. Values in brackets represent {P(:, u1, u2.
elsewhere. Take non- constant policy æ. i..,, (x1) * (x2)). In the example DOMDP (assuming the initial state is drawn uniformly from X, {a1, xz2) one can show that any time in the trajectory, there stationary
Now, consider the reward function (2 -) 10, :-(
probability Pr(x, x1 2. Let us abuse notation and write (2:;) = ( π (z u1) x < u2) )²
and R(x;)= ( R(z,, .) R(x, U2.)) )T. For the given reward structure we have R(æ²)
0 0 )T, and therefore:
x
( E
Σ
7 Re
5 (())) 7
Since the transitions of the MDP are independent of the actions, following the same principle as in equation 7 [TT, T) = } (R(x)), (T) i-
7 For any noise map (- () + Id, for the two-state policy it holds that & Hr = (n, T) # и. Therefore (T, (x1) # क (21) and:
5y
((T) - J((T, T)) = 1-7 (π(21, 1) - (T,, (x1,, 1)) #
which implies that x & Hl.
Example Consider the same MDP in Figure B with reward function R(21,
R(22, u1, = 10, and a reward of zero for all other transitions. Take policy - (21) = (1 0),
π (2x2) (0 1). The policy yields reward of 10 in state æ1 and reward of 0 in state 22. Again
assume the initial state is drawn uniformly from Xo- = [21, Then, observe:
J(x)= = Fxoruio
Rg
1 (R(x)), क (x:))
7
10y
5y
2
1- 21 21-7
1-7
1==
Define now noise map T(- æ1) ( 1) and T(- | x2) ( 1). Observe this noise map
yields policy with non-zero disadvantage, D (21, 7) 5/ (T- 2.5) 2.5 and similarly D" (I2, T) = 225, therefore π & pp. However, the policy is maximally robust:
((),T)) 1 (((1)), (T, (T,)) 7_ + ( (T, (xx))) 7
1 7 (5+5)
5y
-
21
(8)
Therefore, TTg
14

---

Under review as a conference paper at ICLR 2023
B THEORETICAL RESULTS
B.I AUXILIARY RESULTS
Theorem 3 (Stochastic Approximation with Non-Expansive Operator). Let {Ee} be random quence with & E 12th defined by the iteration:
S++1 = & + aF((E) - Ee + M++1),
where:
1. The step sizes Oi satisfy Assumption 2
2. F : R" + R is a || llso non-expansive map. That is, for any Ei E R", [F((1)
Fl - E2llo
3. {M} is martingale difference sequence with respect to the increasing family of a -ffeldds
F; = (Eo, Mo, E1, M,,.., Et, M,).
Then, the sequence &. + E* almost surely where 5" is fixed point such that F(g*) = =-
Proof. See Borkar & Soumyanatha (997).
Theorem 4 (PB-LRL Convergence). Let M be a multi-objective MDP with objectives K3, i E {1. m of the same form. Assume policy is twice differentiable in parameters 6 and if using a critic V; assume it is continuously differentiable on W;. Suppose that if PB-LRL run T steps, there exists some limit point w (0) when is held fixed under conditions on M, and V.. If lim [0] E O for m = then for any m. E we have limr TF, (0) E O where e depends on the representational power of the parameterisations of V4.
Proof Sketch. We refer the interested reader to Skalse et al. (022b) for a full proof, and here attempt to provide the intuition behind the result in the form proof sketch.
Let us begin by briefly recalling the general problem statement: we wish to take multi-objective MDP M with m objectives, and obtain a lexicographically optimal policy (one that optimises the first objective, and then subject to this optimises the second objective, and on). More precisely, for policy æ parameterised by 0, we say that π is (globally) lexicographically e-optimal E O where 0₁ θ is the set of all policies in M, 0 = {0 O maxgge; ((')) (0) 4), and p e > 0
The basic idea behind policy-based lexicographic reinforcement learning (PB-LRL) is to use a multi- timescale approach to first optimise 9 using K1, then at slower timescale optimise using K₂ while adding the condition that the loss with respect to K₃ remains bounded by its current value, and so on. This sequence of constrained optimisations problems can solved using a Lagrangian relaxation (Bertsekas) 1999). either in series or via a judicious choice of learning rates simultaneously. by exploiting a separation timescales (Borkar 2008). In the simultancous case, the parameters of the critic wi (if using actor-critic algorithm, if not this part of the argument may be safely ignored) for each objective are updated on the fastest timescale, then the parameters 0, and finally (i.e., most slowly) the Lagrange multipliers for each of the remaining constraints.
The proof proceeds via induction on the number of objectives, using a standard stochastic approx- imation argument (Borkar 2008). In particular, due to the learning rates chosen, may consider those more slowly updated parameters fixed for the purposes of analysing the convergence of the more quickly updated parameters. In the base case where
1, have (by assumption) that 4om [0] E 0₁ This is simply the standard (non-lexicographic) RL setting. Before con- tinuing to the inductive step. (Skalse al. (2022b) observe that because gradient descent on Ki converges to globally optimal stationary point when m tten KG must be globally invex (where
the opposite implication also true) (Ben-Israel & Mond 1986a
'The proof in Skalse et al.
2022bb also considers local lexicographic optima, though for sake of sim-
plicity, we not so here.
A differentiable function f: Ra RR (globally) invex if and only if there exists a function g R R" RR" such that f(x1) f(x2) 2 (()))))) ( for all z1, 22 R" Hanson 1981).
15

---

Under review as a conference paper at ICLR 2023
The reason this observation is useful is that because each of the objectives K2 shares the same functional form, they are all invex, and furthermore, invexity is conserved under linear combinations and the addition of scalars, meaning that the Lagrangian formed in the relaxation of each constrained optimisation problem is also invex. As a result, if we assume that limy-so E, [0] E O as our inductive hypothesis, then the stationary point of the Lagrangian for optimising objective K2+1 is
a global optimum, given the constraints that it does not worsen performance on K Ki..... K2. Via
Slater's condition (Slater 1950) and standard saddle-point arguments (Bertsekas) 1999 Paternain
et al. 2019), we therefore have that limy E, [0] E O completing the inductive step, and thus the overall inductive argument.
This concludes the proof that limy-+oc [ E O We refer the reader to Skalse et al. (202bb) for a discussion of the error e, but intuitively corresponds a combination of the representational
power of 0, the critic parameters w; (if used), and the duality gap due to the Lagrangian relaxation cases where the representational power of the various parameters is
(Paternain et al.] 2
sufficiently high, then it can be shown that = 0.
Lemma 1. Let be a furlm-pareeelrrisse policy in a DOMDP, and of learning rate satisfying Assumption Consider the following approximated gradient for objective KT(z) and sampled point x & X:
(o)x(0)(2) = (TT(()) Toly)) Then, the following iteration with x E and some initial 0o.
T(: xx).
(9)
0,+1 0. ao.
(10)
yields + 0 almost surely where á satisfies (0) = O.
Proof. See Appendix B.2
B.2 PROOFS
We now present the proofs for the statements through the work.
Proposition / If a policy π E Il is a fixed point of the operator (,,7), then it holds that (T, T) = m. Therefore, one can compute the robustness of the policy x to obtain p( = ( [( T)) ((x) - [(T)
= π E HIg. Therefore, II. C Il
For discrete state and action spaces, the space of stochastic kernels K.: A(X) is equivalent
to the space of row-stochastic [X] x |X| matrices, therefore one can write T x) = Tey as the -y-th entry of the matrix T. Then, the representation of constant policy an X U matrix can be written as π 1 where ||x| where (UU) is any probability distribution over the action space. Observe that, applying the operator (T, T`) to constant policy yields:
( T) = o
(11)
By the Perron-Frobenius Theorem (Hom & Johnson 2012), since T is row-stochastic it has at least one eigenvalue eig(?) = 1, and this admits a (strictly positive) eigenvector T1xx = 1|x-- Therefore, substituting this in equation I1
(T, T") = 71 T maxxi
= III.
Proposition 2 Recall the definition in equation and that the noise disadvantage function of
policy π is given by equation 4 We want to show that (zx 2') = 0 = p( 7) = 0. Taking
1t T') 0 one has policy that produces an disadvantage of zero when noise kernel 7 is applied. Then,
DJ T) = = (=-( (x= (x. u)] = YOEE. Now define the value of the disturbed policy
(12)
(Tn:))(o)) = E (n
Σ
xh Mr( uc)
P (5)
16

---

Under review as a conference paper at ICLR 2023
and take:
VinT)())) (x) By [ u. +v((n
(v))
g) (.,u)
We will now show that (z) V(a.T) (x), for all E X. Observe, from equation 12 using
V*(x) (x)) = (a, Q2 (Ir, u)]. we have Vor E X:
V=(x) ((t))-((..)) (z) =E E
u)) (x ((c,u,y) vV x-P(--a.))
(x, [1 u. +VV (v) rxx,,u,)) - -gV(0-)) P(-l,)))
(13)
(=(() - ((.
Now, taking the sup norm at both sides of equation 13 we get
IIV (x) (= (x)ll> = P(- (TT()) - V(n.T (v)
(14)
Observe
that for the right hand side of equation
14
we
have
Ey-pa) (v) ( >( (w)ll & (x) - (i (x)]loc. Therefore, since < 1,
||V (x) V(=.T) (x) S (x) v(a.T) (1)))())))1a> = IV*((x) - Vin.T (x) = 0. (15)
Finally, [V) - (x) = = (²(x) - Vi=20 = 0 Ve E X, and V*(x)
((nT) (x) = 0V x = J(T) = J(( 7)) p( 7) = O.
Inclusion Theorem / Combining Proposition T and Proposition
2 we simply need to show that and from the definition in
I1 II. Take æ be fixed point of (T,, T). Then (,, T)
equation 4
Dd
(x 10" (x, w)]
-V)(x)
EL 10" (z,u))
-V)( V*(x)
-0.
Therefore, x E Hp, which completes the sequence of inclusions.
To show convexity of II, Ily, first for constant policy हे E II, recall that we can write т = 1 where u E A(U) is any probability distribution over the action space. Now take Tı, T22 E II. For any a E [0, 1), am (1 TT = alvI + (1 au. 1(av) + (1- a))e)) II.
At last, for the set II,, assume there exist two different policies Tı, T2 both fixed points of (- T)) Then, for any a [0. 1]. ((aT) + (1- a2) T) aT'; + (1 T) am + (1 a R2. Therefore, any affine combination of fixed points is also a fixed point.
Corollary 7 For statement ii) let :(....) = c for some constant c E R. Then, J(x) = Exg~ro 2 TTe π]
which does depend the policy n. For any noise kernel T
and policy म. (TT - J (T,,
= π E ll..
For statement assume Im E Ho $ 11. Then, Ex X and u² e U such that ((x",u)) + (T,, (x" u*
Let:
R(x, u, x') u,xa)===() := { otherwise
Sc if = x² and u == u²
Then, E[R(2,, [x),,=] E(R(a, (T,, (x), x') and since the MDP ergodic visited infinitely often and (TT) -J(TTT))) > 0 = & Ho. which contradicts the assumption. Therefore, I1 11, = 0 = II. =II..
Lemma [ We make of standard results stochastic approximation with non-expansive op- erators (specifically. Theorem 3 in the appendix) Borkar & Soumyanathal (1997). First, observe that for fully parameterised policy, one can assume have tabular representation such that
17

---

Under review as a conference paper at ICLR 2023
(o u) oz and VoTo (2)) = Id. We can then write the stochastic gradient descent problem in terms of the policy. Let y T( z). Then:
T+)1 - (x) 04 (me(T) Te(y))
= (x)) au (T((2)) (me. (x) (Tr(V) (me, (T)))
We now need to verify that the necessary conditions for applying Theorem hold. First, ar satisfies Assumption 2 Second, making use of the property || for any row-stochastic matrix T, for any two policies T1, E II:
(T T> (T2, T7 ac 11'T - Talloo = (T 12) -
| -22llx || T2 Io.
Therefore, the operator (+, T) is non-expansive with respect the sup-norm. For the final condition, we have
E (/ (T(()) (TT, (x) Te, T]
Σ VEX
T(y x))((()) (T (x)
Therefore, the difference Te (e( (Ie, (xx is martingale difference for all x. One can then apply
Theorem 3 with (x(x) = (x). F()) = () and M =\t =<( (Te; (xx) to conclude that
(a(x) (z) almost surely. Finally from assumption [ for any policy all states X are visited infinitely often, therefore (x) (x))v X (+) O.
# and satisfies (it, T) n, and
Theorem We apply the results from Skalse et al. (2022b) in Theorem Essentially, [Skalse et al. (20226) prove that for a policy gradient algorithm to lexicographically optimise a policy for multiple objectives, it a sufficient condition that the stochastic gradient descent algorithm finds optimal parameters for each of the objectives independently. From Lemma [ we know that policy gradient algorithm using the gradient estimate in equation converges to a maximally robust policy, i.e. a set of parameters 8' arg max, K, Additionally, by assumption, the chosen algorithm for K1 converges to an optimal point 0* While the two objective functions are not of the same form - as in Skalse al. (2022b) the fact they both invex (Ben-Israel & Mond 1986b) either locally or globally depending on the form of K1, implies that K is also invex and hence that the stationary point 0 computed by LRPG satisfies equation
B.3 ON ADVERSARIAL DISTURBANCES AND OTHER NOISE KERNELS
problem that remains open after this work is what constitutes an appropriate choice of T, and what can we expect by restricting a particular class of î. We first discuss adversarial examples, and then general considerations on versus T.
As mentioned in the introduction, much of the previous work focuses on adver- sarial disturbances. We did not directly address this in the results of this work since our motivation lies in the scenarios where the disturbance is not adversarial and is unknown. However, following the results of Section we are able to reason about adversarial disturbances. Consider an adversarial map Tade to be
Ad Aeersariall Noise
(T,, (a) Tty), y E argmax,yex.x()) d(T(L), T()))
with Xad C being a set of admissible disturbance states for x, and d((..) )) distance measure between distributions (e.g. 2-norm).
Proposition 3. Constant policies are a fixed point of Tadv, and are the only fixed points if for all pairs Fo, 2% there exists a sequence {Zo. ..., I& } C X such that x; E Xad(x.).
Proof. First, is straight-forwar that if E πI - ( (T) = (zx) To show they are the only fixed points, assume that there is non-constant policy x' that is fixed point of Tad. Then, there exists x, 2 such that 7' (xx # N 7(()). However, by assumption, we can construct a sequence (x...., 2} C X that connects and = and every state in the sequence is in the admissible set of
18

---

Under review as a conference paper at ICLR 2023
the previous one. Assume without loss of generality that this sequence is {x.y,2}. Then, if a' is a fixed point, (5', Tade) (z) = x (z), (I',
(ade) = n (')) and (x', TTdea (z) = (2). However, d(r' (v), (z)) o O, therefore x'' cannot be a fixed point of Tadu-
(x) x' so either (x) (1)
# 0 or (2)) # x2)
The main difference between an adversarial operator and the random noise considered throughout this work is that Tado being modified at every time step of the PG algorithm). Therefore, including it as a LRPG objective would invalidate the assumptions required for LRPG retain formal guarantees of the original PG algorithm used, and it is not guaranteed that the resulting policy gradient algorithm would converge.
a linear operator, and additionally, it time varying (since the policy is
Assumption of Noise Kernel A question emerging from Section 4 is how to choose T, and how the choice influences the resulting policy robustness towards any other true T. general, for any arbitrary policy landscape with respect to utility in given MDP, there is no way of bounding the distance of resulting policies for two different noise kernels Ti, T2. As a counter-example consider a MDP where there are 2 possible optimal policies πi, my. and take these two policies to be maximally different, iee. [x) < (x)]l = 1 Yz E X. Then, when using LRPG to obtain a robust policy, a slight deviation the choice of can cause the gradient descent scheme to deviate from converging "ं converging to n². yielding in principle completely different policy. However, what remains bounded is the optimality of the policy: Through LRPG guarantees we know that, for both cases, the resulting policy will be at most far from the optimal sum of rewards. We can, however, state the following. Take T to be any arbitrary noise kernel, and T kernel that satisfies 11 = II. Let π to be a policy resulting from a LRPG algorithm. Assume, for distance metric d, 1. Then, holds for any T that mil d(TT, X²) S a: That is, the resulting policy is at most a far from the set of fixed points (and therefore a maximally robust policy) with respect to the true T. This is the key argument behind our choices for T: A priori, the most sensible choice kernel that has no other fixed point than the of constant policies.
that min d((T, T') S for some
C EXPERIMENTS METHODOLOGY
We use the experiments well-tested implementations of A2C and PPO adapted from Zhang 2018) include the computation of the lexicographie parameters equation [ Since all the environments
use a pixel representation of the observation, we use a shared representation for the value function and policy, where the first component is convolutional network, implemented in Zhang (018). The hyper-parameters of the neural representations are presented in Table
Layer
Output
Func.
Convl
16
ReLu
Conv2
32
ReLu
Conv3
64
ReL.u
Fc4
256
ReLu
Table 2: Shared Observation Layers
The actor and critic layers, for both algorithms, are a fully connected layer with 256 features as input and the corresponding output. We used in all cases an Adam optimiser. We optimised the parameters for each (vanilla) algorithm through a quick parameter search, and apply the same parameters for the Lexicographically Robust versions.
19

---

Under review as a conference paper at ICLR 2023
LavaCiap
LavaCrossing
DynamicObstacles
Steps
10"
10
8 x 10
0.99
0.999
0.99
a
0.001
0.001
0.001
e(Adam)
10
10-8
10-
Grad. Clip
0.5
0.5
0.5
Gae
0.95
0,95
0.95
Rollout
256
512
256
Table 3: A2C Parameters
LavaGap
LavaCrossing
DynamicObstacles
Parallel Envs
8
8
Steps
10c
106
8 x 10s
7
0.99
0.99
0.99
0.001
0.001
0.001
(Adam)
10-3
10
10-8
Grad. Clip
0.5
0.5
0.5
Ratio Clip
0.2
0.2
0.2
Gae
0.95
0.95
0.95
Rollout
256
512
256
Epochs
10
10
10
Entr. Weight
0
0
0
Table 4: PPO Parameters
For the implementation of the LRPG versions of the algorithms, in all cases we allow the algo- rithm iterate for 1/3 of the total steps before starting compute the robustness objectives. In other words, we use (()) = (0) until = 3 max_steps, and from this point we resume the lexicographic robustness computation as described in Algorithm [ This is due to the structure of the environments simulated. The rewards (and in particular the positive rewards) are very sparse in the environments considered. Therefore, when computing the policy gradient steps, the loss for the primary objective is practically zero until the environment is successfully solved at least once. implement the combined lexicographic loss from the first time step, many times the algorithm would converge to a (constant) policy without exploring for enough steps, leading to convergence towards maximally robust policy that does not solve the environment.
Noise Kernels. We consider two types of noise; normal distributed noise 7o and uniform distributed noise T For the environments LavaGap and DynamicObstacles, the kernel T produces a disturbed state à = x + & where [|| < 2, and for LavaCrossing ||[| x 1.5. The normal distributed noise is in all cases (00, 0.5). The maximum is due to the structure of the observations in these environments. The pixel values are encoded as integers
of the noise is quite large, but this
where each integer represents different feature in the environment (empty space, doors, lava, obstacle, goal..... Therefore, any noise ||E]| < 0.5 would most likely not be enough to confuse the agent. On the other hand, too large noise signals are unrealistic and produce pathological environments. All the policies are then tested against two "true" noise kereels,
T and
T2 19, The main reason for this is to test both the scenarios where we assume wrong noise kernel, and the case where we are training the agents with the correct kernel.
LRPG Parameters. The LRL parameters are initialised in all cases as 38) 2, 38 and n = 0.001. The LRL tolerance is set to e = 0.99k; to ensure we never deviate too much from the original objective, since the environments have very sparse rewards. We use first order approximation to compute the LRL weights from the original [MORL implementation!
Comparison with SA-PPO. One of the baselines included is the proposed in Zhang et al. (200)). The implementation includes an extra parameter that multiplies the regularisation objective, kppo- Since were not able find indications the best parameter for
PPO algorithm
20

---

Under review as a conference paper at ICLR 2023
PPO on MiniGird Emvironments
A2C on MiniGrid Environments
Noise
Vanilla (K))
LR)
SA-PPO
Vanilla (KX) (Racc(33)
(Kx)
LovaGap
0.95=00003
0.95=0.075
0,9540.101
0.94+00068
0.94+00004
0.94=00005
0.94=0.003
0.94=00.006
T1
0.80=0.041
0.95=0.078
0,93=00124
0.8620.064
0.83+000661
0.93=200019
0.89=0.032
0.91
0.92::0:015
0.95::0052
0.951:00094
0.931000000
0.891:0.029
0.94:10.008
0.93=0.011
0.93:10.021
Te
0.56
0.11
0,911000766
0.9
0.92.10.034
0.043
0.93:10.015 0.047
7
0.20=
0.90=0.124
196
0.90=10.33
0.75
0.94:00000
0.92=0.038
0.8840
T24m
0.00
0.71
0,2157
0.87=201116
0.27=00119
0.79=
0.68=0.127
0.56=002499
LovaChssiing
0.95=0.023
0.93=00000
0.93
0.88:00009
0.91
0.91
0.90=0.017
0.92:10.034
T1
0.50=0.110
0.92=0.053
0.0920.029
0.64
0.66::0.071
0.78::0.111
0.72=0.073
0.76=00098
T2
0.84=0.061
0.92=0.050
0.92:00021
0.85::0.094
0.78:t0.054
0.83-00.105
0.86=0.029
0.87 0.06
T
0.29=0.098
0.91=000881
0.91=00054
0.87=00045
0,56+0.039
0.01
0.43=0.04]
0.18
0.03=00022
0.8
0.8611.132
0.89110059
0.27::0158
0.25
0.17=00067
0.461
T
0.0=0.004
0.5
0.38:0.020
0.82::0.02
0.06
0.04:00030
0.01
0.09:00.000
Obbtacee
0.91=0.002
0.01=00008
0,91
0.91
0.91-:0.011
0.80
0.89=0.009
0.91 0.001
Ti
0.23:10.201
0.77 0.102
0.6119
0.5510.188
0,27:10.104
0.43100108
0.45
0.56 1 0.270
T2
0.50=0.117
0.75=0.075
0,70::0002
0.68::0490
0.45:10.886
0.5310.109
0.52-0.161
0.67 0.200
T
0.74=0.230
0.89=0.118
0.85+0.061
0,90=:0112
0,46+t02214
0.55=0.197
0.51=0.371
0.62:
0.26=0.269
0,79=0.157
0.68
0.14
0.19:4.2284
0.15
0.23=0.370
0.10:
-0.49=0.312
0.51=00234
0.33+00222
0.55=0.170
-0.54::02009
0.211:0192
-0.53=0.261
.0.51=10.260
Table 5: Extended Reward Results.
discrete action environments, implemented Apppo 1,,1, and picked the best result for each entry in Table [ Larger values seemed to de-stabilise the learning in some cases. The rest of the parameters are kept as in the vanilla PPO implementation.
C.I EXTENDED RESULTS: ADVERSARIAL DISTURBANCES
Even though we do not adversarial attacker disturbance in our reasoning through this work, we implemented a policy- against, and evaluate how well each of the methods reacts to such adversarial disturbances.
policy-based based state-adversarial noise disturbance to test the benchmark algorithms
Adversarial Disturbance We implement a bounded policy-based adversarial attack, where at each state x we maximise for the KL divergence between the disturbed and undisturbed state, such that the adversarial operator is:
Tado (y) x)) =
> E arg max (Tz(
s.t. || a1|2 S..
The optimisation problem is solved at every point by using Stochastic Gradient Langevin Dynam- ics (SGLD) optimiser. The results are presented in Table
This type of adversarial attack with SGLD optimiser was proposed in ZZhag al. (2020) As one see, the adversarial disturbance is quite successful at severely lowering the obtained rewards in all scenarios. Additionally,
expected SA-PPO was the most effective at minimizing the disturbance effect (as it is trained with adversarial disturbances). although LRPG produces reasonably robust policies against this type of disturbances well. last, A2C appears to be much more sensitive to adversarial disturbances than PPO, indicating that the policies produced by PPO are by default more robust than A2C.
21


Reviews:
[{"review_id": "gpC7sDSaBX", "reviewer": "Reviewer_rSvU", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the robustness of reinforcement learning with respect to observational disturbances. They proposed to use a recently proposed lexicographic optimization framework. Experiments on 3 grid worlds type environment and compare against an adversarial training RL baseline and one naive baseline without considering environmental uncertainty.", "summary_of_the_review": "This paper considers policy robustness in RL with respect to observation disturbance. They used a lexicographic optimization framework that can be plugged into different policy optimization algorithms. The method sections (Sections 3 and 4) need to be significantly improved for readers to follow and provide the rationale why the proposed objective function (e.g., eq 5-6) are reasonable objectives, and how to compute them efficiently when the environmental model is unknown. The choice of simulation environment (all discrete state action grid world MDPs) and the comparison to existing algorithms are insufficient. ", "strength_and_weaknesses": "Strength: The problem studied in the paper - RL with respect to observation perturbation is an interesting and important problem.\n\nWeaknesses:\n\n* Section 3 and 4 are written in a convoluted way and is very hard to follow. \n\n* In (5), how to compute <\\pi_{\\theta}, \\tilde{T}>(x), for arbitrary policy \\pi_\\theta? Why optimizing (5) (rather than optimizing the expected J(\\theta)) is a good or even meaningful objective function?\n\n* Algorithm 1 states MDP and \\tilde{T} as input. Does it mean the proposed method requires model knowledge of the MDP? If so, that seems very unrealistic since one of the main motivations of using RL for real-world control is that the environment model is unknown. Also, how is the \\tilde{T} computed?\n\n* In (6), which is formulated as a lexicographic optimization problem. How does K_2(\\theta) is computed? Also, how is K_1^* computed without knowing the ground-truth MDP?\n\n* It is not clear what is the main advantage that lexicographic optimization provides compared to tons of stochastic and robust RL frameworks. The authors argue that a min-max framework might be too conservative - but there are tons of other works that consider different models of environmental noise and takes a weighted combination of the average or worst-case cost.\n\n* The experimental section is rather short. More importantly, the choice of the environment (all discrete state action grid world MDP) and the choice of baselines are insufficient. Experiments on Mujoco and comparison to recent robust RL works are needed (many related works are mentioned in Section 1).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "fKGPDe9SjP", "reviewer": "Reviewer_WdQf", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers reinforcement learning in an observationally-disturbed MDP (DOMDP), where the learning agent is able to access the full state, but the state is disturbed by some unknown random signal when deploying actions. The paper provides theoretical characterization of the robust policy set, which constructs sufficient conditions to learn a robust policy. Inspired by the theoretical findings, the paper develops an algorithm based multi-objective optimization to learn a policy that is robust to the disturbing while still preserving optimality. Finally, the paper conducts empirical studies to show the effectiveness of proposed method. ", "summary_of_the_review": "I recommend rejecting this paper as the problem setup and some implementation details are not clear to me. Please correct me if I missed anything important. I am happy to adjust my score based on how well the authors answer the questions in the rebuttal. ", "strength_and_weaknesses": "Strength \n\nThe paper considers a problem setting where the observation for a learning agent can be perturbed by some random noise.  A multi-objective learning algorithm is proposed to solve this problem. Both theoretical and empirical studies are provided. \n\nWeakness\n\nI have some questions and concerns about the problem setting and practical implementation of the algorithm. Please correct me if I missed anything important. I am happy to adjust my score based on how well the authors answer the questions in the rebuttal. \n\n1. I am a little bit confused by the problem definition. Is there any application that motivates this setting? According to Definition 1, in a DOMDP, the transition of the underlying MDP is not effected by the random disturbing kernel. It is also suggested that the learning agent can access the full state, just that the policy will be disturbed by a certain mapping. This definition is very confused to me given the “robot navigation in a dangerous environment” example in the appendix, where it seems that the transition kernel should also be effected by the disturbing mapping? \n\n2. I think the robustness of a policy should be related to the maximum possible perturbation. That is, one cannot expect a certain degree of robustness given an extremely adversarial disturbing signal. Maybe only when $T$ is not that “adversarial” (e.g. using SLAM in navigation where the computed position is near the true position) some good theoretical properties can be guaranteed. Which result discusses such connection? \n\n3. It seems that the authors consider an extreme case, where the learning agent does not have any information about $T$, and cannot even estimate the random noise from data. Is there any motivation to consider such problem? In the worst case, I don’t think one can expect to find any good algorithm. \n\n4. Should it be $K_{\\tilde{T}}$ in equation 5? The paper argues that a reasonable choice of $\\tilde{T}$ is the uniform distribution. I agree with this, as in the problem setting no prior knowledge of $T$ is given. But it seems that a uniform $\\tilde{T}$ (or even gaussian) is not available in most RL problems? \n\n5. Since $\\tilde{T}$ and $T$ could be arbitrarily different. How does the difference (measured by any probabilistic divergence measurement) affect the robustness of learned policy? \n\n6. I am wondering how does the MiniGrid environment is modified in the experiments. It seems to me that at a given state, an action is taken by sampling from a distribution computed by Equation 1, but the transition and reward are not affected?  Is it correct? \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "dE7wRqd6Ju", "reviewer": "Reviewer_9ZEw", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work studies robustness to observations perturbations which are generated according to a stochastic kernel. It first characterizes robust policies by operator invariant sets, then formulates robustness criteria via a lexicographic objective. The proposed scheme preserves the convergence properties of vanilla policy-gradient algorithms and helps achieve robust policies. ", "summary_of_the_review": "For the reasons above, I recommend acceptance of this paper. \n\nQuestion to the authors: \nThe way this study tackles uncertainty is specific to observation perturbation. Yet, it may be equivalently formulated to tackle transition perturbation or, perhaps also, action perturbation. Have you investigated such directions? For example, under which conditions does maximal robustness hold robustness guarantees to model (reward, transition) perturbations? ", "strength_and_weaknesses": "The paper is well-written and easy to follow. The objectives are clearly formulated, which makes the reading enjoyable. This work is also well-motivated: how to ensure robustness to observation perturbations without altering the theoretical convergence of existing policy-gradient algorithms. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "WqWI1gIl2zT", "reviewer": "Reviewer_BQBq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of observationally robust reinforcement learning.  In this setting, an agent learns via interacting with an MDP, but is evaluated in a version of this MDP where noise is added to the observed states by applying an (unknown) “noise kernel” $T: X \\rightarrow \\Delta(X)$; this evaluation environment is called a observationally-disturbed MDP (DOMDP), and is a form of POMDP.\n\n\nThe main idea is to apply lexical reinforcement learning (LRL) to this problem.  Lexical RL algorithms optimize over multiple (e.g. 2) objectives, say $R_1$ and $R_2$, to find the best policy according to $R_2$ among those that are (approximately) optimal according to $R_1$ (i.e. prioritizing $R_1$ over $R_2$).  In this case, performance (i.e. value of the policy) on the MDP is $R_1$, and the drop in performance resulting from some proxy noise kernel $\\tilde{T}$ is $R_2$.\n\nThe main benefit claimed is the guarantee that LRL will yield an approximately optimal policy, while previous approaches to observationally robust reinforcement learning may sacrifice arbitrary amounts of performance in the MDP in order to achieve robustness.  ", "summary_of_the_review": "While this work is well executed, I'm not convinced by the technical contributions, motivation, or significance.\nBut the author's response could potentially convince me on these points, and I believe the issues of clarity could be addressed in the revision.", "strength_and_weaknesses": "\nStrengths:\n- Quality and Clarity (see next section)\n\n\nWeaknesses:\n- Novelty (see next section)\n- The motivation for applying LRL to observationally robust reinforcement learning is unclear.  The abstract and introduction mention “explainability”, but this is not elaborated on.  Regarding the argument that this work provides a guarantee: this is a guarantee of eps-optimal performance in the MDP, but it is not clear why we care about performance in the MDP (vs. the DOMDP) in this setting.  This could be motivated by the unknown nature of $T$: if nothing is known about $T$, then it seems sensible to aim to optimize performance in the MDP, and hope $T$ only introduces mild noise.  On the other hand, in the worst case, $T$ can render observations useless at test time, in which case we might be much better off using a different approach (e.g. one that aims to optimize the performance of a constant policy).  No clear guidance is given for when the approach taken in this work is preferable, but “guarantees” are advertised without appropriate caveats.\n- Somewhat related to the previous point: I'm not convinced by the choice of $\\tilde{T}$ as “any stochastic kernel whose set of fixed points coincides with the collection of constant policies”.  This choice is only discussed minimally, and seems weakly motivated via allowing Theorem 2, and generic maximum entropy considerations.  The experiments are too limited to be informative about whether this is a good choice in practice, and if we knew more about $T$, the entire approach suggested in this work might be suboptimal. \n- Overall, more discussion is needed to justify the significance of this work, and to elaborate what value (practical or otherwise) it is expected to provide.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QTv-gfX3S0", "reviewer": "Reviewer_qpNg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper focuses on the robustness problem in partially observable MDPs. They characterize the set of robust policies for any MDP in the form of operator-invariant sets and analyze how the structure of these sets depends on the MDP and noise kernel. Then they provide an inclusion relation that motivates how to search for robust policies more effectively. Finally, they cast robustness as a lexicographic objective to compute the robust policy while maintaining the optimality of the policy.", "summary_of_the_review": "Overall, the paper proposes a new method to solve the robustness problem. Given the concern about the weaknesses, I recommend marginally above the acceptance threshold. ", "strength_and_weaknesses": "Strengths:\nThis paper provides sufficient theoretical analysis to support their idea. \nThe problem solved in this paper is interesting and the idea seems novelty.\nWeaknesses:\nIn the experiments, they test the policy against a noiseless environment and two pre-defined kernels. Here I have one question. If the environment is disturbed adversarially, how will the computed robust strategy perform? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "FhPMMXJDAE", "reviewer": "Reviewer_LTJa", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides ideas for observational robustness when learning control policies via Reinforcement learning. The setting of the paper is an observationally distributed MDP (DOMDP) -- one in which the agent can access the true state during learning but stochastic noise is introduced at deployment. i.e. when acting according to the learnt policy. This work studies a notion of robustness by analyzing how policies are altered by a noise inducing stochastic kernel -- to construct robust policy sets -- policy classes which minimize the difference between the expected long run value-to-go under the unaltered and altered policies. Authors propose to leverage ideas from lexicographic optimization to trade-off between robustness and optimality of the learnt policies. ", "summary_of_the_review": "Overall, I am leaning towards accepting this paper. I think characterization of maximally robust policy sets is a useful first step but to me the potential of disadvantage based policy sets seems yet to be explored which is a bit of a let down. See for example Remark 2 which only applies to robust policies invariant to the kernel $T$ and that too under a fully parameterized setting. While constant policies is one way to minimize robustness regret, is it really a useful notion? Do these not correspond to smoothness constraints on the policy class. Similarly, imposing invariance to $T$ for all states, as done in defining the set $\\Pi_{T}$, seems too strong. The notion of using disadvantage function seems the most useful - robustness corresponds to minimizing the long run disadvantage of the perturbed policy from the most useful states. \n\nPlease clarify if I am unable to appreciate the usefulness of the contributions here but I feel like the most useful ideas from this setting are missing in the current presentation. ", "strength_and_weaknesses": "I found the paper quite interesting. The setting of DOMDP that the authors consider is quite well motivated from the point of view of practical applications - very often control policies are learnt in simulation so the true state is observable but the state observations are corrupted by noise at deployment time. I also found the idea of adding robustness objectives in lexicographic RL quite interesting - it seems to be a principled way of trading-off between optimality and robustness. The paper is also well organized - introducing the setting (DOMDP and robustness regret) in Section 2 -> characterization of maximally robust policy sets in Section 3 -> lexicographic objectives in Section 4. Some detailed comments and questions: \n\n1) On Inclusion Theorem: Given the definition of robustness regret and policy robustness along with the arguments in section 3.2, I am not sure about the gap between $\\Pi_D$ and $\\Pi_0$. I think if $\\Pi_D$ is defined as $[\\pi \\in \\Pi : \\rho^{\\pi}_{\\mu_0}(x) D^{\\pi}(x,T) = 0 \\, \\forall \\, x \\in X ]$, then it should characterize $\\Pi_0$ completely? Here $\\rho^{\\pi}$ refers to the steady state distribution under start state distribution $\\mu_0$ and policy $\\pi$.\n\n\n\n2) On Corollary 1: I am not sure I quite understand/am able to appreciate the usefulness of this. Also, the proof of statement (ii) seems to have some typos.\n\n3)  On Lemma 1 in Appendix (Convergence proof of 5): I seem to be missing something here. For a fully parameterized policy, $\\pi_{\\theta}(x, u) = \\theta_{x,u}$, we need to analyze a constrained optimization problem? Basically, one needs to restrict the parameter $\\theta$ to the probability simplex (I am thinking a projection step might be needed). The arguments from Theorem 3 might have to be modified.\n\nSome other minor comments:\n\n1) Please do correct typos in the presentation, for example indiuced -> induced etc. \n2) Do the learning rates in (3) change over time? That is, do you want to say $\\beta^1_t$ or $\\beta^1$? Both are written. On a related note, it might be a good idea to summarize convergence results and details of PB-LRL in the Appendix. A self contained presentation is often much more accessible. \n3) In (5), $K(\\theta) \\rightarrow K_{\\tilde{T}}(\\theta)$? Also, $p^{\\pi_{\\theta}}(x)$ seems to be formally undefined as well.\n4) Since a reference is made to policy gradient algorithms which converge to optimal policies to guarantee LRPG converges to an approximately optimal policy that maximizes robustness, may I suggest citing some recent work on different problem settings under which convergence of policy gradient methods to optimal policies actually holds? See for example:\n- \"On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift\"\n- \"Global Optimality Guarantees For Policy Gradient Methods\"\n\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject