Year: 2021

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.

text: 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.

heading: 1 INTRODUCTION
text: In a wide range of modern reinforcement learning (RL) applications, it is not sufficient for the learning agents to only maximize a 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), scheduling of resources on a computer cluster (Mao et al., 2016), imitation learning (Syed & Schapire, 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 to a subfield—constrained RL, which focuses on designing efficient algorithms to find near-optimal policies for RL 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 et 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 is highly nontrivial to translate the progress in the unconstrained RL to the constrained setting.
On the other hand, reward-free RL—proposed in Jin et al. (2020a)—is a framework for the unconstrained 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 a 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 a 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.,
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 a simple approach to 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-free 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 a reward-free RL 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-free RL.
Our framework enables direct translation of any progress in reward-free RL to constrained RL. Leveraging recent advances in reward-free RL, our 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 particular,
• Tabular setting: Our work achieves sample complexity of Õ(min{d, S}H4SA/ 2) for all three tasks of reward-free RL for Vector-valued MDPs (VMDP), approachability, and RL with general convex constraints. Here d is the dimension of VMDP or the number of constraints, S,A are the number of states and actions, H is the horizon, and is the error tolerance. It matches the best existing results up to a factor of H .
• Linear setting: Our work provides new sample complexity of Õ(d3linH6/ 2) for all three tasks above for linear MDPs. To our best 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( /2 + √ H2ι/T ) at the cost of this
O( ) bias in regret as well as additional samples for preprocessing.

heading: 1.1 RELATED WORK
text: In this section, we review the related works on three tasks studied in this paper—reward-free RL, approachability, and constrained RL.
Reward-free RL. Reward-free exploration has been formalized by Jin et al. (2020a) for the tabular setting. Furthermore, Jin et al. (2020a) proposed an algorithm which has sample complexity Õ(poly(H)S2A/ 2) outputting -optimal policy for arbitrary number of reward functions. More
1The presented sample complexities are all under the L2 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/L∞ normalization conditions. While the results in Wu et al. (2020) can be directly adapted to our setting as 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.
recently, Zhang et al. (2020); Liu et al. (2020) propose algorithm VI-Zero with sharp sample complexity of Õ(poly(H) log(N)SA/ 2) capable of handling N fixed reward functions. Wang et 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 to find the near-optimal policies for an arbitrary number of (linear) reward functions within a sample complexity of Õ(poly(H)d3lin/ 2). All results mentioned above are for scalar-valued MDPs. For the vector-valued MDPs (VMDPs), very recent work of Wu et al. (2020) designs a reward-free algorithm with sample complexity guarantee Õ(poly(H) min{d, S}SA/ 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 Õ(poly(H) min{d, S}SA/ 2) for approachability in VMDPs and Õ(poly(H) min{d, S}SAB/ 2) 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 et al. (2021); Singh et al. (2020). All these works are also limited to linear constraints except Brantley et al. (2020) which extends their approach to general convex constraints achieving sample complexity of Õ(poly(H)d2S2A/ 2) . However, Brantley et al. (2020) requires solving a large-scale convex optimization sub-problem. The best result for constrained RL with general convex constraints can be achieved by the approachability-based algorithm in Yu et al. (2021) obtaining sample complexity of Õ(poly(H) min{d, S}SA/ 2). Technically, our meta-algorithm is 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 RL, 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.

heading: 2 PRELIMINARIES AND PROBLEM SETUP
text: We consider an episodic vector-valued Markov decision process (VMDP) specified by a tuple M = (S,A, H,P, r), where S is the state space, A is the action space, H is the length of each episode, P = {Ph}Hh=1 is the collection of unknown transition probabilities with Ph(s′ | s, a) equal to the probability of transiting to s′ after taking action a in state s at the hth step, and r = {rh : S × A → B(1)}Hh=1 is a collection of unknown d-dimensional return functions, where B(r) is the d-dimensional Euclidean ball of radius r centered at the origin.
Interaction protocol. In each episode, agent starts at a fixed initial state s1. Then, at each step h ∈ [H], the agent observes the current state sh, takes action ah, receives stochastic sample of the return vector rh(sh, ah), and it causes the environment to transit to sh+1 ∼ Ph(· | sh, ah). We assume that stochastic samples of the return function are also in B(1), almost surely.
Policy and value function. A policy π of an agent is a collection of H functions {πh : S → ∆(A)}Hh=1 that map states to distribution over actions. The agent following policy π, picks action ah ∼ πh(sh) at the hth step. We denote Vπh : S → B(H) as the value func-
tion at step h for policy π, defined as Vπh(s) := Eπ [∑H h′=h rh′(sh′ , ah′) | sh = s ] . Similarly, we denote Qπh : S × A → B(H) as the Q-value function at step h for policy π, where Qπh(s, a) := Eπ [∑H h′=h rh′(sh′ , ah′) | sh = s, ah = a ] .
Scalarized MDP. For a VMDP M and θ ∈ B(1), we define scalar-valued MDP Mθ = (S,A, H,P, rθ), where rθ = {〈θ, rh〉 : S ×A → [−1, 1]}Hh=1. We denote V πh (·;θ) : S → [−H,H] as the scalarized value function at step h for policy π, defined as
V πh (s;θ) := Eπ [∑H h′=h〈θ, rh′(sh′ , ah′)〉 | sh = s ] = 〈θ,Vπh(s)〉.
Similarly, we denote Qπh(·;θ) : S ×A → [−H,H] as the scalarized Q-value function at step h for policy π, where
Qπh(s, a;θ) := Eπ [∑H h′=h〈θ, rh′(sh′ , ah′)〉 | sh = s, ah = a ] = 〈θ,Qπh(s, a)〉.
For a fixed θ ∈ Rd, there exists an optimal policy π?θ, maximizing value for all states (Puterman, 2014); i.e., V π ? θ
h (s;θ) = supπ V π h (s;θ) for all s ∈ S and h ∈ [H]. We abbreviate V π
? θ (·;θ) and
Qπ ? θ (·;θ) as V ?(·;θ) and Q?(·;θ) respectively.

heading: 2.1 REWARD-FREE EXPLORATION (RFE) FOR VMDPS
text: 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 1. 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 {skh, akh}(k,h)∈[K]×[H] in 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 is revealed to the agent, i.e. {rkh}(k,h)∈[K]×[H]. Based on the episodes collected during the exploration phase, the agent outputs the near-optimal policies ofMθ given an arbitrary number of vectors θ ∈ B(1). Definition 1 (Reward-free algorithm for VMDPs). For any , δ > 0, after collecting mRFE( , δ) episodes during the exploration phase, with probability at least 1− δ, the algorithm satisfies
∀θ ∈ B(1) : V ?1 (s1;θ)− V πθ 1 (s1;θ) ≤ , (1)
where πθ is the output of the planning phase for vector θ as input. The function mRFE determines the sample complexity of the RFE algorithm. Remark 2. Standard reward-free setup concerns MDPs with scalar reward, and requires the algorithm to find the near-optimal policies for N different prespecified reward functions in the planning phase, where the sample complexity typically scales with logN . This type of results can be adapted into a guarantee in the form of (1) for VMDP by -covering of θ over B(1) and a modified concentration arguments (see the proofs of Theorem 7 and Theorem 13 for more details).

heading: 2.2 APPROACHABILITY FOR VMDPS
text: In this section we provide the description for the approachability 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 a 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 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.
1RFE for VMDPs is also called preference-free exploration problem in Wu et al. (2020)
Definition 3 (Approachability algorithm for VMDPs). For any , δ > 0, after collecting mAPP( , δ) episodes, with probability at least 1− δ, the algorithm satisfies
dist(Vπ out
1 (s1), C) ≤ min π dist(Vπ1 (s1), C) + , (2)
where πout is the output of the algorithm and dist(x, C) is the Euclidean distance between point x and set C. The function mAPP determines the sample complexity of the algorithm.

heading: 2.3 CONSTRAINED MDP (CMDP) WITH GENERAL CONVEX CONSTRAINTS
text: In this section we 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 are akin to r in our case). Although, the original definition only allows for linear constraints, we consider the more general case of arbitrary convex constraints. More formally, consider a VMDPM, a cost function c = {ch : S ×A → [−1, 1]}Hh=1, and a convex constraint set C. The agent goal is to compete against the following benchmark:
min π Cπ1 (s1) s.t. V π 1 (s1) ∈ C, where Cπh = Eπ [∑H h′=h ch′(sh′ , ah′) | sh = s ] .
Definition 4 (Algorithm for CMDP). For any , δ > 0, after collecting mCMDP( , δ) episodes, with probability at least 1− δ, the algorithm satisfiesC πout 1 (s1)− min π:Vπ1 (s1)∈C Cπ1 (s1) ≤ dist ( Vπ out 1 (s1), C ) ≤ , (3)
where πout is the output of the algorithm. The function mCMDP determines the sample complexity of the algorithm.
As also mentioned in the prior works (Miryoosefi et al., 2019; Yu et al., 2021), we formally show in the following theorem that approachability task (Definition 3) can be considered more general compared to 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 a negligible overhead. The idea is to incorporate cost into the constraint set 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 algorithm (Definition 3) with sample complexity mAPP, we can design an algorithm for CMDP (Definition 4) with sample complexity mCMDP, satisfying
mCMDP( , δ) ≤ O ( mAPP ( 6 , δ 12H ) + H 2 log[dH/ δ] 2 ) · log 1 .

heading: 3 META-ALGORITHM FOR VMDPS
text: In this section, equipped with preliminaries discussed in Section 2, we are ready introduce our main algorithmic framework for VMDPs bridging reward-free RL and approachability.
Before introducing the algorithm, we explain the intuition behind it. By Fenchel’s duality (similar to Yu et al. 2021), one can show that
min π dist(Vπ1 (s1, C)) = min π max θ∈B(1)
[ 〈θ,Vπ1 (s1, C)〉 −max
x′∈C 〈θ,x′〉
] .
It satisfies the minimax conditions since it’s concave in θ and convex in π (by allowing mixture policies); therefore, minimax theorem Neumann (1928) implies that we can equivalently solve
max θ∈B(1) min π
[ 〈θ,Vπ1 (s1, C)〉 −max
x′∈C 〈θ,x′〉
] .
This max-min form allows us to use general technique of Freund & Schapire (1999) for solving a max-min by repeatedly playing a no-regret online learning algorithm as the max-player against best-response for the min-player. In particular, for a fixed θ, minimizing over π is equivalent to finding optimal policy for scalarized MDP M−θ. To achieve this, we can utilize a reward-free oracle as in Definition 1. On the other hand for θ-player we are able to use online gradient descent (Zinkevich, 2003). By combining ideas above, we obtain Algorithm 1.
Algorithm 1 Meta-algorithm for VMDPs 1: Input: Reward-Free Algorithm RFE for VMDPs (as in Definiton 1), Target Set C 2: Hyperparameters: learning rate ηt 3: Initialize: run exploration phase of RFE for K episodes 4: Set: θ1 ∈ B(1) 5: for t = 1, 2, . . . , T do 6: Obtain near optimal policy forM−θt :
πt ← output of planning phase of RFE for preference vector −θt
7: Estimate Vπ t
1 (s1) using one episode:
Run πt for one episode and let v̂t be the sum of vectorial returns
8: Apply online gradient ascent update for utility function ut(θ) = 〈θ, v̂t〉 −maxx∈C〈θ,x〉: θt+1 ← ΓB(1)[θt + ηt(v̂t − argmaxx∈C〈θt,x〉)]
where ΓB(1) is the projection into Euclidean unit ball 9: Let πout be uniform mixture of {π1, . . . , πT }
10: Return πout
Theorem 6. There exists an absolute constant c, such that for any choice of RFE algorithm (Definition 1) and for any ∈ (0, H] and δ ∈ (0, 1], if we choose
T ≥ c ( H2ι/ 2), K ≥ mRFE( /2, δ/2), and ηt = √ 1/(H2t),
where ι = log(d/δ); then, with probability at least 1− δ, Algorithm 1 outputs an -optimal policy for the approachability (Equation 2). Therefore, we have mAPP( , δ) ≤ O(mRFE( /2, δ/2) +H2ι/ 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 is provided in Appendix B. Equipped with this theorem, since we have already shown the connection between approachability and constrained RL in Theorem 5, any results for RFE can be directly translated to results for constrained RL.

heading: 4 TABULAR VMDPS
text: In this section, we consider tabular VMDPs; namely, we assume that |S| ≤ S and |A| ≤ A. Utilizing prior work on tabular setting, we describe our choice of reward-free algorithm.
In the exploration phase, we use VI-Zero proposed by Liu et al. (2020). It can be seen as UCB-VI (Azar et al., 2017) with zero reward. Intuitively, the value function computed in the algorithm measures the level of uncertainty and incentivizes the greedy policy to visit underexplored states. The output of VI-Zero is P̂out, which is an estimation of the transition dynamics.
In the planning phase, given θ ∈ B(1) we can use any planning algorithm (e.g., value iteration) for M̂θ = (S,A, H, P̂out, 〈θ, r̂〉) where r̂ is empirical estimate of r using collected samples {rkh}. The following theorem state theoretical guarantees for tabular VMDPs. Proof of Theorem 7 and more details can be found in Appendix C. Theorem 7. For tabular VMDP, we have a reward-free algorithm (Definiton 1) with mRFE( , δ) ≤ O(min{d, S}H4SAι/ 2 + H3S2Aι2/ ), an algorithm for approachability (Definition 3) with mAPP( , δ) ≤ O(min{d, S}H4SAι/ 2 +H3S2Aι2/ ) , and an algorithm for CMDP (Definition 4) with mCMDP( , δ) ≤ O(min{d, S}H4SAι2/ 2 +H3S2Aι3/ ).
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 on pluging in VI-Zero into our meta algorithms, and the corresponding sample complexity results are obtained by applying Theorem 5 and our main result— Theorem 6.
Theorem 7 shows that the sample complexity of all three tasks are connected—the leading terms are all Õ(min{d, S}H4SA/ 2) 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 we 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 et al. (2021) up to a single factor of H . 2 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 reward-free nature of our approach unlike Yu et al. (2021), we can no longer provide regret guarantees.

heading: 5 LINEAR FUNCTION APPROXIMATION: LINEAR VMDPS
text: 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 to a feature map φ : S ×A → Rdlin 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 VMDPM = (S,A, H,P, r) is said to be a linear VMDP with a feature map φ : S ×A → Rdlin , if for any h ∈ [H]:
1. There exists dlin unknown (signed) measures µh = {µ(1)h , . . . , µ (dlin) h } over S such that for
any (s, a) ∈ S ×A we have Ph(· | s, a) = 〈µ(·),φ(s, a)〉.
2. There exists an unknown matrix Wh ∈ Rd×dlin such that for any (s, a) ∈ S × A we have rh(s, a) = Whφ(s, a).
Similar to Jin et al. (2020b), we assume that ‖φ(s, a)‖ ≤ 1 for all (s, a) ∈ S ×A, ‖µh(S)‖ ≤ √ dlin
for all h ∈ [H], and ‖Wh‖ ≤ √ dlin 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) with mRFE( , δ) ≤ O(d3linH6ι2/ 2), an approachability algorithm (Definition 3) with mAPP( , δ) ≤ O(d3linH6ι2/ 2) and an algorithm for CMDP (Definition 4) with mCMDP( , δ) ≤ O(d3linH6ι3/ 2).
The reward-free algorithm with stated sample complexity in Theorem 9 is the Algorithm 6 in 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 scalarvalued MDPs to the settings of VMDPs in this paper. The algorithms for approachability and CMDP is 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 result—Theorem 6.
Theorem 9 provides a new sample complexity result of Õ(d3linH6/ 2) for the reward-free exploration (Definition 1) in the linear setting (Assumption 8). It further provides a new sample complexity result of Õ(d3linH6/ 2) for both approachability (Definition 3) and CMDP (Definition 4) in the linear setting (Assumption 8). To best our knowledge, this is the first sample-efficient result for constrained RL problems with linear function approximation and general convex constraints.

heading: 6 VECTOR-VALUED MARKOV GAMES

heading: 6.1 MODEL AND PRELIMINARIES
text: Similar to Section 2, we consider an episodic vector-valued Markov game (VMG) specified by a tuple G = (S,A,B, H,P, r), whereA and B are the action spaces for the min-player and max-player,
2This 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.
respectively. The d-dimensional return function r 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 s1. Then, at each step h ∈ [H], both players observe the current state sh, take their own actions ah ∈ A and bh ∈ B simultaneously, observe stochastic sample of the return vector rh(sh, ah, bh) along with their opponent’s action, and it causes the environment to transit to sh+1 ∼ Ph(· | sh, ah, bh). We assume that stochastic samples of the return function are also in B(1), almost surely.
Policy and value function. A policy µ of the min-player is a collection of H functions {µh : S → ∆(A)}Hh=1. Similarly, a policy ν of the max-player is a collection of H functions {νh : S → ∆(B)}Hh=1. If the players are following µ and ν, we have ah ∼ µ(·|s) and bh ∼ ν(·|s) at the hth step. We use Vµ,νh : S → B(H) and Q µ,ν h : S ×A× B → B(H) to denote the value function and Q-value function at step h under policies µ and ν.
Scalarized markov game and Nash equilibrium. For a VMG G and θ ∈ B(1), we define scalarvalued Markov game Gθ = (S,A, H,P, rθ), where rθ = {〈θ, rh〉 : S ×A×B → [−1, 1]}Hh=1. We use V µ,νh (·;θ) and Q µ,ν h (·, ·, ·;θ) to denote value function and Q-value function of Gθ, respectively. Note that we have V µ,νh (s;θ) = 〈θ,V µ,ν h (s)〉 and Q µ,ν h (s, a, b;θ) = 〈θ,Q µ,ν h (s, a, b)〉.
For any policy of the min-player µ, there exists a best-response policy ν†(µ) of the max-player; i.e. V µ,ν†(µ)h (s;θ) = maxν V µ,ν h (s;θ) for all (s, h) ∈ S × [H]. We use V µ,† to denote V µ,ν†(µ). Similarly, we can define µ†(ν) and V †,ν . We further know (Filar & Vrieze, 2012) that there exist policies (µ?, ν?), known as Nash equilibrium, satisfying the following equation for all (s, h) ∈ S × [H]:
min µ max ν
V µ,νh (s;θ) = V µ?,† h (s;θ) = V µ?,ν? h (s;θ) = V †,ν? h (s;θ) = maxν min µ V µ,ν(s;θ)
In words, it means that no player can gain anything by changing her own policy. We abbreviate V µ ?,ν?
h and Q µ?,ν? h as V ? h and Q ? h.

heading: 6.1.1 REWARD-FREE EXPLORATION (RFE) FOR VMGS
text: Similar to Section 2.1, we can define RFE algorithm for VMGs. Similarly, it consists of two 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 Gθ. Definition 10 (RFE algorithm for VMGs). For any , δ > 0, after collecting mRFE( , δ) episodes during the exploration phase, with probability at least 1− δ, the algorithm for all θ ∈ B(1), satisfies
V µθ,†1 (s1;θ)− V †,νθ 1 (s1;θ) = [V µθ,† 1 (s1;θ)− V ?1 (s1;θ)] + [V ?1 (s1;θ)− V †,νθ 1 (s1;θ)] ≤
where (µθ, νθ) is the output of the planning phase for vector θ as input. The function mRFE determines the sample complexity of the RFE algorithm.

heading: 6.1.2 BLACKWELL APPROACHABILITY FOR VMGS
text: We assume we are given a VMG G and a 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-player we have a response such that the return is in the set, we cannot hope to find a single policy for the min-player so that for every policy of the 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 ν1, . . . , νT , we have
dist( 1T ∑T t=1 V µt,νt 1 (s1), C) ≤ maxν minµ dist(V µ,ν 1 (s1), C) + α(T ).

heading: 6.2 META-ALGORITHM FOR VMGS
text: Similar to Section 3, we introduce our main algorithmic framework for VMGs bridging reward-free algorithm and Blackwell approachability in VMGs. The pseudo-code is displayed in Algorithm 2 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 ηt 3: Initialize: run exploration phase of RFE for K episodes 4: Set: θ1 ∈ B(1) 5: for t = 1, 2, . . . , T do 6: Obtain near optimal Nash equilibrium for Gθt :
(µt, ωt)← output of planning phase of RFE for the vector θt as input 7: Play µt for one episode:
Play µt against max-player playing arbitrary policy νt for one episode and let v̂t be the sum of vectorial returns
8: Apply online gradient ascent update for utility function ut(θ) = 〈θ, v̂t〉 −maxx∈C〈θ,x〉: θt+1 ← ΓB(1)[θt + ηt(v̂t − argmaxx∈C〈θt,x〉)]
where ΓB(1) is the projection into Euclidean unit ball
Theorem 12. For any choice of RFE algorithm (Definition 10) and for any ∈ (0, H] and δ ∈ (0, 1], if we choose K = mRFE( /2, δ/2) and ηt = √ 1/H2t ; then, with probability at least
1− δ, the min-player in Algorithm 2, satisfies Definition 11 with rate α(T ) = O( /2 + √ H2ι/T ) where ι = log(d/δ). Therefore to obtain -optimality, the total sample complexity scales with O(mRFE( /2, δ/2) +H2ι/ 2).

heading: 6.3 TABULAR VMGS
text: In this section, we consider tabular VMDPs; namely, we assume that |S| ≤ S, |A| ≤ A, and |B| ≤ B. 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.
Theorem 13. There exists a reward-free algorithm for tabular VMGs and a right choice of hyperparameters that satisfies Definition 10 with sample complexity mRFE( , δ) ≤ O(min{d, S}H4SABι/ 2 +H3S2ABι2/ ), where ι = log[dSABH/( δ)].
The theorem provides a new sample complexity result of Õ(min{d, S}H4SABι/ 2) for reward-free exploration in VMGs (Definition 10). It immediately follows from Theorem 13 and Theorem 12 that we can achieve total sample complexity of Õ(min{d, S}H4SABι/ 2) for Blackwell approachability in VMGs (Definition 11). Our rate for α(T ) scales with Õ( √ poly(H)/T ) while the results in
Yu et al. (2021) has the rate of α(T ) scaling with Õ( √
poly(H) min{d, S}SA/T ). However, we require initial phase of self-play for K = O(mRFE) episodes which is not needed by Yu et al. (2021).

heading: 7 CONCLUSION
text: This paper provides a 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 to factor of horizon dependence), new results for the linear function approximation setting. Our framework further extends to tabular two-player vector-valued Markov games for solving Blackwell approachability problem.

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

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).