Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss

Constrained Markov decision processes play an important role in control and planning. It aims at maximizing a reward or minimizing a penalty metric over the set of all available policies subject to constraints on other relevant metrics. The constraints aim at enforcing the fairness or safety of the policies so that over time the behaviors of the chosen policy are under control. For example, in an edge cloud serving network (Urgaonkar et al., 2015; Wang et al., 2015), one would like to minimize the average cost of serving the moving targets subject to a constraint on the average serving delay. In an autonomous vehicle control problem (Le et al., 2019), one might be interested in minimizing the driving time subject to certain fuel efficiency or driving safety constraints.

Classical treatment of CMDPs dates back to Fox (1966); Altman (1999) reformulating the problem into a linear program (LP) via stationary state-action occupancy measures. However, to formulate such an LP, one requires the full knowledge of the transition model, reward, and constraint functions, and also assumes them to be fixed. Leveraging the episodic structure of a class of MDPs, Neely (2012) develops online renewal optimization which potentially allows the loss and constraint functions to be stochastically varying and unknown, while still relying on the transition model to solve the subproblem within the episode.

More recently, policy-search type algorithms have received much attention, attaining state-of-art performance in various tasks without knowledge of the transition model, e.g. Williams (1992); Baxter and Bartlett (2000); Konda and Tsitsiklis (2000); Kakade (2002); Schulman et al. (2015); Lillicrap et al. (2015); Schulman et al. (2017); Sutton and Barto (2018); Fazel et al. (2018); Abbasi-Yadkori et al. (2019a, b); Bhandari and Russo (2019); Cai et al. (2019); Wang et al. (2019); Liu et al. (2019); Agarwal et al. (2019). While most of the algorithms focus on unconstrained reinforcement learning problems, there are efforts to develop policy-based methods in CMDPs where constraints are known with limited theoretical guarantees. The work Chow et al. (2017) develops a primal-dual type algorithm which is shown to converge to some constraint satisfying policy. Achiam et al. (2017) develops a trust-region type algorithm which requires solving an optimization problem with both trust-region and safety constraints during each update. Generalizing ideas from the fitted-Q iteration, Le et al. (2019) develops a batch offline primal-dual type algorithm which guarantees only the time average primal-dual gap converges.

The goal of this paper is to solve constrained episodic MDPs with more generality where not only transition models are unknown, but also the loss and constraint functions can change online. In particular, the losses can be arbitrarily time-varying and adversarial. Let $T$ be the number of episodes¹¹1In the non-episodic (infinite-horizon) setting, $T$ denotes the total number of steps, which is a little different from the aforementioned $T$ for the episodic setting.. When assuming the transition model is known, Even-Dar et al. (2009) achieves $\widetilde{\mathcal{O}}(\varrho^{2}\sqrt{T\log|\mathcal{A}|})$ regret with $\varrho$ being the mixing time of the MDPs, and the work Yu et al. (2009) achieves $\widetilde{\mathcal{O}}(T^{2/3})$ regret. These two papers consider a continuous setting that is a little different to the episodic setting that we consider in this paper. Zimin and Neu (2013) further studies the episodic MDP and achieves $\widetilde{\mathcal{O}}(L\sqrt{T\log(|\mathcal{S}||\mathcal{A}|)})$ regret. For the constrained case with known transitions, the work Wei et al. (2018) achieves an $\widetilde{\mathcal{O}}(\text{poly}(|\mathcal{S}||\mathcal{A}|)\sqrt{T})$ regret and constraint violations, and Zheng and Ratliff (2020) attains $\widetilde{\mathcal{O}}(|\mathcal{S}||\mathcal{A}|T^{3/4})$ for the non-episodic setting.

After we finished the first version of this work, there are several concurrent works appearing which also focus on CMDPs with unknown transitions and losses. The work Efroni et al. (2020a) studies episodic tabular MDPs with unknown but fixed loss and constraint functions, where the feedbacks are stochastic bandits. Leveraging upper confidence bound (UCB) on the reward, constraints, and transitions, they obtain an $\mathcal{O}(\sqrt{T})$ regret and constraint violation via linear program as well as primal-dual optimization. In another work, Ding et al. (2020) studies the constrained episodic MDPs with a linear structure and adversarial losses via a primal-dual-type policy optimization algorithm, achieving $\widetilde{\mathcal{O}}(\sqrt{T})$ regret and constraint violation. While the scenario in Ding et al. (2020) is more general than ours, their dependence on the length of episode is worse when applied to the tabular case. Both of these two works rely on Slater condition which is also more restrictive than that of this work.

On the other hand, for unconstrained online MDPs, the idea of UCB has shown to be effective and helps to achieve tight regret bounds without knowing the transition model, e.g. Jaksch et al. (2010); Azar et al. (2017); Rosenberg and Mansour (2019a, b); Jin et al. (2019). The main idea there is to sequentially refine a confidence set of the transition model and choose a model in the interval which performs the best in optimizing the current value.

The main contribution of this paper is to show that UCB is also effective when incorporating with primal-dual type approaches to achieve $\widetilde{\mathcal{O}}(L|\mathcal{S}|\sqrt{|\mathcal{A}|T})$ regret and constraint violation simultaneously in online CMDPs when the transition model is unknown, the loss is adversarial, and the constraints are stochastic. This almost matches the lower bound $\Omega(\sqrt{L|\mathcal{S}||\mathcal{A}|T})$ for the regret Jaksch et al. (2010) up to an $\widetilde{\mathcal{O}}(\sqrt{L|\mathcal{S}|})$ factor. Under the hood is a new Lagrange multiplier condition together with a new drift analysis on the Lagrange multipliers leading to low constraint violation. Our setup is challenging compared to classical constrained optimization in particular due to (1) the unknown loss and constraint functions from the online setup; (2) the time-varying decision sets resulting from moving confidence set estimation of UCB. The decision sets can potentially be much larger than or even inconsistent with the true decision set knowing the model, resulting in a potentially large constraint violation. The main idea is to utilize a Lagrange multiplier condition as well as a confidence set of the model to construct a probabilistic bound on an online dual multiplier. We then explicitly take into account the laziness nature of the confidence set estimation in our algorithm to argue that the bound on the dual multiplier gives the $\widetilde{\mathcal{O}}(\sqrt{T})$ bound on constraint violation.

In this paper, we are more interested in a class of online MDP problems where the loss functions are arbitrarily changing, or adversarial. With a known transition model, adversarial losses, and full-information feedbacks (as opposed to bandit feedbacks), Even-Dar et al. (2009) achieves $\widetilde{\mathcal{O}}(\varrho^{2}\sqrt{T\log|\mathcal{A}|})$ regret with $\varrho$ being the mixing time of the MDP, and the work Yu et al. (2009) achieves $\widetilde{\mathcal{O}}(T^{2/3})$ regret. These two papers consider a non-episodic setting that is different to the episodic setting that we consider in this paper. The work Zimin and Neu (2013) further studies the episodic MDP and achieves an $\widetilde{\mathcal{O}}(L\sqrt{T\log(|\mathcal{S}||\mathcal{A}|)})$ regret.

A more challenging setting is that the transition model is unknown. Under such setting, there are several works studying the online episodic MDP problems with adversarial losses and full-information feedbacks. Neu et al. (2012) obtains $\widetilde{\mathcal{O}}(L|\mathcal{S}||\mathcal{A}|\sqrt{T})$ regret by proposing a Follow the Perturbed Optimistic Policy (FPOP) algorithm. The recent work Rosenberg and Mansour (2019a) improves the regret to $\widetilde{\mathcal{O}}(L|\mathcal{S}|\sqrt{|\mathcal{A}|T})$ by proposing an online upper confidence mirror descent algorithm. This regret bound nearly matches the lower bound $\Omega(\sqrt{L|\mathcal{S}||\mathcal{A}|T})$ (Jaksch et al., 2010) up to $\mathcal{O}(\sqrt{L|\mathcal{S}|})$ and some logarithm factors. Our work is along this line of research, and further considers the setup that there exist stochastic constraints observed at each episode during the learning process.

Besides, a number of papers also investigate online episodic MDPs with bandit feedbacks. Assuming the transition model is known and the losses are adversarial, Neu et al. (2010) achieves $\widetilde{\mathcal{O}}(L^{2}\sqrt{T|\mathcal{A}|}/\beta)$ regret, where $\beta$ is the probability that all states are reachable under all policies. Under the same setting, Neu et al. (2010) achieves $\widetilde{\mathcal{O}}(T^{2/3})$ regret without the dependence on $\beta$, and Zimin and Neu (2013) obtains $\widetilde{\mathcal{O}}(\sqrt{L|\mathcal{S}||\mathcal{A}|T})$ regret. Furthermore, with assuming the transition model is not known and the losses are adversarial, Rosenberg and Mansour (2019b) obtains $\widetilde{\mathcal{O}}(T^{3/4})$ regret and also $\widetilde{\mathcal{O}}(\sqrt{T}/\beta)$ where all states are reachable with probability $\beta$ under any policy. Jin et al. (2019) further achieves $\widetilde{\mathcal{O}}(L|\mathcal{S}|\sqrt{|\mathcal{A}|T})$ regret under the same setting of the unknown transition model and adversarial losses. We remark that our algorithm can be extended to the setting of constrained episodic MDP where both the loss and constraint functions are time-varying and we only receive bandit feedbacks. We leave such an extension as our future work.

On the other hand, instead of adversarial losses, extensive works have studied the setting where the feedbacks of the losses are stochastic and have fixed expectations, e.g. Jaksch et al. (2010); Azar et al. (2017); Ouyang et al. (2017); Jin et al. (2018); Fruit et al. (2018); Wei et al. (2019a); Zhang and Ji (2019); Dong et al. (2019). With assuming that the transition model is known, Zheng and Ratliff (2020) studies online CMDPs under the non-episodic setting and attains an $\widetilde{\mathcal{O}}(|\mathcal{S}||\mathcal{A}|T^{3/4})$ regret which is suboptimal in terms of $T$. The concurrent work Efroni et al. (2020a) studies episodic MDPs with unknown transitions and stochastic bandit feedbacks of the losses and the constraints, and obtains an $\widetilde{\mathcal{O}}(\sqrt{T})$ regret and constraint violation.

In addition to the aforementioned papers, there is also a line of policy-search type works, focusing on solving online MDP problems via directly optimizing policies without knowing the transition model, e.g., Williams (1992); Baxter and Bartlett (2000); Konda and Tsitsiklis (2000); Kakade (2002); Schulman et al. (2015); Lillicrap et al. (2015); Schulman et al. (2017); Sutton and Barto (2018); Fazel et al. (2018); Abbasi-Yadkori et al. (2019a, b); Bhandari and Russo (2019); Cai et al. (2019); Wang et al. (2019); Liu et al. (2019); Agarwal et al. (2019); Efroni et al. (2020b). Efforts have also been made in several works (Chow et al., 2017; Achiam et al., 2017; Le et al., 2019) to investigate CMDP problems via policy-based methods, but with known transition models. In another concurrent work, assuming the transition model is unknown, Ding et al. (2020) studies the episodic CMDPs with linear structures and proposes a primal-dual type policy optimization algorithm.

Consider an episodic loop-free MDP with a finite state space $S$ and a finite action space $\mathcal{A}$ at each state over a finite horizon of $T$ episodes. Each episode starts with a fixed initial state $s_{0}$ and ends with a terminal state $s_{L}$. The transition probability is $P:\mathcal{S}\times\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$, where $P(s^{\prime}|s,a)$ gives the probability of transition from $s$ to $s^{\prime}$ under an action $a$. This underlying transition model $P$ is assumed to be unknown. The state space is loop-free, i.e., it is divided into layers, i.e., $\mathcal{S}:=\mathcal{S}_{0}\cup\mathcal{S}_{1}\cup\cdots\cup\mathcal{S}_{L}$ with a singleton initial layer $\mathcal{S}_{0}=\{s_{0}\}$ and terminal layer $S_{L}=\{s_{L}\}$. Furthermore, $\mathcal{S}_{k}\cap\mathcal{S}_{\ell}=\varnothing,~{}k\neq\ell$ and transitions are only allowed between consecutive layers, which is $P(s^{\prime}|s,a)>0$ only if $s^{\prime}\in\mathcal{S}_{k+1}$, $s\in\mathcal{S}_{k}$, and $a\in\mathcal{A}$, $\forall k\in\{0,1,2,\cdots,L-1\}$. Note that such an assumption enforces that each path from the initial state to the terminal state takes a fixed length $L$. This is not an excessively restrictive assumption as any loop-free MDP with bounded varying path lengths can be transformed into one with a fixed path length (see György et al. (2007) for details).

The loss function for each episode is $f^{t}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow\mathbb{R}$, where $f^{t}(s,a,s^{\prime})$ denotes the loss received at episode $t$ for any $s\in\mathcal{S}_{k},~{}s^{\prime}\in\mathcal{S}_{k+1}$ and $a\in\mathcal{A}$, $\forall k\in\{0,1,2,\ldots,L-1\}$. We assume $f_{t}$ can be arbitrarily varying with potentially no fixed probability distribution. There are $I$ stochastic constraint (or budget consumption) functions: $g_{i}^{t}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow\mathbb{R},~{}\forall i\in\{1,2,\ldots,I\}$, where $g_{i}^{t}(s,a,s^{\prime})$ denotes the price to pay at episode $t$ for any $(s,a,s^{\prime})$. Each stochastic function $g_{i}^{t}$ at episode $t$ is sampled according to a random variable $\xi_{i}^{t}\sim\mathcal{D}_{i}$, namely $g_{i}^{t}(s,a,s^{\prime})=g_{i}(s,a,s^{\prime};\xi_{i}^{t})$. Then, we define $g_{i}(s,a,s^{\prime}):=\mathbb{E}[g_{i}^{t}(s,a,s^{\prime})]=\mathbb{E}_{\xi_{i}^{t}}[g_{i}(s,a,s^{\prime};\xi_{i}^{t})]$ where the expectation is taken over the randomness of $\xi_{i}^{t}\sim\mathcal{D}_{i}$. For abbreviation, we denote $g_{i}=\mathbb{E}[g_{i}^{t}]$. In addition, the functions $f^{t}$ and $g_{i}^{t},~{}\forall i\in\{1,\ldots,I\}$, are mutually independent and independent of the Markov transitions. Both the loss functions and the budget consumption functions are revealed at the end of each episode.

For any episode $t$, a policy $\pi_{t}$ is the conditional probability $\pi_{t}(a|s)$ of choosing an action $a\in\mathcal{A}$ at any given state $s\in\mathcal{S}$. Let $(s_{k},a_{k},s_{k+1})\in\mathcal{S}_{k}\times\mathcal{A}\times\mathcal{S}_{k+1}$ denotes a random tuple generated according to the transition model $P$ and the policy $\pi_{t}$. The corresponding expected loss is $\sum_{k=0}^{L-1}\mathbb{E}{\left[f^{t}(s_{k},a_{k},s_{k+1})|\pi_{t},P\right]}$, while the budget costs are $\sum_{k=0}^{L-1}\mathbb{E}{\left[g_{i}^{t}(s_{k},a_{k},s_{k+1})|\pi_{t},P\right]},i\in\{1,\cdots,I\}$, where the expectations are taken w.r.t. the randomness of the tuples $(s_{k},a_{k},s_{k+1})$.

In this paper, we adopt the occupancy measure $\theta(s,a,s^{\prime})$ for our analysis. In general, the occupancy measure $\theta(s,a,s^{\prime})$ is a joint distribution of the tuple $(s,a,s^{\prime})\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}$ under some certain policy and transition model. Particularly, under the true transition $P$, we define the set $\Delta:=\{\theta~{}:~{}\theta\text{ satisfies \ref{item:cond1}, \ref{item:cond2}, and \ref{item:cond3}}\}$ (Altman, 1999) where

1. (a)

   $\sum_{s\in\mathcal{S}_{k}}\sum_{a\in\mathcal{A}}\sum_{s^{\prime}\in\mathcal{S}_{k+1}}\theta(s,a,s^{\prime})=1,\forall k\in\{0,\ldots,L-1\},\text{ and }~{}\theta(s,a,s^{\prime})\geq 0$.

2. (b)

   $\sum_{s\in\mathcal{S}_{k}}\sum_{a\in\mathcal{A}}\theta(s,a,s^{\prime})=\sum_{a\in\mathcal{A}}\sum_{s^{\prime\prime}\in\mathcal{S}_{k+2}}\theta(s^{\prime},a,s^{\prime\prime}),\forall k\in\{0,\ldots,L-2\},~{}s^{\prime}\in\mathcal{S}_{k+1}$.

3. (c)

   $\theta(s,a,s^{\prime})/\sum_{s^{\prime\prime}\in\mathcal{S}_{k+1}}\theta(s,a,s^{\prime\prime})=P(s^{\prime}|s,a),\forall k\in\{0,\ldots,L-1\},s\in\mathcal{S}_{k},a\in\mathcal{A},s^{\prime}\in\mathcal{S}_{k+1}$.

We can further recover a policy $\pi$ from $\theta$ via $\pi(a|s)=\sum_{s^{\prime}\in\mathcal{S}_{k+1}}\theta(s,a,s^{\prime})/\sum_{s^{\prime}\in\mathcal{S}_{k+1},a\in\mathcal{A}}\theta(s,a,s^{\prime})$.

We define $\overline{\theta}^{t}(s,a,s^{\prime})$, $s\in\mathcal{S},~{}s^{\prime}\in\mathcal{S},~{}a\in\mathcal{A}$, to be the occupancy measure at episode $t$ w.r.t. the true transition $P$, resulting from a policy $\pi_{t}$ at episode $t$. Given the definition of occupancy measure, we can rewrite the expected loss and the budget cost as $\sum_{k=0}^{L-1}\mathbb{E}{\left[f^{t}(s_{k},a_{k},s_{k+1})|\pi_{t},P\right]}=\langle f^{t},\overline{\theta}^{t}\rangle$ where $\langle f^{t},\overline{\theta}^{t}\rangle=\sum_{s,a,s^{\prime}}f^{t}(s,a,s^{\prime})\overline{\theta}^{t}(s,a,s^{\prime})$ and $\sum_{k=0}^{L-1}\mathbb{E}{\left[g_{i}^{t}(s_{k},a_{k},s_{k+1})|\pi_{t},P\right]}=\langle g_{i}^{t},\overline{\theta}^{t}\rangle$ with $\langle g_{i}^{t},\overline{\theta}^{t}\rangle=\sum_{s,a,s^{\prime}}f^{t}(s,a,s^{\prime})\overline{\theta}^{t}(s,a,s^{\prime})$. We aim to solve the following constrained optimization, and let $\overline{\theta}^{*}$ be one solution which is further viewed as a reference point to define the regret:

where $\sum_{t=1}^{T}\langle f^{t},\theta\rangle=\sum_{t=1}^{T}\mathbb{E}[\sum_{k=0}^{L-1}f^{t}(s_{k},a_{k},s_{k+1})|\pi,P]$ is the overall loss in $T$ episodes and constraints are enforced on the budget cost $\langle g_{i},\theta\rangle=\mathbb{E}[\sum_{k=0}^{L-1}g_{i}(s_{k},a_{k},s_{k+1})|\pi,P]$ based on the expected budget consumption functions $g_{i},\forall i\in[I]$. To measure the regret and the constraint violation respectively for solving (1) in an online setting, we define the following two metrics:

where the notation $[\mathbf{v}]_{+}$ denotes the entry-wise application of $\max\{\cdot,0\}$ for any vector $\mathbf{v}$. For abbreviation, let $\mathbf{g}^{t}(\theta):=[\langle{g_{1}^{t}},{\theta}\rangle,~{}\cdots,~{}\langle{g_{I}^{t}},{\theta}\rangle]^{\top}$, and $\mathbf{c}:=\left[c_{1},~{}\cdots,~{}c_{I}\right]^{\top}$.

The goal is to attain a sublinear regret bound and constraint violation on this problem w.r.t. any fixed stationary policy $\pi$, which does not change over episodes. In another word, we compare to the best policy $\pi^{*}$ in hindsight whose corresponding occupancy measure $\overline{\theta}^{*}\in\Delta$ solves problem (1). We make the following assumption on the existence of a solution to (1).

Then, we assume the following boundedness on function values for simplicity of notations without loss of generality.

When the transition model $P$ is known and Slater’s condition holds (i.e., existence of a policy which satisfies all stochastic inequality constraints with a constant $\varepsilon$-slackness), this stochastically constrained online linear program can be solved via similar methods as Wei et al. (2018); Yu et al. (2017) with a regret bound that depends polynomially on the cardinalities of state and action spaces, which is highly suboptimal especially when the state or action space is large. The main challenge we will address in this paper is to solve this problem without knowing the model $P$, or losses and constraints before making decisions, while tightening the dependency on both state and action spaces in the resulting performance bound.

In this section, we introduce our proposed algorithm, namely, the upper confidence primal-dual (UCPD) algorithm, as presented in Algorithm 1. It adopts a primal-dual mirror descent type algorithm solving constrained problems but with an important difference: We maintain a confidence set via past sample trajectories, which contains the true MDP model $P$ with high probability, and choose the policy to minimize the proximal Lagrangian using the most optimistic model from the confidence set. Such an idea, known as optimism in the face of uncertainty, is reminiscent of the upper confidence bound (UCB) algorithm (Auer et al., 2002) for stochastic multi-armed bandit (MAB) and first proposed by Jaksch et al. (2010) to obtain a near-optimal regret for reinforcement learning problems.

In the algorithm, we introduce epochs, which are back-to-back time intervals that span several episodes. We use $\ell\in\{1,2,\cdots\}$ to index the epochs and use $\ell(t)$ to denote a mapping from episode index $t$ to epoch index, indicating which epoch the $t$-th episode lives in. Next, let $N_{\ell}(s,a)$ and $M_{\ell}(s,a,s^{\prime})$ be two global counters which indicate the number of times the tuples $(s,a)$ and $(s,a,s^{\prime})$ appear before the $\ell$-th epoch. Let $n_{\ell}(s,a)$, $m_{\ell}(s,a,s^{\prime})$ be two local counters which indicate the number of times the tuples $(s,a)$ and $(s,a,s^{\prime})$ appear in the $\ell$-th epoch. We start a new epoch whenever there exists $(s,a)$ such that $n_{\ell(t)}(s,a)\geq N_{\ell(t)}(s,a)$. Otherwise, set $\ell(t+1)=\ell(t)$. Such an update rule follows from Jaksch et al. (2010). Then, we define the empirical transition model $\widehat{P}_{\ell}$ at any epoch $\ell>0$ as

As shown in Remark 6.8, introducing the notion of ‘epoch’ is necessary to achieve an $\widetilde{\mathcal{O}}(\sqrt{T})$ constraint violation.

The next lemma shows that with high probability, the true transition model $P$ is contained in a confidence interval around the empirical one no matter what sequence of policies taken, which is adapted from Lemma 1 of Neu et al. (2012).

Before presenting our results, we first make assumption on the existence of Lagrange multipliers. We define a partial average function starting from any time slot $t$ as $f^{(t,\tau)}:=\frac{1}{\tau}\sum_{j=0}^{\tau-1}f^{t+j}$. Then, we consider the following static optimization problem (recalling $g_{i}:=\mathbb{E}[g_{i}^{t}]$)

Denote the solution to this program as $\theta^{*}_{t,\tau}$. Define the Lagrangian dual function of (10) as $q^{(t,\tau)}(\eta):=\min_{\theta\in\Delta}~{}f^{(t,\tau)}(\theta)+\sum_{i=1}^{I}\eta_{i}(g_{i}(\theta)-c_{i})$, where $\eta=[\eta_{1},\ldots,\eta_{I}]^{\top}\in\mathbb{R}^{I}$ is a dual variable. We are ready to state our assumption:

As is discussed in Section B of the supplementary material, Assumption 5.1 proposes a weaker condition than the Slater condition commonly adopted in previous constrained online learning works. The following lemma further shows the relation between Assumption 5.1 and the dual function.

Based on the above assumptions and lemmas, we present results of the regret and constraint violation.

In this section, we provide lemmas and proof sketches for the regret bound and constraint violation bound in Theorem 5.3. The detailed proofs for Section 6.1 and Section 6.2 are in Section C and Section D of the supplementary material respectively.