Regret Guarantees for Model-Based Reinforcement Learning with Long-Term Average Constraints

Consider a wireless sensor network where the devices aim to update a server with sensor values. At time $t$, the device can choose to send a packet to obtain a reward of $1$ unit or to queue the packet and obtain $0$ reward. However, communicating a packet results in $p_{t}$ power consumption. At time $t$, if the wireless channel condition, $s_{t}$, is weak and the device chooses to send a packet, the resulting instantaneous power consumption, $p_{t}$, is high. The goal is to send as many packets as possible while keep the average power consumption, $\sum_{t=1}^{T}p_{t}/T$, within some limit, say $C$. This environment has state $(s_{t},q_{t})$ as the channel condition and queue length at time $t$. To limit the power consumption, the agent may choose to send packets when the channel condition is good or when the queue length grows beyond a certain threshold. The agent aims to learn the policies in an online manner which requires efficiently balancing exploration of state-space and exploitation of the estimated system dynamics [Singh et al., 2020].

Similar to the example above, many applications require to keep some costs low while simultaneously maximizing the rewards [Altman, 1999]. Owing to the importance of this problem, in this paper, we consider the problem of constrained Markov Decision Processes (CMDP). We aim to develop a reinforcement learning algorithm following which an agent can bound the constraint violations and the regret in obtaining the optimal reward to $o(T)$.

The problem setup, where the system dynamics are known, is extensively studied [Altman, 1999]. For a constrained setup, the optimal policy is possibly stochastic [Altman, 1999, Puterman, 2014]. In the domain where the agent learns the system dynamics and aims to learn good policies online, there has been work where to show asymptotic convergence to optimal policies [Gattami et al., 2021], or even provide regret guarantees when the MDP is episodic [Zheng and Ratliff, 2020, Ding et al., 2021]. Recently, [Singh et al., 2020] considered the problem of online optimization of infinite-horizon communicating Markov Decision Processes with long-term average constraints. They provide an optimism based algorithm where confidence bounds on each transition probabilities $p(s^{\prime}|s,a)$ is constructed. Using this, they obtain a regret bound of $\tilde{O}\left(\sqrt{SAT}+T_{M}T^{2/3}\right)$¹¹1$\tilde{O}(\cdot)$ hides the logarithmic terms. Additionally, finding the optimistic policy is a computationally intensive task as the number of optimization variables become $S^{2}\times A$ for MDP with $S$ states and $A$ actions.

In this paper, we consider the reinforcement learning an infinite-horizon ergodic MDP [Tarbouriech and Lazaric, 2019, Gattami et al., 2021] with long-term average constraints. We use $\ell_{1}$ deviation bounds [Jaksch et al., 2010] and use a Bellman error analysis to bound the reward regret of the MDP as $\tilde{O}(T_{M}S\sqrt{AT})$. Additionally, we also bound the constraint violations as $\tilde{O}(T_{M}S\sqrt{AT})$. We propose a posterior sampling based algorithm where we sample the transition dynamics using a Dirichlet distribution [Osband et al., 2013], which achieves this regret bound.

Unlike optimistic algorithms, the sampled MDP may not be infeasible for the constrained optimization. Hence, we consider slackness characterized by Slater’s parameter Ding et al. [2020], which allows us to prove that the optimization problem is feasible even with the sampled MDPs. Posterior sampling also helps to reduces the optimization variables, to find only the optimal policy for the sampled MDP, to only $S\times A$ variables. Finally, we provide numerical examples where the algorithm converges to the calculated optimal policies. To the best of our knowledge, this is the first work to obtain $O(\sqrt{T})$ regret guarantees for the infinite horizon long-term average constraint setup with posterior sampling.

Stochastic Optimization using Markov Decision Processes has very rich roots [Howard, 1960]. There have been work in understanding convergence of the algorithm to find optimal policies for known MDPs [Bertsekas and Tsitsiklis, 1996, Altman, 1999]. Also, when the MDP is not known, there are algorithms with asymptotic guarantees for learning the optimal policies [Watkins and Dayan, 1992] which maximize an objective without any constraints. Recent algorithms even achieve finite time near-optimal regret bounds with respect to the number of interactions with the environment [Jaksch et al., 2010, Osband et al., 2013, Agrawal and Jia, 2017, Jin et al., 2018]. Jaksch et al. [2010] uses the optimism principle for minimizing regret for weakly communicating infinite horizon MDPs with bounded diameter. Osband et al. [2013] extended the analysis of Jaksch et al. [2010] to posterior sampling for episodic MDPs and bounded the Bayesian regret and further improved the regret bounds Osband and Van Roy [2017]. Agrawal and Jia [2017] uses a posterior sampling based approach and obtains a frequentist regret for the infinite horizon MDPs with bounded diameter.

In many reinforcement learning settings, the agent not only wants to maximize the rewards but also satisfy certain cost constraints [Altman, 1999]. Early works in this area were pioneered by [Altman and Schwartz, 1991]. They provided an algorithm which combined forced explorations and following policies optimized on empirical estimates to obtain an asymptotic convergence. [Borkar, 2005] studied the constrained RL problem using actor-critic and a two time-scale framework [Borkar, 1997] to obtain asymptotic performance guarantees. Very recently, [Gattami et al., 2021] analyzed the asymptotic performance for Lagrangian based algorithms for infinite-horizon long-term average constraints.

Inspired by the finite-time performance analysis of reinforcement learning algorithm for unconstrained problems, there has been a significant thrust in understanding the finite-time performances of constrained MDP algorithms. [Zheng and Ratliff, 2020] considered an episodic CMDP and use an optimism based algorithm to bound the constraint violation as $\tilde{O}(\sqrt{T^{1.5}})$ with high probability. [Kalagarla et al., 2020] also considered the episodic setup to obtain PAC-style bound for an optimism based algorithm. [Ding et al., 2021] considered the setup of $H$-episode length episodic CMDPs with $d$-dimensional linear function approximation to bound the constraint violations as $\tilde{O}(d\sqrt{H^{5}T})$ by mixing the optimal policy with an exploration policy. [Efroni et al., 2020] proposes a linear-programming and primal-dual policy optimization algorithm to bound the regret as $O(S\sqrt{H^{3}T})$. [Qiu et al., 2020] proposed an algorithm which obtains a regret bound of $\tilde{O}(S\sqrt{AH^{2}T})$ for the problem of adversarial stochastic shortest path. Compared to these works, we focus on setting with infinite horizon long-term average constraints.

After developing a better understanding of the policy gradient algorithms [Agarwal et al., 2020], there has been theoretical work in the area of model-free policy gradient algorithms for constrained MDP and safe reinforcement learning as well. [Xu et al., 2020] consider an infinite horizon discounted setup with constraints and obtain global convergence using policy gradient algorithms. [Ding et al., 2020] also considers an infinite horizon discounted setup. They use a natural policy gradient to update the primal variable and sub-gradient descent to update the dual variable.

Recently [Singh et al., 2020] considered the setup of infinite-horizon CMDPs with long-term average constraints and obtain a regret bound of $\tilde{O}(T^{2/3})$ using an optimism based algorithm and forced explorations. We consider a similar setting with ergodic CMDP and propose a posterior sampling based algorithm to bound the regret as $\tilde{O}(poly(DSA)\sqrt{T})$ using explorations assisted by the ergodicity of the MDP.

We consider an infinite horizon discounted Markov decision process (MDP) $\mathcal{M}$, defined by the tuple $\left(\mathcal{S},\mathcal{A},P,r,c_{1},\cdots,c^{k}\right)$. $\mathcal{S}$ denotes a finite set of state space with $|\mathcal{S}|=S$, and $\mathcal{A}$ denotes a finite set of actions with $|\mathcal{A}|=A$. $P:\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S})$ denotes the probability $P(s^{\prime}|s,a)$ of transitioning to state $s^{\prime}$ from state $s$ after taking action $a$. $r:\mathcal{S}\times\mathcal{A}\to[0,1]$ denotes the average reward in state $s$ after taking action $a$. $c^{k}:\mathcal{S}\times\mathcal{A}\to[0,1]$ denotes average cost incurred by the agent for constraint $k\in[K]=\{1,2,\cdots,K\}$ after taking action $a$ in state $s$. We use a stochastic policy $\pi:\mathcal{S}\to\Delta(\mathcal{A})$, such that given state $s$, $\pi(a|s)$ is the probability of selecting action $a$.

Note that the a policy $\pi$ induces a Markov chain over the state space of the MDP. Pertaining to the Markov chains generated by the policies for $\mathcal{M}$, we now define the mixing time of MDP.

Similar to Singh et al. [2020], let $P_{\pi}^{t}(s)$ be the $t$ step state distribution starting from state $s$ following policy $\pi$ and $P_{\pi}$ be the steady-state state distribution generated by policy $\pi$.

Our first assumption on the MDP allows any policy to reach any state $s^{\prime}$ starting from any state $s$, and to converge to a steady state. We formalize the result in the following assumption:

After discussing the transition dynamics of the system, we move to the rewards and costs of the MDP $\mathcal{M}$.

We note that in most of the problems, rewards are engineered. Hence, Assumption 2 is justified in many setups. However, the system dynamics are stochastic and typically not known.

Following a policy $\pi$, the expected long-term average cost are given by $\zeta_{\pi}^{P,k}$. Also, we denote the average long-term reward using $\zeta_{\pi}^{P,k}$. Formally, we have:

For brevity, in the rest of the paper, $\mathbb{E}_{s_{t},a_{t},s_{t+1};t\geq 0}[\cdot]$ will be denoted as $\mathbb{E}_{\rho,\pi,P}[\cdot]$, where $s_{0}\sim\rho_{0}(s_{0}),\ a_{t}\sim\pi(s_{t}|a_{t}),\ s_{t+1}\sim P(s_{t+1}|s_{t},a_{t})$. Both, $\zeta_{\pi}^{P,k}$ and $\lambda_{\pi}^{P,r}$ satisfy the following form of Bellman equation:

where $h_{\pi}^{P,r}(s)$ is the bias for reward and $h_{\pi}^{P,k}$ is the bias for cost $k\in[K]$.

The objective is find a policy $\pi^{*}$ which is the solution of the following optimization problem.

where $C_{k}\leavevmode\nobreak\ \forall\leavevmode\nobreak\ k\in[K]$ are the bounds on the average costs which the agent needs to satisfy.

After formulating the optimization problem, we now state our next assumption characterizing the slackness.

The slackness assumption is mild because, in various applications some a priori knowledge about a strictly feasible policy is available. Hence, this assumption is again a standard assumption in the constrained RL literature Efroni et al. [2020], Ding et al. [2021, 2020]. $\kappa$ is referred as Slater’s constant. Ding et al. [2021] assumes that the Slater’s constant $\kappa$ is known.

Any online algorithm starting with no prior knowledge will require to obtain estimates of transition probabilities $P$ and obtain reward $r$ and costs $c^{k},\forall\ k\in[K]$ for each state action pair. Initially, when algorithm does not have good estimates of the model, it accumulates a regret as well as violates constraints as it does not know the optimal policy. We define reward regret $R(T)$ as the difference between the cumulative reward obtained $r_{t}$ vs the expected rewards from running the optimal policy $\pi^{*}$ for $T$ steps, or

Additionally, we define constraint regret $R_{k}(T)$ for each constraint $k\in[K]$ as the gap between the cumulative cost incurred $c_{t}^{k},k\in[K]$ and constraint bounds, or

where $(x)_{+}=\max(0,x)$.

In the following section, we present a model-based algorithm to obtain this policy $\pi^{*}$, and reward regret and the constraint regret accumulated by the algorithm.

For infinite horizon optimization problems (or $\tau\to\infty$), we can use steady state distribution of the state to obtain expected long-term rewards or costs [Puterman, 2014]. We use

where $d_{\pi}^{P}(s,a)$ is the steady state joint distribution of the state and actions under policy $\pi$.

Based on the above formulation, we can solve the joint optimization problem of following form

with the following set of constraints,

for all $s^{\prime}\in\mathcal{S},\leavevmode\nobreak\ \forall\leavevmode\nobreak\ s\in\mathcal{S},$ and $\forall\leavevmode\nobreak\ a\in\mathcal{A}$. Equation (15) denotes the constraint on the transition structure for the underlying Markov Process. Equation (16) ensures that the solution is a valid probability distribution. Finally, Equation (17) are the constraints for the constrained MDP setup which the policy must satisfy.

Note that arguments in Equation (14) are linear, and the constraints in Equation (15) and Equation (16) are linear, this is a linear programming problem. Since convex optimization problems can be solved in polynomial time [Potra and Wright, 2000], we can use standard approaches to solve Equation (14). After solving the optimization problem, we obtain the optimal policy from the obtained steady state distribution $d^{*}(s,a)$ as,

Since we assumed that the CMDP is ergodic, the Markov Chain induced from policy $\pi$ is ergodic. Hence, every state is reachable following the policy $\pi^{*}$, we have $\mathbb{P}(s)>0$ and Equation (18) is defined for all states $s\in\mathcal{S}$.

Further, since we assumed that the induced Markov Chain is irreducible for all stationary policies, we assume Dirichlet distribution as prior for the state transition probability $P(s^{\prime}|s,a)$. Dirichlet distribution is also used as a standard prior in literature [Agrawal and Jia, 2017, Osband et al., 2013]. Further, there exists a steady state distribution when the transition probability is sampled from a Dirichlet distribution [Agarwal et al., 2022, Proposition 1].

The complete constrained posterior sampling based algorithm, which we name CMDP-PSRL, is described in Algorithm 1. The algorithm proceeds in epochs, and a new epoch is started whenever the visitation count in epoch $e$, $\nu_{e}(s,a)$, is at least the total visitations before episode $e$, $N_{e}(s,a)$, for any state action pair (Line 8). In Line 9, we sample transition probabilities $\tilde{P}$ using the updated posterior and in Line 10, we update the policy using the optimization problem specified in Equation (14)-(17) for $P=\tilde{P}_{e}$. Further, if the sampled MDP does not satisfy the cost constraint in Equation (17), we ignore that constraint ²²2We will show in the analysis that cumulative constraint violations are still bounded. for that epoch.

We first obtain the feasibility of the optimization problem Equation (14)-(17) for the sampled MDP. We note that we assumed slackness in the true MDP with transition probabilities $P$. Hence, if the the sampled MDP is close to the true MDP, the deviation in the cost will be less and there will be a policy which satisfies the constraint in Equation (17). We formalize this intuition in the following result.

After obtaining a feasible policy $\pi_{e}$ maximizing rewards for the sampled MDP, we now quantify is regret. We note that when optimizing for long-term average rewards and long-term average constraints, we want to simultaneously minimize the reward regret and the constraint regrets. Further, if we know the optimal policy $\pi^{*}$ before hand, the deviations resulting from the stochasticity of the process can still result in some constraint violations. Also, since we sample a MDP, the policy which is feasible for the MDP may violate constraints on the true MDP. We want to bound this gap between $K$ costs for the two MDPs as well.

We aim to quantify the regret from (R.1) deviation of long-term average rewards of the optimal policy because of incorrect knowledge of the MDP ($\lambda_{\pi^{*}}^{P,r}-\lambda_{\pi_{e}}^{\tilde{P}_{e},r}$), (R.2) deviation of the long-term average rewards generated by the optimal policy for the sampled MDP on the sampled MDP and the long-term average rewards generated by the optimal policy for the sampled MDP on the true MDP ($\lambda_{\pi_{e}}^{\tilde{P}_{e},r}-\lambda_{\pi_{e}}^{P,r}$), and (R.3) deviation of the expected rewards from following the optimal policy of the sampled MDP ($\lambda_{\pi_{e}}^{P,r}-r(s_{t},a_{t})$).

Similarly, the constraint violations for each $k\in[K]$ are incurred from (C.1) deviation of long-term average rewards of the optimal policy because of incorrect knowledge of the MDP ($C_{k}-\zeta_{\pi_{e}}^{\tilde{P}_{e},k}$), (C.2) deviation of the long-term average costs generated by the optimal policy for the sampled MDP on the sampled MDP and the long-term average costs generated by the optimal policy for the sampled MDP on the true MDP ($\zeta_{\pi_{e}}^{\tilde{P}_{e},r}-\lambda_{\pi_{e}}^{P,r}$), and (C.3) deviation of the expected costs from following the optimal policy of the sampled MDP ($\zeta_{\pi_{e}}^{P,r}-c^{k}(s_{t},a_{t})$).

We now prove the regret bounds for Algorithm 1. We first give the high level ideas used in obtaining the bounds on regret. We divide the regret into regret incurred in each epoch $e$. Then, we use the posterior sampling lemma [Osband et al., 2013, Lemma 1] to obtain the equivalence between the long-term average rewards of the true MDP $\mathcal{M}$ and the long-term average rewards for the optimal value of the sampled MDP $\widehat{\mathcal{M}}$. This step allows us to deal with the regret from (R.1). Then we use the Bellman error formulation to relate average rewards for the policy $\pi_{e}$ on $P$ and $\tilde{P}_{e}$ [Agarwal et al., 2022]. Combining this with Azuma’s concentration inequality for Martingales allows us to bound the regret from (R.2) and (R.3).

Bounding constraint violations requires similar considerations for (C.2) and (C.3). Further, (C.1) becomes zero if Equation (17) is feasible for the sampled MDP. However, if Equation (17) is not feasible, the cost may be as high as $1$ ($c^{k}(s,a)\leq 1\leavevmode\nobreak\ \forall\leavevmode\nobreak\ k\in[K]$). We bound the violations by bounding the time-steps for which the optimal policy for unconstrained optimization runs.

To obtain bounds on the regret, we first note that the total number of epochs, $E$, for which the Algorithm 1 runs is bounded by $O(1+2SA+SA\log(T)$ from [Jaksch et al., 2010, Proposition 1].

We formally state the regret bounds and constraint violation bounds in Theorem 1 which we prove rigorously in the supplementary material.

We note that the fundamental setup of unconstrained optimization ($K=0$), the bound is loose compared to that of UCRL2 algorithm Jaksch et al. [2010]. This is because we use a stochastic policy instead of a deterministic policy. Recall that the optimal policy for CMDP setup is possibly stochastic Altman [1999].

To validate the performance of the proposed CDMP-PSRL algorithm and the understanding of our analysis, we run the simulation on the flow and service control in a single-serve queue, which is introduced in [Altman and Schwartz, 1991]. A discrete-time single-server queue with a buffer of finite size $L$ is considered in this case. The number of the customer waiting in the queue is considered as the state in this problem and thus $|S|=L+1$. Two kinds of the actions, service and flow, are considered in the problem and control the number of customers together. The action space for service is a finite subset $A$ in $[a_{min},a_{max}]$, where $0<a_{min}\leq a_{max}<1$. Given a specific service action $a$, the service a customer is successfully finished with the probability $b$. If the service is successful, the length of the queue will reduce by 1. Similarly, the space for flow is also a finite subsection $B$ in $[b_{min},b_{max}]$. In contrast to the service action, flow action will increase the queue by $1$ with probability $b$ if the specific flow action $b$ is given. Also, we assume that there is no customer arriving when the queue is full. The overall action space is the Cartesian product of the $A$ and $B$. According to the service and flow probability, the transition probability can be computed and is given in the Table 1.

For the reward function as $r(s,a,b)$ and the constraints for service and flow as $c^{1}(s,a,b)$ and $c^{2}(s,a,b)$, respectively, and stationary policies for service and flow as $\pi_{a}$ and $\pi_{b}$, respectively, the problem can be defined as

According to the discussion in [Altman and Schwartz, 1991], we define the reward function as $r(s,a,b)=5-s$, which is an decreasing function only dependent on the state. It is reasonable to give higher reward when the number of customer waiting in the queue is small. For the constraint function, we define $c^{1}(s,a,b)=-10a+6$ and $c^{2}=-8*(1-b)^{2}+2$, which are dependent only on service and flow action, respectively. Higher constraint value is given if the probability for the service and flow are low and high, respectively.

In the simulation, the length of the buffer is set as $L=5$. The service action space is set as $[0.2,0.4,0.6,0.8]$ and the flow action space is set as $[0.4,0.5,0.6,0.7]$. We use the length of horizon $T=50000$ and run $50$ independent simulations of the proposed CMDP-PSRL algorithm. We also plot the standard deviation around the mean value in the shadow to show the random error. In order to compare this result to the optimal, we assume that the full information of the transition dynamics is known and then use Linear Programming to solve the problem. The optimal cumulative reward from LP is shown to be $4.47$. The reward performance of the CMDP-PSRL algorithm is shown in the Figure 1 where we observe that the reward converges towards the optimal value. We also plot the constraint violations in Figure 2. The service and flow constraints converge to 0 as expected. We note that the reward of the proposed CMDP-PSRL algorithm becomes closer the optimal reward as the algorithm proceeds, and to further increase the reward, it does not violates the constraint.

We also compared our algorithm against the optimistic algorithm of Singh et al. [2020]. We note that their algorithm performs significantly worse compared to our algorithm. We account this poor performance on two accounts. An optimistic algorithm does not find a policy for transition probabilities close to $P$ for significantly large time. The other issue is because they consider confidence interval for each $P(s^{\prime}|s,a)$. This also shows in their analysis and hence they obtain a $O(T^{2/3})$ regret bound. Further, the optimization problem takes a significantly more time to solve for optimistic setup. However, the variance of their optimistic algorithm is significantly lower compared to the variance of our CMDP-PSRL algorithm.

This paper, considers the setup of reinforcement learning in ergodic infinite-horizon constrained Markov Decision Processes with $K$ long-term average constraint. We propose a posterior sampling based algorithm, CMDP-PSRL, which proceeds in epochs. At every epoch, we sample a new CMDP and generate a solution for the constraint optimization problem. A major advantage of the posterior sampling based algorithm over an optimistic approach is, that it reduces the complexity of solving for the optimal solution of the constraint problem. We also study the proposed CMDP-PSRL algorithm from regret perspective. We bound the regret of the reward collected by the CMDP-PSRL algorithm as $\tilde{O}(T_{M}S\sqrt{AT}+CS^{2}A/(1-\rho))$. Further, we bound the gap between the long-term average costs of the sampled MDP and the true MDP to bound the $K$ constraint violations as $\tilde{O}(T_{M}S\sqrt{AT}+CS^{2}A/(1-\rho))$. Finally, we evaluate the proposed CMDP-PSRL algorithm on a flow control problem for single queue and show that the proposed algorithm performs empirically well. This paper is the first work which obtains a $\tilde{O}(\sqrt{T})$ regret bounds for ergodic MDPs with long-term average constraints using a posterior sampling algorithm. A model-free algorithm that obtains similar regret bounds for infinite horizon long-term average constraints remains an open problem.