1 Introduction↩︎

The framework of Reinforcement Learning (RL) is concerned with a class of problems where an agent learns to yield the maximum cumulative reward in an unknown environment via repeated interaction. RL finds applications in diverse areas, such as wireless communication, transportation, and epidemic control [1]–[3]. RL problems are mainly categorized into three setups: episodic, infinite horizon discounted reward, and infinite horizon average reward. Among them, the infinite horizon average reward setup is particularly significant for real-world applications. It aligns with most of the practical scenarios and captures their long-term goals. Some applications in real life require the learning procedure to respect the boundaries of certain constraints. In an epidemic control setup, for example, vaccination policies must take the supply shortage (budget constraint) into account. Such restrictive decision-making routines are described by constrained Markov Decision Processes (CMDP) [4]–[6]. Existing papers on CMDPs utilize either a tabular or a linear MDP structure. This work provides the first algorithm for an infinite horizon average reward CMDP with general parametrization and proves its sub-linear regret and constraint violation bounds.

There are two primary ways to solve a CMDP problem in the infinite horizon average reward setting. The first one, known as the model-based approach, involves constructing estimates of the transition probabilities of the underlying CMDP, which are subsequently utilized to derive policies [5]–[7]. The caveat of this approach is the large memory requirement to store the estimated parameters, which effectively curtails its applicability to CMDPs with large state spaces. The alternative strategy, known as the model-free approach, either directly estimates the policy function or maintains an estimate of the \(Q\) function, which is subsequently used for policy generation [8]. Model-free algorithms typically demand lower memory and computational resources than their model-based counterparts. Although the CMDP has been solved in a model-free manner in the tabular [8] and linear [9] setups, its exploration with the general parameterization is still open and is the goal of this paper.

General parameterization indexes the policies by finite-dimensional parameters (e.g., weights of neural networks) to accommodate large state spaces. The learning is manifested by updating these parameters using policy gradient (PG)-type algorithms. Note that PG algorithms are primarily studied in discounted reward setups. For example, [10] characterizes the sample complexities of the PG and the Natural PG (NPG) algorithms with softmax and direct parameterization. Similar results for general parameterization are obtained by [11], [12]. The regret analysis of a PG algorithm with the general parameterization has been recently performed for an infinite horizon average reward MDP without constraints [13]. Similar regret and constraint violation analysis for the average reward CMDP is still missing in the literature. In this paper, we bridge this gap.

Challenges and Contribution: We propose a PG-based algorithm with general parameterized policies for the average reward CMDP and establish its sublinear regret and constraint violation bounds. In particular, assuming the underlying CMDP to be ergodic, we demonstrate that our PG algorithm achieves an average optimality rate of \(\tilde{\mathcal{O}}(T^{-\frac{1}{5}})\) and average constraint violation rate of \(\tilde{\mathcal{O}}(T^{-\frac{1}{5}})\). Invoking this convergence result, we establish that our algorithm achieves regret and constraint violation bounds of \(\tilde{\mathcal{O}}(T^{\frac{4}{5}})\). Apart from providing the first sublinear regret guarantee for the average reward CMDP with general parameterization, our work also improves the state-of-the-art regret guarantee, \(\tilde{\mathcal{O}}(T^{5/6})\) in the model-free tabular setup [8].

Despite the availability of sample complexity analysis of PG algorithms with constraints in the discounted reward setup [4], [14] and PG algorithms without constraint in average reward setup [13], obtaining sublinear regret and constraint violation bounds for their average reward counterpart is challenging.

• [4], [14] solely needs an estimate of the value function \(V\) while we additionally need the estimate of the gain function, \(J\).

• [4], [14] assume access to a simulator to generate unbiased value estimates. In contrast, our algorithm uses a sample trajectory of length \(H\) to estimate the values and gains and does not assume the availability of a simulator.

• The first-order convergence analysis (Lemma 6) differs from that in [13]. Note that both of these papers use an ascent-like inequality. In [13], this bounds the term \(J(\theta_{k+1})-J(\theta_k)\). The final result is obtained by calculating a sum over \(k\) which cancels the intermediate terms and leaves us with \(J(\theta_K)-J(\theta_1)\). We would like to emphasize that the cancellation of the intermediate terms is crucial to establishing the result. However, a similar effort in our case only leads to a bound of \(J_{\mathrm{L}}(\theta_{k+1}, \lambda_k)-J_{\mathrm{L}}(\theta_k, \lambda_k)\). Note that directly performing a sum over this difference does not lead to the cancellation of intermediate terms. We had to take a different route and apply the bounds of the Lagrange multipliers and the estimate of the constraint function to achieve that goal.

• After solving the problems mentioned above, we prove \(\tilde{\mathcal{O}}(T^{-\frac{1}{5}})\) convergence rate of the Lagrange function. Unfortunately, the strong duality property, which is central to proving convergence results of CMDPs for tabular and softmax policies, does not hold under the general parameterization. As a result, the convergence result for the dual problem does not automatically translate to that for the primal problem, which is a main difference from [13]. We overcome this barrier by introducing a novel constraint violation analysis and a series of intermediate results (Lemma 16-18) that help disentangle the regret and constraint violation rates from the Lagrange convergence. It is important to mention that although the techniques applied are inspired by the [14], those techniques cannot be directly adopted for average reward MDPs. This is primarily because the estimate \(\hat{J}_c(\theta_k)\) is biased in the average case. To the best of our knowledge, constraint violation analysis with a biased estimate of the cost value is not available in the literature and is performed for the first time in our paper.

• Due to the presence of the Lagrange multiplier, the convergence analysis of a CMDP is much more convoluted than its unconstrained counterpart. The learning rate of the Lagrange update, \(\beta\), turns out to be pivotal in determining the growth rate of regret and constraint violation. Low values of \(\beta\) push the regret down while simultaneously increasing the constraint violation. Finding the optimal value of \(\beta\) that judiciously balances these two competing goals is one of the cornerstones of our analysis.

Related work for unconstrained average reward RL: In the absence of constraints, both model-based and model-free tabular setups have been widely studied for infinite horizon average reward MDPs. For example, the model-based algorithms proposed by [15], [16] achieve the optimal regret bound of \(\tilde{\mathcal{O}}(\sqrt{T})\). Similarly, the model-free algorithm proposed by [17] for tabular MDP results in \(\tilde{\mathcal{O}}(\sqrt{T})\) regret. Regret analysis for average reward MDP with general parametrization has been recently studied in [13], where a regret bound of \(\tilde{\mathcal{O}}({T}^{3/4})\) is derived.

Related work for constrained RL: The constrained reinforcement learning problem has been extensively studied both for infinite horizon discounted reward and episodic MDPs. For example, discounted reward CMDPs have been recently studied in the tabular setup [18], with both softmax [14], [19], and general policy parameterization [4], [12], [14], [19]. Moreover, [20]–[22] investigated episodic CMDPs in the tabular setting.

Recently, the infinite horizon average reward CMDPs have been investigated in model-based setups [5]–[7], tabular model-free setting [8] and linear CMDP setting [9]. For model-based CMDP setup, [6] proposed a model-based online mirror descent algorithm in the ergodic setting which achieves \(\mathcal{\tilde{O}}(\sqrt{T})\) for regret and violation at the same time. [7] proposed algorithms based on the posterior sampling and the optimism principle that achieve \(\mathcal{\tilde{O}}(\sqrt{T})\) regret with zero constraint violations in the ergodic setting. However, the above model-based algorithms cannot be extended to large state space. In the tabular model-free setup, the algorithm proposed by [8] achieves a regret of \(\tilde{\mathcal{O}}({T}^{5/6})\) with zero constraint violations. Finally, in the linear CMDP setting, [9] achieves \(\tilde{\mathcal{O}}(\sqrt{T})\) regret bound with zero constraint violation. Note that the linear CMDP setting assumes that the transition probability has a certain linear structure with a known feature map which is not realistic. Table 1 summarizes all relevant works. Unfortunately, none of these papers study the infinite horizon average reward CMDPs with general parametrization which is the main focus of our article.

Additionally, for the weakly communicating setting, [6] proposed a model-based algorithm achieving \(\mathcal{\tilde{O}}(T^{2/3})\) for both regret and violation in tabular case. [9] further extends such result to linear MDP setting with \(\mathcal{\tilde{O}}(T^{3/4})\) regret and violation. In general, it is difficult to propose a model-free algorithm with provable guarantees for Constrained MDPs (CMDPs) without considering the ergodic model. [6] pointed out several extra challenges in Weakly communicating MDP compared to the ergodic case. For example, there is no uniform bound for the span of the value function for all stationary policies. It is also unclear how to estimate a policy’s bias function accurately without the estimated model, which is an important step for estimating the policy gradient.

2 Formulation↩︎

This paper analyzes an infinite-horizon average reward constrained Markov Decision Process (CMDP) denoted as \(\mathcal{M}=(\mathcal{S},\mathcal{A}, r, c, P,\rho)\) where \(\mathcal{S}\) denotes the state space, \(\mathcal{A}\) is the action space of size \(A\), \(r:\mathcal{S}\times\mathcal{A}\rightarrow [0,1]\) is the reward function, \(c:\mathcal{S}\times\mathcal{A}\rightarrow [-1,1]\) is the constraint cost function, \(P:\mathcal{S}\times\mathcal{A}\rightarrow \Delta^{|\mathcal{S}|}\) is the state transition function where \(\Delta^{|\mathcal{S}|}\) denotes a probability simplex with dimension \(|\mathcal{S}|\), and \(\rho\in\Delta^{|\mathcal{S}|}\) is the initial distribution of states. A policy \(\pi\in\Pi:\mathcal{S}\rightarrow \Delta^{A}\) maps the current state to an action distribution. The average reward and cost of a policy, \(\pi\), is, \[\label{Eq95reward} J_{g,\rho}^{\pi}\triangleq \lim\limits_{T\rightarrow \infty}\frac{1}{T}\mathbf{E}\bigg[\sum_{t=0}^{T-1}g(s_t,a_t)\bigg|s_0\sim \rho, \pi\bigg]\tag{1}\] where \(g=r, c\) for average reward and cost respectively. The expectation is calculated over the distribution of all sampled trajectories \(\{(s_t, a_t)\}_{t=0}^{\infty}\) where \(a_t\sim \pi(s_t)\), \(s_{t+1}\sim P(\cdot|s_t, a_t)\), \(\forall t\in\{0, 1, \cdots\}\). For notational convenience, we shall drop the dependence on \(\rho\) whenever there is no confusion. Our goal is to maximize the average reward function while ensuring that the average cost is above a given threshold. Without loss of generality, we can mathematically write this problem as, \[\begin{align} \label{eq:def95unparametrized95optimization} \begin{aligned} \max_{\pi\in\Pi} ~& J_r^{\pi} ~~ \text{s.t.} ~ J_c^{\pi}\geq 0 \end{aligned} \end{align}\tag{2}\] However, the above problem becomes difficult to handle when the underlying state space, \(\mathcal{S}\) is large. Therefore, we consider a class of parametrized policies, \(\{\pi_\theta|\theta\in \Theta\}\) whose elements are indexed by a \(\mathrm{d}\)-dimensional parameter, \(\theta\in\mathbb{R}^{\mathrm{d}}\) where \(\mathrm{d}\ll|\mathcal{S}||\mathcal{A}|\). Thus, the original problem in Eq 2 can be reformulated as the following parameterized problem. \[\begin{align} \label{eq:def95constrained95optimization} \begin{aligned} \max_{\theta\in\Theta} ~& J_r^{\pi_{\theta}} ~~\text{s.t.} ~J_c^{\pi_{\theta}}\geq 0 \end{aligned} \end{align}\tag{3}\] We denote \(J_g^{\pi_\theta} = J_g(\theta)\), \(g\in\{r, c\}\) for notational convenience. Let, \(P^{\pi_{\theta}}:\mathcal{S}\rightarrow \Delta^{|\mathcal{S}|}\) be a transition function induced by \(\pi_\theta\) and defined as, \(P^{\pi_{\theta}}(s, s') = \sum_{a\in\mathcal{A}}P(s'|s,a)\pi_{\theta}(a|s)\), \(\forall s, s'\). If \(\mathcal{M}\) is such that for every policy \(\pi\), the function, \(P^{\pi}\) is irreducible and aperiodic, then \(\mathcal{M}\) is called ergodic.

Ergodicity is a common assumption in the literature [23], [24]. If \(\mathcal{M}\) is ergodic, then \(\forall \theta\), there exists a unique stationary distribution, \(d^{\pi_{\theta}}\in \Delta^{|\mathcal{S}|}\) given as follows. \[\begin{align} d^{\pi_{\theta}}(s) = \lim_{T\rightarrow \infty}\dfrac{1}{T}\sum_{t=0}^{T-1} \mathrm{Pr}(s_t=s|s_0\sim \rho, \pi_{\theta}) \end{align}\] Ergodicity implies that \(d^{\pi_{\theta}}\) is independent of the initial distribution, \(\rho\), and obeys \(P^{\pi_{\theta}}d^{\pi_{\theta}}=d^{\pi_{\theta}}\). Hence, the average reward and cost functions can be expressed as, \[\begin{align} \label{eq95r95pi95theta} J_g(\theta) = \mathbf{E}_{s\sim d^{\pi_{\theta}}, a\sim \pi_{\theta}(s)}[g(s, a)] = (d^{\pi_{\theta}})^T g^{\pi_{\theta}} \end{align}\tag{4}\] where \(g^{\pi_{\theta}}(s) \triangleq \sum_{a\in\mathcal{A}}g(s, a)\pi_{\theta}(a|s), ~g\in\{r, c\}\). Note that the functions \(J_g(\theta)\), \(g\in\{r, c\}\) are also independent of the initial distribution, \(\rho\). Furthermore, \(\forall \theta\), there exist a function \(Q_g^{\pi_{\theta}}: \mathcal{S}\times \mathcal{A}\rightarrow \mathbb{R}\) such that the following Bellman equation is satisfied \(\forall (s, a)\in\mathcal{S}\times\mathcal{A}\). \[\label{eq95bellman} Q_g^{\pi_{\theta}}(s,a)=g(s,a)-J_g(\theta)+\mathbf{E}_{s'\sim P(\cdot|s, a)}\left[V_g^{\pi_{\theta}}(s')\right]\tag{5}\] where \(g\in\{r, c\}\) and \(V_g^{\pi_{\theta}}:\mathcal{S}\rightarrow \mathbb{R}\) is given as \(V_g^{\pi_{\theta}}(s) = \sum_{a\in\mathcal{A}}\pi_{\theta} (a|s)Q_g^{\pi_{\theta}}(s, a), ~\forall s\in\mathcal{S}\). Note that if \(Q_g^{\pi_{\theta}}\) satisfies \((\ref{eq95bellman})\), then it is also satisfied by \(Q_g^{\pi_{\theta}}+c\) for any arbitrary, \(c\). To uniquely define the value functions, we assume that \(\sum_{s\in\mathcal{S}}d^{\pi_{\theta}}(s)V_g^{\pi_{\theta}}(s)=0\). In this case, \(V_g^{\pi_{\theta}}(s)\) is given by, \[\label{def95v95pi95theta95s} \begin{align} V_g^{\pi_{\theta}}(s) &= \sum_{t=0}^{\infty} \sum_{s'\in\mathcal{S}}\left[(P^{\pi_{\theta}})^t(s, s') - d^{\pi_{\theta}}(s')\right]g^{\pi_{\theta}}(s')= \sum_{t=0}^{\infty}\mathbf{E}\left[\left\{g(s_t,a_t)-J_g(\theta)\right\}\big\vert s_0=s\right] \end{align}\tag{6}\] where the expectation is computed over all \(\pi_{\theta}\)-induced trajectories. In a similar way, \(\forall (s, a)\), one can uniquely define \(Q_g^{\pi_{\theta}}(s, a)\), \(g\in\{r, c\}\) as follows. \[\label{def95q95pi95theta95s} Q_g^{\pi_{\theta}}(s,a)=\sum_{t=0}^{\infty}\mathbf{E}\left[\big\{g(s_t,a_t)-J_g(\theta)\big\}\big\vert s_0=s,a_0=a\right]\tag{7}\] Moreover, the advantage function \(A_g^{\pi_{\theta}}:\mathcal{S}\times \mathcal{A}\rightarrow \mathbb{R}\) is defined such that \(A_g^{\pi_{\theta}}(s, a) \triangleq Q_g^{\pi_{\theta}}(s, a) - V_g^{\pi_{\theta}}(s)\), \(\forall (s, a)\), \(\forall g\in\{r, c\}\). Assumption 1 also implies the existence of a finite mixing time. Specifically, for an ergodic MDP, \(\mathcal{M}\), the mixing time is defined as follows.

Mixing time characterizes how fast a CMDP converges to its stationary state distribution, \(d^{\pi_\theta}\), under a given policy, \(\pi_\theta\). We also define the hitting time as follows.

Define \(\pi^*\) as the optimal solution to the unparameterized problem \(\eqref{eq:def95unparametrized95optimization}\). For a given CMDP \(\mathcal{M}\), and a time horizon \(T\), the regret and constraint violation of any algorithm \(\mathbb{A}\) is defined as follows. \[\begin{align} \mathrm{Reg}_T(\mathbb{A}, \mathcal{M}) \triangleq \sum_{t=0}^{T-1} \left(J_r^{\pi^*}-r(s_t, a_t)\right), \; \mathrm{Vio}_T(\mathbb{A}, \mathcal{M}) \triangleq -\sum_{t=0}^{T-1} c(s_t, a_t) \end{align}\] where the algorithm, \(\mathbb{A}\), executes the actions, \(\{a_t\}\), \(t\in\{0, 1, \cdots \}\) based on the trajectory observed up to time, \(t\), and the state, \(s_{t+1}\) is decided according to the state transition function, \(P\). For simplicity, we shall denote the regret and constraint violation as \(\mathrm{Reg}_T\) and \(\mathrm{Vio}_T\) respectively. Our goal is to design an algorithm \(\mathbb{A}\) that achieves low regret and constraint violation bounds.

3 Proposed Algorithm↩︎

We solve \(\eqref{eq:def95constrained95optimization}\) via a primal-dual algorithm based on the following problem. \[\begin{align} \label{eq:def95saddle95point95opt} \max_{\theta\in\Theta}\min_{\lambda\geq 0}~ J_{\mathrm{L}}(\theta, \lambda), \end{align}\tag{8}\] where \(J_{\mathrm{L}}(\theta, \lambda) \triangleq J_r(\theta) +\lambda J_c(\theta)\). The function, \(J_{\mathrm{L}}(\cdot, \cdot)\), is called the Lagrange function and \(\lambda\) the Lagrange multiplier. Our algorithm updates the pair \((\theta, \lambda)\) following the policy gradient iteration as shown below \(\forall k\in\{1, \cdots, K\}\) with an initial point \((\theta_1, \lambda_1)\), \(\lambda_1=0\). \[\begin{align} \label{eq:update} \begin{aligned} \theta_{k+1} &= \theta_k+\alpha\nabla_\theta J_{\mathrm{L}}(\theta_k, \lambda_k),~ \lambda_{k+1} = \mathcal{P}_{[0,\frac{2}{\delta}]}[\lambda_k -\beta J_c(\theta_k)] \end{aligned} \end{align}\tag{9}\] where \(\alpha\) and \(\beta\) are learning parameters and \(\delta\) is the Slater parameter introduced in the following assumption. Finally, for any set, \(\Lambda\), \(\mathcal{P}_{\Lambda}[\cdot]\) denotes projection onto \(\Lambda\). The assumption stated below ensures that we have at least one feasible interior point solution to 2 .

Note that in 9 , the dual update is projected onto the set \([0,\frac{2}{\delta}]\) because the optimal dual variable for the parameterized problem is bounded in Lemma 16. The gradient of \(J_{\mathrm{L}}(\cdot, \lambda)\) can be computed by invoking a variant of the well-known policy gradient theorem [25].

where \(\forall (s, a)\), \(A_{\mathrm{L},\lambda}^{\pi_\theta}(s,a)\triangleq A_r^{\pi_\theta}(s, a)+\lambda A_c^{\pi_\theta}(s, a)\), and \(\{A_g^{\pi_\theta}\}_{g\in\{r, c\}}\) are the advantage functions corresponding to reward and cost. In typical RL scenarios, learners do not have access to the state transition function, \(P\), and thereby to the functions \(d^{\pi_\theta}\) and \(A^{\pi_\theta}_{\mathrm{L}, \lambda}\). This makes computing the exact gradient a difficult task. In Algorithm 1, we demonstrate how one can still obtain good estimates of the gradient using sampled trajectories.

Algorithm 1 runs \(K\) epochs, each of duration \(H=16t_{\mathrm{hit}}t_{\mathrm{mix}}T^{\xi}(\log T)^2\) where \(\xi\in (0, 1)\) defines a constant whose value is specified later. Clearly, \(K=T/H\). Note that the learner is assumed to know the horizon length, \(T\). This can be relaxed utilizing the well-known doubling trick [26]. Additionally, it is assumed that the algorithm is aware of the mixing time and the hitting time. This assumption is common in the literature [13], [17]. The first step in obtaining a gradient estimate is estimating the advantage value for a given pair \((s, a)\). This can be accomplished via Algorithm 2. At the \(k\)th epoch, a \(\pi_{\theta_k}\)-induced trajectory, \(\mathcal{T}_k=\{(s_t, a_t)\}_{t=(k-1)H}^{kH-1}\) is obtained and subsequently passed to Algorithm 2 that searches for subtrajectories within it that start with a given state \(s\), are of length \(N=4t_{\mathrm{mix}}(\log T)\), and are at least \(N\) distance apart from each other. Assume that there are \(M\) such subtrajectories. Let the total reward and cost of the \(i\)th subtrajectory be \(\{r_i, c_i\}\) respectively and \(\tau_i\) be its starting time. The value function estimates for the \(k\)th epoch are \[\begin{align} \label{eq:eq951395new95rev} \hat{Q}_g^{\pi_{\theta_k}}(s, a) = \dfrac{1}{\pi_{\theta_k}(a|s)} \left[\dfrac{1}{M}\sum_{i=1}^M g_i \mathrm{1}(a_{\tau_i}=a)\right], ~\hat{V}_g^{\pi_{\theta_k}}(s) = \dfrac{1}{M}\sum_{i=1}^M g_i , ~~\forall g\in\{r, c\} \end{align}\tag{10}\]

This leads to the following advantage estimator. \[\begin{align} \hat{A}^{\pi_{\theta_k}}_{\mathrm{L}, \lambda_k} (s, a) = \hat{A}^{\pi_{\theta_k}}_{r} (s, a) + \lambda_k \hat{A}^{\pi_{\theta_k}}_{c} (s, a), \end{align}\]

where \(\hat{A}^{\pi_{\theta_k}}_{g}(s, a) = \hat{Q}^{\pi_{\theta_k}}_{g}(s, a) - \hat{V}^{\pi_{\theta_k}}_{g}(s)\), \(g\in\{r,c\}\). Finally, the gradient estimator is, \[\begin{align} \label{eq95grad95estimate} & \omega_k\triangleq\hat{\nabla}_{\theta} J_{\mathrm{L}}(\theta_k,\lambda_k) =\dfrac{1}{H}\sum_{t=t_k}^{t_{k+1}-1}\hat{A}_{\mathrm{L},\lambda_k}^{\pi_{\theta_k}}(s_{t}, a_{t})\nabla_{\theta}\log \pi_{\theta_k}(a_{t}|s_{t}) \end{align}\tag{11}\] where \(t_k=(k-1)H\) is the starting time of the \(k\)th epoch. The parameters are updated following [udpates95algorotihm]. To update the Lagrange multiplier, we need an estimation of \(J_c(\theta_k)\), which is obtained as the average cost of the \(k\)th epoch. It should be noted that we remove the first \(N\) samples from the \(k\)th epoch because we require the state distribution emanating from the remaining samples to be close enough to the stationary distribution \(d^{\pi_{\theta_k}}\), which is the key to make \(\hat{J}_c(\theta_k)\) close to \(J_c(\theta_k)\). The following lemma demonstrates that \(\hat{A}_{\mathrm{L},\lambda_k}^{\pi_{\theta_k}}(s, a)\) is a good estimator of \(A_{\mathrm{L},\lambda_k}^{\pi_{\theta_k}}(s, a)\).

Lemma 2 shows that the \(L_2\) error of our proposed advantage estimator can be bounded above as \(\tilde{\mathcal{O}}(T^{-\xi})\). We later utilize the above result to prove the goodness of the gradient estimator. It is to be clarified that our Algorithm 2 is inspired by Algorithm 2 of [17]. However, while the authors of [17] choose \(H=\tilde{\mathcal{O}}(1)\), we adapt \(H=\tilde{\mathcal{O}}(T^{\xi})\). This subtle change is important in proving a sublinear regret for general parametrization.

4 Global Convergence Analysis↩︎

This section first shows that the sequence \(\{\theta_k, \lambda_k\}_{k=1}^K\) produced by Algorithm 1 is such that their associated Lagrange sequence \(\{J_{\mathrm{L}}(\theta_k, \lambda_k)\}_{k=1}^{\infty}\) converges globally. By expanding the Lagrange function, we then exhibit convergence of each of its components \(\{J_g(\theta_k, \lambda_k)\}_{k=1}^K\), \(g\in\{r,c\}\). This is later used for regret and constraint violation analysis. Before delving into the details, we would like to state a few necessary assumptions.

Note that by combining Assumption 3 with Lemma 2 and using the gradient estimator as given in \((\ref{eq95grad95estimate})\), one can deduce the following result.

Lemma 3 claims that the gradient estimation error can be bounded as \(\tilde{\mathcal{O}}(T^{-\xi})\). We will use this result later to prove the global convergence of our algorithm.

Assumption 5 is also called Fisher-non-degenerate policy assumption and is quite common in the literature [29], [32], [33] in the policy gradient analysis. [29][Assumption 2.1] provided a detailed discussion on the requirement of policy class to satisfy the assumption 5. Moreover, [34] describes a class of policies that obeys assumptions \(\ref{ass95score}-\ref{ass954}\) simultaneously. The Lagrange difference lemma stated below is important in establishing global convergence.

We now present a general framework for the convergence analysis of Algorithm 1.

Lemma 5 proves that the optimality error of the Lagrange sequence can be bounded by the average first-order and second-order norms of the intermediate gradients. Note the presence of \(\epsilon_{\mathrm{bias}}\) in the result. If the policy class is severely restricted, the optimality bound loses its importance. Consider the expectation of the second term in 15 . Note that, \[\label{eq95second95term95bound} \begin{align} &\bigg(\frac{1}{K}\sum_{k=1}^{K}\mathbf{E}\Vert\omega_k-\omega^*_k\Vert\bigg)^2\leq \frac{1}{K}\sum_{k=1}^{K}\mathbf{E}\bigg[\Vert\omega_k-\omega^*_k\Vert^2\bigg]\nonumber=\frac{1}{K}\sum_{k=1}^{K}\mathbf{E}\bigg[\Vert\omega_k-F_\rho(\theta_k)^\dagger\nabla_\theta J_{\mathrm{L}}(\theta_k,\lambda_k)\Vert^2\bigg]\\ &\leq \frac{2}{K}\sum_{k=1}^{K}\Bigg\lbrace \mathbf{E}\bigg[\Vert\omega_k-\nabla_\theta J_{\mathrm{L}}(\theta_k,\lambda_k)\Vert^2\bigg]\nonumber+ \mathbf{E}\bigg[\Vert \nabla_\theta J_{\mathrm{L}}(\theta_k,\lambda_k)- F_\rho(\theta_k)^\dagger\nabla_\theta J_{\mathrm{L}}(\theta_k,\lambda_k)\Vert^2\bigg]\Bigg\rbrace \\ &\overset{(a)}{\leq} \frac{2}{K}\sum_{k=1}^{K}\mathbf{E}\bigg[\Vert \omega_k-\nabla_\theta J_{\mathrm{L}}(\theta_k,\lambda_k)\Vert^2\bigg]\nonumber+\frac{2}{K}\sum_{k=1}^{K}\left(1+\dfrac{1}{\mu_F^2}\right)\mathbf{E}\bigg[\Vert \nabla_\theta J_{\mathrm{L}}(\theta_k,\lambda_k)\Vert^2\bigg] \end{align}\tag{16}\]

where \((a)\) follows from Assumption 5. The expectation of the third term in 15 can be bounded as \[\label{eq95third95term95bound} \dfrac{1}{K}\sum_{k=1}^{K}\mathbf{E}\bigg[\Vert\omega_k\Vert^2\bigg]\leq \dfrac{1}{K}\sum_{k=1}^{K}\mathbf{E}\left[\norm{\nabla_\theta J_{\mathrm{L}}(\theta_k,\lambda_k)}^2\right] \nonumber+ \dfrac{1}{K}\sum_{k=1}^{K}\mathbf{E}\bigg[\Vert \omega_k-\nabla_\theta J_{\mathrm{L}}(\theta_k,\lambda_k)\Vert^2\bigg]\tag{17}\] In both \(\eqref{eq95second95term95bound}\) and \(\eqref{eq95third95term95bound}\), \(\mathbf{E}\norm{\omega_k-\nabla_{\theta}J_{\mathrm{L}}(\theta_k,\lambda_k)}^2\) is bounded above by Lemma 3. To bound the term, \(\mathbf{E}\norm{\nabla_\theta J_{\mathrm{L}}(\theta_k,\lambda_k)}^2\), the following lemma is applied.

Note the presence of \(\beta\) in 18 . To ensure convergence, \(\beta\) must be a function of \(T\). Invoking Lemma 3, we get the following relation under the same set of assumptions and the choice of parameters as in Lemma 6. \[\begin{align} \label{eq9533} \begin{aligned} \dfrac{1}{K}\sum_{k=1}^{K} \mathbf{E}\norm{\nabla_\theta J_{\mathrm{L}}(\theta_k,\lambda_k)}^2\leq \tilde{\mathcal{O}}\left(\dfrac{AG^2t_{\mathrm{mix}}^2}{\delta^2 T^{\xi}}\right)+\tilde{\mathcal{O}}\left(\dfrac{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}{\delta^2 T^{1-\xi}}\right)+\beta \end{aligned} \end{align}\tag{19}\] Applying Lemma 3 and 19 in 17 , we arrive at, \[\begin{align} \label{eq9534} \dfrac{1}{K}\sum_{k=1}^{K}\mathbf{E}\bigg[\Vert\omega_k\Vert^2\bigg]&\leq \tilde{\mathcal{O}}\left(\dfrac{AG^2t_{\mathrm{mix}}^2}{\delta^2 T^{\xi}}+\dfrac{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}{\delta^2 T^{1-\xi}}\right)+\beta \end{align}\tag{20}\] Similarly, using \((\ref{eq95second95term95bound})\), we deduce the following. \[\begin{align} \label{eq9535} \begin{aligned} \frac{1}{K}\sum_{k=1}^{K}\mathbf{E}\Vert\omega_k-\omega^*_k\Vert \leq \left(1+\dfrac{1}{\mu_F}\right)\sqrt{\beta}+ \left(1+\dfrac{1}{\mu_F}\right)\tilde{\mathcal{O}}\left(\dfrac{\sqrt{A}Gt_{\mathrm{mix}}}{\delta T^{\xi/2}}+\dfrac{\sqrt{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}}{\delta T^{(1-\xi)/2}}\right) \end{aligned} \end{align}\tag{21}\] Inequalities 20 and 21 lead to the following global convergence of the Lagrange function.

Lemma 7 establishes that the average difference between \(J_{\mathrm{L}}(\pi^*, \lambda_k)\) and \(J_{\mathrm{L}}(\theta_k, \lambda_k)\) is \(\tilde{\mathcal{O}}(\sqrt{\beta}+T^{-\xi/2}+T^{-(1-\xi)/2})\). Expanding the function, \(J_{\mathrm{L}}\), and utilizing the update rule of the Lagrange multiplier, we achieve the global convergence for the objective and the constraint in Theorem 1 (stated below). In its proof, Lemma 18 (stated in the appendix) serves as an important tool in disentangling the convergence rates of regret and constraint violation. Interestingly, Lemma 18 is built upon the strong duality property of the unparameterized optimization 2 and has no apparent direct connection with the parameterized setup.

Theorem 1 establishes \(\tilde{\mathcal{O}}(T^{-1/5})\) convergence rates for both the objective and the constraint violation.

5 Regret and Violation Analysis↩︎

In this section, we use the convergence result of the previous section to bound the expected regret and constraint violation of Algorithm 1. Note that the regret and constraint violation decompose as, \[\begin{align} &\mathrm{Reg}_T = \sum_{t=0}^{T-1} \left(J_r^{\pi^*} - r(s_t, a_t)\right)=H\sum_{k=1}^{K}\left(J_r^{\pi^*}-J({\theta_k})\right)+\sum_{k=1}^{K}\sum_{t\in\mathcal{I}_k} \left(J(\theta_k)-r(s_t, a_t)\right)\\ &\mathrm{Vio}_T =\sum_{t=0}^{T-1} \left(-c(s_t, a_t)\right)=H\sum_{k=1}^{K}\left(-J_c({\theta_k})\right)+\sum_{k=1}^{K}\sum_{t\in\mathcal{I}_k} \left(J_c(\theta_k)-c(s_t, a_t)\right)\nonumber \end{align}\]

where \(\mathcal{I}_k\triangleq \{(k-1)H, \cdots, kH-1\}\). Observe that the expectation of the first terms in regret and violation can be bounded by Theorem 1. The expectation of the second term in regret and violation can be expanded as follows, \[\label{eq9538} \begin{align} &\mathbf{E}\left[\sum_{k=1}^{K}\sum_{t\in\mathcal{I}_k} \left(J_g(\theta_k)-g(s_t, a_t)\right)\right]\overset{(a)}{=}\mathbf{E}\left[\sum_{k=1}^{K}\sum_{t\in\mathcal{I}_k} \mathbf{E}_{s'\sim P(\cdot|s_t, a_t)}[V_g^{\pi_{\theta_k}}(s')]-Q_g^{\pi_{\theta_k}}(s_t, a_t)\right]\\ &\overset{(b)}{=}\mathbf{E}\left[\sum_{k=}^{K}\sum_{t\in\mathcal{I}_k} V_g^{\pi_{\theta_k}}(s_{t+1})-V_g^{\pi_{\theta_k}}(s_t)\right]=\mathbf{E}\left[\sum_{k=1}^{K} V_g^{\pi_{\theta_k}}(s_{kH})-V_g^{\pi_{\theta_k}}(s_{(k-1)H})\right]\\ &=\mathbf{E}\left[\sum_{k=1}^{K-1} V_g^{\pi_{\theta_{k+1}}}(s_{kH})-V_g^{\pi_{\theta_k}}(s_{kH})\right]+\mathbf{E}\left[V_g^{\pi_{\theta_K}}(s_{T})-V_g^{\pi_{\theta_0}}(s_{0})\right] \end{align}\tag{22}\]

where \(g\in\{r, c\}\). Equality \((a)\) uses the Bellman equation and \((b)\) follows from the definition of \(Q_g\). The first term in the last line of Eq. 22 can be upper bounded by Lemma 8 (stated below). On the other hand, the second term can be upper bounded as \(\mathcal{O}(t_{\mathrm{mix}})\) using Lemma 9.

Lemma 8 states that the obtained policy parameters are such that the average consecutive difference in the sequence \(\{J_g(\theta_k)\}_{k=1}^K\), \(g\in\{r, c\}\) decreases with time horizon, \(T\). We would like to emphasize that Lemma 8 works for both reward and constraint functions. Hence, we can prove our regret guarantee and constraint violation as shown below.

The detailed expressions of these bounds are provided in the Appendix. Here, we keep only those terms that emphasize the order of \(T\). Note that our result outperforms the state-of-the-art model-free tabular result in average-reward CMDP [8]. However, our regret bound is worse than that achievable in average reward unconstrained MDP with general parameterization [13]. Interestingly, the gap between the convergence results of constrained and unconstrained setups is a common observation across the literature. For example, in the tabular model-free average reward MDP, the state-of-the-art regret bound for unconstrained setup, \(\tilde{\mathcal{O}}(T^{1/2})\) [17], is better than that in the constrained setup, \(\tilde{\mathcal{O}}(T^{5/6})\) [8].

6 Conclusions↩︎

This paper establishes the first sublinear regret and constraint violation bounds in the average reward CMDP setup with general parametrization (and do not assume the underlying constrained Markov Decision Process (CMDP) to be tabular or linear). We show that our proposed algorithm achieves \(\tilde{\mathcal{O}}(T^{4/5})\) regret and constraint violation bounds where \(T\) is the time horizon. Note that the state of the art in unconstrained counterpart is \(\tilde{\mathcal{O}}({T}^{3/4})\). Closing this gap by designing more efficient algorithms is an open question in the average reward CMDP literature with the general parametrization. Moreover, our current algorithm requires the knowledge of mixing time. Relaxing such assumptions is another important future direction in realistic settings. For further discussions on future work directions, the readers are referred to [35].

7 Acknowledgement↩︎

This research was supported in part by the National Science Foundation under grant CCF-2149588 and Cisco, Inc.

8 Proofs for Lemmas in Section 3↩︎

8.1 Proof of Lemma 1↩︎

Since the first step of the proof works in the same way for functions \(J_r\) and \(J_c\), we use the generic notations \(J_g, V_g, Q_g\) where \(g=r,c\) and derive the following. \[\label{eq9522} \begin{align} &\nabla_{\theta} V_g^{\pi_{\theta_k}}(s) =\nabla_{\theta}\bigg(\sum_{a}\pi_{\theta}(a|s)Q_g^{\pi_{\theta}}(s, a)\bigg)\\ &=\sum_{a}\bigg(\nabla_{\theta}\pi_{\theta}(a|s)\bigg)Q_g^{\pi_{\theta}}(s, a)+\sum_{a}\pi_\theta(a|s)\nabla_{\theta} Q_g^{\pi_{\theta}}(s, a)\\ &\overset{(a)}=\sum_{a}\pi_{\theta}(a|s)\bigg(\nabla_{\theta}\log\pi_{\theta}(a|s)\bigg)Q_g^{\pi_{\theta}}(s, a)+\sum_{a}\pi_\theta(a|s)\nabla_{\theta} \bigg(g(s, a)-J_g(\theta)+\sum_{s'}P(s'|s, a)V_g^{\pi_{\theta}}(s')\bigg)\\ &=\sum_{a}\pi_\theta(a|s)\bigg(\nabla_{\theta}\log\pi_{\theta}(a|s)\bigg)Q_g^{\pi_{\theta}}(s, a)+\sum_{a}\pi_\theta(a|s) \bigg(\sum_{s'}P(s'|s,a)\nabla_{\theta} V_g^{\pi_{\theta}}(s')\bigg) - \nabla_{\theta}J_g(\theta) \end{align}\tag{24}\] where the step (a) is a consequence of \(\nabla_{\theta}\log\pi_{\theta}=\frac{\nabla\pi_{\theta}}{\pi_{\theta}}\) and the Bellman equation. Multiplying both sides by \(d^{\pi_{\theta}}(s)\), taking a sum over \(s\in\mathcal{S}\), and rearranging the terms, we obtain the following. \[\begin{align} \begin{aligned} &\nabla_{\theta}J_g(\theta)=\sum_{s}d^{\pi_{\theta}}(s)\nabla_{\theta}J_g(\theta)\\ &=\sum_{s}d^{\pi_{\theta}}(s)\sum_{a}\pi_\theta(a|s)\bigg(\nabla_{\theta}\log\pi_{\theta}(a|s)\bigg)Q_g^{\pi_{\theta}}(s, a)+\sum_{s}d^{\pi_{\theta}}(s)\sum_{a}\pi_\theta(a|s) \bigg(\sum_{s'}P(s'|s,a)\nabla_{\theta} V_g^{\pi_{\theta}}(s')\bigg)\\ &- \sum_{s}d^{\pi_{\theta}}(s)\nabla_{\theta}V_g^{\pi_\theta}(s)\\ &\overset{}{=}\mathbf{E}_{s\sim d^{\pi_\theta}, a\sim \pi_\theta(\cdot|s)}\bigg[Q_g^{\pi_{\theta}}(s, a)\nabla_{\theta}\log\pi_{\theta}(a|s)\bigg]+\sum_{s}d^{\pi_{\theta}}(s) \sum_{s'}P^{\pi_\theta}(s'|s)\nabla_{\theta} V_g^{\pi_{\theta}}(s') - \sum_{s}d^{\pi_{\theta}}(s)\nabla_{\theta}V_g^{\pi_\theta}(s)\\ &\overset{(a)}{=}\mathbf{E}_{s\sim d^{\pi_\theta}, a\sim \pi_\theta(\cdot|s)}\bigg[Q_g^{\pi_{\theta}}(s, a)\nabla_{\theta}\log\pi_{\theta}(a|s)\bigg]+ \sum_{s'}d^{\pi_{\theta}}(s')\nabla_{\theta} V_g^{\pi_{\theta}}(s') - \sum_{s}d^{\pi_{\theta}}(s)\nabla_{\theta}V_g^{\pi_\theta}(s)\\ &=\mathbf{E}_{s\sim d^{\pi_\theta}, a\sim \pi_\theta(\cdot|s)}\bigg[Q_g^{\pi_{\theta}}(s, a)\nabla_{\theta}\log\pi_{\theta}(a|s)\bigg] \end{aligned} \end{align}\] where \((a)\) uses the fact that \(d^{\pi_\theta}\) is a stationary distribution. Note that, \[\begin{align} &\mathbf{E}_{s\sim d^{\pi_{\theta}},a\sim\pi_{\theta}(\cdot|s)}\bigg[ V_g^{\pi_{\theta}}(s)\nabla\log\pi_{\theta}(a|s)\bigg]\\ &=\mathbf{E}_{s\sim d^{\pi_{\theta}}}\left[ \sum_{a\in\mathcal{A}}V_g^{\pi_{\theta}}(s)\nabla_{\theta}\pi_{\theta}(a|s)\right]\\ &=\mathbf{E}_{s\sim d^{\pi_{\theta}}}\bigg[ V_g^{\pi_{\theta}}(s)\nabla_{\theta}\left(\sum_{a\in\mathcal{A}}\pi_{\theta}(a|s)\right)\bigg] =\mathbf{E}_{s\sim d^{\pi_{\theta}}}\bigg[ V_g^{\pi_{\theta}}(s)\nabla_{\theta}(1)\bigg]=0 \end{align}\] We can, therefore, replace the function \(Q_g^{\pi_{\theta}}\) in the policy gradient with the advantage function \(A_g^{\pi_{\theta}}(s, a)=Q_g^{\pi_{\theta}}(s, a)-V_g^{\pi_{\theta}}(s)\), \(\forall (s, a)\in\mathcal{S}\times \mathcal{A}\). Thus, \[\nabla_{\theta} J_g(\theta)=\mathbf{E}_{s\sim d^{\pi_{\theta}},a\sim\pi_{\theta}(\cdot|s)}\bigg[ A_g^{\pi_{\theta}}(s,a)\nabla_{\theta}\log\pi_{\theta}(a|s)\bigg]\] The proof is completed using the definitions of \(J_{\mathrm{L},\lambda}\) and \(A_{\mathrm{L},\lambda}\).

8.2 Proof of Lemma 2↩︎

9 Proofs for the Section of Global Convergence Analysis↩︎

9.1 Proof of Lemma 3↩︎

9.2 Proof of Lemma 4↩︎

9.3 Proof of Lemma 5↩︎

9.4 Proof of Lemma 6↩︎

9.5 Proof of Theorem 1↩︎

9.5.1 Rate of Convergence of the Objective↩︎

Recall the definition of \(J_{\mathrm{L}}(\theta,\lambda)=J_r(\theta)+\lambda J_c(\theta)\). Using Lemma 7, we arrive at the following. \[\label{eq:bound95Jr1} \begin{align} &\frac{1}{K}\sum_{k=1}^{K}\mathbf{E}\bigg(J_r^{\pi^*}-J_r(\theta_k)\bigg)\leq G\left(1+\dfrac{1}{\mu_F}\right)\tilde{\mathcal{O}}\left(\sqrt{\beta}+\dfrac{\sqrt{A}Gt_{\mathrm{mix}}}{\delta T^{\xi/2}}+\dfrac{\sqrt{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}}{\delta T^{(1-\xi)/2}}\right)\\ &+\dfrac{B}{L}\tilde{\mathcal{O}}\left(\dfrac{AG^2t_{\mathrm{mix}}^2}{\delta^2 T^{\xi}}+\dfrac{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}{\delta^2 T^{1-\xi}}+\beta\right) + \mathcal{\tilde{O}}\bigg(\frac{Lt_{\mathrm{mix}}t_{\mathrm{hit}}\mathbf{E}_{s\sim d^{\pi^*}}[KL(\pi^*(\cdot\vert s)\Vert\pi_{\theta_1}(\cdot\vert s))]}{T^{1-\xi}\delta }\bigg)\\ &-\frac{1}{K}\sum_{k=1}^{K}\mathbf{E}\bigg[\lambda_k\bigg(J_{c}^{\pi^*}-J_c(\theta_k)\bigg)\bigg] + \sqrt{\epsilon_{\mathrm{bias}}} \end{align}\tag{39}\]

Thus, we need to find a bound for the last term in the above equation. \[\label{eq:bound95lambdak} \begin{align} 0&\leq (\lambda_{K+1})^2\\ &\overset{(a)}{=}\sum_{k=1}^{K}\bigg((\lambda_{k+1})^2-(\lambda_{k})^2\bigg)\\ &=\sum_{k=1}^{K}\bigg(\mathcal{P}_{[0,\frac{2}{\delta}]}\big[\lambda_{k}-\beta\hat{J}_{c}(\theta_k)\big]^2-(\lambda_{k})^2\bigg)\\ &\leq\sum_{k=1}^{K}\bigg(\big[\lambda_{k}-\beta\hat{J}_{c}(\theta_k)\big]^2-(\lambda_{k})^2\bigg)\\ &=-2\beta\sum_{k=1}^{K}\lambda_{k}\hat{J}_{c}(\theta_k)+\beta^2\sum_{k=1}^{K}\hat{J}_{c}(\theta_k)^2\\ &\overset{(b)}\leq 2\beta\sum_{k=1}^{K}\lambda_{k}(J_{c}^{\pi^*}- \hat{J}_{c}(\theta_k))+\beta^2\sum_{k=1}^{K}\hat{J}_{c}(\theta_k)^2\\ &\leq 2\beta\sum_{k=1}^{K}\lambda_{k}(J_{c}^{\pi^*}- \hat{J}_{c}(\theta_k))+2\beta^2\sum_{k=1}^{K}\hat{J}_{c}(\theta_k)^2\\ &= 2\beta\sum_{k=1}^{K}\lambda_{k}(J_{c}^{\pi^*}- J_{c}(\theta_k))+2\beta\sum_{k=1}^{K}\lambda_{k}(J_{c}(\theta_k)- \hat{J}_{c}(\theta_k))+2\beta^2\sum_{k=1}^{K}\hat{J}_{c}(\theta_k)^2 \end{align}\tag{40}\] where (a) uses \(\lambda_1=0\) and inequality (b) holds because \(\theta^*\) is a feasible solution to the constrained optimization problem. Rearranging items and taking the expectation, we have, \[\begin{align} \label{eq95appndx957195new} \begin{aligned} -\frac{1}{K}\sum_{k=1}^{K}\mathbf{E}\bigg[\lambda_{k}(J_{c}^{\pi^*}- J_{c}(\theta_k))\bigg] &\leq \frac{1}{K}\sum_{k=1}^{K}\mathbf{E}\bigg[\lambda_{k}(J_{c}(\theta_k)- \hat{J}_{c}(\theta_k))\bigg]+\frac{\beta}{K}\sum_{k=1}^{K}\mathbf{E}[\hat{J}_{c}(\theta_k)]^2\\ & \overset{(a)}{\leq} \frac{1}{K}\sum_{k=1}^{K}\mathbf{E}\left[\lambda_{k}\left(J_{c}(\theta_k)- \hat{J}_{c}(\theta_k)\right)\right]+\beta\\ &\overset{(b)}{=} \frac{1}{K}\sum_{k=1}^{K}\mathbf{E}\bigg[\lambda_{k}\left(J_{c}(\theta_k)- \mathbf{E}\left[\hat{J}_{c}(\theta_k)\big|\theta_k\right]\right)\bigg]+\beta\\ &\leq \frac{1}{K}\sum_{k=1}^{K}\mathbf{E}\bigg[\lambda_{k}\left|J_{c}(\theta_k)- \mathbf{E}\left[\hat{J}_{c}(\theta_k)\big|\theta_k\right]\right|\bigg]+\beta\overset{(c)}{\leq} \frac{2}{\delta T^2}+\beta \end{aligned} \end{align}\tag{41}\] where (a) results from \(|\hat{J}_{c, \rho}(\theta)|^2\leq 1\), \(\forall \theta\in\Theta\) and (b) uses the fact that \(\hat{J}_{c, \rho}(\theta_k)\) and \(\lambda_k\) are conditionally independent given \(\theta_k\). Finally, (c) is a consequence of Lemma 13. Combining 41 with 39 , we deduce, \[\label{eq95bound95Jr95final} \begin{align} &\frac{1}{K}\sum_{k=1}^{K}\mathbf{E}\bigg(J_r^{\pi^*}-J_r(\theta_k)\bigg)\\ &\leq \sqrt{\epsilon_{\mathrm{bias}}} + G\left(1+\dfrac{1}{\mu_F}\right)\tilde{\mathcal{O}}\left(\sqrt{\beta}+\dfrac{\sqrt{A}Gt_{\mathrm{mix}}}{\delta T^{\xi/2}}+\dfrac{\sqrt{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}}{\delta T^{(1-\xi)/2}}\right)+ \mathcal{O}\left(\dfrac{1}{\delta T^2}+\beta\right)\\ &+\dfrac{B}{L}\tilde{\mathcal{O}}\left(\dfrac{AG^2t_{\mathrm{mix}}^2}{\delta^2 T^{\xi}}+\dfrac{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}{\delta^2 T^{1-\xi}}+\beta\right) + \mathcal{\tilde{O}}\bigg(\frac{Lt_{\mathrm{mix}}t_{\mathrm{hit}}\mathbf{E}_{s\sim d^{\pi^*}}[KL(\pi^*(\cdot\vert s)\Vert\pi_{\theta_1}(\cdot\vert s))]}{T^{1-\xi}\delta }\bigg)\\ &\leq \sqrt{\epsilon_{\mathrm{bias}}} + G\left(1+\dfrac{1}{\mu_F}\right)\tilde{\mathcal{O}}\left(\sqrt{\beta}+\dfrac{\sqrt{A}Gt_{\mathrm{mix}}}{\delta T^{\xi/2}}+\dfrac{\sqrt{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}}{\delta T^{(1-\xi)/2}}\right) \end{align}\tag{42}\]

The last inequality presents only the dominant terms of \(\beta\) and \(T\).

9.5.2 Rate of Constraint Violation↩︎

Since \(\{\lambda_k\}_{k=1}^{K}\) are derived by applying the dual update in Algorithm 1, we have, \[\label{eq95appndx957395new} \begin{align} &\mathbf{E}\left\vert\lambda_{k+1} - \dfrac{2}{\delta}\right\vert^2 \overset{(a)}{\leq} \mathbf{E}\left|\lambda_{k} - \beta \hat{J}_c(\theta_{k}) - \dfrac{2}{\delta}\right|^2\\ &=\mathbf{E}\left|\lambda_{k} -\dfrac{2}{\delta}\right|^2 -2\beta \mathbf{E}\left[\hat{J}_c(\theta_k)\left(\lambda_{k} -\dfrac{2}{\delta}\right)\right] +\beta^2 \mathbf{E}\left[\hat{J}^2_c(\theta_{k})\right] \\ &\overset{(b)}\leq\mathbf{E}\left|\lambda_{k} -\dfrac{2}{\delta}\right|^2 - 2\beta \mathbf{E}\left[J_c(\theta_{k})\left(\lambda_{k} -\dfrac{2}{\delta}\right)\right]-2\beta \mathbf{E}\left[\left(\hat{J}_c(\theta_{k})-J_c(\theta_{k})\right)\left(\lambda_{k}-\dfrac{2}{\delta}\right)\right] + \beta^2\\ &\overset{(c)}{=}\mathbf{E}\left|\lambda_{k} -\dfrac{2}{\delta}\right|^2 - 2\beta \mathbf{E}\left[J_c(\theta_{k})\left(\lambda_{k} -\dfrac{2}{\delta}\right)\right]-2\beta \mathbf{E}\left[\left(\mathbf{E}\left[\hat{J}_c(\theta_{k})\big|\theta_k\right]-J_c(\theta_{k})\right)\left(\lambda_{k}-\dfrac{2}{\delta}\right)\right] + \beta^2\\ &\leq \mathbf{E}\left|\lambda_{k} -\dfrac{2}{\delta}\right|^2 - 2\beta \mathbf{E}\left[J_c(\theta_{k})\left(\lambda_{k} -\dfrac{2}{\delta}\right)\right]+2\beta \mathbf{E}\left[\left|\mathbf{E}\left[\hat{J}_c(\theta_{k})\big|\theta_k\right]-J_c(\theta_{k})\right|\left|\lambda_{k}-\dfrac{2}{\delta}\right|\right] + \beta^2\\ &\overset{(d)}{\leq} \mathbf{E}\left|\lambda_{k} -\dfrac{2}{\delta}\right|^2 - 2\beta \mathbf{E}\left[J_c(\theta_{k})\left(\lambda_{k} -\dfrac{2}{\delta}\right)\right] + \dfrac{4\beta}{\delta T^2} + \beta^2 \end{align}\tag{43}\] where \((a)\) is due to the non-expansiveness of the projection \(\mathcal{P}_{[0, \frac{2}{\delta}]}\) and \((b)\) holds because \(\hat{J}_c(\theta)\in[0,1]\), \(\forall \theta\in\Theta\) according to its definition in Algorithm 1. Finally, \((c)\) is a consequence of the fact that \(\hat{J}_c(\theta_k)\) and \(\lambda_k\) are conditionally independent given \(\theta_k\) whereas \((d)\) applies \(|\lambda_k-\frac{2}{\delta}|\leq \frac{2}{\delta}\) and Lemma 13. Averaging 43 over \(k\in\{1,\ldots,K\}\), we get, \[\begin{align} \frac{1}{K}\sum_{k=1}^{K} \mathbf{E}\left[J_c(\theta_k)\left(\lambda_{k} -\frac{2}{\delta}\right)\right] &\leq \frac{\left\vert\lambda_{1} - \frac{2}{\delta}\right\vert^2 -\left\vert\lambda_{K+1} - \frac{2}{\delta}\right\vert^2 }{2\beta K} + \dfrac{2}{\delta T^2} + \dfrac{\beta}{2} \overset{(a)}{\leq} \dfrac{2}{\delta^2 \beta K} + \dfrac{2}{\delta T^2} + \dfrac{\beta}{2} \end{align}\] where (a) uses \(\lambda_1=0\). Note that \(\lambda_k J_c^{\pi^*}\geq 0\), \(\forall k\). Adding the above inequality to 39 at both sides, we, therefore, have, \[\label{eq:bound95Jc2} \begin{align} &\mathbf{E}\bigg[J_r^{\pi^*}-\frac{1}{K}\sum_{k=1}^{K}J_r(\theta_k)\bigg]+\frac{2}{\delta}\mathbf{E}\bigg[\frac{1}{K}\sum_{k=1}^{K}-J_c(\theta_k)\bigg]\leq \sqrt{\epsilon_{\mathrm{bias}}} +\frac{2}{\delta^2\beta K} +\frac{2}{T^2\delta}+ \frac{\beta}{2}\\ &+G\left(1+\dfrac{1}{\mu_F}\right)\tilde{\mathcal{O}}\left(\sqrt{\beta}+\dfrac{\sqrt{A}Gt_{\mathrm{mix}}}{\delta T^{\xi/2}}+\dfrac{\sqrt{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}}{\delta T^{(1-\xi)/2}}\right) + \dfrac{B}{L}\tilde{\mathcal{O}}\left(\dfrac{AG^2t_{\mathrm{mix}}^2}{\delta^2 T^{\xi}}+\dfrac{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}{\delta^2 T^{1-\xi}}+\beta\right)\\ &+ \mathcal{\tilde{O}}\bigg(\frac{Lt_{\mathrm{mix}}t_{\mathrm{hit}}\mathbf{E}_{s\sim d^{\pi^*}}[KL(\pi^*(\cdot\vert s)\Vert\pi_{\theta_1}(\cdot\vert s))]}{T^{1-\xi}\delta }\bigg) \end{align}\tag{44}\] Since the functions \(\{J_g(\theta_k)\}, k\in\{0, \cdots, K-1\}, g\in\{r, c\}\) are linear in occupancy measure, there exists a policy \(\bar{\pi}\) such that the following holds \(\forall g\in\{r, c\}\). \[\label{eq95avg95value} \frac{1}{K}\sum_{k=1}^{K}J_g(\theta_k)=J_g^{\bar\pi}\tag{45}\] Injecting the above relation to 44 , we have \[\begin{align} &\mathbf{E}\bigg[J_r^{\pi^*}-J_r^{\bar\pi}\bigg]+\frac{2}{\delta}\mathbf{E}\bigg[-J_c^{\bar\pi}\bigg]\leq \sqrt{\epsilon_{\mathrm{bias}}}+\frac{2}{\delta^2\beta K} +\frac{2}{T^2\delta}+ \frac{\beta}{2} \\ &+G\left(1+\dfrac{1}{\mu_F}\right)\tilde{\mathcal{O}}\left(\sqrt{\beta}+\dfrac{\sqrt{A}Gt_{\mathrm{mix}}}{\delta T^{\xi/2}}+\dfrac{\sqrt{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}}{\delta T^{(1-\xi)/2}}\right)\\ &+\dfrac{B}{L}\tilde{\mathcal{O}}\left(\dfrac{AG^2t_{\mathrm{mix}}^2}{\delta^2 T^{\xi}}+\dfrac{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}{\delta^2 T^{1-\xi}}+\beta\right) + \mathcal{\tilde{O}}\bigg(\frac{Lt_{\mathrm{mix}}t_{\mathrm{hit}}\mathbf{E}_{s\sim d^{\pi^*}}[KL(\pi^*(\cdot\vert s)\Vert\pi_{\theta_1}(\cdot\vert s))]}{T^{1-\xi}\delta }\bigg) \end{align}\] By Lemma 18, we arrive at, \[\label{eq9583} \begin{align} &\mathbf{E}\bigg[-J_c^{\bar\pi}\bigg]\\ &\leq \delta\sqrt{\epsilon_{\mathrm{bias}}}+\frac{2}{\delta\beta K} +\frac{2}{T^2}+\frac{\delta\beta}{2}+G\left(1+\dfrac{1}{\mu_F}\right)\tilde{\mathcal{O}}\left(\delta\sqrt{\beta}+\dfrac{\sqrt{A}Gt_{\mathrm{mix}}}{ T^{\xi/2}}+\dfrac{\sqrt{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}}{ T^{(1-\xi)/2}}\right)\\ &+\dfrac{B}{L}\tilde{\mathcal{O}}\left(\dfrac{AG^2t_{\mathrm{mix}}^2}{\delta T^{\xi}}+\dfrac{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}{\delta T^{1-\xi}}+\delta\beta\right) + \mathcal{\tilde{O}}\bigg(\frac{Lt_{\mathrm{mix}}t_{\mathrm{hit}}\mathbf{E}_{s\sim d^{\pi^*}}[KL(\pi^*(\cdot\vert s)\Vert\pi_{\theta_1}(\cdot\vert s))]}{T^{1-\xi}}\bigg)\\ &\leq \delta\sqrt{\epsilon_{\mathrm{bias}}} + \tilde{\mathcal{O}}\left(\dfrac{2t_{\mathrm{mix}}t_{\mathrm{hit}}}{\delta \beta T^{1-\xi}}\right) + G\left(1+\dfrac{1}{\mu_F}\right)\tilde{\mathcal{O}}\left(\delta\sqrt{\beta}+\dfrac{\sqrt{A}Gt_{\mathrm{mix}}}{ T^{\xi/2}}+\dfrac{\sqrt{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}}{ T^{(1-\xi)/2}}\right) \end{align}\tag{46}\]

The last inequality presents only the dominant terms of \(\beta\) and \(T\).

9.5.3 Optimal Choice of \(\beta\) and \(\xi\)↩︎

If we choose \(\beta=T^{-\eta}\) for some \(\eta\in(0,1)\), then following 42 and 46 , we can write, \[\begin{align} \frac{1}{K}\sum_{k=1}^{K}\mathbf{E}\bigg(J_r^{\pi^*}-J_r(\theta_k)\bigg)&\leq \sqrt{\epsilon_{\mathrm{bias}}} + \tilde{\mathcal{O}}\left(T^{-\eta/2}+T^{-\xi/2}+T^{-(1-\xi)/2}\right),\\ \mathbf{E}\left[\frac{1}{K}\sum_{k=1}^{K}-J_c(\theta_k)\right]&\leq \delta\sqrt{\epsilon_{\mathrm{bias}}} + \tilde{\mathcal{O}}\left(T^{-(1-\xi-\eta)}+T^{-\eta/2}+T^{-\xi/2}+T^{-(1-\xi)/2}\right) \end{align}\]

Clearly, the optimal values of \(\eta\) and \(\xi\) can be obtained by solving the following optimization. \[\begin{align} {\max}_{(\eta, \xi)\in (0,1)^2} \min \left\lbrace 1-\xi-\eta, \dfrac{\eta}{2}, \dfrac{\xi}{2}, \dfrac{1-\xi}{2} \right\rbrace \end{align}\]

One can easily verify that \((\xi, \eta) = \left(2/5, 2/5\right)\) is the solution of the above optimization. Therefore, the convergence rate of the objective function can be written as follows.

\[\label{eq95bound95Jr95final95par95substituted} \begin{align} &\frac{1}{K}\sum_{k=1}^{K}\mathbf{E}\bigg(J_r^{\pi^*}-J_r(\theta_k)\bigg)\\ &\leq \sqrt{\epsilon_{\mathrm{bias}}} + G\left(1+\dfrac{1}{\mu_F}\right)\tilde{\mathcal{O}}\left(\dfrac{1}{T^{1/5}}+\dfrac{\sqrt{A}Gt_{\mathrm{mix}}}{\delta T^{1/5}}+\dfrac{\sqrt{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}}{\delta T^{3/10}}\right)+ \mathcal{O}\left(\dfrac{1}{\delta T^2}+\dfrac{1}{T^{2/5}}\right)\\ &+\dfrac{B}{L}\tilde{\mathcal{O}}\left(\dfrac{\delta^2+AG^2t_{\mathrm{mix}}^2}{\delta^2 T^{2/5}}+\dfrac{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}{\delta^2 T^{3/5}}\right) + \mathcal{\tilde{O}}\bigg(\frac{Lt_{\mathrm{mix}}t_{\mathrm{hit}}\mathbf{E}_{s\sim d^{\pi^*}}[KL(\pi^*(\cdot\vert s)\Vert\pi_{\theta_1}(\cdot\vert s))]}{T^{3/5}\delta }\bigg)\\ &\leq \sqrt{\epsilon_{\mathrm{bias}}} + \dfrac{\sqrt{A}G^2t_{\mathrm{mix}}}{\delta}\left(1+\dfrac{1}{\mu_F}\right)\tilde{\mathcal{O}}\left(T^{-1/5}\right) \end{align}\tag{47}\]

The last expression only considers the dominant terms of \(T\). Similarly, the constraint violation rate can be computed as, \[\begin{align} \label{eq958795new} \begin{aligned} &\mathbf{E}\bigg[\frac{1}{K}\sum_{k=1}^{K}-J_c(\theta_k)\bigg] \\ &\leq \delta\sqrt{\epsilon_{\mathrm{bias}}}+ \tilde{\mathcal{O}}\left(\dfrac{t_{\mathrm{mix}}t_{\mathrm{hit}}}{\delta T^{1/5}}+\dfrac{1}{ T^2}+\dfrac{\delta}{T^{2/5}}\right) +G\left(1+\dfrac{1}{\mu_F}\right)\tilde{\mathcal{O}}\left(\dfrac{\delta+\sqrt{A}Gt_{\mathrm{mix}}}{ T^{1/5}}+\dfrac{\sqrt{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}}{ T^{3/10}}\right)\\ &+\dfrac{B}{L}\tilde{\mathcal{O}}\left(\dfrac{\delta^2+ AG^2t_{\mathrm{mix}}^2}{\delta T^{2/5}}+\dfrac{Lt_{\mathrm{mix}}t_{\mathrm{hit}}}{\delta T^{3/5}}\right) + \mathcal{\tilde{O}}\bigg(\frac{Lt_{\mathrm{mix}}t_{\mathrm{hit}}\mathbf{E}_{s\sim d^{\pi^*}}[KL(\pi^*(\cdot\vert s)\Vert\pi_{\theta_1}(\cdot\vert s))]}{T^{3/5}}\bigg)\\ &\leq \delta\sqrt{\epsilon_{\mathrm{bias}}} + \tilde{\mathcal{O}}\left(\dfrac{t_{\mathrm{mix}}t_{\mathrm{hit}}}{\delta T^{1/5}}\right) + \sqrt{A}G^2t_{\mathrm{mix}}\left(1+\dfrac{1}{\mu_F}\right)\tilde{\mathcal{O}}\left(T^{-1/5}\right) \end{aligned} \end{align}\tag{48}\] where the last expression contains only the dominant terms of \(T\). This concludes the theorem.

10 Proofs for the Regret and Violation Analysis↩︎

10.1 Proof of Lemma 8↩︎

10.2 Proof of Theorem 2↩︎

11 Some Auxiliary Lemmas for the Proofs↩︎

Although the strong duality holds for the unparameterized problem, the same is not true for parameterized class \(\{\pi_\theta|\theta\in \Theta\}\). To formalize this statement, define the dual function associated with the parameterized problem as follows. \[J_{D,\Theta}^{\lambda}\triangleq\max_{\theta\in \Theta} J_r(\theta)+\lambda J_c(\theta)\] and denote \(\lambda_\Theta^*=\arg\min_{\lambda\geq 0} J_{D,\Theta}^{\lambda}\). The lack of strong duality states that, in general, \(J_{D, \Theta}^{\lambda_{\Theta}^*}\neq J_r(\theta^*)\) where \(\theta^*\) is a solution of the parameterized constrained optimization 3 . However, the parameter \(\lambda_\Theta^*\), as we demonstrate below, must obey some restrictions.

Since the above inequality holds for arbitrary \(\Theta\), we also have, \(0\leq \lambda^*\leq \frac{1}{\delta}\). Define \(v(\tau)\triangleq\max_{\pi\in\Pi}\{J_r^\pi|J_c^\pi\geq \tau\}\). Using the strong duality property of the unparameterized problem 58 , we establish the following property of the function, \(v(\cdot)\).

We note that a similar result was shown in [38]. However, the setup of the stated paper is different from that of ours. Specifically, [38] considers a tabular setup with peak constraints. Note that Lemma 17 has no direct connection with the parameterized setup since its proof uses strong duality and the function, \(v(\cdot)\), is defined via a constrained optimization over the entire policy set, \(\Pi\), rather than the parameterized policy set. Interestingly, however, the relationship between \(v(\tau)\) and \(v(0)\) leads to the lemma stated below which turns out to be pivotal in establishing regret and constraint violation bounds in the parameterized setup.

References↩︎