Year: 2018

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.

heading: 1 INTRODUCTION
text: 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 Rd+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 δ ∈ ∆ := Rd. 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 anyQ 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, Gá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.

heading: 2 PRELIMINARIES
text: For any positive integer d, we denote the set {1, . . . , d} by [d]. The natural partial ordering on vectors in Rd is defined as follows: ∀x, x′ ∈ Rd, x ≤ x′ if and only if x[i] ≤ x′[i] for all i ≤ d. Given any two matrices X1 ∈ Rd1×d2 and X2 ∈ Rd ′ 1×d2 , we denote by [X1, X2] ∈ R(d1+d ′ 1)×d2 the matrix that results from concatenating X1 and X2. Similarly, given any two matrices X1 ∈ Rd1×d2×d3 and X2 ∈ Rd ′ 1×d2×d3 , we denote by [X1, X2] ∈ R(d1+d ′ 1)×d2×d3 the matrix that results from concatenating X1 and X2. 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 : Rd → 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 f1 and f2 : Rd → R, the functions fmax (δ) := max{f1(δ), f2(δ)} and fsum(δ) := f1(δ) + f2(δ), for δ ∈ Rd are also PWC. Moreover, for any α ∈ R, αf1 is PWC. If f1 and f2 are NIPWC and α ≥ 0, then fmax , fsum , and αf1 are NIPWC.

heading: 3 SETUP
text: We consider an agent operating in an environment over a finite time horizon T . The state and action spaces are S and A. If the agent takes action at ∈ A at state st ∈ S and time t ≤ T , then the environment returns a (d + 1)-dimensional reward vector rt(st, at) ∈ Rd+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 rt : S × A→ Rd+1. Using rt we define the scalarized reward Rt at time t defined as follows: for any st ∈ S and at ∈ A,
Rt(st, at, δ) := { rt(st, at)[d+ 1], if ∀ i ≤ d, δ[i] ≤ rt(st, at)[i], and, −∞, otherwise. (1)
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=1Rt(st, at, δ)].
For any t ≤ T , we let Qt : S × A ×∆ → R be the optimal Q-function and let Vt : S ×∆ → R be the value function at the tth time step. For a given value of the parameter δ ∈ ∆, Qt(st, at, δ) is the total reward if action at ∈ A is taken at state st ∈ S and the optimal policy is followed till time T . Similarly, Vt(st, δ) is the total reward if the optimal policy was followed from the time step t till time T starting from state st ∈ S. For a terminal state sT ∈ S and action aT ∈ A,
QT (sT , aT , δ) := RT (sT , aT , δ) (2)
is the terminal reward. Similar to Lizotte et al. (2010), we will present a value iteration algorithm which computes the Qt and Vt functions for all possible inputs recursively starting from T and backwards using the Bellman equation: for any δ ∈ ∆, t ≤ T , st ∈ S, and at ∈ A:
Qt(st, at, δ) = Rt(st, at, δ) + Est+1|st,at [Vt+1(st+1, δ)], (3)
where Vt(st, δ) := maxa∈A(Qt(st, a, δ)).
As usual, once we evaluate the Q-functions, we can compute the optimal policy for a given δ ∈ ∆ by applying the action arg maxa∈AQt(st, a, δ) at state st ∈ S and time t ≤ T .

heading: 4 DATA STRUCTURE FOR PARAMETERIZED VALUE FUNCTIONS: DISCRETE STATE SPACE
text: In this section, we consider a discrete state space S and show how to compute Qt and Vt. 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 sT and four actions a1, a2, a3 and a4 with 2-dimensional reward vectors, and hence,
d = 1. These vectors are represented as points in the plane. From this representation, we can get the representation of the scalarized terminal reward function for each of the actions. In Figure 1b, we plot the QT function for each action and VT versus δ ∈ ∆ = R. As noted earlier, QT = RT which is piecewise constant and shown in the thin lines in the figure and VT is a pointwise maximization of such functions and shown in the thick lines. The points corresponding to actions that are optimal for some δ are surrounded by a square. That is why the one corresponding to action a2 is not.

heading: 4.1 DECRECT REPRESENTATION OF NIPWC FUNCTIONS
text: First, observe that for any fixed st ∈ S and at ∈ A, Rt(st, at, ·) is NIPWC of δ ∈ ∆ as it takes the value of rt(st, at)[d + 1] or −∞. It is a positive constant over axis parallel hyperrectangle δ[i] ≤ rt(st, at)[i] for i ≤ d, and −∞ elsewhere. By Equation (2), it follows that QT (sT , aT , ·) has the same properties as RT (sT , aT , ·) (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 Vt and Qt 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 = [x1, . . . , xm]ᵀ, where each row xj , j ≤ m, is a pair in ∆ × R. We call this representation DecRect. The semantics of DecRect is as follows: for any δ ∈ ∆, let Jδ = {j : ∀i ≤ d, δ[i] ≤ X[j][i]}, then
f(δ) := { maxJδ X[j][d+ 1], if |Jδ| 6= 0 −∞, otherwise. (4)
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 QT (sT , a1, ·) of Figure 1b will be: [[0.2, 0.7]], QT (sT , a2, ·) will be[[0.3, 0.4]], QT (sT , a3, ·) will be [[0.5, 0.6]] and QT (sT , a4, ·) will be [[0.8, 0.2]]. VT (sT , ·) 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 a3 is not optimal for any δ. We will discuss the last point more in Section 4.3.

heading: 4.2 MAXIMIZATION OF NIPWC FUNCTIONS
text: In this section, we describe how to maximize two NIPWC functions represented by two DecRects. Assume we are given two functions f1 and f2 : ∆ → R represented by two DecRects X1 and X2. The pointwise maximum fmax of f1 and f2 is represented simply as Xmax = [X1, X2]. This representation is indeed correct because:
fmax (δ) := max{f1(δ), f2(δ)} = max j,h: h∈{1,2} and ∀i≤d, δ[i]≤Xh[j][i] Xh[j][d+ 1] (5)
= max j: ∀i≤d, δ[i]≤Xmax [j][i] Xmax [j][d+ 1], (6)
while equal to −∞ when neither X1 nor X2 has hyperrectangles that contain δ. For any given δ ∈ ∆, fmax (δ) is equal to the maximum of the values of the functions on all hyperrectangles that contain δ and equal to −∞ otherwise. Example. Let X1 = [[0.2, 0.7]] and X2 = [[0.5, 0.6]] as the DecRects for the QT functions for actions a1 and a2 in Figure 1b. Then, Xmax = [[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.

heading: 4.3 COMPUTING NON-DOMINATED ACTIONS (PARETO FRONT)
text: As can be seen in the DecRect of VT 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 ∃j1, j2 ∈ [m] such that X[j1] ≤ X[j2], j1 is said to be dominated by j2. Hence, the maximal set of the m rows is the set of non-dominated rows and are called Pareto front.
Remember that Vt(st, ·) = maxa∈AQt(st, a, ·). That means that the DecRect of Vt is a concatenation of the DecRects of the Qts. 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 Vt, 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 log2m) time for d = 2 and d = 3 and inO(m(log2m)
d−2) for d ≥ 4. Thus, computing the non-dominated rows can be done efficiently. This can be done after each computation of a Vt(st, ·) 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 VT of Figure 1b.

heading: 4.4 WEIGHTED SUM OF NIPWC FUNCTIONS
text: Computing the weighted sum of NIPWC functions with non-negative weights is the essential operation of computing E[Vt(st, ·)]. Given two piecewise constant non-increasing functions f1 and f2 : ∆ → R+ represented by the DecRects X1 and X2 and two non-negative constants α1 and α2, we describe how to compute the function fsum = α1f1 + α2f2 in Algorithm 1.
First, we create an empty DecRect Xsum . Then, for every pair of rows x1 ∈ X1 and x2 ∈ X2, we add a new row xsum to Xsum where for all i ≤ d, xsum [i] = min{x1[i], x2[i]} (line 5) and xsum [d+ 1] = α1x1[d+ 1] + α2x2[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 x1 and x2 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
1: input: X1 ∈ Rm1×(d+1), X2 ∈ Rm2×(d+1), α1, α2 ∈ R+ 2: j3 ← 0 3: for j1 ∈ [m1] do 4: for j2 ∈ [m2] do 5: Xsum [j3][i]← min{X1[j1][i], X2[j2][i]},∀i ∈ [d] 6: Xsum [j3][d+ 1]← α1X1[j1][d+ 1] + α2X2[j2][d+ 1] 7: j3 ← j3 + 1 8: return: Xsum
[−∞, 0.8] with values 0.7 and 0.2, respectively. It also shows the single-row of the resulting DecRect from the weighted sum of the two functions with arbitrary weights α1 and α2 ≥ 0. Its interval [−∞, 0.2] is shown in bold line. Similarly, Figure 2b plots the projected two-single row DecRects x1 and x2 with d = 2 of two functions to the plane ∆ = R2. It shows their rectangles in thin lines. It also shows the projected single row xsum of the weighted summation to ∆ as a point in the plane along with its rectangle which is the intersection of the rectangles and is shown in bold blue lines.

heading: 4.5 COMPLEXITY ANALYSIS FOR THE DISCRETE CASE
text: In this section, we analyze the space and time complexity of the computations done in Section 4. In this section, we assume that the reward vector rt, and consequently the scalarized reward Rt, are independent of time and thus we drop their t subscript.
We basically count the number of rows each of the DecRects of the Qt and Vt has. The Qts and Vts 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 Rd with bottom-left corners at negative infinity is upper bounded by ( m·e d )d . We prove that in Section B of the Appendix. 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 Vt or Qt is upper bounded by |S||A| plus the number of pairwise intersections which is (|S||A|e/d)d. Hence, the space complexity of computing Qt or VT is O(d(|S||A|e/d)d). To compute time complexity, note first that we compute the intersection of two isothetic hyperrectangles with bottom-left corners at negative infinity by computing the minimum of two values in each dimension which requires O(d) time. Vt is the pointwise
maximum of |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 logd2(d(|S||A|e/d)2d ) time. Thus, the time complexity of computing Vt given
the Qts is O ( d|A|(|S||A|e/d)2d logd2(d(|S||A|e/d)2d ) .
Es′|s,a[Vt(s ′, ·)] is a weighted sum of |S| functions each with a DecRect with at most (|S||A| + (|S||A|e/d)d) 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 logd−22 (d(|S||A|e/d)2d)) time and all |S| − 1 steps would take O(d|S|(|S||A|e/d)2d logd−22 (d(|S||A|e/d)2d)) time, for d ≥ 4. For d = 2 and d = 3, the log term has no exponential term. Thus, computingQt which is the addition of a function with a single row and Es′|s,a[Vt(s′, ·)] takes O(d|S|(|S||A|e/d)2d logd−22 (d(|S||A|e/d)2d)) time.
Once the DecRect of a Qt(s, a, ·) is computed, we decompose the hyperrectangles represented by its rows to disjoint hyperrectangles. Then, retrievingQT (s, a, δ) for any δ ∈ ∆ is a matter of finding the enclosing rectangle which takes O(logd−1m) 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 aQt by intersecting a row with all previously generated hyperrectangles while not adding already existing rectangles. Instead, we just update their values. This would take O(d2(|S||A|e/d)4d) time. The total number of rows of the resulting DecRect would beO(d(|S||A|e/d)2d) since every pair of rows in the original DecRect withO((|S||A|e/d)d) rows can generate O(d) rows. Moreover, the data structure of Edelsbrunner & Maurer (1981) takes O(m logdm) space and preprocessing time. Hence, the space and preprocessing time needed is O(d2(|S||A|e/d)2d logd d(|S||A|e/d)2d) and the query time is O(logd−1 d(|S||A|e/d)2d). Therefore, computing Qt−1 from Qt 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.

heading: 5 VALUE FUNCTIONS FOR ALL THRESHOLDS: CONTINUOUS STATE SPACE
text: In this section, we consider the scenario where the state space S is continuous and for any time step t < T , action at ∈ A and state st ∈ S, the probability distribution of the next state st+1 is a Dirac delta function on some state in S. In other words, there is a function gt : S × A → S where st+1 = gt(st, at). In this case, Equation (3) will become:
Qt(st, at, δ) = Rt(st, at, δ) + Vt+1(st+1, δ), (7)
where st+1 = gt(st, at).
We will use linear function approximation in computing the Qt and Vt functions. Formally, for any state s ∈ S, action a ∈ A and index i ∈ [d+1], the reward will be expressed as rt(s, a)[i] = ψᵀsβat [i], where ψ : S → Rc maps a state to an c-dimensional feature vector and βat [i] ∈ Rc 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:
Rt(s, a, δ) =
{ ψᵀsβ a t [d+ 1], if ∀ i ≤ d, δ[i] ≤ ψᵀsβat [i], and
−∞, otherwise. (8)
Moreover, we assume that the transition functions gt satisfy ψst+1 = F at t ψst , where st+1 = gt(st, at), for some F at ∈ Rc×c.
As in Section 4, we first discuss in Section 5.1 the data structure in which we store the Qt and Vt 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 Qt and Vt functions.

heading: 5.1 CONTDECRECT REPRESENTATION OF NIPWC FUNCTIONS
text: DecRect is not suitable for continuous state spaces: we cannot have explicit representations of Qt and Vt for each s ∈ S. Hence, we introduce a new data structure ContDecRect to store the Qt and Vt functions that handles this issue.
ContDecRect is a data structure that can be used to store functions of the form f : Rc×∆→ R that would result from evaluating the Bellman equation, such as Vt(·, ·) and Qt(·, a, ·) for some a ∈ A, while having reward as in Equation (8) and fixing ψ : S → Rc. It is a directed acyclic graph (DAG) with a special structure. For any fixed state s ∈ S and hence fixed vector ψs in Rc, 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 α ∈ Rc 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 := {(n1, n2)}. N consists of two disjoint sets of nodes: N0 of nodes with no incoming edges and N0̄ = N\N0 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 (n1, n2) ∈ E , where n1 and n2 ∈ N , we call n1 a parent of n2 and n2 a child of n1. The level of a node n ∈ N0 is L[n] = 0. The level of an n ∈ N0̄ with parents n1 and n2 is L[n] = 1 + max{L[n1], L[n2]}. Nodes in N0 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 ∈ N0 is characterized by X[n] which is a matrix in R(d+1)×c and its value by the vector Y [n] ∈ Rc. The semantics of this representation is as follows: for any state s ∈ S and threshold vector δ ∈ ∆, the value of the node is:{
ψᵀsY [n], if ∀ i ≤ d, δ[i] ≤ ψᵀsX[n][i], and −∞, otherwise. (9)
The value of a non-root node n3 ∈ N0̄, with a O[n] = max and parents n1 and n2, would be:{ max{ψᵀsY [n1], ψᵀsY [n2]}, if ∀i ≤ d, δ[i] ≤ min{ψᵀsX[n1][i], ψᵀsX[n2][i]}, and −∞, otherwise. (10)
If O[n] = sum , its value would be ψᵀsY [n1] +ψ ᵀ sY [n2] 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], ψᵀsX[n][i] ≤ δ[i]. For each t ≤ T and a ∈ A, we represent Rt(·, a, ·) as a ContDecRect with a single ON node n with X[n][i] = βat [i] for i ≤ d and Y [n][d + 1] = βat [d + 1]. It follows that for all a ∈ A, QT (·, a, ·) have the same representation.

heading: 5.2 SCALING, MAXIMIZATION AND ADDITION OF NIPWC FUNCTIONS
text: Consider two functions f1 and f2 : S ×∆→ R represented by the ContDecRects H1 and H2. We assume that their components are indexed by the same subscripts.
Fix an α ≥ 0, observe that the function αf1 can be represented by the following ContDecRect: 〈N1, E1, X1, αY1,W1, O1, L1〉.
To find the find the pointwise maximum (sum) of f1 and f2, we create a new ContDecRect that combines both ContDecRects:
H3 = 〈N1 ∪N2, E1 ∪ E2, [X1, X2], [Y1, Y2], [W1,W2], [O1, O2], [L1, L2]〉.
Then, for every pair of ON nodes n1 ∈ N1 and n2 ∈ N2, we create a child node n3 with a max (sum) operator and add it to H3. Formally, n3 gets added to N3, (n1, n3) and (n2, n3) gets added to E3, and O3[n3] is set to max (sum) and L3[n3] to 1 + max{L3[n1], L3[n2]}. X3 and Y3 would not get updated since the added node is a non-root one. W3[n3] 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 ∈ N1 ∪ N2 ⊂ N3. 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 following lemma shows the correctness of this method with a proof in Section C of the Appendix. Lemma 1. If for any δ ∈ ∆, each of H1 and H2 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 H3 has that property too. Moreover, H3 would represent the pointwise maximum (sum) of f1 and f2.
5.3 Qt AND Vt COMPUTATION FOR t ≤ T
Recall that we represent theRt(·, a, ·)s, and consequently theQT (·, a, ·)s, with single-node ContDecRects and VT (·, ·) with the ContDecRect that results from iterative application of the maximization procedure described in Section 5.2 over the QT (·, a, ·)s. Our aim is to construct a ContDecRects that represent Qt(·, a, ·)s and Vt(·, ·)s, i.e. given ψst , the hyperrectangles and values of nodes would be specified and given δ ∈ ∆ the value of Qt or Vt would be determined. Recall from Equation (7) that Qt is the sum of Rt and Vt+1. Observe that if we directly apply the addition procedure described in Section 5.2 on the ContDecRects of Rt and Vt+1, we will need to multiply ψst by F a t before applying it to the nodes corresponding to Vt+1 in the new ContDecRect since Vt+1 takes ψst+1 not ψst as input. Instead, we adjust the parameters, specifically X and Y , of the ContDecRect of Vt+1 to account for the multiplication by F at .
The upper-right corner of the hyperrectangle and value of a node n of the ContDecRect of Vt+1 at a state st would be (F at ψst)
ᵀX[n][i] for i ≤ d and (F at ψst)ᵀY [n], respectively. Note that for any vector γ ∈ Rc, (F at ψst)ᵀγ = (γᵀF at )ψ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 Vt+1 by updating the X and Y matrices so that Xnew [n][i] = X[n][i]ᵀF at and Ynew [n] = Y [n]
ᵀF at , for each i ≤ d and root node n corresponding to action a. Using this method, we can get a ContDecRect representation of any Qt.
On the other hand, fortunately, for any t ≤ T , all of the |A| Qt functions take ψst as input, as would Vt. Hence, to get a ContDecRect representation of Vt, one can simply iteratively apply the maximization method of Section 5.2 over the ContDecRects of the |A| Qt functions.

heading: 5.4 COMPLEXITY ANALYSIS FOR THE CONTINUOUS CASE
text: 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 rt and Rt time independent.
We will start by bounding the number of nodes each of the ContDecRects of the Qt(·, a, ·) and Vt(·, ·) 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 Qt(·, a, ·) and Vt(·, ·) cover all states instead of having different data structure
for each state. Second, because we need to update the parameters of the ContDecRect of Vt(·, ·) as we go backward in time.
It follows from the first difference that we have |A| ContDecRects that represent QT for all possible inputs and a single ContDecRect to represent in VT instead of |A||S| DecRects to represent QT and |S| DecRects to represent VT , 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 Qt for t < T introduces a new root node representing a different hyperrectangle than the one that would be added at a different time step.
Still, for any t ≤ T , we can bound the number of root nodes N0 and the total number of nodes N of the ContDecRect of a Qt(·, a, ·) by O(|A||T |−t) and O(|A|2(|T |−t)) and those of Vt(·, ·) by O(|A||T |−t+1) and O(|A|2(|T |−t+1)), respectively. Recall that each QT (·, a, ·) is represented by a single-node ContDecRect and VT (·, ·) by the ContDecRect resulting from applying the maximization procedure in Section 5.2 over these nodes which would lead to |N0| = |A| and |N | = 1 + 2 + · · · + |A| = |A|(|A| + 1)/2 = O(|A|2) nodes. Assume that at t > 1, the ContDecRect of each Qt(·, a, ·) has |N0| = O(|A|T−t) and |N | = O(|A|2(T−t)) and Vt(·, ·) has |N0| = O(|A|T−t+1) and |N | = O(|A|2(T−t+1)). Then, in the construction of the ContDecRect of a Qt−1(·, a, ·), one would multiply all the parameters of the root nodes of Vt by F at−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 Rt−1 and Vt will create a new node for each of the O(|A|2(T−t)) nodes of Vt and thus the total number of nodes will be O(|A|2(T−t)). Moreover, the set of root nodes of the ContDecRect of Vt−1 will consists of all the root nodes of the |A| ContDecRects of theQt−1s and thus its size isO(|A|T−(t−1)+1). Finally, the total number of nodes of Vt−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 Rc and each non-root node stores the identity of its parents, the space complexity of storing a Qt(·, a, ·) is O(cd|A|T−t + |A|2(T−t)) and Vt(·, ·) is O(cd|A|T−t+1 + |A|2(T−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(d2|A|8(T−t)) time. Once that is done, one can use Edelsbrunner & Maurer (1981) algorithm which would take preprocessing time of O(d2|A|4(T−t) logd2 d|A|4(T−t)) and query time of O(logd2 d|A|4(T−t)).

heading: 6 CONCLUSION AND FUTURE WORK
text: 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.

heading: A DECOMPOSITION OF THE DIFFERENCE OF TWO HYPERRECTANGLES TO HYPERRECTANGLES
text: In this section, we provide an algorithm to decompose the complement of a hyperrectangle r1 ∈ ∆ with respect to an intersecting rectangle r2 ∈ ∆ 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.

heading: B BASIC FACTS ABOUT INTERSECTIONS OF AXIS-PARALLEL HYPERRECTANGLES
text: 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 Rd. Lemma 2. Given m axis-parallel hyperrectangles in Rd, 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 .
Algorithm 2 Decomposition to Hyperrectangles Algorithm
1: input: cb,1, cu,1, cb,2, cu,2 ∈ Rd 2: Cb,new , Cu,new ← [] 3: for i ∈ [d] do 4: if cb,2[i] > cb,1[i] and cb,2[i] ≤ cu,1[i] then 5: cb,new [j]← cb,1[j],∀ j 6: cu,new [i]← cb,2[i], 7: cu,new [j]← cu,1[j],∀ j 6= i 8: append cb,new to Cb,new and cu,new to Cu,new 9: cb,1[i]← cb,2[i]
10: if cu,2[i] > cb,1[i] and cu,2[i] < cu,1[i] then 11: cb,new [j]← cb,1[j],∀ j 6= i 12: cb,new [i]← cu,1[i], 13: cu,new [j]← cu,1[j],∀ j 14: append cb,new to Cb,new and cu,new to Cu,new 15: cu,1[i]← cu,2[i] 16: return: Cb,new , Cu,new
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 them hyperrectangles, and consider the intersection with all combinations of them 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 thesem hyperrectangles
is upper bounded by ∑d i=0
( m
i
) . To compute a simple upper bound on this sum, we multiply it
first by ( d m )d to get:
( d m )d d∑ i=0 ( m i ) = d∑ i=0 ( m i )( d m )d ≤ d∑ i=0 ( m i )( d m )i [since dm ≤ 1]
≤ m∑ i=0 ( m i )( d m )i < ∞∑ i=0 ( m i )( d m )i [again since dm ≤ 1 and m <∞]
= ( 1 + d
m )m ≤ ed. Hence, ∑d i=0 ( m
i
) ≤ ( m d )d ed.

heading: C PROOF OF LEMMA 1
text: 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 H1 and H2 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 H3 has that property too. Moreover, H3 would represent the pointwise maximum (sum) of f1 and f2.
Proof. Fix an s ∈ S, then the hyperrectangles and values of the nodes in H1 and H2 are fixed. Now, fix δ ∈ ∆. If there is no n1 ∈ N1 and n2 ∈ N2 with W1[n1] = W2[n2] = ON and with hyperrectangles that contain δ, there will be no n3 ∈ N3 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 n1 ∈ N1 with a hyperrectangle that contain δ but there is no ON n2 ∈ N2 that does, the value of the resulting function would be f1(s, δ), and vice versa. However, if we are finding the pointwise sum in this case, the value of the resulting function would be −∞ since n1 (and n2) would be OFF. This is the right value since either f1(s, δ) or f2(s, δ) would be equal −∞. Finally, if both H1 and H2 have ON nodes that contain δ, let n1 ∈ N1 and n2 ∈ N2 be the unique ON nodes with maximum levels in H1 and H2 with hyperrectangles that contain δ. Then, the hyperrectangle of the added max (sum) node n3 ∈ H3 with parents n1 and n2 will be the unique maximum level ON node that contains δ in H3 and its value will be the maximum (sum) of the values of n1 and n2 which are f1(s, δ) and f2(s, δ).

Review summaries:
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. 

The authors consider RL with safety constraints, which is framed as a multi-reward problem. At a high-level, this involves finding the Pareto front, which optimally trades off objectives. The paper primarily introduces and discusses a discretization scheme and methods to model the Q-value function as a NIPWC (non-increasing piecewise constant function). NIPWC are stored as values over discrete partitions of state-action spaces. To do so, the authors introduce two data structures DecRect and ContDecRect to store Q function values over geometric combinations of subsets of state-action space.