A Reduction Approach to Constrained Reinforcement Learning
Authors: Tianchi Cai
Wenjie Shi
Lihong Gu
Xiaodong Zeng
Jinjie Gu
Venue:  (2021)

Abstract: Many applications of reinforcement learning (RL) optimize a long-term reward subject to risk, safety, budget, diversity or other constraints. Though constrained RL problem has been studied to incorporate various constraints, existing methods either tie to specific families of RL algorithms or require storing infinitely many individual policies found by an RL oracle to approach a feasible solution. In this paper, we present a novel reduction approach for constrained RL problem that ensures convergence when using any off-the-shelf RL algorithm to construct an RL oracle yet requires storing at most constantly many policies. The key idea is to reduce the constrained RL problem to a distance minimization problem, and a novel variant of Frank-Wolfe algorithm is proposed for this task. Throughout the learning process, our method maintains at most constantly many individual policies, where the constant is shown to be worst-case optimal to ensure convergence of any RL oracle. Our method comes with rigorous convergence and complexity analysis, and does not introduce any extra hyper-parameter. Experiments on a grid-world navigation task demonstrate the efficiency of our method.


Under review as a conference paper at ICLR 2021
A REDUCTION APPROACH TO CONSTRAINED REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Many applications of reinforcement learning (RL) optimize a long-term reward subject to risk, safety, budget, diversity or other constraints. Though constrained RL. problem has been studied to incorporate various constraints, existing methods either tie to specific families of RI. algorithms or require storing infinitely many individual policies found by an RL oracle to approach feasible solution. In this paper, we present a novel reduction approach for constrained RL problem that ensures convergence when using any off-the-shelf RL algorithm construct RL oracle yet requires storing at most constantly many policies. The key idea is reduce the constrained RL problem to distance minimization problem, and novel variant of Frank- Wolfe algorithm is proposed for this task. Throughout the learning process, our method maintains most constantly many individual poli- cies, where the constant is shown to be worst-case optimal to ensure convergence of any RL oracle. Our method comes with rigorous convergence and complex- ity analysis, and does not introduce any extra hyyer-parameter Experiments on a grid-world navigation task demonstrate the efficiency of our method.
INTRODUCTION
Contemporary approaches in reinforcement learning (RL) largely focus on optimizing the behavior of an agent against a single reward function. RL algorithms like value function methods (Zou al. 2019; [Zheng et al.] (018)) or policy optimization methods (Chen et al.] 2019: Zhao et al., 2017 are widely used in real-world tasks. This can be sufficient for simple tasks. However, for complicated applications, designing a reward function that implicitly defines the desired behavior can be challenging. For instance, applications concerning risk (Geibel & Wysotzki] [005]] Chow & Ghavamzadeh 2014; Chow et al.) (017)) safety (Chow et al. 2018) or budget (Boutilier & Lu 2016 Xiao et al. 2019) are naturally modelled by augmenting the RL problem with orthant constraints. Exploration suggestions, such as to visit all states as evenly as possible, can be modelled by using a vector to measure the behavior of the agent, and to find policy whose measurement vector lies in convex set (Miryoosefi et al. 2019).
To solve RL problem under constraints, existing methods either ensure convergence only spe- cific family of RI. algorithms, or treat the underlying RI. algorithms as a black box oracle to find in- dividual policy, and look for mixed policy that randomizes among these individual policies. Though the second group of methods has the advantage of working with arbitrary RL algorithms that best suit the underlying problem, existing methods have practically infeasible memory requirement. To get an e-approximate solution, they require storing O(1/c) individual policies, and an exact solu- tion requires storing infinitely many policies. This limits the prevalence of such methods, especially when the individual policy uses deep neural networks.
In this paper, we propose a novel reduction approach for the general convex constrained RL (C2RL) problem. Our approach has the advantage of the second group of methods, yet requires storing at most constantly many policies, For a vector-valued Markov Decision Process (MDP) and any given target convex set, our method finds mixed policy whose measurement vector lies in the target convex set, using any off-tff-shelf RL algorithm that optimizes a scalar reward as RL oracle. To do so, the C2RL problem is reduced to distance minimization problem between polytope and a convex set, and a novel variant Frank- Wolfe type algorithm is proposed to solve this distance minimization problem. To find e-approximate solution in an m-dimenssonal vector-values MDP,

---

Under review as a conference paper at ICLR 2021
Table 1: Comparison with previous approaches. To find an e-approximate solution, time complexity under orthant or convex constraints compared using the numbers of RL oracle calls. The memory requirement is measured by the number of individual policies stored for an e-approximate solution.
Converge for any RL algo.
No extra
Orthant constraint
Convex constraint
Memory requirement
Method
hyper- parameter
Tessler et al. 2018)
To a fixed point
x
x
X
Le al.
0(1/e) ( ((1/e)
X
V
0(1/e)
Miryoosel et al. (0199)
O(1/e)
/
X
O(1/e)
C2RL (this paper)
O(1/e)
/
S +1
our method only stores at most m + 1 policies, which improves from infinitely many O(1/e) (e et al., 2019 Miryoosefi et al.) 2019) to constant. We also show this + constant is worst- case optimal to ensure convergence of RL algorithms using deterministic policies. Moreover, our method introduces no extra hyper-parameter, which is favorable for practical usage. A preliminary experimental comparison demonstrates the performance of the proposed method and the sparsity of the policy found.
2 RELATED WORK
For high dimensional constrained RL, one line of approaches incorporates the constraint as penalty signal into the reward function, and makes updates in a multiple time-scale scheme (Tessler et al.) 2018 Chow & Ghavamzadeh] 2014). When used with policy gradient or actor-critic algorithms Suttonn & Barto 2018), this penalty signal guides the policy to converge to a constraint satisfying one (Paternain et al. 2019 Chow et al. 2017). However, the convergence guarantee requires the RL algorithm can find a single policy that satisfies the constraint, hence ruling out methods that search for deterministic policies, such as Deep --Neworrks (DQN) (Mnih et al. (0133), Deep Deterministic Policy Gradient (DDPG) (Lillicrap et al. 2015) and their variants (Van Hasselt et al. 2015 Wang
al. 2016 Fujimoto et al. 2018 Barth-Maron et al. 2018).
Another line of approaches uses a game-theoretic framework, and does not tie to specific families of RL algorithm. The constrained problem is relaxed to a zero-sum game, whose equilibrium is solved by online learning (Agarwal et al.) (018). The game is played repeatedly, each time any RL algorithm can be used find best response policy to play against no-regret online learner. The mixed policy that uniformly distributed among all played policies can be shown to converge to an optimal policy of the constrained problem (Freund Schapire 1999 Aberrnehyy et al.) [01T]) Taking this approach. Le et al. (219)) uses Lagrangian relaxation to solve the orthant constraint case, and Miryoosefi et al. (0119) uses conic duality to solve the convex constraint case. However, since the convergence is established by the no-regret property, the policy found by these methods requires randomization among policies found during the learning process, which limits their prevalence.
Different from the game-theoretic approaches, reduce the C2RL to a distance minimization prob- lem and propose a novel variant of Frank- Wolfe (FW) algorithm to solve it. Our result builds on recent finding that the standard FW algorithm emerges as computing the equilibrium of special convex-convave zero sum game (Abernethy & Wang 2017). This connects our approach with pre- vious approaches from game-theoretic framework (Agarwal al. 2018 Le al., 2019; Miryoosefi et al. 2019). The main advantage of our reduction approach is that the convergence of FW algorithm does not rely on the no-regret property of an ouline learner. Hence there no need to introduce extra hyper- prper-parameter, such as learning rate of the online learner, and intuitively, we can eliminate un- necessary policies to achieve better sparsity. To do so, we extend Wolfe's 's method for minimum norm point problem (Wolfe 1976) to solve our distance minimization problem. Throughout the learning process, we maintain an active policy set, and constantly eliminate policies whose measurement vector are affinely dependent of others. Unlike norm function in Wolfe's method, our objective function is not strongly convex. Hence we cannot achieve the linear convergence of Wolfe's 's method as shown in Lacoste-Jullee Julien & Jaggi (2015). Instead, analyze the complexity of our method based on techniques from Chakrabarty et al. (2014). A theoretical comparison between our method and various approaches in constrained RL is provided in Table
2

---

Under review as a conference paper at ICLR 2021
3 PRELIMINARIES
vector-valued Markov decision process can be identified by a tuple AS, c}. where S is a set of states, A is the set of actions and / is the initial state distribution. At the start of each episode, an initial state So is drawn following the distribution B. Then, at each step t = 0, l,... the agent observes state 8; E S and makes decision take action d, After d, is chosen, at the next observation the state evolves to state 8t41 E S with probability P(s [8,, a²). However, instead of a scalar reward, in our setting, the agent receives an m-dimennional vector e₁ RT that may implicitly contain measurements of reward, risk or violation of other constraints. The episode ends after a certain number of steps, called the horizon, or when a terminate state is reached.
Actions are typically selected according to policy т, where (s) is a distribution over actions for any s E S. Policies that take a single action for any state are deterministic policies, and can be identified by the mapping π S + A. The set of all deterministic policies is denoted by II. For discount factor y E [0, 1). the discounted long-term measurement vector of a policy defined as
II is
<xx) E y (',(s),
where the expectation over trajectories generated by the described random process.
Unlike unconstrained setting, for a constrained RL problem, it is possible that all feasible policies non-deterministic (see Appendix for example). This limits the usage of RL algorithms that search for deterministic policies in the setting of constrained RL problem.
One workaround is use mixed policies. For over U, and the set of all mixed policies over U is denoted by A24). To execute a mixed policy j E (2)). we first select policy E U according entire episode. [Altman (1999) shows that any c(-) achievable can be achieved by some mixed deterministic polictes μ E AII.. Therefore. though an off-shelves RL algorithm may not converge to any constraint -tatraiin-satisfyinn policy, it can be used as subroutine to find individual policies (possibly deterministic), and a randomization among these policies can converge to a feasible policy. The discounted long-term measurement vector of mixed policy μ A(II) is defined similarly
of policies U, mixed policy is a distribution
π μ(T)). and then execute for the
e(pa == (E<(((((T))
Σ [((T)C(T). wEll
(2)
For mixed policy μ E A(U), its active set is defined to be the set of policies with non-zero weights A = { E ([)(()) > 0}. The memory requirement of storing μ. is then proportional to the size of its active set. Since mixed policy can be interpreted convex combination of policies in its active set, in the following, the term sparsity mixed policy refers to the sparsity of this combination.
Our learning problem, the convex constrained reinforcement learning (C2RL), is to find policy whose expected long-term measurement vector lies in a given convex set; i.e., for given convex target set C C R,," target is to
find μ² such that c(p²) EQ
(C2RL).
Any policy 2² that satisfies c(l²*) E Q is called a feasible policy, and a C2RL problem is feasible there exists some feasible policies. In the following, assume the C2RL problem is feasible.
4 APPROACH, ALGORITHM AND ANALYSIS
can be reduced to a distance minimization problem 7 between polytope and convex set. novel variant of Trank-Wolfe-ee algorithm then proposed solve the distance minimization problem, followed by theoretic analysis about convergence and sparsity of the proposed method.
We now show how the C2RL 3
4.1 REDUCE C2RL TO DISTANCE MINIMIZATION PROBLEM
Let ||-|| denote the Euclidean norm. For convex set l E R. let Projg(x) E arg min ||æ--/] yll be the projection operator, and d (ar, ?) = || paa--rojggtee ( be half of the squared Fuclidean
3

---

Under review as a conference paper at ICLR 2021
distance function. Then consider the problem to find policy whose measurement vector is closest to the target convex set,
arg min (e(inndst((((()).... (
(4)
policy μ² ((II) is defined be an optimal solution if minimizes imation enror of p E (IT) is defined as
Otherwise, the approx-
err = dist" (c(p)), - dist"(c(("",,)
(Approximation Error) (5)
where μ² is optimal solution, and policy is defined to be an e-approximate solution if its ap- proximation error is no larger than e.
When C2RL (3 is feasible, the equivalence of being optimal to and being feasible to C2RL can be easily established. Since a feasible policy C2RL problem lies inside Ω2 it minimizes the non-negative dist? function, and hence is optimal to (4). Vice versa, any optimal solution to (4) lies inside and is feasible solution to C2RL.
From geometric perspective, let c(II) {c(T)( II} be the set of all values achievable by deterministic policies. If the MDP has finite states and actions (though may be extremely large), then IT is finite well, and hence c(TI) contains finitely many points in Th. Then the set of values achievable by mixed deterministic policies
c(A(II) {c(μ)] A(II)) = E ((())((T)) ((T)== 1, 0} R
(6)
the convex hull of e(IT); i.e., c(I(IT)) is a m-dimension polytope whose vertices are e(II).
Therefore finding policy whose value is closest to the target convex set (4) equivalent to find point in the polytope el c(A() that is closest to the convex set Ω
arg min dist)(c(u), c(p))c(A(())
(Distance minimization problem).
To solve this constrained optimization problem, it might be tempting to consider projection methods. However, constructing a projection operator for c(A(IT) is non-trivial. For any given measurement vector, it is obscure how to modify a general RL algorithm to update the parameters such that the discounted expected measurement vector is closest the given value. Therefore, projection-free methods are preferable for this task.
Frank-Wolfe (FW) algorithm does not require any projection operation, instead uses a linear mini- mizer oracle. Intuitively, finding linear minimizer is similar to the reward maximization process of what a general RL algorithm does. In section 4.3 we formalize this idea. We show that after simple modifications, any RL algorithm that maximizes scalar reward can be used to construct such a linear minimizer oracle. Before getting into details of the construction process, we discuss FW-type algorithms over polytope and its applications in the distance minimization problem (7).
4.2 DISTANCE MINIMIZATION BY MAAN-WWLFFE-YPEE ALGORITHMM
The Frank- Wolfe algorithm (FW) a first-order method to minimize a convex function f P + R over compact and convex set P. with only access linear minimizer oracle. When the feasible set is a polytope P == conv( ( (1,, .2...., 88 (x))) C I defined as the convex hull of finitely many points, FW-rype algorithms discussed by Lacoste-Julien & Jaggil (015) optimize
min f(x) TEP
using Oracle(v) = arg min S
(
.E(e1......)
The standard FW (Algorithm 2 in Appendix A.I consists of making repeated calls to the linear minimizer oracle to find an improving point s, followed by convex averaging step of the current iterate IT-1 and the oracle's 's output s.
we have already constructed a RL oracle(A) that outputs a policy π E arg min X ((())) together with its measurement vector e(Tr), then the distance minimizing problem (7) can be solved with standard FW by using
n, ((T) <- RL or.cra oel.orcleeiisst (x)-1,,)) RL. oracle(z;-1 -rojo((1-1)
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Convex Constrained Reinforcement Learning (C2RL)
Input. RL-Oracle constructed by any RL algorithm, projection operator to target set Projn.
Initialize. Random policy т,, value a c(π), active sets Sp == | S. == [æ] and weight À = [4]
Output. Mixed policy μl and its value c(p) s.t. c(j) minimizes the distance to the target set f2.
1: while true do
Major cycle
2: w + p (x)
3:
T, r. + RL Oracle(x - w)
I/ Potential improving point
4:
(f: " c(T)) I then break
5:
if (c(=)) is affinely independent then S. - U + Sp J (
6:
while true do
I/ Minor cycle y - arg min sEaff(S.) || - w wll2 // y E conv (S.)
7:
y, < AffineMininizerr(S.rrr
8:
if a, > 0 for all & then break // If y é conv(S.), then update y to the intersection of conv(S.) and segment joining æ and y. Then remove points in S. unnecessary for describing y- // Recall À satisfies x = Eses, Ags
9:
10:
f + min;a, 50 x;-a; + By (1 0)x, Oa; + (1 0)1,
A,
11:
12:
S. + [c(TT) E S. and X; > 0}, Sp + { TH Sp and 0 > 0}
13:
end while
14:
Update f + Ens, AR x t y. a.
15:
end while
return μ. c(u) x
2 the convex averaging steps find an improving policy and its measurement vector. For f) 7+2
He + (1 m))4-1 + T,,, C2 f (1 - 7/: 71) + T)c(T)
(10)
then maintain the mixed policy, and the corresponding measurement vector, respectively.
However, after T rounds of iteration, the Pe found has an active set containing up to T individual polices, and is not sparse enough. If neural networks used to parameterize the policy, that requires storing copies of parameters for the individual network, which is unaffordable for large- scale usage.
To find even more sparse policies, we turn to variants of FW-type algorithms. particular, Wolfe's method for minimum norm point in polytope (Wolfe 1976. De Loera al. 2018). In Wolfe's method (Algorithm in Appendix [A.2), the loop in FW is called a major cycle, and the convex averaging step replaced by weight optimization process, called minor cycle. Wolfe's 's method maintains an active set S. and the current point can be represented by sparse combination of points in the active set. The minor cycles maintain S to be an affinely independent set such that the affine minimizer is inside St, which Wolfe calls corrals. Recall an affine minimizer is defined as arg min (S)rr(S)) |//|/2. where aff(S) == {yly = Exes a xx >xES O₂ = 1} the affine hull formed by S. Since the active set affinely independent, the number of active atoms at most m + 1 at any time. Wolfe's 's method is shown to strictly decrease the approximation error between two major cycles.
4.3 OUR MAIN ALGORITIIM
The main obstacle to apply Wolfe's method to our distance minimization problem 7 is that the objective function in Wolfe's method the norm function. However, in our problem, the objective function is the distance function to a convex set. Unlike the norm function, the distance function to a convex set is not strongly convex and affine minimizer is ill-defined with respect to a convex set. To tackle these problems, modify the Wolfe's 's method. At the core of our new variant of FW algorithm, we add a projection step to Wolfe's 's method.
Step In each major cycle, minimize the distance projected point Proj Intuitively, since the distance to the convex set is upper bounded by the distance to this projected point w, if the distance to converges, so does the distance the target convex set.
Projection
Formally, for a set of points S C RR, and a point æ E I"",, we extend the definition of an affine minimizer to define affine minimizer with respect to a arg min minacatt(s) ||s æ||2- For being
5

---

Under review as a conference paper at ICLR 2021
the affine minimizer of S with respect to w. the extended affine minimizer property gives
Given w, Vo E aff(S), - z)(( w) = (Extended affine minimizer property)
(11)
Similar to Wolfe's method, our C2RL method (Algo. D contains an outer loop (called major cycle) to find improving policies and their measurement vectors, and an inner loop (called minor eycle) to maintain the affinely independent property of the active set Se. At the start of each major cycle step, the S, is an affinely independent set. Then, the oracle (defined in (15) finds potential improving policy и E U. and its long-term measurement vector c(T). the c(TT) does not get
strictly closer to the == Proj (æ=), then we are done, and is the optimal value. Otherwise, the
c(T)) is added into the active set, and the minor cycle is run to climinate policies whose mcasurement vectors are affinely dependent.
Line to line 13 contains the minor cycle, which is the same as the original Wolfe's method (except in line 6 we find affine minimizer with respect to w). The elimination is executed series of affine projections. The minor cycle terminates if active set S. is affinely independent. Though the interleaving of major and minor cycles oscillate the size of active set Sc, the minor cycles keep [S,] an affinely independent set, and terminated whenever S. contains a single element. Therefore at the start of any major cycle, the size of the active set satisfies [S, E [0, m + 1]. More background about the minor cycle in Wolfe's 's method is provided in Appendix A.2
Construction of RL Oracle The construction of our RL oracle can use any off-the-shelf RL algo- rithm that maximizes a scalar reward. For any given À E R",, we define any algorithm that finds a policy minimizing the linear function A 2"'((-) as RL oracle, that is
RL.oracle,(A) arg arg X" c(TT). =EII
(12)
Recall that standard RL algorithm receives scalar reward after each state transition, instead of the long-term measurement vector e(T) E TR... We then use the following linear property to reformulate the right hand side of (12) to a standard RL. problem
T
arg min A c(T) TENT
arg min A TEN
E
+²)== = arg max E
Σ t=0
x-X"oa))).
(13)
t=0
E
This shows that if we consider the Markov decision process with the same state, action, and transi- tion probability, and construct a scalar reward r = (-X''c;) ct), then any policy that maximizes the expected is a linear minimizer of (12). Therefore any RL algorithm that best suits the underlying problems can be used to construct a RL oracle.
Certifying constraint satisfaction amounts evaluate the measurement vector of the current policy. This is handy in online settings, where simulations can be used to evaluate the measurement vector of the policy directly. Otherwise, in batch settings, various off- off-polii policy evaluation methods, such as importance sampling (Precup) 2000 Precup et al. (201)) doubly robust (Jiang & Li 2016 ct al. 2011), can be used to evaluate the policy.
Dudik
RL.oracle,(A) (A) := c(arg min A c(T) arg min X XT c(T).
(14)
well
c(r).nEll
To simplify notation, we assume a RL_Oracle returns a policy as well as its measurement vector
RL Oracle(A) = n, c(T) = RL oracle,()) RL oracle.(A)
(15)
Finding Extended Affine Minimizer The process Aff AffiinMinimizer(S... w) returns the (3,, o)) the affine minimizer of S with respect to æ where y is the affine minimizer and a == {aa I's e Sc} is the set of coefficient expressing y as an affine combination of points in S, that y ExEs, 8g where o,, is the weight associated with The process Aff AffineMinimizer/ be straightforwardly implemented using linear algebra. Wolfe (1976) also provides a more efficient implementation that uses a triangular array representation of the active set.
a)) can
4.4 CONVERGENCE AND SPARSITY
In this section, we analyze the convergence and complexity of the proposed C2RL method (Algo. We first show that approximation error of C2RL strictly decreases between any major cycle steps

---

Under review as a conference paper at ICLR 2021
and it converges in (1/tt) rate. Then we show method ensures convergence of arbitrary RL algorithm, including those searching for deterministic policies. Moreover, concerning the memory complexity, we show that maintaining an active policy set of m++1 is worst case optimal ensure the convergence of arbitrary RI. algorithm. Therefore, the proposed C2RL indeed achieves the optimal sparsity for the found policy, making it favorable for large-scale usage.
The main difference between the convergence analysis of C2RL and Wolfe's method is the addition of the projection step. Intuitively, at each major step, if we are making a significant progress toward the projected point, then the distance to the convex set is decreased by at least the same amount.
Time Complexity. In our analysis, we consider the approximation error as defined in (5 We use superscript t to denote the variable in f-th major cycle before executing any minor cycle. To simplify notions, we let x² := c(p²) and sf == c(T'). ). When discussing one step with t fixed, let y' denote the affine minimizer found in i-th minor cycle (line o of Algo. [ We first show that the C2RL method strictly reduces approximation error between two calls of the RL oracle.
Theorem 4.1 (Approximation Error Strictly Decreases). For any non-terminal step t, we have err(u +1 < err(μ²), That is, the measurement vector of μ² found by the C2RL method gets strictly closer to the convex set St after major cycle step.
B The idea is to consider the distance between x' and wt When the major cycle has no minor cycle, the non-terminal condition and the affine minimizer property implies dist f w²) < dist" w²). Otherwise show that the first minor cycle strictly reduces the dist"(x",ur w²t by moving along the segment joining a and y. and the subsequent minor cycle cannot increase it. Since w² E 52, we conclude err(x'+1) S dist? (x ww) dist?(x",, w²) = err(""), and the approximation error strictly decreases.
The proof is provided in Appendix
Given the approximation enror strictly decreases, Wolfe's method for minimum norm point can be shown to terminate finitely (Wolfe) 1976). However, this finitely terminating property does not hold for our algorithm. Since a changed w' may yield lower distance to the same active set St the active set may stay unchanged across major cycles (see Figure S Middle for an example). Therefore we establish the convergence of the C2RL method by the following theorem.
Theorem 4.2 (Convergence in Approximation Error). For 2 1. the mixed policy μt found by the m2RL. method satisfies
err(w') S 16Q2 (t++ 2),
(16)
where Q == maxpe [[c(p)] is the maximum norm of a measurement vector.
The proof is provided in Appendix C which relies on the following two lemmas. We briefly discuss the main idea here. Define major cycle steps with at most one minor cycle as "non-drop step" and major cycle steps with more than one minor cycles as "drop steps". We show that in each non-drop step, Algorithm is guaranteed to make enough progress in the following lemma.
Lemma 4.3. For non-drop step in C2RL method, we have err(μ²' -rr(((t))) err
Though this does not hold for drop steps, we can bound the frequency of drop steps by the following. Lemma 4.4. After t major cycle steps of C2RL method, the number of drop steps is less than t/2.
Since the approximation error strictly decreases (Thm. 4.1. and in more than half of the major cycles steps, the C2RL method makes significantly progress. The Thm. using an induction argument (Appendix(C) C).
can then be proved
Convergence with Arbitrary RL Algo. The convergence of the C2RL method when used with RI. algorithms that search for deterministic policies, such as DQN, DDPG and variants, is indeed straightforward. In (8), though each time the oracle yields vertex, the FW-type algorithms indeed optimize over the polytope formed by these vertices. Then since citetaltman 1999constrained shows that any e(-) achievable can be achieved by some mixed deterministic policies, conclude that if the underlying problem is feasible, then our C2RL method is able to find a feasible policy.
Memory Complexity We then discuss the sparsity of mixed policy for constrained RL problem. We give a constructive proof in Appendix to show that to ensure convergence for RL algorithms that search for deterministic policies, storing + policies is required in the worst case.
7

---

Under review as a conference paper at ICLR 2021
088
08
08
Start
God Strt
Gas Sort
Gcil 04
02
Figure 1: Left: The Risky Mars Rover environment. The agent is required navigate from the starting point to reach the goal point without staying long (0.5 steps in expectation) in the risky area (cross-hatching region). Middle, Right. Example of an optimal mixed policy found by C2RL in single run. After 10k samples, C2RL finds mixed policy that randomizes among two policies with weight 0.49 and 0.51. The visitation probabilities of the two policies are plotted.
Theorem 4.5 (Memory Complexity Bound). For an constrained RL problem with m-dimensional measurement vector, in the worst case, a mixed policy needs to randomize among m + 1 individual policies ensure convergence of RL oracles that search for deterministic policies.
Since the minor cycles in the C2RL method eliminate policies with affinely dependent measurement vectors, after the termination of minor cycles, the size of the active is at most + 1. That is, the policy found by the C2RL method requires randomization among no more than m + individual policies. Therefore the proposed C2RL indeed achieves the optimal sparsity in the worst case, making it favorable for large-scale usage.
Corollary 4.5.1. The C2RL method that randomizes among at most m + policies worst-case optimal ensure convergence of any RL oracle.
5 EXPERIMENTS
We evaluate the performance of C2RL in a grid-world navigation task (Fig. [. and demonstrate its ability to efficiently find sparse policy. this Risky Mars Rover environment, the agent is required to navigate from the starting point to the goal point, by moving to one of the four neighborhood cells each step. The episodes terminate when the goal point is reached or after 300 steps. To enforce robustness, we add risky area to indicate the dangerous states. The agent receives measurement vector indicate the steps it takes (0.1 for every step), and whether stays the risky area (0.1 for every risky step, and 0 otherwise), with discount factor y 0.99. We constrain the agent to reach the goal point with expected cumulative steps measure within 1.1 and the expected cumulative risky steps within 0.05. Note that by design, the shortest path from the starting point to the goal point does not satisfy the constraint. This is common in practice, as robustness typically evolves trade-off between the reward and the constraint satisfaction.
The proposed C2RL method is compared with approachability-based policy optimization (Ap- proPO) (Miryoosefi et al. 2019) and with reward constrained policy optimization (RCPO) (Tessler et al., 2018). ApproPO solves the same convex constrained RL problem by using an RL oracle play against no-regret online learner (Hazan et al. 2008 Zinkevich 2003). Since ApproPO and C2RL both use a RL oracle, ApproPO is natural bascline to be compared with our method. Besides, we also compare with RCPO, which takes a Lagrangian approach to incorporate the con- straints as penalty signal into the reward. Using an advantage actor critic (A2C) et al. (2016), RCPO has been shown to converge to a fixed point. For a fair comparison, C2RL and ApproPO uses an A2C agent as the RL oracle, with the same hyperparameter as used in RCPO. The approximation errors are compared after training for the same number of samples.
Note that the C2RL method does not introduce any extra dyper-parameen they require extra parrmpareeeter for the initialization and learning rate of a variable equivalent to our À in the outer loop. This is because our approach does not rely the online learning framework, and therefore there is no need to tune the initialization and learning rate for our À and ease the usage.
For ApproPO and RCPO,
We first showcase the consequences of our theoretical results using optimal RL oracle. For any x E Rmm, an optimal policy can be easily found via Dijkstra's 's algorithm. If multiple optimal paths exist, is randomly picked to form deterministic policy.
8

---

Under review as a conference paper at ICLR 2021
10
Target conees set <Aully all)
ApprePO canL
2.0
Risky steps
Ricky stoox
steps
1.3-
0.5
App runs C2A1 runs
12
0.0
Steps
Steps
Steps
Figure 2: Left: Visualization of the distance minimization problem (7 in IR,, where the number of steps and the number of steps in risky polytope formed by values achievable by mixed deterministic policies c( (IT() and the red hatched region is the target set. Middle: Using optimal RL oracle, 10 paths convergence property of C2RL and ApproPO, where each cross on the dashed line corresponds to call to the oracle. Right: If we zoom in, ApproPO suffers from the zig-zagging problem.
measured. The green hatched region is the
sampled to showcase the
30
Aggrocination ernor
0.8
C2RL
Approro
Appropn ROPO CIRL
25
Approro
ApproPo cacha
RCPG
20
0.6
Approximation
15
of
10-
0.2
0.0
200
300
40
40
100
samples
samples
Figure 3: Left: Time complexity measured by number of calling an optimal RL oracle. Middle, Right: Using A2C to approximate an RI. oracle, time complexity measured by thousands of samples and memory complexity measured by the number of policies stored are compared.
Using this as optimal RL oracle, the convergence property of C2RL and ApproPo are compared. Figure Middle shows the value of policies c(μ²²) found after each call the oracle. In Figure Right, when approaching the boundary of the feasible set, the iterations of approachability- methods start zigzag. Since C2RL contains minor cycle to re-optimize the weights among the active set, C2RL progresses quickly to reach the exact optimal solution. In Figure Left, the approximation error is shown for 300 calls the optimal RL oracle.
We then compare C2R1,, ApproPO and RCPO using the same A2C agent (details of the model structures and hhyee-ppraamtter are provided in Appendix E). We run each algorithm for 50 times, and each run for maximum of 100 thousands of samples. The mean and standard deviation of the results are presented Figure 3 The original paper of ApproPO suggests using a cache to save memory, and the memory requirement of this variant is also presented. Figure demonstrates that C2RL converges to an optimal policy faster than previous methods, and a sparse combination of individual policies is maintained throughout the iteration process.
CONCLUSION
In this paper, we introduce C2RL, an algorithm to solve RL problems under orthant or convex constraints. Our method reduces the constrained RL problem distance minimization problem, and a novel variant of Frank- Wolfe type algorithm is proposed to solve this. Our method comes with rigorous theoretical guarantees and does not introduce any extra hyper-parameter an c-approximation solution, C2RL takes (11cc) calls of any RL oracle and ensures convergence to work with arbitrary RL algorithm. Moreover, C2RL strictly reduces the approximation error between consecutive calls of RL oracle, and for m-dimensional constraints, the memory requirement reduced from storing infinitely many policies (O(1/e)) to storing at most constantly many (m+ 1) polices. We further show that the constant is worst-case optimal to ensure the convergence for RL algorithms that search for deterministic policies. Experimentally, we demonstrate that the proposed C2RL method finds sparse solution efficiently, and outperforms previous methods.
find

---

Under review as a conference paper at ICLR 2021
REFERENCES
Jacob Abernethy, Peter L Bartlett, and Elad Hazan. Blackwell approachability and no-regret learning are equivalent. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 27-46, 2011.
Jacob D Abernethy and Jun-Kun Wang. On frank-wolfe and equilibrium computation. In Advances in Neural Information Processing Systems, pp. 6584-6593, 2017.
Alekh Agarwal, Alina Beygelzimer. Miroslav Dudik, John Langford, and Hanna Wallach. A reduc- tions approach fair classification, arXiv preprini Prxiiv/8003.. 003402253, 2018.
Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
Gabriel Barth-Maron, Matthew W Hoffman, David Budden, Will Dabney, Dan Horgan, Dhruva Tb, Alistair Muldal, Nicolas Heess, and Timothy Lillicrap. Distributed distributional deterministic policy gradients. arXiv preprint 1804.08888.88/// 2018.
Amir Beck and Shimrit Shtern. Linearly convergent away-step conditional gradient for non-strongly convex functions. Mathematical Programming, 164(1-2):1-27, 2017.
Craig Boutilier and Tyler Lu. Budget allocation using weakly coupled, constrained markov decision processes. 2016
Deeparnab Chakrabarty, Prateek Jain, and Pravesh Kothari. Provable submodular minimization using wolfe's algorithm. In Advances in Neural Information Processing Systems, pp. 802-809, 2014.
Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and Ed H Chi. Top-k pollcy correction for a reinforce recommender system. In Proceedings of the Twelfih ACM International Conference Web Search and Data Mining, pp. 456-464, 2019.
Yinlam Chow and Mohammad Ghavamzadeh. Algorithms for ovar optimization in mdps. In Ad- vances in neural information processing systems, pp. 3509-3517, 2014.
Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained re- inforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 18 (1):6070-6120, 2017.
Yinlam Chow, Ofir Nachum, Edgar Duenez-Guzman, and Mohammad Ghavamzadeh. A Iyapunov- based approach to safe reinforcement learning. In Advances in neural information processing systems, pp. 8092-8101, 2018
Jesús A De Loera, Jamie Haddock, and Luis Rademacher. The minimum euclidean norm point in convex polytope: Wolfe's 's combinatorial algorithm is exponential. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 545-553, 2018.
Miroslav Dudík, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. arXiv preprint 1rXiv: 4600, 2011.
Marguerite Frank, Philip Wolfe, et al. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95-100 1956.
Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-133, 1999.
Scott Fujimoto, Herke Van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. arXiv preprint 1822.08002.0477 2018.
Dan Garber and Elad Hazan. A linearly convergent conditional gradient algorithm with applications to online and stochastic optimization. arXiv preprint 1rXiv:1301.4660 2013a.
Dan Garber and Elad Hazan. Playing non-linear games with linear oracles. 2013 IEEE 54th Annual Symposium Foundations of Computer Science, pp. 420-428. IEFE, 2013b.
10

---

Under review as a conference paper at ICLR 2021
Peter Geibel and Fritz Wysotzki. Risk-sensitive reinforcement learning applied to control under constraints. Journal of Artificial Intelligence Research, 24:81-108, 2005.
Elad Hazan, Alexander Rakhlin, and Peter L Bartlett. Adaptive online gradient descent. In Advances in Neural Information Processing Systems, pp. 65-72. 2008.
Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In Proceedings of the 30th international conference machine learning, number CONF, pp. 427-435, 2013.
Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning. In International Conference on Machine Learning, pp. 652-661. PMLR, 2016.
Simon Lacoste-Julien and Martin Jaggi. On the global linear convergence of frank-wolfe optimiza- tion variants. In Advances in neural information processing systems, pp. 496-504, 2015.
Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In Inter- national Conference Machine Learning, pp. 3703-3712, 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 1500.v555000220 2015.
Sobhan Miryoosefi, Kianté Brantley, Hal Daume III, Miro Dudik, and Robert E Schapire. Reinforce- ment learning with convex constraints. In Advances in Neural Information Processing Systems, pp. 14093-14102, 2019.
BF Mitchell, Vladimir Fedorovich Dem yanov, and VN Malozemov. Finding the point of a polyhe- dron closest to the origin. SIAM Journal on Control, 12(1):19-26, 1974.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602 2013.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference machine learning, pp. 1938-1937, 2016.
Santiago Paternain, Luiz Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained rein- forcement learning has zero duality gap. In Advances in Neural Information Processing Systems, pp. 7565-7565, 2019.
Doina Precup. Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series, pp. 80, 2000.
Doina Precup, Richard S Sutton, and Sanjoy Dasgupta. Off-policy temporal-diiffrencce learning with function approximation. In ICML, pp. 417-424, 2001.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Chen Tessler, Daniel J Mankowitz, and Shie Mannor. Reward constrained policy optimization. In International Conference on Learning Representations, 2018.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. arXiv preprint 100.:: 060601 2015.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Mare Lanctot, and Nando Freitas. Dueling network architectures for deep reinforcement learning. In International conference on machine learning, pp. 1995-2003, 2016.
Philip Wolfe. Convergence theory in nonlinear programming. Integer and nonlinear programming, pp. 1-36, 1970.
Philip Wolfe. Finding the nearest point in polytope. Mathematical Programning, 11(1):128- -19- 1976.
11

---

Under review as a conference paper at ICLR 2021
Shuai Xiao, Le Guo, Zaifan Jiang, Lei Lv, Yuanbo Chen, Jun Zhu, and Shuang Yang. Model-basse constrained mdp for budget allocation in sequential incentive marketing. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pp. 971-980, 2019.
Xiangyu Zhao, Liang Zhang, Long Xia, Zhuoye Ding, Dawei Yin, and Jiliang Tang. Deep rein- forcement learning for list-wise recommendations. arXiv, pp. arXiv-1801, 2017.
Guanjie Zheng, Fuzheng Zhang, Zihan Zheng, Yang Xiang, Nicholas Jing Yuan, Xing Xie, and Zhenhui Li. Drn: A deep reinforcement learning framework for news recommendation. In Pro- ceedings of the 2018 World Wide Web Conference, pp. 167-176, 2018.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference machine learning (icml-03), pp. 928-936, 2003.
Lixin Zou, Long Xia, Zhuoye Ding, Jiaxing Song, Weidong Liu, and Dawei Yin. Reinforcement learning optimize long-term user engagement in recommender systems. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pP- 2810-2818, 2019.
12

---

Under review as a conference paper at ICLR 2021
A MORE ON FRANK- WOLFE-TYPE ALGORITHMS
A.1 STANDARD FRANK-WORE ALGORITHM
Algorithm 2 Frank-Wolfe algorithm (Frnk et al. 1956)
Input: obj. y + R, oracle (()), init. 20 E
1: for t=1, 2, .... do
2: 8 - (O..aleeea(aaaaaeee
arg minl (11....) 8 V (x(+-))
3: 3y + (1 T1:1 + 118 for == E42
4: end for
5: return Øf
For a convex function f & + R the Frank- Wolfe algorithm (FW) solves the constrained opti- mization problem over compact and convex X. The standard FW is known have a sublinear convergence rate, and various methods are proposed to improve the performance. For example, when the underlying feasible is a polytope, and the objective function strongly convex, multi- ple variants, such as away-step FW (Wolfe)
Jaggi 2013). pairwise FW (Mitchell et al. 1974),
and Wolfe's method (Wolfe) 1976) are shown to enjoy linear convergence rate. Linear convergence under other conditions is also studied (Beck & Shtern 2017 Garber & Hazan
2013a b).
A.2 WOLFR'S METHOD FOR MINIMUM NORM POINT
Algorithm Wolfe's s Method for Minimum Norm Point
Initialize P, active set S [a]] and weight À = [1].
Output: z E P that has the minimum Euclidean norm.
1: while true do
// Major cycle // Potential improving point
2: 8 Oracle(x))
3:
if ||| < x² se"s= + then break
4:
S-SURE {s}
5:
while true do
// Minor cycle y = arg min mingeatr(s)) ||*||a y E conv(S)
6:
y, a < AffineMinimizer((})
7:
a > for 8 then break
8:
If & conv(S), then update y the intersection of conv(S) and segment joining and y. Then remove points in S unnecessary for describing y. Recall satisfies æ E.es Ags
9:
0 + min X;-a;
10:
+ Oy + (1 - 0) A = lo; + - (1-0)A;
S S {si|s; S and > 0}
12:
end while
Update y and X a
14:
end while
return
Wolfe's method is an iterative algorithm for finding the point with minimum Euclidean norm in polytope, which is defined as the convex hull of set of finitely many points.
The Wolfe's method consists of finite number of major cycles, each of which consists of a finite number of minor cycles. At the start of each major cycle, let H(x) = {y" x xx be the hyperplane defined by a. If (ax) separates the polytope from the origin, then the major cycle terminated. Otherwise, it invokes oracle to find any point on the near side of the hyperplane. The point is then added into the active set S, and starts minor cycle.
In a minor cycle, let be the point of smallest norm in of the affine hull aff(S). If is in the relative interior of the convex hull conv(S), (S), then x is updated to and the minor cycle is terminated. Otherwise, is updated to the nearest point to y the line segment conv(S) [xx y). Thus y is updated to boundary point of conv(S), and any point that is not on the face of conv(S) in which lies is deleted. The minor cycles executed repeatedly until S becomes corral, that is, set
13

---

Under review as a conference paper at ICLR 2021
whose affine minimizer lies inside its convex hull. Since set of one point is always corral, the minor cycles is terminated after a finite number of runs.
B PROOF OF THEOREM 4.
Theorem 4.1
(Approximation Error Strictly Decreases). For any non-terminal step t, we have err(u'11 err(μ²). That is, the measurement vector of p² found by the C2RL. method gets strictly closer to the convex set ft after major cycle step.
Proof. If the current step is major cycle with no minor cycle, then x' is the affine minimizer of af {s*}) with respect to w' Then the affine minimizer property implies (s' x=++1 (xx+)
w²) 0. Since iteration does not terminate at step
have (x* w=)²(x" s*) 0, and
therefore rg+11 not equal to x' Then x g++1 is the unique affine minimizer implies fa fa( min ||x - w||2 - || w012 ff(x").
Otherwise the current step contains one or more minor cycles. In this case, we show that the first minor cycle strictly reduces the approximation error, and the (possibly) following minor cycles cannot increase it. For the first minor cycle, the affine minimizer y" of aff(S U {{*))) with respect wf is outside conv(S {s']). Let = By + and segment joining and Let V := St and V denote the active set after the i-th minor cycle. Then since y the affine minimizer of V with respect to w², we have
f))=² be the intersection of conv(S {s'])
||z w' 110y (1 (1- w'1l S 011 wIll + 0)||= w'll
|| w'll,
(17)
where the second step uses the triangle inequality and the last step follows since the segment x æ'y² intersects the interior of (onv(SU (s)(s')) }),
and the distance wt strictly decreases along this segment. Therefore the point z found by first minor cycle satisfies
fn(z) min z - w||2 < || w'11 < 1| w'll fn(("). well
(18)
Hence h(y') < h(x²), and the first minor cycle strictly decreases the approximation error. By a cannot be increased. However,
similar argument, in subsequent minor cycles the approximation after the first minor cycle, the iterating point may already at the intersection point and the strict inequality in last step of Eq. Ieee be replaced by non-strict inequality.
Therefore any major cycle either finds an improving point and continue, or enters minor cycles where the first minor cycle finds an improving point, and the subsequent minor cycles does not increase the distance. Adding both side of fa(x**) < fa(œ') by fa(x") and we have the approximation error h( h(x(+1) h( h(x*) strictly decreases.
C PROOF OF THEOREM 4.2
4.3 and Lemma 4.4 Then we present the proof of the We first prove the Theorem 4.2 using Lemma 4.3 lemmas.
Theorem 4.2 (Convergence in Approximation Error). For 1, the mixed policy p² found by the C2RL method satisfies
err(w() S 16Q2/(L++
(19)
where Q == max (a [[((p]]] is the maximum norm of measurement vector.
Proof. Since Lemma 4.4 shows that drop steps more than half of total major cycle steps, and
Theorem 4.1 guarantees these drop steps reducing the approximation error, we can safely skip these step, and re-index the step numbers to include non-drop steps only using k.
14

---

Under review as a conference paper at ICLR 2021
For these non-drop steps, claim that (rr("") 8Q2 + 1). Using Lemma 4.3 convergence rate using induction. We first bound the error of any err(x") For any
prove the
err("²) - dist"(c(u")) dist
(20)
1/2l|c(p*) Proja(c(u"))] 1/21|c(p") Proja(c(u"))]
(21)
I (|rrooicc - ||<("")]1 -|Proja(e(("))]]
(22)
< ||e(x\))2
(23)
||(
(24)
s Q
(25)
where Eq. 21 uses the definition of our squared Euclidean distance function. Eq. 22 follows from triangle inequality, and Eq. 23 is by the contractive property of the Fuclidean distance.
When k 1, the Eq. 25 established the based case. Now for k 2 1, assume that err (n*) S
8Q² /A: + 1) for 2 1, then Lemma 4.3 gives err(u*+1) I err(μ²) - (rr²(1²) //Q22 Since the quadratic function of the right hand side is monotonically increasing on (-o0, 4Q"), using the inductive hypothesis
err(u (1) I err(1²) err (r S
(1) s Q² + (26)
Since for 1 steps of major cycle steps, the number of non-drop steps k: > 1/2, we conclude that err(y') & 16Q216(22 +t.
Then we prove the lemmas.
Lemma 4.3
For non-drop step, we have err(j²) err(u(t1) 2 (rr
Proof. The non-drop step contains either no minor cycle or one minor cycle. We first consider the no minor cycle case.
If a major cycle contains no minor cycle, then #++1 the affine minimizer of the SU {8²}.
err(μ') err(u't1)
= distt , 22) dist +1 .2)
(27)
1/2([|=* w'11 min || 3)
(28)
wen
2 1/2(|1z* w'1l2 || ++1 - w
(29)
1/2([|æ' - w'112 + || - w011 - -2| - w²1l
(30)
1/2([[=* ww'l1 || - w01l1 2(x² w') (x -w")
(31)
- 10
(32)
where the equation 31b follows from the affine minimizer property Eq. the last equation, and Vg USU {8))), we have
For | 1+1 in
||00
||q1|
||00
1+1
Definition Q)
(33)
2Q
||0"
qll
2 1 x1+1||
(Triangle inequality)
(34)
2Q
2 2Q (x' x. x=² ④)
Cauchy-Schwarz inequality)
(35)
2Q (x' w²) - -q)
( (Affine minimizer property).
(36)
Then it suffices show that (sx (xx 9) err(n').
15

---

Under review as a conference paper at ICLR 2021
Since Ω is convex set, the squared Euclidean distance function dist²(x, is convex for æ, which implies
(as" .2) + (q x' Vdd)disst .2) S di,t"(q,
(37)
Putting in Vdist? (æ', !2
(x' Proj (x*)) = (a' w'), we get (a' w q) 2 err(""),
which together with Eq. 32 and Eq. 36 concludes that for non-drop step with no minor cycles, we have err("") err (p'
err [/QQ².
For non-drop step with one minor cycle, we use the Theorem 6 of (Chakrabarty et al. 2014). By linear translation of adding points with -w", gives
|| w'11 - ||x -w'll 2 ((x' w (x' - /))2
(38)
Then applying the same argument as Eq. 37 and we finished our proof.
Lemma 4.4 After t major cycle steps of C2RL method, the number of drop steps is less than t/2.
Proof. Recall that at the termination of minor cycle, the size of the active set |S&l E m.]. Since in each major cycle steps, the size of active set S, increases by one, and each drop step reduces the size of St by at least one, the number of drop steps always less than half of total number of the major cycle steps.
D PROOF OF THEOREM 4.5
(Memory Complexity Bound), For an constrained RL problem with m-dimensional measurement vector, in the worst case, a mixed policy needs to randomize among m + individual policies ensure convergence of RL orucles that search for deterministic policies.
Theorem 4.5
Proof. We give a constructive proof. Consider a m-dimensional vector-valued MDP with a sin- gle state, + actions, and c(a,) e; the unit vector of i-th dimension for i [1, m]. and c(0m+1) == 0, and the episode terminates after 1 steps. The constrained RL problem is to find policy whose measurement vector lies in the convex of single point {1/2m). By linear pro- gramming. it is clear that the only feasible mixed deterministic policy is to select am+1 with 1/2 probability, and the rest m actions with 1/2m probability: i.c. the unique feasible policy this problem has an active set containing m deterministic policies. Therefore any method random- ize among less than m + 1 individual policies does not ensure convergence when used with RL. algorithms searching for deterministic policies.
E ADDITIONAL EXPERIMENT DETAILS
All the methods use the same A2C agent. The input is the one-hot encoded current position index. The A2C is the standard fully connected multi-layer perceptron with ReLU activation function. The actor and critic share the internal representation and have their only final layer. Both actor and critic networks use Adam optimizer with learning rate to 1 The network as follows
Actor
Critic
Input layer
One-hot encoded state index (dim=54)
Hidden layer
Linear out=128, act= act="relu")
Output layer
Linear(in=1222 out=4, reet="r"lu")) Linear(in=128, out=1, act="relu"))
Output name
Action score
State value
For ApproPO, the constant for projection convex set convex cone is set be 20. The 0 is initialized to Following the original paper.
For RCPO, the learning rate of its À is set to 55, and its À is initialized to and updated by online gradient descent with learning rate set to 1, as used by the original paper.
The proposed C2RL introduces extra hyper-parameteen, and has nothing report.
16


Reviews:
[{"review_id": "sg9LptEQPdx", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a reduction approach to tackle the optimization problem of constrained RL. They propose a Frank-Wolfe type algorithm for the task, which avoids many shortcomings of previous methods, such as the memory complexity. They prove that their algorithm can find an $\\epsilon$-approximate solution with $O(1/\\epsilon)$ invocation. They also show the power of their algorithm with experiments in a grid-world navigation task, though the tasks looks relatively simple.\n\npros:\n- The application of Frank-Wolfe algorithm to constrained RL problem is novel. The method is basically different from the that of Miryoosefi et al. (2019).The improvement is mainly due to the algorithm design.\n\n- The theoretical improvement is solid. The paper tackles the memory requirement  issue in the previous literature, and only requires constant memory complexity. Further, the number of RL oracle invocation is also reduced from $O(1/\\epsilon^2)$ to $O(1/\\epsilon)$.\n\n- The paper is well-written. Though I only sketched the proof in the appendix, the algorithm and the analysis in the main part is reasonable and sound.\n\ncomments:\n- The algorithm requires a policy set $\\mathcal{U}$ and finds a mixed policy $\\mu \\in \\Delta(\\mathcal{U})$ to satisfy the constraints. How to get a policy set with a feasible solution? Is $\\mathcal{U}$ predefined? For an MDP with $S$ states and $A$ actions, the possible deterministic policy can be $A^S$. Trivially setting $\\mathcal{U}$ as a set with all possible policies may lead to exponential computational and memory complexity.\n\n- Constrained RL problem can be formulated from the standard dual LP form of RL problem, in which the policy $\\pi$ can be fully represented as the density over state-action $d(s,a)$ (See e.g. [1]). Is it possible to solve constrained RL problem under this formulation? What is the advantage of using mixed policies over fixed policy set $\\mathcal{U}$ compared with this formulation?\n\ntypos:\n- line 3 of Algorithm 2: $(1-\\eta_t w_{t-1})$ -> $(1-\\eta_t) w_{t-1}$\n\n[1] Constrained episodic reinforcement learning in concave-convex and knapsack settings", "extra_scores": {}, "extra_text": {}}, {"review_id": "sHnXKtv1hg0", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1. Summarize what the paper claims to do/contribute. Be positive and generous.\n\nIn this paper, the authors consider a class of constrained MDP problem. In the considered problem, instead of getting a scalar reward, in each step, the MDP returns a vector “reward” which is termed as a measurement vector. Then the problem requires finding a (mixed) policy such that the expected measurement vector belongs to a convex set. This problem was first considered in (Miryoosefi et al. , 2019) and the authors of this paper propose a new algorithm and claim an improvement over the sparsity in the mixed policy. The main idea of the new algorithm is to solve the problem as convex minimization of the squared distance to the target set. A standard Frankwolfe-type algorithm is proposed to solve the problem, convergence and complexity analysis are also provided. \n\n2. Clearly state your decision (accept or reject) with one or two key reasons for this choice.\nThis paper is marginally above the acceptance threshold. \n\n3. Provide supporting arguments for the reasons for the decision. \n\n(i). (Weakness) A significant flaw is the WRONG claim of improvement over the previous result (Miryoosefi et al. , 2019). In this paper, the authors yield dist(c(\\mu),\\Omega) \\leq 1/T. While (Miryoosefi et al. , 2019) proves dist(c(\\mu),\\Omega) \\leq 1/sqrt{T}. Thus the authors claim an improved O(1/\\epsilon) complexity over the O(1/\\epsilon^2) complexity of the compared paper. However, this is a wrong argument. If the authors pay attention to the definition of (Miryoosefi et al. , 2019), they should find that the “dist” denotes the standard notation of Euclidean distance. However, the “dist” function in this paper is the SQUARED Euclidean distance. They are defined differently. Therefore, if we view the two results under the same optimality measure, these two complexity results are the same. No improvement is made in this paper in terms of complexity. \n\n(ii). (strength) Though in (i), we find there is no improvement in terms of complexity and hence the sparsity of the mixed strategy. The reason why I still think it is marginally above the threshold is that, compared to the existing approach in (Miryoosefi et al. , 2019), the Frank-Wolfe type algorithm is way more natural and robust. \n\n(iii). (strength) Due to the desirable structure of the Frank-Wolfe method, the authors are able to constantly eliminate the affinely dependent historical policies/measurement vectors. Thus limiting the storage memory to only m+1, where m is the dimension of the measurement vector.\n\n4. Provide additional feedback with the aim to improve the paper. Make it clear that these points are here to help, and not necessarily part of your decision assessment.\n\n(i). The author should change their claim of the improvement over (Miryoosefi et al. , 2019), such improvement is not achieved in this paper. \n\n(ii). In terms of notation, the definition of the “dist” function should be changed. Traditionally, “dist” only denotes the distance instead of the squared distance. The authors should use “dist^2(c,x)” or simply change to some other notation, otherwise, it will cause confusion. (This notation confusion is also possibly the reason why the authors wrongly claim the improvement over (Miryoosefi et al. , 2019))\n\n(iii). It might worth more discussion about what Algorithm 1 is doing. For example, for line 3, briefly comment that $x-\\omega$ is the gradient of the objective function will make the understanding of the algorithm significantly simpler. Similarly, the authors can make more explanation about the line 6-13 of Algorithm 1, which might cause confusion without explanation.\n\n5. Ask questions you would like answered by the authors that help you clarify your understanding of the paper and provides the additional evidence you need to make be confident in your assessment. \n\nConsider finding a policy \\pi whose measurement vector c(\\pi)\\in\\Omega. For simplicity suppose there are only 2 policies. In this paper, the proposed solution is to find p s.t. \np*c(\\pi) + (1-p)*c(\\pi’)\\in\\Omega. However, this corresponds to the situation where before doing anything, first toss a coin to decide whether \\pi or \\pi’ is used. Then use that policy for all future plays. However, this situation is weird in the sense that none of the \\pi or \\pi’ is feasible, and the variance can be very large. My question is, is it possible to find the convex combination s.t. c(p*\\pi + (1-p)*\\pi’)\\in\\Omega? (It is obvious that c(p*\\pi + (1-p)*\\pi’) \\neq p*c(\\pi) + (1-p)*c(\\pi’)). I think such a policy will be stabler. \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "fLgAt0HPOvD", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose C2RL to solve RL problems under convex constraints. The authors reduce the RL problem under convex constraints to a distance minimization problem and solve the distance minimization problem with a Frank-Wolfe type method (with an RL solver as a sub-routine).\nThe authors further show that the algorithm converges (in terms of approximation error), and validate some of their theoretical findings with simulations.\n\n# Pros:\nI like the fact that the authors have theoretical guarantees for their approximation error.\nThe reduction to distance minimization problem is also clear.\n\n# Cons:\n+ I find it hard to understand Section 4.3 and Section 4.4 even after quite a few passes.\nThis is the main reason for my score and my confidence level. For Section 4.3, while I understand how Algorithm 1 works, I have no intuitive idea why Algorithm 1 converges. There is a lack of connection to the original Wolfe's algorithm (such as what corresponds to the objection function and to the linear minimization oracle? Why the linear property of the RL-oracle is important? etc). For Section 4.4, the authors just pile-up their results without further remark on the implications.\n\n+ I don't understand the role of the sparse policy here. Does finding a sparse policy makes the problem easier or harder? Why do we want to find a sparse policy?\n\n+ It seems that the optimal $\\mu$ is not unique, if there are multiple $\\mu$ such that $c(\\mu) \\in \\Omega$. If this is so, the analysis of the Frank-Wolfe type method could be tricky.\n\n+ While I understand the challenges of RL problem under convex constraints, could the author list specifically what are the applications that can be formulated into RL under cvx constraints? Do we have an easy projection operator for these convex constraints? How to choose the policy set in the real world application?\n\nMinor comments:\n\n+ Above equation (7): “is equivalent to minimizing the distance between the polytope and the convex set”. It is misleading to talk about the distance between the two sets. Maybe \"find a point in the polytope that is closest to the convex set $\\Omega$\"?\n\n+ Some comments on the meaning of equation (4) should be helpful for the readers to understand the main flow\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "IGjEUpJOe5", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The paper proposes a fast method for solving reinforcement learning problems with constraints. Oracle computational and memory complexity of the proposed algorithm are provided along with experiments on a grid-world navigation task to illustrate the convergence behavior of the proposed algorithm.\n\nStrength:\n\n- Instead of using a penalty or a regularization scheme to impose safety, risk or budget constraints, the paper proposes to impose the constraints explicitly, or in other words treat them as hard constraints. Dealing with hard constraints is an important open problem especially in nonconvex problems as in reinforcement learning. The paper uses the reductions approach proposed in Agarwal et al, to transform the policy constrained problem to a mixed policy scheme in which finding a feasible solution is equivalent to finding a distribution over policies. Now, with this reduction, the paper leverages the fact that feasible set is guaranteed to be a polytope (given by the convex hull of all feasible policies), and hence the paper solves the equivalent problem of finding a point that minimizes the distance to the convex polytope. \n\n- The minimum norm point algorithm or Wolfe's method is proposed to solve the distance minimization problem. An advantage of the algorithm is that it can be used in tandem with any off-the-shelf RL algorithm while guaranteeing feasibility unlike the penalty based methods. In addition to the time complexity of the algorithm, they also provide a memory complexity bound which in some sense is inherited from the minimum norm point algorithm. The analysis in the appendix seem to use the techniques from the Chakrabarty et al paper.\n\nWeaknesses:\n\n- There is no discussion or comparison of subproblem complexity with respect to existing methods. I consider this paper to be a theoretical paper, and it is unfortunate that there is no mention to any practical use cases. I believe that this is an important aspect of numerical algorithm that needs to be discussed in papers. For example, it is well known that exact projections do provide strictly feasible solutions and solve a problem that is in theory equivalent. That is, if the feasible set is a polytope, Euclidean projection and minimum norm point are both generic quadratic programming problems, hence it is not clear why the minimum norm point should be preferred in reinforcement learning settings. I believe that sparsity in the intermediate iterates seem like the crucial difference, but the paper discusses this aspect merely in passing. Some specific examples of safety, risk or budget constraints and describing the subproblem complexity for such constraints will make this clear. \n\n- I'm not sure if the experiments are reproducible with the information provided in the paper. First, the experiments seem separate from the rest of the paper and the reader has to go over other papers to get an idea of the overall setup. For example, it is not clear why 300 steps are sufficient or what risky region is. Secondly, there is no discussion of the hyperparameters used in the experiments and algorithm. For example, how was the value of epsilon determined? the step size or learning rate? I think the paper would hugely benefit from ablation studies in more than one task, preferably something that is used in practice.\n\nAfter response: Thanks for the clarifications. However, conceptually important questions are not yet clarified yet. For example,  the objective itself can be made into a pure square function (and hence strongly convex) in both classical Wolfe's formulation and the proposed. As the authors are pointing out, the main issue is in designing separation (or projection) oracle for the constraints which corresponds to the base polytope in the context of submodular optimization and was the main motivation for Wolfe's algorithm. Moreover, authors mention that main difficulty in using projections is intractability but it is not clear why the linear optimization performed in the proposed algorithm is efficient.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper builds on the prior work by Miryoosefi et al. (2019) that finds a feasible mixed policy under convex constraints through distance minimization over a simplex set. Instead of the primal-dual approach used in Miryoosefi et al. (2019), this paper proposes to apply Frank-Wolfe type algorithm (particularly, the minimum norm point algorithm) to promote sparsity of the mixed policy, while achieving the same complexity. 

Despite the improvement on sparsity, the AC and some reviewers share two main concerns: (1) incremental novelty of the algorithm/theory, which basically follows from existing optimization work, (2) lack of (theoretical and numerical) justification of the significance of sparsity (especially given that the main computation costs come from projection and RL oracle). 

Unfortunately, the paper lands just below borderline and cannot be accepted this time. 

Decision: Reject