summaries: The authors propose a DICE-family method for solving constrained offline reinforcement learning problems. To do this, they adapt ideas from OptiDICE and find a reduction from a nested constrained optimization problem to a single unconstrained optimization problem that can be efficiently represented with a neural network. Additionally, they draw on ideas from CoinDICE to estimate a confidence interval over the cost, which makes their method better at obeying constraints. The  authors compare their method to a number of baselines on both random grid worlds and continuous environments, and find that COptiDICE achieves both good performance and better constraint satisfaction than alternative methods.  The paper considers the offline constrained reinforcement learning problem and formulates the problem as a CMDP. First, the paper presents the algorithm COptiDICE, which directly estimates the stationary distribution corrections of the optimal policy. Then, the paper shows that COptiDICE outperforms the baseline algorithms in terms of constraint satisfaction and return-maximization.  This paper studied the policy optimization problem in the offline constrained MDP setting. Compare with previous works, in which policy gradient based approaches are widely adopted, this paper solves the problem via policy visitation distribution that rooted from the primal-dual formulation of Bellman operator, which is novel. In order to guarantee the constraints are always satisfied, this paper provides a novel approach based on CoinDICE to efficiently estimate an upper bound of constraint violation. The author also provide sufficient empirical verifications to support their proposed algorithm. This paper has presented a DICE-based offline constrained RL algorithm for constrained RL. Experimental results on tabular CMDPs and continuous control tasks show that the proposed method can achieve a better trade-off between reward maximization and constraint satisfaction.  1st contribution: They firstly proposed to tackle constrained offline RL by solving a single minimization problem.   2nd contribution: To mitigate constraint violation in practice, they exploit the distribution correction obtained by solving the RL problem for cost upper bound estimation and then constrain the upper bound. 
abstractText: We consider the offline constrained reinforcement learning (RL) problem, in which the agent aims to compute a policy that maximizes expected return while satisfying given cost constraints, learning only from a pre-collected dataset. This problem setting is appealing in many real-world scenarios, where direct interaction with the environment is costly or risky, and where the resulting policy should comply with safety constraints. However, it is challenging to compute a policy that guarantees satisfying the cost constraints in the offline RL setting, since the offpolicy evaluation inherently has an estimation error. In this paper, we present an offline constrained RL algorithm that optimizes the policy in the space of the stationary distribution. Our algorithm, COptiDICE, directly estimates the stationary distribution corrections of the optimal policy with respect to returns, while constraining the cost upper bound, with the goal of yielding a cost-conservative policy for actual constraint satisfaction. Experimental results show that COptiDICE attains better policies in terms of constraint satisfaction and return-maximization, outperforming baseline algorithms.
references.authors: Abbas Abdolmaleki Jost Tobias Springenberg Yuval Tassa Remi Munos Nicolas Heess Martin Riedmiller
references.title: Maximum a posteriori policy optimisation
references.venue: In International Conference on Learning Representations (ICLR),
references.authors: Joshua Achiam David Held Aviv Tamar Pieter Abbeel
references.title: Constrained policy optimization
references.venue: In Proceedings of the 34th International Conference on Machine Learning,
references.authors: Eitan Altman
references.title: Constrained Markov Decision Processes
references.authors: Christopher M. Bishop
references.title: Mixture density networks
references.venue: Technical report,
references.authors: V.S. Borkar
references.title: An actor-critic algorithm for constrained markov decision processes
references.venue: Systems & Control Letters,
references.authors: Yinlam Chow Aviv Tamar Shie Mannor Marco Pavone
references.title: Risk-sensitive and robust decisionmaking: a cvar optimization approach
references.venue: Advances in Neural Information Processing Systems,
references.authors: Bo Dai Ofir Nachum Yinlam Chow Lihong Li Csaba Szepesvari Dale Schuurmans
references.title: CoinDICE: Off-policy confidence interval estimation
references.venue: In Advances in Neural Information Processing Systems (NeurIPS),
references.authors: Gabriel Dulac-Arnold Nir Levine Daniel J. Mankowitz Jerry Li Cosmin Paduraru Sven Gowal Todd Hester
references.title: An empirical investigation of the challenges of real-world reinforcement
references.authors: Bradley Efron Robert J. Tibshirani
references.title: An Introduction to the Bootstrap. Number 57 in Monographs on Statistics and Applied Probability
references.authors: Scott Fujimoto David Meger Doina Precup
references.title: Off-policy deep reinforcement learning without exploration
references.venue: In Proceedings of the 36th International Conference on Machine Learning (ICML),
references.authors: Ishaan Gulrajani Faruk Ahmed Martin Arjovsky Vincent Dumoulin Aaron C Courville
references.title: Improved training of Wasserstein GANs
references.venue: Advances in Neural Information Processing Systems (NeurIPS),
references.authors: Tuomas Haarnoja Aurick Zhou Pieter Abbeel Sergey Levine
references.title: Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor
references.venue: In Proceedings of the 35th International Conference on Machine Learning (ICML),
references.authors: Josiah P. Hanna Peter Stone Scott Niekum
references.title: Bootstrapping with models: Confidence intervals for off-policy evaluation
references.venue: In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems,
references.authors: Matt Hoffman Bobak Shahriari John Aslanides Gabriel Barth-Maron Feryal Behbahani Tamara Norman Abbas Abdolmaleki Albin Cassirer Fan Yang Kate Baumli Sarah Henderson Alex Novikov Sergio Gómez Colmenarejo Serkan Cabi Caglar Gulcehre Tom Le Paine Andrew Cowie Ziyu Wang Bilal Piot Nando de Freitas
references.title: Acme: A research framework for distributed reinforcement learning
references.venue: arXiv preprint arXiv:2006.00979,
references.authors: Garud N. Iyengar
references.title: Robust dynamic programming
references.venue: Mathematics of Operations Research,
references.authors: Natasha Jaques Asma Ghandeharioun Judy Hanwen Shen Craig Ferguson Agata Lapedriza Noah Jones Shixiang Gu Rosalind Picard
references.title: Way off-policy batch deep reinforcement learning of implicit human preferences in dialog, 2019
references.authors: Rahul Kidambi Aravind Rajeswaran Praneeth Netrapalli Thorsten Joachims
references.title: MOReL : Modelbased offline reinforcement learning
references.venue: In Advances in Neural Information Processing Systems (NeurIPS),
references.authors: Ilya Kostrikov Ofir Nachum Jonathan Tompson
references.title: Imitation learning via off-policy distribution matching
references.venue: In Proceedings of the 7th International Conference on Learning Representations (ICLR),
references.authors: Ilya Kostrikov Rob Fergus Jonathan Tompson Ofir Nachum
references.title: Offline reinforcement learning with fisher divergence critic regularization
references.venue: Proceedings of the 38th International Conference on Machine Learning,
references.authors: Aviral Kumar Justin Fu Matthew Soh George Tucker Sergey Levine
references.title: Stabilizing off-policy Qlearning via bootstrapping error reduction
references.venue: In Advances in Neural Information Processing Systems (NeurIPS),
references.authors: Aviral Kumar Aurick Zhou George Tucker Sergey Levine
references.title: Conservative Q-learning for offline reinforcement learning
references.venue: In Advances in Neural Information Processing Systems (NeurIPS),
references.authors: Sascha Lange Thomas Gabel Martin Riedmiller
references.title: Reinforcement learning: State-of-the-art
references.authors: Romain Laroche Paul Trichelair Remi Tachet Des Combes
references.title: Safe policy improvement with baseline bootstrapping
references.venue: In Proceedings of the 36th International Conference on Machine Learning (ICML),
references.authors: Hoang Le Cameron Voloshin Yisong Yue
references.title: Batch policy learning under constraints
references.venue: In Proceedings of the 36th International Conference on Machine Learning,
references.authors: Byungjun Lee Jongmin Lee Peter Vrancx Dongho Kim Kee-Eung Kim
references.title: Batch reinforcement learning with hyperparameter gradients
references.venue: Proceedings of the 37th International Conference on Machine Learning,
references.authors: Jongmin Lee Wonseok Jeon Byungjun Lee Joelle Pineau Kee-Eung Kim
references.title: OptiDICE: Offline policy optimization via stationary distribution correction estimation
references.venue: In Proceedings of the 38th International Conference on Machine Learning,
references.authors: Sergey Levine Aviral Kumar George Tucker Justin Fu
references.title: Offline reinforcement learning: Tutorial, review, and perspectives on open problems, 2020
references.authors: Timothy P. Lillicrap Jonathan J. Hunt Alexander Pritzel Nicolas Heess Tom Erez Yuval Tassa David Silver Daan Wierstra
references.title: Continuous control with deep reinforcement learning
references.venue: In 4th International Conference on Learning Representations,
references.authors: Daniel J. Mankowitz Dan A. Calian Rae Jeong Cosmin Paduraru Nicolas Heess Sumanth Dathathri Martin Riedmiller Timothy Mann
references.title: Robust constrained reinforcement learning for continuous control with model misspecification, 2021
references.authors: Volodymyr Mnih Koray Kavukcuoglu David Silver Andrei A. Rusu Joel Veness Marc G. Bellemare Alex Graves Martin Riedmiller Andreas K. Fidjeland Georg Ostrovski Stig Petersen Charles Beattie Amir Sadik Ioannis Antonoglou Helen King Dharshan Kumaran Daan Wierstra Shane Legg Demis Hassabis
references.title: Human-level control through deep reinforcement learning
references.venue: Nature, 518(7540):529–533,
references.authors: Ofir Nachum Yinlam Chow Bo Dai Lihong Li
references.title: DualDICE: Behavior-agnostic estimation of discounted stationary distribution corrections
references.venue: In Advances in Neural Information Processing Systems (NeurIPS),
references.authors: Ofir Nachum Bo Dai Ilya Kostrikov Yinlam Chow Lihong Li Dale Schuurmans
references.title: AlgaeDICE: Policy gradient from arbitrary experience
references.venue: arXiv preprint arXiv:1912.02074,
references.authors: Alex Ray Joshua Achiam Dario Amodei
references.title: Benchmarking Safe Exploration in Deep Reinforcement Learning
references.authors: Harsh Satija Philip Amortila Joelle Pineau
references.title: Constrained Markov decision processes via backward value functions
references.venue: In Proceedings of the 37th International Conference on Machine Learning (ICML),
references.authors: Noah Y. Siegel Jost Tobias Springenberg Felix Berkenkamp Abbas Abdolmaleki Michael Neunert Thomas Lampe Roland Hafner Nicolas Heess Martin Riedmiller
references.title: Keep doing what worked: Behavioral modelling priors for offline reinforcement learning, 2020
references.authors: David Silver Julian Schrittwieser Karen Simonyan Ioannis Antonoglou Aja Huang Arthur Guez Thomas Hubert Lucas Baker Matthew Lai Adrian Bolton Yutian Chen Timothy Lillicrap Fan Hui Laurent Sifre George van den Driessche Thore Graepel Demis Hassabis
references.title: Mastering the game of Go without human knowledge
references.authors: Aviv Tamar Shie Mannor Huan Xu
references.title: Scaling up robust mdps using function approximation
references.venue: In Proceedings of the 31st International Conference on International Conference on Machine Learning (ICML),
references.authors: Chen Tessler Daniel J. Mankowitz Shie Mannor
references.title: Reward constrained policy optimization
references.venue: In International Conference on Learning Representations (ICLR),
references.authors: Núria Armengol Urpı Sebastian Curi Andreas Krause
references.title: Risk-averse offline reinforcement learning
references.venue: In International Conference on Learning Representations (ICLR),
references.authors: Ziyu Wang Alexander Novikov Konrad Zolna Josh S Merel Jost Tobias Springenberg Scott E Reed Bobak Shahriari Noah Siegel Caglar Gulcehre Nicolas Heess Nando de Freitas
references.title: Critic regularized regression
references.venue: In Advances in Neural Information Processing Systems (NeurIPS),
references.authors: Yifan Wu George Tucker Ofir Nachum
references.title: Behavior regularized offline reinforcement learning, 2019
references.authors: Haoran Xu Xianyuan Zhan Xiangyu Zhu
references.title: Constraints penalized q-learning for safe offline reinforcement learning, 2021
references.authors: Mengjiao Yang Bo Dai Ofir Nachum George Tucker Dale Schuurmans
references.title: Offline policy selection under uncertainty, 2020a
references.authors: Mengjiao Yang Ofir Nachum Bo Dai Lihong Li Dale Schuurmans
references.title: Off-policy evaluation via the regularized lagrangian
references.venue: In Advances in Neural Information Processing Systems (NeurIPS),
references.authors: Qisong Yang Thiago D. Simão Simon H Tindemans Matthijs T.J. Spaan
references.title: Wcsac: Worstcase soft actor critic for safety-constrained reinforcement learning
references.venue: Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Tianhe Yu Garrett Thomas Lantao Yu Stefano Ermon James Zou Sergey Levine Chelsea Finn Tengyu Ma
references.title: MOPO: Model-based offline policy optimization
references.venue: In Advances in Neural Information Processing Systems (NeurIPS),
references.authors: Ruiyi Zhang Bo Dai Lihong Li Dale Schuurmans
references.title: GenDICE: Generalized offline estimation of stationary values
references.venue: In Proceedings of the 8th International Conference on Learning Representations (ICLR),
references.authors: Shangtong Zhang Bo Liu Shimon Whiteson
references.title: GradientDICE: Rethinking generalized offline estimation of stationary values
references.venue: In Proceedings of the 35th International Conference on Machine Learning (ICML),
sections.heading: 1 INTRODUCTION
sections.text: Reinforcement learning (RL) has shown great promise in a wide range of domains, such as complex games (Mnih et al., 2015; Silver et al., 2017) and robotic control (Lillicrap et al., 2016; Haarnoja et al., 2018). However, the need to interact with the environment during learning hinders its widespread application to many real-world problems for which executing exploratory behavior in the environment is costly or dangerous. Offline RL (also known as batch RL) (Lange et al., 2012; Levine et al., 2020) algorithms sidestep this problem and perform policy optimization solely from a set of pre-collected data. The use of existing (offline) data can make offline reinforcement learning applicable to real world systems and and has led to a sharp increase in interest in this paradigm.
  Recent works on offline RL, however, mostly assume that the environment is modeled as a Markov decision process (MDP), and standard offline RL algorithms focus on reward-maximization only (Fujimoto et al., 2019; Wu et al., 2019; Kumar et al., 2019; Siegel et al., 2020; Wang et al., 2020; Kumar et al., 2020). In contrast, in real-world domains it is common that the behavior of the agent is subject to additional constraints beyond the reward. Consider, for example, autonomous driving or an industrial robot in a factory. Some behaviors may damage the agent itself or its surroundings, and safety constraints should thus be considered as part of the objective of a suitable reinforcement learning system. One of the ways to mathematically characterize a constrained RL problem is through the formalism of constrained Markov Decision Processes (CMDP) (Altman, 1999). In CMDPs taking an action incurs a cost as well as a reward, and the goal is to maximize the expected long-term reward while satisfying a bound on the expected long-term cost. In this work, we aim to solve the constrained decision making problem in the offline RL setting, to enable deployment in various safety-critical domains where direct learning interactions are infeasible.
  Offline constrained RL inherits the difficulties of offline unconstrained RL, while introducing additional challenges. First, since the target policy being optimized deviates from the data-collection policy with no further data collection, distribution shift becomes the central difficulty. To mitigate the distributional shift, existing offline RL methods frequently adopt the pessimism principle: either
  by explicit policy (and critic) regularization that penalizes deviation from the data-collection policy (Jaques et al., 2019; Wu et al., 2019; Kumar et al., 2019; Siegel et al., 2020; Wang et al., 2020; Lee et al., 2020; Kostrikov et al., 2021) or by reward penalty to the uncertain state-action regions (Kumar et al., 2020; Kidambi et al., 2020; Yu et al., 2020). Second, in offline constrained RL, the computed policy should satisfy the given cost constraints when it is deployed to the real environment. Unfortunately off-policy policy evaluation inherently has estimation errors, and it is therefore difficult to ensure that a policy estimated from a finite dataset will satisfy the constraint when executed in the environment. In addition, constrained policy optimization usually involves an additional optimization for the Lagrange multiplier associated with the cost constraints. Actor-critic-based constrained RL algorithms thus have to solve triple (i.e. critic, actor, Lagrange multiplier) intertwined optimization problems (Borkar, 2005; Tessler et al., 2019), which can be very unstable in practice.
  In this paper, we present an offline constrained RL algorithm that optimizes the state-action stationary distribution directly, rather than the Q-function or the policy. We show that such treatment obviates the need for multiple estimators for the value and the policy, yielding a single optimization objective that is practically solvable. Still, naively constraining the cost value may result in severe constraint violation in the real environment, as we demonstrate empirically. We thus propose a method to constrain the upper bound of the cost value, aiming to compute a policy more robust in constraint violation, where the upper bound is computed in a way motivated by a recent advance in off-policy confidence interval estimation (Dai et al., 2020). Our algorithm, Offline Constrained Policy Optimization via stationary DIstribution Correction Estimation (COptiDICE), estimates the stationary distribution corrections of the optimal policy that maximizes rewards while constraining the cost upper bound, with the goal of yielding a cost-conservative policy for better actual constraint satisfaction. COptiDICE computes the upper bound of the cost efficiently by solving an additional minimization problem. Experimental results show that COptiDICE attains a better policy in terms of constraint satisfaction and reward-maximization, outperforming several baseline algorithms.
sections.heading: 2 BACKGROUND
sections.text: A Constrained Markov Decision Process (CMDP) (Altman, 1999) is an extension of an MDP, formally defined by a tuple M = 〈S,A, T,R,C = {Ck}1..K , ĉ = {ĉk}1..K , p0, γ〉, where S is the set of states, A is the set of actions, T : S × A → ∆(S) is a transition probability, R : S × A → R is the reward function, Ck : S × A → R is the k-th cost function with its corresponding threshold ĉk ∈ R, p0 ∈ ∆(S) is the initial state distribution, and γ ∈ (0, 1] is the discount factor. A policy π : S → ∆(A) is a mapping from state to distribution over actions. We will express solving CMDPs in terms of stationary distribution. For a given policy π, the stationary distribution dπ is defined by:
  dπ(s, a) =  (1− γ) ∞∑ t=0 γt Pr(st = s, at = a) if γ < 1,
  lim T→∞
  1 T+1 T∑ t=0 Pr(st = s, at = a) if γ = 1, (1)
  where s0 ∼ p0, at ∼ π(st), st+1 ∼ T (st, at) for all timesteps t ≥ 0. We define the value of the policy as VR(π) := E(s,a)∼dπ [R(s, a)] ∈ R and VC(π) := E(s,a)∼dπ [C(s, a)] ∈ RK . Constrained RL aims to learn an optimal policy that maximizes the reward while bounding the costs up to the thresholds by interactions with the environment:
  max π VR(π) s.t. VCk(π) ≤ ĉk ∀k = 1, . . . ,K (2)
  Lagrangian relaxation is typically employed to solve Eq. (2), leading to the unconstrained problem:
  min λ≥0 max π
  VR(π)− λ>(VC(π)− ĉ) (3)
  where λ ∈ RK is the Lagrange multiplier and ĉ ∈ RK is the vector-valued cost threshold. The inner maximization in Eq. (3) corresponds to computing an optimal policy that maximizes scalarized rewards R(s, a) − λ>C(s, a), due to the linearity of the value function with respect to the reward function. The outer minimization corresponds to balancing the cost penalty in the scalarized reward function: if the current policy is violating the k-th cost constraint, λk increases so that the cost is penalized more in the scalarized reward, and vice versa.
  In the offline RL setting, online interaction with the environment is not allowed, and the policy is optimized using the fixed offline dataset D = {(s0, s, a, r, c, s′)i}Ni=1 collected with one or more (unknown) data-collection policies. The empirical distribution of the dataset is denoted as dD, and we will abuse the notation dD for s ∼ dD, (s, a) ∼ dD, (s, a, s′) ∼ dD. We abuse (s0, s, a, s′) ∼ dD for s0 ∼ p0, (s, a, s′) ∼ dD. We denote the space of data samples (s0, s, a, s′) as X . A naive way to solve (3) in an offline manner is to adopt an actor-critic based offline RL algorithm for maxπ VR−λ>C(π) while jointly optimizing λ. However, the intertwined training procedure of offpolicy actor-critic algorithms often suffers from instability due to the compounding error incurred by bootstrapping out-of-distribution action values in an offline RL setting (Kumar et al., 2019). The instability would be exacerbated when the nested optimization for λ is added.
sections.heading: 3 OFFLINE CONSTRAINED RL VIA STATIONARY DISTRIBUTION CORRECTION ESTIMATION
sections.text: In this section, we present our offline constrained RL algorithm, Constrained Policy Optimization via stationary DIstribution Correction Estimation (COptiDICE). The derivation of our algorithm starts by augmenting the standard linear program for CMDP (Altman, 1999) with an additional f -divergence regularization1:
  max d
  E(s,a)∼d[R(s, a)]− αDf (d||dD) (4)
  s.t. E(s,a)∼d[Ck(s, a)] ≤ ĉk ∀k = 1, . . . ,K (5)∑ a′ d(s′, a′) = (1− γ)p0(s′) + γ ∑ s,a d(s, a)T (s′|s, a) ∀s′ (6)
  d(s, a) ≥ 0 ∀s, a, (7) where Df (d||dD) := E(s,a)∼dD [ f ( d(s,a) dD(s,a) )] is the f -divergence between the distribution d and the dataset distribution dD, and α > 0 is the hyperparameter that controls the degree of pessimism, i.e. how much we penalize the distribution shift, a commonly adopted principle for offline RL (Nachum et al., 2019b; Kidambi et al., 2020; Yu et al., 2020; Lee et al., 2021). We assume that dD > 0 and f is a strictly convex and continuously differentiable function with f(1) = 0. Note that when α = 0, the optimization (4-7) reduces to the standard linear program for CMDPs. The Bellman-flow constraints (6-7) ensure that d is the stationary distribution of a some policy, where d(s, a) can be interpreted as a normalized discounted occupancy measure of (s, a). Thus, we seek the stationary distribution of an optimal policy that maximizes the reward value (4) while bounding the cost values (5). Once the optimal solution d∗ has been estimated, its corresponding optimal policy is obtained by π∗(a|s) = d
  ∗(s,a)∑ a′ d ∗(s,a′) .
  Now, consider the Lagrangian for the constrained optimization problem (4-7):
  min λ≥0,ν max d≥0 E(s,a)∼d[R(s, a)]− αDf (d||dD)− K∑ k=1 λk ( E(s,a)∼d[Ck(s, a)]− ĉk ) − ∑ s′ ν(s′) [∑ a′ d(s′, a′)− (1− γ)p0(s′)− γ ∑ s,a d(s, a)T (s′|s, a) ] (8)
  where λ ∈ RK+ is the Lagrange multiplier for the cost constraints (5), and ν(s) ∈ R is the Lagrange multiplier for the Bellman flow constraints (6). Solving (8) in its current form requires evaluation of T (s′|s, a) for (s, a) ∼ d, which is not accessible in the offline RL setting. To make the optimization tractable, we rearrange the terms so that the direct dependence on d is eliminated, while introducing new optimization variables w that represent stationary distribution corrections:
  min λ≥0,ν max d≥0 E (s,a)∼d s′∼T (s,a)
  [ R(s, a)− λ>C(s, a) + ν(s′)− ν(s) ] − αE(s,a)∼dD [ f ( d(s,a) dD(s,a) )] + (1− γ)Es0∼p0 [ν(s0)] + λ>ĉ
  = min λ≥0,ν max w≥0
  E(s,a)∼dD [ w(s, a)eλ,ν(s, a)− αf(w(s, a)) ] + (1− γ)Es0∼p0 [ν(s0)] + λ>ĉ (9)
  1For simplicity, we only consider discounted CMDPs (γ < 1) here, but the result can be generalized to the case of average reward-cost CMDPs (γ = 1) (Appendix A).
  where eλ,ν(s, a) := R(s, a)− λ>C(s, a) + γEs′∼T (s,a)[ν(s′)]− ν(s) is the advantage function by regarding ν as a state value function, and w(s, a) := d(s,a)
  dD(s,a) is the stationary distribution correction.
  Every term in Eq. (9) can be estimated from samples in the offline dataset D:
  min ν,λ≥0 max w≥0
  E(s0,s,a,s′)∼dD [ w(s, a)êλ,ν(s, a, s ′)− αf(w(s, a)) + (1− γ)ν(s0) ] + λ>ĉ (10)
  where êλ,ν(s, a, s′) := R(s, a)−λ>C(s, a)+γν(s′)−ν(s) is the advantage estimate using a single sample. As a consequence, (10) can be optimized in a fully offline manner. Moreover, exploiting the strict convexity of f , we can further derive a closed-form solution for the inner maximization in (9) as follows. All the proofs can be found in Appendix B. Proposition 1. For any ν and λ, the closed-form solution of the inner maximization problem in (9) is given by:
  w∗λ,ν(s, a) = (f ′)−1 ( 1 αeλ,ν(s, a) ) + where x+ = max(0, x) (11)
  Finally, by plugging the closed-form solution (11) into (9), we obtain the following convex minimization problem:
  min λ≥0,ν
  L(λ, ν) = E(s,a)∼dD [ w∗λ,ν(s, a)eλ,ν(s, a)− αf(w∗λ,ν(s, a)) ] + (1− γ)Es0∼p0 [ν(s0)] + λ>ĉ
  (12)
  To sum up, by operating in the space of stationary distributions, constrained (offline) RL can in principle be solved by solving a single convex minimization (12) problem. This is in contrast to existing constrained RL algorithms that manipulate both Q-function and policy, and thus require solving triple optimization problems for the actor, the critic, and the cost Lagrange multiplier with three different objective functions. Note also that when λ is fixed and treated as a constant, (12) reduces to OptiDICE (Lee et al., 2021) for unconstrained RL with the scalarized rewards R(s, a)− λ>C(s, a), without considering the cost constraints. In order to meet the constraints, λ should also be optimized, and the procedure of (12) can be understood as joint optimization of:
  ν ← arg min ν
  L(λ, ν) (OptiDICE for R− λ>C) (13)
  λ← arg min λ≥0 λ> ( ĉ− E(s,a)∼dD [w∗λ,ν(s, a)C(s, a)]︸ ︷︷ ︸
  ≈VC(π)
  ) (Cost Lagrange multiplier)
  Once the optimal solution of (12), (λ∗, ν∗), is computed, w∗λ∗,ν∗(s, a) = dπ ∗ (s,a) dD(s,a)
  is also derived by (11), which is the stationary distribution correction between the stationary distribution of the optimal policy for the CMDP and the dataset distribution.
sections.heading: 3.1 COST-CONSERVATIVE CONSTRAINED POLICY OPTIMIZATION
sections.text: Our first method based on (12) relies on off-policy evaluation (OPE) using DICE to ensure cost constraint satisfaction, i.e. E(s,a)∼dD [wλ,ν(s, a)C(s, a)] ≈ E(s,a)∼dπ [C(s, a)] ≤ ĉ. However, as we will see later, constraining the cost value estimate naively can result in constraint violation when deployed to the real environment. This is due to the fact that an off-policy value estimate based on a finite dataset inevitably has estimation error. Reward estimation error may be tolerated as long as the value estimates are useful as policy improvement signals: it may be sufficient to maintain the relative order of action values, while the absolute values matter less. For the cost value constraint, we instead rely on the estimated value directly.
  To make a policy robust against cost constraint violation in an offline setting, we consider the constrained policy optimization scheme that exploits the upper bound of the cost value estimate:
  max π V̂R(π) s.t. UpperBound(V̂Ck(π)) ≤ ĉk ∀k (14)
  Then, the key question is how to estimate the upper bound of the policy value. One natural way is to exploit bootstrap confidence interval (Efron & Tibshirani, 1993; Hanna et al., 2017). We can
  construct bootstrap datasetsDi by resampling fromD and run an OPE algorithm on eachDi, which yields population statistics for confidence interval estimation {V̂C(π)i}mi=1. However, this procedure is computationally very expensive since it requires solvingmOPE tasks. Instead, we take a different approach in a more computationally efficient way motivated by CoinDICE (Dai et al., 2020), a recently proposed DICE-family algorithm for off-policy confidence interval estimation. Specifically, given that our method estimates the stationary distribution corrections w(s, a) ≈ d
  π(s,a) dD(s,a)
  of the target policy π, we consider the following optimization problem for each cost function Ck:
  max p̃∈∆(X) E(s0,s,a,s′)∼p̃[w(s, a)Ck(s, a)] (15) s.t. DKL(p̃(s0, s, a, s′)||dD(s0, s, a, s′)) ≤ (16)∑ a′ p̃(s′, a′)w(s′, a′) = (1− γ)p̃0(s′) + γ ∑ s,a p̃(s, a)w(s, a)p̃(s′|s, a) ∀s′ (17)
  where p̃(s0, s, a, s′) = p̃0(s0)p̃(s, a)p̃(s′|s, a) is the distribution over data samples (s0, s, a, s′) ∈ X which lies in the simplex ∆(X), and > 0 is the hyperparameter. In essence, we want to adversarially optimize the distribution over data samples p̃ so that it overestimates the cost value by (15). At the same time, we enforce that the distribution p̃ should not be perturbed too much from the empirical data distribution dD by the KL constraint (16). Lastly, the perturbation of distribution should be done in a way that maintains compatibility with the Bellman flow constraint. The constraint (17) is analogous to the Bellman flow constraint (6) by noting that p̃(s, a)w(s, a) = p̃(s, a) d
  π(s,a) dD(s,a)
  ≈ dπ(s, a). In this optimization, when = 0, the optimal solution is simply given by p̃∗ = dD, which yields the vanilla OPE result via DICE, i.e. E(s,a)∼dD [w(s, a)Ck(s, a)]. For > 0, the cost value will be overestimated more as increases. Through a derivation similar to that for obtaining (12), we can simplify the constrained optimization into a single unconstrained minimization problem as follows. We denote (s0, s, a, s′) as x for notational brevity. Proposition 2. The constrained optimization problem (15-17) can be reduced to solving the following unconstrained minimization problem:
  min τ≥0,χ
  `k(τ, χ;w) = τ logEx∼dD [ exp ( 1 τ ( w(s, a)(Ck(s, a) + γχ(s ′)− χ(s)) + (1− γ)χ(s0) ))] + τ
  (18)
  where τ ∈ R+ corresponds to the Lagrange multiplier for the constraint (16), and χ(s) ∈ R corresponds to the Lagrange multiplier for the constraint (17). In other words, minτ≥0,χ `(τ, χ) = E(s,a)∼p̃∗ [w(s, a)Ck(s, a)] where p̃∗ is the optimal perturbed distribution of the problem (15-17). Also, for the optimal solution (τ∗, χ∗), p̃∗ is given by:
  p̃∗(x) ∝ dD(x) exp (
  1 τ∗ ( w(s, a)(Ck(s, a) + γχ ∗(s′)− χ∗(s)) + (1− γ)χ∗(s0) ))
  ︸ ︷︷ ︸ =: ω∗(x) (unnormalized weight for x = (s0, s, a, s′))
  (19)
  Note that every term in (18) can be estimated only using samples of the offline dataset D, thus it can be optimized in a fully offline manner. This procedure can be understood as computing the weights for each sample while adopting reweighting in the DICE-based OPE, i.e. UpperBound(V̂C(π)) = Ex∼dD [ω̃∗(x)w(s, a)C(s, a)] where ω̃∗(x) = (normalized ω∗(x) of (19)). The weights are given non-uniformly so that the cost value is overestimated to the extent controlled by . Remark. CoinDICE (Dai et al., 2020) solves the similar optimization problem to estimate an upper cost value of the target policy π as follows:
  max w≥0 min τ≥0,ν τ logE x∼dD a0∼π(s0) a′∼π(s′)
  [ exp ( 1 τ ( w(s, a)(Ck(s, a) + γν(s ′, a′)− ν(s′, a′)) + (1− γ)ν(s0, a0) ))] + τ
  (20)
  It is proven that (20) provides an asymptotic (1−α)-upper-confidence-interval of the policy value if := ξαN where ξα is the (1−α)-quantile of the χ
  2-distribution with 1 degree of freedom (Dai et al., 2020). Compared to our optimization problem (18), CoinDICE’s (20) involves the additional outer maximization, which is for estimating w(s, a) = d̃
  π(s,a) dD(s,a)
  , the stationary distribution corrections of the target policy π. In contrast, we consider the case when w is given, thus solving the inner minimization alone is enough.
  Finally, we are ready to present our final algorithm COptiDICE, an offline constrained RL algorithm that maximizes rewards while bounding the upper cost value, with the goal of computing a policy robust against cost violation. COptiDICE addresses (14) by solving the following joint optimization.
  ν ← arg min ν
  L(λ, ν) (OptiDICE for R− λ>C) (21)
  τ, χ← arg min τ≥0,χ
  ∑K k=1 `k(τk, χk;w ∗ λ,ν) (Upper cost value estimation)
  λ← arg min λ≥0 λ> ( ĉ− `(τ, χ;w∗λ,ν)︸ ︷︷ ︸ ≈UpperBound(V̂C(π)) ) (Cost Lagrange multiplier)
  Compared to (13), the additional minimization for (τ, χ) is introduced to estimate the upper bound of cost value.
sections.heading: 3.2 POLICY EXTRACTION
sections.text: Our algorithm estimates the stationary distribution corrections of the optimal policy, rather than directly obtaining the policy itself. Since the stationary distribution corrections do not provide a direct way to sample an action, we need to extract the optimal policy π∗ from w∗(s, a) = d π∗ (s,a) dD(s,a)
  , in order to select actions when deployed. For finite CMDPs, it is straightforward to obtain π∗ by π∗(a|s) = d π∗ (s,a)∑
  a′ d π∗ (s,a′) = d D(s,a)w∗(s,a)∑ a′ d D(s,a)w∗(s,a) . However, the same method cannot directly be
  applied to continuous CMDPs due to the intractability of computing the normalization constant. For continuous CMDPs, we instead extract the policy using importance-weighted behavioral cloning:
  max π
  E(s,a)∼dπ∗ [log π(a|s)] = E(s,a)∼dD [w∗(s, a) log π(a|s)] (22)
  which maximizes the log-likelihood of actions to be selected by the optimal policy π∗.
sections.heading: 3.3 PRACTICAL ALGORITHM WITH FUNCTION APPROXIMATION
sections.text: For continuous or large CMDPs, we represent our optimization variables using neural networks. The Lagrange multipliers ν and χ are networks parameterized by θ and φ respectively: νθ : S → R is a feedforward neural network that takes a state as an input and outputs a scalar value, and χφ : S → RK is defined similarly. λ ∈ RK+ and τ ∈ RK+ are represented by K-dimensional vectors. For the policy πψ , we use a mixture density network (Bishop, 1994) where the parameters of a Gaussian mixture model are output by the neural network. The parameters of the νθ network are trained by minimizing the loss:
  min θ Jν(θ) =Ex∼dD
  [ ŵ(s, a, s′)(R(s, a)− λ>C(s, a) + γνθ(s′)− νθ(s)) (23)
  − αf(ŵ(s, a, s′)) + (1− γ)νθ(s0) ] + λ>ĉ
  where ŵ(s, a, s′) := (f ′)−1 (
  1 α (R(s, a) − λ >C(s, a) + γνθ(s ′) − νθ(s)) ) +
  . While Jλν can be a biased estimate of L(λ, ν) in (12) in general due to (f ′)−1(E[·]) 6= E[(f ′)−1(·)], we can show that Jλν is an upper bound of L(ν, λ) (i.e. we minimize the upper bound), and J λ ν = L(ν, λ) holds if transition dynamics are deterministic (e.g. Mujoco control tasks). The parameters of the χφ network and τ can be trained by:
  min τ≥0,φ K∑ k=1 τ logEx∼dD [ exp ( 1 τ ( ŵ(s, a, s′)(Ck(s, a) + γχφ,k(s ′)− χφ,k(s)) (24)
  + (1− γ)χφ,k(s0) ))] + τk
  This involves a logarithm outside of the expectation, which implies that mini-batch approximations would introduce a bias. Still, we adopt the simple mini-batch approximation for computational efficiency, with a moderately large batch size (e.g. 1024), which worked well in practice. The empirical form of the loss we use is given by:
  min τ≥0,φ Jτ,χ(τ, φ) =Ebatch(D)∼D [ K∑ k=1 τ logEx∼batch(D) [ exp ( 1 τ ( ŵ(s, a, s′)· (25)
  (Ck(s, a) + γχφ,k(s ′)− χφ,k(s)) + (1− γ)χφ,k(s0) ))] + τk ]
  Lastly, λ and the policy parameter ψ are optimized by:
  min λ≥0
  Jλ(λ) = λ >(ĉ− Jτ,χ(τ, φ)) (26)
  min ψ Jπ(ψ) = −Ex∼dD [ŵ(s, a, s′) log πψ(a|s)] (27)
  The complete pseudo-code is described in Appendix C, where every parameter is optimized jointly.
sections.heading: 4 EXPERIMENTS
sections.heading: 4.1 TABULAR CMDPS (RANDOMLY GENERATED CMDPS)
sections.text: We first probe how COptiDICE can improve the reward performance beyond the data-collection policy while satisfying the given cost constraint via repeated experiments. We follow a protocol similar to the random MDP experiment in (Laroche et al., 2019; Lee et al., 2021) but with cost as an additional consideration. We conduct repeated experiments for 10K runs, and for each run, a CMDP M is generated randomly with the cost threshold ĉ = 0.1. We test with two types of data-collection policy πD, a constraint-satisfying policy (i.e. VC(πD) = 0.09) and a constraint-violating policy (i.e. VC(πD) = 0.11). Then, a varying number of trajectories N ∈ {10, 20, 50, 100, 200, 500, 1000, 2000} are collected from the sampled CMDP using the constructed data-collection policy πD, which constitutes the offline dataset D. Finally, the offline dataset D is given to each offline constrained RL algorithm, and its reward and cost performance is evaluated. For the reward, we evaluate the normalized performance of the policy π by VR(π)−VR(πD) VR(π∗)−VR(πD) ∈ (−∞, 1] to see the performance improvement of π over πD intuitively, where π ∗ is the optimal policy of the underlying CMDP. More details can be found in Appendix D.
  Offline constrained RL has been mostly unexplored, thus lacks published baseline algorithms. We consider the following three baselines. First, BC denotes the simple behavior cloning algorithm to see whether the proposed method is just remembering the dataset. Second, Baseline denotes the algorithm that constructs a maximum-likelihood estimation (MLE) CMDP M̂ using D and then solves the MLE CMDP using a tabular CMDP solver (LP solver) (Altman, 1999). Third, C-SPIBB is the variant of SPIBB (an offline RL method for tabular MDPs) (Laroche et al., 2019), where we modified SPIBB to deal with the cost constraint by Lagrange relaxation (Appendix D).
  Figure 1a presents the result when the data-collection policy is constraint-satisfying. The performance of BC approaches the performance of the πD as the size of the dataset increases, as expected. When the size of the offline dataset is very small, Baseline severely violates the cost constraint when its computed policy is deployed to the real environment (cost red curve in Figure 1a), and it even fails to improve the reward performance over πD (reward red curve in Figure 1a). This result is expected since Baseline overfits to the MLE CMDP, exploiting the highly uncertain state-actions. This can cause a significant gap between the stationary distribution of the optimized policy computed in M and the one computed in M̂ , leading to failure in both reward performance improvement and cost constraint satisfaction. To prevent such distributional shift, offline RL algorithms commonly adopt the pessimism principle, encouraging staying close to the data support. We can observe that such pessimism principle is also effective in offline constrained RL: both C-SPIBB (orange) and the naive version of COptiDICE (green) show consistent policy improvement over the data-collection policy while showing better constraint satisfaction. Still, the pessimism principle alone is not sufficient to ensure constraint satisfaction, raising the need for additional treatment for cost-conservativeness. Finally, our COptiDICE (blue) shows much stricter cost satisfaction than other baseline algorithms while outperforming Baseline and C-SPIBB in terms of reward performance.
  Figure 1b presents the result when the data-collection policy is constraint-violating, where all the baseline algorithms exhibit severe cost violation. This result shows that if the agent is encouraged to stay close to the constraint-violating policy, it may negatively affect the constraint satisfaction, although the pessimism principle was beneficial in terms of reward maximization. In this situation, only COPtiDICE (blue) could meet the given constraint in general, which demonstrates the effectiveness of our proposed method of constraining the upper bound of cost value. Although COptiDICE (blue) shows reward performance degradation when the size of dataset is very small, this is natural in that it sacrifices the reward performance to lower the cost value to meet the constraint conservatively, and it still outperforms the baseline in this low-data regime.
sections.heading: 4.2 CONTINUOUS CONTROL TASKS (RWRL SUITE)
sections.text: We also evaluate COptiDICE on domains from the Real-World RL (RWRL) suite (Dulac-Arnold et al., 2020), where the safety constraints are employed. The cost of 1 is given if the task-specific safety constraint is violated at each time step, and the goal is to compute a policy that maximizes rewards while bounding the average cost up to ĉ. Per-domain safety constraints and the cost constraint thresholds are given in Appendix D. Due to lack of an algorithm that addresses offline constrained RL in continuous action space, we compare COptiDICE with simple baseline algorithms, i.e. BC: A simple behavior-cloning agent, CRR (Wang et al., 2020): a state-of-the-art (unconstrained) offline RL algorithm, and C-CRR: the constrained variant of CRR with Lagrangian relaxation where a cost critic and a Lagrange multiplier for the cost constraint are introduced (Appendix D).
  Since there is no standard dataset for offline constrained RL, we collected data using online constrained RL agents (C-DMPO; the constrained variant of Distributional MPO) (Abdolmaleki et al., 2018; Mankowitz et al., 2021). We trained the online C-DMPO with various cost thresholds ĉ and saved checkpoints at regular intervals, which constitutes the pool of policy checkpoints. Then, we generated datasets, where each of them consists of β × 100% constraint-satisfying trajectories and the rest constraint-violating trajectories. The trajectories were sampled by policies in the pool of policy checkpoints. Since there is a trade-off between reward and cost in general, the dataset is a mixture of low-reward-low-cost trajectories and high-reward-high-cost trajectories.
  Figure 2 presents our results in RWRL tasks, where the dataset contains mostly constraint-satisfying trajectories (β = 0.8), with some cost-violating trajectories. This type of dataset is representative of many practical scenarios: the data-collecting agent behaves safely in most cases, but sometimes exhibit exploratory behaviors which can be leveraged for potential performance improvement. Due to the characteristics of these datasets, BC (orange) generally yields constraint-satisfying policy, but its reward performance is also very low. CRR (red) significantly improves reward performance over BC, but it does not ensure that the constraints are satisfied. C-CRR (brown) incurs relatively lower cost value than BC in Walker, Quadruped, and Humanoid, but its reward performance is clearly worse than BC. The naive COptiDICE algorithm (green) takes the cost constraint into account but nevertheless frequently violates the constraint due to limitations of OPE. Finally, COptiDICE (blue) computes a policy that is more robust to cost violation than other algorithms, while significantly outperforming BC in terms of reward performance. We observe that the hyperparameter in (16) controls the degree of cost-conservativeness as expected: larger values of lead to overestimates of the cost value, yielding a more conservative policy.
  To study the dependence on the characteristics of the dataset we experiment with different values of β. Figure 3a show the result for β = 0.8 (low-reward-low-cost data), Figure 3b for β = 0.5, and Figure 3c for β = 0.2 (high-reward-high-cost data). These results show the expected trend: more high-reward-high-cost data leads to a joint increase in rewards and costs of all agents. A simple modification of the unconstrained CRR to the constrained one (brown) was not effective enough to satisfy the constraint. Our vanilla offline constrained RL algorithm (green), encouraged to stay close to the data, also suffers from severe constraint violation when most of the trajectories are given as the constraint-violating ones, which is similar to the result of Figure 1c-1d. Finally,
  COptiDICE (blue) demonstrates more robust behavior to avoid constraint violations across dataset configurations, highlighting the effectiveness of our method constraining the cost upper bound.
sections.heading: 5 DISCUSSION AND CONCLUSION
sections.text: The notion of safety in RL has been captured in various forms such as risk-sensitivity (Chow et al., 2015; Urpı́ et al., 2021; Yang et al., 2021), Robust MDP (Iyengar, 2005; Tamar et al., 2014), and Constrained MDP (Altman, 1999), among which we focus on CMDP as it provides a natural formalism to encode safety specifications (Ray et al., 2019). Most of the existing constrained RL algorithms (Achiam et al., 2017; Tessler et al., 2019; Satija et al., 2020) are on-policy algorithms, which cannot be applied to the offline setting directly. A recent exception is the work by Le et al. (2019) that also aims to solve constrained RL in an offline setting, though its method is limited to discrete action spaces and relies on solving an MDP completely as an inner optimization, which is inefficient. It also relies on the vanilla OPE estimate of the policy cost, which could result in severe constraint violation when deployed. Lastly, in a work done concurrently to ours, Xu et al. (2021) also exploits overestimated cost value to deal with the cost constraint, but their approach relies on an actor-critic algorithm, while ours relies on stationary distribution optimization.
  In this work, we have presented a DICE-based offline constrained RL algorithm, COptiDICE. DICEfamily algorithms have been proposed for off-policy evaluation (Nachum et al., 2019a; Zhang et al., 2020a;b; Yang et al., 2020b; Dai et al., 2020), imitation learning (Kostrikov et al., 2019), offline policy selection (Yang et al., 2020a), and RL (Nachum et al., 2019b; Lee et al., 2021), but none of them is for constrained RL. Our first contribution was a derivation that constrained offline RL can be tackled by solving a single minimization problem. We demonstrated that such approach, in its simplest form, suffers from constraint violation in practice. To mitigate the issue, COptiDICE instead constrains the cost upper bound, which is estimated in a way that exploits the distribution correction w obtained by solving the RL problem. Such reuse of w eliminates the nested optimization in CoinDICE (Dai et al., 2020), and COptiDICE can be optimized efficiently as a result. Experimental results demonstrated that our algorithm achieved better trade-off between reward maximization and constraint satisfaction than several baselines, across domains and conditions.
sections.heading: A ALGORITHM FOR UNDISCOUNTED CMDP
sections.text: For γ = 1, the optimization problem (4-7) should be modified by adding an additional normalization constraint ∑ s,a d(s, a) = 1.
  max d
  E(s,a)∼d[R(s, a)]− αDf (d||dD) (28)
  s.t. E(s,a)∼d[Ck(s, a)] ≤ ĉk ∀k = 1, . . . ,K (29)∑ a′ d(s′, a′) = (1− γ)p0(s′) + γ ∑ s,a d(s, a)T (s′|s, a) ∀s′ (30)
  d(s, a) ≥ 0 ∀s, a (31)∑ s,a d(s, a) = 1 (32)
  Then, we consider the Lagrangian:
  min λ≥0,ν max d≥0 E(s,a)∼d[R(s, a)]− αDf (d||dD)− K∑ k=1 λk ( E(s,a)∼d[Ck(s, a)]− ĉk ) − ∑ s′ ν(s′) [∑ a′ d(s′, a′)− (1− γ)p0(s′)− γ ∑ s,a d(s, a)T (s′|s, a) ] − µ [∑ s,a d(s, a)− 1 ] (33)
  where µ ∈ R is the Lagrange multiplier for the normalization constraint (32). Then, we rearrange the terms so that the direct dependence on d is eliminated, while introducing new optimization variables w(s, a) = d(s,a)
  dD(s,a) that represent stationary distribution corrections:
  min λ≥0,ν,µ max d≥0 E (s,a)∼d s′∼T (s,a)
  [ R(s, a)− λ>C(s, a) + ν(s′)− ν(s)− µ ] − αE(s,a)∼dD [ f ( d(s,a) dD(s,a) )] + (1− γ)Es0∼p0 [ν(s0)] + λ>ĉ+ µ
  = min λ≥0,ν,µ max w≥0
  E(s,a)∼dD [ w(s, a)(eλ,ν(s, a)− µ)− αf(w(s, a)) ] + (1− γ)Es0∼p0 [ν(s0)] + λ>ĉ+ µ
  (34)
  which yields the minmax optimization problem that can be optimized in a fully offline manner. Due to the strict convexity of f , we can also derive the closed form solution of the inner maximization problem:
  w∗λ,ν,µ(s, a) = (f ′)−1 ( 1 α (eλ,ν(s, a)− µ) ) +
  (35)
  which simplify the the minmax problem (34) into the following single minimization problem:
  min λ≥0,ν,µ
  L(λ, ν, µ) = E(s,a)∼dD [ w∗λ,ν,µ(s, a)(eλ,ν(s, a)− µ)− αf(w∗λ,ν,µ(s, a)) ] + (1− γ)Es0∼p0 [ν(s0)] + λ>ĉ+ µ (36)
  Once the optimal solution (λ∗, ν∗, µ∗) are obtained, we can also compute the stationary distribution corrections of the optimal policy using (35). Still, naively using (36) would similarly result in cost violation when the resulting policy is deployed to the real environment. We therefore adopt constraining the upper bound of cost value:
  ν, µ← arg min ν,µ
  L(λ, ν, µ) (RL for R− λ>C using (36)) (37)
  τ, χ← arg min τ≥0,χ
  ∑K k=1 `k(τk, χk;w ∗ λ,ν,µ) (Upper cost value estimation using (18))
  λ← arg min λ≥0 λ> ( ĉ−`(τ, χ;w∗λ,ν,µ)︸ ︷︷ ︸ ≈UpperBound(V̂C(π)) ) (Cost Lagrange multiplier)
  which completes the brief description of COptiDICE for γ = 1.
sections.heading: B PROOFS
sections.text: Proposition 1. For any ν and λ, the closed-form solution of
  max w≥0
  L(w, λ, ν) := E(s,a)∼dD [ w(s, a)eλ,ν(s, a)− αf(w(s, a)) ] + (1− γ)Es0∼p0 [ν(s0)] + λ>ĉ
  (38)
  is given by:
  w∗λ,ν(s, a) = (f ′)−1 ( 1 αeλ,ν(s, a) ) + where x+ = max(0, x) (39)
  Proof. For a fixed λ and ν, we write the dual of the maximization problem maxw≥0 L(w, λ, ν):
  max w min κ≥0 L(w, λ, ν) + ∑ s,a κ(s, a)w(s, a).
  By the strong duality, it is sufficient to consider KKT condition for (w∗, κ∗).
  Condition 1 (Primal feasibility) w∗(s, a) ≥ 0 ∀s, a Condition 2 (Dual feasibility) κ∗(s, a) ≥ 0 ∀s, a Condition 3 (Stationarity) dD(s, a)(eλ,ν(s, a)− αf ′(w∗(s, a)) + κ∗(s, a)) = 0 ∀s, a Condition 4 (Complementary slackness) w∗(s, a)κ∗(s, a) = 0 ∀s, a By Stationarity and dD > 0,
  f ′(w∗(s, a)) = 1α (eλ,ν(s, a) + κ ∗(s, a)) ∀s, a ⇔ w∗(s, a) = (f ′)−1 (
  1 α (eλ,ν(s, a) + κ
  ∗(s, a)) ) ∀s, a.
  For each (s, a), consider either w∗(s, a) > 0 or w∗(s, a) = 0.
  (When w∗(s, a) > 0): κ∗(s, a) = 0 holds by Complementary slackness, which means:
  w∗(s, a) = (f ′)−1 (
  1 αeλ,ν(s, a)
  ) > 0.
  Note that Dual feasibility holds. Since f ′ is a strictly increasing function, eν(s, a) > αf ′(0).
  (When w∗(s, a) = 0): By Stationarity and Dual feasibility,
  κ∗(s, a) = αf ′(0)− eλ,ν(s, a) ≥ 0 ⇔ eν(s, a) ≤ αf ′(0)
  This concludes w∗ν(s, a) = (f ′)−1 ( 1 αeλ,ν(s, a) ) + .
  Proposition 2. The constrained optimization problem (15-17) can be reduced to solving the following unconstrained minimization problem:
  min τ≥0,χ
  `k(τ, χ;w) = τ logEx∼dD [ exp ( 1 τ ( w(s, a)(Ck(s, a) + γχ(s ′)− χ(s)) + (1− γ)χ(s0) ))] + τ
  (40)
  where τ ∈ R+ corresponds to the Lagrange multiplier for the constraint (16), and χ(s) ∈ R corresponds to the Lagrange multiplier for the constraint (17). In other words, minτ≥0,χ `(τ, χ) = E(s,a)∼p̃∗ [w(s, a)Ck(s, a)] where p̃∗ is the optimal perturbed distribution of the problem (15-17). Also, for the optimal solution (τ∗, χ∗), p̃∗ is given by:
  p̃∗(x) ∝ dD(x) exp (
  1 τ∗ ( w(s, a)(Ck(s, a) + γχ ∗(s′)− χ∗(s)) + (1− γ)χ∗(s0) ))
  ︸ ︷︷ ︸ =: ω∗(x) (unnormalized weight for x = (s0, s, a, s′))
  (41)
  Proof. For the given constrained optimization problem:
  max p̃∈∆(X) E(s0,s,a,s′)∼p̃[w(s, a)Ck(s, a)] (42) s.t. DKL(p̃(s0, s, a, s′)||dD(s0, s, a, s′)) ≤ (43)∑ a′ p̃(s′, a′)w(s′, a′) = (1− γ)p̃0(s′) + γ ∑ s,a p̃(s, a)w(s, a)p̃(s′|s, a) ∀s′ (44)
  We consider the Lagrangian:
  max τ≥0,χ,ζ max p̃≥0 ∑ x p̃(s0, s, a, s ′)[w(s, a)Ck(s, a)]− τ (∑ x p̃(s0, s, a, s ′) [ log p̃(s0,s,a,s ′) dD(s0,s,a,s′) ] − )
  − ∑ s′ χ(s′) [∑ a′ p̃(s′, a′)w(s′, a′)− (1− γ)p̃0(s′)− γ ∑ s,a p̃(s, a)w(s, a)p̃(s′|s, a) ] − ζ [∑ x p̃(s0, s, a, s ′)− 1 ]
  (45)
  where τ ∈ R+ is the Lagrange multiplier for KL constraint (43), χ(s′) ∈ R is the Lagrange multiplier for (44), and ζ ∈ R is the Lagrange multiplier for the normalization constraint that ensures∑ x p̃(s0, s, a, s ′) = 1. Then, we rearrange (45) by:
  max τ≥0,χ,ζ max p̃≥0 g(τ, χ, p̃) = ∑ x p̃(x) [ w(s, a) ( Ck(s, a) + γχ(s ′)− χ(s) ) + (1− γ)χ(s0)− τ log p̃(x)dD(x) ] + τ − ζ
  [∑ x p̃(x)− 1 ]
  (46)
  Then, we can compute the closed form solution for the inner-maximization problem. Consider ∂g(τ,χ,p̃) ∂p̃(x) = 0 should hold for each x. Then,
  ∂g(τ,χ,p̃) ∂p̃(x) = w(s, a) ( Ck(s, a) + γχ(s ′)− χ(s) ) + (1− γ)χ(s0)− τ log p̃(x)dD(x) + τ − ζ = 0 (47)
  ⇒ p̃(x) ∝ dD(x) exp (
  1 τ
  ( w(s, a) ( Ck(s, a) + γχ(s ′)− χ(s) ) + (1− γ)χ(s0) ))
  (48)
  with some normalization constant described in terms of ζ. Then, by plugging (48) into (46) with eliminating ζ, we obtain the result. (41) is also by direct application of (48).
sections.heading: C PSEUDOCODE OF COPTIDICE
sections.text: Algorithm 1 COptiDICE Input: An offline dataset D = {(s0, s, a, r, c, s′)i}Ni=1, a learning rate η.
  1: Initialize parameter vectors θ, φ, λ, τ, ψ. 2: for each gradient step do 3: Sample mini-batches from D. 4: Compute gradients and perform SGD update: 5: θ ← θ − η∇θJν(θ) (Eq. (23)) φ← φ− η∇φJτ,χ(τ, φ) (Eq. (25)) 6: τ ← [ τ − η∇τJτ,χ(τ, φ) ] + (Eq. (25)) λ← [ λ− ηJλ(λ) ] +
  (Eq. (26)) 7: ψ ← ψ − η∇ψJπ(ψ) (Eq. (27)) 8: end for
sections.heading: D EXPERIMENTAL SETTINGS
sections.text: D.1 RANDOM CMDPS
  For random CMDP experiments, We follow a similar experimental protocol as (Laroche et al., 2019; Lee et al., 2021) with additional consideration of cost constraint.
  Random CMDP generation For each run, we constructed a random CMDP with |S| = 50, |A| = 4, γ = 0.95, and a fixed initial state s0. The transition probability is constructed randomly with connectivity of 4, i.e. for each (s, a), we sample 4 states uniformly, and then, the transition probabilities to those states are determined by Dirichlet(1, 1, 1, 1). The reward of 1 is given to a single state that minimizes the optimal policy’s reward value at s0, and 0 is given anywhere else. This reward design can be roughly understood as choosing a goal state that is most difficult to reach from s0. The cost function is generated randomly, i.e. C(s, a) ∼ Beta(0.2, 0.2) for ∀s ∈ S, a ∈ {a2, a3, a4} and C(s, a1) = 0 to ensure existence of a feasible policy of the CMDP. Lastly, the cost threshold ĉ = 0.1 is used.
  Data-collection policy generation To construct the data-collection policy, we consider the following entropy-regularized CMDP:
  max d
  E(s,a)∼d[R(s, a)]− σE(s,a)[log d(s, a)] (49)
  s.t. E(s,a)∼d[C(s, a)] ≤ ĉD (50)
  where ĉD ∈ {0.09, 0.11} is the hyperparameter that determines the cost value of πD. Starting from σ = 0, we gradually increase σ (i.e. adding stochasticity to policy, which adversarially affect the reward performance) until the reward performance of the computed policy reaches 0.9 × VR(π∗) where π∗ is the optimal policy of the given CMDP. After the data-collection policy πD is generated, we sample trajectories using πD, which constitutes the offline dataset D. We conducted experiments for a varying number of trajectories, i.e. (the number of trajectories) ∈ {10, 20, 50, 100, 200, 500, 1000, 2000}. Each episode is terminated either when 50 time steps have reached or the agent reached the goal state that yields a non-zero reward.
  Hyperparameters For C-SPIBB, we used N∧ = 5. For COptiDICE, we used α = 1N and = 0.1 N , where N denotes the number of trajectories in D. We also used f(x) = 1 2 (x − 1)
  2, which corresponds to χ2-divergence.
  C-SPIBB: Constrained variant of SPIBB C-SPIBB solves the offline RL problem with respect to R − λC via SPIBB while updating λ in the direction of (V̂C(πSPIBB) − ĉ), where V̂C(πSPIBB) is evaluated using the MLE CMDP.
  D.2 RWRL CONTROL TASKS
  Network architecture and hyperparameters We used the ACME framework (Hoffman et al., 2020). For the νθ network and the χφ network, we used LayerNormMLP with hidden sizes of [512, 512, 256]. For the policy network πψ , we used the network architecture used in CRR (Wang et al., 2020). Specifically, we the πψ network consists of 4 ResidualMLP blocks with hidden size of 1024 and a mixture of Gaussians policy head with 5 mixture components. We used the batch size of 1024. We use Adam optimizer with learning rate 3e-4. Similar to ValueDICE (Kostrikov et al., 2021), we additionally adopt gradient penalties (Gulrajani et al., 2017) for the νθ network and the χφ network with coefficient 10e-5. We performed grid search for α ∈ {0.01, 0.05, 0.1} for each domain. We used the following f as in OptiDICE (Lee et al., 2021):
  f(x) = { x log x− x+ 1 if 0 < x < 1 1 2 (x− 1) 2 if x ≥ 1
  Task specification We conduct experiments on domains using the RWRL suite with safety-spec. The safety coefficient is a flag in the RWRL suite with safety-spec, and its value can be between 0.0 and 1.0. Lowering the value of the flag incurs more safety-constraint violation (cost of 1). Originally,
  each domain has multiple types of safety constraints, but we use only one of them, which was the hardest safety constraint to be satisfied by an online constrained RL agent. In summary, we used the following task specifications (safety coefficients, name of the used safety constraint, cost threshold ĉ).
  • Cartpole (realworld-swingup): safety-coeff=0.3, slider pos, ĉ = 0.1, • Walker (realworld-walk): safety-coeff=0.3, joint velocity constraint ĉ = 0.1. • Quadruped (realworld-walk): safety-coeff=0.5, joint angle constraint ĉ = 0.3. • Humanoid (realworld-walk): safety-coeff=0.5, joint angle constraint, ĉ = 0.3.
  The offline dataset consists trajectories of 1000 episodes for Cartpole and Walker, and 5000 episodes for Quadruped and Humanoid.
  C-CRR: Constrained variant of CRR C-CRR additionally introduces the cost critic QC and the Lagrange multiplier λ for the cost constraint. Then, the reward critic and the cost critic are trained by minimizing TD-error for reward and cost respectively. The actor is trained by weighted behaviorcloning: maxπ E(s,a)∼dD [exp(Â(s, a)/β) log π(a|s)] where Â(s, a) = (QR(s, a)− λQC(s, a))− 1 m ∑m j=1(QR(s, a
  j) − λQC(s, aj)), with aj ∼ π(·|s). This corresponds to optimizing the policy with respect to the scalarized reward R− λC. The Lagrange multiplier λ is updated in the direction of (E(s,a)∼dD [QC(s, a)]− ĉ).
sections.heading: E ABLATION EXPERIMENTS ON DIFFERENT COST THRESHOLDS
sections.text: In order to see the sensitivity of the proposed method to different cost thresholds, we conduct ablation experiments on different cost thresholds using randomly generated CMDPs. The experimental setup is identical to the one described in Section 4.1.
  On the same data-collection policy (whose cost value is either 0.09 or 0.11) and the same offline dataset as in Figure 1, we tested each algorithm against different target cost thresholds ĉ ∈ {0.08, 0.09, 0.10, 0.11, 0.12}. Each row in Figure 4 presents the result for each target cost threshold, ranging from ĉ = 0.08 to ĉ = 0.12. Our COptiDICE (blue) shows consistent robustness to constraint violation on varying cost thresholds, while other algorithms fail to meet the constraints especially when the threshold is set to low values (e.g. rows 1 and 2).
sections.heading: F ADDITIONAL EXPERIMENTS USING MIXTURE DATASET
sections.text: In Section 4.1, we demonstrated the results when the offline dataset was collected by a single datacollection policy. However, in real-world situations, it would be common that data-collecting agents act safely in most cases but have some unsafe attempts. To simulate this scenario, we conduct additional experiments on the use of a mixture dataset, where the dataset is collected by both constraintsatisfying and constraint-violating policy.
  Figure 5 presents the result, where the dataset is collected by two policies, the cost-satisfying one (i.e. its cost value is 0.09) and the cost-violating one (i.e. its cost value is 0.11). The overall trend remains the same as in Figure 1 (Figure 5a ≈ Figure 1a, Figure 5b ≈ Figure 1b): when the dataset consists of mostly cost-satisfying trajectories, baseline algorithms exhibits less constraint violation, while they show more constraint violation when the dataset consists of mostly cost-violating ones. Our COptiDICE (blue) still shows much stricter cost satisfaction than other baseline algorithms, demonstrating a better trade-off between reward maximization and constraint satisfaction than baselines.
sections.heading: G DISCUSSION ON THE DATASET COVERAGE ASSUMPTION
sections.text: Although we have made an assumption dD > 0 in Section 3, this is not strictly required for the offline RL algorithm to work in practice. We adopted this assumption same as OptiDICE (Lee et al., 2021) for the simplicity of describing the algorithm derivation from Eq (4-7) to Eq (10): the assumption makes Eq. (10) correspond to solving the underlying true CMDP of Eq. (4-7). If we take this assumption off, Eq. (10) then becomes equivalent to solving the reduced CMDP where the state and action spaces are limited to the support of dD.
  To see this, we consider the following constrained optimization problem, where the optimization variables d(s, a) are defined only for the (s, a) who are within the support of dD. We denote p̂0 and T̂ as the empirical initial state distribution and the empirical transition function respectively.
  max d ∑ (s,a)∈Supp(dD) d(s, a)R(s, a)− αDf (d||dD) (51)
  s.t. ∑
  (s,a)∈Supp(dD) d(s, a)[Ck(s, a)] ≤ ĉk ∀k = 1, . . . ,K∑ a′∈Supp(dD) d(s′, a′) = (1− γ)p̂0(s′) + γ ∑ (s,a)∈Supp(dD) d(s, a)T̂ (s′|s, a) ∀s′ ∈ Supp(dD)
  d(s, a) ≥ 0 ∀s, a ∈ Supp(dD)
  Then, by considering the Lagrangian for (51) and following the similar derivation of Eq. (8-9), we can finally arrive at Eq. (10) without any assumption on the coverage of dD, due to the fact that ∑ (s,a)∈Supp(dD)[d(s, a)(·)] = ∑ (s,a)∈Supp(dD) d D(s, a) d(s,a) dD(s,a) (·) = E(s,a)∼dD [ d(s,a) dD(s,a) (·) ] always holds. In other words, our offline RL algorithms that rely on Eq. (10) essentially solve the reduced CMDP that is limited to the support of dD.
  Furthermore, solving the reduced CMDP is a valid method in the offline RL setting since we may want to optimize the policy only within the dataset support in order to prevent unexpected performance degradation by out-of-distribution actions.