In many practical applications of online reinforcement learning (RL) (e.g., safety, resource constraints), there exist additional constraints on the learned policy in the sense that it also needs to ensure that the expected total utility (cost, resp.) exceeds a given threshold (is below a threshold, resp.). Such problems are formulated as constrained Markov Decision Processes (CMDPs) (Altman, 1999;Efroni et al., 2020) where the agent gets a reward (r) and utility (g) depending on the state and action. In an episodic CMDP, starting from initial state x 1 , the goal is to maximize ⇡ V ⇡ r,1 (x 1 ) subject to V ⇡ g,1 (x 1 ) b, where V ⇡ r,1 (x 1 ) is the cumulative reward value function (defined in (3)) and V ⇡ g,1 (x 1 ) is the cumulative utility value function respectively when the agent follows the policy ⇡.
To develop provably efficient model-free algorithms for CMDPs, most of the prior works (Wei et al., 2021b;Ghosh et al., 2022;Liu et al., 2021a;Ding et al., 2020Ding et al., , 2021) ) seek to minimize the following metrics
where V ⇤ r,1 (x 1 ) is the optimal reward value function. Prior works (Ghosh et al., 2022;Liu et al., 2021a) have shown that Õ( p T ) regret and zero constraint violation are achievable with high-probability. An astute reader may note that in the violation metric defined in (1), a large violation (V ⇡ k g,1 (x 1 ) < b) at an episode can be offset by a strictly feasible policy (V ⇡ k g,1 (x 1 ) > b) at another episode. In particular, consider the sequence of policies {⇡ k } K k=1 , V ⇡ k g,1 (x 1 ) = b + 1 at odd episode k, and V ⇡ k g,1 (x 1 ) = b 1 at even episode. Then
g,1 (x 1 )) 0, even though such a sequence of policies violates the constraints in half of the episodes. Thus, the number of episodes where employed policies are not close to satisfying the constraint can grow sub-linearly even when they achieve zero violation by (1).
Clearly, the above is not a desired setting. Thus, in this paper, we seek to minimize the regret along with the following hard constraint violation:
(2) Subsequently, we denote the violation metric in (1) as soft violation. The example we provided in the previous paragraph shows that even zero soft violation may lead to hard constraint violation that grows linearly with the number of episodes. However, if the hard constraint violation grows sub-linearly, then the number of episodes where the policy violates the constraint by any fixed non-zero amount which is independent of K can only grow sub-linearly with the number of episodes. Efroni et al. (2020) seeks to minimize such hard constraints defined in (2). However, they consider the tabular set-up and proposed algorithms which are linear programming (LP)-based and model-based. The regret and violation scale polynomially with the number of states in the paper. Thus, those results would not be useful for large-scale RL applications, where the number of states could be infinite. To address this curse of dimensionality, modern RL has adopted function approximation techniques to approximate the (action-)value function of a policy, which greatly expands the potential reach of RL, especially via deep neural networks. Model-based and LP-based algorithms are computationally difficult to extend to large-scale systems (Chen et al., 2021). Motivated by this, we aim to address the following open question:
Can we design a model-free algorithm with sub-linear regret and sub-linear hard constraint violation for CMDPs with function approximation?
Contribution: To answer the above question, we consider CMDPs with linear function approximation, where the transition dynamics and the reward function can be represented as a linear function of some known feature mapping. Our main contributions are as follows.
• We show that our proposed algorithm achieves Õ( p d 3 H 3 T ) regret and Õ( p d 3 H 3 T ) (hard) constraint violation bounds with a high probability, where d is the dimension of the feature mapping, H is the length of the episode, and T is the total number of steps.
• Our bounds are attained without explicitly estimating the unknown transition model or requiring a simulator, and they depend on the state space only through the dimension of the feature mapping. To the best of knowledge, these sub-linear bounds for regret and hard constraints are the first such results for model-free online RL algorithms for CMDPs with function approximations. Since linear CMDP contains tabular setup, as a by-product, our result also provides the first sub-linear regret and sub-linear hard constraint bounds even for the tabular setup under the model-free setup or using primal-dual approach.
• This is the first result that shows that Õ( p T ) regret and hard violation can be achieved using primal-dualbased approach since all the existing primal-dual approaches give soft constraint violation bound. Our main results are achieved by a novel approach of tuning the dual variable within each episode rather than updating at the end of the episodes (as done in existing approaches). In particular, we tune the dual variable within each episode to achieve a policy such that the estimated utility value function would exceed b by a small amount indicating the perfect trade-off between reward and utility maximization. This turns out to be the key to achieving hard-constraint violation bound.
Model-based RL algorithms have been proposed for the CMDP (Efroni et al., 2020;Singh et al., 2020;Brantley et al., 2020;Zheng and Ratliff, 2020;Kalagarla et al., 2020;Liu et al., 2021a;Ding et al., 2021). Apart from Efroni et al. (2020) and Liu et al. (2021a) (OptPess-LP), none of the other papers considered the hard constraint bound in (2). Both the papers assumed finite state-space. Naturally, the proposed algorithms there achieved regret bound which scales polynomially with the cardinality of the state-space. Hence, such results cannot cope with the large state space observed in many MDP problems. Moreover, both Efroni et al. (2020) and Liu et al. (2021a) consider LPbased approaches. Further, Liu et al. (2021a) assumes the knowledge of a strictly feasible policy in order to bound which we do not assume. In Section 3, we detail the limitations of existing LP-based approaches for unconstrained linear MDP (Neu and Pike-Burke, 2020;Neu and Okolo, 2023;Lakshminarayanan et al., 2017;Bas-Serrano et al., 2021) and the advantages of our approaches compared to a potential extension of those LP-based approaches to linear CMDP. In the bandit setup, Chen et al. (2022); Pacchiano et al. (2021) consider hard violation for linear bandit setup. Note that the bandit setting can be viewed as a degenerate single-state RL, and bandit settings do not have a state transition kernel associated with them. Hence, the approaches for the linear bandit setup cannot be extended to the linear MDP setup. Furthermore, the approaches in the above paper are not primal-dual based. Recently, Guo et al. (2022) proposed a primal-dual algorithm that obtains sublinear regret and hard constraint violation bound in the bandit setup. However, such an approach cannot be extended to the episodic RL setup (Appendix I). Ding et al. (2020); Xu et al. (2021) proposed policygradient based model-free approaches. However, they require 'simulator' or generative model Azar et al. (2012). Recently, model-free RL algorithms without simulators have also been proposed (Wei et al., 2021b;Ghosh et al., 2022) to solve CMDP. Only Ghosh et al. (2022) considered the large state-space scenario in the linear CMDP setting. However, all the aforementioned works consider soft constraint violation (cf.( 1)) rather the hard constraint violation (cf.( 2)). Since the focus is different our algorithm and analysis are significantly different. Please see Section 4 for more details. We do not assume Slater's condition (i.e., a stirctly feasible policy exists), unlike all the existing approaches. Thus, our analysis does not rely on strong duality. Amani et al. (2021) proposed a RL algorithm for the scenario where a constraint needs to be satisfied at each step of an episode. We consider a constraint where the cumulative utility over an episode must exceed a threshold. Hence, the set of constraints is fundamentally different. Further, unlike in Amani et al. (2021), we do not assume that a safe policy is known.
We consider an episodic constrained MDP, denoted by (S, A, , H, r, g) where S is the state space, A is the action space, H is the fixed length of each episode, = { h } H h=1 is a collection of transition probability measures, r = {r h } H h=1 is a collection of reward functions, and g = {g h } H h=1 is a collection of utility functions. We assume that S is a measurable space with possibly infinite number of elements, A is a finite action set. h (•|x, a) is the transition probability kernel which denotes the probability to reach a state when action a is taken at state x. r h : S ⇥ A ! [0, 1], and g h : S ⇥A ! [0, 1] and are assumed to be deterministic. However, one can readily extend to settings when r h and g h are random.
Each episode k 2 [K] starts with a fixed state x 1 . It can be readily generalized to the setting where x 1 is drawn from a distribution. At each step h 2 [H] in episode k, the agent observes state x k h 2 S, picks an action a k h 2 A, receives a reward r h (x k h , a k h ), and a utility g h (x k h , a k h ). The MDP evolves to
The episode terminates at step H + 1. Without loss of generality, we assume that r H+1 = g H+1 = 0. In this paper, we consider the challenging scenario where the agent only observes the bandit information r h (x k h , a k h ) and g h (x k h , a k h ) at the visited state-action pair (x k h , a k h ). The policy-space of an agent is (A|S, H);
Here (A) is the probability simplex over the action space. For any
denote the expected value of the total reward function starting from step h and state x when the agent selects action using the policy
where is taken with respect to the policy ⇡ and the transition probability kernel . Let Q ⇡ r,h (x, a) denote the expected value of the total reward starting from step h and the state-action pair (x, a) and follows the policy
Similarly, we define the value function for the utility V ⇡ g,h (x), and the action-value function for the utility Q ⇡ g,h (x, a). We denote V ⇡ j,h (x), and Q ⇡ j,h (x, a) for j = r, g. We observe
) for j = r, g. Using this notation, Bellman's equation associated with the policy ⇡ becomes
The objective of the learning agent is to find an optimal solution to the following problem maximize ⇡ V ⇡ r,1 (x 1 ), subject to V ⇡ g,1 (x 1 ) b.
(5) Note that even though we have only one constraint, it can be readily generalized to the scenario with multiple constraints. Further, constraints like V ⇡ g,1 (x 1 ) b can also be accommodated. In order to avoid trivial solutions, we consider b 2 (0, H]. We denote the optimal policy as ⇡ ⇤ which solves the above optimization problem. Since ⇡ ⇤ is obtained by having complete information, it is denoted as the best policy in hindsight. The CMDP setup is standard (Efroni et al., 2020).
Without any constraint information a priori, an agent cannot know the policies that satisfy the constraint. Instead, we allow the policy to violate the constraint and minimize the regret while minimizing the total constraint violations over the K episodes. We now define the performance metric that we seek to minimize.
Performance Metric: Let the policy employed by the agent at episode k be ⇡
The performance metric we consider is the following
where
b, then there is no violation. Thus, we define the total violation as the cumulative sum of all constraint violations over all the episodes. Note the difference with the constraint violation metric (cf. ( 1)) considered in the existing literature (Ghosh et al., 2022;Ding et al., 2020Ding et al., , 2021;;Wei et al., 2021a). In (1), if V ⇡ k g,1 (x 1 ) b it can negate the violation V ⇡ k g,1 (x 1 ) < b in metric (1). As we have shown in the introduction, a sub-linear (even zero) violation defined in (1) does not guarantee that policies that violate the constraint by a fixed amount (independent of K) are selected for a sub-linear number of episodes. On the other hand, if the violation metric defined in (6) grows only sub-linearly with K, it implies that the number of episodes where such policies are selected scales at most sub-linearly with K.
Linear Function Approximation: To handle a possible large number of states, we consider the following linear MDP.
Assumption 1. The CMDP is a linear MDP with feature map : S ⇥ A ! R d , if for any h, there exists d unknown signed measures
|x, a) = h (x, a), µ h (x 0 )i and there exists vectors ✓ r,h , ✓ g,h 2 R d such that for any (x, a) 2 S ⇥ A, r h (x, a) = h (x, a), ✓ r,h i g h (x, a) = h (x, a), ✓ g,h i. This is similar to the setting considered in Ghosh et al. (2022) and is based on the definition of linear MDP (Jin et al., 2020;Yang and Wang, 2019). By the above definition, the transition model, the reward, and the utility functions are linear in terms of the feature map . We remark that despite being linear, h (•|x, a) can still have infinite degrees of freedom since µ h (•) is unknown. Note that tabular MDP is a subset of linear MDP (Jin et al., 2020). A recent study (Zhang et al., 2022) showed that policies for linear MDPs can achieve better results than state-of-the-art approaches for benchmark databases. Linear MDPs are also viewed as a critical step toward studying large-scale RL problems, particularly those with infinite state space. Further, as demonstrated in numerous other settings, analyzing linear MDPs can provide insights that can be used to generalize to other settings. Thus, unconstrained linear MDP is extensively studied (Jin et al., 2020(Jin et al., , 2021;;He et al., 2021b,a;Wang et al., 2020;Hu et al., 2022). Similar to Proposition 1 in Jin et al. (2020), we can show that for a linear MDP and for any policy ⇡ there exists {w ⇡ j,h } H h=1 such that Q ⇡ j,h (x, a) = hw ⇡ j,h , (x, a)i for any (x, a, h) 2 S ⇥ A ⇥ [H]. We, thus, focus on the linear action-value function.
Dual Variable: We also use dual variable to consider a composite function.
, where Y is the dual variable.
We now describe our proposed Algorithm 1.
Algorithm 1 Model Free Algorithm with Linear Function Approximation for hard-constraint violation
for step h = H, H 1, . . . , 1 do 6:
break //Found the ideal dual variable 15:
for step h = 1, . . . , H do 19:
) for all a using w k j,h and Y k .
Take action a k h ⇠ ⇡ h,k (•|x k h ) and observe x k h+1 .
Note that at each episode k, Algorithm 1 can be divided into two steps: i) the dual variable finding step (Lines 4-17), and ii) the policy execution step (Lines 18-20).
The dual variable finding step can be divided into two main steps: i) the policy finding step (Lines 5-12), and ii) the constraint checking step for a given value of Y k (Lines 13-15). We now describe the steps in detail.
In order to obtain V k g,1 (x 1 ), we need to first find the policy and Q-functions. For a given dual variable Y k , lines 6-12 consist of updating the parameters w k r,h , w k g,h and ⇤ k h which are used to update the Q k j,h and V k j,h at episode k. ⇤ k h is the Gram-matrix for the regularized least square problem (see (7), later). Note that the lines 9-12 (i.e., Q, V , and policy) are not evaluated for each state, rather, they are evaluated only for the encountered states till episode k 1. Hence, we do not need to iterate over a potentially infinite number of states. For the first episode, since k 1 = 0 and ⌧ = 1, we have w k j,h = 0, 8j and ⇤ k h = I. We note that Q k j,H+1 (•, •) = 0 for j = r, g. Q function and Value function Estimation: We need to estimate the value-function and Q-function with respect to the policy ⇡ k for a given value of Y k . However, there are challenges. We do not know h in Bellman's equation ( 4), rather h V ⇡ k j,h+1 should be replaced by the empirical samples. Further, since
The intuition is to obtain w k j,h from Bellman's equation (cf.( 4)) using the regularized least-square regression. We obtain w k j,h for j = r, g according to the following equation
Then, an additional bonus term Jin et al. (2020), where is a constant which we will characterize in the next section. Such an additional term is used for the upper confidence bound in LSVI-UCB (Jin et al., 2020). The same bonus term is used for both Q k r,h and Q k g,h . Policy: The value functions are updated based on the Q function and the policy (line 13). The policy is based on a soft-max policy (line 12) unlike the greedy one in the unconstrained case Jin et al. (2020)
for any vector X 2 R |A| is a |A|-dimensional vector with parameter ↵ where the i-th component
At step h, ⇡ h,k (a|x) is computed based on the softmax policy with the composite Q-function vector
x, a)} a2A . When ↵ = 1, this becomes equal to the greedy policy. As shown in Ghosh et al. (2022), the greedy policy is not Lipschitz. Hence, it does not provide a uniform concentration bound for each individual value function, an essential step in proving the regret and violation bound. Note that for different values of Y k , the policy is different, hence V k j,h would also be different. We also use the Lipschitz property of soft-max to obtain Y k that satisfies certain characteristics which we discuss in the following.
Finding Y k : Once we compute Q k g,1 and compute policy according to soft-max, we obtain V k g,1 (x 1 ). If V k g,1 (x 1 ) < b, we increase the dual variable by ⌘ and repeat the steps (lines 5-12). We continue this process till Y k reaches p K or we obtain V k g,1 (x 1 ) b. Once we are out of the inner loop, we use Y k , and w k j,h to compute the policy in the execution phase.
In summary, at every episode, we identify Y k such that one of the following three cases holds:
x 1 ) b, thus, one can focus on maximizing the reward only.
) by proper choice of step-size ⌘ and ↵ (temp. co-efficient) of the soft-max policy ensuring the right balance. Intuitively, if we select a higher Y k such that V k g,1 (x 1 ) exceeds b by a large amount, it would put a smaller weight on reward maximization. Hence, the regret increase.
• Y k = p K, and V k g,1 (x 1 ) < b which means that we reach the upper bound of the dual variable. We show that an upper bound of p K is the enough to obtain Õ( p K) regret and Õ( p K) hard constraint violation.
Execution: The last part includes the execution of the policy for episode k (lines 22-24). The policy is again based on the soft-max policy with w k j,h and Y k obtained in the dual variable finding step.
Difference with other approaches: Ghosh et al. (2022); Ding et al. (2021Ding et al. ( , 2020)); Liu et al. (2021a) (OptPess-PrimalDual) also proposed primal-dual type algorithm. However, their focus was on minimizing the soft violation (cf.(1)) rather than the hard violation. The major difference is that at every episode, we find Y k such that it has the property characterized above. Since in the soft-constraint violation, one can negate violation at one episode by selecting a strictly feasible policy at the other episode, hence searching for such a dual-variable at every episode was not required there. Rather, updating the dual variable at the end of the episode was enough since if the current policy is infeasible one can increase the dual variable to choose a feasible policy in the subsequent episode to negate the violation. However, because of stricter requirements, we need to find the perfect dual variable at every episode. Our analysis is also different compared to those (see Section 4.2).
Space complexities: We remark that Algorithm 1 only needs to store r
hence, it takes O(d 2 H + dAT ) space which is the same as the unconstrained setup Jin et al. (2020). For the tabular setup, using the approach presented in Appendix H, the space complexity is at most O(|S| 2 |A|H) which is the same as the model-based approach in Efroni et al. (2020). We do not need to invert (⇤ k h ) 1 for the tabular case. Comparison with LP-based approach: Efroni et al. ( 2020) and Liu et al. (2021a) proposed LP-based approach to obtain the state-action occupancy measure for tabular setup in order to bound the hard constraint violation. From the state-action occupancy measure, they obtain the policy. However, solving LP for large state-space is challenging as the decision variables scale with the state-space. Neu and Okolo (2023); Lakshminarayanan et al. ( 2017); Neu and Pike-Burke (2020); Bas-Serrano et al. ( 2021) proposed an LP-based approach for linear MDP for the unconstrained problem. One may ask why not extending that approach to the constrained case. However, apart from Neu and Okolo (2023), the above formulations still rely on the finite state space assumption and the decision variables still consist of state-action occupancy measure which can be large for large state space. Neu and Okolo (2023) reduces the number of decision variables by assuming that a core set of state-action pairs is known which essentially means that a low dimensional state-action occupancy measure is enough to represent the rewards for all state-action pairs. However, finding the core set is difficult in general Neu and Okolo (2023). Also, all the above still rely on a model-based approach and need to estimate the transition probability. Neu and Okolo (2023) also proposed a model-free algorithm, however, that relies on the simulator. In summary, all the above approaches either rely on finite state-space assumptions or rely on a simulator and a core-set assumption to obtain a policy.
Instead, we propose a primal-dual-based algorithm and thus, we do not rely on any LP solver. Our algorithm is also model-free and does not need any simulator. Further, our algorithm works for infinite state space and we do not rely on core-set assumption as in Neu and Okolo (2023). Moreover, we would like to point out that since our approach is model-free, our algorithmic approach can be certainly extended to a larger class of RL problems. As described in our approach, we need to estimate the value function (we can use neural-network to estimate the value function) and then tune the dual variable till we achieve
Assumption of strict feasibility: All the primaldual-based approaches which focus on minimizing the soft-constraint violation relies on strict feasibility assumption (aka Slater's condition). In particular, all the primal-dual based approaches (model-free or modelbased) rely on strong duality (Paternain et al., 2019) in order to achieve soft-constraint violation. This is the first result that shows that sub-linear regret and constraint violation (even soft) is achievable without assuming Slater's condition for a primal-dual-based approach. Naturally, our analysis is significantly different (Section 4.2). If we assume the existence of a strictly feasible policy, we can set a lower upper bound for the dual-variable (Appendix J).
Value of ⌘: We obtain theoretical results for
However, in practice, we observe that ⌘ = O(1/( p KH)) works well, hence, the algorithm can be faster in practice. The characterization of a more computationally efficient algorithm with theoretical bound is left for the future work.
We now state the main result. We prove that Algorithm 1 achieves the regret and hard constraint violation which are sublinear in T = KH where T is the total number of steps.
Theorem 1. Fix any p 2 (0, 1). If we set = 1, = C 1 dH p ◆ in Algorithm 1 where ◆ = log(log(|A|)4dT /p) for some absolute constant C 1 . With probability 1 2p, we have
for some absolute constants C, and C 0 .
To the best of our knowledge, this is the first result that achieves Õ( p T ) regret and hard constraint violation bound for linear CMDP. Since linear CMDP contains a tabular setup, as a by-product, our result also provides the hard-constraint violation bound for tabular setup using the model-free algorithm. As we mentioned earlier, existing primal-dual type algorithms only consider soft-constraint violation, rather, we show that it is possible to achieve Õ( p T ) regret and hard constraint violation bound using primal-dual type approach. Our bound with respect to T matches the bounds attained in the tabular model-based and LP-based approach in Efroni et al. (2020) and Liu et al. (2021a) (OptPess-LP). * Note that our bounds are (nearly) optimal. It is shown that ⌦(d p H 2 T ) regret is unavoidable for the unconstrained setup. We can easily construct an example where only one policy is feasible. For example, consider the setup where g = r, and b = V ⇤ r,1 (x 1 ), (in this case, we are forcing an unconstrained problem to be constrained) then only the optimal policy is feasible. Thus, ⌦(d p H 2 T ) is also a lower bound for hard constraint violation as well when there is no strictly feasible policy.
Note that our regret bound matches the same order (with respect to T ) as in the unconstrained case (Jin et al., 2020) and in the linear CMDP setup with softconstraint violation (Ghosh et al., 2022). Ghosh et al. (2022) achieves zero soft-constraint violation when Slater's condition holds. Whether it is possible to reduce our violation bound further for the setup when the Slater's condition holds remains open.
Tabular Case: If we consider the tabular case with the following representation (x, a) = e x,a where e x,a is a |S||A| dimensional vector and e x,a = 1 when (s, a) = (x, a) and 0 otherwise, then plugging in d = |S||A| we obtain the regret and hard constraint violation bound as Õ( p
However, since we can trivially obtain ✏-covering number for a value function when the state-space is bounded, we can obtain a tighter result by modifying the bonus term . In particular, in Theorem 3 (Appendix H) we obtain the regret and hard constraint violation bounds as Õ( p |S| 2 |A|H 3 T ). This matches the result of Efroni et al. (2020). This is the first work which shows that it is possible to achieve Õ( p |S| 2 |A|H 3 T ) regret and hard constraint violation bound using primal-dual based approach matching the result from model-based LP-based approach (Efroni et al., 2020).
We start by highlighting the main differences with the existing approaches.
Novelty in Analysis techniques: Existing primaldual approaches that focus on bounding the softconstraint violation (Ghosh et al., 2022;Ding et al., 2021;Efroni et al., 2020) seek to bound for any Y 0
In order to prove regret, they then bound
using the fact that dual variable is updated based on the gradient descent step in the dual direction. Since our dual update is different, the regret analysis is significantly different. Further, we can not rely on strong duality result to bound the hard constraint violation unlike obtaining the soft constraint violation bound.
Rather, to prove the regret and the hard constraint violation bound, we first show that if the dual variable differs by ✏ amount, the estimated value function for utility (V k g,1 ) can also differ by at
This turns out to be essential to bound the regret and hard constraint violation. Such a guarantee is not required to obtain an upper bound for the soft-constraint violation as considered in the other papers. To bound the total soft constraint violation, one only needs to update the dual variable at the end of the episode k.
To prove that if the dual variable differs by ✏ amount, the estimated value function for utility (V k g,1 ) can also differ by at most O(K 1.5H d H ✏) amount; we use the fact that our policy is a soft-max to show that if the dual variable differs by an ✏ amount, then the value function at the h-th step only differs by at most O(✏ p KH) (Lemma 15). However, as the policy for the h-th step changes, the parameter for the h 1-th step would also change to fit Bellman's equation. Here, we use the linearity property to show that the parameter value w k j,h 1 (obtained via solving the linear regression problem) also differs by O(dK✏) (Lemma 16). Using the above, we show that the value function at the h 1-th step would differ by at most O(d✏K p KH) (Lemma 14). We obtain the final result by induction. Please see Appendix C for details. We now provide the main ideas behind bounding Regret and Hard constraint violation.
Regret Bound: We decompose the regret in the following manner:
In order to bound both T 1 and T 2 we need to obtain uniform concentration bound for each individual value function. In particular, we need to show that the log ✏covering number of (estimated) reward and utility value function must scale as log(K). As discussed in Ghosh et al. (2022), the greedy policy with respect to the composite state-action value function fails to achieve such bound since the greedy policy is not Lipschitz. Instead, the soft-max policy based on the composite state-action policy function achieves the above (Lemma 10).
We, first, discuss how to bound T 1 . We observe that
where we have used the fact that V ⇤ g,1 (x 1 ) b and Y k 0. We now bound T 3 and T 4 .
Readers should note that T 3 is similar to the optimism term with respect to the composite value function. However, since we use soft-max instead of the greedy policy, we cannot bound the above by zero. Rather, using the property of soft-max, we obtain Lemma 1. For any k, with probability 1 p,
When ↵ = log(|A|) p K/(4H), the above can be bounded by O(H 2 /K 1/2 ). Also, note that it shows that a large value of ↵ would degrade the regret. Now, we provide an upper bound for T 4 .
We, first, define the set of episodes where Y k = p K, and V k g,1 (x 1 ) < b,
x 1 ) < b}. Thus, for these episodes V k g,1 (x 1 ) b 0. Hence, for these episodes, T 4 is trivially upper bounded by 0. Hence, we now need to obtain an upper bound on T 4 on the set of episodes which are not in I b , i.e., when they belong to the set I C b . As we have discussed, by the choice of ⌘, when we obtain Y k > 0 such that V k g,1 (x 1 ) b, we also obtain
Intuitively, we strike the balance between reward maximization and utility maximization for V k r,1 (x 1 ) and V k g,1 (x 1 ) (as even if V k g,1 (x 1 ) > b, it would only exceed by O(HK 1 )). Hence, we can upper bound T 4 by O(HK 1/2 ). Thus, summing over the expressions in Lemmas 1 and 2 we obtain with probability 1 p,
We obtain the bound of T 2 using Azuma-Hoeffding inequality and the uniform concentration bound,
Hard constraint Violation Bound: We decompose the violation as the following:
We, further, decompose T 5 as the following
By the definition of I b , for episodes in
In order to bound the second term in the right-hand side of (13) note that
Finally, we bound T 6 . Since we add bonus term to obtain Q k g,h , thus, Lemma 5. With probability 1 p, V k g,1 (x 1 ) V ⇡ k g,1 (x 1 ).
Thus, we can rewrite
). Thus, from Azuma-Hoeffding inequality and uniform concentration bound, we obtain
From Lemma 4 and 6 we obtain the bound on violation in Theorem 1.
We evaluate Algorithm 1 on a simulated model (same as in Ghosh et al. (2022), details in Appendix K.1) to validate our theoretical results. We run Algorithm 1 for 3 ⇥ 10 5 episodes (K). We use ⌘ = 1/ p KH. Thus, we are using a larger ⌘ proposed in Algorithm 1 as it decreases the time complexity. We observe that such ⌘ is enough to achieve sub-linear regret and hard constraint violation. We use the feature-space representation similar to tabular setup (Appendix H). We compare our algorithm with two state-of-the-art algorithm: i) the algorithm proposed in Ghosh et al. (2022), and ii) OptPess-PrimalDual proposed in Liu et al. (2021a). Our empirical results (Figure 1) suggest that our algorithm significantly reduces the hard constraint violations as compared to both the algorithms.
As predicted by our theory, the hard constraint violation scales much smaller than O( p K) (Figure 1). In fact, our algorithm selects feasible policy after 1.5 ⇥ 10 5 episodes. However, the constraint violations grow for the other two algorithms which indicate that those algorithms are unable to find feasible policy. Obviously, infeasible policies can give higher rewards, thus, the average reward achieved by the other two algorithms are slightly higher compared to our approach. Nevertheless, our algorithm indeed achieves optimal reward. Thus, the empirical result shows the efficacy of our approach in achieving sub-linear hard constraint violation and regret. In Appendix K, we observe similar traits in our empirical results on the OpenAIGym control suite (Brockman et al., 2016) and other CMDP setups.
We propose a model-free RL-based algorithm for linear CMDP which achieved Õ( p d 3 H 3 T ) regret and Õ( p d 3 H 3 T ) hard constraint violation bound. To the best of our knowledge, this is the first result which shows Õ( p T ) regret and Õ( p T ) constraint violation bound using primal-dual model-free setup. We achieve our result by finding the dual variable that balances between regret and constraint violation within an episode, rather than only updating it at the end of each episode.
Whether we can tighten the dependence on d and H remains an important future research direction. Extending the work to the setup where the feature space needs to be learnt or non-linear MDP setup is also important. Recent works (Modi et al., 2021;Zhang et al., 2022;Agarwal et al., 2020) on feature-space learning for unconstrained MDPs may provide some insights. Wei, C.-Y., Jahromi, M. J., Luo, H., and Jain, R. (2021a). Learning infinite-horizon average-reward mdps with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pages 3007-3015. PMLR. Wei, H., Liu, X., and Ying, L. (2021b). A provablyefficient model-free algorithm for constrained markov decision processes. arXiv preprint arXiv:2106.01577. Xu, T., Liang, Y., and Lan, G. (2021). Crpo: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, pages 11480-11491. PMLR. Yang, L. and Wang, M. (2019). Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR. Zhang, X., Song, Y., Uehara, M., Wang, M., Agarwal, A., and Sun, W. (2022). Efficient reinforcement learning in block mdps: A model-free representation learning approach. In International Conference on Machine Learning, pages 26517-26547. PMLR. Zheng, L. and Ratliff, L. (2020). Constrained upper confidence reinforcement learning. In Learning for Dynamics and Control, pages 620-629. PMLR. Zhou, D., He, J., and Gu, Q. (2021). Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning, pages 12793-12802. PMLR. Checklist 1. For all models and algorithms presented, check if you include: (a) A clear description of the mathematical setting, assumptions, algorithm, and/or model. [Yes/No/Not Applicable] Yes, (please see Section 3). (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. [Yes/No/Not Applicable] Yes, (please see Section 3). (c) (Optional) Anonymized source code, with specification of all dependencies, including external libraries. [Yes/No/Not Applicable] Yes. We have described all the hyperparameters required to rerun the simulations. The source code will be published for the camera-ready version. 2. For any theoretical claim, check if you include: (a) Statements of the full set of assumptions of all theoretical results. [Yes/No/Not Applicable] Yes, (please see Section 4). (b) Complete proofs of all theoretical results. [Yes/No/Not Applicable] Yes, (please see Appendix). (c) Clear explanations of any assumptions. [Yes/No/Not Applicable] Yes. 3. For all figures and tables that present empirical results, check if you include: (a) The code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL). [Yes/No/Not Applicable] Yes, (in Section 5 and Appendix K). (b) All the training details (e.g., data splits, hyperparameters, how they were chosen). [Yes/No/Not Applicable] Not applicable. (c) A clear definition of the specific measure or statistics and error bars (e.g., with respect to the random seed after running experiments multiple times). [Yes/No/Not Applicable] Not applicable. (d) A description of the computing infrastructure used. (e.g., type of GPUs, internal cluster, or cloud provider). [Yes/No/Not Applicable] Not applicable. 4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include: (a) Citations of the creator If your work uses existing assets. [Yes/No/Not Applicable] Not applicable. (b) The license information of the assets, if applicable. [Yes/No/Not Applicable] Not applicable. (c) New assets either in the supplemental material or as a URL, if applicable. [Yes/No/Not Applicable] Not applicable. (d) Information about consent from data providers/curators. [Yes/No/Not Applicable] Not applicable. (e) Discussion of sensible content if applicable, e.g., personally identifiable information or offensive content. [Yes/No/Not Applicable] Not applicable. 5. If you used crowdsourcing or conducted research with human subjects, check if you include: (a) The full text of instructions given to participants and screenshots. [Yes/No/Not Applicable] Not applicable. (b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable. [Yes/No/Not Applicable] Not applicable. (c) The estimated hourly wage paid to participants and the total amount spent on participant compensation. [Yes/No/Not Applicable] Not applicable.
In Section A, we state some results which we use throughout. In Section B, we prove Lemma 1. In Section B.1, we state and prove base results Lemmas 10, 11, and 12 which are necessary to prove the Lemma 1. Subsequently, we prove Lemma 1. In Section C, we prove Lemma 2. In Section D, we prove Lemmas 4 and 5. In Section E, we prove Lemmas 3 and 6. In Section F we prove Lemma 10 (the uniform concentration result) which is essential to prove all the previous results. In Section G, we state some results proved in the existing literature which we have used in proving our results. In Section H, we detail our algorithm for tabular setup. In Section I, we describe why the approach for Bandit setup can not be applied to our CMDP setup. In Section J, we show that when a strictly feasible policy exists (aka Slater's condition holds) upper bound of H/ for the dual variable is enough to obtain Õ( p K) regret and hard constraint violation instead of an upper bound of p K . Finally, in Section K, we provide empirical results of our algorithm for various CMDP setups including OpenAI Gyms suite Brockman et al. (2016).
Notations: Throughout the rest of this paper, we denote
, as the Q-value, value-function, and the parameter values estimated respectively at the episode k for a given dual variable Y (inside the while loop in Algorithm 1). Note that policy depends on Y , hence, for different Y , V k,Y j,h would be different. Naturally, w k,Y j,h and Q k,Y j,h would be different (cf.( 7)). We denote
, as the Q-value, value-function, and the parameters chosen for the determined Y k (i.e., after the While loop in Algorithm 1 terminates). Hence,
Here, ⇡ h,k (•) depends on the dual variable. Thus, the dependence is implicit. Sometimes, we also use the notation ⇡ Y to make the dependence on the dual variable explicit.
To simplify the presentation, we denote k
Lemma 7. Under Assumption 1, for any fixed policy ⇡, let w ⇡ h be the corresponding weights such that Q ⇡ j,h = h (x, a), w ⇡ j,h i, for j 2 {r, g}, then we have for all h 2 [H],
Proof. From the linearity of the action-value function, we have
where
Thus, the result follows.
Lemma 8. For any (k, h, Y ), the weight w k,Y j,h satisfies
Proof. For any vector v 2 R d we have
here ⇡ h,k (•|x) is the Soft-max policy. Note that ⇡ h,k (•|x) implicitly depends on the dual-variable Y .
Note that Q k,Y j,h+1 (x, a) H for any (x, a). Hence, from (18) we have
Hence, the result follows.
We prove a more general result. Lemma 9. For any episode k and 0 Y p K, with probability 1 p,
Note that since the above holds for 0 Y p K, it will hold for Y k chosen value by Algorithm 1 at episode k when the While loop terminates. Thus, Lemma 1 readily follows.
In order to prove the above result, we prove some base results in Section B.1. Subsequently, we prove Lemma 9 in Section B.2.
We state and prove Lemmas 10,11, and 12.
First, we state the concentration lemma which is essential in controlling the fluctuations in the least square value iteration for individual value function. Lemma 10. There exists a constant C 2 such that for any fixed p 2 (0, 1), if we let E be the event that We now, recursively bound the difference between the value function maintained in Algorithm 1 (without the bonus term) and the value function for any policy for both the reward and utility value functions. We bound this using the expected difference at the next step plus an error term. This error term can be upper bounded by the bonus term with a high-probability. Lemma 11. There exists an absolute constant = C 1 dH p ◆, ◆ = log(log(|A|)4dT /p), and for any fixed policy ⇡, on the event E defined in Lemma 10, we have
Proof. We only prove for j = r, the proof for j = g is similar. For notational simplicity, we also remove Y from the superscript in w k,Y j,h for the remainder of this proof. Note that Q ⇡ r,h (x, a) = h (x, a), w ⇡ r,h i = r h (x, a) + h V ⇡ r,h+1 (x, a). Hence, we have
Now, we bound each term in the right hand side of expression in ( 22). We call those terms as q 1 , q 2 , and q 3 respectively.
First, note that |h (x, a),
Second, from Lemma 10, for the event in E, we have
where = log(4(C 1 + 1) log(|A|)dT /p). Third, h (x, a),
The last term in (25) can be bounded as the following
, q 1 + q 2 + q 3 i. Since = 1, we have from ( 23), (24,(26), and ( 27)
for some constant C 3 which is independent of C 1 . Finally, note that
where ◆ = log(4 log(|A|)dT /p). The last inequality follows from the fact that ◆ 2 [log 4, 1) as |A| 2, and C 3 is independent of C 1 . Hence, we can always pick C 3 p log 4 + log(C 1 + 1) C 1 p log 4 which satisfies ( 29) for all values of ◆ 2 [log 4, 1).
Next, using the above lemma, we bound the difference between the composite value function maintained by the algorithm and the composite value function for a policy with the Lagrangian Y k .
Lemma 12. With prob. 1 p, (for the event in E) and any 0
Proof. Note the fact that |Q ⇡ r,h | H. Thus, from Lemma 11 on the event E and for any Y 2 [0,
where the last equality follows from the definition of Q k,Y r,h . Similarly, for the event E,
Hence, for the event E,
First, we show that for a given Y , the gap between the maximum value attained by any composite (estimated) value function and our (estimated) composite value function are close for the parameters w k,Y j,h which we use to show Lemma 9 by controlling the parameter ↵.
is the value function corresponds to the greedy-policy with respect to the composite Q-function attained by our estimated value function.
where
Denote
where the last inequality follows from Proposition 1 in Pan et al. (2019).
We are now ready to show Lemma 9.
Proof. We prove the lemma by Induction.
First, we prove for the step H.
. Under the event in E as described in Lemma 10 and from Lemma 11, we have for j = r, g,
Hence, from the definition of V k,Y h
for any policy ⇡. Thus, it also holds for ⇡ ⇤ , the optimal policy. Hence, from Lemma 13, we have
Now, suppose that it is true till the step h + 1 and consider the step h.
Since, it is true till step h + 1, thus, for any policy ⇡,
From ( 30) in Lemma 12 and the above result, we have for any (x, a)
Now, again from Lemma 13, we have
Now, since it is true for any policy ⇡, it will be true for ⇡ ⇤ . From the definition of V ⇡,Y , we have
Hence, the result follows by summing over K and considering h = 1.
Before proving Lemma 2, we prove the following result.
Lemma 14. Let V k,Y g,1 be the estimated value function computed by the Algorithm 1 when the dual-variable is Y , then
We first show that because of the soft-max property, the difference between
Hence, by the property of the soft-max (Theorem 4.4 in Epasto et al. (2020))
Since ↵H 1, thus, we have the result.
Since ↵ = log(|A|) p K, then, we have from ( 43), and
We are now ready to prove Lemma 14.
Proof. We prove the above by induction. In particular, we show that if
First, consider h = H. Since V k j,H+1 = 0, thus, we have
Hence, by Lemma 15 (identifying ✏ 0 = ⌘, and plugging ↵ = log(|A|)/(4H)) we have
for all x. Hence, the statement is true for h = H.
In order to prove this for h, we need to show the following.
Proof. We show that for j = r. Note that
Hence,
where in the penultimate step we use Lemma 24. In the last inequality, we use the fact that (⇤ K h ) I,
|| (x, a)|| 1. Hence, we have
for all (x, a).
Thus, we have from Lemma 15
, Thus, plugging ↵ = log(|A|)/(4H), we have for any x,
Thus, by induction we have the result by plugging in h = 1. Now, we are ready to prove Lemma 2.
Proof. First, if Y k = 0, the result is trivially true. Now, consider that the while loop terminates at some value
(x 1 ) < b (otherwise, the loop would have terminated at Y k ⌘). Now, from Lemma 14,
for any x. Hence, the result follows.
D Proof of Lemmas 4 and 5
Recall the definition of I b which is the set of episodes where Algorithm 1 returns
From Lemma 1 and the value of ↵, we obtain
where the last inequality follows from the fact that for all the episodes in
Proof. We prove via induction. Since V k j,H+1 (x) = 0 for all x, thus, from Lemma 11
Recall that Y k is the selected dual variable at episode k.
Thus,
).
In order to prove the Lemma 3 and 6, we state and prove the following result. In this section, we obtain bounds for the selected value Y k , hence, we use Q k j,h , w k j,h and V k j,h . First, we introduce a notation. Let
Lemma 17. On the event defined in E in Lemma 10, we have
Proof. By Lemma 11, for any x, h, a, k
Thus,
Thus, from (64), we have
Hence, by iterating recursively, we have
The result follows.
We, are now ready to prove Lemmas 3 and 6.
Proof. Note from Lemma 17, we have
We, now, bound the individual terms. First, we show that the first term corresponds to a Martingale difference.
For any (k, h) 2 [K] ⇥ [H], we define F k h,1 as -algebra generated by the state-action sequences, reward, and constraint values,
. Similarly, we define the F k h,2 as the -algebra generated by
for any k 2. Let F 1 0,2 be empty. We define a Martingale sequence
where t(k, h, m) = 2(k 1)H + 2(h 1) + m is the time index. Clearly, this martingale is adopted to the filtration
, and particularly
From the Azuma-Hoeffding inequality, we have
With probability 1 p/2 at least for any j = r, g,
Now, we bound the second term. Note that the minimum eigen value of
Now, by Cauchy-Schwartz inequality, we have
Note that = C 1 dH p ◆.
Thus, we have with probability
Hence, the result follows.
To simplify the notation, we remove h and Y from the subscript and superscript from w k,Y j,h , Q k,Y j,h and V k,Y j,h in this Section.
Note that the proof follows the similar direction as in Ghosh et al. (2022) (Lemma 8 there). However, there is a major difference. In Ghosh et al. (2022), the upper bound of the dual variable Y was 2H/ (Appendix J), in our case, the upper bound of Y is p K. However, we show that it only adds to the constant term C 1 .
In order to prove the Lemma 10, we first compute the ✏-covering number for the class of value functions (Lemma 18).
In order to compute that we first compute the ✏-covering number of the individual Q-functions (Lemma 19) which is essential to compute the covering number for composite Q-functions (Corollary 1). Subsequently, we show that if the two Q-functions and the Lagrange multipliers are close, the policies are also close (Lemma 20).
We first introduce the set of Q-functions.
The set Q is parameterized by w j , and ⇤. We have ||w j || 2H p dk/ (from Lemma 8). The minimum eigen value of ⇤ satisfies min 1. Hence, the Frobenius norm of ⇤ 1 is bounded. Note that Q k j 2 Q j for j = r, g. We now introduce the class of value function for j = r, g.
where ⇠ = p K.
The class of value function V j is parameterized by w r , w g , ⇤, and Y 2 [0, ⇠]. Note that even the individual value function depends on the Q-functions for both the reward and utility since the policy depends on the composite Q-function.
First, we need to see whether
We now bound the ✏-covering number for the class of value function Lemma 18. There exists a Ṽj 2 V j parameterized by ( wr , wg , ˜ , ⇤, Ỹ ) such that DIST (V j , Ṽj ) ✏ where
Let N Vj ✏ be the ✏-covering number for the set V j , then,
where
where ⇠ = 2 p K covering number for the set Q j . Towards this end, we first, introduce some notations.
} with respect to the Frobenius norm. Lemma 19.
The ✏-covering number for the set Q j , for j = r, g, N Qj ✏ of the set Q j for j = r, g satisfies the following
The distance metric is the
Proof. For notational simplicity, we represent A = 2 ⇤ 1 , and reparamterized the class Q j by (w j , A). Now, p dk/ } with respect to the 2-norm. Also recall that
For any Q j 2 Q j , there exists a Qj parameterized by (w 2 , A 2 ) where w 2 2 C ✏ w and
, which gives the result since log(•) is an increasing function.
Since the class of Q-function is independent of the policy we do not have ⇠ and ↵ in the ✏-covering number.
From the above lemma and since Y k ⇠, we have the following,
Proof. Note that Qj 2 Q j belongs to the ✏ 0 covering of the set Q.
where the first inequality follows from the property of supremum and the norm. The second inequality follows from the norm, and the fact that | Ỹk Y k | ✏ 0 , and |Q k g (x, a)| H. The third inequality follows from the fact that dist(Q j , Qj ) ✏ 0 .
We now show that if the there exist Qj , and Ỹk which are close to Q j and Y k , then the soft-max policy is also close.
Lemma 20. Suppose that ⇡ is the soft-max policy (temp. coefficient 1/↵) corresponding to the composite
⇡ is the soft-max policy vector with the same temp. coefficient 1/↵ corresponding to the composite Q-function ( Qr + Ỹk Qg ), i.e, 8a 2 A,
then, for any state x,
where ⇡(•|x) = {⇡(a|x)} a2A and ⇡(•|x) = {⇡(a|x)} a2A when dist(Q k j,h , Qj ) ✏ 0 for j = r, g, and
Proof. Let Exp ↵ (P ) be a soft-max corresponding to the vector P , i.e., the i-th component of Exp ↵ (P ) is
.
Note from Theorem 4.4 in Epasto et al. ( 2020) then, we have
for two vectors P 1 and P 2 . Now note that in our case for a given state x, ⇡ is equivalent to
, and ⇡ is equivalent to Exp ↵ ( Qr (x, •) + Ỹk Qg (x, •)). Then from (85) and the fact that dist(Q
Hence, the result follows.
Based on the above two lemmas we show that when the Q-functions are close, the value functions in the class V j are also close.
Lemma 21. There exists Ṽj 2 V j such that
where dist( Qj , Q j ) ✏ 0 , Qj 2 Q j for all j;
Proof. For any x,
where we use the fact that dist(Q k j , Qr ) ✏ 0 , and P a ⇡(a|x) = 1 for the first term and the Holder's inequality in the second term for the second last inequality. For the last inequality, we use Lemma 20, and the fact that Qj (x, a) H for any (x, a). Hence, we have the result.
Note that when ↵ = log(|A|) p K/H as we have in Algorithm 1, the right hand side in (87) becomes
We introduce one more notation which we use to prove Lemma 18.
Note that C ✏ ⇠ consists of points which is ✏-close to any point within the interval [0, ⇠]. Since we have defined ✏-cover for all the parameters, we are now ready to prove Lemma 18.
, then from Lemma 21, we have DIST(V k j , e V j ) ✏. Thus, we only need to find parameters in the ✏ 0 -covering of the Q-functions as described in Lemma 19 in order to obtain ✏-close value function.
Recall the Definition 6. Then, there exists wr , wg 2 C ✏ 0 w such that || wr w r ||
1 , for some ⇤, and Y k , Ỹk such that |Y k Ỹk | ✏ 0 . Then we obtain Qj parameterized by ( wj , , ⇤) for j = r, g, such that dist(Q j , Qj ) ✏ 0 (by Lemma 19). Now define e V j = P a ⇡(a|•) Qj , where
Thus, from Lemma 21, we have DIST(V k j , Ṽj ) ✏. Hence, there exists Ṽj parameterized by wr , wg , Ỹk , Ã, such that Dist( Ṽj , V k j ) ✏. Hence,
Thus, from Lemma 19 and Definition 7, the ✏-covering number N Vj ✏ for the set V j satisfies the following
Hence, the result follows.
From Lemma 18, note that we need ✏ 0 covering for the Q-functions where ✏ 0 = ✏ (H2↵(1 + ⇠) + 1)
if we need to bound DIST (V j , Ṽj ) by ✏.
Now, we are ready to prove Lemma 10.
Proof. By Lemma 18, we know that there exists Ṽj in the ✏-covering for V j such that for every x,
where
The last expression is bounded by 8k 2 ✏ 2 . Now, we bound the first term. Note from Lemma 18 that in order to obtain Ṽj which satisfies (90), we need to obtain we need N V ✏ number of elements to obtain such ( wr , wg , , ⇤, Ỹ ). Such Ṽj is independent of samples. Hence, we can use the Elliptical lemma for self-normalization (Theorem 2). From Theorem 2 and the union bound we obtain
where N V ✏ is upper bounded in (79). is equal to C 1 dH p ◆ for some constant C 1 , and ◆ = log(log(|A|)4dT /p). Further, ⇠ = p K . We obtain from ( 92)
where
. Plugging in the above, and putting ↵ = log(|A|) p K/H, we obtain from ( 93)
for some constant C 2 . Hence, the result follows.
The following result is shown in Abbasi-Yadkori et al. (2011) and in Lemma D.2 in Jin et al. (2020).
Lemma 22. Let { t } t 0 be a sequence in < d satisfying sup t 0 || t || 1. For any t 0, we define ⇤ t = ⇤ 0 + P t j=0 j T j j . Then if the smallest eigen value of ⇤ 0 be at least 1, we have log
Theorem 2. [Concentration of Self-Normalized Process Abbasi-Yadkori et al. ( 2011)] Let {✏ t } 1 t=1 be a real-valued stochastic process with corresponding filtration {F t } 1 t=0 . Let ✏ t |F t 1 be a zero mean and sub-Gaussian, i.e., [✏ t |F t 1 ] = 0, and
Let { t } 1 t=1 be a < d -valued Stochastic process where t 2 F t 1 . Assume ⇤ 0 2 < d⇥d is a positive-define matrix, let, ⇤ t = ⇤ 0 + P t j=0 j T j . Then for any > 0 with probability at least 1 , we have
The next result characterizes the covering number of an Euclidean ball (Lemma 5.2 in Vershynin ( 2010)). The following lemma is similar to Lemma C.4 in Jin et al. (2020).
Lemma 24. Let {✏ ⌧ } be any sequence so that |✏ ⌧ | B for any ⌧ . Then, we have for any (h, k) 2 [H] ⇥ [K] and any 2 < d :
In this section, we describe the tabular setup in detail. First, we describe a structure for the tabular setup where one does not need to take the inverse of ⇤ k h . Further, we note that ⌘
). We can revert back to the tabular case by setting (s, a) = e s,a where e s,a is a d-dimensional (here d = |S||A|) vector where e s,a = 1 for state-action pair (s, a) and zero for other values of state and action. The w r,h vector update becomes as the following
where n k h (x, a) is the number of times the state-action pair (x, a) has been encountered at step h till episode k. The Q k,Y r,h update will be
In a similar manner, we can update Q k g,h . We further remark that if we maintain n k h (x, a, x) to be the number of times the state-action-next state (x, a, x) has been encountered at step h till episode k. Then
A .
In this case, we do not need to go through all samples at each iteration and do not even need to store the old samples. The memory complexity of maintaining the counts {n h (x, a, x)} is O H|S| 2 |A| , which matches model-based algorithms for tabular settings such as Efroni et al. (2020).
Proof. We prove the result via induction. For
where we have used the fact that ✏ 00 = 1 log(|A|) H K H+1 , and ↵ = log(|A|) p K/(4H). Now, let us assume that the result is true for h+1. We have
where ✏ 00 = 1 log(|A|) H K H+1 , and ↵ = p K/(4H) Hence, the result follows after putting h = 1.
Hence, for tabular case, ⌘ = O(1/K H+1 ) is enough. Thus, the maximum number of times the while loop may continue is O(K H+1.5 ) since Y k p K.
Improved Bounds for Tabular Case Using the finite state-space, we obtain a better bound for the regret and hard constraint violation. Theorem 3. Fix any p 2 (0, 1). If we set = 1, = C 4 p |S|log(4|S||A|log(|A|)T /p) for tabular case in Algorithm 1 for some absolute constant C 4 . With probability 1 2p, we have Proof. In order to prove the above result, we show that new bonus term is enough for optimisim.
Now, note that w ⇡ r,h = ✓ j,h + P s 0 P h V ⇡ r,h+1 (s 0 ) for tabular case. Hence ||w ⇡ r,h || H p |S|. For the third term, note that
The last term in ( 101) can be bounded as the following
The first term in ( 101) is equal to
We have to bound the second term in (100). Note that
We now bound the above. First, we express V r,h+1 = Ṽh+1 + V j where | V j | ✏ for Ṽj in the ✏-covering set of V j . Since the upper bound for the value function is H, one can trivially obtain the ✏-covering number for the value function as
From Theorem 2, we obtain with probability 1 for a specific (x, a) 2
Hence, using the union bound where = p/(N ✏ V |S||A|), we obtain with probability 1 p/2 for any (x, a)
Using ✏ = H/K, we obtain from ( 104) and ( 105) as
Hence, we can write
for some constant C 4 and C 5 .
Hence, in Lemma 11, we can use the value as C 4 H p |S|log(|S||A|4T /p). Recall equation ( 67)
Hence, following the same arguments as in Lemmas 3, and 6, we obtain
where we use (76) to bound the above. The above is enough to obtain the improved regret and hard constraint violation bound as the rest of the argument will follow the same logic.
Recently, Guo et al. (2022) proposed an algorithm which achieves Õ( p T ) regret and hard-constraint violation in various bandit setups using primal-dual approach. The episodic RL-setup with H = 1 is equivalent to the bandit setup. Thus, our approach is applicable to the bandit setup as well. However, unfortunately, the approach in Guo et al. (2022) can not be extended to the episodic CMDP setup. We will describe the main issue next. In Guo et al. (2022), a dual variable Ŷk p K is used (hence, the dual variable is always greater than or equal to p K). Since there is no need of multiple steps in bandit setup, there is no need of value function. Rather, one only needs to estimate the reward and utility function f and g respectively. Guo et al. (2022) estimated an optimistic reward function f (a) and utility function ĝ(a) for each a. Then, Guo et al. (2022) proposed an algorithm according to the greedy policy a = arg max a 0 ( f (a 0 ) Ŷk (ĝ(a 0 )) + )
Note that if ĝ(a 0 ) is positive, then it negates the reward which means that such an action would be avoided.
From the optimism, one can show that f (a 0 ) Y k (ĝ(a 0 )) + f (a ⇤ ) Y k (g(a ⇤ )) + where a ⇤ is the optimal solution. Using the above, Guo et al. (2022) obtained the regret and hard constraint violation bound.
The regret and violation bound obtained by Guo et al. (2022) is Õ( p T ) which is the same as ours. However, the computation complexity is much less. In particular, there is no need to obtain the dual-variable Y k at every episode to balance between the reward and the utility maximization which we proposed. Rather, any Ŷk p K would be sufficient.
It is natural to ask whether we can extend the above approach for the RL setup. Readers would note that in the RL one would replace the f and g with Q r,h and Q g,h respectively. In particular, one would be tempted to take action according to the greedy policy
However, the above would not work. The state space consists of location, speed, angle, and angular velocity. We discrete each in evenly-spaced 15 states, thus, the state space is 15 4 . Even though the state space is large, we observe that our approach learns to achieve the optimal policy. It shows that our approach can be applied to continuous state space as well. Further, our approach also learns to satisfy constraints.
From Figure 2, we observe that the hard constraint violation in our approach grows on a much smaller scale compared to both Ghosh et al. (2022) and OptPess-PrimalDual. In fact, even the reward achieved by our approach is higher. The highest achievable reward is 200 and as we can see our approach indeed approaches the optimal reward as K increases.
This MDP is proposed by Moskovitz et al. (2023). If one takes action a = 0, one would stay in state s 0 and gets a reward 1. However, taking action a = 1 would take the agent to state s 1 and reward 0. At state s 1 , the action a = 1 would get the agent to state s 0 and reward 1. On the other hand, the agent will remain in state s 1 if the action a = 0 and the reward will be 0 (see Figure 3a). The length of the horizon H = 10. The utility g = r. The CMDP problem is maximize V r,1 (s 0 ) s.t V g,1 (s 0 ) 5 (115)
Hence, the agent should be in state s 0 half of the time and state s 1 for the rest. Though the maximum cumulative reward can be 10 where the agent can remain in state s 0 . However, such a strategy is not feasible.
From Figure 3 it is evident that the hard-constraint violation in our approach scales at most O( p K) and scales at a much smaller scale compared to Liu et al. (2021a) and Ghosh et al. (2022). Hence, it shows that our algorithm is able to achieve feasible policy at a faster scale compared to the existing state-of-the-art approaches who have only focused on reducing the soft constaint violation. Figure 3 also shows that initially, the reward is higher than 5 as our algorithm still explores. Hence, the algorithm chooses infeasible policies more frequently. Finally, the reward decreases the reward converges to the optimal value of 5 as our algorithm chooses feasible optimal policies more frequently.
We also simulated our method on the frozen lake environment of OpenAIgym Brockman et al. (2016). We consider 4 ⇥ 4 grid. The agent gets a reward 1 when it reaches the goal state. We consider an episode length of H = 9. The agent stays in the goal state once it reaches there. The agent is also permanently in the hole if it reaches a hole. In this case, the reward will be 0.
In the original frozen-lake experiment, there are two optimal ways to get to the goal. We add a constraint to ensure that one of the paths is infeasible. In particular, we add a utility function where the agent gets a utility of 1 except when the agent falls into a hole or goes to any of the blocks on the extreme left-hand column (Figure 4a). This will ensure that the optimal path of the left-hand side is infeasible. We set b to 8 which ensures that only one path is feasible and optimal.
Our simulation result shows that our approach indeed identifies the optimal path (Figure 4). The violation S, g=1 F, g=1 F, g=1 F,g=1 F, g=0, H, g=0 F, g=1 H,g=0 F, g=0 F, g=1 F, g=1 H, g=0 H, g=0 F, g=1 F, g=1 G, g=1
The optimal solution-Move rightward for 2 steps, and downward for 3 steps, and then rightward for 1 step to reach the goal state. becomes almost 0 after 1000 episodes (Figure 4b). Hence, our algorithm indeed achieves the feasible optimal policy. The hard constraint violation achieved by Ghosh et al. ( 2022) is much higher compared to ours and is unable to obtain feasible policy. The hard constraint violation achieved by Liu et al. (2021a) is higher compared to even Ghosh et al. (2022).Further, the reward achieved by our approach converges to the optimal one (3) after only 1000 episodes (Figure 4c). Again, it shows that our algorithm is able to identify optimal policy even within smaller number of episode while the other algorithms are unable to find feasible policy.