Title: MULTI-OBJECTIVE VALUE ITERATION WITH PARAME-TERIZED THRESHOLD-BASED SAFETY CONSTRAINTS

Abstract: We consider an environment with multiple reward functions. One of them represents goal achievement and the others represent instantaneous safety conditions. We consider a scenario where the safety rewards should always be above some thresholds. The thresholds are parameters with values that differ between users. We efficiently compute a family of policies that cover all threshold-based constraints and maximize the goal achievement reward. We introduce a new parameterized threshold-based scalarization method of the reward vector that encodes our objective. We present novel data structures to store the value functions of the Bellman equation that allow their efficient computation using the value iteration algorithm. We present results for both discrete and continuous state spaces.

1. INTRODUCTION:

In reinforcement learning (RL), we often face scenarios where one objective conflicts with safety constraints. For example, Pineau et al. (2007) ; Rush et al. (2004) ; Zhao et al. (2009) have used RL in controlled trial-based treatment analysis. In each treatment stage a medication is administered after which tests are performed to measure symptoms and side effects, and the objective of the doctor may be to optimize treatment for the symptoms while keeping the side effects below some threshold. Different patients may have different preferred thresholds, and hence, it is necessary to generate a family of treatment plans that covers all preferences. One can think of these preferences as values of parameters for threshold-based safety constraints.

We present a value iteration algorithm to compute optimal policies that satisfy safety constraints. We consider a scenario where the safety constraints are parameterized, and the computed family of policies has to cover all possible parameter values. Specifically, we consider an environment that provides the agent with a reward vector in R d+1 corresponding to d + 1 reward functions after doing an action a at a state s and time t. We consider a discrete and finite action space A and time horizon T . The state space S can be finite or not. Both cases are discussed separately. The aim of the agent is to maximize the sum over time of the (d + 1) st coordinate of the reward vector while making sure the other d coordinates pass their thresholds at each time step. The thresholds are encoded in a vector δ ∈ ∆ := R d . To do that, at each time step, we map the reward vector to a scalar equal to its (d + 1) st coordinate when the thresholds are met and to negative infinity otherwise. Hence, the scalarized reward is parameterized by δ.

We present two data structures DecRect and ContDecRect to store the Q functions of the Bellman equation for discrete and continuous state spaces, respectively. They utilize the structure of the scalarized reward function for any state and action as a constant over an axis-parallel hyperrectangle in ∆ with bottom left corner at [-∞] d and -∞ elsewhere. We are abusing notation here since [-∞] d is not a point. This geometrical perspective to the problem inspires intuitive and efficient algorithms to find the pointwise maximum, sum and non-negative scalar multiplication of such functions. These three operations are the only ones needed in the computations of the Bellman equation. We show that they can be done by computing intersections of hyperrectangles in ∆. Hence, in discrete state spaces, we represent any Q function for a given state and action by a DecRect which is a set of pairs of hyperrectangles in ∆ and values in R. In continuous state spaces, we assume linear dependency of the reward functions on a feature space of the states of dimension c. Then, we represent the Q function for a fixed action as sets of d + 1 vectors that when multiplied by the feature vector of the state, provide a set of hyperrectangles and values from which the value of the function can be inferred. In both discrete and continuous state space cases, the Q function will be non-increasing in each dimension and hence the names DecRect and ContDecRect for decreasing, rectangles and continuous.

Using DecRect, for finite state spaces, we present an algorithm that uses polynomial time and space in |S| and |A|, linear in T and exponential in d, to compute a family of policies that cover all possible values of δ. Moreover, we present an efficient method to identify dominated actions using Pareto front computations. For continuous state spaces, we provide an algorithm that uses ContDecRect and with time and space complexity that is exponential in T and polynomial in |A|, d and c, to compute a similar family of policies.

The paper is inspired by the work: "Efficient Reinforcement Learning with Multiple Reward Functions for Randomized Controlled Trial Analysis" by Lizotte et al. (2010) and its extended version Lizotte et al. (2012) . That work aims to maximize the sum over time of a weighted average of the reward vector components instead of a single component with constraints on the others. They assume finite time horizon T and unknown weights, too. They provided an efficient algorithm, yet exponential in T , to synthesize a set of optimal policies that cover all possible weights for cases with up to three reward functions. For more than three, their time complexity bound becomes doubly exponential. There is rich literature focused on multi-objective RL with constraints. For example, Gábor et al. (1998) present a lexicographical order on value functions of policies represented as pairs of reals while having a constraint on the first component. They provide an algorithm to learn an optimal policy based on that order. There are multiple differences with our formulation: their constraint on the first reward is on the total expected reward of the policy while ours is on multiple immediate (instantaneous) rewards. Second, they synthesize a single policy while we generate a family of policies that covers all possible thresholds ∆. Finally, they consider an infinite time discounted reward scenario, while we consider a bounded time scenario. A nice overview of existing algorithms for multi-objective reinforcement learning can be found in Roijers et al. (2013) .

Our contributions can be summarized as follows:

• A threshold-based scalarization function of the reward vector that encodes the goal achievement objective and the safety constraints. It inspires geometric perspective that allows efficient computation and representation of policies. • Efficient data structures to store the Q and V functions of the Bellman equation for both continuous and discrete state spaces. • Efficient algorithms that construct a family of policies for discrete and continuous state spaces with arbitrary number of features that cover a set of safety preferences encoded as threshold vectors.

We start by defining some notations in Section 2. Then, we formally describe our setup and problem statement in Section 3. Section 4 presents the data structure DecRect and a value iteration algorithm to compute a family of policies for all possible thresholds in the case of discrete state space. After that, Section 5 present similar results for the case of continuous state spaces using the data structure ContDecRect. Finally, we conclude and suggest future work in Section 6.

2. PRELIMINARIES:

For any positive integer d, we denote the set {1, . . . , d} by [d] . The natural partial ordering on vectors in R d is defined as follows: ∀x,

x ∈ R d , x ≤ x if and only if x[i] ≤ x [i] for all i ≤ d. Given any two matrices X 1 ∈ R d1×d2 and X 2 ∈ R d 1 ×d2

, we denote by [X 1 , X 2 ] ∈ R (d1+d 1 )×d2 the matrix that results from concatenating X 1 and X 2 . Similarly, given any two matrices X 1 ∈ R d1×d2×d3 and X 2 ∈ R d 1 ×d2×d3 , we denote by [X 1 , X 2 ] ∈ R (d1+d 1 )×d2×d3 the matrix that results from concatenating X 1 and X 2 . Given a finite set S, we denote the cardinality of S by |S|.

We define a special class of functions and some of its properties. Definition 1. A function f : R d → R said to be piecewise constant function (PWC) if there exists finite number of disjoint axis parallel hyperrectangles, possibly with corners at infinity, over which the value of f is constant . If f is PWC and non-increasing along each dimension, it is said to be non-increasing PWC (NIPWC).

The classes of PWC and NIPWC functions are closed under addition, non-negative scalar multiplication, and pointwise maximization. That is, given PWC functions f 1 and f 2 : R d → R, the functions f max (δ) := max{f 1 (δ), f 2 (δ)} and f sum (δ) := f 1 (δ) + f 2 (δ), for δ ∈ R d are also PWC. Moreover, for any α ∈ R, αf 1 is PWC. If f 1 and f 2 are NIPWC and α ≥ 0, then f max , f sum , and αf 1 are NIPWC.

3. SETUP:

We consider an agent operating in an environment over a finite time horizon 

A policy π for M δ maps a time point and a state to an action, that is, π :

[T ] × S → A.

Problem Statement The aim is to design a family of policies Π := {π : [T ] × S → A} such that for any δ ∈ ∆, we can find a corresponding optimal policy π δ ∈ Π that maximizes E[ T t=1 R t (s t , a t , δ)]. For any t ≤ T , we let Q t : S × A × ∆ → R be the optimal Q-function and let V t : S × ∆ → R be the value function at the t th time step. For a given value of the parameter δ ∈ ∆, Q t (s t , a t , δ) is the total reward if action a t ∈ A is taken at state s t ∈ S and the optimal policy is followed till time T . Similarly, V t (s t , δ) is the total reward if the optimal policy was followed from the time step t till time T starting from state s t ∈ S.

For a terminal state s T ∈ S and action a T ∈ A,

EQUATION

is the terminal reward. Similar to Lizotte et al. ( 2010), we will present a value iteration algorithm which computes the Q t and V t functions for all possible inputs recursively starting from T and backwards using the Bellman equation: for any δ ∈ ∆, t ≤ T , s t ∈ S, and a t ∈ A:

EQUATION

where V t (s t , δ) := max a∈A (Q t (s t , a, δ)).

As usual, once we evaluate the Q-functions, we can compute the optimal policy for a given δ ∈ ∆ by applying the action arg max a∈A Q t (s t , a, δ) at state s t ∈ S and time t ≤ T .

4. DATA STRUCTURE FOR PARAMETERIZED VALUE FUNCTIONS: DISCRETE STATE SPACE:

In this section, we consider a discrete state space S and show how to compute Q t and V t . We start by introducing the data structure DecRect for representing these functions in Section 4.1. This representation is key for improving the efficiency of computing maximization and expectation in Equation ( 3), as we will discuss later in Sections 4.2, 4.3, and 4.4. We use the following example to explain the different concepts in this section.

Example:

We borrow the example shown in Figure 1a from Lizotte et al. (2010) . The MDP consists of a single state s T and four actions a 1 , a 2 , a 3 and a 4 with 2-dimensional reward vectors, and hence, The points corresponding to actions that are optimal for some δ are surrounded by a square. That is why the one corresponding to action a 2 is not.

4.1. DECRECT REPRESENTATION OF NIPWC FUNCTIONS:

First, observe that for any fixed s t ∈ S and a

t ∈ A, R t (s t , a t , •) is NIPWC of δ ∈ ∆ as it takes the value of r t (s t , a t )[d + 1] or -∞. It is a positive constant over axis parallel hyperrectangle δ[i] ≤ r t (s t , a t )[i] for i ≤ d,

and -∞ elsewhere. By Equation (2), it follows that Q T (s T , a T , •) has the same properties as R T (s T , a T , •) (Figure 1b ). For example, the Q-functions in Figure 1b are positive over intervals that start from -∞, they are non-increasing and piecewise constant.

Moreover, observe from Equation (3) that the operations for computing V t and Q t consists of a combination of maximization, non-negative scalar multiplication, and addition of NIPWC functions, which means that these functions are always NIPWC.

We will represent an NIPWC function f : ∆ → R by a set of m > 0 hyperrectangles in ∆ and the corresponding values in R; f (δ) is then defined as the maximum value over all the hyperrectangles that contain δ. Assuming that each hyperrectangle has the bottom-left corner at [-∞] d , it can be represented only by its top-right corner in ∆. Collecting all m vertex-value pairs, we represent f by a matrix:

X = [x 1 , . . . , x m ] ,

where each row x j , j ≤ m, is a pair in ∆ × R. We call this representation DecRect. The semantics of DecRect is as follows: for any δ ∈ ∆, let

EQUATION

To reiterate, each row X[j] is (d + 1)-dimensional; the first d-components represent the upper-right corner of a hyperrectangle, and

X[j][d + 1] is the corresponding value.

Example. The DecRect representation of the NIPWC function Q T (s T , a 1 , •) of Figure 1b will be:

[[0.2, 0.7]], Q T (s T , a 2 , •) will be[[0.3, 0.4]], Q T (s T , a 3 , •) will be [[0.5, 0.6]] and Q T (s T , a 4 , •) will be [[0.8, 0.2]]. V T (s T , •) will be represented as [[0.2, 0.7], [0.3, 0.4], [0.5, 0.6], [0.8, 0.2]] or [[0.2, 0.7], [0.5, 0.6], [0.8, 0.2]]

, as a 3 is not optimal for any δ. We will discuss the last point more in Section 4.3.

4.2. MAXIMIZATION OF NIPWC FUNCTIONS:

In this section, we describe how to maximize two NIPWC functions represented by two DecRects. Assume we are given two functions f 1 and f 2 : ∆ → R represented by two DecRects X 1 and X 2 . The pointwise maximum f max of f 1 and f 2 is represented simply as

X max = [X 1 , X 2 ].

This representation is indeed correct because:

EQUATION

while equal to -∞ when neither X 1 nor X 2 has hyperrectangles that contain δ. For any given δ ∈ ∆, f max (δ) is equal to the maximum of the values of the functions on all hyperrectangles that contain δ and equal to -∞ otherwise.

Example. Let X 1 = [[0.2, 0.7]] and X 2 = [[0.5, 0.6]] as the DecRects for the Q T functions for actions a 1 and a 2 in Figure 1b . Then,

X max = [[0.2, 0.7], [0.5, 0.6]].

The resulting function is equal to 0.7 for δ ≤ 0.2, 0.6 for 0.2 ≤ δ ≤ 0.5 and -∞ elsewhere. Thus, it is the pointwise maximum of the two functions.

4.3. COMPUTING NON-DOMINATED ACTIONS (PARETO FRONT):

As can be seen in the DecRect of V T of the example in Figure 1b shown in Section 4.1, there might be rows that are redundant and can be removed without affecting the function. We call such rows dominated, formally defined as follows:

Definition 2. Given a DecRect X with m rows, if ∃j 1 , j 2 ∈ [m] such that X[j 1 ] ≤ X[j 2 ]

, j 1 is said to be dominated by j 2 . Hence, the maximal set of the m rows is the set of non-dominated rows and are called Pareto front.

Remember that V t (s t , •) = max a∈A Q t (s t , a, •).

That means that the DecRect of V t is a concatenation of the DecRects of the Q t s. Before concatenation, we annotate the rows of each DecRect with the corresponding action. Then, once we merge them all and remove the dominated rows, if an action has no corresponding rows left in the DecRect of V t , we call that action dominated. Identifying such actions which are not optimal for any δ is essential for a lot of applications.

Fortunately, Kung et al. (1975) showed that we can compute the maximal set of m d-dimensional vectors (here the rows of the matrix), with the natural partial ordering, in O(m log 2 m) time for d = 2 and d = 3 and in O(m(log 2 m) d-2 ) for d ≥ 4. Thus, computing the non-dominated rows can be done efficiently. This can be done after each computation of a V t (s t , •) to remove unnecessary rows and identify dominated actions.

Example. Computing the pareto front would remove the row [[0.3, 0.4] ] from the DecRect of V T of Figure 1b .

4.4. WEIGHTED SUM OF NIPWC FUNCTIONS:

Computing the weighted sum of NIPWC functions with non-negative weights is the essential op-

eration of computing E[V t (s t , •)].

Given two piecewise constant non-increasing functions f 1 and f 2 : ∆ → R + represented by the DecRects X 1 and X 2 and two non-negative constants α 1 and α 2 , we describe how to compute the function

f sum = α 1 f 1 + α 2 f 2 in Algorithm 1.

First, we create an empty DecRect X sum . Then, for every pair of rows x 1 ∈ X 1 and x 2 ∈ X 2 , we add a new row x sum to X sum where for all i ≤ d, x sum

[i] = min{x 1 [i], x 2 [i]} (line 5) and x sum [d + 1] = α 1 x 1 [d + 1] + α 2 x 2 [d + 1] (line 6).

Informally, we compute the pairwise intersections of the hyperrectangles from the two functions and assign them a value of the weighted sum of the two corresponding values.

Example. To illustrate the method, we provide two examples: Example 1 is described by Figure 2a and Example 2 by Figure 2b . Figure 2a plots the two single-row DecRects x 1 and x 2 with d = 1 corresponding to two functions as points in the plane and their rectangles (here intervals) in thin lines. ∆ in this example is R and the rectangles of the two rows are the intervals [-∞, 0.2] and Algorithm 1 Weighted Sum of NIPWC Functions Algorithm In this section, we analyze the space and time complexity of the computations done in Section 4.

1: input: X 1 ∈ R m1×(d+1) , X 2 ∈ R m2×(d+1) , α 1 , α 2 ∈ R + 2: j 3 ← 0 3: for j 1 ∈ [m 1 ] do 4: for j 2 ∈ [m 2 ] do 5: X sum [j 3 ][i] ← min{X 1 [j 1 ][i], X 2 [j 2 ][i]}, ∀i ∈ [d] 6: X sum [j 3 ][d + 1] ← α 1 X 1 [j 1 ][d + 1] + α 2 X 2 [j 2 ][d + 1] 7: j 3 ← j 3 + 1 8: return: X sum [-∞,

In this section, we assume that the reward vector r t , and consequently the scalarized reward R t , are independent of time and thus we drop their t subscript.

We basically count the number of rows each of the DecRects of the Q t and V t has. The Q t s and V t s are combinations of weighted summations and maximizations of the set of size |S||A| of functions R(s, a, •) for different s ∈ S and a ∈ A. Note that the number of all possible different intersections of combinations of hyperrectangles from a set of m axis-parallel hyperrectangles in R d with bottom-left corners at negative infinity is upper bounded by Once the DecRect of a Q t (s, a, •) is computed, we decompose the hyperrectangles represented by its rows to disjoint hyperrectangles. Then, retrieving Q T (s, a, δ) for any δ ∈ ∆ is a matter of finding the enclosing rectangle which takes O(log d-1 m) time as shown by Edelsbrunner & Maurer (1981) , where m is the number of rectangles.

From any two rows, we can decompose their hyperrectangles to O(d) disjoint ones in O(d) time while not changing the function. We present the algorithm in Section A of the Appendix. We do that sequentially over the rows in the DecRect of a Q t by intersecting a row with all previously generated hyperrectangles while not adding already existing rectangles. Instead, we just update their values. Therefore, computing Q t-1 from Q t takes polynomial in |A| and |S| and exponential in d time with no dependence on T . This is a significant improvement over the doubly exponential bound presented in Lizotte et al. (2012) for linearly scalarized reward. The key difference that allowed this improvement is that the knots (the points of discontinuity) in their case depended on the values of the added or maximized functions and new different knots may be added at each time step even if the reward does not depend on time.

5. VALUE FUNCTIONS FOR ALL THRESHOLDS: CONTINUOUS STATE SPACE:

In this section, we consider the scenario where the state space S is continuous and for any time step t < T , action a t ∈ A and state s t ∈ S, the probability distribution of the next state s t+1 is a Dirac delta function on some state in S. In other words, there is a function g t : S × A → S where s t+1 = g t (s t , a t ). In this case, Equation (3) will become:

EQUATION

where s t+1 = g t (s t , a t ).

We will use linear function approximation in computing the Q t and V t functions. Formally, for any state s ∈ S, action a ∈ A and index i ∈ [d+1], the reward will be expressed as r t (s, a)

[i] = ψ s β a t [i]

, where ψ : S → R c maps a state to an c-dimensional feature vector and β a t [i] ∈ R c is a weight vector. This is the same choice taken by Lizotte et al. (2012) . This choice assumes separate linear dependence of the reward on the state for each action. We can rewrite Equation (3) to:

EQUATION

Moreover, we assume that the transition functions g t satisfy ψ st+1 = F at t ψ st , where s t+1 = g t (s t , a t ), for some F a t ∈ R c×c .

As in Section 4, we first discuss in Section 5.1 the data structure in which we store the Q t and V t functions. After that, we describe how to find the pointwise scaling, addition and maximization of functions in the new representation in Section 5.2. Finally, in Section 5.3, we discuss how to use the methods of Section 5.2 to compute the Q t and V t functions.

5.1. CONTDECRECT REPRESENTATION OF NIPWC FUNCTIONS:

DecRect is not suitable for continuous state spaces: we cannot have explicit representations of Q t and V t for each s ∈ S. Hence, we introduce a new data structure ContDecRect to store the Q t and V t functions that handles this issue.

ContDecRect is a data structure that can be used to store functions of the form f : R c × ∆ → R that would result from evaluating the Bellman equation, such as V t (•, •) and Q t (•, a, •) for some a ∈ A, while having reward as in Equation ( 8) and fixing ψ : S → R c . It is a directed acyclic graph (DAG) with a special structure. For any fixed state s ∈ S and hence fixed vector ψ s in R c , each node of the graph represents an axis parallel hyperrectangle in ∆, with a bottom-left corner at [-∞] d , and a value in R. The graph consists of several levels. The nodes at level zero have no incoming edges, i.e. no parent nodes, and are called root nodes. Any non-root node has exactly two parent nodes and an operator of max or sum. The level of such a node is one plus the maximum of the levels of its parents. Its hyperrectangle would be the intersection of the hyperrectangles of its parents and its value would be either the maximum of the values of its parents or their sum, depending on its operator. Any node can be ON or OFF. The value of the ContDecRect at certain α ∈ R c and δ ∈ ∆ would be the value of the ON node with the maximum level with a hyperrectangle that contains δ. Equivalently, it is the value of the ON node with the maximum value that contains δ. Such a node will be unique for each δ.

Formally, a ContDecRect H is a tuple: N , E, X, Y, W, O, L , where N is the set of nodes of a DAG with a set of directed edges E := {(n 1 , n 2 )}. N consists of two disjoint sets of nodes: N 0 of nodes with no incoming edges and N0 = N \N 0 of nodes with exactly two incoming edges. Moreover, 

X ∈ R |N0|×(d+1)×c , Y ∈ R |N0|×c , W ∈ {ON, OFF} |N | , O ∈ {max , sum} |N0| and L ∈ N |N | . If (n 1 , n 2 ) ∈ E,

EQUATION

The value of a non-root node n 3 ∈ N0, with a O[n] = max and parents n 1 and n 2 , would be:

EQUATION

) If O[n] = sum, its value would be ψ s Y [n 1 ] + ψ s Y [n 2 ]

under the same conditions of Equation ( 10) and -∞ otherwise. The value of the function would be the value of the unique ON node n with the maximum level with a hyperrectangle that contains δ, i.e. for all i ∈

[d + 1], ψ s X[n][i] ≤ δ[i].

For each t ≤ T and a ∈ A, we represent R t (•, a, •) as a ContDecRect with a single ON node n with

X[n][i] = β a t [i] for i ≤ d and Y [n][d + 1] = β a t [d + 1]. It follows that for all a ∈ A, Q T (•, a, •) have the same representation.

5.2. SCALING, MAXIMIZATION AND ADDITION OF NIPWC FUNCTIONS:

Consider two functions f 1 and f 2 : S × ∆ → R represented by the ContDecRects H 1 and H 2 . We assume that their components are indexed by the same subscripts.

Fix an α ≥ 0, observe that the function αf 1 can be represented by the following ContDecRect:

N 1 , E 1 , X 1 , αY 1 , W 1 , O 1 , L 1 .

To find the find the pointwise maximum (sum) of f 1 and f 2 , we create a new ContDecRect that combines both ContDecRects:

H 3 = N 1 ∪ N 2 , E 1 ∪ E 2 , [X 1 , X 2 ], [Y 1 , Y 2 ], [W 1 , W 2 ], [O 1 , O 2 ], [L 1 , L 2 ] .

Then, for every pair of ON nodes n 1 ∈ N 1 and n 2 ∈ N 2 , we create a child node n 3 with a max (sum) operator and add it to H 3 . Formally, n 3 gets added to N 3 , (n 1 , n 3 ) and (n 2 , n 3 ) gets added to E 3 , and

O 3 [n 3 ] is set to max (sum) and L 3 [n 3 ] to 1 + max{L 3 [n 1 ], L 3 [n 2 ]}.

X 3 and Y 3 would not get updated since the added node is a non-root one. W 3 [n 3 ] would be set to ON.

Added nodes represent the intersections of pairs of hyperrectangles from the two functions being maximized (added) and their values are the maximum (sum) of the values of the intersected hyperrectangles. Moreover, their level will be higher than the levels of their parents.

If we are finding the sum of the functions, W [n] would be set to OFF for all n ∈ N 1 ∪ N 2 ⊂ N 3 . That is because only the intersections of the hyperrectangles should have the value of the sum, δs that do not belong to an intersection, at least one of the functions being added is equal to -∞ which means that the sum is also -∞.

The lemma shows the correctness of this method with a proof in Section C of the Appendix. Lemma 1. If for any δ ∈ ∆, each of H 1 and H 2 has either an ON node that contains δ with a level that is strictly higher than all other ON nodes that contain δ or does not have an ON nodes that contain δ, then the constructed H 3 has that property too. Moreover, H 3 would represent the pointwise maximum (sum) of f 1 and f 2 .

5.3 Q t AND V t COMPUTATION FOR t ≤ T

Recall that we represent the R t (•, a, •)s, and consequently the Q T (•, a, •)s, with single-node ContDe-cRects and V T (•, •) with the ContDecRect that results from iterative application of the maximization procedure described in Section 5.2 over the Q T (•, a, •)s. Our aim is to construct a ContDecRects that represent Q t (•, a, •)s and V t (•, •)s, i.e. given ψ st , the hyperrectangles and values of nodes would be specified and given δ ∈ ∆ the value of Q t or V t would be determined.

Recall from Equation (7) that Q t is the sum of R t and V t+1 . Observe that if we directly apply the addition procedure described in Section 5.2 on the ContDecRects of R t and V t+1 , we will need to multiply ψ st by F a t before applying it to the nodes corresponding to V t+1 in the new ContDecRect since V t+1 takes ψ st+1 not ψ st as input. Instead, we adjust the parameters, specifically X and Y , of the ContDecRect of V t+1 to account for the multiplication by F a t . The upper-right corner of the hyperrectangle and value of a node n of the ContDecRect of V t+1 at a state s t would be (F a t ψ st ) X[n][i] for i ≤ d and (F a t ψ st ) Y [n], respectively. Note that for any vector γ ∈ R c , (F a t ψ st ) γ = (γ F a t )ψ st , since the left hand side is a scalar and thus equal to its transpose. Hence, we update the parameters of the ContDecRect H of V t+1 by updating the X and Y matrices so that

X new [n][i] = X[n][i] F a t and Y new [n] = Y [n] F a t ,

for each i ≤ d and root node n corresponding to action a. Using this method, we can get a ContDecRect representation of any Q t .

On the other hand, fortunately, for any t ≤ T , all of the |A| Q t functions take ψ st as input, as would V t . Hence, to get a ContDecRect representation of V t , one can simply iteratively apply the maximization method of Section 5.2 over the ContDecRects of the |A| Q t functions.

5.4. COMPLEXITY ANALYSIS FOR THE CONTINUOUS CASE:

In this section, we analyze the space and time complexity of the computations done in Sections 5.2 and 5.3. As in Section 4.5, we assume that the reward vector r t and R t time independent.

We will start by bounding the number of nodes each of the ContDecRects of the Q t (•, a, •) and V t (•, •) functions has for each t ≤ T and a ∈ A. It is similar to bounding the number of rows of DecRects in Section 5.2.

There are two differences from the complexity analysis in Section 4.5: First, the ContDecRects corresponding to a Q t (•, a, •) and V t (•, •) cover all states instead of having different data structure for each state. Second, because we need to update the parameters of the ContDecRect of V t (•, •) as we go backward in time.

It follows from the first difference that we have |A| ContDecRects that represent Q T for all possible inputs and a single ContDecRect to represent in V T instead of |A||S| DecRects to represent Q T and |S| DecRects to represent V T , in the discrete case. However, it follows from the second difference that even though the rewards are time-independent, the addition of the reward in the computation of Q t for t < T introduces a new root node representing a different hyperrectangle than the one that would be added at a different time step. -t+1) ). Then, in the construction of the ContDecRect of a Q t-1 (•, a, •), one would multiply all the parameters of the root nodes of V t by F a t-1 and consider them as the root nodes in addition to the one node of R(•, a, •). Thus, it will have O(|A| T -(t-1) ) root nodes. Moreover, the addition procedure of R t-1 and V t will create a new node for each of the O(|A| 2(T -t) ) nodes of V t and thus the total number of nodes will be O(|A| 2(T -t) ). Moreover, the set of root nodes of the ContDecRect of V t-1 will consists of all the root nodes of the |A| ContDe-cRects of the Q t-1 s and thus its size is O(|A| T -(t-1)+1 ). Finally, the total number of nodes of

= 1 + 2 + • • • + |A| = |A|(|A| + 1)/2 = O(|A| 2 ) nodes. Assume that at t > 1, the ContDecRect of each Q t (•, a, •) has |N 0 | = O(|A| T -t ) and |N | = O(|A| 2(T -t) ) and V t (•, •) has |N 0 | = O(|A| T -t+1 ) and |N | = O(|A| 2(T

V t-1 will be O(|A| 2(T -t) )(1 + 2 + • • • + |A|) = O(|A| 2(T -(t-1)) ).

Since each of the root nodes store d + 1 vectors in R c and each non-root node stores the identity of its parents, the space complexity of storing a Q -t+1) ). Moreover time complexity of constructing them is linear in their size, so we have the time complexity the same as the space one. The time complexity of retrieving the value of such functions for a given state s ∈ S and δ ∈ ∆ is also linear in the size since in the worst case every node should be checked if it contains the δ before reaching the one with the maximum level. However, for a fixed state, all hyperrectangles and values of the nodes would be fixed, which means as in Section 4.5, one can decompose the O(|A| 2(T -t) ) rectangles to O(d|A| 4(T -t) ) disjoint regions. Here, the structure of intersections is explicit: a node hyperrectangle is the intersection of its parents hyperrectangles. One can start from the maximum level assigning the hyperrectangles covered by the ON nodes by the values and removing them from ∆, then decomposing the rest of their parents' hyperrectangles to disjoint hyperrectangles. Then, repeat the process iteratively till the roots. This would take O(d 2 |A| 8(T -t) ) time. Once that is done, one can use Edelsbrunner & Maurer (1981) 

t (•, a, •) is O(cd|A| T -t + |A| 2(T -t) ) and V t (•, •) is O(cd|A| T -t+1 + |A| 2(T

6. CONCLUSION AND FUTURE WORK:

We presented a nonlinear reward scalarization function that encodes constraint and goal based specifications. Moreover, we presented data structures that store the Q and value functions that allowed efficient computations of the iterations of the Bellman equation. We presented efficient algorithms to compute a family of policies that cover all preferences. We plan to design an algorithm for learning policies using linear regression over the parameters of the ContDecRects in cases where the transition and reward functions are unknown. Moreover, we plan to design an algorithm to determine dominated actions in the case of continuous state spaces. Finally, we would apply the algorithms to a real life case study.

A DECOMPOSITION OF THE DIFFERENCE OF TWO HYPERRECTANGLES TO

HYPERRECTANGLES:

In this section, we provide an algorithm to decompose the complement of a hyperrectangle r 1 ∈ ∆ with respect to an intersecting rectangle r 2 ∈ ∆ to O(d) hyperrectangles. The method iterates over the dimensions adding a maximum of two hyperrectangles at each one. It is described in the Algorithm 2.

B BASIC FACTS ABOUT INTERSECTIONS OF AXIS-PARALLEL:



The following lemma bounds the number of different hyperrectangles that may result from the intersection of any combination of m hyperrectangles with bottom left corners at negative infinity in R Algorithm 2 Decomposition to Hyperrectangles Algorithm Proof. Since the hyperrectangles are d dimensional with bottom left corner at -∞, the intersection of any number of them is equal to the intersection of at most d of them. A hyperrectangle part of the combination being intersected has to be the minimum in one of the d dimensions to be effecting the intersection. Hence, to generate all possible intersections, one can start by considering one of the m hyperrectangles, and consider the intersection with all combinations of the m hyperrectangles in which it has the minimal upper right coordinate in each dimension. All would have it as the intersection. Then, repeat that for all of the m rectangles. After that, consider any pair of the m hyperrectangles and take their intersection, and then consider all combinations of the m hyperrectangles that would not effect the intersection. Repeat that for all pairs of hyperrectangles. One can continue this process up to considering the intersections of all possible tuples of d hyperrectangles. Hence, the number of possible different intersections of any combination of these m hyperrectangles is upper bounded by C PROOF OF LEMMA 1

1: input: c b,1 , c u,1 , c b,2 , c u,2 ∈ R d 2: C b,new , C u,new ← [] 3: for i ∈ [d] do 4: if c b,2 [i] > c b,1 [i] and c b,2 [i] ≤ c u,1 [i] then 5: c b,new [j] ← c b,1 [j], ∀ j 6: c u,new [i] ← c b,2 [i], 7: c u,new [j] ← c u,1 [j], ∀ j = i

In this section, we provide a proof for Lemma 1 which shows the correctness of the methods used in Section 4.2 to find the pointwise maximum and sum of two ContDecRects. We restate the lemma here for completeness.

Lemma 1. If for any δ ∈ ∆, each of H 1 and H 2 has either an ON node that contains δ with a level that is strictly higher than all other ON nodes that contain δ or does not have an ON nodes that contain δ, then the constructed H 3 has that property too. Moreover, H 3 would represent the pointwise maximum (sum) of f 1 and f 2 .

Proof. Fix an s ∈ S, then the hyperrectangles and values of the nodes in H 1 and H 2 are fixed. Now, fix δ ∈ ∆. If there is no n 1 ∈ N 1 and n 2 ∈ N 2 with W 1 [n 1 ] = W 2 [n 2 ] = ON and with hyperrectangles that contain δ, there will be no n 3 ∈ N 3 that contains δ and the value of the function will be -∞. If we are finding the pointwise maximum of the functions and there is an ON n 1 ∈ N 1 with a hyperrectangle that contain δ but there is no ON n 2 ∈ N 2 that does, the value of the resulting function would be f 1 (s, δ), and vice versa. However, if we are finding the pointwise sum in this case, the value of the resulting function would be -∞ since n 1 (and n 2 ) would be OFF. This is the right value since either f 1 (s, δ) or f 2 (s, δ) would be equal -∞. Finally, if both H 1 and H 2 have ON nodes that contain δ, let n 1 ∈ N 1 and n 2 ∈ N 2 be the unique ON nodes with maximum levels in H 1 and H 2 with hyperrectangles that contain δ. Then, the hyperrectangle of the added max (sum) node n 3 ∈ H 3 with parents n 1 and n 2 will be the unique maximum level ON node that contains δ in H 3 and its value will be the maximum (sum) of the values of n 1 and n 2 which are f 1 (s, δ) and f 2 (s, δ).

:



Figures and Tables:

Figure 1: Example with four actions with the corresponding reward vectors, Q T and V T

Figure 2: Weighted summation of two NIPWC functions

) rows. We need to multiply the last entry of each row of each DecRect by a constant. That would take O(|S|(|S||A|e/d) d ) time. We then need to add these functions which we do sequentially, adding one function at a time and then compute the Pareto front to remove the dominated rows. Hence, each step would take O(d(|S||A|e/d) 2d log d-2 2 (d(|S||A|e/d) 2d )) time and all |S| -1 steps would take O(d|S|(|S||A|e/d) 2d log d-2 2 (d(|S||A|e/d) 2d )) time, for d ≥ 4. For d = 2 and d = 3, the log term has no exponential term. Thus, computing Q t which is the addition of a function with a single row and E s |s,a [V t (s , •)] takes O(d|S|(|S||A|e/d) 2d log d-2 2 (d(|S||A|e/d) 2d )) time.

This would take O(d 2 (|S||A|e/d) 4d ) time. The total number of rows of the resulting DecRect would be O(d(|S||A|e/d) 2d ) since every pair of rows in the original DecRect with O((|S||A|e/d) d ) rows can generate O(d) rows. Moreover, the data structure of Edelsbrunner & Maurer (1981) takes O(m log d m) space and preprocessing time. Hence, the space and preprocessing time needed is O(d 2 (|S||A|e/d) 2d log d d(|S||A|e/d) 2d ) and the query time is O(log d-1 d(|S||A|e/d) 2d ).

where n 1 and n 2 ∈ N , we call n 1 a parent of n 2 and n 2 a child of n 1 . The level of a node n ∈ N 0 is L[n] = 0. The level of an n ∈ N0 with parents n 1 and n 2 is L[n] = 1 + max{L[n 1 ], L[n 2 ]}.Nodes in N 0 are called root nodes. For any node n ∈ N0, its operator O[n] can be max or sum. W stores the state of each node if it is ON or OFF. The hyperrectangle of a node n ∈ N 0 is characterized by X[n] which is a matrix in R (d+1)×c and its value by the vector Y [n] ∈ R c . The semantics of this representation is as follows: for any state s ∈ S and threshold vector δ ∈ ∆, the value of the node is:

Still, for any t ≤ T , we can bound the number of root nodes N 0 and the total number of nodes N of the ContDecRect of aQ t (•, a, •) by O(|A| |T |-t ) and O(|A| 2(|T |-t )) and those of V t (•, •) by O(|A| |T |-t+1 ) and O(|A| 2(|T |-t+1) ), respectively. Recall that each Q T (•, a, •)is represented by a single-node ContDecRect and V T (•, •) by the ContDecRect resulting from applying the maximization procedure in Section 5.2 over these nodes which would lead to |N 0 | = |A| and |N |

d . Lemma 2. Given m axis-parallel hyperrectangles in R d , where d ≤ m, with bottom-left corners at [-∞] d . The number of different intersections of any combination of hyperrectangles from the m hyperrectangles is upper bounded by m•e d d .

,new to C b,new and c u,new to C u,new 9:c b,1 [i] ← c b,2 [i] 10: if c u,2 [i] > c b,1 [i] and c u,2 [i] < c u,1 [i] then 11: c b,new [j] ← c b,1 [j], ∀ j = i 12: c b,new [i] ← c u,1 [i], 13: c u,new [j] ← c u,1 [j], ∀ j 14: append c b,new to C b,new and c u,new to C u,new 15: c u,1 [i] ← c u,2 [i] 16: return: C b,new , C u,new

T . The state and action spaces are S and A. If the agent takes action a t ∈ A at state s t ∈ S and time t ≤ T , then the environment returns a (d + 1)-dimensional reward vector r t (s t , a t ) ∈ R d+1 . The first d components of the reward are used to specify safety constraints and the (d + 1) st component corresponds to achievement of a goal. For a parameter δ ∈ ∆, our aim is to maximize the sum of the last component of the reward over the time horizon while keeping the other d components above their correspondent thresholds specified by δ. Our objective is to design a parameterized policy π δ that solves the problem for any constant δ ∈ ∆.Formally, we consider a Markov Decision Process (MDP) M δ parameterized by δ ∈ ∆ with state space S, finite action space A, state transition matrix P and a reward function r t : S × A → R d+1 . Using r t we define the scalarized reward R t at time t defined as follows: for any s t ∈ S and a t ∈ A,

Table content: <table><tr><td>R t (s t , a t , δ) :=</td><td>r t (s t , a t )[d + 1], if ∀ i ≤ d, δ[i] ≤ r t (s t , a t )[i], and, -∞, otherwise.</td></tr></table>

Recall from Sections 4.2 and 4.4 that the summations and maximizations are done by adding the intersections of the set of hyperrectangles of the R(s, a, •) to the DecRect under construction. Moreover, recall that the Pareto front computation in Section 4.3 removes any row representing a hyperrectangle that is equal or included in another hyperrectangle of a row with higher value. Hence, there are no rows with the same hyperrectangle in any given DecRect. Therefore, the maximum possible number of rows of a DecRect of a V |A| functions each with a DecRect with at most (|S||A| + (|S||A|e/d) d ) rows. This can be done sequentially in |A| -1 steps, one function at a time. At each step computing the pairwise intersections would take O d(|S||A|e/d) 2d time and computing the Pareto front would take O d(|S||A|e/d) 2d log d 2 (d(|S||A|e/d) 2d time. Thus, the time complexity of computing V t given the Q t s is O d|A|(|S||A|e/d) 2d log d 2 (d(|S||A|e/d) 2d . E s |s,a [V t (s , •)] is a weighted sum of |S| functions each with a DecRect with at most (|S||A| + (|S||A|e/d) d

Table content: <table><tr><td>of the Appendix.</td><td>m•e d</td><td>d . We prove that in Section B</td></tr></table>

algorithm which would take preprocessing time of O(d 2 |A| 4(T -t) log d 2 d|A| 4(T -t) ) and query time of O(log d 2 d|A| 4(T-t) ).

Table content: <table/>

Peer review (iclr2019):
 I generally like the paper. The paper discussed a constrained value iteration setting where the safety contraints must be greater some threshold, and thresholds .delta are parameters. The paper attempts to develop an value iteration algorithm to compute a class of optimal polices with such a parameter. The algorithm is mainly based on a special design of representation/data structure of PWC function, which can be used to store value functions and allows to efficiently compute several relevant operations in bellman equation. A graph-based data structure is developed for continuous state domains and hence value iteration can be extended to such cases. In general, the paper presents an interesting direction which can potentially help solve RL problems with the proposed constraint setting. However, the paper spends lots of effort explaining representations, but only a few sentences explaining about how the proposed representations/data structures can help find a somehow generic value iteration solution, which allows to efficiently compute/retrieve a particular solution once a .delta vector is specified. The paper should show in detail (or at least give some intuitive explanations) that using the proposed method can be more efficient than solving a value iteration for each individual constraint given that the constraints are independent. Specifically, the author uses the patient case to motivate the paper, saying that different patients may have different preferred thresholds and it is good to find class of policies so that any one of those policies can be retrieved once a threshold is specified. However, in this case, when dealing with only one patient, the dimension of reward is reduced to 1 (d = 1), while the computation of the algorithm is exponential in d, plus that the retrieval time is not intuitive to be better, so it is unsure whether computing such a class of policies worth. In terms of novelty, the scalarization method of the vector-valued reward seems intuitive, since breaking a constraint means a infeasible solution. Furthermore, it is also unclear why the representation of PWC in discrete case is novel. A partial order on a high-dimensional space is naturally to be based on dominance relation, as a result, it seems natural to store value function by using right-top coordinates of a (hyper)rectangle. As for the clarity, though the author made the effort to explain clearly by using examples after almost every definition/notation, some important explanations are missing. I would think the really interesting things are the operations based on those representations. For example, the part of computing summation of two PWC function representation is not justified. Why the summation can be calculated in that way? Though the maximum operation is intuitive, however, the summation should have some justification. I think a better way to explain those things is to redefine a new bellman operator, which can operate on those defined representations of PWC function. I think it could be a nice work if the author can improve the motivation and presentation. Experiments on some simple domains can be also helpful.