Thresholded Lexicographic Ordered Multi-Objective Reinforcement Learning
Authors: Alperen Tercan
Vinayak Prabhu
Venue: Submitted to ICLR 2023 (2023)
Keywords: Reinforcement Learning
Lexicographic Ordered Multi-Objectives

Abstract: Lexicographic multi-objective problems, which impose  a  lexicographic importance order over the objectives, arise in many real-life scenarios. Existing Reinforcement Learning work  directly addressing lexicographic tasks has been scarce. The few proposed approaches were all noted to be heuristics without theoretical guarantees as the Bellman equation is not applicable to them. Additionally, the practical applicability of these prior approaches also  suffers from various issues such as not being able to reach the goal state.  While some of these issues have been known before, in this work we investigate further shortcomings, and propose fixes for improving practical performance in many cases. We also present a  policy optimization approach using our Lexicographic Projection Optimization (LPO) algorithm that has the potential to address these theoretical and practical concerns. Finally, we demonstrate our proposed algorithms on benchmark problems.

Under review as a conference paper at ICLR 2023
THRESHOLDED LEXICOGRAPHIC ORDERED MULTI- OBJECTIVE REINFORCEMENT LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Lexicographic multi-objective problems, which impose a lexicographic importance order over the objectives, arise in many real-life scenarios. Existing Reinforcement Learning work directly addressing lexicographic tasks has been scarce. The few proposed ap- proaches were all noted to be heuristics without theoretical guarantees as the Bellman equation is not applicable to them. Additionally, the practical applicability of these prior approaches also suffers from various issues such as not being able to reach the goal state. While some of these issues have been known before, in this work we investigate fur- ther shortcomings, and propose fixes for improving practical performance in many cases. We also present policy optimization approach using our Lexicographic Projection Opti- mization (LPO) algorithm that has the potential to address these theoretical and practical concerns. Finally, we demonstrate our proposed algorithms benchmark problems.
INTRODUCTION
The need for multi-objective reinforcement learning (MORL) arises in many real-life scenarios and the setting cannot be reduced to single-objective reinforcement learning tasks in general Vamplew et al. (2022). However, solving multiple objectives requires overcoming certain inherent difficulties. In order to compare candidate solutions, we need to incorporate given user preferences with respect to the different objectives. This can lead to Pareto optimal or non-inferior solutions forming a set of solutions where no solution is better than another in terms of all objectives. Various methods of specifying user preferences have been proposed and evaluated along three main fronts: (a) expres- sive power, (b) ease of writing, and (c) the availability of methods for solving problems with such preferences. For example, writing preference specifications that result in a partial order of solutions instead of total order makes the specification easier for the user but may not be enough describe unique preference. Three main motivating scenarios differing on when the user preference becomes available used have been studied in the literature. (1) User preference is known beforehand and incorporated into the problem a priori. (2) User preference used a posteriori, i.e., firstly a set of representative Pareto optimal solutions is generated, and the user preference is specified over it. (3) An interactive setting where the user preference is specified gradually during the search and the search is guided accordingly.
The most common specification method for the priori scenario linear scalarization which re- quires the designer to assign weights to the objectives and take a weighted sum of the objectives, thus making solutions comparable Feinberg Shwartz (1994). The main benefit of this technique is that it allows the use of many standard off the shelf algorithms as it preserves the additivity of the reward functions. However, expressing user preference with this technique requires significant domain knowledge and preliminary work in most scenarios [i & Czarnecki] (2019). While can be the preferred method when the objectives can be expressed in comparable quantities, e.g. when all objectives have a monetary value, this is not the case most of the time. Usually, the objectives are expressed in incomparable quantities like money, time, and carbon emissions. Additionally, com- posite utility combining the various objectives, and an approximation of that with linear scalarization limits us subset of the Pareto optimal set.
To address these drawbacks of linear scalarization, several other approaches have been proposed and studied. Nonlinear scalarization methods like Chebyshev Perny & Weng (2010) are more expressive and capture all of the solutions in the Pareto optimal set, however, they do not address the user-friendliness requirement. In this paper, we will focus on an alternative specification method that overcomes both limitations of linear scalarization, named Thresholded Lexicographic Ordering

---

Under review as a conference paper at ICLR 2023
(TLO) Gabor et al. (1998) Li & Czarnecki 2019). In lexicographic ordering, the user determines an importance order for the objectives, and the less important objectives are only considered two solutions respect the ordering of the more important objectives. The thresholding part of the technique allows a more generalized definition for being the same w.r.t. an objective. The user provides a threshold for each objective except the last, and the objective values are clipped at the corresponding thresholds. This allows the user to specify values beyond which they are indifferent
to the optimization of an objective. There is no threshold for the last objective as it is considered an unconstrained open-ended objective.
Despite the strengths of this specification method, the need for a specialized algorithm to use it in reinforcement learning (RL) has prevented it from being common technique. The Thresholded Lexicographic Q- (TLQ) algorithm was proposed as such an algorithm and has been studied and used in several papers Li & Czarnecki (2019) Hayes et al. (2020). While it has been noted that this algorithm does not enjoy the convergence guarantees of its origin algorithm (Q-Learning) we found that its practical use is limited to an extent that has not been discussed in the literature before. In this work, we investigate such issues of TLQ further. We also present Policy Gradient algorithm as general solution that has the potential to address many of the shortcomings of TLQ algorithms.
Our Contributions. Our main contributions in this work as follows: (1) We demonstrate the shortcomings of existing TLQ variants on common control scenario where the primary objective is reaching goal state and the other secondary objectives evaluate trajectories taken to the goal. We formulate a taxonomy of the problem space in order to give insights into TLQ's performance in different settings. (2) We propose a lexicographic projection algorithm which computes a lexi- cographically optimal direction that optimizes the current unsatisfied highest importance objective while preserving the values of more important objectives using projections onto hypercones of their gradients. Our algorithm allows adjusting how conservative the new direction w.r.t. preserved objectives and can be combined with first-order optimization algorithms like Gradient Descent or Adam. We also validate this algorithm on a simple optimization problem from the literature. (3) We explain how this algorithm can be applied to policy-gras sriic-traddent algorithms to solve Lexicographic Markov Decision Processes (LMDPs) and experimentally demonstrate the performance of REIN- FORCE adaptation on the cases that were problematic for TLQQ
Additionally. in Appendices C and D we give further insights into TLQ by giving more details about how different TLQ variants fail in problematic scenarios. Then, we present both some of our failed efforts and the promising directions we identified in order to guide future research.
2 RELATED WORK
Gábor et al. (998) was one of the first papers that investigate the use of RL in multi-objective tasks with preference ordering. It introduces TLQ as RL algorithm to solve such problems. /Vamplew et al. (201T) showed that TLQ significantly outperforms Linear Scalarization (LS) when the Pareto front is globally concave or when most of the solutions lie on the concave parts. However, LS performs better when the rewards are not restricted to terminal states, because TLQ cannot account for the already received rewards. Later, Roijers et al. (013)) generalized this analysis by comparing more approaches using a unifying framework. To our knowledge, Vamplew et al. (201 is the only previous work that explicitly discussed shortcomings of TLQ. However, we found that TLQ has other significant issues that occur even outside of the problematic cases they analyze.
Wray et al. (2015) introduced Lexicographic MDP (LMDP) and the Lexicographic Value Iteration (LVT) algorithm. LMDPs define the thresholds as slack variables which determine how worse than the optimal value is still sufficient. While Wray et al.] (2015) proved the convergence to desired policy if slacks are chosen appropriately, such slacks
generally too tight to allow defining user preferences. This is also observed in |Pineda et al. (015) which claimed that while ignoring these slack bounds negates the theoretical guarantees, the resulting algorithm still can be useful in practice.
Li & Czarnecki 2019) investigated the use of Deep TLQ for urban driving. It showed that the
TLQ version proposed in Gābor et al. (1998) introduces additional bias which is especially prob- lematic in function approximation settings like deep learning. Also, it depends on learning the true Q function, which can not be guaranteed. To overcome these drawbacks, it used slacks instead of the static thresholds and proposed different update function. [Hayes al. (2020) used TLQ in multi-objective multi-agent setting and proposed a dynamic thresholding heuristic to deal with the explosion of the number of thresholds to be set.
2

---

Under review as a conference paper at ICLR 2023
However, discovered that these works on using Q-learning variant with thresholded ordering perform very poorly in most cases due to non-Markovianity of the value function they try to learn. It is possible to bypass this issue by using policy gradient approaches as they do not require learn- ing an optimal value function. In order to handle conficting gradients, some modifications to the gradient descent algorithm are needed. Recent work on modified gradient descent algorithms came mostly from Multi Task Leamnngg literature, which could be considered a multiobjective optimiza- tion problem Désidéri (2009) SSnner & Koltun (2018) Lin et al. (2019) Mahapatra & Rajan (2020) Parisi al. (2014) Liu et al. (202)). While these papers use similar ideas with our work, their setting is different than ours as they do not have any explicit importance order; hence, not applicable to our in gradient- baaed algorithms. considers a set of constraints with an unconstrained objective. Then, the gradient of the uncon- strained objective is projected onto the positive half-space of the active (violated) constraints and adds a correction step to improve the active constraints. When no valid projection found, the most violated constraints are ignored until a valid projection exists. This is one of the main differences with our setting: As we have an explicit importance-order of the objectives, it is not acceptable to ignore constraint without considering the importance order. Also, we project the gradients onto hypercones instead of hyperplanes, which a hypercone with x/2 vertex angle. Thus, our algorithm allows varying degrees of conservative projections to prevent decline in the constraints.
Liu
setting. [Cchibe & Doya (0008) has the most similar setting
While there are many other recent works on Constrained Markov Decision Process (CMDPs) (Wachi & Sui 2020; Garefa et al., 2017] Junges et al. 2016). their approaches are not applicable as an importance order over the constraints not allowed. Recently, using RL with lexicographic ordering began to attract attention from other communities as well. For example, |Hahn et al. (2021) uses formal methods to construct single objective MDPs when all of the objectives are w-regular.
Finally, [Skalse et al. (2022) was published in August 2022 and it proposes both value- and policy-based approaches. Their value-based approach is based on slacks like Li & Czarnecki (2019) and they require using very small slack values. This protects their approach from the issues with having relaxations by limiting their setting to strict lexicographic order. For policy-based methods, they use Lagrangian relaxation and their setting is again a strict lexicographic ordering, i.e. it does not allow treating values above a threshold equal.
3 BACKGROUND
Multiobjective Markov Decision Process (MOMDP). A MOMDP is a tuple (S,A,T,R, R, where
S is the finite set of states with initial state 8init E and set of terminal states SF,
A is finite set of actions,
S + [0, 1] is the state transition function given by a(). = P(s'|s, as) the probability of transitioning to state s' given current state and action a.
P: S x
R RR [R...... Rx] I a vector that specifies the reward of transitioning from state s to s' upon taking action a under K different reward functions R₃ S x A xxx3 S + lk for E {1,.... K}. 7 R is discount factor.
In such a MOMDP, a finite trajectory Ç E (S x A)" x 5 is a sequence Ç = Sydg$11 01 QT--18 where s; E 8, a, E A and indices denote the time steps. The evolution of an MDP is governed by repeated agent-environment interactions, where each step, an agent first picks actions a state 8 according to some probabilistic distribution, and for each of these actions a the environment generates next states according to P(s'|s Is, a). Each reward function R; corresponds to an objective og the discounted rewards sum that the agent tries to maximize. Control over MOMDP requires finding an optimal policy function ;² S A - [0. 1 which assigns probability P.. (als) to actions E A. In this paper, we use the episodic case of MDP where the agent-environment interaction consists of sequences that start in Sinit and terminates when state in Sr is visited. The length of the episode is finite but not a fixed number. In MDP literature, this is known as "indefinite-horizon be ensured by restricting ourselves suitable policies which have
MDP. The episodic case non-zero probability for all action in all states.
We define the quality of a policy π with respect to an objective o, E {L...., K} by the value function V S - IR given by V (s) = E. [ET 7 RR (s1, at S(41)180 = s). Intuitively, of (s) is the expected return from following policy starting from state s w.r.t. objective o, Overall, the quality of a policy æ is given by the vector valued function V S - IRKK which is defined as
3

---

Under review as a conference paper at ICLR 2023
(T(()~ (V) V As V is vector-valued, without a preference for comparing V values across different i, we only have partial order over the range of V, leading to Pareto fromt of equally good quality vectors. Further preference specification is needed to order the points on the Pareto front. A Lexicographic MDP (LMDP) is a class of MOMDP which provides such an ordering. It adds another component to MOMDP definition:
E 1K is a tuple of threshold values where т; indicates the minimum acceptable value for objective i. The last objective does not require a threshold: hence, there are only K values. Then, T can be used compare value vectors u, v E IK by defining the thresholded lexicographic comparison >> as u > v iff there cxists i S K such that:
(TI,..,,TTK
Vj < we have uj 2 min(v;, Ty); and if < K then min u; Ti) > (V). * otherwise if i = K then u; > Vi.
Intuitively. we compare u and starting from the most important objective (j 1); the less important objectives are considered only if the order of higher priority objectives respected. The relation 2n is defined as >" OR =.
Value-function Algorithms for Optimal Policies. An optimal policy '" is policy that is better than or equal to any other policy क E II, i.e., if V* dn V*(s) Vs E S for all other policies Gāboo et al., (998). There are two approaches to finding an optimal policy in RL: Value- falutifuntiion algorithms and Policy Gradient algorithms. Value function based methods estimate the optimal action-value function Q" and construct x" using it. The action- value function under x, Q" S x
A + RKK is defined as: Q" (s(ss) - Ex [2t 7 7'R(s; at St+1)|50
8, ag a] The optimal action-value function, Q", is defined as: Q* (ss,a) a) max Q" a). Then, π can be obtained as: ा" (s,a) a) 1 if a arg max (' a'), and 0 otherwise. In single objective MDPs, the Bellman Optimality Equation as seen in Eq. [ is used to leam Q' as it gives an update rule that converges to Q* when applied iteratively.
(' = E [R((s, s'rup
max (*(s'a e'EA
1992) is a very popular algorithm that takes this approach. TLQ tries to extend Q-learnin for LMPDs; however, Bellman Optimality Equation does not hold in LMDPs. Hence, this approach lacks the theoretical guarantees enjoyed by Q-learning.
Q-Jearning Watkins & Dayan
Policy Gradient Algorithms for n² Policy gradient algorithms in RL try to learn the policy directly instead of inferring from the value functions. These methods estimate the gradient of the optimality measure w.r.t. policy and update the candidate policy using this potentially imperfect information. We denote the policy parameterized by a vector of variables, as TT.. The performance of the policy Te. denoted (O), can be defined as the the expected return from following Te starting from 8inits
ie. ((0) - V** (sinit). Once the gradient of the optimality measure w.r.t. the parameters of the policy function is estimated, we can use first-order optimization techniques like Gradient Ascent to maximize the optimality measure. While all based on the similar theoretical results, myriad of policy gradient algorithms have been proposed in the literature [Sutton et al.) (1999) Konda &
Tsitsiklis 1999) Schulman et al. (2017) Lillicrap et al. 2015) Haarnoja et al. (2018).
4 TLQ: VALUE FUNCTION BASED APPROACHES FOR TLO
Previous efforts find solutions to the LMDPss have been focused on value-function methods. Apart from Wray et al. (2015), which takes a dynamic programming approach, these have been variants of Thresholded Lexicographic Q-Learning (TLQ),, an LMDP adaptation of Q-learning Gábor et al. 1998) Li & Czarnecki (2019). While these methods have been used and investigated in numerous papers, the extent of their weaknesses has not been discussed explicitly.
In order to adapt Q-learning to work with LMDPs, one cannot simply use the update rule Q- learning for each objective and learn the optimal value function of each objective completely inde- pendent of the others. Such an approach would result in the actions being suboptimal for some of the objectives. Based on this observation, two variants of TLQ Gábor et al. (1998] Li & Czarnecki (2019) have been proposed, which differ in how they take the other objectives into account. We analyze these variants by dividing their approaches into two components: update rules; and (2) acceptable policies for action selection. However, it should be noted that these
(1) value functions and
4

---

Under review as a conference paper at ICLR 2023
components are inherently intertwined due to the nature of the problem the value functions and acceptable policies are defined recursively where each of them uses the other's last level of recur- sion. Due to these inherent circular referencing, the components will not be completely independent and some combinations of introduced techniques may not work.
Value Functions and Update Rules. The starting point of learning the action-value function for both variants is Q* (Qi...... Qk) where each Q S x A - E is defined as in Section 3 only with the change that the maximization is not done over the set of all policies IT but over a subset
11;-1 S II which will be described below. Gábor et al. 1998) proposes learning Q : :S x A + R
where each component of Q' denoted by Q is defined as: (5, a) _ min( Q7 a)) other
words, it is the rectified version of Q It is proposed to be learned by updating Q1 (s, a) with the following value iteration which is adapted from Eq.
min
TEi Σ (R,,,,, +Y max ( (s')) -Ell.-1
(2)
Notice that similar to the definition of Q; the main change during the adaptation is limiting the domain of max operator to II from II. On the other hand, [i & Czarnecki] (2019) proposes that
we estimate Q" instead and use it when the actions are being picked. This Q" uses the same update rule as Eq. I with only change being maximization over II,-1-
Acceptable Policies II, and Action Selection. The second important part of TLQ is the definition of " Acceptable Policies", NT; which is likely to be different for each objective. The policies in II; are ones that satisfy the requirements of the first objectives. Values of the acceptable policies in given state are the acceptable actions in that state. Hence, these sets will be used the domain of both max operator the update rules and arg max operator in ActionSelee ion function. The pseudocode of this function can be seen in Algorithm[] Note that the structure of this function the same for both variants of TLQ and different instantiations of the function differ in how the Acceptab baabblle leActts subroutine is implemented. Acceptabl eActs takes the current state the Q-function to be used, and the actions acceptable to the objectives up to the last one and outputs the actions acceptable to the objectives up to and including the current one. Below, we will describe how I1, has been defined in the literature, see Appendix B for the formal definitions.
Absolute Thresholding: Gábor et al. (1998) pro- poses this approach where the actions with values higher than a real number are considered acceptable. Hence, II, is the subset of II,-1 for which Q-values are higher than some T.
Algorithm ActionSelection
Function Act i oonnelectt on (8, Q,e(A);
r <~ 1) i < e then
a is picked randomly from A
Absolute Slacking: This is the approach taken by Li & Czarnecki (2019) where a slack from the opti- mal value in that state is determined and each action within that slack is considered acceptable.
else
Ao < A for K, do
if AA-1l > 1 and < then Acceprablecct(ss..AGk Ao-1)
A.
4.1 SHORTCOMINGS OF PRIOR TLQ APPROACHES
else
The shortcomings of TLQ depend on the type of task. We introduce taxonomy to facilitate the dis- cussion.
a + arg max,' Q((s,a')
break
end return
ConstrainedUUnccostrrinee Objective: Constrained objectives bounded in quality by their thresh- old values above which all values are considered the same. Unconstrained objectives do not have a such threshold value. In an LMDP setting, all objec- tives but the last one are constrained objectives.
Terminating Objective: An objective that either implicitly or explicitly pushes the agent to go to terminal state of the MDP. More formally, this means discounted cumulative reward for an episode that does not terminate within the horizon is lower than an episode that terminates.
Reachability Objective: A reachability objective is represented by non-zero reward in the terminal states of the MDP and zero rewards elsewhere. We will call an objective that has non-zero rewards in at least one men-telminal state a reachabcyyyy objective.
This taxonomy also helps seeing the problematic cases and potential solutions. To summarize the empirical demonstrations about the applicability of T for different parts of the problem space:
5

---

Under review as a conference paper at ICLR 2023
(I) TLQ successful case studies: Vamplew et al. 2011) shows experiment where the constrained objective is reachability, unconstrained objective is terminating, and TLQ works. Li & Czarnecki (219) shows this for case study where the constrained objective is a non-terminating reachability constraint. Note that these are just demonstrations of empirical performance for some case studies that fall into these categories and the papers do not make claims about the general instances.
(II) TLQ does not work: Vamplew et al. (201T) shows that TLQ does not work when constrained ob- jective is non -onhhbachabilitt. In this work, we show that TLQ also does not work when the constrained objective is terminating reachability objective but the unconstrained one is non-terminating.
Benchmark. We describe some scenarios that are common in control tasks yet TLQ fails to solve. To illustrate different issues caused by TLQ, we need an adaptable multiobjective task. Also, limit- ing ourselves to finite state and action spaces where the tabular version of TLQ can be used simplifies the analysis. Our MAZE environment satisfies all of our requirements. Figure [ shows an example.
In all MAZE instantiations, each episode starts in S and Gs the ter- minal state. There are also two types of bad tiles. The tiles marked with HHs are high penalty whereas the ones with his show the low penalty ones. In this work, we will use -5 as high penalty and -4 as low penalty. But we consider the penalty amounts pa- rameters in the design of a maze; so, they could change. There are two high-level objectives: Reach G and avoid bad tiles. Ordering of these objectives and exact definition of them results in different tasks. We use these different tasks to cover different parts of the problem space described in the taxonomy. The action space con- sists of four actions: Up. Down, Left, Right. These actions move the agent in the maze and any action which would cause the agent to leave the grid will leave its position unchanged.
IG
2
HH HH
1
|S_
0
Figure 1: A simple maze that can be used to demonstrate how TLQ fails to reach the goal state.
Problems with Reachability Constraint. A common scenario in control tasks is having primary objective to reach a goal state and a secondary objective that evaluates the path taken to there. Formally, this is a scenario where the primary objective is reachability objective. However, TLQ either needs to ignore the secondary objective or fails to satisfy the primary objective in such cases. All of the thresholding methods above fail to guarantee to reach the goal in this setting when used threshold/slack values are uniform throughout state space. The maze in Figure [ can be used to observe this phenomenon. Assume that our primary objective is to reach G and we encode this with a reward function that 0 everywhere but G where it is R. And our secondary objective is to avoid the bad tiles. A Pareto optimal policy in this maze could be indicated by the state trajectory (1, + () (2, 1) (2, 2) (1, 2). However, this is unattainable by TLQ.
Since the reward is given only in the goal state, Qi can be equal to T1 only for the state-action pairs that lead to the goal state. All others will be discounted from these; hence, all are less than T1. This means the agent will always ignore the secondary when using absolute thresholding of Gábor et al. (1998). If no discounting was used, all actions would have the value Tı, hence the agent would not need to reach the goal state. We believe the reason why Vamplee et al. (2011) has not observed this issue in their experiments with undiscounted (7 = -) Deep Sea Treasure (DST) is due to their objectives. The secondary objective of DST, minimizing the time steps before terminal state, is terminating objective which pushes the agent to actually reach a goal state.
In Appendix C.1 we show how Absolute Slacking also leads to contradicting requirements when the trajectory described above is aimed. Moreover, in Appendix [22] we present another case study which shows all TLQ variants fail to find the optimal policies in some very standard scenarios where the primary objective is a reachability objective. More generally, it highlights the shortcomings of having a single threshold/slack value for all states which can manifest itself in other settings too.
5 POLICY GRADIENT APPROACH FOR TLO
In this section, we introduce our policy gradient approach that utilizes consecutive gradient projec- tions to solve LMDPs. Policy gradient methods treat the performance of a policy, ((H), as a function of policy parameters that needs to be maximized and employ standard gradient ascent optimization algorithms Ruder (216)). Following this modularity, we start with proposing general optimization algorithm, the Lexicographic Projection Algorithm (LPA), for multiobjective optimization (MOO)

---

Under review as a conference paper at ICLR 2023
problems with thresholded lexicographic objectives. Then, we will show how single objective Policy Gradient algorithms can be adapted to this optimization algorithm.
As gradients w.r.t. different objectives can be conflicting for MOO, various ways to combine them have been proposed. [Uchibe & Doya (2008) proposes projecting the gradients of the less important objectives onto the positive halfspaces of the more important gradients. Such projection vector has the highest directional derivative w.r.t. less important objective among the directions with non- negative derivative w.r.t. the important objectives. This is assumed to protect the current level for the important objective while trying to improve the less important. However, non-negative derivative actually does not guarantee to protect the current level as infinitely small step sizes are not used in practice. For example, if function is strictly concave, the change in zero-derivative direction will be always negative for any step size greater than 0. Therefore, we propose projecting onto hypercones which allows more control over how safe the projection is. A hypercone is the set of vectors that make at most & - A angle with the axis vector; a positive halfspace is a special hypercone where A = O. Increasing A brings the projection closer to the axis vector. A hypercone Ca with axis E E= and angle? A is defined as C.
a² x
E
R
[
OV
COS
A)
|a
x
2
We can derive the equation for projection of g on Co by firstly showing that g. a, and the projection g" are planar using Kuhn-Tucker (KKT) conditions. Then, we can derive the formula by using two-dimensional geometry (the details are in the appendix); giving us g"
cos
sin (A+ + Φ) +
||g| ||
(sin o tan A - --cos ())
44)
sin Φ
where ob is the angle between a and projectCone(g, a, A) which returns gd according this equation.
Moving forward, we assume a function
Lexicographic Projection Algorithm (LPA). A Thresholded Lexicographic MOO (TLMOO) prob-
lem with K objectives and parameters can be formulated as maximizing a function F : A - R where E IR,", and the ordering between two function values F(0 is according to > as defined as in Section 3 Notice that when we have multiple objectives, the gradients will form K-tuple, G = (VF1, F2 FFk), where VF, the gradient of 7th component of F.
Since TLMOO problems impose a strict importance order on the objectives and it is not known how many objectives can be satisfied simultaneously beforehand, a natural approach is to optimize the objectives one-by-one until they reach the threshold values. However, once an objective is satisfied, optimizing the next objective could have detrimental effect the satisfied objective. We can use hypercone projection to avoid this. More formally, when optimizing F,, we can project V.;; onto the intersection of {Cêr, Jiss where A is hyperparameter representing how risk-avers is, and use the projection the new direction. If such an intersection does not exist, it means that it is not possible to improve F; without taking a greater risk and we can terminate the algorithm.
projection
Improving this approach with heuristic that prevents overly conservative solutions leads to better performance in certain cases. Conservative updates usually lead to further increases on the already satisfied objectives instead of keeping them at the same level. This means most of the time, we have enough buffer between the current value of the satisfied objectives and their thresholds to sacrifice some of it for further gains in the currently optimized objective. Then, we can define a set of "active constraints" which is subset of all satisfied objectives that will not accept any sacrifice and only consider these when projecting the gradient. The "active constraints" can be defined loosely, potentially allowing hyperparameter that determines the minimum buffer zone needed sacrifice from an objective.
function in Algorithm 2 (our LPA algorithm) incorporates these ideas. This function takes the tuple of all gradients M, the tuple of current function values F(0), threshold values т, the conservativeness hyperparameter A, a boolean AC' that determines whether "active constraints" heuristic will be used or not, and a buffer value b to be used alongside active constraints heuristic as inputs. Then, it outputs the direction that should be followed at this step, which can replace the gradient in gradient ascent algorithm. For the optimization experiments, using the vanilla gradient ascent algorithm. A Algorithm finds the first objective that has not passed its threshold and iteratively projects its gradient onto hypercones of all previous objectives. If such
The LindDrrectio
will be
7

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Lexicographic Constrained Ascent Direction
Function FindD iindiireetion (A1, F(0), T, A, AC,6):
Initialize action-value function Q with random weights
for = 1, do = K -1 or Fo(O) < To then
Initialize direction u with initial state M.
j= 1, do
if not ((AC and (0) > 7; + bj or ((u, M,) < - (A)
+ projectConee My. A)
end
for j 1,0 do if not ((j * K 1 and AC and F2 Tj + b) or 4(u, < -
return None
end return 2
end
projection exists, it returns the projection the "Lexicographic Constrained Ascent" direction. Otherwise, returns null. In our experiments, we will set = O. In general, can be set to any non-negative value and higher values of 6 would result in more conservative algorithm which does not sacrifice from an objective unless it is well above the threshold.
Experiment, As a benchmark for the Lexicographic Projection Algorithm, we used Fa 3) 4x2 + -y² + zy and F2 y) (x 1)2 (y 0.5)² which are taken from Zerbinati et al. 201T). We modified F3 slightly for better visualization and multiplied both functions with -1 to convert this to maximization problem. We set the threshold for Fi to -0.5. The behavior of our cone algorithm without using active constraints heuristic on this problem with T (-0.5) and can be seen in Figure Further results with AC heuristic can be found Appendix F44
A
30
Function by
Algorithm
Using Lexioggraphic Projection Algorithm in RL. We show how LPA can be combined with policy gradient algorithms. We use REIN- FORCHSutton et al. (1999) as the base policy gradient algorithm because its simplicity mini- mizes conceptual overhead.
0.0
0.450
0.5
-1.0
-1.5
Runction
Threshold Passing Point
We can adapt REINFORCE work in LMDPs by repeating the gradient computation for each objective independently and computing new direction using F unndDrrectto
2.5
-3.0
Primary Objective
-3.5
Secondary Objective Threshold
function. Then, this direction be passed to the optimizer. Algorithm 5 in the appendix shows the pseudocode for this algorithm.
-4.0
10
20
30
50
60
Iteration
Figure 2: The changes in the function values. No- tice that Fz, in orange, is completely ignored un- til the threshold for F1 is reached. Then, the al- gorithm optimizes F2 while respecting the passed threshold of Fi.
Note that our algorithm is compatible with most policy gradient algorithms. Uchibe & Doya (2008) shows how similar idea is applied to actor-critic family of policy gradient algorithms which reduces the variance in the gradient esti- mation by using a critic network. We believe that more stable policy gradient algorithms like actor-critic methods could further improve the performance of lexicographic projection approach as our algorithm might be sensitive to noise in gradient estimation.
Experiments. We evaluate the performance the Lexicographic REINFORCE algorithm on two Maze problems. In both experiments, we use two layer neural network (LeCun et al. 2015) for policy function. Details of the policy function can be found in Appendix G.3
Reachability Experiment. As the first experiment, we consider the case where the primary objec- tive is reachability objective and the secondary objective is non-terminating, which was the setting that we found that TLQ fails to reach the goal state in Section 4.1 Our experiments show that Lexi- cographic REINFORCE can successfully solve this problem. Details of this experiment and results can be found in Appendix G.3.2
8

---

Under review as a conference paper at ICLR 2023
Non-reachability Experiment. The primary objective is non- reachability objective, i.e. it takes non-zero values in some non- terminal states. For this, we flip our objectives from the previous setting and define our primary objective as minimizing the cost in- curred from the bad tiles. HHs give -5 reward and h/s give -4 reward. A +1 reward is given in the terminal state to extend the pri- mary objective to have rewards in both terminal and non non-terminal states. The secondary objective the terminal state. We formalize this by defining our secondary re- ward funetion
G_1
4
hh
hh
3
2
HH
HH
HHI
18_
0
0
to minimize the time taken to
Figure 3: The Maze for the non-reachability experiment.
O in terminal state and - everywhere else. We use the Maze in Figure 3 for this experiment. Note that this is the setting that Vamplew et al. (201T) has found that TLQ fails. However, our experiments show that Lexicographic REINFORCE can solve this setting too.
We found that out of the 10 seeds, 7 find policies that have 90% success over 100 episodes. The change in satisfaction fre- quencies of individual objec- tives for successful seed can be seen in Figure 4 Notice that the primary objective initially starts very low and quickly increases while the secondary objective does the opposite. This hap- pens while the algorithm mostly optimizes the primary objective. Once the primary objective is learned, the algorithm starts im- proving the secondary objective.
Satisfaction Frequency by Objective
1.0
0.8-
0.4
Both
Objective
Dejective
2500
5000
7500
10000
12500
15000
17500
20000
Episodes
These experiments illustrate the usefulness of projection based policy gradient algorithm for different tasks. We believe that these results can be generalized to more complex tasks when our algorithm combined with more stable and sophisticated policy gradient algorithms.
Figure 4: Satisfaction frequency for single successful seed for the non-reachability experiment.
6 CONCLUSION
In this work, we considered the problem of solving LMDPs using model-free RL. While previous efforts on this problem have been focused on value-function based approaches, the applicability of these approaches over different problem settings and investigation of the extent of their shortcomings have been limited. Our first contribution was providing further insights into the inherent difficulties of developing value function based solutions to LMDPs. Towards this end, we both illustrated failure scenarios for the existing methods, and also presented (in Appendices Cand (D) potential new value-function based approaches. These approaches include both our failed attempts and promising directions, we believe both will be helpful for future research.
Our second focus in this work was developing and presenting a policy-gradient based approach for LMDPs. Policy gradient algorithms have not been studied in MDPs with thresholded lexicographic objectives before even though they are more suitable for this setting as they bypass many inherent issues with value functions, such as non-convergence due to non-greedy policies w.r.t. value func- tions, and the need for different threshold values across the state space. For this, we developed general thresholded lexicographic multi-objective optimization procedure based on gradient hyper- cone projections. Then, we showed how policy gradient algorithms can be adapted to work with LMDPs using our procedure, and demonstrated the performance of our REINFORCE adaptation. While our results are promising for the REINFORCE adaptation, future research could be further empirical studies with more stable policy-gradien algorithm adaptations, and over more complex tasks.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
In this work, we list all the hyperparameters that we used in the experiments in Section and Appendix G.3] We also share the source code for Section 5 in the supplementary material and we will make the rest of the source code public for the camera-ready version. Moreover, we provide the derivations of the projection formula for policy gradient approach, in Appendix B
10

---

Under review as a conference paper at ICLR 2023
REFERENCES
Abstract Vectors, chapter 5, pp. 245-334. John Wiley & Sons, Ltd, 2021. ISBN 97911494 doi:
URL https://
Abien Fred Agarap. Deep learning using rectified
linear
units
(relu).
arXiv preprint
arXiv:1803.08335, 2018.
Edwin KP Chong and Stanislaw H Zak. An introduction to optimization. John Wiley & Sons, 2004.
Jean-Antoine Désidéri. Multiple-Gradien Gradient Descent Algorithm (MGDA). Research Report RR-6953, INRIA, June 2009. URL httth::////halliiiiii http:///h...iiattttmmaaaa0133111
Eugene A Feinberg and Adam Shwartz. Markov decision models with weighted discounted criteria. Mathemattics of Operations Research, 19(1):152-168, 1994.
Zoltán Gábor, Zsolt Kalmár, and Csaba Szepesvári. Multi-criteria reinforcement learning. In ICML, volume 98, pp. 197-205 Citeseer, 1998.
Javier Gareía, Roberto Iglesias, Miguel A Rodríguez, and Carlos V Regueiro. Incremental rein- forcement learning for multi-objective robotic tasks. Knowledge and Information Systems, 51()): 911-940, 2017.
Peter Geibel. Reinforcement learning for mdps with constraints, In European Conference on Ma- chine Learning, pp. 646-653. Springer, 2006.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor, 2018. URL https://arxiv,
org//bb//801101120
Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, and Dominik Wojtczak. Model-free reinforcement learning for lexicographic omega-regular objectives. In Marieke Huisman, Corina Päsäreanu, and Naijun Zhan (eds.), Formal Methods, pp. 142-159, Cham, 2021. Springer International Publishing. ISBN 978- 1118--000--0870-6.
Sarah L Harris and David Harris. Digital design and computer architecture. Morgan Kaufmann, 2015.
Conor F Hayes, Enda Howley, and Patrick Mannion. Dynamic thresholded lexicographic ordering. In Adaptive and Learning Agents Workshop (AAMAS 2020), 2020.
Sebastian Junges, Nils Jansen, Christian Dehnert, Ufuk Topcu, and Joost-Pieter Katoen. Safety- constrained reinforcement learning for mdps. In International conference on tools and algorithms for the construction and analysis of systems, pp. 130-146. Springer, 2016.
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553)433-444, 2015.
Changjian Li and Krzysztof Czarnecki. Urban driving with multi-objective deep reinforcement learning. In Proceedings of the 18th International Conference on Autonomous Agents and Multi- Agent Systems, pp. 359-367, 2019.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arxiv: 029.91029991.... 2015.
Xi Lin, Hui-Ling Ling Zhen, Zhenhua Li, Qing-Fu Zhang, and Sam Kwong. Pareto multi-task learning. Advances in neural information processing systems, 32, 2019.
11

---

Under review as a conference paper at ICLR 2023
Bo Liu, Xingchao Liu, Xiaojie Jin, Peter Stone, and Qiang Liu. Conflict-averse gradient de- scent for multi-task learning. M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp- 18878-18890. Curran Associates, Inc., 2021. URL https:/pnoeeddngssuuusss.ccoooop
Debabrata Mahapatra and Vaibhav Rajan. Multi-task learning with user preferences: Gradi- ent descent with controlled ascent in pareto optimization. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 6597-6607, PMLR, 13-18 Jul 2020. URL
https:/prooceedngg..lrrpp press/v htt.://s.......s.111//mmmmrrrruu 19/maaaaattr22aahum
Simone Parisi, Matteo Pirotta, Nicola Smacchia, Luca Bascetta, and Marcello Restelli. Policy gra- dient approaches for multi-objective sequential decision making. 2014 International Joint Conference on Neural Networks (IJCNN.. pp. 2323 2330.. IEEE, 2014.
Patrice Perny and Paul Weng. On finding compromise solutions in multiobjective markov decision processes. In ECAI 2010, pp. 969-970. IOS Press, 2010.
Luis Enrique Pineda, Kyle Hollins Wray, and Shlomo Zilberstein. Revisiting multi-objective mdps with relaxed lexicographic preferences. In 2015 AAAI Fall Symposium Series, 2015.
Diederik M Roijers, Peter Vamplew, Shimon Whiteson, and Richard Dazeley. A survey of multi- objective sequential decision-making. Journal of Artificial Intelligence Research, 48:67-113, 2013.
Sebastian Ruder. An overview of gradient descent optimization algorithms. arXiv preprint 14070777, 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint vrXivv1707.06::: 2017.
Ozan Sener and Vladlen Koltun. Multi-task learning as multi-objective optimization. Advances in neural information processing systems, 31, 2018.
Satinder Singh, Tommi Jaakkola, Michael L Littman, and Csaba Szepesvári. Convergence results for single-step on-policy reinforcement-leamingg algorithms. Machine learning, 38(3):287-308, 2000.
Joar Skalse, Lewis Hammond, Charlie Griffin, and Alessandro Abate. Lexicographic multi objeito the Thirty- Carry--Fisttan International Joins Conference on Arlificial Intelligence, IJCAI-22, pp. 3430-3436. International Joint Conferences on Artificial Intelligence Organization, 7 2022. doi: 10.24963/iccai.22227777 URL https:///oi. Main Track.
reinforcement learning. In Lud De Raedt (ed.), Proceedings the
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15()):122-1198. 2014.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In S. Solla, T. Leen, and K. Müller (eds.), Advances in Neural Information Processing Systems, volume 12. MIT Press, 1999. URL
Eiji Uchibe and Kenji Doya. Finding intrinsic rewards by embodied evolution and constrained reinforcement learning. Neural Networks, 21100):444-1155, 2008. ISSN 0893-6080. doi: https: 101 newnet.0008..09 $08936080080021004 ICONIP 2007.
#dbbi.rr/10..000/..neemmmm
URL http::/wwwww..ccccccccccccc////a
Peter Vamplew, Richard Dazeley, Adam Berry, Rustam Issabekov, and Evan Dekker. Empirical evaluation methods for multiobjective reinforcement learning algorithms. Machine learning, 84 (1):51-80, 2011.
12

---

Under review as a conference paper at ICLR 2023
Peter Vamplew, Benjamin Smith, Johan Källström, Gabriel Ramos, Roxana Rádulescu. Diederik M Roijers, Conor F Hayes, Fredrik Heintz, Patrick Mannion, Pieter JK Libin, al. Scalar reward is not enough: A response to silver, singh, precup and sutton (2021). Autonomous Agents and Mulli-Agent Systems, 36(2):1-19, 2022.
Akifumi Wachi and Yanan Sui. Safe reinforcement learning in constrained markov decision pro- cesses. In International Conference on Machine Learning, pp. 9797-9806. PMLR, 2020.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3):279-292 1992.
Kyle Hollins Wray, Shlomo Zilberstein, and Abdel-Illah Mouaddib. Multi-objective mdps with conditional lexicographie reward preferences. In Twenty-ninth AAAI conference on artificial telligence, 2015.
Runzhe Yang, Xingyuan Sun, and Karthik Narasimhan. A generalized algorithm for multi-objectivy reinforcement learning and policy adaptation. Advances Neural Information Processing Sys- tems, 32, 2019.
Adrien Zerbinati, Jean-Antoine Desideri, and Régis Duvigneau. Comparison between MGDA and PAES for Multi-Objectinn Optimization. Research Report RR-7667, INRIA, June 2011. URL https://hal.i inria. wwr.aaafriiria-0000555520
13

---

Under review as a conference paper at ICLR 2023
A TECHNICAL APPENDIX ORGANIZATION
In this section, we will give an overview of the Appendix.
Technical Appendix for Section In Appendix B, we share further mathematical details for the different acceptable policy definitions. In Appendix C we firstly describe how Absolute Slacking and Relative Slacking suffer from the failure to reach the goal. Then, we present different issue that was not covered in the main paper: failure to sacrifice at both ends of the episode. After the discussion of issues, we propose different approaches that can address these issues in Appendix D
Technical Appendix for Section 5 We start by describing the derivation of the projection formula used in the paper in Appendix Then, in Appendix [ we show why cone projection is useful and share the rest of the experiments for the LPA algorithm on the simple optimization benchmark used in the main paper too. Finally, we share further results from the experiments with the adapted REINFORCE algorithm in Appendix G
Within this technical appendix, we would like to highlight the following sections.
Appendix C continues our discussion in Section
4. and demonstrates how existing TLQ variants fail in the given scenarios. Appendix D.2 presents TLQ fix that addresses some shortcomings of
TLQ for two objectives. Appendix D.3.3 formulates how the well nell-known state augmentation idea can be used solve LMDPs and proposes this new research direction.
For the policy gradient part of our work, Appendix Ilstrratss why hypercone projection needed instead of halfspace projections for lexicographic optimization. Then, Appendix G.2 shows the
Flllttrrttts
pseudocode of our REINFORCE adaptation. Finally, Appendices F.4 and G.3 present rest of the experiments that could not fit in Section
B FURTHER DETAILS ON ACCEPTABLE POLICIES
In this section, we will give the mathematical definitions of different thresholding methods. Also, will describe Relative Slacking, an alternative thresholding method that does not exist in the literature. We include it for the sake of completeness.
1. Absolute Thresholding: This is the approach proposed by Gábor al. (1998) where the actions with values higher than a real number are considered acceptable. Formally,
max II; A [ E II:11 (s, (s(s)) ())
ass
(5)
2. Absolute Slacking: This the approach taken by Li & Czarnecki (019 and Skalse et al. (2022) where slack from the optimal value in that state is determined and each action within that slack is considered acceptable.
I1, (T, E I1, Q iT(ss) 2
max
(s, 5, Vs E S}
(6)
Notice that this thresholding scheme is not directly compatible with our definition of LMDPs in Section 3 While they are both used to simply introduce some relaxation in policy selection and it does not affect our general analysis, see Wray et al. (2015) and Pineda et al. (2015) for definition based on slacks.
3. Relative Slacking: In this approach, slacks are defined as ratios rj E (0, 1] rather than absolute values. Then, any action with value greater than (1 (1-1) 17) times the optimal value is considered acceptable. Formally,
Q1 a), Vs S} I1, e ( E IT-1 (s, (s))) 2 (1 (1-1) ( 1(9) IET;
max
(7)
While has not been proposed in any previous work, we included this for the sake of complete- ness. Notice that "Relative Thresholding" would be essentially the same technique, only with different parameters.
C ISSUES WITH TLQ
In this section, we will elaborate the different issues with TLQQ.
14

---

Under review as a conference paper at ICLR 2023
C.I FAILING TO REACH THE GOAL
In this section, we will explain how Relative Slacking and Absolute Slacking fail to reach the goal, an issue discussed in Section for Absolute Thresholding. We will again use Figure
Relative Slacking determines the maximum detour. If non-optimal action delays reaching the goal for & steps, this can be allowed only by defining r) > 7 However, this detour can be taken repeatedly, preventing actually reaching the goal.
Seeing how Absolute Slacking fails to overcome this problem is a little trickier. It requires a closer inspection of action-values. Since we want that the agent go left in (2, 2), the following should be true:
Right) < (T((22)), Right)
81
7R < R δ1 51 < R(1 77)
However, allowing the agent pick Righl, instead of Up in (1,0) requires:
(i((1,0), Right) (), 81
27 7R
61 2 Ry 72)
Combining these two requirements implies that:
R(1 -1) (1(1-77 72
>> 7(1 77)
0 72 +7
Solving the quadratic equation
0.62 >
This shows that to reach the desired policy, not only d but needs to be adjusted too. However, the y parameter assumed to be an environment constant and traditionally set values close to 1. Moreover, there is no real way to find the correct y value apart from computing the action-value function, the very thing we are trying compute.
Also, a similar analysis shows that small tricks like replacing the primary reward function with
0, if G
(s, a.)
(8)
11, otherise
with or without discounting does not solve this problem.
C.2 FAILURE TO SACRIFICE EARLY AND LATE
In this section, we will discuss issue that was not discussed in the main paper: the failure to sacrifice in the early and late parts the episode. This issue still occurs even if "failure to reach the goal" issue is avoided because the secondary objective happened to be terminating one.
Consider the maze shown Figure 3]
There are bad tiles in four rows and avoiding any of the rows of bad tiles takes two steps. For example, compare the following two paths:
1. (1,0) - (1, (1,2) 2. (1,0) - (2. - (2,1) (2 (1,,)
Path 2 avoids the bad tiles but takes steps to get (1,2) from (1, 0) compared only 2 steps of Path 1. Since avoiding any tiles costs the same number of extra steps, a natural policy in this maze would be avoiding H H tiles and ignoring hh tiles. However, this is not possible with either
15

---

Under review as a conference paper at ICLR 2023
MAZE
G
10
HH
HH
9
8
hh
hh
7
6
5
4
hh
hh
3
2
HH
S
0
2
Figure 5: An example MAZE which can be used to demonstrate the issues with uniform threshold- ing for TLQ.
thresholding method. Now, we will discuss how each thresholding method fails this achieving this Pareto optimal policy.
The action-values show the reward in G' discounted by the length of the shortest path to G from the cell this state-action pair leads to. For example, Q(11,)) 8), Right) = Rtys as it takes 3 steps to get to G' from (2, 8). Hence, the action-values increase as the agent gets closer to the goal. Assume that the agent is in (1, 0), the action that we need to take is Right, meaning TI should be set smaller than or equal to > R in Absolute Thresholding. However, since the action values will be larger than this in the states closer to G, will mean that the primary objective will be ignored for the rest of the episode. Hence, the agent will avoid h tiles too and the desired policy is unattainable.
Similarly, since Relative Thresholding effectively limits the length of detours and detours for avoid- ing hs are of the same length as the ones for Hs, this cannot give a policy that only goes through hs.
Absolute Slacking will cause this problem in the reverse, meaning the late episode detours requires detours during the whole episode. Assume the agent is in cell (1, (), then we need
(11,18)) R) Q1((1,8),U) - 51
, 7R 61
$1 Ry(1- 72)
Then, if going left instead of up is not allowed in cell (1,6):
(i((1,6), R) Qi((1,)), - 51
- Ry²(1 (1-2)
Combining these two requirements gives 3 -22) > Ry(1 - 72), which requires y > 1 which is false.
D VARIATIONS TO TLQ AND SOME ALTERNATIVES
In this section, we will try address the problems with TLQ within the framework of value function algorithms. We will start by briefly talking about two of our failed attempts (one completely failing and another half- half-working) to develop working TLQ variants to show the breadth of the problems and our work. Moreover, we helieve these ideas are quite natural and can look promising; so, we would like to share our experience to help people working TLQ algorithms.
16

---

Under review as a conference paper at ICLR 2023
Then, will describe two of our working solutions. While these solutions are limited either in terms of convergence or applicable domains, they provide either a good solution to a sizeable subset of common tasks give good alternative to TLQ in the general case.
D.1 FAILED ATTEMPTS
In this section, we will give our not very successful attempts to improve the performance of TLQ.
D.1.1 TL-SARSA
Our first failed attempt was switching to an on-policy learning framework which could solve agents getting stuck problem in Section 4.1 An important reason for this issue agents' optimistic expectation that they would be following the optimal behavior after each action. So, we considered an on-policy agent which actually uses its realistic behavior to Iearn could solve our issues.
So, we modified our update functions from Section B to mimic SARSA (Sutton & Barto (0188)
instead of Q-Learning This would mean replacing the max operators with the actual action. For example, the update function from Li & Czarnecki (2019)
(7(,,))= Σ P(s,a,)) s'eS
max (7(5'(((6))) sell:-1
will become:
())
(10)
dEES
where a' = (s').
However, this naive attempt failed due to some theoretical limitations of SARSA. Singh al. (2000) states that the convergence of SARSA is guaranteed under the condition that the policy greedy in limit. However, our policies are necessarily greedy with respect Q* in limit. Thresholding means that sometimes actions suboptimal w.r.t. Q* are chosen. For example, Qi > (2)
TI and (s a2) Qī(s,a) for state in two objective task, the policy we want to learn is not greedy w.r.t. Qi- This manifested itself as constant oscillations in the policy in experiments.
D.1.2 CYCLIC ACTION SELECTION
Our second half-failed attempt was modifyyng the action selection mechanism to solve the phe- nomenon described in Section [CII was based on the intuition that the reason for this issue was unnecessary sacrifices in the primary objective that is not required by the secondary objective. For example, we consider the maze Figure [ going left right cell (2,2) is the same w.rt. secondary objective, hence the agent should not sacrifice from the primary objective irrespective of the thresholds/slacks. Using this intuition, we developed cyclic action selection algorithm. In Algorithm 3, we show a two objective version of it for simplicity. While can be generalized to K objectives, we do believe it would be of interest considering its failure completely address our problems.
Algorithm CycllcActionSSelectio
Function CycliccAttionseeecttte
Q[A):
Ap < A1 & srcceptableactsss..... // If there are not more than one option A1 < 1 then
return arg A as)
end
Ag <- AcceptableActss( A1)
if [A] < then
return arg max (2(8,a)
end
return arg max,e4, ())
// Max over Ag but wrt Q1
17

---

Under review as a conference paper at ICLR 2023
As the pseudocode shows, the idea is to assign the unconstrained function threshold/slack which would be used to return the action selection right back to the primary objective but after applying this new threshold. This can be seen from the Q-functions used with arg max and Acceptab teagptableAcoo leccss starts with using Q1, then uses Q2 if there are multiple acceptable
throughout the algorithm. actions w.r.t. Q1- Finally, it uses Q1 again if there is more than one action acceptable w.r.t. Q2- Notice that there is a aewpptaableeeett..... call using Q2 which is different than Algorithm []] This requires having a threshold/slacking for the unconstrained objective which is basically a hack. It can be used with any thresholding function from Section
B
However, there are several problems with this approach. Firstly, having a threshold for the uncon- strained objective removes one of the important supposed benefits of TLQ, namely its intuitiveness. Especially the cyclic nature of this makes two different threshold values, one for each objective, to be coupled in complex way when deciding which detours will be taken. This can lead to a blind hyperparameter search. Our experiments show that the success of the policy is highly sensitive to the choices of these two hyperparamettrs..
Also, the problem described in Section C.2 persists, which means some of the very natural policies cannot be found with this technique.
D.2 INFORMED TARGETS
While using the SARSA variant has failed as seen in Section D.I.I. we believe that our intuition about the root of the issues described in Section C.1 was correct. Hence, we decided that an approach that could better align the update target with the "actual policy" could still solve the problem with short-sighted sacrifices. One such way could be accounting for the possibility of actions not being taken according to the given objective. Here, we will present the approach for two objectives. Its generalization K objectives is not necessarily straightfor straightforward and we regard it as a future research direction. To illustrate the idea, assume that Qi a1) > Q7(s', a2) > Ti and (s's', a2) > Q5 a1) for state s' in task with only two actions. Eq. 1 Juses R1 s') + 7/1 (s', a1) when computing update target for (T,s, a) as a1 maximizes Qi in state s'. However, this is misleading a1 will never be chosen in state s'. Instead (T's', a2) should be used as a2 maximizes Q3 in s'. Notice that this is still different than TL-SARSA as we may be following a completely different policy. In other words, 02 is used not because it is actually the action taken but it would be the action taken in the optimal case. We call this "informed targets" as value functions make "informed" updates, knowing what would be the actual action taken. More formally, this means modifying the update function for the primary objective to:
@i(s,a) = (BR +' arg max mag Q2(5 ((8))) F'ES
(11)
mell
Notice that the target for the objective is computed by choosing the optimal action with respect to 2. This prevents optimistic updates that happen due targets computed with actions that never would be taken. It should be noted that these updates were the reason for the failure mode discussed in Section C. Preventing them solves this issue but brings different problem: Instability in update targets. Consider the scenario in Section C If the current policy is going to left in state (2, 2). the value of going right would be RR. Assuming that the threshold is smaller than yR, at some point the value of going right would pass the threshold and both going right and left would be equally good. Once this happens, the update target for going right will become 7Q(s, Right), hence it will start to decrease until it is smaller than the threshold. Then, the target will go back to its original value, hence resulting in endless cycle. While it is possible to introduce some buffer in these updates such that the oscillations do not affect the policy that is being followed, the optimality of the resulting policy will depend on the initialization.
The update function with buffer hyperparameter can be obtained by replacing II; in Section with I1, which is defined as:
n. A (m E u.-1
max (s, aE 169 eem; 1)
(5, 8: b, Vs E S)
(12)
Notice that this will lead to a smaller oscillation zone which in turn is going to prevent the policy from oscillating as it still uses IT Also, note that the problems in Section C.2 still persists.
18

---

Under review as a conference paper at ICLR 2023
D.3 STATE AUGMENTATION FOR NON- REARHABILITT CONSTRAINED OBJECTIVE CASE
In this section, we will show how problem where constrained objectives are non-reachability can be solved by augmenting the state space. This idea of state augmentation has been used before with slightly different or narrower purposes Geibel (2006).
D.3.1 SINGLE CONSTRAINED OBJECTIVE
When the constrained objective is a non-reachability objective, this can be solved by using state augmentation that keeps track of obtained cost/reward for the constrained objective so far. In this section, we will use a different MDP that is inspired by a real-life scenario to also give a more intuitive example and show the real use of LMDPs.
An example: car travels across the country using highways. starts the journey in the city so and tries to go to city SF Sy. Once he reaches city in the set 8r, he will stop traveling. The highway toll for the highway from the city 8 to s' is represented by the function h(s, 8') where h S x S - R. The driver has a budget of B dollars and tries to have the best trip within this budget. His cost within this budget will be reimbursed by his company, so he has incentive to spend less as long as he is within the budget. His pleasure from arriving in the city s is given by p(s) where p: S IR and p(s) 0, Vs $ SF.
Formally, we have two objectives: minimizing the tolls and maximizing pleasure. Minimizing tolls is constraineddhhreehhlledd by the budget B. Maximizing the pleasure is unconstrained. Following our formulation in Section 3
R1 (s, a, s') = -h((s, s') and T = - B. Notice again that we expressed the threshold without discounting. Since we will not be using TLQ, we do not need to find the corresponding dis- counted threshold. Also, notice that the corresponding discounted threshold actually depends the trajectory.
(ssss'
R2(s, a, s = p(s').
We can express this two-objective task and preserve the preferences by constructing the following single-objective task:
Set of states: = S x R where (s, c) means the driver is in the city s and so far the driver has spent B - c dollars tolls. Augmented initial state (so, B).
Set of actions: À
Transition function P: S x x S [0, 1] where
P(s, a, c c h(s,8')
P((s,c), a. (d(,')) = {o,
(13)
otherwise
Reward function nt A $ S+
0,if $ SF p(s'), if 0 otherwise
R((s,c), a, a
(14)
Note that a non-zero reward will be given only when the car reaches a final destination. If the driver has stayed within the budget, he gets his pleasure value the reward. he has exceeded the budget, he is penalized accordingly with a multiplier X. Implicitly, we assume that p(s) 0, Vs E Sp.
Also, note that while this reward function specifies the optimal policy correctly, it may not be good reward function for learning and exploration purposes. For instance, until the agent learns how to stay within the budget, all the terminal states will have negative values and non-terminal states will have higher values. Hence, the agent can get stuck here by trying to avoid terminal states. Realizing that it can get positive rewards may require a good exploration policy.
This has the following advantages:
Different thresholds are supported
Thresholding is intuitive
Convergence proofs exist.
19

---

Under review as a conference paper at ICLR 2023
D.3.2 OPTIMALITY OF NEW MDP
We can easily show that this single-objective task has the same ordering of trajectories the original task. More formally, <² = sp. ag. si aj...., S,, is better than C² sy ag s S under the original task if and only if the augmented trajectory ç² also better than augmented trajectory ?² under this when comparing trajectories. For the original task trajectories, we use the thresholded lexicographic comparison relation defined in Section 3. Note that subscripts n' and n² denotes the indexes of Ç and ²² not the polynomials.
task. Here, we will use the cumulative reward as the optimality metric
Proof:
Ç' 2² under the original task if and only if one of the following must be true:
1. Eς Ee 2 Ti and Ee Ra(s, Ee² (2(s,,,5))
2 2. Ee Ri(s,,, 2 11 EsRRi(s,0,s)
3. n > Es Ri(s,a, E. Ri(s,a,8)
We can show that each these statements implies that the same ordering holds for 2² (2 under the single objective task. Firstly observe that:
Σ R(3,0,8)) = (s)
= E )'( >0
Sn(s) E Sp A (x(c)2
= Eh(s,s)) 2B B Σ
2
Then, for the first case:
Σ Ri(s,a,s)). Σ (i(s,,,s))2 21
5²
Σ A(s,a,8)= = p(3, (s)) A Σ
2,))) = (s))
2²
Also,
Σ R2'2, Σ R2(), ạ
p(8 (s)) 2 (s))
Σ R(s,0,8) > Σ R(s,ā,8))
- 2
For the second case,
20

---

Under review as a conference paper at ICLR 2023
E ()( Σ Ri(s,a,s))
E((3,,,8') > 0^ Σ )( S0
Ç
5²
Σ R((,,,8)) Σ a)))
26
For the third case, can observe that:
Σ Ri(s, 2 Σ R1(),,,55)
B> Σ (), 2 E(s,,'')
Ç¹
5²
8n2 2 8,2
Aba (c) (0)
Σ
R(S, à 8') > Σ 8(),0,8)
-
Note that we've ve specified the unconstrained objective as a quantitative reachability objective, ie. it is non-zero only in the terminal states. Now, we will remove the restriction over p.
Alternative 1:
First option is to extend the state space again to keep track of as well. So, the
MDP will be:
State Space: Š = S x x I where the state (s, c, p) corresponds to accumulating p p(s) so far.
Transition function: P: S x A x S + 1] where
P((s, (s', v')
(15)
(((ss c), a, ( p(s) 0, otherwise
(16)
Reward function: Š A $ + R where
0f & Sr if 20 otherwiie
R((s.c.p). =
(17)
Extending the state space is not always optimal, as it increases the complexity. Instead, we can try to directly modify 14 With this, we will still use Š and P as the state space and transition function, respectively.
Alternative 2:
start giving p(s') reward in the non-terminal states. Then, antee the lexicographic ordering by subtracting a large value Ct that is guaranteed to be larger than E.P(s) from Xc.
Most simply,
guar-
p(s'),if'''s $ SF p(s') (is'),els else if e' 20 Ac' C₁ otherwise
(s
(18)
21

---

Under review as a conference paper at ICLR 2023
Optimality proofs of these new MDPs are very similar to proof in Section D.3.2 So, leave it to the reader to avoid repeating
D.3.3 MULTIPLE CONSTRAINED OBJECTIVES CASE
Our analysis above assumes that there only two objectives: constrained primary objective and an unconstrained secondary objective. However, that setting, many CMDP algorithms are readily applicable. Therefore, we are more interested when we have multiple constraints that need to be solved in the lexicographic order. Yet, extending the approach above to this setting is not straightforward. To apply it, we need to know which constraints can be satisfied together. More formally, if the constrained objectives are I,..., (k 1). we need to find the maximum such that there exists policy that satisfies objectives 1, I,.... (i. (i- (1- i.c. can reach a state (s, C1 ....... C/-1) such that s E Sp and C1, .2...., C--1 2 O. We identified three different approaches that could be used for this but we believe future work is needed to develop more efficient methods.
One-by-one The simplest method solve tasks with multiple constrained objectives is reminis- cent of linear search algorithm. We can start with the first (most important) constraint and see if we find policy that satisfies it, i.c. can reach (s, c1) such that Sy and c1 2 0 from 8intt If such a policy exists, we can introduce the second constraint to see if policy that satisfies both of them simultancously exists. Continuing in this fashion, it can be found up which objective the agent can satisfy simultaneously. However, this method can be prohibitively expensive as requires solving ((k) subproblems. More importantly, it is very hard if not impossible to know whether subproblem not solvable or just taking too long to learn.
For this method, we can construct the following reward function for each value in different ways. An approach would be maximizing the worst violated constraint:
R((s, (Ils,.,...,,..II)) (s' (s)))...,)))))))
(19)
R(s, a, s), if $ Sr R(s, else Amin dainnyd-- Cj, otherwise
else if c, 20 Vj <i
(20)
Where R is the reward function of the unconstrained objective in the original MDP and Ct is an upper bound on the unconstrained reward that can be collected during an episode.
Binary Search As the name suggests, this method is inspired by binary search algorithm. As- suming the constrained objectives are 1, 1.... (k 1), we can start by trying to solve constraints .,..., 1 then we can try I,..., not, respectively. While this method is faster than one-by-one, it still suffers from the same halting problem. We can Eq. 1 this approach too.
or 1...., _ depending on whether was solvable or
Dynamic Search This method not concretized and is intended mostly as an idea for future re- search. HHaes et al. (2020) presents approach to set the threshold values for TLQ dynamically, depending on the attainable performance up to that point in the training. Similarly, we can intro- duce and remove constraints dynamically during the training without waiting for the algorithm to successfully converge for subproblem.
E CONE PROJECTION
In this section, we show how the projection equation in Eq. derived. For the sake of com- pleteness, we start with some simpler and well-known projections and move to the derivation of Eq.
E. ORTHOGONAL. PROJECTION ONTO HYPERPLANE
One of the most well-known projection tasks is projecting a vector y E R.a onto a hyperplane H that passes through origin, specified by its normal vector RR as Ha {x R (æ, a) 0)
22

---

Under review as a conference paper at ICLR 2023
where () denotes the dot product defined as v a E; v,a,. Projection of y onto Ha is notated as p (3) and defined as P (y) arg min H., 110 p (z)ll. ||l I|I| denotes the L2 norm defined
|| Vor
Σ 2
(o( (y) can be found easily by using well-known result p!l (y) || a, i.e. the projection error is
parallel to the normal vector of the hyperplane. Then, there is a E R such that p! (y) ca.
y P (y) a
P (y) = y ca
(Pd (y), a) = (y, a) c(a, a)
0 = (y. a) - c|la||
c = (y. a)
||a||2
( a)
pM (v) = y
||| a
E.2 PROJECTION ONTO A HALFSPACE
In many cases, may want not project vector that is already one side of the hyperplane. For example, if we want to project vector onto feasible set, the vector that already the feasible set should not be projected. This idea can be formalized by extending the definition above to halfspaces. positive halfspace S is defined as S {æ E g" (a, a) 0}. This can be thought of as the set of vectors with which makes angle less than or equal to z. We can define the projection onto S follows:
Ps
(a)
y p (a), otherwise
y E St
(21)
Note that the piecewise function handles y St and y & S cases separately.
E.3 PROJECTING VECTOR ONTO A CONE
While halfspaces are one of the most common sets in practice, they can be limiting in many cases. A natural extension to this idea would be limiting the set to vectors with which makes an angle A for some < < g. The angle between two vectors defined using dot product:
(u, u) cos Lu, _|||||| Note that since cos(A) () cos 2n - A, the Lv, a can take two values between 0 and 2x. For simplicity, will always talk about the smaller angle, i.c. R" x R [0. pi). This would be hypercone which simplifies to a halfspace when Let CA be a hypercone with axis E R and angle 5 - A, i.c.
a 2 cos
C = x E
[ = 0V
π 2
A)}
(22)
|
|
which uses the dot product formula above to see cosine of the angle between a and æ is greater
than cosine of A. For 0 < A 5. this corresponds to the angle between and æ being in the
interval [0, - AJ.
Then, the projection of vector g R" onto C' defined as
ge arg min | 9|12 gEC
(23)
23

---

Under review as a conference paper at ICLR 2023
Solving this equation is not straightforward for the halfspaces. We will first show that g" is planar with g and a, i.e. they can be written as linear combinations of each other. are on the same plane. This is intuitive and well-known in lower dimensions, but below can be seen formal proof for higher dimensions. Once this proven, we can utilize some two-dimensional geometric intuition to simplify the algebra.
E.4 PROOF OF PLANARITY
The projection is constrained optimization problem:
min |
gl12
a²'x x
subject
2 -A)
a |||||
If can show that the solution this vector planar with g and a, will be done. The solu- tion to this constrained optimization problem should satisfy Karush-Kuhn-Tucker (KKT) conditions which generalize the Lagrange Multiplier method to problems with inequality constraints. However, applying KKT conditions this format does not provide a clean result. Therefore, we will prove stronger claim that gives cleaner KKT conditions:
Lemma E.1. For any fixed length the projection is minimized when æ, g, and a are planar.
Proof. This gives us the following modified optimization problem with an additional constraint. Now, we will show that the planarity does not depend on ||æ]],, which will be denoted as c.
min
f(x) || gli2
a œ
subject to
r(x) ||a |
cos
aT
-A)
sin A
2
h(x)) |x|
=
Swapping norms with their dot product equivalents (replacing the norm in the objective and equality constraint with a norm square for conciseness) and writing the remaining in the standard format gives us:
min
f(x) x 2g x + g g a T x
subject to
r(x) = sin VaTavo' - æ
<
h(()) = x x
=0
KKT conditions for this problem require that any minimum point should satisfy the following condition Chong & Zak 2004):
24

---

Under review as a conference paper at ICLR 2023
Vf(ā)+ (VV())) =0
a(va'av va a 25 (a (a''t)
2 2g X2 +
V
=0 0
a" è from feasibility
(a=))
a(cva"a) va x( a
= 28 2g X2Ā +
0
(c))
ca a e² =0
a' = Ava C.S.
= 28 2g X2Φ +
2 aaa
V &
sin A Ava a
7 2 2g X2 +
vva a
sin
28 2g X28 + 1
CV a P
2 0
Reorganize the terms
= 4(2 2X sin A
a
= 2g cf a
Since g" is such a minimum point, the above analysis holds for it too. Hence, be written linear combination of a and This means that the three vectors are planar.
Note that we can see another important result from the analysis above. The complementary slackness condition of KKT requires that pr({) 0. However, if μ O, the last line equation in the proof simplifies to
(2 + 2X) 2g
If (2 + 2A) 2 means g and è in the same direction. This only possible if g is already in the hypercone. If (2 + 2A) < O, this means g and & are in the opposite directions which cannot be the projection, choosing 0 vector would give smaller projection error. Hence, unless g is already in the hypercone and does not require a projection, r(t) should be 0. That means the angle between a and à is - A.
E.5 DERIVATION OF THE PROJECTION FORMULA
Now that it is known that all three vectors planar, can just two-dimensional geometry to reason about it and derive the formula. This can be done as these three vectors in R" will span two-dimensional subspace of [R" unless they are all collinear, i.e. scalar multiplicative of each other. This would mean that a and g are already the same direction and no projection is needed, which is special case we will consider separately. Also, any 2-dimensional subspace of R is isomorphic to R.2, i.e. identical in structurellin (2021). }. Figure shows the case when the angle between a and g, Φ. is larger than _. It can be confirmed that the other configurations like will result in the same equations too. Note that when writing the equations below, we considered when g is outside of the cone. When E C, we will simply call gd = similar to the piecewise function in Section E.2
Firstly, will find the direction of the projection. Let p' be vector with the same direction g" and it can be written as below.
p' = g + aa
25

---

Under review as a conference paper at ICLR 2023
2.
21
Figure 6: This figure shows how the vectors would be positioned on a plane. The orange region
shows the cone. The angle between a and g. di is omitted to not crowd the figure.
Then, can find below by using the law of sines:
1
al|a||| |||||
sin (cb
2 + [g cos (ő
cos
sin A
2
sin (5 A
al[a]] = -lggg sin π
Φ) + | cos
sin A
2
2
sin
1
A)
=
a||a|||
= gl cos Φ + ||و|| sin Φ cos A
sin
a||a]]
|| (sin Ø
sin A cos (b)
cos A
|g
a
(sin
sin A cos Φ) cos A
|a]|
|g||
a
(sin Φ tan cos
|all
||g||
p'
g
(sin @ tan A cos Φ)a
||a||
This p' has the correct direction but not necessarily the correct norm to minimize the projection error. The correct projection will be g" kpp where l E R. We find the l using the well-known rule
26

---

Under review as a conference paper at ICLR 2023
that the projection error is perpendicular to the projection.
(g kp', .p) 0
(.,p", k(p p²) =0
l cos (A + Φ
z
2
kllp'11 112 =
=
| |00
008
π 2
+ Φ) k 11p1'11 =
|| sin (A + Φ) k||le'1" =
Ip ( sin (A + Φ) kllp'l)) -0
| sin (A + 6) - k||p'|| =0
if if +0
| sin (A + Φ) = k k|lp'll
|g
sin (A + の) IP
The same result also could obtained by solving another optimization problem with as the variable. Combining the formula for p' and k gives the formula for g" pes.scsspppppeeeprrccbblllll
Moving forward, we'll assume function projectConelg, a, A) which returns the projection of onto CA possibly handling g E Ca and g & Ca cases separately.
F LEXICOGRAPHIC PROJECTION ALGORITHM
In this section, start by giving some background gradients and directional derivatives that necessary to understand our algorithm. Then, we share the formulation of the lexicographic optimization problems projection instead of halfspace projection and share the remaining results with our algorithm that was left out of the main paper due to space constraints.
solve. Finally, we give some further justification why need cone
F.1 BACKGROUND ON GRADIENT AND DIRECTIONAL DERIVATIVES
Gradient of a function gives the direction and rate of the fastest increase from point p. Moreover, directional derivative of F' at along direction u, i.c. 8F Du (p), can be computed (u, FF())).
Intuitively, the directional derivatives give the rate of change (F(() in the given direction. As can dot product implies, this rate the largest when the angle between u and V zero. other words, the gradient gives the direction of the fastest increase.
Using directional derivatives, we can reason about how changes to p affect the value of F. For example, since the gradient has the fastest instantaneous rate of change, F(p + VF(p) [VP())
> F(p+
|TwT] ), Vu R for sufficiently small E.
Similarly, if Zu, (p S y. F(p cu) 2 F(p) for sufficiently small c. This can be confirmed by computing the directional derivative using (u, VF(p)) | [u]][[F((p)) F()) cos Zu, F In other words, using the directional derivatives, we can obtain a direction of non-decrease for sufficiently small step size.
F.2 FORMULATION OF THRESHOLDED LEXICOGRAPIIC MULTI-OBJECTIVE OPTIMIZATION PROBLEMS
A generic multi-objective optimization problem with K objectives and parameters can be formu- lated as:
Given a function F : + IRK where A E IR" and a comparison relation 2" for value vectors in K find an element 8" A such that f(0*) 2d f(0) for all A.
Notice that when we have multiple objectives, the gradients will form a K-tuple, G = Fi,,, ..,..., FK)), where V.F is the gradient of tth component of F.
27

---

Under review as a conference paper at ICLR 2023
Different instantiations of the comparison relation lead to various multi-objective problem families. In the case of Lexicographic Multi-Objective Optimization, the comparison relation >5, is defined as
>"
Bi
K
S. t.
m1 2 o2 11
<
u2)
In Thresholded Lexicographic Multi-Objectio Optimization, threshold vector RK-1 is intro- duced to express the values after which the user does not care about improvements in that objective. This new comparison relation can be denoted by > (c,r) which is defined as:
iff there exists i S K such that:
Yj < i we have uj 2 (yj, Ty):: and i K then min U4 Ti) min(vi, 7),, otherwise if i K then u, > Vi.
The relation >n is defined
Notice that this completely parallels the definition of LMDPs from Section
F.3 JUSTIFICATION OF CONE PROJECTION
Since thresholded lexicographic multi-objective optimization problems impose a strict importance order the objectives and it is not known how many objectives can be satisfied simultaneously be- forehand, a natural approach is to optimize the objectives one- my- until they reach the threshold values. However, once objective is satisfied, optimizing the next objective could have detrimen- tal effect on the satisfied objective. This could even lead to the previous objective failing. While we can always go back to optimizing this failing objective, this would be inefficient, even worse, potentially leading to endless loops of switching between objectives.
However, we could limit our search for satisfying point for the new objective to the directions detrimental to already satisfied objectives by using our results about directional derivatives. For simplicity, assume that we have a primary objective F1 which is satisfied at the current point 6, and secondary objective F2 which we are trying to optimize next. V. Fi, the change in F1 along direction u, is equal to (u, V (0.)) = |u V (0x) cos( Lu, Fi,(),,) choosing a direction which makes angle negative. Therefore, updating as 0n+1 = 0, + eu with an infinitesimal e would not reduce the value of Fi. If V P2 is positive, we can optimize F22 without jeopardizing Fi. Note that the same logic hold even if we have already satisfied objectives F,,..., F& and now optimizing F 1 as long as vi < FV 2 0.
[ m with (F, would make the directional derivative non-
While any such u allows us to carefully optimize our new objective Fz, we should pick an u with maximum aFa (0.,) to optimize F2 most efficiently. While we know that V (9,.) has the maximum directional derivative, may not satisfy our previous requirements. Instead, we can use the vector projection find the which minimizes I| F2((0) under the constraint V Fi > O. Notice that non-negative directional derivative means that u lies on the positive halfspace of V E (0,), i.c. u E St So, projecting (2,.)) onto F will give us the u which satisfies the requirement and is closest to F220 i.e. has the largest directional derivative. As a special case, when V F1 and F2 point in opposite directions, this projection will give zero vector which means that cannot optimize F2 without sacrificing F,. This point would be locally Pareto optimal. In general, itera- tively projecting Vi++i (0,) on the positive halfspaces of V F, (0,), VF. gives the desired vector as long as the final vector satisfies the requirements. If it does not satisfy the requirements, this point can be called locally Pareto optimal point.
2u
While the approach above has the theoretical guarantees for the infinitely small step size, this does not translate to practice as the step sizes are not small enough. For example, Figure shows how
direction that líes on the positive halfspace of the gradient lead to decrease. It can be also seen
that unless the step size is infinitely small, this would always lead to a decrease. We can overcome this issue by generalizing halfspace to hypercone for which the central angle is z A where A
28

---

Under review as a conference paper at ICLR 2023
04
V (i)))
F2
Figure 7: This figure shows why projecting onto the positive hyperspace always enough. The curves show the level curves of function Fi. V shows the projection of V on the positive halfspace of VF. Note that following V V2 reduces the function from 0.5 0.4.
the hyperparameter of conservativeness. For A 0, this would be the halfspace case introduced above. Figure X shows how hypercone projection differs from halfspace projection and keeps the function above at the current level for reasonably large step sizes.
F,4 EXPERIMENTS
In this section, we present rest the results for the experiments shown Figure 2 All of experiments are done using the same benchmark problem described in the main paper.
Figure demonstrates how the value changes shown in Figure were reflected on the parameter space. The figure shows the trajectory the algorithm takes over the level curves of the functions. Notice that F2, in blue, is completely ignored until the threshold for F₁ is reached. Then, the algo- rithm optimizes F2 while respecting the passed threshold of Fj, indicated by its trajectory almost along the level curve of Fi.
Repeating the same experiment with AC heuristic and 0.01 yields the results shown in Figure I0 and Figure [T] Notice that the highest value we were able to obtain for Fz was -0.580 without AC heuristic; but this was improved to -0.554 with AC. This is because AC' prevents unnecessarily improving Fi over the threshold. This can be observed from the final values of Fj which is - -0.450 without AC and -0.496 with AC. The downside is losing the smooth and safe trajectory allowed by our vanilla algorithm, indicated by the zig-zags in Figure 10 and Figure [1 The zig-zags represent the corrections for sacrificing too much from Fi when optimizing F2.
G USING LEXICOGRAPHIC PROJECTION ALGORITHM RL
In this section, we first give the REINFORCE algorithm we use as the basis for our Lexicographic REINFORCE algorithm for easier comparison. Then, share further details of our experiments.
29

---

Under review as a conference paper at ICLR 2023
V((())
F22
Figure 8: A visualization cone projection. The dashed line shows the boundaries of the cone which are two lines in two dimensions. Notice that following VF2 keeps the function from or above 0.5 unless a very large step size is chosen.
G.1 REINFORCE ALGORITHM
The pseudocode for REINFORCE algorithm that we will use as the basis for our adaptation (Algo- rithm 5)) can be seen Algorithm
Algorithm Vanilla REINFORCE
Process REINFORCE:
Initialize policy function π (a]s,, 0) with random parameter 0
for ep 1, Nº do
Generate episode So, Ao, R....., . ST-I, AT 1, Ry and save In (AA,(S)) at every step.
Gr-1 f- 0
for f = T, do
G. Rg GG+41
end
L ---EEoo In x (A,
Update 0 taking optimizer step for loss L
end return (als,, 0)
Note that Algorithm experiments, we found that Adam is easier to use with the tasks at hand. Similarly, we found that using Adam optimizer is better than vanilla gradient descent for adaptation too.
be used with optimizers other than vanilla gradient descent. In
30

---

Under review as a conference paper at ICLR 2023
Trajectory of the Search for the Maximum Point
1.2
0.4
0.2
-0.4
24
02
6.0
53
3A
0.5
0.0
3.0
Figure 9: Behavior of the algorithm without the active constraints heuristic and hyperparameters 90 The red and blue curves show the level curves of Fi and F2, respectively. The
= 0.2 and A = и single yellow curve shows the threshold for Fi. The black line shows the trajectory of the solution, while the red and blue arrows show the gradients w.r.t. Fg and Fg, respectively.
31

---

Under review as a conference paper at ICLR 2023
Trajectory of the Search for the Maximum Point
1.2
0.4
0.2
-0.4
24
02
6.0
53
3A
0.5
0.0
3.0
13
Figure 10: Behavior of the algorithm with the active constraints heuristic and b 0.01. The rest of the hyperparameters are as described in Figure
G.2 OUR ADAPTATION OF REINFORCE
Algorithm 5 Lexicographic REINFORCE
Process REINFORCE (T, A, AC, b, Ne))
Initialize policy function N (a|s,, 0) with random parameter 0
ep = Ne do
Generate an episode So, Ao, Ri , ST AT 1, Por and save In T (AA(S.)) at every step.
F+0 0
for o= 1, do
GT+1 f- 0
for 1 = T,10. do
G. Rg 7G41
F. - Fo R
end
L - In π (A,[S)))
Compute the gradient of with respect 0 and append it to M
end d
FindDi rection F, A, AC
Use d as the gradient for the optimizer step to update
end
return 7 (als,
32

---

Under review as a conference paper at ICLR 2023
Function Values by Iteration for Vanilla Algorithm
0.0
-0.496
0.5
-0.554
1.0
Function Value
-1.5
Threshold Passing Point
2.5
-3.0
Primary Objective
3.5
Secondary Objective
Threshold
-4.0
10
30
40
60
Iteration
Figure 11: The changes in the function values for the experiment described in Figure 10
MAZE
G
1h hh
3
2
HH
HH
0
2
Figure 12: The maze be used in Reachability experiment.
G.3 EXPERIMENTS
In this section, share the details of the experimental setup for the adapted REINFORCE algo- rithm.
G.3.1 POLICY FUNCTION
In both experiments, We represent the state via one-hot encoding (Harris & Harris (015)). hence the input dimension the same the size of state space. For example, 20 for the maze Figure 3 Then the hidden layer a fully connected layer with 128 units and they use ReLU activation function Agarap (018)). We also used dropout layer (Srivastava al. (2014)) with drop probability 0.6. Finally, the output layer has units, representing the four valid actions in our benchmark. The outputs of these units are converted to action probabilities by applying softmax function with temperature 10 LeCun et al. (2015). The temperature hyperparameter allows making the policy less deterministic by making the action probabilities closer to each other. This makes sure that the policy keeps exploring so it does get stuck in local minima. This is particularly important for our algorithm, considering that the learning of the less important objectives does not start until the important ones are learned.
two layer neural network (LeCun al. (2015)) for policy function.
G.3.2 REACHABILITY EXPERIMENT
For Reachability experiment, we use the maze Figure As we only care about the agent eventually reaching the goal, the agent can completely avoid going on bad tile. All the policies where it reaches the goal but goes through bad tile in the process will be dominated by this policy. Hence, we will expect our agent to learn the policy where it eventually reaches the goal and never steps bad tile.
33

---

Under review as a conference paper at ICLR 2023
Frequency of Reaching the Desired Trajectory
0.8
0.6
Frequency
0.4
0.2
0.0
500
1000
1500
2000
2500
3000
3500
4000
Episode
Figure 13: Average satisfaction frequency of 10 seeds for the experiment described in Section G.3.2
The shaded region shows confidence interval of two standard deviation width around the mean.
We run S for N. = 4000 episodes and we repeat our experiment with 10 different ran- dom seeds. As the policy Figure 13 summarizes the performance
is stochastic, different seeds give significantly different results. seeds. The plot shows the ratio of the successful tra- jectories out of 100 trajectories where successful is defined satisfying the reachability constraint without stepping on bad tile. The line shows the mean of 10 different seeds where the shaded region shows the variance in the experiment as two standard deviations around the mean. It can be clearly seen that as the training progresses, the satisfaction frequency increases. Out of the seeds, 4 find policies that have 90% success over 100 episodes.
We can also take closer look into how the training progresses for successful seed. Figure [4 shows how the satisfaction frequency for each objective changes throughout the training. It can be that the primary objective, reaching the goal eventually starts with high frequency but drops a little bit while the secondary is being learned. Then, the frequencies for both objectives start to increase together. Intuitively, the initial drop represents when the agent starts to consider "do nothing" policies which reduces the success of the primary objective. But the agent then learns that it can still maintain 0 penalties without just staying in place.
G.4 ADDITIONAL. EXPERIMENTS WITH MORE OBJECTIVES AND ADDITIONAL. BASELINES
In this section, will present additional results using benchmark domain from the literature. Fruit Tree Navigation (FTN) Yang et al.] (2019) requires the agent to explore a full binary tree of depth with fruits the leaf nodes. Each fruit has randomly assigned vectorial reward which encodes the amount of different nutrition components of the fruit. The agent needs to find path from the root to the fruit with that fits to the user preferences by choosing between left and right subtrees at every non-leaf node.
R
This domain perfectly highlights the benefits of thresholded lexicographic user preference compared linear scalarization. The user can have certain threshold that needs be reached for each nutrition component and an importance order between these components that should be followed if it is not possible satisfy all of the thresholds. Using linear scalarization in this case requires knowing the reward values of all of the fruits beforehand, deciding which fruit would fit the user preference, and finding weight vector for which the desired fruit is bettr than others.
34

---

Under review as a conference paper at ICLR 2023
Satisfaction Frequency by Objective
1.0
0.6
0.2
Both
Objective
Objective
500
1000
1500
2000
2500
3000
3500
4000
Episodes
Figure 14: Satisfaction frequency for single seed for the experiment described in Section G.3.2
Figure 13 shows the need for the A parameter. can be seen that using just hyperplanes as done in Uchibe & Doya 2008) fails this task. Similarly, TLQ agent also fails to find the desired leaf.
35

---

Under review as a conference paper at ICLR 2023
Probability reaching the desired leaf in FTN environment
0.6
A 4-10 5
HyperPlanc TLQ
Probability
0.3
02
5000
10000
15000
20000
25000
30000
35000
40000
Number episodes
Figure 15: Probability of reaching the desired leaf, averaged over three different random seeds. A values represents conservativeness hyperparameter of the hypercone in degrees.
36


Reviews:
[{"review_id": "_U2CgZm3QD", "reviewer": "Reviewer_Ekhh", "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": "The authors investigate multi-objective RL with thresholded lexicographic ordered objectives. The authors start by investigating the shortcomings of the existing TLQ algorithm. While some of these shortcomings are already known (for example Vamplew et. al.) the authors also show that TLQ does not work under certain circumstances (terminating reachability on the constrained objective and the unconstrained is non-terminating).\nAfter that, the authors propose a lexicographic projection algorithm that projects the gradients onto hypercones and shows how to use the projection algorithm in RL.\nIn the end, the authors evaluate the lexicographic projection on a simple analytic function. For RL they evaluate their approach on a simple Maze setting only with no comparison to baselines.", "summary_of_the_review": "Because of the evaluation, the benefits and limitations of the proposed approach in practice are unclear. The experiments done in the paper are insufficient. They are on very few settings (e.g., only two objectives), and relevant baselines, and metrics are not reported. Additionally, the paper should be more self-contained and is very hard to follow without reading the appendix.", "strength_and_weaknesses": "Strong points:\n* A dive into the shortcomings of TLQ is interesting\n* The method could lead to improvements over existing methods. Unfortunately, due to a lack of evaluation, it is unclear how well this method performs.\n\nWeak points:\n* The approach and the reasoning why certain things are that way are extremely hard to follow without the appendix. The description of the approach just takes 1 1/2 pages. The authors should write the paper in a more self-contained way.\n* The influence and sensitivity wrt. several hyperparameters and how to choose them is unclear (what is a good value for b, ∆,...?)\n* The approach of the paper (projecting into hypercones instead of positive half-spaces) is not very novel and the improvements of that in practice are unclear.\n* The evaluation of the proposed method has serious flaws:\n** The comparison to relevant baselines like TLQ or Lexicographic Multi-Objective Reinforcement Learning (Joar Skalse et al.) is missing. ** All experiments are only done with two objectives. This is problematic because with more objectives finding a good solution is likely much more challenging, and it is unclear how well the method performs with more objectives.\n** Comparison to different (existing projections) like into positive half-spaces is missing. Therefore, it is unclear whether the proposed projection into hypercones has benefits in practice.\n** It is unclear how the proposed method works in settings where TLQ does not fail.\n** Important and commonly used metrics in the evaluation are missing. In RL, the average reward (for each objective) gathered by the policy is one of the most commonly used metrics. However, the authors do not report such metrics.\n** The comparison has been made on a single RL setting only; for more benchmarks see for example A Survey on Discrete Multi-Objective Reinforcement Learning Benchmarks, Thomas Cassimon et. al.\n", "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": "W2YHAnaOGd", "reviewer": "Reviewer_NWsv", "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": "The authors discuss shortcomings of existing approaches for thresholded lexicographic ordered multiobijective problems in reinforcement learning.  Additionally, the authors provide a policy gradient algorithm that performs well on this class of problems.", "summary_of_the_review": "A solid submission tackling a fairly new space.  The manuscript could use more extensive, and more practically relevant experiments, though.", "strength_and_weaknesses": "Strengths: The paper did an excellent job formalizing the problems existing with current methods (especially failure cases), as well as how the author's approach directly addresses these problems.\n\nWeaknesses: It's a tired objection, but it's somewhat difficult to situate the author's results with respect to the rest of the literature.  While this is certainly true of any novel work, for which there isn't much else to compare to, then the onus is exceptionally upon the authors to provide compelling results on difficult problems.  While the problems that the authors chose to present were great as educational devices demonstrating the utility of their methods, it's unclear how _practically_ useful the author's algorithm is.  It would be great if the authors could further discuss how their algorithm might fare in a more difficult, less synthetic setting.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OmNY7Lfiq36", "reviewer": "Reviewer_Jg7J", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 focuses on lexicographic multi-objective problems. Firstly, the shortcomings of the existing algorithm Lexicographic Q-Learning (TLQ) are analyzed, and the scenarios in which it is not applicable are pointed out. Secondly, this paper proposes the lexicographic projection algorithm (LPA), which performs multi-objective optimization by a heuristic projection of gradients, so that the current optimization targets the highest priority objective that does not reach the threshold while preventing the degradation of higher priority objectives as much as possible. Finally, this paper combines LPA with a policy-based reinforcement learning algorithm and validates it in the MAZE environment.", "summary_of_the_review": "I think this paper introduces a new algorithm combined with policy gradient, which approaches the lexicographic multi-objective problem from a new perspective. However, this paper has some fatal flaws. (1) The motivation is not well-supported. (2) The experiment needs to be more fully validated.", "strength_and_weaknesses": "**Strengths**:\n\n1. The problem this paper tries to solve is greatly concerned in the RL community.\n2. The idea of solving lexicographic MORL problems with policy-based algorithms is a good attempt. The LPA algorithm is very versatile since it can be combined with any gradient-optimization algorithms and any policy-gradient (and actor-critic) algorithms.\n3. This paper is well organized.\n\n**Weaknesses**:\n\n1. The motivation is not well-supported. This paper focus on the lexicographic multi-objective problems that can not be solved by Lexicographic Q-Learning (TLQ), and two types of maze example are analyzed. Each of them will be discussed below.\n   1) Problems with Reachability Constraint (Fig.1). The problem can be solved by TQL, but the problem itself needs to be redefined. The problem should contain a third objective time cost. The primary objective (Reach G) does not consider the time spent, i.e. no discounting situation, so the algorithm converges to a random policy (described in the paper as \"all actions would have the value $\\tau_1$\"). If the time factor is not taken into account, the random policy is right, but it's not an ideal policy. The discount factor is a mathematical trick to make an infinite sum finite, and it also chooses a suitable planning horizon. So discount factor can be viewed as a trade-off of task rewards and time costs, which is also necessary in reality, because no one can do something without considering the time. Then, the secondary objective (avoid bad tiles) will lead to another stochastic policy that does not step on tiles but may move back and forth. The third objective (time cost) can be formalized as a time penalty or discount factor, leading to the deterministic ideal policy.\n   2) Problems with Non-reachability Constraint (Fig.3). This problem (or just the example in Fig.3.) can be solved by TQL. The primary objective (minimizing the cost of tiles) can converge to the unique path (including *(0-3,0), (3,1), (0-3,2), (0,3), (0-1,3)* ), but there may be backtracking (like *Left* in *(1,0)* with previous step *Right* in *(0,0)*). And the secondary objective (minimizing the time) then allows the agent to reach the goal without backtracking, i.e., in 11 steps.\n2. If the number of objectives is greater than or equal to 3, which means that \"return None\" of Algorithm 2 may occur, no theoretical proof of the convergence or experimental verification is given in this paper.\n3. Here are some minor typographical errors and suggestions.\n   1) Spelling error on page 4, line 9. \"iff\" $\\rightarrow$ \"if\"\n   2) The full name of LMDP should be given before using LMDP in Sec. 1.\n   3) The description of Fig. 1 uses $H$s and $h$s indicate tiles, while $HH$s and $hh$s are in the description of Fig. 3.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0kRkN0Ikba", "reviewer": "Reviewer_oJxc", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "Multiobjective (MO) RL  has many applications with the thresholding algorithm often used. The authors point out a deficiency of such algorithms and propose a PG based approach. They also conduct a numerical study comparing their algorithm with benchmark algorithms. ", "summary_of_the_review": "While adapting PG to MO is new the underlying ideas are not significantly innovative. \nI don't find the identified problems with reachability of significant importance. \n\nLack of sound experiments is a significant drawback of the work. There are no benchmark algorithms and the datasets are very easy. \n\nThere is also abundant work in MO-MAB that might be applicable here. While MAB doesn't have the notion of PG, they can serve as benchmarks. ", "strength_and_weaknesses": "Strengths:\nThe idea of using PG for MO-RL. \nThe example showing the drawbacks for the thresholding algorithms. \n\nWeaknesses:\nSome references and algorithms are missing in the background work (and experiments). See M. Fleischer. The measure of Pareto optima applications to multi-objective metaheuristics. EMO, Springer Verlag, pages 519-533, 2003.\nThe computational experiments are not strong. It seems the experiments only deal with the proposed algorithm and don't compare the algorithm vs existing algorithms. ", "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": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject