A Simple Reward-free Approach to Constrained Reinforcement Learning
Authors: Sobhan Miryoosefi
Chi Jin
Venue: ICLR 2022 Submitted (2022)
Keywords: constrained reinforcement learning
reward-free
reinforcement learning theory
approachability
linear function approximation

Abstract: In constrained reinforcement learning (RL), a learning agent seeks to not only optimize the overall reward but also satisfy the additional safety, diversity, or budget constraints. Consequently, existing constrained RL solutions require several new algorithmic ingredients that are notably different from standard RL. On the other hand, reward-free RL is independently developed in the unconstrained literature, which learns the transition dynamics without using the reward information, and thus naturally capable of addressing RL with multiple objectives under the common dynamics. This paper bridges reward-free RL and constrained RL. Particularly, we propose a simple meta-algorithm such that given any reward-free RL oracle, the approachability and constrained RL problems can be directly solved with negligible overheads in sample complexity. Utilizing the existing reward-free RL solvers, our framework provides sharp sample complexity results for constrained RL in the tabular MDP setting, matching the best existing results up to a factor of horizon dependence; our framework directly extends to a setting of tabular two-player Markov games, and gives a new result for constrained RL with linear function approximation.

Under review as a conference paper at ICLR 2022
A SIMPLE REWARD-FREE APPROACH TO CONSTRAINED REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
In constrained reinforcement learning (RL), a learning agent seeks to not only optimize the overall reward but also satisfy the additional safety, diversity, budget constraints. Consequently, existing constrained RL solutions require several new algorithmic ingredients that are notably different from standard RL. On the other hand, reward-free RL is independently developed in the unconstrained literature, which learns the transition dynamics without using the reward information, and thus naturally capable of addressing RL with multiple objectives under the common dynamics. This paper bridges reward-free RI. and constrained RI.. Particularly, we propose a simple meta-algorithe such that given any reward-free RI. oracle, the approachability and constrained RI. problems can be directly solved with negligible overheads in sample complexity. Utilizing the existing reward-free RL solvers, our framework provides sharp sample complexity results for constrained RL in the tabular MDP setting, matching the best existing results up factor of horizon dependence; our framework directly extends to a setting of tabular two- player Markov games, and gives a new result for constrained RL with linear function approximation.
INTRODUCTION
In wide range of modern reinforcement learning (RL) applications, is not sufficient for the learning agents to only maximize scalar reward. More importantly, they must satisfy various constraints. For instance, such constraints can be the physical limit of power consumption or torque in motors for robotics tasks (Tessler et al., 2019): the budget for computation and the frequency of actions for real-time strategy games (Vinyals et al., 2019); and the requirement for safety, fuel efficiency and human comfort for autonomous drive (Le et al., 2019). In addition, constraints are also crucial in tasks such as dynamic pricing with limited supply (Besbes & Zeevi, 2009; Babaioff et al., 2015), computer cluster (Mao et al., 2016), imitation learning (Syed & Schapire,
scheduling of resources 2007; Ziebart et al., 2008; Sun et al., 2019), as well as RL with fairness (Jabbari et al., 2017).
These huge demand in practice gives rise efficient algorithms to find nptr-optimal policies for RI. problems under linear or general convex constraints. Most constrained RL works directly combine the existing techniques such as value iteration and optimism from unconstrained literature, with new techniques specifically designed to deal with linear constraints (Efroni al., 2020; Ding et al., 2021; Qiu et al., 2020) or general convex constraints (Brantley et al., 2020; Yu et al., 2021). The end product is a single new complex algorithm which is tasked to solve all the challenges of learning dynamics, exploration, planning as well as constraints satisfaction simultaneously. Thus, these algorithms need to be re-analyzed from scratch, and it highly nontrivial to translate the progress in the unconstrained RI. to the constrained setting.
RI., which focuses designing
On the other hand, reward-free Propssed in Jin et al. (2020a)-is is a framework for the uncon- strained setting, which learns the transition dynamics without using the reward. The framework has two phases: in the exploration phase, the agent first collects trajectories from Markov decision process (MDP) and learns the dynamics without a pre-specified reward function. After exploration, the agent is tasked with computing near-optimal policies under the MDP for collection of given reward functions. This framework is particularly suitable when there are multiple reward functions of interest, and has been developed recently to attack various settings including tabular MDPs (Jin et al.,

---

Under review as a conference paper at ICLR 2022
Table 1:
Sample complexity for algorithms to solve reward-free RL for VMDP (Definition 1),
approachability (Definition 3) and CMDP with general convex constraints (Definition 4).
Algorithm
Reward-free
Approachability
CMDP
Wu et al. (2020)
0(min(d,S)H'5A//)
Brantley et al. (2020)
O(d2
Tabular
Yu al. (2021)
O(min(d,S)44$A
Ó (d,S)HHAA/A))
This work
(imind,,S/4AAA/C O(d /c2)
(imindd,S)HHt50
Linear
This work
Odd
Ó H /
2020a; Zhang et al., 2020), linear MDPs (Wang et al., 2020; Zanette et al., 2020), and tabular Markov games (Liu et al., 2020).
Contribution. In this paper, we propose simple approach solve constrained RL problems by bridging the reward-free RL literature and constrained RL literature. Our approach isolates the challenges of constraint satisfaction, and leaves the remaining RL challenges such as learning dynamics and exploration to reward-fri RL. This allows us to design a new algorithm which purely focuses on addressing the constraints. Formally, we design a meta-algorithm for RL problems with general convex constraints. Our meta-algorithm takes reward-free RI solver, and can be used to directly solve the approachability problem, as well as the constrained MDP problems using very small amount of samples in addition to what is required for reward- RL.
Our framework enables direct translation of any progress in reward-free RL to constrained RL. Leveraging recent advances in reward-fiee free RL, meta-algorithm directly implies sample-efficient guarantees of constrained RL in the settings of tabular MDP, linear MDP, as well as tabular two-player Markov games. In partieular,
Tabular setting: Our work achieves sample complexity of Ó(min S}H+*A/²² for all three tasks of reward-free RL for Vector-valued MDPs (VMDP), approachability. and RL with general convex constraints. Here is the dimension of VMDP or the number of constraints, S, A the number of states and actions, H is the horizon, and is the error tolerance. matches the best existing results up to a factor of H.
Linear setting: Our work provides new sample complexity of Ö H /62) for all three tasks above for linear MDPs. To our hest knowledge, this result is the first sample-efficient result for approachability and also constrained RL with general convex constraints in the linear function approximation setting.
Two-player setting: Our work extends to the setting of tabular two-player vector-valued Markov games and achieves low regret of (<T) O + /H²i// at the cost of this (e)) bias regret as well as additional samples for preprocessing.
1.1 RELATED WORK
In this section, we review the related works on three tasks studied in this paper paper-rewwrr--fiie reward-free RL, approachability, and constrained RI.
Reward-free RL. Reward-free exploration has been formalized by Jin et al. (2020a) for the tab- ular setting. Furthermore, Jin et al. (2020a) proposed an algorithm which has sample complexity (ppol((H) (H) 5² A/(2 outputting c-optimal policy for arbitrary number of reward functions. More
'The presented sample complexities are under the Le normalization conditions as studied in this paper. We comment that the results of (Wu et al., 2020; Brantley et al., 2020; Yu et al., 2021) are originally presented under L1/ Loo normalization conditions. While the results in Wu et al. (2020) can be directly adapted to our setting stated in the table, the other two results Brantley et al. (2020); Yu et al. (2021) will be no better than the displayed results after adaptation.
2

---

Under review as a conference paper at ICLR 2022
recently, Zhang et al. (2020); Liu et al. (2020) propose algorithm VI-Zero with sharp sample complex- ity of (polyy H) log(N) ()/e/ capable of handling N fixed reward functions. Wang al. (2020); Zanette et al. (2020) further provide reward-free learning results in the setting of linear function approximation, in particular, Wang et al. (2020) guarantees find the near-optimal policies for an arbitrary number of (linear) reward functions within sample complexity of Opoly (H (d All results mentioned above are for scalar-valuee MDPs. For the vector vector-valued valued MDPs (VMDPs), very recent work of Wu al. (2020) designs reward-free algorithm with sample complexity guarantee O(poly (H) minfd, S)/2) in the tabular setting. Compared to Wu et al. (2020), our reward-free algorithms for VMDP is adapted from the VI-Zero algorithm presented in Liu et al. (2020); While achieving the same sample complexity, it allows arbitrary planning algorithms in the planning phase.
Approachability and Constrained RL Approachability and Constrained RL are two related tasks involving constraints. Inspired by Blackwell approachability (Blackwell et al., 1956), recent work of Miryoosefi et al. (2019) introduces approachability task for VMDPs. However, the proposed algorithm does not have polynomial sample complexity guarantees. More recently, Yu et al. (2021) gave a new algorithm for approachability for both VMDPs and vector-valued Markov games (VMGs). Yu et al. (2021) provides regret bounds for the proposed algorithm resulting in sample complexity guarantees of (poly(H) min(d, S)/A(( for approachability VMDPs and O(poly min d.S)S.A/A for approachability in VMGs.
Sample-efficient exploration in constrained reinforcement learning has been recently studied in a recent line of work by Brantley et al. (2020); Qiu et al. (2020); Efroni et al. (2020); Ding al. (2021); Singh et al. (2020). All these works are also limited to linear constraints except Brantley et al. (2020) which extends their approach general convex constraints achieving sample complexity of (poly((H))) (d) S A/e²) However, Brantley et al. (2020) requires solving large-scale convex optimization sub-problem. The best result for constrained RL with general convex constraints can be achieved by the approachability-base algorithm in Yu al. (2021) obtaining sample complexity of ((poly(H) (H) min(d, S.S.S))AA/ Technically, our meta-algorithm
based on the Fenchel's duality, which is similar to Yu et al. (2021). In contrast, Yu et al. (2021) does not use reward-free RI., and is thus different from our results in terms of algorithmic approaches. Consequently, Yu et al. (2021) does not reveal the deep connections between reward-free RL and constrained RL, which is one of the main contribution of this paper. In addition, Yu et al. (2021) does not address the function approximation setting.
Finally, we note that among all results mentioned above, only Ding et al. (2021) has considered models beyond tabular setting in the context of constrained RL. The model studied in Ding et al. (2021) is known as linear mixture MDPs which is different and incomparable to the linear MDP models considered in this paper. We further comment that Ding et al. (2021) can only handle linear constraints for CMDP, while our results is capable of solving CMDPs with general convex constraints.
2 PRELIMINARIES AND PROBLEM SETUP
We consider an episodic vector-valued Markoy decision process (VMDP) specified by a tuple M = (S, H, F.r,, where S is the state space, A is the action space, H is the length of each episode, P = {IP ) is the collection of unknown transition probabilities with (n (s, equal to the probability of transiting to s' after taking action in state s at the tt step, and r = {IA x A - ( is a collection of unknown d-dimensional return functions, where (rr) the d-dimensional Euclidean ball of radius r centered at the origin.
Interaction protocol. each episode, agent starts at a fixed initial state 81. Then, at each step h [H), the agent observes the current state sh, takes action ag receives stochastic sample of the return vector Th (3), on). and it causes the environment to transit to S1+1 ~ P. sh, ax). We assume that stochastic samples of the return function are also in ((1), almost surely.
Policy and value function. A policy ग of an agent is a collection of H functions { S + (f that map states distribution over actions. The agent following policy n. picks action Og. (s())) the h1th step. We denote V S B(H) the value func-
3

---

Under review as a conference paper at ICLR 2022
tion at step h for policy π, defined as Vī(s) == Ex E>*=> (wrss,,a)) 1 = Similarly, we denote Q% S A B(H) as the Q-value function at step for policy n, where (%, a) == E EN Ei' (wws an) Sh. s, an =
Scalarized MDP. For a VMDP M and 0 e B(1), we define scalar- MDP Ma (S, A, H, Pr).. where тo = {00, rn) :S A A [-1, We denote V (=:0) :S | H, H as the scalarized value function at step h for policy π, defined as
V (s; 0) E,,
Σ # (0, re (w (x))
8h = (0, (())).
Similarly, we denote ()):;): 8 A H-H, H| as the scalarized Q-value function at step h for policy where
Qhis, = E Σi= (0, Tn (sw, ax = s, = = (0, (s,
For fixed 0 Rd, there exists an optimal policy Tg. maximizing value for all states (Puterman, 2014); i.e., V (x; 0) sup, Vi (s; 0) for all E S and h [H]. We abbreviate (=a(;; 0) and Q (: as (* 0) and (: respectively.
2.1 REWARD-FREE EXPLORATION (RFE) FOR VMDPs
The task of reward-free exploration (formalized by Jin et al. (2020a) for tabular MDPs) considers the scenario in which the agents interacts with the environment without guidance of reward information. Later, the reward information is revealed and the agents is required to compute the near-optimal policy. In this section, we describe its counterpart for VMDPs Formally, it consists of two phases:
Exploration phase. In the exploration phase, agent explores the unknown environment without observing any information regarding the return function. Namely, at each episode the agent executes policies to collect samples. The policies can depend on dynamic observations {sf a ({,A)][A]x[[]] the past episodes, but not the return vectors.
Planning phase. In the planning phase, the agent no longer interacts with the environment; however, stochastic samples of the d-dimensional return function for the collected episodes revealed the agent, i.e. (r% (k. ({))))[]]{{(]] Based on the episodes collected during the exploration phase, the agent
outputs the near-optimal policies of Mo given an arbitrary number of vectors 0 E B(1).
Definition 1 (Reward-free algorithm for VMDPs). For any é, 0, after collecting MAPE 6) episodes during the exploration phase, with probability at least 1 - 8, the algorithm satisfies
AO E B(1): (s1 0) ViTe (#1 0) S 6,
(1)
where me is the output of the planning phase for vector as input. The function MiFE determines sample complexity of the RFE algorithm.
Remark 2. Standard reward-free setup concerns MDPs with scalar reward, and requires the algo- rithm to find the near-optimal policies for N disferent prespecifted reward functions in the planning phase, where the sample complexity typically scales with log N. This type of results can be adapted into a guarantee in the form of (1) for VMDP by e-covering of 0 over B(1) and a modified concen- tration arguments (see the proofs of Theorem 7 and Theorem 13 for more details).
2.2 APPROACHABILITY FOR VMDPS
In this section we provide the description for the approuchability task for VMPDs introduced by Miryoosefi et al. (2019). Given a vector-valued Markov decision process and a convex target set C, the goal is to learn policy whose expected cumulative return vector lies in the target set (akin to Blackwell approachability in single-turn games, Blackwell et al. 1956). We consider the agnostic version of this task which is more general since it doesn't 't need to assume that such policy exists; instead, the agent learns to minimize the Euclidean distance between expected return of the learned policy and the target set.
RFE for VMDPs is also called preference-free exploration problem Wu al. (2020)
4

---

Under review as a conference paper at ICLR 2022
Definition 3 (Approachability algorithm for VMDPs). For any c, > 0, after collecting MAPP(E, 6) episodes, with probability at least - 6, the algorithm satisfies
dist VT (s1), I min (VT(s))) +
(2)
where nou is the output of the algorithm and dist C) is the Euclidean distance between point and set The function APP determines the sample complexity of the algorithm.
2.3 CONSTRAINED MDP (CMDP) WITH GENERAL CONVEX CONSTRAINTS
In this section describe constrained Markov decision processes (CMDPs) introduced by Altman (1999). The goal of this setting is to minimize cost while satisfying some linear constraints over consumption of d resources (resources only allows for linear constraints, we consider the more general case of arbitrary convex constraints. More formally, consider VMDP M, a cost function {cr, S A 1]]]] and a convex constraint set C. The agent goal is to compete against the following benchmark:
akin in case). Although, the original definition
min CT x
s.t. Vī(si) EC,
where -%= = 1E, E on (sM,
=
Definition (Algorithm for CMDP). For any c, > 0, after collecting MCMDF(C, 8) episodes, with probability at least 1 - 6, the algorithm satisfies
C C
(81)
min <:Viee
(f(81) S
(3)
dist (VT
(s1), Sc.
where out the output of the algorithm. The function mcMDP determines the sample complexity of the algorithm.
As also mentioned in the prior works (Miryoosefi al., 2019; Yu al., 2021), we formally show in the following theorem that approachability task (Definition 3) can be considered more general compared CMDP (Definition 4); Namely, given any algorithm for the former we can obtain an algorithm for the latter by incurring only extra logarithmic factor and negligible overhead. The idea incorporate cost into the constraint C and perform an (approximate) binary search over the minimum attainable cost. The reduction and the proof can be found in Appendix A.
Theorem 5. Given any approachability algorithu (Definition with sample complexity MAPP. we can design an algorithm for CMDP (Definition 4) with sample complexity MCMDP, satisfying
MCMDr(E, 5) S O (mAPE (g. 12f
1²2 log|dH/e))
.lo 1
2
3 META- FOR VMDPS
In this section, equipped with preliminaries discussed in Section 2, we are ready introduce our main algorithmic framework for VMDPs bridging reward-free RI. and approachability.
Before introducing the algorithm, we explain the intuition behind it. By Fenchel's duality (similar to Yu et al. 2021), one show that
min dist( V (s1, C)) = min max BEB(1)
(00, (T - (a x.)x)
x'ec
satisfies the minimax conditions since it's concave in 0 and convex in æ (by allowing mixture policies); therefore, minimax theorem Neumann (1928) implics that
equivalently solve
max min (0, (T ()) max (0, (0,²)) BEB(1)
x'eC
This max-min form allows us to use general technique Freund Schapire (1999) for solving max-min by repeatedly playing no-regret online learning algorithm as the max-player against best-response for the min-player. In particular, for a fixed e, minimizing over т is equivalent to finding optimal policy for scalarized MDP M_e. To achieve this, can utilize reward-free oracle as in Definition 1. On the other hand for 0 8-player we are able to use online gradient descent (Zinkevich, 2003). By combining ideas above, we obtain Algorithm 1.
5

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Meta-algorithm for VMDPs
1: Input: Reward-Fres
Algorithm RFE for VMDPs (as in Definiton 1), Target Set C
2: Hyperparameters: learning rate ry'
3: Initialize: run exploration phase of RFE for K episodes
4: Set: 0 E =
5: for t = 2,....., do
6: Obtain near optimal policy for M-ar:
n² output of planning phase of RFE for preference vector -0"
7: Estimate Vf (81) using one episode:
Run n² for one episode and let & be the sum of vectorial returns
8: Apply online gradient ascent update for utility function u'(0) (0, V4) m0x
@ [ r/ argmax x)]]
where (1 is the projection into Euclidean unit ball
9: Let nout be uniform mixture of { ,
10:
Return out
Theorem 6. There exists absolute constant c, such that for any choice of RFE algorithm (Defini- tion 1) and for any e E (0, H] and ô E (0, 1]. if we choose
T c(H K2 m2re(e/2,8/2), and Ty² VI/(H
where = (d)); then, with probability at least 1 - 6, Algorithm I outputs an c-optimal policy for the approachabiliity (Equation 2). Therefore, we have mPPP(E, < O(mRrE(e/22 8/2) (²).
Theorem 6 shows that given any reward-free algorithm, Algorithm 1 can solve the approachability task with negligible overhead. The proof for Theorem 6 provided in Appendix B. Equipped with this theorem, since we have already shown the connection between approachability and constrained RL Theorem 5, any results for RFE can be directly translated results for constrained RL.
TABULAR VMDPS
In this section, we consider tabular VMDPs; namely, we assume that [S] S S and |A| S A. Utilizing prior work tabular setting, we describe our choice of reward-free algorithm.
In the exploration phase, we use VI-Zero proposed by Liu al. (2020). It can seen as UCB-V VI (Azar et al., 2017) with zero reward. Intuitively, the value function computed in the algorithm measures the level uncertainty and incentivizes the greedy policy to visit underexplored states. The output of VI-Zero is Poout which an estimation of the transition dynamics.
In the planning phase, given 0 (1)
any planning algorithm (e.g., value iteration) for Mo = (S, A, H, pout (0, P)) where is empirical estimate of using collected samples (r*)-
The following theorem state theoretical guarantees for tabular VMDPs. Proof of Theorem 7 and more details can found in Appendix C.
Theorem 7. For tabular VMDP, have reward-free algorithm (Definiton 1) with mRrE (c, S
Ommin d, S} S + H 222 /e), an algorithm for approachability (Definition 3) with + S2 Ai? (e) and an algorithm for CMDP (Definition 4)
MAPP(E, 5) S ( with mcMDD 8) < (minn S
H A Ar/(c).
The reward-free algorithm with stated sample complexity in Theorem 7 is the VI-Zero algorithm (Algorithm 5 in Appendix C). Its sample complexity result is obtained by adapting the results in Liu et al. (2020) for scalar-valued MDPs to the settings of VMDPs in this paper. The algorithms for approachability and CMDP is based pluging in VI-Zero into meta algorithms, and the corresponding sample complexity results are obtained by applying Theorem and our main result- Theorem 6.

---

Under review as a conference paper at ICLR 2022
Theorem 7 shows that the sample complexity of all three tasks are connected the leading terms are all ( (d, S HA//EE which differ by only logarithmic factors. In particular, our sample complexity for the reward free exploration (Definition 1) in the tabular setting matches the best result in Wu et al. (2020). It further shows that can easily design an sample-efficient for approachability (Definition 3) and CMDP with general convex constraints (Definition 4) in the tabular setting, with sample complexity matching the best result in Yu al. (2021) up single factor of H. Therefore, our framework while being modular enabling direct translation of reward-free RL to constrained RL, achieves sharp sample complexity guarantees. We comment that due to wearrd-free nature of our approach unlike Yu et al. (2021), we can no longer provide regret guarantees.
5 LINEAR FUNCTION APPROXIMATION: LINEAR VMDPs
In this section we consider the setting of linear function approximation and allow S and A to be infinitely large. We assume that agent has access feature map Φ S x A Rd and the return function and transitions are linear functions of the feature map. We formally define the linear VMDPs in Assumption 8 which adapts the definition of linear MDPs (Jin et al., 2020b) for VMDPS; namely, they coincide for the case of d = 1.
Assumption 8 (Linear VMDP). A VMDP M = (S,A, is said to be a linear VMDP with feature map &: S A IRd",, for any h E [H]:
(dun) over S such that for 1. There exists din unknown (signed) measures μh { ..... any (s, E S x A we have P. s,a) = (p((),, (ls, a))
(1)
Uh
2. There exists an unknown matrix Wn E Rexxdii such that for any (8, a) E x A we have ra(s, a) ())
Similar to Jin et al. (2020b), we assume that || ((ss S 1 for all (s,a) E Sx ([)]| S vdin for all h E [H), and | S Vdiin for all h [H].
Wang et al. (2020) has recently proposed a sample-efficient algorithm for reward-free exploration in linear MDPs. Utilizing that algorithm and tailoring it for our setting, we can obtain the following theoretical guarantee. The algorithm and the proof can be found in Appendix D.
Theorem 9. For linear VMDPs (Assumption 8), we have a reward-free algorithm (Definiton 1) H with MRFE (c, S 11 22),, an approachability algorithmm (Definition 3) with MAPP (E, 8) <
(dP lin 2//2/2 and an algorithm for CMDP (Definition 4) with (cMDD(C, 5) S O (d) H 8 2
The reward-free algorithm with stated sample complexity in Theorem Appendix D. it is a modified version of the reward-free algorithm introduced by Wang et al. (2020). Its sample complexity result is again obtained by adapting the results in Wang et al. (2020) for scalar- valued MDPs to the settings of VMDPs in this paper. The algorithms for approachability and CMDP based on pluging in this reward-free algorithm into our meta algorithms, and the corresponding sample complexity results are obtained by applying Theorem 5 and our main
the Algorithm 6 in
6.
Theorem 9 provides a new sample complexity result of Odd 41 /e2) for the reward-free exploration (Definition 1) in the linear setting (Assumption 8). further provides a new sample complexity result of Od H6 /e²) for both approachability (Definition 3) and CMDP (Definition 4) the linear setting (Assumption 8). To best our knowledge, this is the first sample- sample-efficiett result for constrained RL problems with linear function approximation and general convex constraints.
6
VECTOR-VALUTE MARKOV GAMES
6.1 MODEL AND PRELIMINARIES
Similar Section 2, we consider an episodic vector-valued Markov game (VMG) specified by tuple G = A,, B, H, P),,, r), where A and B are the action spaces for the min-player and max-player,
This H factor difference is due the Bernstein-type bonus used in Yu et al. (2021), which can not be adapted the reward-free setting.
7

---

Under review as a conference paper at ICLR 2022
respectively. The d-dimensional return function and the transition probabilities P, now depend on the current state and the action of both players.
Interaction protocol. In each episode, we start at a fixed initial state 81. Then, at each step h E [H] both players observe the current state 8h, take their own actions ад E A and bj E B simultancously. observe stochastic sample of the return vector Fy (Sh, ap by) along with their opponent's ss action, and causes the environment to transit to 8/+1 ~ (x 8h, ag bn)- We assume that stochastic samples of the return function also in (1), almost surely.
Policy and value function. A policy j of the min-player is a collection of H functions {pm S + A(A)) h= Similarly, a policy of the max-player is collection of H functions {u%, S A(B) M= If the players are following and v, have a₁ p(-ls) and by v--ls) at the hthh step. We use Vir S + B H) and Q% S x A x B + ()) to denote the value function and Q-value function step h under policies y and
Scalarized markoy game and Nash equilibrium. For a VMG G and E B()). we define scalar- valued Markov game Go
A, H, H.,,Pro) ro), where re = (0, r2.) S A x B [-1, 1, We use (:; and Q (., ', : 0) to denote value function and Q-value function of Go. respectively. Note that we have L.
h (s; 0) (0, Vil (s)) and Q" (s,
(0, Q (s, a, b)).
For any policy of the min-player there exists a best-response policy v4(n) of the max-player; Lee V7l-e(() (s; 0) max, Vit 0) for all (s, h) E S x [H]. We use Vu4t to denote Varr(w) Similarly, we can define (+(v) and Vt." We further know (Filar & Vrieze, 2012) that there exist policies (n²,,"), known as Nash equilibrium, satisfying the following equation for all (s, h) [H]:
min max VI (s; Vg (s; = V/ (s: = vl.e" (s; = max max V" (s
In words, it means that no player can gain anything by changing her own policy, We abbreviate A s² and Q ,²* as Vi and Qi.
6.1.1 REWARD-FRRE EXPLORATION (RFE) FOR VMGS
Similar to Section 2.1, we can define RFE algorithm for VMGs. Similarly, it consists of phases. In the exploration phase the it explores the environment without guidance of return function. Later, in the planning phase, given any B(1), it requires to output near optimal Nash equilibrium for Gg.
Definition 10 (RFE algorithm for VMGs). For any e, 0, after collecting MRFE (e. 8) episodes during the exploration phase, with probability at least 1 - 8, the algorithm for all 0 E B(1), satisfies
Vit (s1; Vt.' (81; 0) [V (s1; 0) VI 0) (s1;
V t0 (s1; 0)] Se
where (po, va) is the output of the planning phase for vector 0 as input. The function MRFE determines the sample complexity of the RFE algorithm.
6.2.2 BLACKWELL APPROACHABILITY FOR VMGS
We assume we are given a VMG and target set C. The goal of the min-player is for the return vector to lie in the set C while max-player wants the opposite. For the two-player vector-valued games it can be easily shown that the minimax theorem does no longer hold (see Section 2.1 of Abernethy et al. 2011). Namely, if for every policy of the max-pla max-player we have response such that the return is in the set, we cannot hope to find single policy for the min-player so that for every policy of the max-plan max-player the return vector lie in the set. However, approaching the set on average is possible.
Definition 11 (Blackwell approachability), We say the min-player is approaching the target C' with rate (T), if for arbitrary sequence of max-player polices v1 ,...,, yT, we have
dist Etn Vg ''' (ss), max, min, (VIl +T())
8

---

Under review as a conference paper at ICLR 2022
6.2 META-ALGORITHN FOR VMGS
Similar to Section 3, we introduce our main algorithmic framework for VMGs bridging reward-free algorithm and Blackwell approachability in VMGs. The pseudo-code displayed in Algorithm and the theoretical guarantees are provided in Theorem 12. The proof can be found in Appendix E.
Algorithm 2 Meta-algorithm for VMGs
1: Input: Reward-Free Algorithm RFE for VMG (as in Definition 10), Target Set C
2: Hyperparameters: learning rate 1y'
3: Initialize: run exploration phase of RFE for K episodes
4: Set: 0¹ [(1)
5: for f. = 2......, T
6: Obtain near optimal Nash equilibrium for 9
(p'ww") + output of planning phase of RFE for the vector 0c as input
7: Play μ for episode:
Play 2³ against max max- player playing arbitrary policy y' for one episode
and let V be the sum of vectorial returns
8: Apply online gradient ascent update for utility function u' u'()) (0, v() maxxec x):
0++1 + 1'B O + r (V argmaxxee' [0',))]
where I' B(1) is the projection into Euclidean unit ball
Theorem 12. For any choice of RFE algorithm (Definition 10) and for any E (0, and 6 e (0, if we choose K
(c/2,6/ and r/' /1/H²t, then, with probability at least 1- 8, the min- min-player in Algorithm satisfies Definition with rate a(T) = O(e/2 + (/ where log(d/8). Therefore to obtain E-optimality, the total sample complexity scales with 0//2 + 11²
6.3 TABULAR VMGS
In this section, we consider tabular VMDPs; namely, we assume that |S| S S, [A] Similar to Section 4, by utilizing VI-Zero (Liu et al., 2020) we can have the following theoretical guarantees. The algorithm and the proof can be found in Appendix E.
< A, and |B] s B.
Theorem 13. There exists a reward-free algoritiu for tabular VMGs and a right choice of hyperparameters that satisfies Definition 10 with sample complexity mRrE(c, S (min S SABI + H AB:2 /e), where + = log[dS
The theorem provides exploration in VMGs (Definition 10). It immediately follows from Theorem 13 and Theorem 12 that we can achieve total sample complexity of Ô (min in VMGs (Definition 11). Our rate for a<T') scales with plV/poy(HH)/T while the results in Yu et al. (2021) has the rate of a(T)) scaling with O(vpoly (H) (H) min,d, S)SA/T). However, require initial phase of self self-play for = OmRREE) episodes which is not needed by Yu et al. (2021).
sample complexity result of (miin
for reward-free
)) for Blackwell approachability
7 CONCLUSION
This paper provides meta algorithm that takes a reward-free RL. solver, and convert it to an algorithm for solving constrained RL problems. Our framework enables the direct translation of any progress in reward-free RL to constrained RL setting. Utilizing existing reward-free solvers, our framework provides sharp sample complexity results for constrained RL in tabular setting (matching best existing results up factor of horizon dependence), results for the linear function approximation setting. Our framework further extends tabular two-player rector-valued Markov games for solving Blackwell approachability problem.

---

Under review as a conference paper at ICLR 2022
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. JMLR Workshop and Conference Proceedings, 2011.
Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference Machine Learning, pp. 263-272 PMLR, 2017.
Moshe Babaioff, Shaddin Dughmi, Robert D. Kleinberg, and Aleksandrs Slivkins. Dynamic pricing with limited supply. TEAC, 3(1):4, 2015. Special issue for 13th ACM EC, 2012.
Omar Besbes and Assaf Zeevi. Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms. Operations Research, 57(6):1407-1422) 2009.
David Blackwell et al. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematicx, 6(1):1-8, 1956.
Kianté Brantley, Miro Dudik, Thodoris Lykouris, Sobhan Miryoosefi, Max Simchowitz, Aleksan- drs Slivkins, and Wen Sun. Constrained episodic reinforcement learning in concave-convex and knapsack settings. In Advances in Neural Information Processing Systems, volume 33, pp. 16315-16326. Curran Associates, Inc., 2020. URL www.t:ttp//tt. https::/ppooceeeiiiitt www.innn..neeieeeeeieeeeeeeeeene ps. cc/ pdd.
Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 3304-3312, PMLR, 13-15 Apr 2021. URL http:/tt///// http://poceeee.....ee mlr wwwpss/vv3///e/eee ht113////ngg1e1e html.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitatio in constrained mdps. arXiv preprint arXiv:2003.02/880 2020.
Jerzy Filar and Koos Vrieze. Competitive Markov decision processes. Springer Science & Business Media, 2012.
Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-103, 1999.
Shahin Jabbari, Matthew Joseph, Michael Kearns, Jamie Morgenstern, and Aaron Roth. Fairness in reinforcement learning. In International Conference on Machine Learning, pp. 1617-1626. PMIR, 2017.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael Jordan. short note on concen- tration incqualities for random vectors with subgaussian norm. arXiv preprint 1rXiv:1902.03736. 2019.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. International Conference on Machine Learning, pp. 4870-4879. PMLR, 2020a.
Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020b.
Hoang Minh Lc, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. CoRR, 1ets/9933.8788. 2019, URL http: /ttp:://axxaaa org/ abs/ 1903. 08738.
Qinghua Liu, Tiancheng Yu. Yu Bai, and Chi Jin. A sharp analysis of model-based reinforcement learning with self-play. arXiv preprint 2rXiv:2010.01604 2020.
10

---

Under review as a conference paper at ICLR 2022
Hongzi Mao, Mohammad Alizadeh, Ishai Menache, and Srikanth Kandula. Resource management with deep reinforcement learning. In Proceedings of the 15th ACM Workshop on Hot Topics in Networks, pp. 50-56, New York, NY. USA. 2016. Association for Computing Machinery. ISBN 9781450346610. doi: 10. 14114/9005745533055550 URL https:://// /doi otgg//..1/..../01 30055455.0055555
Sobhan Miryoosefi, Kianté Brantley, Hal Daume III, Miro Dudik, and Robert E Schapire. Reinforcement learning with convex constraints. In Advances in Neu- ral Information Processing Systems, volume 32, pp. 14093-14102. Curran Asso- httppppcccppppp/2119999 /ttp///01///eee////
ciates, Inc., 2019. URL httpss:///rcceeeeeeee 8 373e0770500007772211ftb 72d55999972998- Paper.
neurips
J Neumann. Zur theoric der gesellschaftsspiele. Mathematische annalen, 100(1):295-3200 1928.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Shuang Qiu, Xiaohan Wei, Zhuoran Yang. Jieping Ye, and Zhaoran Wang. Upper confidence primal- dual optimization: Stochastically constrained markov decision processes with adversarial losses and unknown transitions. arXiv preprint arXiv:2003. 00660, 2020.
Ralph Tyrell Rockafellar. Convex analysis. Princeton university press, 2015.
Rahul Singh, Abhishek Gupta, and Ness B Shroff. Learning markov decision processes under constraints. arXiv preprint MxXiv:2002./2435 2020.
Wen Sun, Anirudh Vemula, Byron Boots, and J Andrew Bagnell. Provably efficient imitation learning from observation alone. arXiv preprint arXiv: 1et.i9995..9945 2019.
Umar Syed and Robert E. Schapire. A game-theoretic approach to apprenticeship learning. In Pro- ceedings of the 20th International Conference on Neural Information Processing Systems, N7PS'07, pp. 1449-1456 Red Hook, NY, USA, 2007. Curran Associates Inc. ISBN 9781605603520.
Chen Tessler, Daniel J. Mankowitz, and Shie Mannor. Reward constrained policy optimization. In International Conference on Learning Representations, 2019, URL https: /ttpt::e////ppeeeieeee.. net/ forum? Sd-
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(77822:350-354 2019.
Ruosong Wang, Simon Du, Lin F Yang, and Ruslan Salakhutdinov. On reward-free reinforcement learning with linear function approximation. arXiv preprint arXh::2006.11274 2020.
Jingfeng Wu, Vladimir Braverman, and Lin F Yang. Accommodating picky customers: Regret bound and exploration complexity for multi-objective reinforcement learning. arXiv preprint arXiv:2011.13034, 2020.
Tiancheng Yu, Yi Tian, Jingzhao Zhang, and Suvrit Sra. Provably efficient algorithms for multi- objective competitive rl. arXiv preprint arXiv:2 2021.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Provably efficient reward-agnostic navigation with linear value iteration. arXiv preprint arXiv:2008.07737, 2020.
Xuezhou Zhang, Adish Singla, et al. Task-agnostic exploration in reinforcement learning, arXiv preprint arXiv:2006.094// 09497, 2020.
Brian Ziebart, Andrew Maas, Andrew Bagnell, and Anind Dey. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pp. 4433-1438. Chicago, II., USA, 2008
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pp. 928-936. 2003.
11


Reviews:
[{"review_id": "QI8_5UeuH9c", "reviewer": "Reviewer_qB13", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "I enjoyed reading this paper and I think that it has numerous merits:\n- The paper is clear and very well-written.\n- It studies an interesting topic for which optimal solutions are still not clear.\n- The connection between reward-free RL and constrained RL is very clever and presented in an intuitive way.\n- The resulting approach is indeed simple as the title suggests.\n- The approach is general and gives sample complexity guarantees to any constrained RL formulation for which reward-free algorithms exist.\n- I like the unification of constrained MDPs and approachability problems.\n\nHowever, there are still quite a few things that prevent me from rating this paper as a clear accept:\n- In general I think that the reward-free approach is celebrated by the authors a little too much without addressing its flaws. Here are a few things that I thought about (and maybe there are even more things to address):\n     1. Sample complexity vs regret. The authors do mention that \"due to reward-free nature of our approach unlike Yu et al. (2021), we can no longer provide regret guarantees\", but I think that this is a major downside to the authors approach that needs to be addressed in details. Moreover, I am wondering whether the reward-free approach is simple simply because it is sub-optimal but optimal algorithms haven't been discovered yet. Can the authors please elaborate on regret?\n     2. Lower bound. Are there any lower bounds for constrained MDPs? the authors do not mention them at all, and I think that they are crucial in order to put the presented algorithms and their guarantees in perspective. This is very related to the previous section, but again my guess is that the given guarantees have sub-optimal dependence in the number of states that may be removable with other approaches, but cannot be removed with the reward-free approach.\n     3. The sub-optimality also comes into play in the $H$ dependence. The authors mention that \"This H factor difference is due the Bernstein-type bonus used in Yu et al. (2021), which can not be adapted to the reward-free setting\", and again this reveals the big downside of the reward-free approach which is probably sub-optimal as far as I understand.\n     4. Computational complexity. The authors do not discuss computational complexity at all. How does the computational complexity of the proposed approach compare with other approaches? I am not sure what is the answer, but if it is worse then this is definitely another shortcoming of the presented approach. Anyway, it should absolutely be discussed in the paper.\n- There is not a single proof sketch in this paper! In my opinion presenting sketches for theorems 5 and 6 are crucial in order to clearly convey the ideas of the paper, and it looks to me like the authors could easily find space for them (many models are presented in much detail, and I think that some of them, e.g., linear MDPs or MGs, could go to the appendix).\n     1. I read the proof of theorem 5 in the appendix and I think that it presents a very nice idea that can and should be shown in 2-3 paragraphs in the main paper.\n     2. Theorem 6 is the main contribution of the paper and an analysis overview must be provided in the main paper including the main techniques used by the authors.", "summary_of_the_paper": "This paper proposes a meta-algorithm that takes an algorithm for reward-free RL and uses it to compute an (approximately) optimal policy for a constrained RL problem or an approachability problem. The proposed method keeps similar sample complexity guarantees to the ones provided by the reward-free algorithm, i.e., there is very small overhead.", "summary_of_the_review": "The paper presents a simple approach to an interesting (and still open) problem, but in my opinion the mentioned flaws of the approach must be addressed in much detail before the paper is published.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "5-zD5RbJYSo", "reviewer": "Reviewer_zcw7", "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": "## Strengths:\n\n- Theorem 5 is a really interesting result. This result will allow the community to use advances in the approachability setting and to the constrained RL. This allows further advances in reward-free RL to directly translate in the approachability and constrained RL setting. \n- The paper is well-written and generally clear. \n\n## Weaknesses:\n- **Constraints violation during learning?**: I’m unsure of the implication of the results in the Constrained-RL case. When working with the CMDP formulation, constraint violation during learning is a major motivation and it also brings the additional challenges of working with them (safe-exploration). I find it concerning that there is no mention of results regarding the constraint violation during the learning of the proposed algorithms or even the associated related work such as [1,2].  For instance, for tabular CMDPs and linear constraints, Liu et al [1] provide an approach that achieves $\\mathcal{O)(1)}$ constraint violation in the general setting while still achieving regret bound of $\\mathcal{\\tilde{O}(H^3)}$. I think it is important to address the constraint violation in the exploration phase, especially in terms of CMDPs, and I wonder how do the authors approach fares in this regard. \n\n- **Too much content?:** Unfortunately, the paper at times feels rushed and the reader is left out to figure the details to themselves. In particular, I felt that Section 3 is the core component but it is covered in not much detail. \nThis concern also follows the other parts of the work.  In the linear VMDPs section, applying Wang 2020 to the slightly modified setting gives us the new result for linear function approximation for constrained-RL. Although this result is new, I’m not sure if this is particularly useful. If it is, I fail to see how. Maybe the authors can motivate this further? \n\n  The setting also changes significantly from MDPs to Markov games. I’m not sure if squeezing this component in the last two pages was the best approach. Moreover, the motivation for VMGs is missing from the introduction. I also don’t get why we don’t have a constrained-RL equivalent for the VMGs (Does the Blackwell approachability encompasses that component too?).  I’m not familiar with the literature from Markov games so my concerns with this section should be taken with a grain of salt. \n\n- **Empirical experiments:** Although, I understand that the main contribution of the work is theoretical, however empirical experiments in the constrained-RL setting can shed some light on how the algorithm performs in practice wrt the behaviour during the learning. ", "summary_of_the_paper": "The paper applies the techniques from reward-free RL literature to the constrained RL setting. They propose a meta-algorithm that takes a reward-free RL solver and uses it to solve the approachability and constrained-RL problems with convex constraints. The proposed approach comes with an overhead factor that is logarithmic in the number of samples.   They apply this approach to provide sharp analysis on three different settings: tabular VMDPs, linear VMDPs and two-player VMGs. ", "summary_of_the_review": "I think there are some really interesting results in this work, however, there seems to be a conflict in the motivation (constrained-RL problems) and methodology (reward-free RL solutions). On a high level, the exploration phase in the reward-free RL seems orthogonal to the safe exploration problem in Constrained-RL. If exploration is not an issue, then the motivation behind the tabular and linear VMDPs is not clear (as one can use other CMDP solvers).  I wonder applying the methods from the reward-free literature to the constrained-RL setting gives us any meaningful results. I think in the current form, it is not clear what the benefits of such an approach are. Hence, I’m voting for a weak reject. I’m happy to revise the score if the authors can further motivate the benefits of applying RL-free methods to the constrained-RL setting.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "3aI8Q2gFyMd", "reviewer": "Reviewer_ohJk", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "\nWhile the paper is well executed and seems sound to me (I didn't have time to check all the proofs), I have doubts due to the limited technical novelty. I understand the proposed meta-structure allows to account for multiple problems, but the core idea is not very novel.\nAt a high level, the idea is that the considered problems can be formulated as a saddle point problem that can be solved with different incremental techniques. A standard approach is to use a dual approach where a best response algorithm is used to solve for the optimal policy and an incremental (gradient) algorithm is used to update the other player.\nThis approach was studied for example in (Miryoosefi et al., 2019) or (Efroni et al., 2020). In particular, the second approach used an estimate of the model to compute an optimistic policy (in the best response step), and they were able to prove regret guarantees. In this paper, the idea is to leverage reward-free techniques instead of estimating the model. Hence my doubts.\nHowever, I acknowledge that, as far as I know, the proposed framework allows to derive results in new settings. \n\nFurthermore, I think the result can be improved. In particular, the authors claim that Bernstein techniques cannot be used for RFE. However, [1] shows the opposite. Through the use of Bernstein technique, they were able to improve the sample complexity by a factor $H$ in RFE. So, could you please explain why it is not possible in this setting? I think this is quite a limitation of the current paper.\n\n\nMinor comments:\n- In section 3, you said that the minmax problem is convex in $\\pi$. It should be clarified since it's not convex in $\\pi$ but rather in the occupancy measure of a policy.\n- First paragraph of Sec 3: ready introduce -> ready to introduce\n- First paragraph of Sec 6.1.1: phase the it -> phase, it\n\n\n[1] Menard et al. Fast active learning for pure exploration in reinforcement learning. ICML 2021\n\n", "summary_of_the_paper": "The paper introduces a connection between reward-free and constrained MDPs. The interesting result in the paper is the fact that it is possible to use any reward-free method to solve constrained and approachability problems. In particular, they show that starting from an RFE method with sample guarantees, it is possible to obtain guarantees in these settings paying only a small cost. This meta-framework can be used to solve many different problems (e.g., tabular and linear problems).\n", "summary_of_the_review": "I have concerns about novelty and contributions, and the fact the bounds may be improved.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a general solution method for constrained RL problems using reward-free exploration. While the reviewers found this reduction interesting in general, they had concerns about the price of this reduction in general (such as the increased regret or for suboptimal dependence of the bounds on some problem parameters), which is to be paid in exchange for the simplicity and flexibility of the proposed approach. This, coupled with the limited technical novelty used in the derivations, made all reviewers think that this is a borderline paper, and I also agree with this assessment. The paper could benefit a lot from presenting more evidence of the benefits of their approach (either theoretically or empirically). Based on the above, unfortunately, I am not able to recommend acceptance at this point.
Decision: Reject