A CMDP-within-online framework for Meta-Safe Reinforcement Learning
Authors: Vanshaj Khattar
Yuhao Ding
Bilgehan Sel
Javad Lavaei
Ming Jin
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Meta-Reinforcement learning
Constrained MDPs
online learning
safe RL
dynamic regret

Abstract: Meta-reinforcement learning has widely been used as a learning-to-learn framework to solve unseen tasks with limited experience. However, the aspect of constraint violations has not been adequately addressed in the existing works, making their application restricted in real-world settings. In this paper, we study the problem of meta-safe reinforcement learning (meta-SRL) through the CMDP-within-online framework. We obtain task-averaged regret guarantees for the reward maximization (optimality gap) and constraint violations using gradient-based meta-learning and show that the task-averaged optimality gap and constraint satisfaction improve with task-similarity in the static environment, or task-relatedness in the changing environment. Several technical challenges arise when making this framework practical while still having strong theoretical guarantees. To address these challenges, we propose a meta-algorithm that performs inexact online learning on the upper bounds of intra-task optimality gap and constraint violations estimated by off-policy stationary distribution corrections. Furthermore, we enable the learning rates to be adapted for every task and extend our approach to settings with the dynamically changing task environments. Finally, experiments are conducted to demonstrate the effectiveness of our approach. The proposed theoretical framework is the first to handle the nonconvexity and stochastic nature of within-task CMDPs, while exploiting inter-task dependency for multi-task safe learning.


Published as a conference paper at ICLR 2023
A CMDP-WITHIN-ONLINN FRAMEWORK FOR META SAFE REINFORCEMENT LEARNING
Vanshaj Khattar Virginia Tech Blacksburg, VA 24061
Yuhao Ding UC Berkeley Berkeley, CA 94709
Bilgehan Sel Virginia Tech Blacksburg, VA 24061 bsel@vt.edu
vansha jkl vt jk@vt. edu
Javad Lavaei
Ming Jin
UC Berkeley Berkeley, CA 94709
Virginia Tech
Blacksburg, VA 24061 j nm ng@vt. edu
lavaei i @berree ey. edu
ABSTRACT
Meta-reinforcemment learning has widely been used as a learning-to-leam framework solve unseen tasks with limited experience. However, the aspect of constraint violations has not been adequately addressed in the existing works, making their application restricted in real-world settings. In this paper, we study the problem of meta-safe reinforcement learning (Meta-SRL) through the -Min--withi--online framework to establish the first provable guarantees in this important setting. We obtain task-averaged regret bounds for the reward maximization (optimality gap) and constraint violations using gradient-baser meta-learning and show that the task- averaged optimality gap and constraint satisfaction improve with task-similarity in a static environment or rask-relassdness in a dynamic environment. Several technical challenges arise when making this framework practical. To this end, we propose a meta-algorithm that performs inexact online learning on the upper bounds of within-tas, optimality gap and constraint violations estimated by off- policy stationary distribution corrections. Furthermore, we enable the learning rates be adapted for every task and extend our approach to settings with a competing dynamically changing oracle. Finally, experiments are conducted to demonstrate the effectiveness of our approach.
INTRODUCTION
The field of meta-reinforcement learning (meta-RL) has recently evolved as one of the promising directions that enables reinforcement learning (RL) agents to learn quickly in dynamically changing environments (Finn et al. 2017 Mitchell et al., 2021 Zintgraf et al.) 2021). Many real-world applications, nevertheless, have safety constraints that should rarely be violated, which existing works do not fully address. Safe RL problems are often modeled as constrained Markov decision processes (CMDPs), where the agent aims to maximize the value function while satisfying given constraints on the trajectory (Altman| 1999). However, unlike meta-lcarning, CMDP algorithms not designed to generalize efficiently over unseen tasks (Paternain et al.) 2022 Ding et al.) 2222 Ding & Lavaei 2022) In this paper, study how meta-learning can be principally designed to help safe RL algorithms adapt quickly while satisfying safety constraints.
There several unique challenges involved in meta-learning for the CMDP settings. First, multiple losses are incurred at each time step, i.e., reward and constraints, which are typically nonconvex and coupled through dynamics. Hence, adapting existing theories developed for stylized settings such as online convex optimization (Hazan et al. 2016) is not straightforward. Second, is unrealistic to assume the computation of globally optimal policy for CMDPs (unlike online learning (Hazan et al. 2016)). Thus, classical online learning algorithms that assume exact or unbiased estimator of the loss
"Corresponding author

---

Published as a conference paper at ICLR 2023
function do not apply (Khodak al. 2019). Overall, there is interplay among nonconvexity, the stochastic nature of the optimization problem, as well as algorithm and generalization considerations, posing significant complexity to leverage inter-task dependency (Denevi al. 2019).
To this end, we propose a provably low-regret online learning framework that extends the current meta-learning algorithms to safe RL settings. Our main contributions are follows:
1. Inexact CMDP-within-onliin framework: We propose a novel CMDP-within-one online framework where the within- task is CMDP, and the meta-learner aims to learn the meta- veta-initialization and learning rate. In our framework, the meta-learner only requires the inexact optimal policies for each within-tas CMDP and the approximate state visitation distributions estimated using collected offline trajectories to construct the upper bounds on the suboptimality gap and constraint violations. An upper bound on these estimation errors is established in Theorem 3.1
2. Task-averaged regret in terms of empirical task-similarity: We show that the task-averaged regrets for optimality gap (TAOG) and constraint violations (TACV) (Def. D diminish with respect to both the number of steps in the within-task algorithm M and the number of tasks T. Specifically,
task-averaged regret of O V E -D3) holds, where Ey is the total inexactness in online learning and D* is the empirical task- (Theorem 3.2).
3. Adapting to a dynamic environment: We adapt the learning rates for each task to envi- ronments that entail dynamically changing meta-initializzaionn policies. An improved rate of for TAOG and TACV are shown, where Vi the empirical
O Ma/AVT ( + E V v+))
fask-relatedness with respect sequence of changing comparator policies {ust >T= (Corollary !
Incorporating all these components makes our Meta-safe RL (Meta-SRL) approach highly practical and theoretically appealing for potential adaption to different RL settings. Furthermore, we remark on some key technical contributions that support the above developments, which may be of independent interest: /) We study the optimization landscape of CMDP (Theorem (.1) that is algorithmic-agosticc 3 and 15] that is restricted to the
which differs from the existing work of (Mei et al., setting of policy gradient. This is achieved by developing new techniques based on tame geometry and subgradient flow systems; 2) we provide static and dynamic regret bounds for inexact online gradient descent (see Appendix Db. which we leverage to obtain our final theoretical results in Theorems 3.2
3.3 and Corollary
Due to the space restrictions, the related work can be found in Appendix A
2
FRAMEWORK
In this section, we introduce the CMDP-within-online framework for the Meta-SRL problems. In this framework, a within task algorithm (such as CRPO (Xu et al. 2021)) for some CMDP task t E [T] encapsulated in an online learning algorithm (meta-learning algorithm), which decides upon sequence of initialization policy o, and learning rate a, > 0 for each within-task algorithm. The goal of the learning algorithm to minimize some notion of task lask-averaged performance regret to facilitate provably efficient adaptation to a new task.
2.1 CMDP AND THE PRIMAL APPROACH
Model. For each task / E [7]. CMDP M, is defined by the state space S, the action space A, discount factor y, initial state distribution over the state-space pt, the transition kernel P (s'|s,, (s||s,ur a)
S S A + S, reward functions ct, : S x AA + [0, 1] and cost functions C, S x A [0, 1 for i= I,.... p. The actions are chosen according to a stochastic policy ग. : S - A(4) where A(A) is
the simplex over the action space. We use ((A)(S) to denote the simplex over all states S. The initial policy for task t is denoted as Te..- The discounted state visitation distribution of policy is defined
as Vi,,0g()) (s) (1 - 7) Im 7hh P. (sm = म, 80) and we write v (s) Espep [v (s)] the visitation distribution when the initial state follows Pt at task t. We denote गद as an optimal policy for task t and (s) := Eegrp 1i.0 (s) is the corresponding state visitation distribution induced by policy कद when the initial state 8o is sampled from initial state distribution Pr at task t.
2

---

Published as a conference paper at ICLR 2023
Policy parametrization. We consider the softmax parametrization. For any 0 RS xIAI, the exp(e(s,a)) corresponding softmax policy we is defined TT(a s) := Ented exp(U(s.a")) V(s,a) E x A. We neglect the dependence on 9 to alleviate the notational burden.
Value function. For task & and a policy TT, we define the state-value function as Vi,
Eg I=== 7 c1, (8ms am, Sm+1) So = s, т] and the action-value function as (i, a) = E. mm= cr, (8m, am, Sm+1) 80 8, An = a, m), where m denotes the time steps. Further- more, the expected total reward/cost functions are JT, = Ep, [V,,, = E [s,,x
CMDP. In each task the goal of the agent is solve the following CMDP problem
max
(TT
s.t. JT,s(T) S de,s. =i=
(1)
where de, is fixed limit on the expected total cost Jr.; for task and constraint i (among total of p constraints). We denote the optimal solution ofr for the task t as n, which can be non-unique.
Primal approach. In this work, we focus on the primal approach, CRPO (Xu et al., 2021] D), as an exemplary algorithm with guarantees for a single-task CMDP. CRPO is primal- based online CMDP algorithm, which performs policy optimization (natural gradient ascent on the reward) when constraints are not violated, or constraint minimization (natural gradient descent on the constraint function) for one of the violated constraints. Specifically, with softmax parametrization and carefully chosen parameters, the suboptimality gap and constraint violation for task t are bounded as follows (if the exact action-valus function {Qi,5 Tho are available for all n
a, Bonuz [DKL (T, [e,0]] + 40,c2 |S|AA
2
Ro = -(,((=;)) - B[Jro(+tt]]
(1-7)s
(2)
2 a.M
R DKL [oo0 (x) + 4arcoma. |S||A|
R₂ = [+)] - d, S
Vi = 1,.,,p
(1 (1- 21)
where tे the policy returned by running CRPO for M steps with learning rate a4 in task t, a is the optimal policy, Craz is the upper bound on reward/cost function, and D-r(-l-) is the KL divergence.
2.2 META-SRL PROBLEM SETUP
We now consider the lifelong extension of CMDPs in which safe RI. tasks arrive one at a time, and t = 1,2,.... T denotes the index for sequence of online learning problems. In each single task t, the agent must sequentially optimize the policy { so that the corresponding sub-optimality and the constraint violation, given in [] decays sub-linearly in M. Beyond the single task, the meta- learner should aim to optimize the upper bounds in over the initial policy Te.0 and the learning rate or so that the task-averaged sub-optimality and constraint violation are expected improve as the meta-learner solves more tasks. Therefore, we will aim to minimize the task-averaged sub-optimality gap and the task-averaged constraint violation defined as follows:
1M
Definition 1. The task-averaged optimality gap (TAOG) Rg and the task-averaged constraint- violation (TACV) R; of a safe RL algorithm after T tasks are
Ro = 1 T
- t=1
-E -[Jao(tt)) R4 -
[[Ja(tt))) des Vi Ii
where tee is the policy returned by running some safe RL algorithm for M time-steps at task where the expectation is taken with respect to the randomness of the algorithu and environment.
We can observe from (2) that the task-averaged regrets can be upper bounded by terms based on the policy initializations { [=r,a]T= and the learning rates (at ) The crux of our idea is to design a meta- aega-algo that can sequentially update the initial policy Te and the learning rate of the CRPO algorithm Oe by performing online learning on the upper bounds, i.e., we consider the right-hand sides of (2) as the individual loss function. This enables us to bound the dynamic regrets (TAOG and TACV), which are measured against dynamic sequence of optimal policies {mī 12" | via the static regret, which is measured against a fixed initial policy Φ.
TTii regret is slightly different from (Xu et al. 2021 as we assume an exact critic estimation for simplicity. For more details about the CRPO algorithm, choice of parameters, and the convergence analysis for a single task, we refer the reader Appendices B and
3

---

Published as a conference paper at ICLR 2023
2.3 FASK-SIMILARITY
In Meta-SRL, we expect TAOG and TACV to improve with the similarity among the online CMDP tasks. We now discuss the notions of similarity in a static environment; an extension to dynamic environment is introduced in Sec. 3.2 Given optimal polices (m] where m E IT for every I, the
lask-similarity can be measured as D
min 7 E Be-r [ [0)] If the optimal (EA(A)IS
policy is not unique, we take the worst case for D i... a set of policies for which D is maximum. This notion of task-similarity in the static environment is natural for studying gradient-base -based meta- learning, as implies that there exists a meta initialization ø with respect to which optimal policies for individual tasks are all close together. In particular, when the tasks are all identical, i.e., { )r are all equal, we have D = O. In the practical scenario where only suboptimal policies are accessible, we denote the empirical mask-similarity as D=2 = min
7 Ei= Es [ (ft which
dEA(A))
depends on the suboptimal policies (ft))=1 returned by a within-task algorithm. As it is desirable that the meta-initialization policy Te.0 has good exploration properties, we need the initial policy to have full support over S x A. We introduce the following assumption:
Assumption 1. The meta- inttaiiiitillizatinn policy Te.0 for any task t lies inside a shrinkage simplex set, i.e., T-,0(-1s) E AA,= == {a1el + ... + On, Cn., Li=o a = a; 2 Q =i= Li for all E S. where Ei,..., Ong E =L. are one-hot vectors for each action (e.g., e1 is the vector of all Os except 1 at the first location) and @ > 0. In particular, Agg lies inside the regular simplex set AA (e 0).
Technically, Assumption]] T is a minimal requirement for the CRPO to provide any guarantees in single task. This can be seen in (2): if T.p does not have full support over the state/action space, then there may be state and action where nt (als)
0 but (alo(a)s) = O, which would make the KL divergence term in (2) infinite. Furthermore, Assumption | eenuures the following
holds for the meta-initialization policy T for any state 8 E S with positive constants Oz., Lug L and Mx: (1) [ {(((ss))) [DKL(fe
S C.; (2) DKI(= (-1s) Te,o(-
Lg-Lipschitz and L.p -soooh in (=,o(=)s); (3) DKI(TT (-[s) [T,o(-ss)) is M4 -trongly convex in
(-s)) We use these conditions in the proof of Lemma Lemma 3 and Theorem 3.2
In this work, we develop algorithms whose TAOG and TACV scale with the task- aask-similarity, which implies that the method will do well if tasks are similar. To understand the CMDP-within-onling framework and the impact of sask-iimilarity on the upper bounds of TAOG and TACV for Meta-SRL, we first present simplified result under the ideal setting where {Mi and {मī ) are available for each task and the task-similarity D²2 is known.
Lemma 1. Assume {vī TT and {-] )T are given after each lask and the task task-similarity D is
known. For each task I, we run CRPO for M iterations with a = (SIA)
(1-7)²
Lg T+1)
+ D=2 neT
In addition, the initialization ) are determined by playing Follow- whwww-theReere -eee--aeieed--aauueee Leader
(FTRL) or online gradient descent (OGD) on the functions Rigwui (DKL. (=tl.)] 111 for 1 1,.... Then, it holds that
(
1
log' T
logT T
Ro SSO
+
D22
+ D22
Vi 1,.
VM
T
VM
The above result reveals an interesting benefit brought by including more tasks (the regret decays at rate of log(T))(T with more similarity (i.e., lower D*), which improves upon single-task guarantee and serves as the initial point of our study. However, there several limitations. First, if the optimal policies πद and the induced state distributions 2i are not revealed after each task, it is not likely that the plug-in estimator (E [DxI (#x >)) with the learned policy म, and estimated visitation distribution ù; is an unbiased estimator, ruling out existing analysis for FTRL or OGD in the bandit setting. Besides, while the knowledge of D* used to determine the learning rate can be relaxed (Khodak et al., [2119) Balcan et al. 2019), the resulting scheme is complex to implement- we expect that the learning rates can be chosen adaptively for different tasks based on losses observed in the past. We aim to address these challenges with a series of developments in the next section.
When online leaming is played on B.-e, B and E A as the decision variable. For simplicity, we will refer as the decision variable.
[Dx (#g [r]] to determine Te+1.0, we treat 0 in for all a S
4

---

Published as a conference paper at ICLR 2023
Algorithm I: Inexact CMDP-within-online framework (exemplified with CRPO (Xu et al. 2021) as the within-task safe RL algorithm)
1: Initialize actor policy 11.0 and learning rate
2: for task E [T] do
3: Run CRPO with initializations for actor policy 7,,0 and learning rates o, to obtain policy f
4: Estimate the discounted state visitation distribution Pr of ãG based on trajectory data collected
within-task & with DuaIDICE (Nachum et al., 2019)
5: Run one or multiple steps of OGD on
(a) INIT: fenst (6) Ee, (+e()))
(b) SIM: ft faim (x) = ci [
K( (ccM + vvMM) + V
to obtain 1,+ and 04+1. Here of = =2, c2
2x2
maz |A -
and ca 36maz
(1-7)*
(1-7
[1-3]²
6: end for
3 PROVABLE GUARANTEES FOR PRACTICAL CMDP-WITHIN-ONLNS FRAMEWORK
3.1 INEXACT HMDDP-WIHIN-ONL.AN FRAMEWORK
One of the key steps to generalize the online-within-on within-onlinn methodology (Balcan et al. 2019) to Meta-SRL is to relax the assumption of accessing the exact upper bounds of within-task performance by designing algorithms estimate and update their inexact versions.
Estimation of upper bounds. Once CMDP task is complete, the meta-learner only has access to suboptimal policy ã and the trajectory dataset D. produced by some safe RL algorithm. Let in denote the discounted state visitation distribution induced by policy ž.. To obtain an estimate ù; from Dr, recent methods often rely on estimating discounted state visitation distribution corrections (Liu iet al. 20118: Gelada & Bellemare 2019). However, the main issues are that D, is collected by multiple behavior policies during the learning period, and depending on how far these behavior policies are from the target policy, the per-step importance ratios involved in these methods may have large variance, which may result detrimental effect on stochastic algorithms. In this work, we use methods from the distribution correction estimation (DICE) family, namely DualDICE (Nachum et al.) 2019), which agnostic to the number of behavior policies used and does not involve any per-step importance ratios, thus is less likely to be affected by their high variance. In particular, for each state- (s.a)
action pair (s, a). the method aims estimate the quantity wx/D, (s, a) (s.a) i.e., the likelihood that the target policy æ will experience the state-action pair normalized by the probability with which the date-action pair appears in the off off-policy data D, Thereby, we estimate Ex; [Dx L (mī (r) with E,, [Dxr z. (fte [=)] by plugging in it, from the within-task CMDP and in from DuaIDICE in lieu of the optimal policy nē and the corresponding discounted state visitation distribution v/"
Bounding the estimation error. We breakdown the error by sources of origin:
Exp (DKL(TT) Es, (KL(((( = B,y [Dxz (N []] - Es, [ (TT [T]
(4)
(A)
E2, ( E,, [Dx (x] + EA, (DkL E, (+.1m,)
(C)
where (A) accounts for the mismatch between the discounted state visitation distributions of an optimal policy गं and suboptimal one ât. (B) originates from the estimation error of DualDICE, and (C) is due to the difference between कł and ît, measured according to म,.
To bound (A), we need to control the distance between vf and it, which can be bounded by the distance between the inducing policy parameters as long they are Lipschitz continuous (Xu et al. 2020 Lemma 3). addition, the bound on (C') also depends on the distance between policies. Controlling the distance between policy to optimal policy based on the suboptimality gap requires the optimization to have some curvatures around the optima (e.g.. Hölderian growth (Johnstone &
Moulin 2020)). However, the best of our knowledge, available results are algorithm-dependee PI.
5

---

Published as a conference paper at ICLR 2023
inequalities for policy gradient (Mei al. 2020)
quadratic growth with entropy regularization
(Ding et al. (2021b). Given some mild assumptions on the objective/constrail functions and policy parametrization, we can show that a growth condition holds broadly for any CMDP problem.
Assumption 2. The functions J.,s(-) for = O, 1...,, P and L E [T) and parametric policy we are definable in some o-minimal structure (Van den Dries Miller 1996).
The definition of "o-minimal structure" is given in Appendix F.1 Assumption 2 is mild as practically all functions from real-world applications, including deep neural networks, are definable in some o-minimal structures. For Assumption to to hold, a sufficient condition requires that the reward and utility functions belong to the same o-minimal structure. We use Assumption to bound the terms (A) and (C") as definable sets admit the property of Whitney stratification, and any stratifiable function enjoys a nonsmooth Kurdyka-Lojasiewice Lojasiewizz inequality, which implies some curvature around the local/giobal minima. Details on tame geometry and proof of Theorem 3.1 is given in Appendix F
Theorem 3.1 (KL divergence estimation error bound). The following bound holds:
[Ru [D ( [r]]
Ex, (fel((]
so
1
+ VEopt /+*VVeanne Eapproz (F, (F, H)) Ex,
VM
where h is strictly increasing continuous function with the property that h(0) = 0 specified in Proposition 7 Capprea (F, , 'H) and Copt are the approximation error and optimization error of DualDICE, defined in Equation 38 and Equation 33 respectively.
Remark 1. We define cumulative inexactness ET = ET= Et. This quantity decays with M
rate of O (n + up to some approximation and optimization errors Capprox and Copt- Moreover, there is trade-off belween Eappron und topt: if the purametrization functions F and H used to solve DualDICE optimization are chosen as neural networks, then capprox can be reduced at the cost of increasing Copt. If we stochastic gradient descent as optimization algorithm in DualDICE with K steps, then Eopt decays at a rate of (1/K). Note that h is a definable function used in the Sordyka-Lojasiewicc (KL) inequality (see, e.g., (Bolte et al. 2007 Thm. 14)).
With the above uniform bound on estimation error, our next step is to develop static regret bounds for the inexact online gradient descent, which are used to furnish the upper bounds TAOG and TACV of the proposed inexact HLDD--wthin-om
algorithm.
Lemma 2 (Static regret bound for inexact OGD). Denote fe( = Eug Duz ( for all t E [T]. For any fixed comparator म = arg min ΣL f((TT). if OGD is run on a sequence of T.E
loss functions (feheery where f((mr.)) = EE, (f Te,o)) for all i E [T] with the step-size of OLL/VT), then the following bound holds for static regret:
T s (o(m))s(VTTE)))
1=1
E=1
where ET == Ete E2 is the cumulative inexactness, and e is the upper bound from Theorem 3.1
The static regret analyzed above is defined with respect to the optimal initial policy Tō in hindsight, not the final learned policy. A static regret with respect an initial policy provides freedom for the safe RL algorithm to adapt the initial policy based on observations within the task. Once the static regret for the inexact OGD is established, we can obtain the upper bounds on TAOG and TACV for the proposed inexact HMDP-within-online algorithm in terms of the empirical task lask-similarity Dr.
for M iterations with =0 ( (MM V + + D and we obtain (v. and { YT= In addition, the initialization { T for each task are determined by playing inexact OGD (Algorithm) 2 on E,, [Dxt ( for t = 1,... T. Then, the following holds for TAOG (i 0) and TACV (i p):
Theorem 3.2. For each task t,
1 VT
+ & + Dr22 )r2a)
R S O
=i= 0,.......
VM
V
T
6

---

Published as a conference paper at ICLR 2023
The benefit of task-similarity is preserved when we perform directly on the plug-in estimator Eg, [DeL (fel-)]. though we incur an additional cost on the inexactness Er and the dependence on I' is worse compared to Lemma []] As / diminishes when the learned policy becomes optimal across tasks, e.g., by increasing within-task steps M or meta-initialization is chosen such that a few steps suffice to reach optimal, we expect the inexactness have limited effect on the performance.
3.2 DYNAMIC REGRET AND TASK- RELATEDNESS
In many settings, we have a changing environment, so it is natural to study dynamic regret and compare with sequence of potentially time-varying initial policies (wi) To mea- sure task-similarity in this case, we define task-relatedness which can be measured by V2
T E/=1 Es [DxL (Tī) (.. This notion of mask-relatedness gives the measure of how far optimal policies are in each task from some time- tie-varying comparator. We denote empirical task-relatedness as 1/2 = + Es-e, k @ (v)) )}. which depends on the suboptimal policy returned by the within-task algorithm. To measure the performance of Meta-SRe SRL in dynamic settings, we analyze the dynamic regret bound, i.e., Ur == Σ S(((t) E Se(1)), where 1/ E arg min (xr) is a sequence of minimizers for each loss, and fc(-) = Eswn; [= By exploiting the strong convexity of the loss function (KL divergence in our case), previous studies have shown that the dynamic regret can be upper bounded by the path- of the comparator sequence, defined as PT Ei= | - ll. which captures the cumulative difference between successive compara- tors (Zhao et al., 2020p. The bound can be further improved for strongly convex functions as the
1
minimum of the path-length and the squared path-length, ST == Ein |I -/2111 which can be much smaller than the path-length (Zhang et al. 2017). We extend these results to the settings of inexact online gradient descent by allowing the learner to query the inexact gradient of the function. Lemma 3 (Dynamic regret bound for inexact OGD). Denote fe(0t) = =Eug (D ( (é))))l for all t E (T.. For any dynamically varying comparator v, if single-step inexact OGD is run with the step-size B S 2n1 on a sequence of loss functions {fe where f(((t) = Ez, (DKL (x)) then the following bound holds for dynamic regret:
T
T
Σ IMde
Ei(AE S 5 (min(8r + Er, Pr &
1=1
1=1
where Pr= == Et 10 - 1i- is the path-length of the comparator sequence, ST == Et= 1Iv
-i=ill= is the squared path-length, ET == Ei= et is the cumulative inexaciness, ET is the cumulative square root of inexactness, and 6 is the upper from Theorem 3.1
Ver
3.3 DYNAMIC REGRET WITH ADAPTIVE LEARNING RATES
can be observed from the last section that to set the learning rate at for the within-task algorithm CRPO, knowledge of optimal/suboptmmal policies from all T'' tasks is used. This makes the algorithm less applicable in online settings where tasks
encountered sequentially. Moreover, when the ees--environment changes dynamically, a fixed policy initialization v! may not be the best candidate comparator, where it natural to study dynamic regret by competing with a potentially time-vary varying sequence (v/ [T Also, the tasks may share some common aspects of the optimization landscape, so adapting learning rates based on prior experience may further improve performance. This the direction we pursue. Recall the regret for suboptimality and constraint violation of the CRPO:
ci Ruwny [DKL(T; [m.,))] + ar(c + c + CMMM,
Ue(Te,, 04) =
at where the constants (c] are given in Algorithm 1 We assume that Or E A == (az aa 2 2 for some ( > O, where A is a convex set. Overall, the goal of the meta-learner is to make sequence of decisions, collected by 2; = { E AA! aa E A}. such that TAOG and TACV are minimized.
To design the adaptive algorithm, over initial policy o. fi finit (o) = E,; (Tpl and learning rate K.
consider the following two parallel sequences of loss functions
guim (n) = ef Ey; (D (Tī [T.))
K n( M + clMM) + + cgVM.

---

Published as a conference paper at ICLR 2023
Note that ftnm(a = (F(TT,,, a.) matches the upper bound in We also denote the inexact versions ft finse (() and ft frim (x) by replacing Byy [DxL (TT (6)] with Es, P (ft [6)] the above. Inspired by (Khodak al. 2019) instead of running one online algorithm on Ug (Tt, will run two online algorithms separately for the function sequences finstt and fe by taking actions on the initial policy and learning rates, respectively, such that the overall regret can be bounded by an expression that depends on the regrets for each sequence. Let INIT and SIM be two algorithms, such that the actions 1,0 = [t) are taken over fimit and the actions 0++1 = (tM(t) are taken over ft feim; these actions will then be used as policy initialization and learning rates for the CMDP. We assume the following regret upper bounds for each algorithm
1. Ut (t MEz): upper bound on the dynamic regret for INIT over functions {finit 1T with respect to time-varying sequence {
Ji=1
2. Uf"" (w:): upper bound on the static regret for STM over functions (feim) J with respect to a comparator k >> 0.
Theorem 3.3. Let each within-task CMDP run M steps of CRPO, initialized by policy ne.0 = (t) and learning rates O = SIM((). Let K² = arg min L(R)) where
L(x) = U (n) U.mist ((1))=)
Er
Pinit (vi) + frate (1))
state(())
+
(6)
K
K
R
and [W is any comparator sequence. Then, the following bounds on TAOG and TACV hold:
L(ne)
R. S T
Vi= O....p
Note that the terms Uf and Un are simply placeholders for upper bounds on the respective regrets for some inexact online algorithms. particular, INIT and SIM can be any inexact online algorithms in Algorithm
| and the results of Theorem 3.3 can be instantiated by plugging in the respective U Usmit and Uni The following corollary presents the TAOG, and TACV regret bounds when INIT and SIM are inexact OGD over the loss functions (f It=1 and {frim] )T_1 respectively.
Corollary 1. IfINIT(t) and SIM(t) are inexact OGD, and are run over the sequences { fiiitt Te= and { frim 1T
IE=1 then, the following bounds on TAOG and TACV hold all i = ......pP
1 VM
ET TVM
min(Sr + Er, Ex) + & + v2
Rd 50
+
VMT
MI/VT
T
(8)
Remark 2. The bounds are improved in terms of M and T due to the adaptive learning rate. Specifi-
cally, the bounds diminish at a rate O (11 (ET /4 +Vz) as compared to the previous rate O (wM (V²++
MT
Note that V. is same D in the case of fixed comparator ei"
Moreover, a practical aspect of our algorithm is that it does not require the knowledge of quantities like ST, Pr and &r to decide the value of learning rate oz-
EXPERIMENTS
In this section, we show the effectiveness of the proposed Meta-SRL framework and compare it with the following baselines: simple averaging (i.e., initialize with the average of learned policies from past CMDPs), pre-trained (i.e., initialize test task with the suboptimal policy from another CMDP), Follow the Average Leader (FAL), and random initialization strategies. Note that simple averaging takes the average of previous suboptimal policies obtained from random initializations on all CMDP tasks, while FAL does this in online manner while tasks arrive sequentially. Different CMDPs are
Whiile we run the online learning algorithm on the inexact versions of the loss (f. (T,) regret is the standard measured using the exact losses: Ur Σr, fe(we) - Σr_ fe())).
, the dynamic/static
8

---

Published as a conference paper at ICLR 2023
Frozen lake performance
Froze lake constraint violation
1.75
Mete-SRL
FAL
1.50
Pre-trained
0.8-
Random intialization
Reward
Simple averaging
1.00
Cost
0.50
0.25
0.2
Number of steps
Number of steps
Figure 1: Frozen lake results for reward maximization and constraint violations when the task- relatedness is low. The Blue dashed line represents the averaged thresholds for the constraint violations. We do 10 runs on each baseline to get the performance plots with variance.
Parformance
Constra
Acrobot Constraint
200
Mota: SRL
175
Pre-trained
Simple Averaging
Random Initalization
-1099
Number of stops
Number steps
Number of steps
Figure Acrobot results for reward maximization and constraint violations when the task-relatedness is low. Blue dashed line represents the averaged thresholds for the constraint violations.
generated using probability distribution over the parameters of CMDPs (e.g., rewards, transition dynamics), similar to the latent CMDP model (Chen et al.) 202 consider the Frozen lake, acrobot, half-Cheetah, and humanoid environments from the OpenAl gym (Brockman et al. 2016) and MuJoco Todorov et al. (2012) under constrained settings. For more details on experimental setups, distribution shift, and extra experiments Mujoco, please refer to Appendix H
We can observe from Figure I that Meta-SRL achieves higher rewards and lower constraint violations more quickly than bascline initializations. The baseline FAL which simply takes the average of previous suboptimal policies, performs poorly. This illustrates the benefit of incorporating stationary distribution correction estimation and adaptive learning rates. Indeed, for Frozen lake, different locations of the hole can result in different stationary distributions-il is more sensible to put higher weights on policies that frequently visit a particular state since it implies that the corresponding strategies can have substantial impact on the case of low task-similarity conditions. We also observe similar trends for the Acrobot in Figure 2 where Meta-SRL achieves higher rewards quickly and zero constraint violations as compared to other baseline initializations under low task-relatedness settings. The pre-trained baseline was able achieve higher rewards but did not achieve constraint satisfaction for both constraints. Under high task-similarity settings, we expected all the methods (except vanilla CRPO) to perform well; however, we noticed that simple averaging does poorly even in this setting, possibly due to adverse interference among different tasks.
CONCLUSION AND FUTURE DIRECTIONS
We introduced novel framework. Meta-SRL, for meta-learning over CMDPs. The proposed frame- work does not assume access to globally optimal policies from the training tasks, and instead performs online learning over inexact within-task bounds estimated by stationary distribution correction. More- over, strategies for learning rate adaptation are designed to further exploit task-relatedness. One limitation of the proposed method is that it only considers CRPO the within-task algorithm; nevertheless, our framework can be potentially adapted to more single-task algorithms by making the initial policy/step sizes explicit. Some potential future directions could
dependence of guarantees be to design Meta-SRL with zero constraint violation (Liu et al., 20216), non-stationary environments
(Ding & Lavaei 2022). and multi-agent settings (De Nijs et al.
2021

---

Published as a conference paper at ICLR 2023
6 BROADER IMPACT STATEMENTS
There is an increasing need to address fairness as constraint in learning settings. Existing works that aim achieve zero-shot generalization without any task-specific adaptation have limited capability to adapt to shifting environments. While online meta-learning is principled technique to learn good priors over model parameters for fast adaptation in a sequential setting, existing methods often do not address constraints and thus have limited applications in fairness-awaee learning.
The proposed MADD-within-onliig framework can potentially be adapted to reinforcement learning tasks with fairness constraints in non-stationary environment. In practice, this can provide a strategy that learns priors over policy parameters not only to master the current fairness-aware task but also to become proficient with quick adaptation at learning newly arrived tasks. Our theoretical analysis can be leveraged to provide a sublinear bound on the "task-averaged fairness violation" regret. Similar ideas have been explored by (Zhao al., 2021) in the supervised learning setting, while we are not aware of any work on the reinforcement learning counterpart, Thus, can be an extension for future work explore the extent which our method can address this important problem.Nevertheeee settings, as fairness constraints should rarely violated in a real-world setting due to the implicated discrimination or bias. Additional efforts, such as incorporating pessimism |Bai et al. (2021) or developing offline methods, may be entailed reduce fairness violations during initial deployment.
fairness constraints present unique challenge for meta-safe RL
7 ACKNOWLEDGMENTS
The authors acknowledge the generous support by NSF, the Commonwealth Cyber Initiative (CCT), 4-VA collaborative research grant, C3.ai Digital Transformation Institute, and the U.S. Department of Energy. We would also like to thank the anonymous reviewers, which helped us to improve the quality the manuscript and Tengyu Xu for providing the code for CRPO.
REFERENCES
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International Conference on Machine Learning (ICML), pp. 22-31. PMLR, 2017.
Eitan Altman. Constrained Markov decision processes: stochastic modeling. Routledge, 1999.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference Machine Learning, pp. 322-332. PMLR, 2019.
Peter Auer, Nicolo Cesa Desa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-255 2002.
Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach. arXiv preprint arXiv:2 109.06339 2021.
Maria-Florin Balcan, Avrim Blum, and Santosh Vempala. Efficient representations for lifelong learning and autoencoding. In Conference on Learning Theory, pp. 191-210. PMLR, 2015.
Maria-Florina Balcan, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees for gradient- based meta-learning. In International Conference on Machine Learning, pp.
PMLR, 2019.
Maria-Florina F Balcan, Mikhail Khodak, Dravyansh Sharma, and Ameet Talwalkar. Learning- to-lear non-convex piecewise-lipschiie functions. Advances in Neural Information Processing Systems, 34, 2021.
Amrit Singh Bedi, Paban Sarma, and Ketan Rajawat. Tracking moving agents via inexact online gradient descent algorithm. IEEE Journal of Selected Topics in Signal Processing, 12(1):202-2) 217, 2018.
10

---

Published as a conference paper at ICLR 2023
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations research, 6365)1122-12244, 2015.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. Conference on learning theory, pp. 1691-1692.
PMLR, 2018.
Shalabh Bhatnagar and Lakshmanan. An online actor-critic algorithm with function approximation for constrained markov decision processes. Journal of Optimization Theory and Applications, 153 (3):688-708, 2012.
Jérôme Bolte, Aris Daniilidis, Adrian Lewis, and Masahiro Shiota. Clarke subgradients of stratifiable functions, SIAM Journal on Optimization, 18(2):556-57,, 2007.
Jérôme Bolte, Aris Daniilidis, Olivier Ley, and Laurent Mazet. Characterizations of tojasiewicz inequalities: subgradient flows. talweg, convexity. Transactions of the American Mathematical Society, 362(6) 2010.
Vivek S Borkar. An actor-critic algorithm for constrained markov decision processes. Systems & control letters, 54(3):207-233, 2005.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. OpenAl gym, arXiv preprint arXiv: 2016.
Nicolo Resa-Bianchi, Shai Shalev-Shwartz, and Ohad Shamir. Online learning of noisy data. IEEE Transactions on Information Theory, 57(12):907-7731, 2011.
Xiaoyu Chen, Jiachen Hu, Chi Jin, Lihong Li, and Liwei Wang. Understanding domain randomization for sim-to-real transfer. arXiv preprint arXiv:2110.032.38 2021a.
Yi Chen, Jing Dong, and Zhaoran Wang. A primal-dual approach constrained markov decision processes. arXiv preprint arXiv:2101.10895 2021b.
Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained reinforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 18(1):6070-611 2017.
Yinlam Chow, Ofir Nachum, Edgar A Duéñez-Guzmán, and Mohammad Ghavamzadeh. Lyapunov- based approach safe reinforcement learning. In Advances in Neural Information Processing Systems, 2018.
Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D Lee. Stochastic subgradient method converges on tame functions. Foundations of computational mathematics, 20(1): 19-154, 2020.
Frits De Nijs, Erwin Walraven, Mathijs De Weerdt, and Matthijs Spaan. Constrained multiagent markov decision processes: A taxonomy of problems and algorithms. Journal of Artificial Intelligence Research, 70:955-1001, 2021.
Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Borming-to-leane stochas- tic gradient descent with biased regularization. International Conference on Machine Learning, pp. 1566-1575. PMLR, 2019.
Dongsheng Ding, Xiaohan Wei, Zhuoran Yang. Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. In International Conference Artificial Intelligence and Staristics, pp. 3304-3312. PMLR, 2021a.
Yuhao Ding and Javad Lavaci. Provably efficient primal-dus dual reinforcement learning for CMDPs with non- sta--tationary objectives and constraints. arXiv preprint arXiv:2201.11965 2022.
Yuhao Ding, Junzi Zhang, and Javad Lavaei. Beyond exact gradients: Convergence of stochastic soft-max policy gradient methods with entropy regularization. arXiv preprint 110.1721 2021b.
11

---

Published as a conference paper at ICLR 2023
Rishabh Dixit, Amrit Singh Bedi, Ruchi Tripathi, and Ketan Rajawat. Online learning with inexact proximal online gradient descent algorithms. IEEE Transactions on Signal Processing. 67(5): 1338-1352, 2019.
Dmitriy Drusvyatskiy and Adrian Lewis. Error bounds, quadratic growth, and linear convergence of proximal methods. Mathematics of Operations Research, 43(3):919-945) 2018.
Simon Shaolei Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. In International Conference on Learning Representations, 2020.
Yan Duan, John Schulman, Xi Chen, Peter L Bartlett, Ilya Sutskever, and Pieter Abbeel. RL:: Fast reinforcement learning via slow reinforcement learning. arXiv preprint arXiv:1611.02779, 2016.
Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optinng off off-po evaluation with linear function approximation. In International Conference on Machine Learning, pp. 2701-2709. PMLR, 2020.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploiatioo in constrained MDPs.
arXiv preprint arXiv:2003.02/89, 2020.
Alireza Fallah, Kristian Georgiev, Aryan Mokhtari, and Asuman Ozdaglar. On the convergence theory of debiased model-agnostic meta-reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
Jianqing Fan, Cong Ma, and Yiqiao Zhong. A selective overview of deep learning. Statistical science: review journal of the Institute of Mathematical Statistics, 36(2):264, 2021.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. International conference on machine learning, pp. 1126-1135. PMLR, 2017.
Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online meta-lcarning, In International Conference Machine Learning, pp. 1920-19300 PMLR, 2019.
Javier Gareia and Fernando Fernández. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(1):1437-1480, 2015.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision processes. In International Conference on Machine Learning, pp. 2160-2169, PMLR, 2019.
Carles Gelada and Marc G Bellemare. Off-policy deep reinforcement learning by bootstrapping the covariate shift. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3647-3655, 2019.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimiza- fion, 233-4):1573255, 2016.
Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey. Meta-learning in neural networks: A survey, arXiv preprint arXiv:2004.05439, 2020.
Alexander loffe. An invitation to tame optimization. SIAM Journal on Optimization, 19(4): 1894-1917, 2009.
Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimization: Competing with dynamic comparators. In Artificial Intelligence and Statistics, pp. 398-406.
PMLR. 2015.
Max Jaderberg, Wojciech M Czarnecki, lain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari S Morcos, Avraham Ruderman, al. Human- level performance in 3d multiplayer games with population-basse reinforcement learning. Science, 36416443):859-865 2019.
HU Jean-Bape -antttatiste.. Convex analysis and minimization algorithms: advanced theory and bundle methods, 2010.
12

---

Published as a conference paper at ICLR 2023
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Theoretical convergence of step model-agnostic meta-learning. Journal of Machine Learning Research, 23(29):1-41, 2022.
Patrick R Johnstone and Pierre Moulin. Faster subgradient methods for functions with hölderian growth. Mathematical Programming, 180(1):417-450, 2020.
Mikhail Khodak, Maria-Florina F Balcan, and Ameet $ Talwalkar. Adaptive gradient- based meta- learning methods. Advances in Neural Information Processing Systems, 32, 2019.
Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. RL for latent MDPs: Regret guarantees and a lower bound. Advances in Neural Information Processing Systems, 34, 2021.
Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In Interna- tional Conference on Machine Learning, pp. 3703-3712. PMLR, 2019.
Jongmin Lee, Wonseok Jeon, Byungjun Lee, Joelle Pineau, and Kee-Eung Kim. Optidice: Offline policy optimization via stationary distribution correction estimation. In International Conference on Machine Learning, pp. 6120-6130. PMLR, 2021.
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathemat- ical Soc., 2017.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. Advances Neural Information Processing Systems, 31, 2018.
Zhenguo Li, Fengwei Zhou, Fei Chen, and Hang Li. Meta-SGD: Learning to learn quickly for few-shot learning. arXiv preprint arXiv: 1707v0/777..98..00 2017.
Hao Liu, Richard Socher, and Caiming Xiong. Taming maml: Efficient unbiased meta-reinforcement
learning. In International conference on machine learning, pp. 4061-4071. PMLR, 2019.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off-policy estimation. Advances Neural Information Processing Systems, 31, 2018.
Tao Liu, Ruida Zhou, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Learning policies with zero bounded constraint violation for constrained MDPs. Advances in Neural Information Processing Systems, 34, 2021a.
Tao Liu, Ruida Zhou, Dileep Kalathil, PR Kumar, and Chao Tian. Fast global convergence of policy optimization for constrained MDPs. arXiv preprint 1.X0522111.0055,, 2021b.
Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81):1-32, 2016.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pp. 6820-6829. PMLR, 2020.
Eric Mitchell, Rafael Rafailov, Xue Bin Peng, Sergey Levine, and Chelsea Finn. Offline meta- reinforcement learning with advantage weighting. In International Conference on Machine Learning, pp. 7780-7791. PMLR, 2021.
Aryan Mokhtari, Shahin Shahrampour, Ali Jadbabaie, and Alejandro Ribeiro. Online optimization in dynamic environments: Improved regret rates for strongly convex problems. In 2016 IEFE 55th Conference on Decision and Control, pp. 7195-7201. IEEE, 2016.
Ofir Nachum, Yinlam Chow, Bo Dai. and Lihong Li. Dualdice: Behavior agnosiic estimation of discounted stationary distribution corrections. Advances Neural Information Processing Systems, 32, 2019.
Behnam Neyshabur, Zhiyuan Li. Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards un- derstanding the role of over paraamartttiinnnoonnn in generalization of neural networks. International Conference Learning Representations (ICLR), 2019.
13

---

Published as a conference paper at ICLR 2023
Santiago Patermain, Miguel Calvo-Fullana, Luiz FO Chamon, and Alejandro Ribeiro. Safe policies for reinforcement learning via primal-dual methods. IEEE Transactions on Automatic Control, 2022.
Alon Resler and Yishay Mansour. Adversarial online learning with noise. In International Conference Machine Learning, pp- 5429-5437. PMLR, 2019.
Jonas Rothfuss, Dennis Lee, Ignasi Clavera, Tamim Asfour, and Pieter Abbeel. Promp: Proximal meta-policy search. arXiv preprini arXiv:1810.06788. 2018.
Xingyou Song, Wenbo Gao, Yuxiang Yang, Krzysztof Choromanski, Aldo Pacchiano, and Yunhao
Tang. Es-maml: Simple hessian-free meta learning. arXiv preprint 190iv1111..0125,, 2019.
Marnix Suilen, Thiago D Simão, Nils Jansen, and David Parker. Robust anytime learning of markov decision processes. arXiv preprint rrXiv:2205.15827 2022.
Guy Tennenholtz, Uri Shalit, and Shie Mannor. Off-po evaluation in partially observable en- vironments. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 10276-10283, 2020.
Philip S Thomas, Joelle Pineau, Romain Laroche, et al. Multi-objective spibb: Seldonian offline policy improvement with safety constraints in finite MDPs. Advances in Neural Information Processing Systems, 34, 2021.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033. IEEE, 2012.
Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory transfer learning: The importance of task diversity. Advances in Neural Information Processing Systems, 0177852-78622 2020.
Eiji Uchibe and Kenji Doya. Constrained reinforcement learning from intrinsic and extrinsic rewards. In 2007 IEEE 6th International Conference on Development and Learning, pp. 163-168. IEEE, 2007.
Lou Van den Dries and Chris Miller. Geometric categories and o-minimal structures. Duke Mathe- matical Journal, 84(2):9975540, 1996.
Runzhe Wu, Yufeng Zhang, Zhuoran Yang, and Zhaoran Wang. Offline constrained multi-objective reinforcement learning via pessimistic dual value iteration. Advances in Neural Information Processing Systems, 34, 2021.
Tengyu Xu, Zhe Wang, and Yingbin Liang. Improving sample complexity bounds for (natural) actor-critic algorithms. Advances in Neural Information Processing Systems, 33:4358 4369, 2020.
Tengyu Xu, Yingbin Liang, and Guanghui Lan. Crpo: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, pp- 11480-11491. PMLR, 2021.
Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. In International Conference Machine Learning, pp. 449-457. PMLR, 2016.
Donghao Ying, Yuhao Ding, and Javad Lavaei. A dual approach to constrained markov decision processes with entropy regularization. 25th International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
Kenny Young, Baoxiang Wang, and Matthew E Taylor. Metatrace: Online step-size tuning by meta-gradient descent for reinforcement learning control. arXiv preprint hao.:::800055//4/ 2018.
Ming Yu, Zhuoran Yang, Mladen Kolar, and Zhaoran Wang. Convergent policy optimization for safe reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
14

---

Published as a conference paper at ICLR 2023
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Lijun Zhang, Tianbao Yang, Jinfeng Yi, Rong Jin, and Zhi-Hua Zhou. Improved dynamic regret for non-degenerate functions. Advances in Neural Information Processing Systems, 30, 2017.
Chen Zhao, Feng Chen, and Bhavani Thuraisingham. Fairness-aware online meta-learning. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp- 2021.
Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. Advances in Neural Information Processing Systems, 33:tmms,33:15555 13:12510-12520, 2020.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pp. 928-936, 2003.
Luisa M Zintgraf, Leo Feng. Cong Lu, Maximilian Igl, Kristian Hartikainen, Katja Hofmann, and Shimon Whiteson. Exploration approximate hyper-state space for meta reinforcement learning. In International Conference on Machine Learning, pp. 12991-13001. PMLR, 2021.
Difan Zou, Yuan Cao. Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint arXiv: 18/ 1.08888, 2018.
15

---

Published as a conference paper at ICLR 2023
APPENDIX
In this section, we start with a summary of related work in Sec. followwed by brief recapitulation of the CRPO algorithm in Sec. B Note that CRPO will be our focus as the exemplary within-task safe RL algorithm. We also introduce notations therein that will be used in later analysis. In Sec. C algorithm, with further discussions on key aspects. Sec. provides the proof for Sec. of the main paper, which focuses on an elementary yet illustrative example of the CHOD--wihin-oniing approach. We start by providing simplified proof to help the reader understand the main approach of CRPO, and then demonstrate the potential improvement by exploiting in extending online learning approaches, specifically online gradient descent, to the case of inexact loss functions. We start with some preliminaries e-subgradient (Sec. E.I. Then, we conduct
we give the pseudo-code of our inexact
serr--tt----eeetdeee (Lemma 5). Sec. contains the key developments
the analysis for static regret (Thm. E. and dynamic regret (Thm. E.3 In Sec. F we provide detailed analysis of the KI, divergence estimation error bound, which contributes one of our main contributions in understanding the key aspects of the proposed inexact CMDP-within-oniee framework. Our development leverages the seminal results developed for tame geometry, which we briefly review in Sec. F.T We also briefly set up the notations and recall basic properties of subgradient flow systems Through a series of bounds, the final result obtained in Thm. [..
We then provide proofs for Sec. 3.3 In Sec. I.I. we first extend the analysis of CRPO to the case
of adaptive learning rates. Then, we provide the proof for Thm. 3.3 and Corollary | in Sec. G.2 Experimental details are provided in Sec. H Frequently used notations and constants are listed in Sec
A RELATED WORK
Meta-reinforcemenn learning: Current state-of-the-art meta-RI. includes learning the initial condi- tions (Finn et al., 20.7). hyperparameters (Jaderberg et al. 2019), step directions (Li et al.) (017) and stepsizes ( (Young et al., 20188), and training recurrent neural networks to embed previous task experience (Duan et al. 2016) (see also (Chen et al. 202 la) for sim-to-real transfer, and Suilen et al. (2022) for the extension to robust MDPs), with recent developments on improving meta- mnta-optimization (Rothfuss et al. 20188) Liu et al. 2019 Song et al. 2019) (see (Hospedales et al., (020) for a review). Recently, (Fallah et al. [021]] Ji et al.] 2022) provided theoretical studies on the convergence of model-agnostic meta-RL. RL. However, these works all focus on the unconstrained meta-RL. and their local optimality convergence, while our work is the first to obtain provable guarantees for optimality
and constraint satisfaction for CMDPs.
Online metaa/eerninnnlleennnn-----eeee
(LTL). Most initialization based meta- meta-learning studies focus on the setting with decomposable within-task loss functions that are often convex (Finn et al.,
2019 Denevi et al. 2019 Balcan et al. 2019); nonconvex within-tass settings are studied usually for multi-task representation learning (Balcan et al. 2013) Maurer et al., 2016 Du et al. 2020
Tripuraneni et al. 2020). Theoretically, our work is inspired by the Average Regret-Upper--Be Upper-Bound
Analysis (ARUBA) strategy (Khodak et al.) 2019) for obtaining meta-proceduree, which has been recently extended to learning nonconvex piccewise-Lipschie functions (Balcan et al. [02T]): the main technical advance in our work is in providing the guarantees for CMDPs. which is challenging due to the interplay between the nonconvexity and stochasticity of the optimization and the complexity of the within-task safe RL algorithms that involve policy update, critic learning, and the proper choice of stepsizes for reward/constraints.
Inexact online learning. Online learning with access to inexact loss/gradient information has been studied for stochastic zero-biased noise (Cesa- (Cesa-Bianchi et al. 2011 Yang et al. 2016 Bedi et al. 2018. Dixit et al.) 2019), deterministic error/nonzero-
stochastic noise (Bedi et al. 2018 Dixit et al. 2019), and adversarial perturbation (Resler & Mansour (019). Our analysis for static regret uses the formalism of e-subgradient (Jean-Baptiste 2010 Chap. XI); for dynamic regret, we extend the work (Zhang et al. 2017) to the inexact setting allowing multiple updates per round and provide improved rates than prior results (Bedi et al.) 2018 Dixit et al. 2019).
safe RL and CMDP. Direct policy search methods have had substantial empirical successes in solving CMDPs (Borkar 2005 [Chhbe & Doya 2007 [Bhatnagar & Lakshmanan 2012) Achiam
et al. 2017
Chow al. 2017 (see, e.g., (Garcıa & Fernández 2015) for survey of safe RL).
16

---

Published as a conference paper at ICLR 2023
Recently, major progress in understanding the theoretical nonasymptotic global convergence behavior of policy-based methods for CMDPs has also been achieved (Chow et al. 2018 Paternain et al.
2022; Efroni al. 2020; Ding al.
2021a Ding & Lavaei 2022 Ying al. [002]] Yu et a 2019
eu et al. 2021 Chen et al. 2021b Liu et al. 2021b a). However, most of these works only study
single CMDP task and don't seek to make the algorithm perform well on new, potentially related
CMDP tasks. In addition, while our work uses the constraint-rectiffed policy optimization (CRPO) algorithm proposed in (Xu et al. 202T as building block, our framework can be potentially adapted to most of the existing RL literature by making the dependence of guarantees on initial policy/step
sizes explicit, e.g., safe exploration (Efroni et al. 2020). regularization (Geist al. 2019), off off-policy
evaluation (Duan et al. [0200] Tennenholtz et al. 20220) and offline RL under constraints (Le et al.
2019
Wu et al. 2021
Lee al. 2021 Thomas et al. 2021
B CRPO ALGORITHM AND NOTATIONS
We provide some preliminaries and notations for the CRPO algorithm for the sake of completeness. CRPO (Xu et al. 2021) is a primal-hased CMDP algorithm, which performs policy optimization (natural gradient ascent on the reward) when constraints are not violated, or constraint minimization (natural gradient descent on the constraint function) for the corresponding violated constraint. There are three crucial components the overall strategy solve the CMDP problem]]
1. Policy evaluation: In each step m of task t, for certain policy Tt.m. the action-value functions Qi are estimated for the reward (i = 0) and constraints (i 1,.., TD- learning is employed for critic evaluation (Bhandari et al. 2018).
2. Estimation of constraint violation: Once the Qeestimates Qi. (s. a) are obtained, then a weighted average is taken to estimate expected constraint violation (T. under a given policy Tr,m.
3. Policy optimization: After the constraint estimation, it is checked if the expected constraint violation Jr. J..m... exceeds the given safety threshold, i.e., if (T, S de,; + 7t for all = 1, ... p. If none of the constraints are violated, then one step of natural policy gradient ascent is performed to maximize the objective. If one or more constraints are violated, then one step of natural policy gradient descent conducted to minimize one of the unsatisfied constraints.
The set of time steps the policy optimization for reward maximization takes place is denoted by Ni and the set of time steps constraint minimization takes place is denoted by Ne.s. Thus [Nr En a = M for any task
C INEXACT CMDP WITHIN-ONLINN ALGORITHM
Algorithm| I presents the inexact-CMDP- Www.--Mttii--ooiniiiiieiie within-online algorithm for Meta-SRL. The first step in the algorithm is to initialize with some random actor policy 6), and the learning rate for the first task. Then, for each task f, within-task algorithm (i.e., CRPO) is run for M steps to obtain a policy ît. The discounted state visitation distribution in induced by n is then estimated using the trajectory data collected within task 4. Afterward, an inexact OGD method run on the new loss functions to update the meta-initialization policy dr+1, and the learning rate 01+11 The online learning loop is iterated for all tasks E [T].
D PROOF IN SECTION 2
We first present simplified proof for the results in Equation 2 This result also shows in 9 how the safety threshold nhe can be chosen to achieve sublinear convergence rate in M.
Lemma For CRPO (Xu al. (027) with the softmax parametrization and the exact critic estimation (i.e., no critic evaluation error), if we have
2 1/ aM (Eawer (D (m [0.0) +
222 Cmax (S(|AA)
(9)
(1 7)3
17

---

Published as a conference paper at ICLR 2023
then the following holds
1. No,0 + 0, i.., te is well-defined,
2. Jr,0 (Tt) J1,0 (+t) S tr-
3. Jr (m?) - Je,s (+t) 2 for I.....p.
Proof. The following inequality holds due to Lemma (Xu al. 2021
2Ma2|S|1A|
Σ (Je,0 (Tī) Je,0 (Fr.m)) ) + aTl
Σ Wea S Eawn; [D (T m))
(10)
(1-
meALo
i=1
We first verify item 1. Nf = 0, then Ei [ird = M, and 10 implies that
D [ T.,O)l + 2Maa
am St
71
which contradicts Thus, must have Ne.0 + 0.
We then proceed to verify item 2. If E EmENOO (Je,0 (Tī) - Je, (Te,m)) )) > mo Ne.l then 10 10mplies that
Oтд S Eonyy [D (N (m/]m,o)) + 2Ma2|S114|
(1-
which contradicts Hence, item holds.
Finally, the item 3 holds obviously since f, is sampled from Ne This completes the proof.
We now prove Lemmal in Section 2
Lemma Assume {v/ TT= and { Fiz1 are given. For each task t, we run CRPO for iter- ations with a
(1-7)² (1MAS
L3 (log T+1) P.T
+ +r2)). In addition, the initialization {T 17 are
determined by playing FTRL or OGD the functions Esnny (DEL (=t11) for t 1, 1,..., T. Then, it holds that
|AA
12(log T + 1) + D12) Vi I,.....
VM 73 V
HTT
Proof. By the within-task guarantee for CMDP, we know that Ro and { (Rij are well-defined. In addition, holds that
2E [DRL. (T (m)]]
4a Sa/SA|AA
Ro
T
aM
(1 733
T
Eswu; [DLL (τi(0r) - Eown; WKL (TT [o
a&d
T Σ
Bagnn (DeL (m [x])))]
+ 2a(SSIAA)
aM
(1 (1-
where Te.0- The first inequality follows from the choice of 1) from Lemma 4
The key step is
the last step, which splits the total loss into the loss of the meta-update algorithm and the the loss had always initialized at o²
Since each Eawny [Dx (m ]) is f4y -strongyyy convex due to Assumption | and each Φe determined by playing OGD, have that:
Exwny DDx (T/]))))
Eswey aM
[DeL (T [5*))
21 T + 1)
T
P.MMT
t=1
18

---

Published as a conference paper at ICLR 2023
where Lg is the upper bound Volsaur [DE (Till)), Mx is the strong convexity parameter for the KL divergence the softmax policy.
arg ming Et t- Bown DxL (m by the definition of D", we have Bs-ut D [T] D Thus, by substituting the definition of Øt, it holds that
Since 0"
2
Bywey Dx (m]])-)] a.M
2a/5||
2D
4 7)
(1 11-78 (1-
aM
T+11
+D=2 (1-7)² hel
Setting the value of a
we can obtain the TAOG Rg as:
/2M//I|A
1.g(ng T- n,T
+ D
|
Ro
/M(1 7)3
The bound for R2 can derived similarly.
The lemma above shows how the parameters like learning rate and safety threshold ne be chosen to achieve decreasing TAOG and TACV in the number of updates per task M and the number of tasks T.
E INEXACT ONLINE GRADIENT DESCENT
E. BASICS FOR E-SUBGRADIENT
We start with some basics for e-subdifferential used in the subsequent analysis. This material is based on Jean-Baptiste 2010 Chap. XI). Throughout this section, we consider convex, closed, and proper function f R R U {+00} with domain Dfm(f). We always consider positive >> 0.
Definition (e-subgradient (Jean-Bayn Baptiste 2010 Given â E Dom(f) ff. the vector u E IR is called e-subgradient of at & when the following property holds for any RRd
f(x) 2 f(i) + (u, 2) -
The set of all e-subgradients of f at à the e-subdifferential of denoted by f.f(
In view of the exact subdifferential af(x), ($)( can be called an approximate subdifferential, which a set-valued function with a convex graph. For practical use, f.f( can be used to characterize the e-solution to convex minimization problem.
Lemma 6. (1Jean-Baan Baptiste
2010 Thm. 1.1.5)) The following two properties are equivalent. 0 E 0. (()
> f(i) S f(x) + for all E Rd
One useful result that stems directly from the definition is to link the e-subdifferential of two uniformly close functions (c.g., an expectation of function and its empirical version).
Lemma 7. Consider two convex functions and g. with the property that [| - glloo I e. where Ilf glooo max, [f(x) g(x)).. Then, for any Rd and 0f(x) in the subdifferential of at x, it is also in the 2c-subdifferential of at x, Le., u E 02.g(x).
Proof. The proof follows directly by convexity and the uniform condition:
2 f(x) (s. - xx) - g(v) 2 f'y)
> ((x) + (s, x)) 2E,
where the second incquality is by the convexity of f. and the first and last inequalities are due to the supremum condition.
19

---

Published as a conference paper at ICLR 2023
Algorithm 2: Inexact OGD Algorithm
Input: Learning rate a, .i
1: for / = ,,,,, T do
2: Incur loss (x and compute c-gradient Vele(z))
3: 2(+1 Px (x (V,(((z)
4: end for
Our next result concerned with bounding the distance (measured & norm) between the true gradient and the e-subgradient of the function, assuming the function is differentiable and smooth. Lemma 8. Suppose a function I is convex, differentiable, and I-smooth over Dom(f), and u E (x)()) is an e-subgradient of J at E (om(s). Then,
2
|/u vf(=) - 201 - -CL
for any Ci {ce (0, ?) x cu Vf(x)) Dom(f)}- In particular, if {( Vf(x))
Dfm then ||u (z))) S 2eL.
Proof. Since u is an e-gradient, f(y) 2 f(x) + (u.y x) -c for all E Dom(J). Thus,
f() f()) + (V/(x), y x) + アタ fly x||
(V) u, σ) デ x1| +
Choose y + c(u f(()) for E (0, ) such that + clu vx(x)) E Dom(f), we have that
2e
||u - \/())
2c 2
The smoothness condition in the above seems necessary, as we can construct counterexamples that drive the distance of an e-subgradient and its exact counterpart arbitrarily large without the smoothness condition. In fact, it is known that the set-valued mapping (z, e) - 0x)(x) is inner semi-continuous for a Lipschitz-continouus f. which is implied by the fact that the distance (using the Hausdorff distance for sets) between any two subdifferential (z) and a f fa') for all x' Rd
and e' is positive, and shown to be bounded by O (min(e,e)) (I)= x'll + <')) Jean-Baptin
2010, Thm. 4.1.3). While the exact gradient can be interpreted as e-subgradient driving + 0*,, the existing bound provided by (Jean-Baptiste 2010, Thm. 4.1.3) is vacuous in this case; on the other hand, the bound provided in Lemma 8 remains meaningful.
E.2 STATIC REGRET FOR THE INEXACT OGD ALGORITHM
In the following, we consider the online learning setup, where a sequence of loss functions {4heem revealed sequentially, and the performance of the OGD algorithm (see Algorithm is measured against a static decision in hindsight:
T
T
(static regret)
Σ l((x))
min zeX
(()))
(11)
where {x+ E X) )EETT) is sequence of actions played by the online algorithm. For simplicity, we assume that X belongs to the domains of l, for all t E [T]. Furthermore, we define the following cumulative inexact error bounds:
T
Eq = Σ
Ct.
(12)
where e, corresponds to the inexactness of the e/-subgradient in each round of OGD.
20

---

Published as a conference paper at ICLR 2023
Theorem E.1 (Static regret bound for the inexact OGD). Assume that bEem convex and T/2 Tm-ssmothh, with bounded gradient, i.e., [VVe(<))]22 S Ln for all & [T] and all E X. Then, for any comparator x X, with the stepsize a LIv2T we have that
T
I (xr)) - &
(1+
V2cL, L I2l|a1
T Σ
E21
VT
t=1
1=1
where Et is the amount of inexactness at each step t.
Proof. By convexity and the fact that V, is an e--uugradieet & at Ir, we have that
Vo e ((xx)) (x) - (V,, 2r x) t
Hence, summing over /. = I,..., T, we get
1 T Σ 4(x)) -
1
- (x(x) S
Vi, Tr x) + Ex.
T
To bound the RHS, observe that
|,+4| x/|² < || a.. - x||
= ||0 - x1|² 2a(x; - x, V.) + V
where the first inequality is due to the OGD update rule and the nonexpansiveness the projection operator. Thus, rearranging the terms and exploiting the telescopic
over t [T], we have that
Σ (a--a) - x, V.) S (1 - z||2 - || 10211-x113))
1
2113)
a Σ
1
2xx
2
211² + a T
|01
Σ
1..1?
2a
2 t=1
Furthermore, since 4 is L2- with bounded gradient, and V, is an e-gradient for any E [T]. by Lemma X the following holds:
| < 2II - &.12
21 + 2cL2et,
where the constant e is specified by Lemma g Hence, by combining the above relations, we get
T 4(xx) - lx(x) <
T a
| - x0|2
+
Σ t=1
2
+
T
2nT
2
T
1
|||
2012
t
acL2 +1
Σ
2nT
T
t=1
Let then get the RHS
[|]|||
Liv2T"
/2cl La |all|
T
2
/T
c
T
We can relax the dependence of setting the stepsize on by using a standard doubling trick (first proposed in (Auer el al. 2002), see also, e.g., (Balean al. 2019 Khodak al. 2019
Remark 3.
21

---

Establishing the above Published as a conference paper at ICLR 2023
this result to obtain the proof of Lemma [ which gives the static regret we run inexact OGD over the loss sequences Ey; ( [e,0)] for all t E [T.. Overall, the following regret bound will eventually help us establish the proof of Theorem 3.2 where we will utilize the static regret upper bound for inexact
After establishing the static regret for the inexact OGD,
OGD over the loss sequences E D (xz [= for all [7]. Also, we denote the norm of the policy with respect to the state distribution ||]|| Eees V (())T(s). Now proceed to present the proof for Lemma 2
Lemma 9. Denote (TT,)))) Ev; (m) (t,)) for all t E [T]. For any fixed comparator T = arg min Et= (((TT), if OGD is run on a sequence of loss functions {le)eetr where
T
4 = Es, [ ( with the step-size a = by /2T then the following bound holds for static regret:
||
T
4V2L, Lz | (1+
ET, To + c(v, T where V, and V, are an 6--Suggradient and exact subgradient of Buy (KK (T) at n,, respectively, ET Σ E the cumulative inexactness.
Σ (
Σ (((T)) < V2TL,1(Töl
(2C1 -CILT
for any C1 E ECE (0.
2.)
Proof. The proof follows directly after substituting 20, -C,L and other appropriate constants in Theorem
4
Note that the inexactness bound 6 can be obtained from Theorem 3.1 Corollary, we can finally provide the proof for Theorem 3.2
Proof of Theorem 3.2
Theorem E.2. Let D min 1 IT Eari, [DKL (ftl0) be the empirical task-similarity,
dEGA!S!
and let 01 /2Lg and C2 initialization for all the tasks given by 0² arg min 7
(2+
4V 1
where o* the fixed optimal meta- Et= E Eove, (Fel(fel))) For each task SEAA!
(2C) CCCi-C
t, we run CRPO for M iterations with a
SSA 2M
S + = + D and we obtain
(D. yi and )r= In addition, the initialization ) are determined by playing OGD on the functions E Egri [D& f)) for 1,..., T. Then, holds that
S
V2Lgl107) T
L. (2C,
Er T
R <
+
2
+ D
= O....p.pp
MM 3//
CLL.)
22

---

Published as a conference paper at ICLR 2023
Proof. We know that Ro and J= well-defined. In addition, it holds that
T
Bowu; (DEL (Filde)]
|a|S||A
Ro
aM
(1 71)
T
Bsnuz (DEL. (Ti1d)]]
Eanug D (T [
T
aM
t=1
T
Bonn; [Dxl (TE
aM + 2a|S||A
+
T
(13
t=1
2
Σ
T
Bswu;
[DKL (xi - Esnuz [DE (Ti
aM
t=1
T Besner [DEL (ftz (5 te
2a|S||A1 (1 73
+
aM
where Φi ve.0- Second equality follows from the fact that the total loss can be split into the loss of the meta-update algorithm and the the loss if we had always initialized at ø". Last inequality follows from the KL-divergence estimation error bound in Theorem 3.1
Since each Een,, [De (ftl-)] is str-only convex due to Assumption 1, and since each de is determined by playing FTI. inexact OGD, the following term can be upper bounded using Lemma gas follows:
2
Eswer [DKL (Til)() - Eowuz [DKL (o (0')
T
aM
t=1
2 V2L, 11 VT
4V 122 101 1+
ET
aM
(2C1 CFL
where the constants are from the Corollary Now, will upper bound the second term. Since o* arg min& T Et=EE D+2 Thus, by substituting the definition of o², it holds that
Eyne, [D (#r[0)] by the definition of Dr, we have Eswi, [DKL. (fre S
2
T
Egwp, [DL ( + 2a|S||A|
2D aM +
29 Sa/
T
aM
7)3
TaM
(1 7)33
(1- 3/2
+ cxer + h-2
Setting the value of a =
where
= V2Lgl10'11, C2 =
2 4V21, |0_|| we can obtain the TAOG Ro as follows:
(20) -FL-)VV
9 + off DD2) |S|AA VT
Ro
VM - 7)
The bound for R² can be derived similarly.
E.3 DYNAMIC REGRET FOR THE INEXACT OGD ALGORITHM
In the following, we consider a stronger notion of regret that measures the performance of the OGD algorithm (see Algorithm 2 against dynamically changing sequence in hindsight (see, e.g., ZZinkevich 2003 Jadbabaie et al. 2015 Zhang et al. (017)):
T
T
(dynamic regret)
Σ ((x,)) - Σ (((x))
(13)
1=1
23

---

Published as a conference paper at ICLR 2023
where z E arg m (x) is the optimal decision for the loss f. It well known that in the worst case, is impossible to achieve a sub-linear dynamic regret bound, due to the arbitrary fluctuation in the functions (Zinkevich] 2003 Besbes et al. 2013 Yang et al., 2016). Thus, it is common to upper bound the dynamic regret terms of a certain regularity of the comparator sequence. One possible regularity condition is the path length of the comparator sequence (Zinkevich) 2003 Jadbabaie et al., 2015::
T
PT | - +7-111
(14)
which captures the cumulative Euclidean norm of the difference between successive comparators (note that we will use || for the Euclidean norm, unless otherwise specified). The path-length measure is also the regularity condition used in existing inexact OGD literature (Bedi et al., 2018
Dixit et al. 2019). However, remarked in (Zhang et al. 2017). potentially tighter bound can be achieved by examining the squared path-length measure:
T
ST = Σ
10 - x7 11
(15)
which can be much smaller than Py when the local variations small. For example, when ||> -;-1" O(/vTT) for all [T], have Pr @(VT) but Sr O In this section, we provide analysis with respect to both measures for strongly convex and smooth functions. Furthermore, we propose to apply inexact OGD multiple times each round, and demonstrate that the dynamic regret is reduced from O(Pr Er) O(min (Pr ST Er]), where
E
Va
is the cumulative square root inexactness bounds. Note that our results improve over existing bounds for inexact online learning (Bedi et al. 2018 Dixit et al. (2199) and can be regarded as a generalization of (Zhang et al.) (017)) to the inexact settings. We start with result that will be used in later analysis.
Lemma 10. Assume that f: X + R is d-strongly convex and smooth, and let x¹ = arg m
=eX
be the unique optimal solution. Let Px(x aVf(z)) where ff()) E 0.f(u) and a S + we huve that
ca + 2La
10- 2112
Xa +1+1 ||" x112
MLa + L
where the constant e is specified in Lemma
g
Proof. By the update rule, we have that
V arg (2)) ( (Vf(x,, -x)
1| - =x:l2-
(16)
#'eX
2a
By strong convexity of the objective above,
(v)())) z²) + - f =||2 < (Vf(z), 2)
1
1
x12
1
||u
xx
x112.
(17)
2a
20
20
Since, f(x) is X-strongly convex and L-smooth, we have that
f(x*) 2 ||0 - x112 2 f(x) +
(Vf(x), x),
(18)
and
I f(x²) f(x) + [V)x))x)' x))
2 || 10112.
(19)
Also, since (x(x) is an c-subgradient, we can write
(())) (V - =x)
(20)
24

---

Published as a conference paper at ICLR 2023
Algorithm 3: Inexact Online Multiple Gradient Descent Algorithm
Input: Learning rate a, 31
1: for 1 = ,,,, T do
2: Incur loss (1xt
3: z It
4:
for k = ,.., K do
5:
k+1 Px (xt - a (zf))
6: end for
7: 2e+-1 2t 2K+1
8: end for
Combining 18
19 and
20
we have that
L -- x
f(x")
-() c.
2
Combining the above relations, have that
L
f(v) s f(x) (Vf(z), x)
|V x1
2
L
= =f(a) + (VI(x), x)
| x1 + (V) vʃ(x), x))
2
(
1
$ f(x) + (VI()), x- 2)
||u x||2
2a
x
=x1/
|10 - x
v(()),
20
20
(
7
1
S f(x*) +
||V
x
1|
+
| x||
2
20
2a
| x"
11
(v)
Vf(x), x) +
(18)
L
1 f(v)
+
1
x 2 +
2 2a 210 - x|1
2
2a
100
x
2
(V) v.((),, v x) +e
(in)
(
1
1
2 [(v)
+
||U
x' 1| +
|1 x
2
20x
2 20
x
x1
[(x(
ff(=)]lu--)) +
2a
1
f(v) -
+
|10
1
2
2a
1
+
|/0
2|
+ 2a ||"" - x1 +
+ +1)e, e, 2k
c
2
2a
2
where the first inequality is due to I-smoothness, (i) follows from 17 (ii) is due to convexity, (iii) is due to strong convexity, (iv) follows from Cauchy-Schwarz inequality, and (u) is due to the inequality
ab < La² + 6² for a, 0 and > 0 and the constant comes from Lemma g Choosing L.
1. and rearranging the above, we have then proved the claim.
21
Theorem E.3 (Dynamic regret for inexact OGD with multiple updates). Assume that E, : X -> strongly convex, L L-Lisschiiz, and L2-smooth for all t E [T). By setting S II, K = Im then, for any B > 0, we have that
In2
25

---

Published as a conference paper at ICLR 2023
T
T
Σ (1x)) - l((x)) s min (A1lm1- zill + C2Er + C3Sr +
Σ
[[((2))1
23
T
2all01-11 + Cs Σ
V +
CaPT
t=1
where C1 = =2(T2 + B), C2 (In + 3)
Lo Zhalz
C3 = 3(12 + B), C₁ 2-v2
and C3
2h1
ca+2Lna 2axh2
2- /2
Proof. The proof has two parts, where we use different techniques to bound the dynamic regret by ST and Er, as well as Pr and εr. Then the final bound is obtained by taking the minimum between the two bounds.
Bounding the dynamic regret by Si and Eq, Since & is L2-smooth, we have that
L
(((x)) - (x()) < (V 24 - x;) - +
|| - x;
(21)
2
L.2
- [4(xt) || - x;' +
|| - x 11?
(22)
2
Le + B
$ 23
1| +
||, - x;11?
(23)
2
where the second inequality is due to Sauchy-Schwande and the third inequality is due to ab 29 a² + b2 for a, 2 and O.
Now, using || - 2 v (1 + +)1l - 2112 + (1 1) 1| - - we can bound
T
Σ I - 112 S ||ا zil1?
Σ
(1 + 1) | - x;=111 + [ +) ||
21-111?
(24)
1=2
Recall the updating rule zー-1
Px (2/ a fo- ( ... K; then, we can write that
| 21111 ||=K-1
1121?
(25)
K ca 2T.0
K
Aa+I
Aa Xa+1
|1-11
x1-11
61-11
ALza + L2
Ao+I
where we recursively apply the result from Lemma 10 the definitions of ST and Sr, we have that
Thus, by plugging in 25 into 24 and using
K
T
Σ I - 2;1l S |1-1 xill2 + (1 +
10t - x2l12
(26)
Aa+
+
1=1
K
Aa+11
ca + 2Lza Ex + (1+2) ST.
+ (1 +1+00
ALza + L2
Aa+II
Rearranging the terms, the above relation implies that
T
I xil12= < (1 + Aa) - (1+ ||01 - x2l12 + (1+!) (1 + Xa) (1 +1) ST
(1 Aa)x K
(1 +
(1+ )ax K - ca + 2L22 Er
(1 (1+0) (1 + Aa) - -(1 -11 + ALza
Let L and choose
K=
log(1 (1+Aa) we have
log
2
T
|| - 1; < 4||21 - x1112 + 3ca + 6L22
Er + 68T.
dalz
26

---

Published as a conference paper at ICLR 2023
Combine the above with 23 and summing over t [T), we have that
T
((x))) - E((xx)
t=1
[V(((=))1*+ 3(L2 335r (I2 3) 3ea + 6lar
2daL Er + 2 B)] xill?
28
which holds true for any positive O.
Bounding the dynamic regret by Pr and ET. By 26 and the choice K
log 2
1. we have
log [a]
that:
1 1 2;_1 2 2
2 111?? + 2L2a
Ft-1
4-11
2a
Thus,
ca + 2
|10 x2-111 S
122 14-1 x9-111
20x2222
Ft-1
1
+ 2T,ax
x.-11 1| + 1
Va-1,
(27)
222
2adL2
where the last inequlity follows from va+bs Tu + vb. Due to the bounded gradient assumption, we have that
Σ - s L1 Σ
2z x7
(28)
[=1
To bound
Ei= || - x;ll, notice that
T
T
[x - xill S x - zill +
Σ
x + +||1 - x/7
2=
T
ca + 2L
$ ||2 - zill +
Σ
| xiil +
Eg + Pr:
V2
2a:22
t=1
which implies that
2
co. + 2L
2 ET +
Σ 1=1
Ia 2ill
|01
-rill
+
Pr.
/2
2
22
20dL2
2 V2
Plugging the above in 28 proves the claim.
In the above result, the number of OGD updates per round is on the order of OL2//a), where L2/a the condition number of each loss function. Below, we also provide dynamic regret bound for standard OGD (single update round); as result, we only provide the bound in terms of Pr (similar to (Jadbabaie et al. 2015 Mokhtari et al. 2016).
After establishing the dynamic regret for the inexact OGD, we can use this result to obtain the proof of Lemma 3 in the main paper, which provides the dynamic regret of inexact OGD over the loss sequences E, [Dr (#² (o:)] for all E [T]. Here, present the full statement with constants for
the Lemma
Lemma (Dynamic regret bound for inexact OGD). Denote ((()) == Eu |D ( (6)) for all
t E [T]. For any dynamically varying comparator v/ arg min IT Eu; [D ( 1oO) if OGD W.EAA,
sequence of loss functions Ee(ght), where (e(())) Eng [Dx ( for all E [T] with
27

---

Published as a conference paper at ICLR 2023
the step I 1- number of iterations K == dynamic regret for any 0:
ln2 In(1+
then the following bound holds for
2p.²
T
T
1 T
Σ (e(or)
Σ 4(1))) & min (Cillo) will +2 + +
2/ Σ
Callø1 - rill + C3ET C.PI,
2h, and Cs where Cr = 2(T 3), B), C2 (Ixx + (133++))000000 Schattbaar C3 3( + B). C4 2-v2 Mnral
2hg 2-v2
Ca0-21,0, for any Co E {ee (0. T..) 11 +c( v.) AA where V, and V, are
an Et Su-Subgradeent and exact subgradient of Eny [DKL ( [1)) at 1h. respectively, ET = Σt= Et is the cumulative inexactness.
Proof. The proof directly follows after plugging in the constants from Theorem E.3
F KL DIVERGENCE ESTIMATION ERROR BOUND
We recall the following notations. For each task f, the initial state distribution is denoted by Pt, the state distribution for the optimal policy कं is given by vf, the state distribution for the policy मे is denoted by it and the state distribution estimated using the trajectory sample dataset DD denoted as it
In the main paper, we breakdown the KL divergence estimation error by the sources of origin:
Exg [PKL(m]lm) E,, (0xx Ryz (Px (m/l - Exp [PxI (x7 [r]
(29)
(1)
+ Ep, (KL(((TTTT) Es, -x, (x]
Es, (
(B)
(C)
where (A) accounts for the mismatch between the discounted state visitation distributions of an optimal policy गं and suboptimal one tt. (B) originates from the estimation error of DualDICE, and (C) is due to the difference between के and it, measured according to ît. By the triangle inequality, we can bound the total error by controlling each term separately. This decomposition is general in the sense that it provides a guideline to bound each term with potentially different strategies. In particular, the term (B) can be bounded differently if we replace DualDICE with another stationary distribution estimation algorithm. To bound the terms (A) and (C), we have developed new techniques based on tame geometry and subgradient flow systems. To streamline the presentation, consider the tabular setting with softmax parametrization.
To bound (A), we need to control the distance between 2/ and i/, which can be bounded by the distance between the inducing policy parameters as long as they Lipschitz continuous (Xu et al. 2020 Lemma 3). In addition, the bound on (C) also depends on the distance between policies. In general, controlling the distance between policy an optimal policy based on the suboptimality gap requires the optimization to have some curvatures around the optima (c.g., quadratic growth
(Drusvyatskiy & Lewis 2018) Hölderian growth (Johnstone & Moulin 2020 However, to the best of the knowledge of the authors, the only available results are algorithm-depender PL inequalities for policy gradient (Mei al., 2020) or quadratic growth with entropy regularization (Ding et al. 2021b).
Discussion on Assumption T: As discussed in the main text, Assumption T limplies boundedness and Lipschitzness of the KI. divergence. We make use of this in bounding the terms (A) and (C)
in 29) and eventually obtain Theorems 3.1 and 3.3 We expect that Assumption iis also needed in unconstrained meta-learning by adapting method, i.e., the Technically, Assumption T iis minimum requirement even for single-task CRPO to provide provable guarantees. This can be seen in the convergence guarantec of the original CRPO method (Lemma 4 and Lemma 2T our paper, or Theorem in (Xu et al.) (02T)) last line their proof before the term DKL (mī) me.o) is submerged in the big-O notation). For example, shown in our (2)
framework.
28

---

Published as a conference paper at ICLR 2023
2 a.M Banny DDK 4ctrmax |8||
Ro = J(,( E[Jro(fe)) v
(1 (1-7)3
To ensure that the bound is nontrivial, we need to bound the term DKL ( (e.0). However, if Tt does not have full support over the state/action space, then there may be state where m5(ss 0 but (8) O, which would make the KL divergence infinite.
F.1 PRELIMINARIES ON TAME GEOMETRY
For the sake of completeness, let us recall some fundamental concepts/results in tame geometry, which allows us to study the global geometry of the solution maps of a wide range of optimization problems, which will be used in bounding the estimation error for the KL divergence. More information can be found in (Davis al. 2020 Van den Dries Miller 1996). Recall that a class of functions on bounded set is called C smooth when it possesses the uniformly bounded partial derivatives up to order p.
Definition 3 (Whitney Stratification). A Whitmey C* stratification of set is partition of I into finitely many nonempty Ck manifolds, called strata, satisfying the following compatibility conditions:
1. For any two strata La and Io, the implication Ia II + implies that Ia C clIy holds, where cl denotes the closure of the set I,-
2. For any sequence of points in a stratum Ias converging point x² in stratum Io, if the corresponding normal vectors Up Nr, (ax) converge to a vector v, then the inclusion N1,(x*) holds. Here N1, (xx) denotes the normal cone to Io at Tk-
Roughly speaking, stratification is a locally finite partition of given set into differentiable manifolds, which fit together in regular manner (property 1 in Def. 3 Whitney stratification defined above is special type of stratification for which the strata are such that their tangent spaces (as viewed from normal cones) also fit regularly (property 2).
There are several paths to verifying Whitney stratifiability. For instance. one can show that the function under study belongs to one of the well-known function classes, such as semialgebraic functions (Davis et al. 2020), whose members are known to be Whitney stratifiable. However, to study the solution function of a general convex optimization problem, we need far-reaching axiomatic extension of semialgebraic sets to classes of functions definable on "o-minimal structures," which are very general classes and share several attractive analytic features as semialgebraic sets, including Whitney stratifiability (Davis et al. 2020 Van den Dries & Miller 1996).
Definition (o-minimal structure). (Van den Dries & Miller 1996) An o-minimal structure defined as a sequence of Boolean algebras Or of subsets of R", such that for each ny E N, the following properties hold:
1. If some set X belongs Ou, then X R belong to Outi-
2. Let Pproj RR" x R + R" denote the coordinate projection operator onto RR,,, then for any
X in Ou41, the PPros(X) belongs O,-
3. O₂ contains all sets of the form {x E R" y(z) = 0}, where y(ι) is polynomial in R".
4. The elements of O, exactly the finite unions of intervals (possibly infinite) and points.
Then all the sets that belong to O, are called definable in the o-minimal structure.
Definable sets have broader applicability than semialgebraic sets (in the sense that the latter is special kind of definable sets) but enjoys the same, remarkable stability property: the composition of definable mappings (including sum, inf-convolution, and several other classical operations of analysis involving finite number definable objects) in some o-minimal structure remains in the same structure. We will crucially exploit these properties in the following sections.
29

---

Published as a conference paper at ICLR 2023
F.2 BASIC PROPERTIES OF SUBGRADIENT FLOW SYSTEMS
We also recall some basic definitions and properties of the subgradient flow system (see, e.g., (Bolte al. 2010 Thm. 13)). Let ʃ Rd R U {+o0} be a proper lower semicontinuous function. Definition 5 (Subgradient flow system). For every x E dfom(f) there exists a unique absolutely continuous curve (called trajectory or subgradient curve) 0(T) :00 +00) IR that satisfies
(((T) E (0T(()) (( = 8g E dom(f).
a.e. on (0, +00)
(30)
Moreover, the trajectory also satisfies the following properties (Bolte et al. 2010 Thm. 13):
1. ((T) E dom(af) for all T E +0o).
2. For all 7 > 0, the right derivative 0(r+) is well defined and equal to 0()+)= = - 8 f(((T))
where f(f) is the minimum norm subgradient in (f)) In partieular, we have that ((T) = - ((0TT)) for almost all r.
F.3 BOUNDING THE DISTANCE ||0, - -0
Recall Assumption 2 which requires that the objective/constraint functions and policy parametrization are definable in some o-minimal structure (Van den Dries & Miller 1996). This is a mild assumption as practically all functions from rorldworld applications, including deep neural networks, are definable in some o-minimal structure (Davis et al. 2020); also, the composition of mappings, along with the sum, inf-convolution, and several other classical operations of analysis involving a finite number of definable objects in some o-minimal structure remains in the same structure (Van den Dries & Miller 1996). The far-reaching consequence of definability, exploited in this study, is that definable sets and functions admit, for each l: > C* - stratification with finitely many strata (see, for instance, (Van den Dries & Miller 1996 Result 4.8)). This remarkable property, combined with the result that any stratifiable functions enjoys a nonsmooth
-ojjsssawa-js inequality (Bolte et al.) 2007), provides the foundation to bound the distance || #ell by the suboptimality gap. Note that without further specifications, .r is understood as one of the optimal policies that are closest to the policy #e (i.e., the projection of # onto the optimal policy set).
We start with the following elementary result. Here and throughout the section, we use Ft.d {ITL (T, I dr,i) } to denote the feasible set with upper bounds d. Note that Fe,d is the original feasible set. We also let (.),(.)) be the indicator function for the set F,..
Lemma 12. The function (with variable 0) (e,0(Te.)) + UF, (F,.( where de is any vector such that FL.ā is non-empty, is definable.
Proof. Since (.,s(-) is definable for i = 1,.... by the rule of composition, which is due to the definable counterpart of the Seinki-Seidenbegg theorem, (T,,( d;,, is definable for i 1,... p.
Thus, Fe,a is definable on the same o-minimal structure by definition. Furthermore, (., is
definable as the indicator of Fr.5. The definability of (m,, follows similarly. Since definability
preserved under addition, the function (T, + + (T) is definable.
For the convenience of the reader, we restate the result for non non-smooth Kurdyka Bardyka-Lojasewwice. (KL) inequality from (Bolte et al. 2007 Thm. 14). Proposition (Non-smooth
Soadyka-Lojasiewiicz inequality). Let f be a lower semicontinuous definable function. There exists > O, strictly increasing continuous definable function h.
10, p) + (0, oc) which is C² smooth on (0, with h(0) = 0, and a continuous definable function
X R (0, p) such that
1100 100)())) (((f(()))
whenever 0 [f(x)) ((([==])
30

---

Published as a conference paper at ICLR 2023
Ft,d
π *
Fi,d
* T t
π t
Figure 3: To bound the distance between मं and ft, we first bound the distance between #ं and the optimal policy with respect to a larger feasible set F, by an argument based on subgradient flow curve. Note that f. E F,a may be infeasible with respect to the original set of constraints but feasible with respect to the relaxed constraints. We then bound the distance between the optimal policies nं and म.. which correspond to the original feasible set Ft.d and the enlarged set F, z.ā By the triangle inequality, we can then derive the desired bound on the distance between कद and a.. Note that for better visualization, we vertically separate the sets Ft.d and F,,ā. which also aims to indicate that in general the optimal solution मे has a higher objective than के due to the relaxed constraints.
Let 0 and 6 denote the parameters of a policy To and n; respectively. Directly bounding the distance between 0 and 0r is difficult because ı may be infeasible (this is even true for म. since it is only guaranteed to approximately satisfy the constraints), i.e., 0 & Fr.d- Thus, the typical approach of following the subgradient flow of (T,((T)) + (Te) to reach 62 is not applicable. The idea is to enlarge the feasible set Fr.d by increasing the violation threshold de, 2 de, 1 6, for any > such that with high probability, 0 E F r.a Then by following the subgradient flow for (T,o(TT)) + Ls, (TT),
we can arrive at a critical point 07 (corresponding to the policy #,). which is most likely different from 0z. It then remains to bound the distance between 02 and 07, which is possible due to the preservation of definability through inf projection. This is the roadmap we will follow. A graphical illustration of the approach is shown in Fig. 3
Bounding the term 00 ||- In this part, we will bound the term ||0; -0: []. which will be used to bound || # ||. Firstly, we will prove that the parameter Or, which represents the solution map of an optimization with definable objective and constraints, is definable.
Proposition 2. Let (d) E arg min (Je,o(Ts.o), s.t. Je, I - l...,pp be the solution map of the construint parameters d. Then, the function (c(d) is continuous and definable. Further- more, there exists a finite partition of the space such that the restriction of (x(d) to each partition is CP smooth.
Proof. First, it can be seen that the solution map 0.(d) E arg min (r. + II... Let (d) = min Je,0(T (T)))) ) + II, (Te.e) be the optimal value function. Since (T.( + IF,, (Te, is detinable by Proposition 12. and definability is preserved under inf projection, (x(c) is definable. Since (d) (0 Jr o (T,)) I (Te,,) (c(d)) by the Tarski-Seidenberg Theorem, (d) is
definable. The continuity property follows directly from Berge's 's Maximum theorem.
Following the discussion of Whitney stratifications in (Bolte et al. 2007), since the graph of a definable function is Whitney stratifiable, we can construct a partition by projecting the stratification into the function domain, which will be a Whitney CD CF-stratification by the constant rank theorem. Furthermore, the restriction of the definable function to each stratum is C*-smooth. Alternatively, we can directly use the fact that for any definable function, there exists CP-decomposition which has a finite number of cells, and the restriction to each cell is CP-smooth (Van den Dries & Miller 1996). This completes the proof.
Now that we have proved that the function (c(d) is definable, we can obtain the bound ||0; 01 Intuitively, our proof exploits the fact that continuous and definable functions exhibit controlled behaviors along any path, even if it crosses over finite number of Whitney strata.
Lemma 13. For any d such that F,,ä is non-empty, the following holds:
100
0, [10(d) 0(x) -lld
31

---

Published as a conference paper at ICLR 2023
Proof. Since every smooth function
bounded set Lipschitz, let us denote L3 as the maximum
of the Lipschitz constants for all the cells of the Whitney stratification of 8g (d). Let d(A) = A
X)d, where 0 S À I 1, be the curve that connects between d and d. Also, let 0 = \ 1. A, =
be the partition such that (c)) belongs one cell for all X X < Ai+1 for i 1,,,, 1. We know that n < oo since d(O,) is Whitney stratifiable. Thus,
[[0((d) - (c(d)ll
Σ 1 (d(a)) - (c(((A+1))
< La Σ
|d((;) - d(Ac+1)ll
i=1
S Talld - d]| Σ
Di+1 - Asl
1=1
Lalld - -āl
where the first inequality is due to triangle inequality, the second inequality is due to Lipschitz continuity, the third inequality due the definition of d(A), the first equality is due to the non- decreasing sequence of A;.
Bounding the term ||0| Bell- Recall that &e is the parameter for At (output of within-task CRPO),
and 07 is the parameter for an optimal solution with an enlarged feasible set e, In this subsection, will obtain the upper bound for the term 10 doll- Let f d) (T, +II (TT)), and choose d, O(1 / M) for i = 1, .....P p. which coincides with the upper bound on constraint violation for within-tass CRPO such that 6g Fi. with high probability. In the next result, we will condition on this probbprobability event.
Lemma 14. With the choice of d = d 8, where = O110 M) coincides with the upper bound on constraint violation for within-task CRPO such that O₂ FGG the following holds:
10: 0.1 S o (n (I/M))
where h is strictly increasing continuous function with the property that h(O) as specified in Lemma 1
Proof. Without loss of generality, consider f(0) = (e,0(TO) + L5 (TB) + c, where e = - innf (TT) + I,, (TO), so that the minimal value of f is translated to 0. For simplicity, also assume that f(0:) S x'(( Note that this assumption can be relaxed by using the concept of "curves of maximal slope" at the cost of slightly more complicated analysis and bounds (loffe 2009).
Now, consider subgradient flow ((T) - (f((())) (see Definition
5), initialized at 8(0) = 0 then,
for any 0 < s' < s, we have that
((((s)))((((((()))) (((((()))) = ' d (b((((+))) dr de
((((0()))) -
[ M ((106)))))(+))22
((()))
J 0 ((T)
10(ss) 0(5')1
where the second equality is due to the property of the subgradient flow (see Sec. F2). the first inequality is due (1)((())))) > from Proposition 1 and the second inequality is due the
32

---

Published as a conference paper at ICLR 2023
triangle inequality. Thus, by taking s' = 0 and - oc, have shown that
h(f(6.)) 2 1|0 01|1-
Therefore,
11.. 0,1 s h(f((.) f(0)))
- h - (,,)(
where the first inequality is due the optimality of # and (i) follows since both f and nz feasible for F,, t. Note that the suboptimality bound can be split as
h()zo((,)) - )c,(;;)) = h (),(( J(,(m;)) + Jeolat) -
By CRPO, can bound the value difference (ft) Je,o(m)) O(L/VM). Moreover, Since the value function Lipschitz (Xu et al. 2020 Lemma 4), the value difference Jr,0(T;) - Jo can be bounded by the distance ||07 l, which is bounded again by (I1/VM) according to Lemma 13 Hence, recognizing that is strietly increasing, we have proved the claim.
Bounding the term ||0| - -dll. Finally, we are able to bound the term of our original interests.
Lemma 15. Under assumption) 2 the following holds:
|00|- = (
VM)
where h is strictly increasing continuous function with the property that h(O) as specified in Lemma 1
Proof. The claim follows directly from Lemmas 13 and 14 and the triangle inequality.
as it only relies on the optimization landscape. The only place we rely on the algorithmm is to bound the suboptimality gap, which is then converted set should be viewed as proof technique and has no implications for the algorithum design. Indeed, the motivation for the enlargement is to properly design a subgradient flow system. Thus, the result how the enlargement is performed. Also, note that defimability
Remark Note that our strategy to bound ||0; 0 algorithmic-anonn
bound on ||ē: 0 Lemma 14 Also, the enlargement of the feasible
of Lemma 15 is not conditioned andnTee 14 the former case, we exploit the Whitney stratification property provide upper bound, while in the latter case, exploit the KL property obtain lower bound, hence they serve different purposes.
used differently in Lemmas 13
F.4
BOUNDING TERM (A): [w=; [DKL(T))=)) Fe, [=x((t))]]]]
The result from Lemma 1 can be used directly to provide bounds for (A) and (C). We start with the term (A).
Lemma 16. The following bound holds:
Essiy -Bwaa o (
(31)
VM
VM
where h is strictly increasing continuous function with the property that h(0) as specified in Lemma 0
Proof.
Eenuy [KL (T][T]] E Ceo.,,DDLCee [KL((]]T)]
Σ (15(8) -g (()))))(((((()))
.ES.
< C+lluz - it1l1
20,Co1107 dellz
33

---

Published as a conference paper at ICLR 2023
where the first equality is by definition, the first inequality is due to Assumption 1 and the second inequality due to (Xu et al. 2020 Lem. 3), which also specifies the constant Cp. and (Levin &
Peres 2017
Prop. 4.2). The result then follows by recalling the result from Lemma 15
F.5
BOUNDING TERM (C): [B,, (DK2((/Z Ex, (R (felmll
Similarly, we can prove the upper bound for the error term (C).
Lemma 17. The following bound holds:
1 VM
1Bgwe, [Dxr ( - Ex -
(32)
VM
Proof.
Band, -Ba
Σ (s) ( -
(s)
- -
SES
s Lg Σ (T( (s) #e(3)]l2
#ES
< Lg Σ p2()))10; - 0, d'1loo
AES
< Lg 10; 0.112
where the first inequality due the non non-negativity of (s(s) and triangle inequality, the second inequality is due to Assumption the third inequality holds for any constant e' and is due to (Mei al., 2020 Lem. 24), and the last inequality is due Σ E (s) and by choosing = 0. The
result then follows by recalling the result from Lemma
F.6 BOUNDING TERM (B): [Ez, [DKI. (mī())) RR, (Px((T]]=]]
Now, we will upper bound the error term (B). The proof follows DualDICE (Nachum et al. 2019). We introduce the following notations. Let E,,, denote an average of empirical samples where {si, di, Tú, L dP,, and Pr be the initial state distribution for the CMDP task The number of
data points N ((M OMM1+ 1+1/), where is any positive number (0, 1). Note that the additional factor of ( results from the critic evaluation per policy update (see (Xu al. 2021 Thm. 1)). We will roughly bound N = O(M²) in the following to simplify the presentation. The stationary (s(s.))
distribution correction factor is denoted Wa,/D, D. (s, a) ("*aa,))*
We make the following regularity assumption on the distribution dDd with respect to the target policy t, Nachum et al. 2019, Asm. 1).
Assumption (Reference distribution property). For any (8,a), ()(8,a) O implies that (P((s,) a) > 0. Furthermore, the correction terms are bounded by some finite constant Cw: [Wa,/D, 11.0 C..
For convenience, we recapitulate the key points from DualDICE, where we also omit the task dependence (i.e., we use d?, n, and p in lieu of dP: t. and Pt. respectively). The objective function is given by
J(z, () = E(s.a.'")m [[2(s, a) - 72(5 (() -((.))))())) -(1 -1-9 7) E (00~5,00~(50)) [2(80, an)].
(33)
(34)
The objective in the form prior to introduction of ( is denoted as (z):
1 J(z)
2 B(o,a)~ [[= =){{,a)]] (1 7) E Es B,o [2(80, ao)]
(35)
34

---

Published as a conference paper at ICLR 2023
Let Jzz, 5) denotes the empirical surrogate of J(2, () with optimal solution as (2 (²) We de- note z arg minge J(z and 2* = arg min 2 [z). We denote L(z) = mäX J(,
and [(z) maxçen Jz, () the primal objectives, and ((() minger [ (). {(5)
mingeF J () as the dual objectives. We apply some optimization algorithm OPT for optimizing (z,(C with samples {si, d, Ti, di ~, {su] ~ 3, and target actions af ~ (s(), ag ~ (sb) for
i= ,. ... capture the error of approximation with F for and H for & in optimizing [z, S)
The output of OPT is denoted by (2, <). We also make the following definitions to
Eapprox (F) = sup inf (1 - =I|p,1 + 2|5 - =l(pa,1)
(36)
=ESx R RFET
Capproz (H) = sup
inf (llSH Sllp,1 + 11sH (1IpT,1
(37)
ÇESxA- & CHEH
Capprox F, H) Capprox (F) Capproz (H)
(38)
We also define
Copt == - Ilb, +
BmT=" 2* BB" - ( 2)) P.
(39)
as the optimization error of OPT from DualDICE.
Lemma 18. By estimating ù, with DualDICE, the following bound holds:
(V
[R,[DKL [ Ex, (x]]] =
VVM + Copt + Capprox (F, H))
Proof. We begin with the following decomposition:
(Eg, (Dx (DKL(T)])) - Ee, [Dx (x; <
Eao. Σ ((8 (), - (8" - (
+ 2 Esp, E(e (ss Es w (ssa)((
We will bound each term above separately.
1 S 202
Brg Σ (3 - (s, -(8- 18*- (st,a))),
< 20
- 11 + |1( 2x (8 13 2
where the error Eopt is induced by the optimization OPT. The error term e2 can be decomposed as
2
62 $2 22
Exp, Σ - (*,=*)(ssa))
Egp, (8 1a - ().a)
Catas
+ 20
Es,, Σ ((3 B
( - (s,aa)
(40)
=2Ettot + 202 Exo, Σ E( (
B 20 (s, - -B -B.2))
where the equality is due to the result that x* B* 20 (s. a) = We, /
D,, (s, a) (see Nachum et al.
2019 Eq. 17)) and Estat is the error due to the finite number error. By (Nachum et al. 2019 Lem.
35

---

Published as a conference paper at ICLR 2023
7), Estat = O ( of data as ( To bound the second term, use the fact that (z) as defined in 35 is 1-strongly convex. Hence,
log M4 1 with probability at least 1 8, where we use the bound on the number
M=
B EgD: E (1 - 2²t²²))) (s, " (s. =Bs,>'((s))))))
1 |1(5 - B²x²²) - -2= -B >1B
S ((J(2) ((2)))
where (i) follows from (Nachum et al. 2019 Section D.1) Capproz (F) is the enror due to the approximation with F for 2, Capproz (H) is the error due to the approximation with H for Ç, and cest the estimation error, and L is the Lipschitz constant for
To bound the error between (2*) and J(=)), we use the decomposition suggested in Nacchum et al. 2019):
J(²) - J(²)) - L(8)) L(3") L(2j) (6)
-
L(2 - J(3z)
+ J (3}) J(²),
(41)
(665)
(in)
where (1) S 1-n
2C 1c ('Il,,, S
20 1-y Caprror (H), (ii) 0
v log M+log M
by (Nachum
al. 2019 Lem.
6) (by also plugging in N ((M))) Note that we refer the reader to
(iii)
by definition,
and (ir) (apaparr (F)).
Nachum et al. 2019 Sec. J(²)) on the order of
D.I) for the above bounds.
Therefore, we can bound J(#t)
y log M++ogg M
O Capprom (H) Eapproz (F)
Combining the above relations, while noting that VM thus kept as the upper bound, we have shown the result.
I decreases slower than J in terms of M and is
F.7 PUTTING IT TOGETHER: BOUNDING THE KL DIVERGENCE ESTIMATION ERROR
Theorem F.1 (KL divergence estimation error bound). The following bound holds:
|E,; ([K((((TT))) - Ex, [DK((R]]T]]]
= (0(n
1 + VM
1
+ /Copp + Capproz (F, 72)
VM
where h strictly increasing continuous function with the property that h(O) as specified in Lemmal Capprox (F, H.) is defined in 38 and Copt is defined in 39
Proof. The result follows by combining the upper bounds for the error terms (A), (B) and (C),
as specified by Lemmas 16 18 and 17 We also apply the elementary inequality va ta+b+e bbbcc vā + Vb + Vē to further simplify the bound.
Remark 5. The bound above depends on the number of iterations M per task in different ways. By increasing M, we can expect to reduce the suboptimality gap. which can help reduce the distance between tt to the optimal set of policies. Also, increasing M results estimate its stationary distribution offline by DualDICE, which reduces the estimation error. The bound indicates that the only terms that do not vanish as we increase the number of iterations per task are those due to the inherent optimization error copt and function approximation error Eapprox (F, H)) In the case those terms are negligible (which are possible in view of the recent breakthrough in overparametrized deep learning (Zhang al. 2021 Neyshabur al. 2011 Li & Liang) 2018 Zou let al. [218)) Arora et al. 2019), see also (Fan et al. 2021) for a survey), then the KL divergence estimation can be driven arbitrary accuracy.
larger dataset used to
36

---

Published as a conference paper at ICLR 2023
G PROOFS FOR THE SECTION 3.3
G.1 TAOG AND TACV BOUNDS FOR CRPO WITH ADAPTIVE LEARNING RATES
This section presents the task lask-averaged regret upper bounds for the CRPO when the adaptive learning rates a are used for each task, and the Q-estimation error is accounted for. We also recall that de, the constraint upper bound for increasing the upper bound to de,: + .T.). For a single run of CRPO in task f, we denote Neu as the set of time steps the reward is maximized and M as the set of time step constraint i minimized. The Q-function in the CRPO algorithm is learned through TD learning with the total number of iterations denoted by Kn The Q-function of objective for policy Tt.m at time step m is denoted by Qi, and the estimated Q-function denoted by Qi, The maximum value for both rewards and constraints is assumed to be Cmaz-
1, ..... P and 7) is the tolerance for constraint violation (i.e.,
With all notations for CRPO in place, we present the following result (Xu et al. 2021
Lemma 19. For the CRPO algorithm in the tabular settings with learning rates or, the following bound holds:
Σ (JoO(Ti) - Je.o(Te.)) + Tiak
Σ We,
at
mENio
< E Eorwy [DKL [Te,0]] + 20 mmn SS|AA|
Ne,el
7)3
==0
ar + (1 - -7)- + 30,cmmo)))
1Q
Qi, 1l
71-
<=0 mEN,
Proof. m E No. by (Xu et al. 2021 Lemma 7), we have that:
20 2cmaa |
ae()ro(TT)) Je,0(Femm)) s Ey; (KL((T/ (Tem) - DKL ( [T.m++)l +
(1 - (1-733 0g
3ar (1 a:Cmar) 110m.m Q2.mll2.
(42)
(1 (1-
Similarly, if m E Ne, we can write
2c |
a() - Jr, s Evg [Dx (T]]Te,m) DKL( (x
(1 7)3 ai
30, (1 + (4Cmazz)
1Q - -l
(43)
71-
Taking the summation of 42 and 43 from m = 0 to 1, we get
Σ (Juo(=i) - JTo(TT.,
Σ Σ
(Jea((Te)))) (T)(
meA.
i=1 meNa,i
< (F)
202 |
Σ
P
a Nessl
71-
i=0
31 ((emma))
-Qi.m llz
(1-
mEN.
Since (T.(())
(m)) 2 7)t 11Qu.m terms above, we obtain the result.
Qimml
Xu et al. 2021 Eq. 15), by rearranging the
Next, we study the condition on the maximum constraint violation threshold 7 and how it affects Noo and the upper bounds for TAOG and TACV. We make the following assumption to proceed.
Assumption 4. Assume that EmeNio (m,) Jr.o(Te,,i 2 CJ for some ey E ( (-bo 0).
37

---

Published as a conference paper at ICLR 2023
The assumption above indicates that the policies in Ni,0 do not have rewards higher than the optimal policy by more than 2777 average. Note that it is indeed possible to have rewards higher than the optimal policy if the corresponding policy does not satisfy some safety constraints (i.e., infeasible policy). However, it is not strong assumption since The above assumption not present (Xu et al. (021). which invalidates one of its derivation steps (in particular, (Xu al. [02T Thm. 3)), and is thus introduced to rectify the proof.
comparing it with the optimal policy.
Lemma 20. Suppose that the following condition holds:
2 n. Bug (T + 2c S|
ai
(1-7)3
1=
ax + (1 -1)2 30m
11
Vumllz.
(44)
(1-7)2
1=0 m
Then, have that No.0 + 0, i.e. te is well-defiedd; also, one the following two statements must hold,
1. NNcol= 2 M/2.
2. EmENio (Joo(=z) - Jr, Je,o(Te,m)) s O.
Under assumption 4 we also have the following holds:
We,o0 2 - ki M
for some E (0, 22
Proof. The proof for Ni,0 * 9 follows directly from (Xu et al. 2021 Lem. 9). For the second
statement, we consider the case that ΣmENi, (Jro(TT) J. implies that
O. From Lemma
au Ne.i S Eon~ [xI((((FTe.))) + 2cmaan |
Σ
a Ne,
7)3
1=1
1=
a+ (1- 330,
1122, - Qi.mlla-
71-
1= mcNLi
Suppose that (Neol M/2, then E Wi,11 > M/2, we have that
2 a < Ex (TL
1
202 |S||A|| P 7)3
Σ af
i=0
(1 (1 )) (1 7)
(334
11Qi Qi
== meN
which contradicts 44 Hence, we must have Wi,oo 2 M/2.
Next, we show that Wo 2 ( x)M for some x (0, f)). Under assumption Aa by Lemma 19 we have that
2c 2c2 | a Ne.1 < E [DKL(T)|mmu))+++
P
Σ 1=0
a We
(1 (1-7)3
ar(3 (1 7)² 30x
11 - -imml12 C...y-
(1 72
1=0 mEA...
38

---

Published as a conference paper at ICLR 2023
Choose K - a. case that [V6.0l < (2 - 1)) M, which implies that E We,51
Since -cy 2am by assumption, we have that (0, 2) Consider the
> (2 + K. This implies that
26 26maz |S||A| P
2 x)aanMM s Bewr [TK [T,))
Σ W
(1 - (13
(3 + (1-7)² + 300, 11
Qimlla,
(1-7)2
< mEN.
which again contradicts 44. Hence, we must have |Wooo 2 (2 K)
Now, we prove the upper bound of suboptimality and constraint violation per task. Lemma 21. Let the violation tolerance be chosen as:
2 2 [ (1z [T.u)]
+ a44cmaz |
20x + +11 (1-1) -7)² + 304 Cman)
1
Ma;
(1 7) 1=0
VMaa(1 7))
Then, the following holds
ci Bonny [DLL(T) caa +
p
Ga + cáa²
U an)
(45)
a,M
04 M
(,((T),) = U,,((Te,0,05)) c
(46)
VM
where ej 2, c²
1ca 1S
(1-2) c3
3+(1-g) [1-7)²
ct = 3amor (1-7)a, and cf = (1- 3)155 [A
1-2N
Proof. From Lemma
19 we have that
(Jeu(Tt) Jeo((ee.)) m1 Σ a
Cg
meNLo
20 20maz [S|AA|
Esnuz [DLL(T;(TT.)))
Σ at Wasl
(1 (1-
1=0
ar(3+ + 72) 304
11 Di 112
(1 72
mEN
(Je,((Ti) E
-e,0 < 0, then -B II (Jeo(T²)-
Jeo(Te,)) 0. then, by Lemma 20 we have Woool 2 M/2. Hence,
Je,( B[Jro(+te)]- We.ol
[Jro(TT) - Je,o(Te.m))
meAs.0
2 s
(cga + chat)
a,M Eu, (KL + char +
11
-iiwn 1121
Mas
1=0 meA
2
(chars + chaff)
a.M Eu Eu + chor +
VMal
1=0 mEN.
where the last inequality is due to the choice of K,, (/M 1/a log 2og (1S as specified by (Xu et al. 2021 Lem. 8) for critic evaluations. Here, the constants chosen as ===0
39

---

Published as a conference paper at ICLR 2023
o 4c
|i (1-7)* 73
cg
3+(1-2)
(1- For constraint violation, consider any 1, ...,, P.
(I-7)
we have
[[),, - -de;i
Σ
Je,(Te, - dr,i
|eooo
mENo.,
$
E (Jes(Te,m)) - de,s) + N meNio
[J,,(Te,,m) Je,((Te,))
|o mEN,o
S 1/1 + N
11 - Qi, ll2
1=0 mENis
2
< 1/
Σ
11
-
QQ
2
m.N.,
where the first inequality is due triangle inequality, the second inequality is by the design of the CRPO algorithm, and the third inequality is due to Lemma 20 where & E (0, }). By the choice of
Kin, we have that E Emen., 11Q - Qi ll2 s v(1 8) Plugging the value of Ni yields the desired result.
Finally, we are able to provide the following bounds on TAOG and TACV in the case of adaptive learning rates.
Theorem G.1 (Bounds on TAOG and TACV). Suppose the CRPO algorithm for M steps per task t with learning rates ot. Then, after tasks, the TAOG Ro is given by
1 ci (Dxe: +ca Ro
co + caa
(47)
T
a.M
as a. M
1=0
and the TACV R₁ is given by
T
ci ar
caa + cha
+ cf
R
E Eown [DKL(Ti(Teo)) + cla +
(48)
a.
VM
1=0
for = 1,...,P, P. where of = 2, ch =
dop 1o |S||A|
3+(1-g)² (1-7)²
c4 = (1-7)2, and
3cmaz
(1 (1-g)3
of 2/(1-7)|8114 1-2p
Proof.
The proof follows directly by summing the results 45 and 46 over t
1,..., T.
G.2 ADAPTING THE DYNAMIC REGRET USING ADAPTIVE LEARNING RATES
We restate the theorem below for convenience.
Theorem G.2. Let each within-task CMDP t run M steps of CRPO, initialized by policy Te,0 = INIT(I) and learning rates {as) = SIM(I). Let K² = arg min L(k), where
Uimit(( ((va)TT)) + ET Σ
(dee)
L(K) U.ii(()) +
+ frate (x))
(49)
and (17 (T is any comparator sequence. Then, the following bounds on TAOG and TACV hold:
L(R²) R. S T
= yi=0...,.
(50)
Proof. The idea of the proof is to freeze the learning rates first to obtain dynamic regret bound based on policy initialization and then optimize over the learning rates to obtain tighter characterization.
40

---

Published as a conference paper at ICLR 2023
Also, since TAOG and TACV only differ by bias term that does not depend either the learning rates or the initial policy, we can treat them indistinguishably. In particular,
Ul) an) =
ssi (ax)
(51)
1=1
t=
min
U. (R)
peim (R)
(52)
S min (x)) + Uimit (V)
(1/e)
P6 + (1()
(53)
Upmil (W²
T (Dr)
S min (k)
K + (1a)e((s))
(54)
where = ) Let
T(K)) = (1z(m(())
Up
ET
+
T
finit (d))
+ se seate(ss)
(55)
R
Ri
t=1
and define
n² = === arg min L(k).
(56)
Thus, plugging = x² in 54 results in 50
Now, provide the regret upper bound for Upim (R)), when SIM(t) is OGD over the sequence feim (n:).
Corollary 2. For any fixed comparator a" arg min EL frim SIM(() is OGD which is run
R
on sequence of loss functions (feiim)ee with the step-size K. K.V2T then the following bound holds for static regret:
T
4v2K, Irala"1
Ee (x: Σ faim (a") V2TKala" 1+
Er.
(2C² - CLL.NVT
1=1
for any C1 E fcr (0, 2 ( a + ccu-ccuu - V.) E A} where u is an e-subgradient of feim with respect KG ET Etm, 4 the cumulative inexactness, 6, is the upper bound from Theorem 3.1
Proof. The proof follows directly after substituting 20, -0LL and other appropriate constants in Theorem
4
Next, we provide the proof of Corollary TTAG and TACV regret bounds when INIT and SIM are either FTL inexact OGD.
Corollary 3. For any fixed comparator a* = arg min Σt feim and ca 3+(1-1) (1-7)- IJINIT(I)
and SIM(t) are FTL or inexact OGD over the sequences fenét and feim, then, the following bounds on TAOG and TACV hold:
V2Kala1
(66
4V2Ko (2C1 CTIa)VT
Ex 1
Uimit (fut) + + TV2
R S
VM
VMT
VMT
Voz
MI/TT
(57)
for all O,..., p. where (v) Joerr is any comparator sequence, dg
3+(1-))²
- and c/ =
4.2 1.2
[S|[AA
11-)8
41

---

Published as a conference paper at ICLR 2023
Proof. Firstly, the following inexact upper bounds hold for Uprit and Ugit::
1 UT ((V))tr)) min (ill + C3ST +
2B Σ [e((())
(58)
Callói +ill CgÊT + CPP)).
4v2KaLa a0'l
Ugim( V2VK2 MaTKalo |0*1 +
1+
ET,
(59)
(2C) - CLLa)
where the constants in the 58 and 59 are from the Lemmal 11 and Corollary respectively.
Plugging these the equation we can obtain the following:
Lolo" ET min Cilleb +ill (2C1 - CCL-CT
((K) SV2TKa +
1+
+ C2ET + C3ST
[Ve(6)))) will +3EE + CsPr) C(Pr)
23
TV Φ
+ frate
+
k
k
where the relation 1/3 = + Σt= Eg, DDL (ite (xt) AS such that [xx) is minimized, we proceed using the KKT optimality conditions to get dL
is used to get the second last term
TV3
To get
as de
dL
( (E))))
ET
TV x2 + &M + &VM.
dx
62
Uniitt +6))
Therefore, we obtain k**
e.M+o
Substituting this value of x- in G.2. and using the approximation the final result.
Mi7i we can obtain
M+VM
H ADDITIONAL EXPERIMENTS AND DETAILS
In this section, we describe our experimental setup and other additional details for the OpenAl gym experiments under constrained settings. We present the performance of Meta-SRL on the Acrobot and the Frozen lake under high similartt conditions. We first present some details on the baselines used to avoid any confusion.
Details of baselines used: Denote the policy initialization for task f di. First baseline the FAL, which initializes the policy Φi+1 for the test task 1 as Φe+1 the tasks are encountered sequentially.
1 : Ei= Φi. This is done online as
For the simple averaging baseline, we run CRPO on 10 tasks with the random initialization and evaluate the performance on a test task by initializing with the average of all the suboptimal policies from the batch of suboptimal policies, i.c., Φr --. ΣT= T- o,, where T is the test task. This can be seen as offline method, where suboptimal policies from T tasks are stored and averaged to get the initialization for the test task.
The pre-trained baseline uses suboptimal policy from already trained task initialize the policy on the test task, i.e., Φe = कØ. where o, is the policy initialization for the task f, and से. is the suboptimal policy returned some pre-trained task t'. This baseline could be thought of as the Strawman initialization strategy, where the policy for the next task initialized using the suboptimal policy from the previous task, i.e., Φ1+1 -
42

---

Published as a conference paper at ICLR 2023
For the Meta-SRL in the discrete state action space (i.e., Frozen lake), take the weighted average of the previous suboptimal policies weighted by the stationary distributions induced by each suboptimal policy over all the states. We also adapt the learning rates a for the CRPO algorithm for each task t. The difference between FAL and Meta-SRI. is that Meta-SRL. weights the suboptimal policies higher in the states which were encountered more frequently.
Random initialization baseline is using random iniitalization for the within-tase algorithm CRPO.
Experimental setup:
We run all the algorithms online where tasks encountered sequentially and present the results for the test task after the policy initialization suggested by respective baselines. We do 10 runs for each baseline the test task and present the variance plots. On the test task, we train for 8 steps on the Frozen lake and for 5 steps on the Acrobot. In Frozen lake, each step corresponds to 5 episodes, and the average rewards/costs are reported for each step in the performance and constraint violation plots.
H.1 FROZEN LAKE
For the Frozen lake, we randomly generate T = 10 different orientations as tasks over the probability of a state being frozen hole and evaluate the performance for the scenarios with high task lisk-similartty (low variance for the latent CMDP distribution) or low task-similarity (high variance for the latent CMDP distribution). The agent gets rewarded +2 when it reaches the goal state and incurs a cost -1 when it falls into a hole. We choose the constraint threshold d,; = 0.3.
Frozen lake:
High task task-similarrtt: To generate tasks with high task-similarity, grid of 4 x 4, where the probability of each grid being frozen is 0.7. Then, we generate 9 different grids which differ from the first one by only one of the grids. This means the agent always encounters the new grid, which is very similar to the previous task. From Figure 4 we can observe that baselines pre-trained and FAL are competitive with the Meta-SRL in terms of reward maximization and almost zero constraint violations. The good performance of the pre-trained baseline can be explained using the fact that the the test task and the training task are very similar; the policy initialization will be close to the optimal policy of the test task.
start with random frozen lake
Frozen lake performance
Froze lake constraint violation
2.0
Mata-
FAL
trainendd
1.5
0.8-
initialization
Reward
Cost
Simple everoging
0.4
0:5
0.0
0.0
5
4
5
6
7 8
Number of steps
Number steps
Figure 4: Frozen lake results for reward maximization and constraint violations when the task- relatedness is high. The blue dashed line represents the averaged thresholds for the constraint violations.
Low task-similarity: In this case, random tasks are generated where the probability of tile being frozen kept between 0.3 and 0.7. The tasks are less similar due the high uncertainty associated with the changing orientations.
H.2 ACROBOT
Acrobot: Acrobot a link robot OpenAl gym environment with continuous state space. The agent is rewarded when it achieves certain height of the end link. Two constraints introduced for two links, where a -1 cost is incurred if any link swings in the prohibited direction. We randomly generate T 50 different tasks with different mass links and centers of gravity.
43

---

Published as a conference paper at ICLR 2023
High task-similarity: To generate tasks with high similarity for the acrobot, considered changing the mass of the links, the center of gravity (COG), and constraint threshold for each link. The changes in these quantities were done by adding noise to the default quantities. We considered Gaussian noise with a low variance of 0. to change the tasks only slightly. From Figure 5 we can observe that only pre-trained and FAL baselines are competitive with the Meta-SRI. in terms of reward maximization and almost zero constraint violations.
Acrobot Performance
Acrebot Constraint Violation
Acrobot Constraint Violation
Meta-SRL
Pre-trained
Rewward
-123
Simple Aveergging
CORE
Rondom Intiaalizaioon
-203
Steps
Slags
Sceps
Figure 5: Acrobot results for reward maximization and constraint violations when the task-relatedness is high. The blue dashed line represents the averaged thresholds for the constraint violations.
Low task-similarity: To generate low similar tasks, we increased the variance of the Gaussian noise 0.3. We can observe from FigureZ the performance of the baselines was poor for con- straint satisfaction, while Meta-SRL could converge quickly for reward maximization and constraint satisfaction.
Note that, in real-worid settings, tasks are likely to have low similarity in terms of how close their optimal policies are. The good performance of Meta-SRL. under these settings highlights its potential to be extended to real-world settings where safety constraints are present.
H.3 HALF CHEETAH
Half-cheetah is a simulation environment for a 2-dimensional robot. consists of links and eight joints, where the goal for the cheetah is to run at certain velocity. It has 17-dimensional state space and a 6-dimensional action space. The reward is calculated as the negative of the absolute difference between the current cheetah velocity and the desired velocity. The original HalfCheetah environment does not have any constraints. We introduce a constraint that penalizes the deviation of the cheetah's head from some desired height:
Rcheetak
htorget
where we specify the cumulative absolute difference between the cheetah head height and the desired height to be less than tolerance c. The cheetah is trained on T 100 tasks for both high and low task-similarity settings.
To generate tasks with high similarity, the goal velocity for each training task uniformly sampled from a range of [0.35, 0.65]m/s. From Figure we can observe that under high task similarity settings. Meta-SRL is able achieve high rewards and also able to keep the constraint violation of the cheetah's 's head height below the threshold. Under high task-similarity settings, pre-trained and Meta-SRL perform well, expected. However, can be observed that both simple averaging and random initialization perform poorly in this setting.
High task-similarity:
Low lask-similarity: To generate tasks with low similarity for the half-cheetah, the goal velocity for each training task is uniformly sampled from a range of [0.0, 1.0jm/s. Tasks are less similar due to the high variance of goal velocities that the cheetah is trained on. It can be observed from Figure that Meta-SRL is able to achieve higher rewards and zero constraint violations quickly compared to other baseline initializations under low task-relatedness settings. The pre-trained baseline can achieve higher rewards, but similar to other baselines, it cannot achieve constraint satisfaction within 10 steps. can also be observed that both simple averaging and random initialization perform poorly in reward maximization in this setting. Close inspection indicates that there is high variance among the policy parameters learned from each task, which may result in interference among different tasks in the relatively high dimensional state space.
44

---

Published as a conference paper at ICLR 2023
Half-Cheetah, Perfarmance
HalfChhettah Constraint Violation
w-RRL
Muta SRL
-303
Pro trained
Pro trained
mille Averaging
Averaging
-443
Rendom in tislization
Handom intiuaization
543
steps
Figure 6: Half-cheetah results for reward maximization and constraint violations when the task- relatedness is high. The blue dashed line represents the averaged thresholds for the constraint violations. Here, the simple averaging and random initialization perform the worst on the test task.
Half-Cheetah Half-CheeahnPrrfammaaa Performance
Half Jall-Cheetah Constraint Violation
-103
Hota SRL
Meta-SRi winee Averaging Random initielizatnn inn
Pre-tr re-trained
-12
Smole Averaging
-353
Random Bolization
-10
10
Figure 7: Half-cheetah results for reward maximization and constraint violations when the task- relatedness low. The blue dashed line represents the averaged thresholds for the constraint violations.
H.4 HUMANOID
Humanoid is simulation environment 3D bipedal robot, which consists of torso (abdomen) with two arms and legs. Each leg and arm has two links (representing the knees and elbows, respectively). It has a 376-dimensional observation space and 17-dimensional action space. The goal of the humanoid is to walk forward as fast as possible without falling over.
The original humanoid environment does not have any constraints. We introduce a constraint that penalizes the deviation of the angles between the torso and the upper arm and the angle between the upper arm and the lower arm, such that humanoid motions are smooth and graceful. The cumulative constraint is given
Fur
+
0n
+
0,
0:
S
where O.., Ou, 0,, and are the angles between the and right arm, the angle between the torso and the left arm, the angle between both the upper and lower right arms, and the angle between both the upper and lower left arms, respectively. We specify the cumulative absolute difference between all these angles and the desired angle to be less than a tolerance The reward is calculated on the basis of the dot product between the direction and the velocity vector of the Center Gravity humanoid, multiplied by the default scaling value in the humanoid environment Wy. the humanoid as follows:
r = (,, sin + U2 cos f),
where r is the instantaneous reward that accounts for the amount of forward movement by the humanoid, Up, and by are the horizontal and lateral components of the velocity, and 0 is the walking direction of the humanoid. The default value W, is 1.25. The humanoid is trained on T 250 tasks for both high and low task-similarity settings.
45

---

Published as a conference paper at ICLR 2023
High task-similarity: We generate different tasks by changing the direction of motion of the humanoid. Possible direction angles in the humanoid environment range from - - to //2 (which varies from left to right). To generate tasks with high similarity, the goal direction of the humanoid for each training task uniformly sampled from a range of [- π r//4.. From Figure g we can observe that under high task similarity settings, Meta-SRI. is able achieve high rewards and maintain the constraint violation of the humanoid's hand and torso angles below the threshold of e = 4. Under high task-similarity settings, both pre-trained and Meta-SRL perform well, as expected. However, can be observed that both simple averaging and random initialization perform poorly in this setting. Moreover, the pre-trained baseline also fails to learn wewaaddmaximizing behaviors.
Humanoid Performance
Humanoodd Constraint Violation
18
Meta-Sh SRL Pre-tra ned
Cod
Simple Aowe Random inttailzation
Simple Avcraging
Random Inttl izatiizatton
Number of
Number steps
(a)
(b)
Figure 8: Humanoid results for reward maximization and constraint violations when the task- relatedness is high. The blue dashed line represents the averaged thresholds for the constraint violations.
Low task-similarity: To generate tasks with low similarity for the humanoid, the goal direction for each training task is uniformly sampled from range of |-x/4, т //4 Tasks are less similar due to the high variance of goal direction that the humanoid trained on. Figure Shours that Meta-SRI. is able to quickly achieve higher rewards and zero constraint violations compared to other baseline initializations under low task-relatedness settings. The pre-trained baseline also achieves constraint satisfaction in this case but fails to learn behaviors to maximize the rewards within 10 steps. It can also be observed that both simple averaging and random initialization perform poorly in reward maximization in this setting. This can be attributed high variance among the policy parameters learned from each task, which may result interference among different tasks in the relatively high-dimensional state space.
Performance
Humanold Constroint Vialation Vialation
Mota-SRL
SRL
Simple Avee aging
Pro tranedd
200
Simple Averaging
22
Random intiulization
Random Iritiaizztion
32.
31
Number of Steps
Number of steps
(a)
(b)
Figure Humanoid results for reward maximization and constraint violations when the task- relatedness is low. The blue dashed line represents the averaged thresholds for the constraint violations.
I RELATION OF META-SRL TO HARDNESS RESULTS IN (KWON ET AL.. 2021
There is a key difference in the problem setting of meta- meta-nngrning in our study and the latent MDP setting in (Kwon et al.] 2021). The latent MDP setting is more challenging in the sense that there is no clear boundary between tasks. the latent MDP setting, each episode may come from an unknown MDP drawn from distribution (as special case of POMDP); in the meta-learning setting, the agent
46

---

Published as a conference paper at ICLR 2023
knows when task has arrived and is allowed to interact with the MDP over set of episodes (the number is linear with respect to M in our paper). Due to the above difference, the worst-case lower bound of requiring
exponential number of episodes to learn e-optimal policy in (Kwon et al. 2021> does not hold in our case. Indeed, if the identity (referred to as "context" in latent MDP) be inferred, (Kwon al. 202T) is able to achieve regret that is polynomial in the number of episodes (Thms. 3.3 and 3.4 from (K Kwon et al. 2021)).
revealed
Furthermore, a close examination of the bounds provided by (Kwon al. 2021 also reveals some differences from our result. In particular, let K be the number of contexts in a latent MDP and N be the total number of episodes (N is on the order of TMM in our case as we encounter T tasks, each with M episodes). Then (Kwon et al.) 2021) is able to bound the regret (without dividing by the number of episodes N) as O(v K To compare their bound with ours, we consider each task in the meta-lea setting as a context, so T O(K). Therefore, their upper bound (after dividing by the number of episodes N TM) becomes (I/vMM, which does not diminish with the number of tasks Note that our bound (see the comment after Corollary
Ve
M8/4/T (after dividing by the number of episodes N = -M,, where for simplicity we have assumed E = O, i.e., exact access to the loss function. Note that Vi is measure of task-relatedness (a smaller value indicates more relatedness among tasks). It can be seen that while we have a worse order dependence on M, our bound scales with task relatedness Vo and diminishes with respect to the increasing number of tasks T. This is expected
leverage the relatedness among contexts (in fact, the result of (Kwon) et al, (02T)) would hold when tasks are sufficiently different from each other to infer the contexts with spectral methods). In summary, we refer to (Kwon al., (021) as an example that achieving regret diminishing in the number of tasks I' is hard, even with the assumption of observing the task identities (contexts).
NOTATIONS AND CONSTANTS
47

---

Published as a conference paper at ICLR 2023
Notation
Definition
t
index of task
index of OGD steps
policy initialization for task learning rate of within-task algorithm all tasks, where [2] (1...., T
O
[2]
M
CMDP for task & state space of CMDP MM
A e R
action space of CMDP Mr
Pt.
initial state distribution of task transition kernel for task reward function cost function for task t total number of constraints set of all timesteps for within-task algorithm simplex over all state-action pairs stochastic policy for task t state visitation distribution of policy ı at task softmax policy parameters
a)()),a)
0,00 A- [0,
0,118 A [0.1 1]
P
[M
A(A) ST
T S A(A)
0
(x)
state-value function for reward (i 0) or cost i task with policy a action-value function for reward (i 0) or cost i in task with policy ा expected total reward (i 0) cost i for task and policy π bound on expected total cost for task t set of optimal solutions for task optimal policy for task maximum value of reward/cost functions
(s,
(T,
de.;
II;
Cmax
(+1(-)))
KI. divergence TAOG and TACV
Ro, R.
tt
suboptimal policy returned by within-tass ttak algorithm in task true and empirical task-similarit true and empirical task-relatednn shrinkage simplex set inside AA
D", D
Vs Ve
AA
Lig Lu
Lipschitzness and smoothness parameter for KL divergence of policy w.r.t initial policy maximum value of KL divergence of policy æ w.r.t. initial policy stationary distribution correction for task at state action off policy dataset for task /. strong convexity parameter for KL divergence of policy a w.r.t initial policy dynamically varying comparator sequence inexactness in the KL divergence estimation using DualDICE state distribution induced by â optimization error in DualDICE approximation error DualDICE hypothesis class used in DualDICE
O
Wa/ D, ())
Dr
Pa
(wi)E
i
Copt
Capproz
F.H
Er
cumulative inexactness for KL divergence estimation given by Σ G, cumulative square root of inexactness for KI. divergence estimation given by Σ Vor strictly increasing continuous definable function used in Theorem 3.1
Er
h: (0, p) + +0,000 o0)
V.. Ve
Exact and inexact gradient learning rate for inexact OGD Projection operator
Px(-)
Pr
path-length the comparator v/r
Kin
number of iterations in the critic estimation of CRPO tolerance for the constraint violation de, for task f path-length and squared path-length of the comparator vi c-subgradient of function f Domain of the function loss functions for suboptimal policy Ep, (ft(
Pr, ST
0.f(.)
(fm(f)
f(()
Table Table of notations
48

---

Published as a conference paper at ICLR 2023
Table 2: Table of constants.
Notation
Definition
Notation
Definition
di
4e I
(1
c/
3+(1-))
d
36mes
(1-2)²
(1-3)
cf
2v (1-)) I|AAA
0,
2
1-2k
Tre
C
2(L
3)
C2
(Lx + B) 3ea Gaa
C3
3 + 3)
C4
2L.
2-
C3
21.
22
22
200 l.a
49


Reviews:
[{"review_id": "wPX9aPNU_r", "reviewer": "Reviewer_DCQm", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The proposed method concerns safe reinforcement learning as a constrained MDP problem. In particular, the authors consider safe meta RL, a method to deal with dynamically shifting environments. Technically, the method is realized using a so-called ‘CMDP-within-online’ framework, where a constrained learning task is performed ‘within’, and the resulting policies are input for the meta learner. Theoretical regret bounds and estimation errors (regarding sub-optimality) are given, and the expected theoretical learning rates are derived. \n", "summary_of_the_review": "Strong paper, experimental evaluation should slightly be improved.", "strength_and_weaknesses": "++Important problem, clearly fitting into ICLR\n++Strong technical contribution\n\n—Experimental evaluation is very sparse. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "WxMHV58puI", "reviewer": "Reviewer_fmH2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the meta-learning problem regarding various safe RL tasks that are modeled by constrained Markov decision processes (CMDPs).  The authors proposed a CMDP embedded online learning framework to generalize learnt safe policies to other unseen CMDP environments. In theory, the authors proved regret bounds in terms of within-task optimality gap and constraint violations in both static and dynamic regret metrics. Finally, some comparison experiments are provided to show the effectiveness of the proposed method.  ", "summary_of_the_review": "All claims of the paper are supported by proofs or references. Most of them are well-supported, but some cited results are vague or modified in an ambiguous way. The proposed meta learning method combines existing RL algorithms for safe RL and theory builds on existing results and assumptions. The experiments are based on some basic RL environments. \n\n\n============================\n\nPOST-REBUTTAL. Thank you for your response. Since most of my concerns are addressed, the score has been updated. ", "strength_and_weaknesses": "Strengths:\n\n- The studied meta learning problem is motivated by applications of learning a safe policy. This is a useful generalization of meta-learning to  constrained Markov decision processes, which allows to adapt the learnt policy to new constraints quickly. \n\n- The propsoed CMDP embedded online learning framework is practical in sense that it only relies on the inexact solution to sub-CMDP  tasks and data trajectories from previous tasks. \n\n- When the task similarity is bounded, the authors provide theoretical guarantees on both task-within optimality gap and constraint violation in static regret bound, under some assumptions on policy initializations. For practical use, the authors generalize this result to a dynamic regret bound, which is more useful since it does not assume boundedness of the task-similarity. \n\nWeaknesses:\n\n- The provided CMDP embedded online learning framework builds on a simplified version of the existing CRPO algorithm. Although this simplification permits convenience in analysis, it brings some restriction to the applicability of the proposed algorithm. \n\n- In the meta-learning problem with multiple tasks, the static regret seems to be not very useful since the bounded ask similarity is assumed and environments associated with different tasks are different. Otherwise, this becomes a single task problem which doesn't have to necessitate meta-learning.\n\n- The authors mentioned the hardness of bounding regrets in meta-learning by citing Kwon et al. (2021). This seems to be the key challenge to establish the theoretical guarantees. Although a series of assumptions are made, it is not very clear if they are necessary to address this challenge. In addition, the challenge from constraint seems to be unrevealed yet.\n\n- The proposed CMDP embedded framework relies on DualDICE to estimate state-action distributions. However, DualDICE is an existing offline RL algorithm for the standard MDPs. It is more natural to think of some off-line CMDP algorithms that respect the constraints more effectively. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "L3fKobwqpo", "reviewer": "Reviewer_GvYx", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of meta-safe reinforcement learning (Meta-SRL) through the CMDP-within-online framework to establish the first provable guarantees in this important setting. It obtains task-averaged regret bounds for the reward maximization (optimality gap) and constraint violations using gradient-based meta-learning and show that the task-averaged optimality gap and constraint satisfaction improve with task-similarity in a static environment, or task-relatedness in a dynamic environment.\n\nFurthermore, it enables the learning rates to be adapted for every task and extends our approach to settings with a competing dynamically changing oracle. Finally, experiments are conducted to demonstrate the effectiveness of the approach.\n", "summary_of_the_review": "Please address the questions I mentioned above.", "strength_and_weaknesses": "Strength: Propose the a novel CMDP-within-online framework where the within-task is CMDP and the meta learner aims to learn the meta-initialization and learning rate. It shows that the task-averaged regrets for optimality gap (TAOG) and constraint violations (TACV) diminish with respect to both the number of steps for the within-task algorithm M and the number of tasks T.  It adapts the learning rates for each task\nto a dynamic environment.\n\nWeakness: \n\n1. the notation $\\nu^*_t$ in page 2 is unclear. What is $\\pi^*$? It makes harder to understand this paper.\n\n2. The primal approach explained in Section 2.1 is confusing. Why the sub-optimality gap in (2) holds by running CRPO? What is CRPO? Is CRPO an online or offline algorithm? There is no explanation about CRPO and no comments about the \"carefully chosen parameters\". It is not helpful for people who is not familiar with CRPO and makes the paper not self-contained. Those observations make the paper hard to read.\n\n3. Lemma 1 relies on $D^*$ is known and Theorem 3.1 relies on approximation error of DualDIce. The whole algorithm/analysis seems to be a composition of existing analysis (DualDice+CRPO), which might lack generality. It is hard to understand what is the key contribution of this paper.\n\n4. Theorem 3.3 replies on the assumptions of two regret upper bound $U^{init}_T$ and $U^{sim}_T$. There is no explanation regrading why those assumptions are reasonable. With those assumptions, the hardness of analysis is largely diminished.\n\n5. In the experiment, only frozen lake and acrobot are considered. How about the your algorithm for Mujoco environments?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%