Mirror Descent Policy Optimisation for Robust Constrained Markov Decision Processes
Authors: David Mark Bossens
Atsushi Nitanda
Venue: Accepted by TMLR ()

Abstract: Safety is an essential requirement for reinforcement learning systems.  The newly emerging framework of robust constrained Markov decision processes allows learning policies that satisfy long-term constraints while providing guarantees under epistemic uncertainty. This paper presents mirror descent policy optimisation for robust constrained Markov decision processes, making use of policy gradient techniques to optimise both the policy (as a maximiser) and the transition kernel (as an adversarial minimiser) on the Lagrangian representing a constrained Markov decision process. Our proposed algorithm obtains an $\tilde{\mathcal{O}}\left(1/T^{1/3}\right)$ convergence rate in the sample-based robust constrained Markov decision process setting. The paper also contributes an algorithm for approximate gradient descent in the space of transition kernels, which is of independent interest for designing adversarial environments in general Markov decision processes. Experiments confirm the benefits of mirror descent policy optimisation in constrained and unconstrained optimisation, and significant improvements are observed in robustness tests when compared to baseline policy optimisation algorithms.

Published in Transactions on Machine Learning Research (12/2025)
Mirror Descent Policy Optimisation for Robust Constrained Markov Decision Processes
David M. Bossens
david bossens@a-star..eeeoososo edu.sg
Centre for Frontier AT Research, Agency for Science, Technology and Reseorch (A *SAAR), Singapore
Institute of High Performance Computing, Agency for Science, Technology and Research (A ASTR), Singupore
Atsushi Nitanda
atsushi_ matushi_mittaadaaao malandaaa-starr.eeee
Centre for Frontier AI Research, Agency for Science, Technology and Research (A STAR)) Singapore
Institute of High Performance Computing, Agency for Science, Technology and Research (A *STAR), Singopore
College of Computing and Date Science, Nanyang Technologioal University, Singogore
Reviewed on OpenReview: / net/ forum? id= tmfdqtFUqQ
Abstract
Safety is an essential requirement for reinforcement learning systems. The newly emerging framework of robust constrained Markov decision processes allows learning policies that satisfy long-term con- straints while providing guarantees under epistemic uncertainly. This paper presents mirror descent policy oplimisation for robust constrained Markov decision processes, making use of policy gradient techniques to optimise both the policy (as a maximiser) and the transition kernel (as an adversarial minimiser) on the Lagrangian representing constrained Markov decision process. Our proposed algorithm obtains an Ô (1/T2/33 convergence rate in the sample-based robust constrained Markov decision process setting. The paper also contributes an algorithm for approximate gradient descent in the space of transition kernels, which is of independent interest for designing adversarial environ- ments in general Markov decision processes. Experiments confirm the benefits of mirror descent policy optimisation in constrained and unconstrained optimisation, and siguificant improvements are observed in robustness tests when compared baseline policy optimisation algorithms.
1 Introduction
Reinforcement learning (RL) traditionally forms policies that maximise the total reward, within the Markov decision process (MDP) framework. Two important aspects, often overlooked by RL algorithms,, are the safety of the policy, in terms of satisfying behavioral constraints, or the robustncss of the policy to environment mismatthes.. In continuous control applications, for instance, there are often constraints on the spaces the agent may go and on the objects it may not touch, and there the presence of the simulation-realit gap.
Safe RL techniques have been primarily proposed within the constrained Markov decision process (CMDP) formalism (Altman 1999h. In infinite CMDPs, which are characterised by large continuous state and action spaces, traditional solution techniques include linear programming and dynamic programming with Lagrangian relaxation. Following their empirical performance in high-dimensional control tasks (Lillicrap)
ct al.
2015; Mnih et al.] 2016), policy gradient algorithms have become particularly popular option for safe
RL
rontrol applications (Achiam et al. 2017 Yang et al. 2020; Ding et al. 2020 Liu al. 2021b Xu
ct al.
2021 Paternain al. 2023 Ying et al. 2023 Wu et al. 2024).
The robustness to mismatches in training and test transition dynamics has been the main subject of interest in the robust MDP (RMDP) framework (Lyengar 2005 Nilim & Ghaoui 2005), which formulates robust policies by training them on the worst-case dynamics model within a plausible set called the uncertainty
set. The framework has led to a variely of theoretically sound policy gradient approaches (Ho el al.] 2021
Zhang et al.] 2021 Kumar et al.) 20233 Kuang et al., 2022 Wang et al.) 2024 [i et al., [0233 Zhou et al.
2023: Wang et al. 2023). Recently, the approach has also branched out into the robust constrained MDP
(RCMDP) framework (Russel et al. 2020 2023 Wang et al. 2022 Bossens
2024 Zhang et al. 2024 Sun
et al. 2024 which seeks to provide robustness guarantees to CMDPs.

---

Published in Transactions on Machine Learning Research (12/2025)
The framework of RCMDPs is newly emerging and hence the theoretical development lags behind compared to CMDPs and RMDPs. At present, few challenges have hampered the progress of RCMDP policy optimisation. First, since the framework is based on a worst-case cost function and one or more additional worst-case constraint-cost functions, it is challenging to implement in a single simulator since cach of the robust cost functions may turn out to be based on a different transition kernel. This has lead to practical objectives that, do not meet the original objective (Russel et al., 2020) or which only work for a discrete set of transition kernels (Mankowitz et al.) 2020). Second, the state-of-the-art CMDP techniques for policy optimisation and RMDP techniques for adversarially optimising the transition dynamics have not yet widely made their way into the RCMDP literature, which has lead to a lack of theoretical guarantees. In RMDPs, state-of-the-art results are obtained for mirror descent based policy gradient algorithm (Wang et al. 2024), which applies mirror descent in the policy space and mirror ascent in the transition kernel space. In CMDPs, the policy mirror descent primal-dual (PMD-PD) algorithm is a related mirror descent based policy gradient algorithm which provides (log(T)/TT) convergence rate is obtained in the oracle-basod sctting and an ((1/T!/3) convergence rate in the sample- sample--aseddee setting QLu et al., 20211b) We then pose the question: using mirror descent based policy optimisation, is it intrinsically more difficult to optimise RCMDPs, or is it possible to obtain similar convergence rates?
With the aim of solving these challenges and providing an affirmative answer to the above question, we draw inspiration from the robust Lagrangian objective (Bossens] 2024) and the success of mirror descent, optimisation in RMDPs and CMDPs (Wang et al.) 2024 Liu et al. 2021b). We show that it is indeed possible to obtain convergence rates similar to fample-bases PMD-PD in the sample- based RCMDP setting. For theoretical analysis, we contribute Robust Sample-based PMD-PD, which extends the theory of Liu ct al. (2021b) and Wang et al. (2024) to the RCMDP sctting, while focusing on the softmax parametrisation within the sample-based setting. Doing so, we achieve the ((1/T//3) convergence rate as also obtained by (non-robust) Sample-basee PMD-PD. We then also extend the analysis to non-rnctan RCMDPs, albeit with a weaker sample-based convergence rate. For a practical implementation, we formulate MDPO-Robust- Lagrangian, which introduces a robust Lagrangian to Mirror Descent Policy Optimisation (MDPO) (Tomar empirically by comparing it to robust-ccosstrained
et al.) 2022p. We evaluate variants of PPO-Lagrangian (Ray al.) 2019) and RMCPMD (Wang et al.) 2024), and find significant improvements in the penalised return in worst-case and averago-case test performance dynamics in the
uncertainly set.
In addition to techniques drawn from Liu et al. 2021b), Wang et al. (024). and Tomar et al. (0022), our work designs novel tochniques for thcoretical analysis and contributes tools and results for practical experiments. In theoretical development, our work designs the following techniques:
Bounding the error due to sub-optimal dual variables: the proof of Theorem 4.2 of Wang et al. (2024) provides a result. for bounding the robust regret in RMDPs by adding the tolerance of TMA and the regret on the current transition kernel. To extend this reasoning to RCMDPs, we
provide an upper bound on the robust Lagrangian regret (Lemma S which in addition to these two terms also considers the suboptimality of the dual variables. This additional error is then shown to vanish in an average regret sense duc to the constraint-costs averaging to O(c) across iterations, where e > 0 is the error tolerance (Lemmaa 29
Bounding errors due to transition kernel changes: a challenge in applying the telescoping analysis of Liu et al.] (2021b) to RCMDPs is that some of the terms no longer cancel since the transition kernel changes after the policy update. To ensure that this analysis is still possible, Lemma 24 and Lemma 25 bound the error introduced by changes in the transition kernel using different telescoping sums.
Approximate TMA: previously, the TMA algorithm of Wang et al. (024 relied on oracle information. To extend the algorithm to the sample-basod sctting, we have designed the Approximate TMA algorithm, which approximates the value function to perform mirror descent on transition kernels, and we derive its sample complexity as ((1/e).
2

---

Published in Transactions on Machine Learning Research (12/2025)
Continuous pseudo-KL divergence of occupancy: present a pseudo-KL divergence for continuous state-action spaces and show it is Bregman divergence, making PMD-PD techniques applicable to continuous state-action spaces.
while Wang et al. 2024 provides an analysis of TMA only for s-rectangular RMDPs and derives oracle-based convergence rates for the policy optimiser, our work applics the Appproximate TMA algorithm to non-roctangular RCMDPs and then derives a full sample-based analysis of the full algorithm optimising all three parameters (T,
Non-rectangular RCMDPs:
From experimental perspective, highlight the following novelties:
Comprehensive ablation study: our study compares MDPO, PPO, and MCPMD algorithms for MDPs, CMDPs, RMDPs, and RCMDPs across three problem domains, including tests on the uncertainty set where the return and different penalised returns are evaluated.
Scalable implementation: the practical algorithm is highly scalable, making use of function approximators and other deep RL tools, as opposed to the pure Monte Carlo considered in Wang et al. (024).
Learning rate schedules: we also present an empirical comparison of learning rate schedules, including traditional schedules fixed an linear schedules (Tomar et al.) 2022), geometric schedules (Xiao) 2022 Wang al. 2024), and newly designed restart schedule. We show that for RCMDPs, the best performance is obtained by the MDPO-Robust Awg.ootettt-mmeeeee-eeeeeaaea variant under batch-based restart schedules.
2 Related work
2.1
Robust constrained objectives
Russel al. (2020] proposed the robust constrained policy gradient (RCPG) algorithm, which solves the inner problem based either the robust cost or the robust constraint-cost, which ignores at least one part of the robustness problem in RCMDPs. Solving the RCMDP objective directly, the R3C objective (Mankowitz
ct al. 2020 combines the worst-case costs and worst-case constraint-costs by running distinct simulators with different parametrisations,, each being run for one step from the current state. This unfortunately cannot be realised within a single simulator and only applicable for discrete parametrisation Additionally, is also computationally expensive, even more so when there are multiple constraints. Alternatively, the robust Lagrangian objective trades off the cost and different constraint-cost according to whether the constraints are active while requiring only a single simulator with dilferentiable parameters [Bossens] 2024
In this paper, we use the robust Lagrangian objective with multiple constraints and rather than performing a single-step transition kernel update, we perform multi-stop updates to the transition kernel at cach macro- iteration, a double-loop manner, to ensure that a near-oplimal solution to the inner problem has been found, which in turn allows to provide guarantees on the near-optimality of the policy solving the robust Lagrangian objective. Assuming that there exists at least one policy that is strictly feasible for all the constraints under all dynamics in the uncertainty set, the policy that optimises the robust Lagrangian will satisfy the worst-case constraint-costs and will, due to complementary slackness, optimise the worst-case value.
2.2 Adversarial transition kernels
Techniques for the design of adversarial transition kernels are of general interest for reinforcement learning. They represent different trade-ofls between realism, scalability, computational cost, and sample elliciency. In the context RMDPs and RCMDPs, they are used in the inner problem, which computes the worst-case transition kernel for the current policy. In general, convex uncortainty and rectangular uncertainty sets are required to make the problem tractable, since non-convex sets and nontrcctag set are in general NP-Hard (Wiesemann al. 2013
3

---

Published in Transactions on Machine Learning Research (12/2025)
The scalability of these techniques is key challenge. Linear programming based techniques (Russel et al. 2020) and techniques based on small subset of simulators (Mankowitz et al. 2020 are not scalable. Instead, sradient-based methods can potentially be performed at scale. In RMDPs, gradient descent techniques for computing the inner problem have been proposed. Unfortunately, many previous techniques do not have known guarantees (Abdullah et al. 2019 Bossens 2024). Recent work has proposed transition mirror ascent (TMA), which comes with an (1/TT) convergence rate the oracle-based setting under convex rectangular uncertainty sets when using fixed learning rates, and O((1 (((1->))*) "²) convergence rates when using geometric schedules for the learning rate (Wang et al.
2024). A similar guarantee was earlier provided with a projected subgradient ascent algorithm, under slightly less general conditions, i.c. when the uncertainty set is a rectangular ball (Kunar et al. 2023).
In RCMDPs, the Adversarial RCPG algorithm [Bossens 2024) provides a neural representation for transition kernels. Unfortunately, the algorithm does not have known thcoretical guarantoes. Our work takes note of the oracle-based convergence guarantees of the TMA algorithm of Wang et al. (2024). and extends the approach to design an algorithm for approximate TMA with O(1/74/2) convergence rate in the sample-based setting. The result corresponds to slightly improved oracle-basee rate O((1 0(11+))) compared to the analysis of TMA in Wang ct al. (2024) and further provides the additional sample complexity and estimation error from the estimation of the Q-values.
Despite the NP-Hardness result, recent work has also explored non-rectangular sets albeit with much weaker convergence guarantees (Li et al.] 2023 Kumnr et al. 2025). In addition to a non-tractable but globally optimal solution, [i et al. [2023) provides a conservative policy iteration algorithm for transition kernels that converges to sub-optimal solution of an RMDP, with an error increasing based on the degree of non-rectanguulariyy While the rates in the paper hide the oracle for the value or gradient computation, it is the first to provide an approximate solution to general non-rectangular uncertainty sets. We exploit a similar technique and note its relation to the TMA algorithm, and then further analyse the overall algorithm with policy optimisation in the context of the non-roctangular RCMDP setting.
Obtaining tight and statistically based uncertainty sets important for RMDP and RCMDP algorithms. The & norm over the probability space is arguably the most widely used uncertainty set in the RMDP literature. For our purposes, it is convenient to use and ariscs naturally in our regret bounds. First, many other distance measures and statisties can be directly related to the l norm, including bap total variation distances, Chi-squared sets, student-t statistics, Hoeffding or Chebyshev inequalities, the total variation distance, and KL-divergences. Beyond their statistical derivation and simplicity, by sets are also fairly easy to project back onto the feasible set. The KL divergence is another distance metric with known analytical form for the transition kernel (see Table 7 in AppendixA) and with a direct connection to the norm. Second, as shown in Lemma 24 general uncertainty sets can be related to the & norm, which appears naturally in the cumulative regret computation, and in this sense our main theorem is flexible to different divergences. In our convergence rate analysis, ly sets with small uncertainty budgets can potentially reduce one of the constants, although otherwise leading to the same convergence rate as in general uncertainty sets. Specialised algorithms have also been designed for the construction of tight weighted e, uncertainly sets while maintaining Bayesian confidence guarantees (e.g. Behzadian et al. (2019))
Alternative models of uncertainty, suitable for indirect parametrisation and compatible with continuous state-action spaces, include examples such as the double sampling uncertainty sets, integral probability metrics uncertainty sets, and Wasserstein uncertainty sets (Zhou et al. 2023 Abdullah et al. 2019 Hou et al. 2007). Similarly, bg sets can also be applied to indirect parametrisations, which is compatible with the TMA algorithm (Wang et al. 2024). As supported by our experiments, Lagrangian TMA methods can similarly be applied with indirect parametrisations, such as the Gaussian Mixture PTK and the Entropy PTK (Wang et al. 2024).
2.3 Policy optimisation algorithms
Different policy opimisation algorithms have been proposed for RCMDPs and the related framework of CMDPs. As summarised in Table [ the algorithms proposed in the literature work in the primal space, dual space, or a combination thereof, and they provide different guarantees under varying parametrisations.
4

---

Published in Transactions on Machine Learning Research (12/2025)
In the CMDP literature on policy optimisation, many of the algorithms do not come with formal guarantees apart from local optima improvement in the feasible space (Achiam et al. 2017 Tessler et al. 2019 Yang et al, 2020g. Ding et al. (2020) present a primal-dual technique, NPG-PD, which obtains an (11 rate in the oracle-based sctting for the softmax parametrisation, which extrapolates to an ((1/T1/4) bound in the sample-based setting. The work also presents a rate for a general parametrisation although it is considerably worse for the constraint-cost. CRPO applics NPG in the primal space with backtracking steps to ensure the constraint-cost. remains satisfied, and is able to achieve comparable rates to NPG-PD (Xu et al, 2021). State-of-the the-art results of ((1/T)/3) in the sample-based setting and (11/T) in the oracle- based setting are obtained by PMD-PD, which applies a primal-dual mirror descent algorithm specifically with KL-divergence as a Bregman divergence (Liu et al., 2021bb. Unlike other techniques using regularisation (Cen et al. 2022), the algorithm provides unbiased convergence results (i.e. they are expressed as the solution to the unregularised Lagrangian). PMD-PD does not account for variability in the transition kernel, and therefore we extend it to the RCMDP setting, obtaining comparable rates in the sample-basod setting.
From the RMDP literature, the techniques by Wang et al. (2024) apply to the based rectangular RMDP setting, where for some b E (0, 1) they achieve a sfate-of-the-an O(b²) convergence to the global optimum under a direct paramctrisation of the policy and the transition kernel. For the softmax policy parametrisation, they report an O(1/T)) oracle- based convergence rate in Theorem 4.5, a theorem which formulates the regret on the RMDP of interest based on the regret of an MDP optimiser passing through the same policy at the same iteration and with the transition kernel fixed to the nominal transition kernel at that iteration. However, their supporting Lemma B.5 incorrectly relies on a specific, favourable policy initialisation, which cannot. be done in practice, rather than a general policy initialisation. The lemma also holds for any policy parameters at any iteration, such that no inference can be made about the regret of particular policy in the RMDP optimisation simply by virtue of passing through the same parameters. Li et al. (2023) provides an O(1/T"/4) oracle-based result for non-rectangular RMDPs, the first convergence result for the global optimum of non-roctangular RMDPs considering the full algorithm solving both policy optimisation and the inner problem, while only requiring an approximate oracle for the gradient. The challenge of non-rectangularit shows up not only in the added complexity but also in additional error based on the degree of non-rectangularity. These works do not account for constraints or the samples to estimate the gradient; our work derives convergence results for the more challenging sample-based rectangular and non-rectangular RCMDP settings while maintaining similar global optimality properties.
In the RCMDP literature, policy optimisers either come with no policy convergence guarantees (Russel et al. 2020: Mankowitz et al.] 2020 Bossens 2024), basic fcasibility and improvement results (Sun ct al. 2024h. or sub-optimal convergence points (Russel et al. 2023 Wang et al. 2022). Our sample-baser theory for roctangular uncertainty sets provides results on par with CMDPs, namely an ((1/T1/3) convergence rate to the robust Lagrangian optimum, result which is on par with the state-of-the-at PMD-PD algorithu (Liu) et al. 2021b). This compares favourably to the ((1/T1/4) oracle- based rate of Wang et al. (2022) which comes only with local convergence guarantees. We also provide sample-based theory for non-rectangular RCMDPs, where an O(1/T1/5) rate is achioved. Both of our mentioned convergence rates account for all the samples required, including those for gradient estimation, transition kernel updates, policy updates, and dual variable updates.
Our algorithm also practical in the sense that it can be implemented with deep RL tochniques. In particular, we use MDPO (Tomar et al. 2022 as the backbone of our algorithm's 's implementation. The technique has been previously studied in traditional MDPs as highly performing alternative to trust region based deep policy optimisers (e.g. PPO, Schulman et al. 2015)) and TRPO, |Sculman et al. (217))) ). While the clipping implemented in PPO also allows a KL-constrained property, it often loses this property since due to averaging effects the policy is updated even if its clipping ratio is out of bound for some state-action pairs. TRPO computes the Fisher information, which can be expensive, and performs a KL constraint with a reversed order (i.e. ( 7)) instead of (TI as used in mirror descent). The MDPO backbone leads to a novel algorithm for RCMDPs as well for CMDPs, which turns out to be highly performant as an alternative to PPO-Lagrangian (Ray et al. 2019).
5

---

Published in Transactions on Machine Learning Research (12/2025)
Table 1: Overview of theoretical guarantees for policy optimisation algorithms CMDPs and RCMDPs. MDP indicates the type of MDP, with prefixes C, R, and RC having their obvious meanings, while rR indicates rectangular robust and nR indicates non-rectangular robust. Param indicates the parametrisation. Oracle rate indicates the convergence rate in the oracle setting. Sample rate indicates the convergence rate in the sample-based setting. Other notations: O hides logarithmic factors from the big O notation; b E (0, 1).
Algorithm
Algorithm type
MDP
Param
Convergence
Oracle rate
Sample rate
point
Adhaam
region dual program with locktracking
gemeral
lessible
improve
ment
Tosler et
primai-dual projection
general
optimum loca opthoum
Vang al
220
trust region with projection
C
goneral
Ding d a X12
priunl-Lud NPG with projected subgradient descent.
sollumx
globel oplimum
00/2aay
Oupra Ou/rang ourrus
al
primal uncnsttsinnd NPG with backtracking
softmax
global optimum
00//7//3)
Liu et ml.
202
primul-dunl mirror descent
C
softmax
global optimum
00/TT
Waus
2722
double-loop loop mitror desceat /ascent
IR
direct
global optinuam
O
G al. 2123
projected descent and CPI ascen
nR
direct
global with error 6p
00//744)
Russel Mu
2023
primm--dual, linear programmiing inner problem primul-dunl, projected deseent with robuss, TD
#RC
general
locad optimum
Wany
RRC
geurra
stationary
00/711)
Sum ot A1
4724
trust region with projection
/BC
general
feusible
impprove-
Ours
donble-loop primal-dual mirror descens/ double-loup primal-dual mirror descent, ancens
:RC
softmax
global optimum
00/7449 01/r1/
Ours
aRC
softuax
global with error dp
3 Preliminaries
The setting of the paper is based on RCMDPs. Formally, an RCMDP is given by a tuple (S,A, P. Co. Clom: P,7), where is the state space, A is the action space, p A(S) is the starting distribution, cu A + E is the cost function, 4; : S x A -> TR, [m] are constraint-cost functions, P is the uncertainty set, and y E [0, 1) is discount factor. To denote the cardinality of sets S and A, use the convention $ : [ and A = [A]. In RCMDPs, at any time step 1 I= O,.... 0o, an agent observes state E S, takes an action ar E AA based on its policy π E 11 C (A()))) and receives cost co(st, a)) and constraint-cost signals cy a) for all j E [m]] = (1..... m) Following the action, the next state is sampled from a transition dynamics model p E P according to 8141 ~ p(-1st, at). The transition dynamics model p is chosen from the uncertainty set P to solve a minimax problem. In particular, denoting
xc Σ
V (p) Esorp
(
(1)
and
Vp) = Eeo~p
Σ
r'co(s),
(2)
1
the goal of the agent in traditional RCMDP is to optimise minimax objective of the form
min sup V (p)
s.t.
Vi (p) s 0, Vj [m]] PYE
sup
(3)
pEP
The objective in Eq. 3q.Bor does not represent a single plausible transition kernel for the CMDP since the different suprema are usually met by different transition kernels. In practice, a choice is often made to take the supremum of the traditional cost only (Russel et al. 2020). Since this ignores the constraint-coste one may instead optimise related problem, namely the robust Lagrangian RCMDP objective (Bossens 2024).
m >x=>>VV (2v2p(o)) }.
min ((T) = sup max pEP X20
V=+(pp) + Σ
(4)
which only requires a single simulator and will allow optimisation to focus on constraint-costs if they are violated and on the traditional cost otherwise. If the inner optimisation problem is solved pk iteration

---

Published in Transactions on Machine Learning Research (12/2025)
k, this in turn corresponds to equivalent value function traditional MDP
Taleghan & Dietterich
2018
Bossens
2024 according to the Lagrangian value function,
F. (
00 Σ
co(s), + Σ (sn
m
|s0 ~ p. a.p
(5)
which has single cost function defined by
- a) + (s, and no constraint-costs. The multiplier A denotes the vector of dual variables at iteration h and AR.j denotes the multiplier for constraint E [m]] at iteration k. Occasionally, in proofs where the iteration is not needed, the iteration index will be omitted. In the context of dynamic updates to X, we often emphasise the value À by including it as a pararameter the notation V n. (p; X).
A convenient definition used in the following is the discounted state visitation distribution
o y PP(ss = s|s0, Tk. pb)
(s) = (1 Boo
(6)
and the discounted state-action visitation distribution
d (8, a) = =(1 -1 20 Σ
PP((s = =8 8,04
a/s0: Th pk)
(7)
For any optimisation problem min f(x), we define three notions of regret:
(mx) f(x")
(regret)
K
(xxx -(xx)
(cumulative regret)
K
Σ f(x)) - f(x*)
(average regret)
K
where {ΛK]aR) represent the iterates of the algorithm and x² is the optimum. Based on these regret notions, the paper provides sample-based analysis in terms of how many samples required until the regret is below some small threshold >> 0.
A first objective of interest is the maximisation over transition kernels within Eq. 3 i.e.
sup V Ap; pEP
(8)
where À E R and II are fixed. Our analysis aims to show that is possible to obtain, within limited mumber of samples using only approximate evaluations of the Lagrangian w.r.t. the current parameters, near-optimal maximiser, i.e. transition kernel with limited regret,
sup V Ap) Vap (p; A) Se,
(9)
PEP
where p is the transition kernel being optimised at iteration t 2 1.
A second objective of interest the minimax optimisation problem Eq. 3 itself. To design an optimal
algorithm for the full RCMDP problem, the main goal of the sample- based analysis is to minimise the average regret w.r.t. Eq. 4
K Σ ((T)) - se,
(10)
within limited number of samples. To count the samples, we account for those used for the evaluation and optimisation of the policy and the transition kernel, for full sample-based analysis.

---

Published in Transactions on Machine Learning Research (12/2025)
4 PMD-PD for CMDPs
We briefly review the PMD-PD algorithm for CMDPs (Liu et al. 2021b). PMD-PD uses natural policy gradient with parametrised softmax policies, which is equivalent to the mirror descent.
iteration E {O...., - 1} and policy update t E (O....,tt.. t within the iteration, PMD-PD defines the regularisod state value function,
= =x(ayl1)) )
E
Σ (+((1, ar) + a
80 8, m
(11)
where p fixed transition kernel, (5,, a) = co(s), ar) + Ein (Du.s + T1 V..Ve.pu (5 a)) and a 2 the regularisation coeffient. The regularisation implements a weighted Bregman divergence which similar to the KT-divergence. The augmented Lagrangian multiplier Ào.J AR. + 7/ ViJ Vi is used to improve convergence rosults by providing more smooth Lagrangian compared to techniques that clip the Lagrangian multiplier. At the end of each iteration A is updated according to Ak. = max {
(AK. + TA Vil
me- P -7 Vi M841.PP441
Analogous to 11 the regularised state-action value function is given by
(x a (a(a)s)) + 3
Vo
(12)
While the bold indicates the summation over + m terms (i.e. the costs and constraint-costs) in Eq. tilde notations will be used throughout the text to indicate the use of the augmented Lagrangian multipliers dg. Note that since all the costs and constraint-costs range in [-1,1],
5 the
a)) < +1+ Σ
Akj + 1 1-7
(13)
Consequently, for any set of multipliers X E R", the Lagrangian is bounded by -)) P3, based on the constant
7A (1-7)
B=
(14)
j=1
for the augmented Lagrangian, and according to
m Fx =
(15)
for the traditional Lagrangian.
Note that this can be equivalently written based on the weighted Bregman divergence (equivalent pseudo KT-divergence over occupancy distributions),
B de (
Tx)
Thop Ed
Σ
Σ
(((ss)
( (T
(16)
sES
according to
Qa ps (s.
a
B ( Tk).
(17)
In this way, PMD-PD applics entropy regularisation with respect the previous policy as opposed the uniformly randomized policy used in Cen et al. (2022). allowing PMD-PD converge to the optimal unregularised policy opposed to the optimal regularised (and sub-optimal unregularised) policy.
8

---

Published in Transactions on Machine Learning Research (12/2025)
With softmax parametrisation, the policy is defined as
No (a(a)))
(18)
Exe e'
Under this parametrisation, the mirror descent update the unregularised augmented Lagrangian with the KL-divergence as the Bregman divergence can be formulated for cach state independently according to
aV -()))())) a0(s..) (-(11)) ) + oy (T(())))) -
* ++ (+1s) arg min mell
,
1
- (6) (Oozz (, + 1 (ian(
arg min mell
(oizlls, (,(()))))))) + 1 DKL a (111)))
arg min nell
(19)
where the last step defines = - 4)/ // (s) and subsoquently removes the constant I-y dp
from the minimisation problem. Treating Qx v as any other value function, Eq. 19 shown to be equivalent the natural policy gradient update, as discussed by works in traditional MDPs Zhan et al. 2023 Cen et al.
2022 In particular, based on Lemma 6 in Cen et al. (2022) the update rule derives from the properties of the softmax parametrisation in Eq. 18
(als) = (1(s) (m) (ak(a
(20)
#
where t/t is the +++ 1'th policy at the k'th iteration of the algorithm and (s) is the normalisation constant.
Denoting T T= = lk: the oracle version (with perfect gradient info) converges at rale O(log(T)TT) in value and constraint violation. PMP-PD Zero (oracle version aiming for zero constraint violation) achieves O violation with the same convergence rate for the value. Finally, the sample-based version, which has imperfect gradient information, was shown to converge at a rate (3/ where T denotes the total number of samples.
5 Robust Sample-based PMD-PD for RCMDPs
Having reviewed the performance guarantees of PMD-PD, we now derive the Robust. Sample-based PMD-PD algorithm for RCMDPs. The algorithm performs robust training based on Transition Mirror Ascent (TMA) [Wang et al. 2024 over the robust Lagrangian objective (Bossens] 2024 Using TMA provides principled way to compute adversarial dynamics while maintaining the transition dynamics within the bounds of the uncertainty sets. Such uncertainty sets allow for rich parametrisation such as Gaussian mixtures, which can estimate rich probability distributions, and entropy-based parametrisations, which are motivated by the optimal form of KL-divergence based uncertainty sets (see Table 7 for these examples). The algorithm takes place in the sample-based setting, where the state(-action) values are approximated from limited number of finite trajectories. With an average regret bound Ó(1/T2/3), results are in line with the Sample-based PMD- PD algorithm. The resulting algorithm is given in Algorithm 3 While the first subsection develops the theory of TMA in the oracle setting (Section 5.2). where exact values and policy gradients are given, the subsequent subscctions derive convergence results for the sample-based setting, where values and policy gradients are estimetes. In particular, Sention 5.3 proposes and analyses Approximate TMA, an algorithm for TMA within the cample-based setting, and Section 5.4 proposes and analyses Robust Sample- based PMD-PD the full sample-based RCMDP setting. Further extensions are then considered, namely non-rectangular uncertainty sets (Section 5.5 and continuous state-action spaces (Section 5.6p. The last subsection (Section 5.7 then proposes a practical implementation.
5.1 General assumptions
As shown below, the assumptions of our analysis are common and straightforward.
9

---

Published in Transactions on Machine Learning Research (12/2025)
Assumption 1 (Bounded costs and constraint-costs). Costs and constraint-costs are bounded in [-1, 1].
The boundedness assumption is ubiquitous in the MDP literature although some authors prefer the range 1] or some other constant. For our purposes, it implies that all 1 + m value functions in the Lagrangian are bounded by T-y
Assumption 2 (Bounded range of the dual variables). The dual variables are upper bounded by Bx 0.
We assume that the dual variables are bounded by constant, such that also Fx = O(1), which allows bounding the regret of policy with respect to the optimal Lagrangian in Eq. to be bounded. The variables can take wider range compared to other primal-dual algorithms due to the use of the augmented Lagrangian instead of clipping. The parameter is expected to be large for domains with highly active, restrictive constraints. The assumption is not particularly strong since it may be that BA > (I-7X the clipping bound usually taken for primal-dual variables (Ding et al. 2020). While with the modified Lagrangian update, the iterates obtained in the algorithm are always bounder, Assumption the maximising dual variables of cach iterate. In the sample complexity analysis of Robust Sample- based PMD-PD, the assumption is only required to limit the average regret induced by mismatch of the dual variable with the optimal ones for that macro-iteration (see Lemma 29 There, the assumption could be removed when the dual variables are, on average, close their optima of their respective inner problems.
2 additionally allows bounding
Assumption 3 (Sufficient exploration). The initial state distribution satisfies pus) > for all s E S.
This assumption is common in MDPs. It ensures that when sampling from some μ instead of the initial state distribution p. any importance sampling corrections with μ and di are finite. In particular, ensures that for any transition kernel p and any policy æ that the mismatch coefficient Mp(T): = d7 is finite MMii
et al. 2020 This is also useful for RMDPs [Wang et al. 2024 since
:= sup PEP,*EII
Mp(T)
(21)
is also finite. Similarly, via Lemma 9 of Mei et al. (2020), it ensures U, = inf (=(())))))) 0 when following softmax policy gradient, where (,(s) is the action for state s under the optimal deterministic policy under the transition dynamics p. Again, this also finds its use RMDPs (Wang et al.. 2024 where follows that
inf Up 0. PEP
(22)
We use Eq. 22 to upper bound the KL divergence (Lemma 25 by further noting the relation to the global optimum T pp):
OKU= inf Th Ta(a(())ss)
<
inf TR Ta (s)[s) xES,K21
inf (s)ss)
(23)
PEP,ESAA21
sES,k21
Assumption 4 (Slater's condition). There cxists a slack voriable <> O and (al least one) policy म with (p) < - for all j [m] and all p E P.
The condition is an extension of the traditional Slater's condition for CMDPs. The assumption of Slater points not strong: since the constraints are based on expected values, they take on real values. Therefore, if it possible to obtain the constraint-cost of zero, is almost. surely true that one can also obtain a negative constraint-cost (however small the slack variable). The possible non-negativity of instantancous constraint-costs does not matler since al least very small positive budget would be allowed.
In traditional CMDPs, Slater's condition implies strict feasibility of the constraints, zero duality gap, and complementary slackness for any convex optimisation problem, of which the CMDP is an instance due to its equivalence to a linear programming formulation (Altman 1999). The assumption of Slater points is common in CMDPs, and it is inherited from (Liu et al. 2021a). It is a ubiquitous but often hidden assumption when using dual and primal-dual algorithms, since it needed to satisfy strong duality, such that min maxx20 V Vx.((::)) max min V (p: X). Many constrained RL algorithms do mention
the assumption explicitly (Achiam et al. 2017 Liu et al.
2021b Ding al. 2020 2021 Note that we do
10

---

Published in Transactions on Machine Learning Research (12/2025)
not require knowledge of the parameter Ç while other primal-dual algorithms (Ding et al. 2020 2021 need to know the parameter to clip the Lagrangian. Another approach, which assumes a Slater point but also does not require knowledge of C (Germano et al. (024)) bounds the dual variables by showing a strong no-regret property for both the primal and the dual regret minimizers. Approaches without Slater's condition are
possible using primal linear programmiing (Altman 1999; Efroni et al. 2020). Unfortunately, such techniques are less practical due to requiring estimates of the occupancy measure.
Assumption D is slightly more restrictive than in traditional CMDPs due to the requirement of the condition to hold for all p P. The condition of having subset of the policies being able to strictly satisfy all the constraints for all the transition dynamics reflects the RCMDP objective in Eq. 3 since it is presumed that the worst-case dynamic with respect to the constraints is solvable. For our purposes, the assumption ensures each of the individual CMDPs in the uncertainty set can be individually solved without duality gap similar to Liu et al. (2021b) and that the dual variable optimum and iterates (sce Lemma 26 and Lemma 28 can be bounded by a constant that can be significantly smaller than the B, that bounds the space of dual variables.
Due to the occupancy being a function of an induced transition kernel which is potentially different for each policy, zero duality gap may be hard to guarantee for RCMDPs even with Slater points (Wang et al. 2022). However, our sample- based analysis provides an average regret upper bound with respect to the (primal) global optimum of the RCMDP "r",,",A" using Lemma g which is derived based on information from the iteration of the algorithm, namely the error tolerance of LTMA, the suboptimality of the dual variables, and the Lagrangian at (TT", Pk, Ax-1). Such errors are then shown to vanish in an average regret analysis.
Before stating the next assumption, we require the definition of rectangular uncertainty sets.
Definition 1 (Rectangularity). An uncertainty set is (s, -rectanaraa if it can be decomposed as P (s.))ESx Pa.a where Ps.a C A(S). Similarly, it is s-rectangular if it can be decomposed as P X.es Pa
where Ps C (SS).
With the above definition, our assumption on the uncertainty set is as follows.
Assumption 5 (Convex and rectangular uncertainty set). The uncertainty set is s-rectangular or (s, a)- rectangular (Def. [ and is conver, such that for any pair of transition kernel parameters E.E' E Us, and any a E 1], if Pę, Per E P then also Poş+(1-a) E P.
The convex set assumption ensures updates to the transition kernel will remain in the interior so long as it is a line between two interior points, a common assumption for mirror descent which is also needed for TMA (Wang et al. 2024). The assumption is standard (often hidden) assumption in gradient algorithms to ensure the parameter remains in the feasible set.
type
The roctangular uncortainty set assumption is satisfied for most common uncertainty sets, e.g. statc-action conditioned &, and & sets centred around nominal probability distributions. In our main theorem, a tight rectangular by uncertainty set used in Lemma 24 to provide an improved upper bound on the average regret, although the same convergence rate is achieved for general uncertainty sets albeit with a larger constant. While Wang et al. (0244) mentions the policy optimisation part of their algorithm works with non-rectangular uncertainty sets in principle, the guarantees of the TMA algorithm only apply to reclangular uncertainty sets, where it can provide an ascent property to guarantee an increase in the objective. Consequently, Lagrangian TMA algorithms inherit this property.
Proposals for solving the inner problem of non-rectangular uncertainty sets do exist but most results are not encouraging. As noted by Wicsemann et al.] (2013), the inner loops of non-rectangular and non-convex uncertainty sets are NP-Hard problems. Other alternatives include r-rectangular uncertainty sets, which could help reduce the number of distinct factors included to compose the uncertainty set. Recent work shows that r-rectangular and non-rectangular frameworks are only tractable if one assumess costs with no next-state dependencies, an assumption that may undermine their usefulness (Grand-Clément et al. 2024).
However, recent research has also highlighted some benefits of non-rectangular uncertainty sets, such as allowing statistically optimal confidence regions (Li ct al. 2023) and covering the maximum likelihood areas rather than the edges (Kumar et al. 2025). These works also introduce techniques for approximately solving the inner and outer problems in the context of RMDPs. To supplement our analysis of rectangular sets, we
11

---

Published in Transactions on Machine Learning Research (12/2025)
also consider non-rectangular RCMDPs in Section 5.5 The analysis uses the conservative policy iteration
algorithm defined for transition kernels in Li et al. 2023), which treats policy iteration special case of Approximate TMA.
Note that when using parametrised transition kernels, it is convenient to formulate an uncertainty set in the parameter space, which for a parameter & we denote as Mg. A few examples of parametrised transition kernels (PTKs) and their associated parametrised uncertainty sets can be found in Table 7 (see Appendix (A] including the Entropy PTK (Wang et al. 2024), which presents parametrisation related to the optimal parametrisation for KL divergence uncertainty sets of the form Pa.e {p (pL (p. ((-ss,)))))))) n3 (Nilim & Ghaoui 2005), and the Gaussian mixture PTK (Wang et al.] 2024), which is able to capture a rich set of distributions for each state-action pair. Such uncertainty sets can be considered as general uncertainty sets although they are often also contained within an bg set.
5.2 Global optimality of Lagrangian TMA
As shown below, Lagrangian TMA (LTMA) demoustrably solves the maximisation problem in the robust objective (sce Eq. 4 by performing mirror ascent on suitable PTK. Note that the analysis follows closely that of Wann al. (0024), where the Lagrangian and the weighted Bregman divergence are explicitly separated in this subsection.
The first step of our analysis of LTMA is to derive the gradient of the transition dynamics.
Lemma (Tagrangian transition gradient theorem). Let Vp,ppp X) be the Lograngian, for a policy a E II, a transition kernel p E parametrised by &, and dual variables IR" Then the transition kernel has the gradient
1 VeVnp(p:ii 1-7 B Ve logp(s (. s, + (s
(24)
Proof. The result follows from Theorem 5.7 in Wang et al. 2024) by considering the Lagrangian as a value function (see Eq. 50
Note that the Lagrangian adversarial policy gradient in Bossens 2024g follows similar reasoning but there are two differences in the setting. First, due to the formulation of costs as co(8, a, s') rather than co a), the state-action value of every time step appears rather than the value of every next time step. Second, we show the proof for discounted Lagrangian of a potentially infinite trajectory rather than an undiscounted T-step trajectory. Third, in the following, we apply it not only to the traditional Lagrangian but also to the augmented Lagrangian and the augmented regularised Lagrangian.
The second step of our analysis of LTMA to show that optimising the transition dynamics Pe while fixing the policy x and the Lagrangian multipliers yields a bounded regret w.r.t. the global optimum.
Lemma 2 (Regret of LTMA). Let c' > 0, let æ be a fixed policy, let X E R be fired vector of multipliers for each constraint, let p' be the transition kernel at iteration t, and let p" be the transition kernel at the start of I.TMA. Moreower, let p² = arg minper V <P: A), let M := auPpeP,NEII Mp(T) be an upper bound on the mismatch coefficient as in Eq. [2 and let πp > O be the learning rate and op > O be the penalty parameter for LTMA. Then for any starting distribution p E A(S) and any s E S, the regret of LTMA is given by
V xx (p: A) - V pp (p;
2Fx
M
Op B B (p", p²)
(25)
t
71-
(p
where Fx defined according to Eq. 15 for the traditional Lagrangian and on Eq. 14 for the augmented Ff
Lagrangian. Moreover, if hp/ap 2 (1 B a. (p..P)) and t 2 2Fx, M+1 found such that
an é' -precise transition kernel is
V x (p; V Va (p: SE.
Proof. Following Theorem 5.5 in Wang et al. 2024), , it follows for any value function with cost in [0, 1] that
Va.gr (p) - Vn (0) 5
M
+ (p -7) B B5z (p' (1'10))
ap
(26)
(1 7)-
12

---

Published in Transactions on Machine Learning Research (12/2025)
Reformulating the Lagrangian value function (see Eq. 5 considering the bounds on the absolute value of the constraint-cost Eq. 13 and observing that the bounds on the (un-jaugmented Lagrangian lie in [-Fx, Fx]
(see Eq. 14 and
15 the result can be scaled to obtain
2F's ( M
V (x:p-(;;)) V (p:
+ Op
B on (p', PP))
t (1 (1- 1pp 7)
From the settings of hp/a, (1 7) xz (p' po) and 2 2F
c(117)}2 obtain
M+1
V (p: V (p: 2F M +1
sé.
>}
5.3 Analysis of Approximate TMA
While the above-mentioned LTMA algorithm was formulated in terms of exact policy gradient evaluations, such computations are intractable in practice. Now we turn to the design of an algorithm for TMA based on approximate policy gradient evaluations, which we call Approximate TMA (see Algorithm D Since it has not been proposed in carlier work, the algorithm will be presented functions. To maintain consistency across different value functions (including the Lagrangian and traditional value functions), we deal with their difference through factor C' > 0 that scales the maximal cost at each time step.
generic manner, i.c. for general value
To construct the Approximate TMA algorithm, the definition of the action next-state value function provides a useful short hand that is an essential part of the transition gradient for directly parametrised transition kernel.
Definition 2 (Action next-state value function (Definition 3.2 in Li ct al. 2023 )) For any cost function e: S:S x IR and starting distribulion p, the action next-stale value function for transilion kernel p and policy æ is defined as
Ga.l8,,, = E
8,40 = 6., T
(27)
1=0
It can also be wrillen as G s')) c(s, 8') + (b)) Wang et al. 2024
The directly parametrised transition kernel can now be written in terms of Definition 2 based the lemma below.
Lemma 3 (Partial derivative for approximate TMA). Under the direct parametrisation, the partial derivative of (p) has the form
1 d ( 1- _
V (p) Pr..a.a
(28)
Proof. The proof follows directly by applying Lemma. 5.1 of Wang et al. (2024 (or Lemma 3.4 of Li et al. 2023) with direct paranctrisation) to the approximate value function.
The resulting update rule is then given by
1
p² (1ss,a) arg sup (t) pep
17,0 (s, (x a, ag (p for all S A.
(29)
As a consequence this update rule, the value difference in p and p' can be bounded. particular, the ascent property of TMA (Lemma 5.4 of Wang et al.] (2024)) is a key result which provides proof based on rectangularity (Definition D to show that TMA increases the objective over iterations. For our purposes, it is used not only in the bracle-based I.MAA but also to prove related ascent. property for the Approximate
13

---

Published in Transactions on Machine Learning Research (12/2025)
TMA algorithm. The property, which is given below, notes that conditioning the state state-action, pushback property can be achieved, and this can be used to show that (under perfect gradient information) TMA updates always result in increasing value.
Lemma 4 (Ascent property of TMA (Lemmna 5.4 of Wang et al. (2024)) [)) Denoting Gr.((,r-)))
(x(a)s))z,p(8 a, :))E) for any p E Ps and E II, we have that
+ B(p" (+s, p' s B(p p' - b(, (-1s,-))
(30)
where B(p.g) is the unweighted Bregman divergence between and g. Morcover,
Va (p) Va (p) 50.
(31)
With imperfect information on the gradient, monolonic increase in value cannol be guaranteed. However, it is possible to bound the potential decrease, resulting in the following ascent property of Approximate TMA.
Lemma 5 (Ascent property of Approximate TMA). Let t 2 O be the current iteration, let V S - R be value function with instantaneous cost bounded in [-C, C₁ and let π E II. Suppose we have an estimate G. G:S S AxS- R of the action next-state value function such that
|Gmpp - Gr.p 11.0 SC
(32)
Then at iteration t 1, Approzimate TMA satisfies
26'
(p) - Vi (p) S
(33)
1-77
Using the first performance difference lemma (Lemma 23 and the ascent property (Eq. 31 we have that
Proof.
Va (p) - ((. 1
F
at p²+ (-1s, (s,
(Lemma 22
1
p
SES
AEA
F.
{aass (p'((11, - + (11s, Gr. (s,
p
SES
aEA
(p'(11s -p -pp''pp'((t0 (+(s Gx ( (s, - Gn
(decompasing)
d p
(s) Σ x(als)(p((1s,a) - p²+ (-1s,,) (s,a,) (s,
(s,a,.))
SES
aEA
(Eq.
31
Σ
p11 p
(s) Σ
a(a|s) (t,r(s, - Gxp (s, a, )) (1)s
- p ( (-Is,)))l
SES
aEA
(Hölder's inequality)
2
(Eq. 32
1 1-
With the ascent properly established, the theorem below bounds the regret of Approximate TMA. In the context of Robust Sample-based PMD-PD, the following algorithm can be used to obtain the updated transition kernel Pk+1 such that it closely matches Pt, the worst-casc transition kernel for particular macro-iteration, using the Lagrangian a value function. However, since it is also of independent interest, it is formulated more generally here with respect to any policy and independent of the macro-iteration.
14

---

Published in Transactions on Machine Learning Research (12/2025)
Theorem 1 (Regret bound for Approximate TMA). Let V - R be value function with instantancous cost bounded in [-C,C), fir E IT, and let p" E argsuP,EP Vp,( Suppose we have an estimate G 8 x A x S + R of the action neat-state value function which is é' e'prrice as in Eq. 32 and the step sizes follow (0) 2 a0( c(i-;) Bag (p= (p",p",, mp(t) 2 Ap(t - 1)/7 and ap(() = ap(0) > 0 for all t 2 1. follows
that approzimate TMA (Algorithm 1) yields regret bounded by
Fx (p) Vi S (1 1
3C
4M
+
d.
(34)
M
1
1-7
1 1-9
for all 2 1, where M is given by Eq.
21
Proof. The proof decomposes the approximate G-value into the true G-value and the estimation error, which allows using the ascent property of TMA and limited factor O(e'), followed by further derivations based on pushback properties. The full proof is given in Appendix C.2
Algorithm Approximate TMA.
Inputs: Discount factor Y E [0, 1), sample size Ma,,, episode lengths No.,, and learning rate schedule (t)t) for all & {0,.... ...,.....0 & 1}, penalty coefficient Op 0, cost function e: A R, initial transition kernel p", and fixed policy do
2: for t = .
3: Generate Mc.. samples of length No., based on a and p'-
4: if using function approximation then
Gapp' + arg minGeFa Ma., Eym (G(s)) ob st) - No,r1 o (f
5:
6: else
7:
for (8, ES A do 1 Ma. No.-1
(s,0,, = Mc. Exm Em //(s// ( where so = 8,00 = s'.
8:
end for 10: end if
11: if using direct parametrisation then
(-s,,)) = arg sup (t) (p. (s, an B.B
12:
(p.p) for all S x A.
13: else
14: g++l +- arg maxşeu (p) Vet F. (p).5) (p) -a Br (5.5")
Generic form
15: Define pt-1 P.t+1.
16: end if
17:
end for
Theorem relics on an e-precise estimate of the action next-state value, which can be established within ( as shown in the lemma below.
Lemma (Approximate action next-state value). Let k 2 0, let 8 E (0, 1) and let E fo...., the 1}. Moreover, let C> O be the marimal absolute value of the instantaneous cost. Then provided the number of trajectories for the estimator G (l.7 of Algorithm satisfies
27 -2Na,
28 A1'
Ma. 2
(1 (1-7) (1- log
Algorithm provides an approzimately correct estimate such that with probability at least 1 8,
No.
| Gz 20
1 for all t e (O...., 1.
(35)
Proof. The proof of this lemma is based on Hoeffding's inequality and is given in Appendix
15

---

Published in Transactions on Machine Learning Research (12/2025)
Due to the above results, the sample complexity of Approximate TMA can be bounded by (c Lemma (Approximate TMA sample complexity). Let k: 2 0, Let e' > 0, 8 E (0, 1), and define M according Moreover, let C > 0 be the marimal absolute value of the instantaneous cost, and let
to Eq. 21
60
t/2 2 log ItI (7(1)))
Define step sizes (0) Ba (p', ,p),,,, (t(l) - nolt - 11/7 and at = ap(0) for all t E 14]. Moreover, let.
16MC
Na.- = 2 logg
71-
and
MG. Mg = 27 27-21 2H
22S2 Att%
(1 7)2 log
for all [4]. Then Algorithm gields a transition kernel p²h such that
V (0) V x.p (p) S e
(36)
wilhin at most
AM
Ö
(37)
(1 7)2
samples.
Proof. The proof bounds both parts in the RHS of Eq. 34 with é/2 and then counts the number of state- action-state triples, the number of iterations, the horizon, and the number of trajectories per mini- batch. The full proof given in Appendix C.4
5.4 Analysis of Robust Sample-based based PMD-PD
Having shown results Lagrangian TMA in oracle-based and sample-based settings, now turn to proving the sample complexity of Robust. Sample-based PMD-PD (Algorithm 3 The algorithm modifies Sample-based PMD-PD [Liu et al.) 2021b) by accounting for the mismatch between the nominal transition kernel and the optimal transition kernel in the min-max problem in Eq. 4 The complexity analysis below is slightly simplified by dropping purely problem-dependent constants (e.g.
77 <) from the big-O statements.
As a first auxiliary result, we note that the robust Lagrangian objective in Eq. can be upper boundod basod the Lagrangian macro-iteration k obtained alter the policy update and the LTMA updale, and two error terms, namely the LTMA error tolerance and the suboptimality of the dual variable. These terms then be bounded using Lemma g Lemma 34 and Lemma 29
Lemma (Upper bound on robust Lagrangian regret). Let D be the objective in Eq. and let n e arg inf (xx). Then for any macro-slep k 2 1,
((T)) ((TT) S Vax.p. (p; Ab-1) + + AAe Var.ps (p:Ax-1))
(38)
where c the error tolerance for LTMA, and Ar, En (1 X 24-1, Te (p) where
(0h-1; arg maxpeP,X20 V Vopppp;)) X)-
16

---

Published in Transactions on Machine Learning Research (12/2025)
Proof. Note that
((TT)) V MKIPE- (p; 1
sup V (p Ak-1) + ( (p: suup V VeL.p Ak-1) pep
(decomposing)
PEP
sup V Teip (Vi..PE,, pEp
(p: (/1) -V VeiiPh (p; Ak-1)
(Ph-1 is optimal for A but not for Ak-1)
= sup V (p= ViNiiii (P) Vi (p) +
Σ (AE-1.) Ak- V m.PPi_ (p)
pEp
1=1
(definition of Lagrangian, rearranging)
< V (p; 16-1) + EN + Axe
where the last step follows from the error tolerance of LTMA and the definition of Axe
Eq. 38 then follows from (x=²) = suppEr maxx20 Vx A) 2 V -p (0; At-1).
As hample-based algorithms work with approximate value functions, Lemma 9 describes the conditions under which one can obtain an e-approximation of the cost. functions and the regularised augmented Lagrangian. The same settings as sample-based PMD in Lemma 15 of Liu PMD algorithm. We rephrase the lemma to include updated transition dynamics.
(2021b) transfer to the Robust Sample-based
Lemma 9 (Value function approximation, Lemma 15 of Liu et al. 2021b rephrased). Let k 2 0 be the macro-slep of the PMD-PD algorithm. With parumeter sellings
K = = (:)
8 Klx
tx = (log(max {1, (A dy 6==0 θ
(1o8(1 (log(1/bgg (1/k))
(max {1, ] + eta)² log(1/6x) )
Nv.x = θ (108117
Mv. = θ
e2
Nox = @1181117
(max {1, [1bell1))) 1)
MQ =
62
the oppresimation e-oplimal, i.e.
a)
14i a(sp (p) Vi px) Se =i= [k]
(p)
b)
Qr pp (s, - Qm (8) Se ((s,0)
with probability 1 5.
Proof. The full proof can be found in Appendix D.5
Denoting V as the unregularised augmented Lagrangian, can show a relation between two otherwise unrelated policies based on their divergence to two consecutive policy iterates.
Lemma 10 (Bound on regularised augmented Lagrangian under approximate entropy-regullarised NPG,
Lemma 18 Liu et al. (2021b)). Assume the some sellings as Lemma g Lagrangian is bounded by
Then the regularised augmented
V. TT + 1-7 Bigutine (Ak-1, Th) V V..p. (s) 1-y (T, mk) BBs (T,, (1,Tk+4))) O(c) (39)
Proof. The proof makes use of Lemmn 20 In particular, it notes that K = O(1/e) and the value difference
to Tे is bounded by 1/K after tx steps. After applying the pushback property (Lemma 17 to म, Tky and क, and derives an upper bound on the Bregman divergence w.r.l. T based on Br ps (T, M&+1) +
[log((m]) log(=(+1)) Ilac where the second term is @(1KK). We refer Lemma 18 of Liu al. (021b) for the detailed proof.
17

---

Published in Transactions on Machine Learning Research (12/2025)
The theorem below proves the sample complexity of Robust Sample-based PMD-PD, using Lemma 9 to compute estimates of the Q-values for policy updates and using Lemma i to compute estimates of the G-values for transition kernel updates. This then allows to demonstrate the overall sample complexity for obtaining an average regret in the value, constraint-cost, and Lagrangian bounded by O(c).
Theorem 2 (Sample complexity of Robust Sample-based PMD-PD). Choose parameter sellings according to 272mms [1-7]5> 1I L, and 1j === 1=2, Moreover, let x¹ E arg inf ((T),, let Eg > 0 be the upper bound on the LTMA error tolerance at macro-iteration k such that e = O(c), and let P be a reclangular uncertainty set according to Lemma 24a) or b). Then within a total number of queries to the generative model equal T == =(C))), Robust Sample-base based PMD-PD provides the following guarantees:
Lemma g let a
(a) average regret upper bound:
Vunaea (p) - Var = O(e).
(40)
(b) average constraint-cost upper bound:
max jelm
1
Σ
V2u. O(e).
(41)
K
c) robust Lagrangian average regret upper bound under (oracle-based) LTMA: under the conditions
of Lemma with a number of LTMA iterations U/2 = θ preconditions of Lemma 24b), we have
Ps, and with P defined according to the
2,10
K (Tk)) -
K
d) robust Lagrangian average regret upper bound under Approzimate LTMA: under the conditions of Lemma / as applied the Lagrangian at each macro-iteration, with C Fx, and with P defined according to the preconditions of Lemma b) we have
((()) = O()..
K
Proof. A proof sketch is given below for convenience while the full deriviation is given in Appendix D.6.2 (a) The proof uses Lemma 10 and Lemma 15 to obtain a telescoping sum similar to the analysis of Theorem 3
in Liu et al. (2021a). To account for transition kernel changes, it then upper bounds the cumulative regret
difference using Lemma (4) and the Bregman divergence terms the RHS of Eq. 39 using Lemma 25 This
then results in a telescoping sum.
(b): The proof uses the update rule of the dual variable and its relation to the approximate constraint-cost to obtain telescoping c): The proof uses Lemma. to upper bound the robust Lagrangian regret with respect to (x',p", p²,,")) by using the regret bounds with respect obtained in a) and b). Noting that the regret from oracle-based LTMA (Lemma 2p is at most e = -e)) for each k and that the average regret induced by the dual variable is bounded by Oc) (via Lomma 29
and additional term O(c).
d): The proof is analogous to part c) but now applies Approximate TMA using the settings of Lemma 7 Sample complexity: To obtain the sample complexity under Algorithm with Approximate TMA, plug the settings from Lemma g and Lemma to obtain
K
T
Mv..Nv. +
MoNNQ.
MasNas = -66-))
(42)
0=
18

---

Published in Transactions on Machine Learning Research (12/2025)
5.5 Extension to non-rectangular uncertainty sets
Similar to arguments made by Xiao 2022 for Policy Mirror Descent, oracle-based TMA has direct relation to the policy iteration algorithm.
Lemma 11 (Relation between TMA and Policy Iteration). Let 7p(t) for all E {0, (0...., 13. Then
under the direct paramctrisation, TMA is equivalent to Policy Iteration as defined for transition kernels in L
el al. 2023)
Proof.
Note that for mp(t) 7 oo, applying the TMA update rule, analogous to Eq.
29
p² (+(s,))) = sug 7pp (t))
PEP 1 - d (0, (s. (s,a,.) ag o7 (p.p')
arg sup (p. G..pt (s, Op B(p.r') pEP
(reweighting similar to Eq.
19
(p())
sug (p, G (s.0()))))))
PEP
which is equivalent to policy iteration. which based on Lemma is equivalent to
The latter can also be written as argsuppeP (p - p', G Ga (8,
arg sup (p- p", VV (p)
(43)
pEP
as in Eq. 3.4 of (2023
Algorithm Conservative Policy Itcration over transition kernels using Approximate TMA
1: Inputs: é' > O, policy π E II, value function V S + IR, initial transition kernel p", compact and convex uncertainty set P, learning rate Tp)()) + do for all / 2 0.
2: while True do
3: One step of Approximate TMA with learning rate (p)) to obtain pe as e'ooptimal solution to Eq. 43 Compute Frank- Wolfe gap G2 (V (p).pe p²)
if G, è' then return p =pp p².
7: else
8: Let 3r = G1 (1-g)3
47d
Let 1 (1 3:)p² Bipe.
10:
+-++1.
11: end if
12: end while
Exploiting the above relation, and using Conservative Policy Iteration to transition kernels according to obtain the sample complexity under non-rectangular RCMDPs using arguments by Li et al. 2023). In particular, while Wang et al. (2024) provide analysis of TMA only for s-rectangular RMDPs and derives oracle-based convergence rates for the policy optimiser, it is possible to extend the analysis to non-rectangular uncertainty set by relating it to the smallest. s-rectangular uncertainty set. that contains it. With this reasoning, the result below considers the Appproximate TMA algorithm for non- roctangular RCMDPs and then derives a full sample-based analysis of the full algorithm optimising all three parameters (T, p. A). The Algorithm 2 requires t = O(e 2) iterations of the Approximate TMA algorithm. Therefore, with derivations in Theorem 2 sample complexity of Ö(c-9) is obtained. In addition to the added complexity, the non-rectangularrty also comes with an additional error term based on the degree of non-rectangularity 6p, defined as
Algorithm 2
6p = max max (VV
'.p' - p²) max VV
x. 11))
(44)
P'EP E.
PEP
19

---

Published in Transactions on Machine Learning Research (12/2025)
where P& is the smallest s-rectangular uncertainty set that contains P. In the algorithm, the supremim and maximum are equivalent since P and P, are assumed to be compact. Using compactness and convexity of these sets, Remark 3 of Li et al. (2023) shows that ôp is finite using Berge's maximum theorem.
Theorem 3 (Sample complexity for non-rectangular RCMDPs). Let a rentagatan uncertainty set b).b) or c). Further, assume the preconditions of Theorem and Lemma 30 Then
according to Lemma 24
applying Algorithm to solve the inner problem on the Lagrangion, Robust Sample-buas based PMD-PD obtains
average regret of
K ((T))) - -((=") O(e + 8p)
K
within Ö(1/E)) samples.
Proof.
Let l E [K]. Applying Lemma 30 to Th, Algorithm obtains a solution ps = á such that
V (ps 11-1) Pa (pr A1-1) S M(24, 6p) O(e + 0p)
within t2 = (n/ee) samples, where indicates the number of samples evaluate Eq. same argumentation as in Theorem 2d) and adding the additional term O(6p),
43
Following the
K
K V Fe O(C+)) + Ax V parde = 0
(((T)) 0(x
K
K
Since n (11/²) in Approximate TMA, substituting Σ fn Ö(1/e²) into Eq. 42 the term dominates the sum, resulting in a T = ((1/e) sample complexity.
5.6 KL-based Mirror Descent in continuous state-action spaces
To generalise the algorithm to contimuous state-action spaces, we follow similar algorithm but replace the tabular approximation with function approximation (see Algorithm 4b. A further required change is related to the weighted Bregman divergence term formulated Eq. 16 While the weighted Bregman divergence not a proper Bregman divergence over policies, it is over the occupancy distribution, i.c. Bæp (') = B(d dj "",, as shown in the pseudo-KI. divergence in Lemma 10 of Liu et al. (2021b). To maintain similar theoretical results in continuous state-action spaces, extend the discrete pseudo-KT. divergence of occupancy
continuous pseudo-KL divergence of occupancy.
Definition 3. Continuous pseudo-Ki KL divergence of occupancy. Define the generating function h A:AA + R according to
(s, log(d) d))dsda / (s))
k(d JSXA
Then its Bregman divergence is given by the continuous pseudo KL.-divergence, defined as
B d 12) = [ (7,( log
(T ds. (s, a) /d ((s)
(45)
JSX
Moreover, it equivalent weighted Bregman divergence over policies B x²) over continuous state-action spaces.
20

---

Published in Transactions on Machine Learning Research (12/2025)
Proof. From the definition in Eq 45 and Vl(d log(d)"(ss, - (og( it follows that
B dg. p:h) = h(d, h(d,)) Vh(dd d) dh
1 (s log log(d, (s. a))dd de (s)
SXA
I JsnA d5 (s) "(8 dssda +
d r (s) log(d (()))ds
/
- (s. ( log(d)""(s (s. - log(d log(d dsda
[ (0) a) p as)s)ddsdaa - S (0g6))))))) *ss)ds
SxA
(3)" (ss,a)/ (s)
(s,
a) log
dsda
SXA
((s))
The equivalence to the weighted Bregman divergence over policies shown by extending Eq. 16 to continuous state-action spaces and noting that (s, - (s)((s).
5.7 MDPO-Robust-Lggragiann a practical implementation
To implement the algorithm in practice, we use MDPO Tomar et al. 2022 as the policy optimiser. On-policy MDPO optimises the objective
Tk+1 +- arg max JMDPO = Bs Bawns pa a)) - ( [+((ss))
(46)
based on is SGD steps per batch k, which corresponds to the macro-iteration. For macro-iteration k, it defines the policy gradient for o == 0% at any iteration t E [tx] as
VJMDPO 0x) E.,
and To (o) Euntoz
Top (a|s) Ve log(To(als)) ma (5,)0) -a DK no, (-(1s))
(a(ss)
(47)
where in our case the advantage A pe (s, a) is implemented based on the Lagrangian. The use of the importance weight nu used MDPO to correct for the deviation from mirror descent theory, where it za, is assumed that the data at each epoch is generated from ve rather than Th.- In line with our theory, our implementation performs the critic updates together with policy updates, which deviates from the original MDPO implementation. There still remains some gap of the practical implementation to our theoretical algorithm in that the state occupancy of MDPO given by the old policy whereas in theory it based on the current. The implementation of advantage values is based on generalised advantage estimation (Schulman ct al. 2018) and the critic estimates the value and the constraint-coste based on an MLP architocture with out puts. The update of the multipliers is based the observed constraint-coots in separate samples.
To form robust-constrainet variant of MDPO, use Lagrangian relaxation similar to the above (i.e. Algorithm 3 The algorithm considers multiple constraints and preserves the structure of the PMD-PD algorithm
Liu et al.) 2021b). The LTMA algorithm implementation follows the TMA implementation from Wang et al. 2024). which applies a projected gradient descent based on clipping to the uncertainty set bounds. Due to its similarity to PPO-Lagrangian (or PPO-Lag for short) (Ray al.) 2019) and the use of updates in (or MDPO-Robust- short). While MDPO-Robust-Tag is based traditionally clipping the multiplier, we also implement MDPO- Robust-Augmentedd Lag, which uses the augmented Lagrangian according to the theory (as sunmarised in 4 The practical implementation of the KL estimate follows the standard implementation [
the robust Lagrangian, we name the algorithm
SooPo-Robust-agrannee
for
Algorithm and
in StableBaselines3,, i.e. (TT((()-ss). r((ss)) R E (og(r((le))--ooff (ala)) - 1- (log(=(als)) log(n'(als))) (al=)))
21

---

Published in Transactions on Machine Learning Research (12/2025)
6 Experiments
To demonstrate the use of MDPO for RCMDPs, we assess ADDOO-Robstee on three RCMDP domains. We compare MDPO-Robust-Tag to robust-constrained algorithms from related algorithm families, namely Monte Carlo based mirror descent (RMCPMD (Wang et al., 2024) in particular) and proximal policy optimisation with function approximation (PPO-Lag (Achiam et al. 2017) in particular). All the involved algorithm families (MDPO, MCPMD, and PPO) are included with four variants, namely with and without Lagrangian (indicated by the -Lag suffix) and with and without robustness training (indicated by the R- prefix or the -Robust- infix). Additionally, the MDPO-Lag implementations also have Augmented- variants which use the augmented Lagrangian as proposed the theory section. The implementation details of the algorithms included in the study can be found in Appendix E The code for all experiments can be found at https://github. wwt.eocooocooaeeeeeeoe Wwomm/osssdd//MDP-RRDDDD
After training with the above-mentioned algorithms, the agents are subjected to a test which presents transition dynamics based on the distortion levels setup in Wang et al. (2024). The test procedure follows the same general procedure for all domains. For distortion level x E [0, IJ, the agent is subjected to a perturbation such that if the nominal model is & and the uncertainty set varies the parameter in [s. E), the transition dynamics kernel parameter of the test with distortion level x is given for each dimension by either & = E + 2² E.) or & = & + (2 Eo). We slightly improve the test evaluation by considering all the + directions rather than just single one, amounting to total number of test evaluations N fitest X 2", where n is the dimensionality of the uncertainty set parametrisation and Rieet is the number of episodes per perturbation.
To summarise the results, we use the penalised return, a popular summary statistic for robust constrained RL (Mankowitz et al.) 2020; Bossens 2024). The statistic is defined for a maximisation problem as Rpen = -V(p) -xnax bj= max(0, (p)) where V(p) denotes the value (negative of the cost) from the starting distribution and (o) denotes the j'th constraint-cost. from the starting distribution. In addition, we also formulate the signed penalised return Rp V(p) -E C We note that the penalised return matches the objective of the constrained methods and the return matches the objective of the unconstrained methods. The signed penalised return might be especially useful for robust problems; as even our extensive testing procedure may not find the worst case in the uncertainty set, and it is also of interest to generalise even beyond the uncertainty set, a solution that has negative cost can be evaluated more positively since it is more likely not have a positive cost in the worst-case transition kernel. The summary statistics reported included both the mean and the minimum since the minimum indicates the effectiveness in dealing with the minimax problem (the worst-case robustness). However, as a note of caution, the minimum is challenging to establish accurately because even though we test many environments it may still not contain the worst-case enviromment.
We report the results based on two distinct sample budgets, one with a limited number of time steps (200-500 times the maximal number of time steps in the episode) and one with a large number of time steps (2000 5000 times the maximal number of time steps in the episode). This setup allows to assess the sample-effccienc and convergence properties more clearly.
An additional set of experiments is to establish which kind of schedule for ag works best for MDPO algorithms, and the robust(-constrained) variants in particular (see Apppendix Hp. From this set of experiments, it is confirmed that a fixed setting works reasonably well across problems. The best overall performance for vobust-constrained RL is obtained by SoPPO-RobuttAugnentedl with restarts, and a geometric schedule achieves high performance with MDPO-Robust-Tagg For simplicity, the fixed schedule is used for all MDPO based algorithms throughout the remaining experiments.
using a batch-based linear schedule
6.1 Cartpole
To assess our algorithm on an RCMDP, we introduce the robust constrained variant of the well-known Cartpole problem (Barto et al.
1983 Brockman et al.) (016)) by modifying the RMDP from Wang et al. (2024). The problem involves a mechanical simulation of a frictionless cart moving back and forth to maintain pole, which is attached to the cart an un-actuated joint, in the upright position. The agent observes
22

---

Published in Transactions on Machine Learning Research (12/2025)
2, 22, 0, I and takes actions in (left, right), which apply small force moving either left or right. The agent receives reward of +1 until either the cart goes out of the [-2.4, 2.4Jm bounds or the pole has angle outside the range [-12", 12%]. In contrast to the traditional problem, the mechanics are not deterministic, and following Wang et al. 2002). transitions dynamics models are multi-variate Gaussians of the form
(0' (e(ea)))=-""''pppto
(48)
)
where Me(s,a) a) is the deterministic next state given (s, E S x A based on the mechanics of the original Cartpole problem. We first train and evaluate algorithuns in a CMDP problem for their ability to adhere safety constraints. We then also show the benefits of robustness training and evaluate algorithms in an RCMDP problem.
To formulate safety constraints into the above Cartpole problem, we define the instanlanous constraint-cosi as q | d, where d is a constant, set to d = 0.15 in the experiments, and å is the velocity of the cart. The safety constraint of the agent is to maintain constraint C = 30,,,/c) 0.
To incorporate robustness into our setting, we introduce delta- celta-perturbations as in Wang et al. 2024 using an uncertainty set with parametrisation
(49)
(27)m/2(0
where 8 E [-Ka; Kv]l=1- Our parameter settings differ in that we larger uncertainty sel, with Ky being increased fivefold (making the problem more challenging) while the number of time steps is reduced to make the constraint satisfiable. The robust algorithms are trained on this uncertainty set, where the transition dynamics are adjusted based on the transition mirror ascent algorithm of Wang et al. (2024), i.e. by using Monte Carlo and mirror ascent. In the experiment, this amounts to a projected update, where the projection restricts the update to lie within the uncertainty set.
Training performance The training performance non-robust algorithms can be found in Appendix F.1 (Figure 7). The training performance of robust methods, which use LTMA, can be found Figure g A trade-off in reward vs constraint- cost can be observed; that is, the constrained algorithms put emphasis on reducing the constraint-cost. while the unconstrained only maximise the reward. The plots demonstrate the rapid convergence of the MDPO-based algorithms.
HOME
(a) Reward
(b) Constraint-cost
Test performance of MDP and CMDP algorithms obtained by applying the learned determinstic policy from the Cartpole domain after 20,000 time steps of training. The line and shaded area represent the mean and standard error across the perturbations for the particular distortion level.
Figure 1:
Test performance Figure and 2 show the test performance after 20,000 time steps depending on the distortion level. MDPO-Robust and PPO achieve the highest performance on the reward. However, since they do not optimise the Lagrangian, they perform poorly on the constraint-cost. achieves the best overall performance by providing the lowest constraint-cost by far across all distortion levels. In the test performance after 200,000 time steps (see Figure 13 and 14 of Appendix G.I). the MCPMD algorithms are able to get to similar performance levels, and all three baselearners are competitive.
POOPO-Robust-AAe Augmented-Lon
23

---

Published in Transactions on Machine Learning Research (12/2025)
(a) Reward
(b) Constraint-cost
Figure 2: Test performance of RMDP and RCMDP algorithms obtained by applying the learned determinstic policy from the Cartpole domain after 20,000 time steps of training. The line and shaded area represent the mcan and standard error across the perturbations for the particular distortion level.
To summarise the overall performance quantitatively, Table 2a shows that MDPO-Robust is the top performer on the return after 20,000 time steps. MDPO-Robust-Lag and MDPO-Lag algorithms obtain similar levels of performance on the mean penalised return statistics, although the former obtain an improved minimum score, and both are far ahead of PPO-Lag and MCPMID-Lag algorithms. In Table 2b] the performance after 200,000 time steps can be observed. MDPO-Robust-Lag, with without augmentation, is the top performer the mean penalised return metrics, followed by non-robust MDPO-Lag. MCPMD-Lag and RMCPMD-Lag perform highest on the minimum performance, and are followed by MDPO-Robust-Lag algorithms. In summary, the solutions converge to relatively similar test performance levels but MDPO-based algorithms are superior in terms of sample efficiency.
Table 2: Test performance on the return and penalised return statistics in the Cartpole domain based on 11 distortion levels, 16 perturbations per level, 10 seeds, and 100 evaluations per test. The mean score is the grand average over distortion levels, perturbations, seeds, and evaluations. The standard error and minimum are computed across the different environments (i.c. distortion levels and perturbations), indicating the robustnesss of the solution to changes in the environment. Bold indicales the top performance and any additional algorithms that are within one pooled standard error.
(a) After 20,000 time steps of training
(b) After 200,000 time steps of training
Belunn
R... (pediiee)
Botara
RS. Gieer d)
Ryn (poutin))
Mear
Mis
Mren St
Mis
Moan
Mis
Moun SR
Min
Moas
Min
Moar SR
Min
257
33.3
-2394
-20.9
$4.1
-352.3
-340
MDPO
-278.1
MDPO
15
723
3385
3353
3000
RX11
16.3
-1533
PPO-Raleat
07.1
10.3
-225.2
-66.8
-2588
365.0
PFO-Baluol
(2.5
51.2
-19L0
-200.3
-25 0
-25874
63.3
56.4
-19-7
-2811
63.2 c.1
59.1
-U97
2147-11
-185
-2516-3
140
231.3
-531
300
20.7
21.0
12.0
201
$1.6
2911
33.3
-1144
ITALLAR
31.8
76.6
-5..
MDPO Arguesed
MIPO Leersted-
96.
-5.11
-5.3
142
122
-25.7
-95.6
-29.7
RMPSSSI Log
25.4
2211
70.8
2011
POO Rohves Tag
25....
26.6
-13
-354
3875
PFO Rocheed ag
36.1
37.1
812
-5.9
291
-3.6
36.3
108.4-1
05.9
14.2
24.9
41.5 -12
82.1
105.1
54
35.0 m24
200
MDDO MONNO-totrwee-oo Lag.
316 cm
267
11088
61.6
31.6
24.7
O Hotteet Lapr
11.2
31.1
106.2
13.7
38.6 p.0
30
6.2 Inventory Management
A second domain is the Inventory Management domain from Wang el al. (2024), which involves maintaining an inventory of resources. The resources induce a period-wise cost and the goal is to purchase and sell resources such that minimal cost is incurred over time. To form a constrained variant of this benchmark, we introduce the constraint that the discounted sum of actions should not average to higher than zero (i.e. the rate of selling should not exceed that of purchasing). We use the same radial features and clipped uncertainty set as in the implementation on github htttp:///giiiee catiuu..oo//eerssowwaay. DRR The implementation uses Gaussian parametric transition dynamics
p(8'18, a) 122)
1
e de (V)a(ss)((((aa))))
(50)
24

---

Published in Transactions on Machine Learning Research (12/2025)
with o 1, and the feature vector for i = 1,2 is given by
|
((ss (8,,a==c =
(51)
where P4;, 5-4, Mc; = (-2,8). The uncertainty set is given by {n : 111 Tello I k} where T7 (-2, 3.5). With the exception of the constraint, and the number of steps per episode for the adversary, the setting matches Wang et al. (2024). The constraint at time is given by
dss,, ar) = (a st) d,
(52)
with constants set as Ke,a 0.01 and d= 0.0 in the experiments. The constraint indicates a preference for actions with modest squared transaction magnitudes and preference for having positive inventory.
Training performance The training performance can be found in Figure 9 of Appendix F.2 for non-robust algorithms and in Figure 10 of Appendix F.2 for robust algorithms. The plots confirm the effectiveness of the constrained optimisation algorithms and the robust algorithms can also find a good solution despite the environment being adversarial. It is also clear that the MDPO based algorithms converge more rapidly solutions of the highest quality in constrained and cobust-constraing optimisation, although there appears to be a small benefit of PPO in non-robust unconstrained optimisation.
Takedd Cantia
(a) Reward
(b) Constraint-cost
Figure 3: Test performance of MDP and CMDP algorithms in the Inventory Management domain using the deterministic policy on the test distortions.
Test performance Figure 5 and Figure visualise the results for the test performance after 16,000 time steps. MDPO-Robust obtains the highest performance on the test reward, followed closely by MDPO and PPO. The constraint is challenging to satisfy for all algorithms, but MDPO-Lag based algorithms obtain the best solutions with cost between 2 and 3 across the distortion levels. Algorithms based PPO-Lag and MCPMD-Lag perform poorly with worst starting points and stronger performance degrading across distortion levels. After 400,000 time steps, the differences between the algorithms is relatively small in the
test cases (see Figure
15 and
16 of Appendix G.2
(a) Reward
(b) Constraint-com
Figure 4: Test performance of RMDP and RCMDP algorithms in the Inventory Management domain using the deterministic policy on the test distortions.
As can be observed in Table Ba MDPO-Robuss is the top performer on the return after 16,000 time steps. All other statistics, including the mean and minimum of the signed and positive penalised return maximised by
25

---

Published in Transactions on Machine Learning Research (12/2025)
MDPO-Lag based algorithms. In Table 3b the performance after the full 400,000 time steps can be observed. With the exception of PPO-Robust-Tagg, all constrained algorithms converge to a similar optimum, indicating that the nominal environment and the other environments in the uncertainty set have large overlap. Similarly, the unconstrained algorithms reach a similar optimum. In summary, the solutions converge to relatively similar lest performance levels but MDPO-based algorithms are superior in terms of sample efficiency.
Table Test performance on the return and penalised return statistics in the Inventory Management domain based on 11 distortion levels, perturbations per level, 10 seeds, and 50 evaluations per test. The mean score is the grand average over distortion levels, perturbations, seeds, and evaluations. The standard error and minimum are computed across the different environments (i.e. distortion levels and perturbat ions), indicating the robustness of the solution to changes in the environment. Bold indicates the top performance and any additional algorithms that are within one pooled standard error.
(a) After 16,000 time steps of training
(b) Aftr 400,000 time steps of training
Hetron
The (iggad)
Mem (peattio)
Hamera
HR. (4aped)
Rgg (poetive)
HCPSD
-32115
1547
90.7
-2886
-3162.
-2385
PTO
121.0
73.6
3156-7
-3885
AIDEO
102.
40.4
-3491
0637
-1557
MEPO
138.6
102.3
2417.
3156.7
36367
-22.0
3548
35450
36.0
250.
3556-1
300.
100.7
-1130
-85210
35875
23364
<182.5
119.0
73.2
386-3
MCP
PrO-Lag
647
-28.1
-1903
-1878
-2387-2
-18789
PPO-Lag
-36.7
-557.2
-339.0
-517.5
-339.0
MIFF-LLa
03.8
-1072
-537.8
-523.0
-837.3
-009.0
MDPO-L
BL5 +14
-JAKS
-557.5
-339.3
-535.0
-939.3
XINOO Approdedd Tay
-1594
-01.5
MIFO Aegrested Lag.
1625
pm
.838.
439.3
033 211
2001
415--11
-06.5
-557.4
.39.0
233.0
PPO FF0-Bohar-La
-3555
-011
-1188
-32-2
-11183
MEIPO Nokrat
06P
3665
-837.1
-838.3
-938.3
63.9
-2114
200.0
-1722
-946.1
-11722
015
-1677
-557.8
.999.1
-887.0
.99.1
6.3 3-D Inventory Management
The third (and last) domain in the experiments introduces a multi-dimensional variant of the above Inventory Management problem, with dynamics
1 p(s(ss,a) (2T) e 2o (Vsss)
(53)
3..5, where the feature vectors of Eq. 51 are now given by (4,, (-3,-2.5,33.5,..0,,2, 2.0, 4.5), MCg
(-6.0, 2.8, -4.0, 8.0, 2.0, 2.5), oc- (4, 4.5), and the uncertainty set is given by {n : || Nel oo S x}
where T/. = 2, 1.8, 1.5), [1.5, 2.0] and == 0.5. The constraint j E [m] at time & is given by
cg(se, ar) Ut.j Kast. - d,
(54)
where ætz and st,j denote the j'th dimension of the state and action, respectively, at time i, and constants are set as K2 = 0.5 and d 0.0 in the experiments. The constraint indicates that the agent should not get a negative inventory and if the inventory is positive, it should not sell more than 50% of the current inventory.
Training performance The training performance can be found in Figure 11 and Figure 12 of Appendix F.3 It is clear that the MDPO-based algorithm have improved sample-efficiency and converge to the highest. unconstrained and constrained performances.
Test performance Figure 5 and Figure t visualise the results for the test performance after 40,000 time steps. While all algorithms are sensitive to the distortion level, can be scen that the robust algorithms have are generally shifted up for the rewards, and robust-constrained algorithus have been shifted down for the constraint-costs, indicating the effectiveness of robustness training. The MDPO-Robust algorithm is superior in the return and the the MDPO-Robust-Lag algorithms are found to be superior in the constraint-cost. While it is challenging to satisfy the constraint with limited training, after 400,000 time all algorithms have can satisfy all the constraints for all but the highest distortion levels (see Figure 17 and Figure 18 of Appendix G.3
further improved, but remarkably MDPO-Robuste
The return and penalised return statistics after 40,000 time steps can be observed in Table 4a MDPO- Robust has the highest score the mean and minimum of the test return, which indicates the robustness
26

---

Published in Transactions on Machine Learning Research (12/2025)
Nrode fourt Pieseed
Nylde Desirate Diowernd
Spea Cancs Preveree)
(a) Reward (b) Constraint-cost 1
(c) Constraint-cost (d) Constraint-cost
Figure 5: Test performance of MDP and CMDP algorithms in the 3-D Inventory Management domain using the deterministic policy on the test distortions.
(a) Reward
(b) Constraint-cost 1
(c) Constraint-cost 2
(d) Constraint-cost 3
Figure 6: Test performance of RMDP and RCMDP algorithms in the 3-D Inventory Management domain using the deterministic policy on the test distortions.
Table 4: Test performance on the relurn and penalised return statistics in the 3-D Inventory Management
domain based on 11 distortion levels, 64 perturbations per level, 10 seeds, and 10 evaluations per test. The standard error and minimum are computed across the different environments (i.c. distortion levels and perturbations), indicating the robustness of the solution to changes in the environment. Bold indicates the top performance and any additional algorithms that are within one pooled standard error.
(a) After 40,000 time steps
(b) After 400,000 time steps
Tasturs
(rodties)
(pottiis)
Meas
Min
New
Min
Min
Mous
SE
Mis
Monn
Sia
Mous
Min
MUSMD
..s
-11007
MIPO
41151
11516-2
-333510
MUPO
<2017.4
-099214
-227911
-2977L5
BADEPAID
453
-35174
-364541
-71864
-112255
1510
-8117
10001.3
77 7570
PrO-Rubktt
912
-1877
-20435
-13025-4
-3120
-54227-
PrO.Boler
218...
-24
10608-2
-1788
893
.12000
Bdret
54.8
-8.6
147178
4338
319313
67.0
24.4
-01814
22499.
PRO-Lag
447
PPO
318..4
195.5
31365
MDPO-La
424
-239.4
-51123
-35305
-
MENO Fat
319...
33.5
15065
5080
-1991.5
S131
XBPO-Argu
-2.5
-2:25
-5585-7
-3999
-64422
MENO Antreeted
210 201
0121-1
1517.0
-1198.5
1991
300367
2181
012
+15SILE
-33140
PRO.Bitee-
MIPO Rdoat-lg
MDPO- Suira-Suraaaaa
32.5
-2.4
2:173
-0011
-101144
-5767
330
-025-0
.066..
00357
-8289.3
JDDPo-Burak
215
-300
06125
798
-22992
-S887.7
27

---

Published in Transactions on Machine Learning Research (12/2025)
training succesful in guarantecing high levels of performance across the uncertainty set. MDPO-Robust Augmented-Lag outperforms all other algorithms the signed and positive penalised return statistics. MDPO-Robust-Lag follows closely in mean and minimum performance on the positive penalised return. After 400,000 time steps, LIDPO-Robust-e
algorithms have by far the highest minimum penalised return while MDPO algorithms with augmented Lagrangian score remarkably well on the signed penalised return (see Table Abj. Overall, the data indicate the effectiveness for MDPO-based algorithms, and particularly the effectiveness of MDPO-Robust-Lag algorithms for robust constrained optimisation.
7 Conclusion
This paper presents mirror descent policy optimisation for RCMDPs, making use of policy gradient techniques to optimisc both the policy and the transition kernel (as an adversary) on the Lagrangian representing a CMDP. In the sample-based reclangular RCMDP setting, we require Ō samples for an average regret of at most e, confirming an O (1/T*/$) convergence rate. Our analysis also covers the case non-rectangular RCMDPs, where our algorithm provides an Ô (5/T)/55 sample- basel rate. An approximate algorithm for transition mirror ascent. is also proposed which is of independent interest for designing ad adresariial environments in general MDPs. Experiments confirm the performance benefits mirror descent policy optimisation in practice, obtaining significant improvements test performance.
Acknowledgments
This rescarch/ / project supported by the National Research Foundation, Singapore under its National Large Language Models Funding Initiative (ATSG Award No: AISG-NMLP-2024-003). Any opinions, findings and conclusions reflect the views of National Research Foundation, Singapore. This research is supported by the National Research Foundation, Singapore and the Ministry of Digital Development and Information under the AI Visiting Professorship Programme (award number ATVP-2024-004). Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore and the Ministry of Digital Development and Information.
recommendations expressed in this material are those of the author(s) and do not
References
Mohammed Amin Abdullah, Hang Ren, Haitham Bou Ammar, Vladimir Milenkovic, Rui Luo, Mingtian Zhang, and Jun Wang. Wasserstein Robust Reinforcement Learning, arXiv preprint drXiv:1907.13196, 2019.
Joshua Achiam, David Held, Aviv Tamar, and Picter Abbeel. Constrained policy optimization. In Proceedings of the International Conference on Machine Learning (ICML 2017), pp. 30 47, 2017. ISBN 9781510855144.
Eitan Altman. Construined Markov Decision Processses. CRC Press, 1999.
Andrew G. Barto, Richard S. Sutton, and Charles W. Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE Transactions on Systems, Man, and Cybernetics, SMC-13(5): 634-846, 1983. doi:
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31:167-175, 2003.
Bahram Behzadian, Reazul Hasan Russel, and Marck Petrik. High-confidence policy optimization: Reshaping ambiguity sets in robust mdps. In Advonces in Neural Information Processing Systems (NeurIPS 2019), 2019.
David M. Bossens. Robust Lagrangian and Adversarial Policy Gradient for Robust Constrained Markov Decision Processes. In IEFE Conference on Artificial intelligence (CAT 2024), 2024.
28

---

Published in Transactions on Machine Learning Research (12/2025)
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. OpenAT Gym. arXiv preprint orx:::1600 01540, pp. 1-4, 2016.
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization. Operations Research, 70(4):2563-2517 2022. ISSN
15265463. doi: 001287/pppe.02211
Dongsheng Ding, Kaiqing Zhang. Tamer Basar, and Mihailo R. Jovanovic. Natural policy gradient primal-dual method for constrained Markov decision processes. In Advances in Newral Information Processing Systems (NeurIPS 2020), 2020.
Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo R. Jovanović. Provably Efficient Safe Exploration via Primal-Dual Policy Optimization. Proceedings of Machine Learning Research, 130: 3304-3312, 2021.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Expploaation-Exxlootaaiiio in Constrained MDPs. arXiv preprint, 2020. ISSN 2331-8422. URL httpp///aaxxvv.og/aa////////////
Jacopo Germano, Francesco Emanuele Stradi, Gianmarco Genalti, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. A best-of-both-worldss algorithm for constrainod mdps with long-term constraints. arXiv preprinl Xiv:22304. 14326, 2024. URL
220e 14322 14326
Julien Grand-Clément, Nian Si, and Shengbo Wang. Tractable Robust Markov Decision Processes, arXiv preprinl ar Xiv:24 11.04355, pp. 1-45, 2024.
Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Partial policy iteration for L1-Robust Markov decision processes. Journal of Machine Learning Research, 22:1-46, 2021.
Linfang Hou, Liang Pang, Xin Hong, Yanyan Lan, Zhiming Ma, and Dawei Yin. Robust Reinforcement Learning with Wasserstein Constraint. arXie preprint 1xx::2006.0004501, 2007.
Garud N. Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2):257-20) 280, 2005. ISSN 0364765X. doi: 10.1287, wtt.12/0r.o..o/1o /mmoo..0000001....0
Yufei Kuang, Miao Lu, Jie Wang, Qi Zhou, Bin Li, and Houqiang Li. Learning Robust Policy against Disturbance in Transition Dynamics via State-Consorvative Policy Optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, AAAI 2022, pp. 7247 7254, 2022. doi: 10. 2..1609/aaii.vee aaaaaaaiivv330 23667.2086.
Navdeop Kumar, Matthicu Gcist, Kfir Levy, Esther Derman, and Shic Mannor. Policy Gradient for Reetangular Robust Markov Decision Processes. In Advances in Neural Information Processing Syslems (NeurIPS 2023), 2023.
Navdeep Kumar, Adarsh Gupta, Maxence Mohamed Elfatihi, Giorgia Ramponi, Kfr Yehuda Levy, and Shie Mannor. Dual Formulation for Non-Rectangula Lp Robust Markov Decision Processes. arXiv preprint arXiv:2502.094.3 2025.
Mengmeng Li, Tobias Sutter, and Daniel Kuhn, Policy Gradient Algorithms for Robust MDPs with Non- Rectangular Uncertainty Sets. In Advances in Neural Information Processing Systems (NeurIPS 2023), pp. 1-31, 2023.
Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning, arXiv preprint wwXXv:1509.00971 pp. 1-127, 2015.
Tao Liu, Ruida Zhou, Dileep Kalathil, P. R. Kumar, and Chao Tian. Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs. Advances in Neural Information Processing Systems, 21 (NeurIPS)::711331177
2021a. ISSN 10495258.
Tao Liu, Ruida Zhou, Dileep Kalathil, P. R. Kumar, and Chao Tian. Policy Optimization for Constrained MDPs with Provable Fast Global Convergence. arXiv preprint ar 2rXi::2111.000 2021b.
29

---

Published in Transactions on Machine Learning Research (12/2025)
Daniel J. Mankowitz, Dan A. Calian, Rae Jeong, Cosmin Paduraru, Nicolas Heess, Sumanth Dathathri, Martin Riedmiller, and Timothy Mann. Robust Constrained Reinforcement Learning for Continuous Control with Model Misspecification. arXiv preprint orXiv:2010.10444 pp. 1 1-23, 2020.
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 (ICML 2020), pp. 2020.
Volodymyr Mnih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy P Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous Methods for Deep Reinforcement Learning. In Proceedings of the International Conference on Machine Learning (ICML 2016), New York, NY, USA, 2016. doi:
Arnab Nilim and Laurent. El Ghaoui. Robust control of Markov decision processes with uncertain transition matrices. Operations Research, 53(5):780 798, 2005. doi: 10.1287//pre.1000.0 10500002....
Santiago Paternain, Miguel Calvo-Fullana, Luiz F.O. Chamon, and Alejandro Ribeiro. Safe Policies for Reinforcement Learning via Primal-Dual Methods. IEEE Transactions on Aulomalic Control, 68(3): 1321-1336, 2023.
doi: N0.1109/TAAC.2222..1122
Alex Ray, Joshua Achiam, and Dario Amodei. Benchmarking Safe Exploration in Deep Reinforcement Learning. OpenAl, pp. 1 6, 2019. URL httpp:///ddtt https://cddnoopnaa... com/com//////// com/safexp
Reazul Hasan Russel, Mouhacine Benosman, and Jeroen Van Baar. Robust Constrained-MDDP: Soft- Constrained Robust Policy Optimization under Model Uncertainty. arXiv preprint arXiv:2010.044 04870, 2020.
Reazul Hasan Russel, Mouhacine Benosman, Jeroen Van Baar, and Radu Corcodel. Lyapunov Robust Constrained-MDPS: Coft-Constroined Robustly Stable Policy Optimization under Model Uncertainty, pp. 307 328. Springer International Publishing, 2023.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In Proceedings of the International Conference Machine Learning (TCML 2015), volume 37, pp. 1889 1897, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alee Radford, and Oleg Klimov. Proximal policy optimization algorithms. Xiv preprint arxiv: 1a0:1707.000 703706347, 2017.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. In Proceedings of the International Conference on Learning Representations (ICLR 2018), pp. 14, 2018.
Zhongehang Sun, Sihong He, Fei Miao, and Shaofeng Zou. Constrained Reinforcement Learning Under Model Mismatch. In Proceedings of the International Conference on Machine Learning (ICML 2024), pp. 47017-47032, 2024.
Majid Alkaee Taleghan and Thomas G. Dietterich. Efficient exploration for constrained MDPs. In AAAI Spring Symposium 2018 Technical Report, pp. 313-319, 2018.
Chen Tessler, Daniel J. Mankowitz, and Shie Mannor. Reward constrained policy optimization. In Proceedings of the International Conference on Learning Representations (ICLR 2019), pp. 1-15, 2019.
Manan Tomar, Lior Shani, Yonathan Efroni, and Mohammad Ghavamzadeh. Mirror Descent Policy Opti- mization. In International Conference on Learning Representations (ICLR 2022), pp. 1-24, 2022.
Qiuhao Wang, Chin Pang Ho, and Marck Petrik. Policy Gradient in Robust MDPs with Global Convergence Guarantee. In Proceedings of the International Conference on Machine Learning (ICML 2023), pp. 35763 -3793, 2023.
30

---

Published in Transactions on Machine Learning Research (12/2025)
Qiuhao Wang, Shaohang Xu, Chin Pang Ho, and Marck Petrik. Policy Gradient for Robust Markov Decision Processes. ar Xixiv preprint arXiv:2410 10.22/10.221 0222112 22114u2 pp. 1-59, 2024.
Yue Wang, Fei Miao, and Shaofeng Zou. Robust Constrained Reinforcement Learning. arXiv preprint arXin:2299.06666, 2022.
Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust markov decision processes. Mathematics of Operations Research, 38(1):153 183, 2013. ISSN 0364765X. doi: 10. (t35/mmor.112..0000 1120.0566.
Zifan Wu, Bo Tang, Qian Lin, Chao Yu, Shangqin Mao, Qianlong Xie, Xingxing Wang, and Dong Wang. Off-Policy Primal-Dual Safe Reinforcement Learning. In Proceedings of the International Conference on Learning Represenlations (ICLR 2024), pp. 1 1-20, 2024.
Lin Xiao. On the Convergence Rates of Policy Gradient Methods. Journal of Machine Learning Research, 23:
1-36, 2022.
Tengyu Xu, Yingbin Lang, and Guanghui Lan. CRPO: New Approach for Safe Reinforcement Learning with Convergence Guarantee. In Proceedings of the International Conference on Machine Learning (ICML 2021), pp. 11480-11491, 2021.
Tsung Yen Yang, Justinian Rosca, Karthik Narasimhan, and Peter J. Ramadge. Projection-Basee Constrained Policy Optimization. In 8th International Conference on Learning Representations, ICLR 2020, pp. 1 24, 2020.
Donghao Ying, Mengzi Amy Guo, Yuhao Ding, Javad Lavaei, and Zuo Jun Shen. Policy-Based Primal-Dual Methods for Convex Constrained Markov Decision Processes. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI 2023), pp. 10963 10971, 2023. doi: 10.1609/
Wenhao Zhan, Shicong Cen, Baihe Huang, Yuxin Chen, Jason D. Lee, and Yuejie Chi. Policy Mirror Descent for Regularized Reinforcement Learning: a Generalized Framework With Linear Convergence. SIAM Journal on Optimization, 33(2):1061-10911 1091, 2023. doi:
Xuezhou Zhang, Yiding Chen, Jerry Zhu, and Wen Sun. Robust Policy Gradient against Strong Data Corruption. In Proceedings of the International Conference on Machine Learning (ICMT, 2021), pp- 12391 12401, 2021.
Zhengfei Zhang, Kishan Panaganti, Laixi Shi, Yanan Sui, Adam Wierman, and Yisong Yue. Distributionally Robust Constrained Reinforcement Learning under Strong Duality. arXiv preprint 1077:2446.155788 2024.
Ruida Zhou, Tao Liu, Min Cheng, Dileep Kalathil, P. R. Kumar, and Chao Tian. Natural Actor-Critie for Robust Reinforcement Learning with Function Approximation. In Advances in Neural Information Processing Systems (NeurIPS 2023), 2023.
31

---

Published in Transactions on Machine Learning Research (12/2025)
A
Bregman divergence and associated policy definitions
Definition 4. Bregman divergence. Let h (AA) + R be convex and differentiable function. We define B M. h) = h(z) h(y) (Vh(y), v)
(55)
the Bregman divergence with distance-genenatin function h.
The Bregman divergence represents the distance between the first-order Taylor expansion and the actual function value, intuitively representing the strength of the convexity. A list of common distance-generating functions and their associated Bregman divergences is given in Table
Table 5: Bregman divergence for common distance-generrtiing functions.
Distance--enneratnng function (h) Bregman divergence (B(,:h))
4--norm |PI|]
for æ, E I2.
Squared fg-norm ||0:1|2
Squared Euclidian distance DsE(x, = | -ll for x, RRR
Negative entropy p() log(p(i))
Kullbach-Lcibler divergence DKL = (0g(()))(((0)//00)) for P.qEA
Table G and Table 7 show the update rules for different policy and transition kernel parametrisations. They hold true for any value function as well as Lagrangian value functions, so the tables omit the bold for generality purposes.
Table 6: Update rules for different policy parametrisations and Bregman divergences.
Parametrisation
Bregman divergence
Update rule
Direct: x == 0
(sE(0,0.)
6-11 proj (0. The VoVr,
Softmax: T[als)= E. explo..rr
exp(o..)
(0,(0,0,)
0,11 + ni VoVapld
Softmax: ([ass) explo
axp(O
weeupane KL-divergence (Eq, 16
[+] (als) = スミंス (a((s me
Table 7: Update rules and uncertainty sets for different parametric transition kernels (PTKs). The notation D---)) indicates a particular distance function such as & or loo -orm and the 전 notation indicates the nominal model for any parameter x (lypically obtained from parameter estimates).
Parametrisation
Update rule
Uncertainty sets
Entropy PTK:
20 and sherds
p( E. ala eoep
fus ang (nn D(e.E.)
(8 D(s.E) me).
Glussian PTK:
p(sl/s, M ((s)
fui mrg (WV D(E.E.)
(n Vin [M] D(n mnd)
U4 (u e A Vim (M. e (Fx:16/2), Frl(1 8/2)))
32

---

Published in Transactions on Machine Learning Research (12/2025)
B Robust Sample-based PMD-PD pseudocode
B.1 Discretised state-action space
Algorithm 3 Robust Sample-based PMD-PD (discrete setting)
Inputs: Discount E [0, 1), error tolerances c, cg > 0, failure probability E [0, 1), learning rates vj = 1-7
Mp >0, 0, yл 1.0, and penalty coefficients a 27 may and Cpp >
(1->)"
Initialise: To uniform random policy, λo. max (0. 1/A Voo.Po (0) Po p.
for h fo....,.K -- 1} do
for t E .0, - 1) do for (8,4) E x A do Generate MQ.x samples of length No.* based on oh.. and ps (following Lemma 9h. Estimate the value: e.g. for softmax parametrisation,
Q (8,a) = (x a) log( (p(als) + Ma.k Eja Σi=1 Nv.-l ot [én(s), at) + a En (1(a0(s)) logg( (
}
=a(a"(s?)
end for
Policy mirror descent
if Using Softmax parametrisation then exp
Q (s,a) -1 o p2
"k (als) - (T (als))) ma
v(s.a) ESAA.
else
D Use general Bregman divergence
gft arg minsee VoQ: p. 0) + aB
B. (0,0x)
Define & := kgtt1. end if end for
Define Tk+1
:= T
Apply Tabular Approximate TMA (Algorithm with cb. Th+1, and pd = ps to get p
Define Pk+1 : %
Augmented update of Lagrangian multipliers
Generate Mv samples of length Nv.++ based on Th-1 and pk41 starting from P Lemma 9
Estimate Vi Vumm (p) Mv. Eje E Nv. 7'a(s// for all i [m].
AR+1,1 < max {
-nx
77 VaLnn Peti (p), des nx Di (ett (0)]
Vi [m]
end for
33

---

Published in Transactions on Machine Learning Research (12/2025)
B.2 Continuous state-action space
Algorithm Robust Sample-based PMD-PD (contimuous setting)
Discount factor 7 E [0, 1), sample sizes Mq My, and episode lengths NQ. Nv. for k E [K], learning rate 77, TMA learning rate 7pp > O, dual learning rate Ta error tolerance for LTMA eg > and penalty coefficients a > 0 and op >
Inputs:
Initialise: To uniform random policy, Ao,j max {0, 1/a Vo (0)}. po p.
for & E {O...., K - 1) do for E (O...... fx - 1) do Generate Mo.s samples of length No.x based on o and Pk.
Update Qui.p arg argmingeRA Ma. E/1a" (Q(sh: ob) Ei=o IN 7t [
b Policy mirror descent
8/ + arg mingge 1/ Vo 0) + BBuuooo (0,8)).
Define o 1++ == Tgtt1
end for
Define T&+1
m
t
Apply Function Approximation TMA (Algorithm 1 with Ck. TR411 and pd p%. to get pi.
Define PE+1 := P
& Dual update of augmented Lagrangian multipliers
Generate Mv,++1 samples of length Ny.++1 based on th+1 and pk+1 starting from
Estimate V me+1 (p) + arg minveFv Mv,R+1 Ejmu (V(s)) Etm Nya+: fa((s),a)) for all [m].
AR+I,E < max {
7A Vz mx-1 (p); AR, na Vi Tats (0)} for all [m].
end for
C Supporting lemmas and proofs for Approximate TMA
C.1 Recursion property
The following straightforward recursion property useful in the proof of the regret bound of approximate TMA.
Lemma 12 (Recursion property, Lemma 13 in Xiao (022 non-negative sequence such that 2++1 I Ba, + b, then Ht 3 + 1-3.
Let B E (0, 1), and b > 0. If {arh2o is
C.2 Regret bound for approximate TMA
The regret bound of Approximate TMA (Theorem is shown below.
Proof. Note that.
(p" ())s,))) - (-18, a), (1),a))p++3((oo
(s, (0' (-18,)) - ('1s,, a), (x + - 11(((1)), (s,u,))
From the above and the pushback property in Eq. 30 with p = p",
()),))))) - 1'(1,, (r (p' (1'( + (+)s,a), Gr,p (s, ap(()
mp(1) (B(p'.p") B(y' (10",(+11) x111
34

---

Published in Transactions on Machine Learning Research (12/2025)
Weighting both sides according to the occupancy measure, we obtain
(s)
Σ
(((
SES
aEAA
+
1
d
(s)
Σ
I
1 Y
P
SES
aEA
1 Ap(t) (t)
B (Boz.r (0', B sp (p" (p',p"*1) p111))
For part A), note that
1
Σ P
(8)
Σ
(p - (1)ss, (s,a,)) (spa))
P
1
#ES
aEA
1
P
(8)
Σ
(a|s) (1=())00 Grp
(s, + (11,))) - p1(1,, a), (s, - (s,
8ES
aEA
(decomposing)
= Vx (p) - Va (p) +
P
(s)
Σ
- ('(s,,, (-1s,))-
- Gr (s, (s,a,
SES
aEA
(Lemma 23
26'
2 (x) - Vi (p)
7
where the last step follows from a bound of the absolute value as in the proof of Lemma S For part B), note that applying the ascent property (Eq. 31 on Ô results in
0
(8)
Σ (1s,)) (+1, Gr (s,a,))
SES
aEA
1
P
Σ
m(als) / (1.
7
#ES
aEA
(1((18, (11s (s, - (s,
(decomposing)
F (s) pt
d
p c+ (s) Σ
r(als) - (-11 a),
dp
(s)
SES
a
(v'(1s,a)) p1 a), Gn - Ga (8,
35

---

Published in Transactions on Machine Learning Research (12/2025)
dz dp phtptti
((Vn (p) - Vxp++1 (p)) +
2
Σ x (alls) (+)s - (11, ( Grg (8, a, -))
?
aEA
(since the term is negative, upper bound the ratio; Lemma 23
2 M( (Vr.pe (p) - Va (p)) +
dp
d
Σ
(1)))) - -+ a), (s, - G (8, a, +))
d
(definition of M- = suppEP
2 M (Vapr(0)- - Ve (0) 1--1--
2E'
1
where the last step again follows from derivations in Lemma 5
Combining both A) and B), denoting oz = Vr (p) - V (p), and rearranging, we obtain
de + M (0+11-2 - 66 1
2
(t)((1 7) (0', - Bapri
ap(t)
(p" (1' +
2c'
1
1-7
Md++1
S (1]((( -7)
(t)
(f' (Bazo-D'.1D)- Baz (p', - x2
B
2é'(1= + -M)
(rearrange)
1-7
1 ( M
(t)
4c'
-1) 1
81 + 81t1 5 (t) (1)
(B Ber (p' - B ae (p', p(1)
1-7 (divide by M and note 1 + 1 2)
8441 + (1)
(tp 7) Baz "p" (p' 221) S <(1-1) M
61 1
al(
4e'
- 1)7 - 7) Beg (p (0")P')) (,0)((0))p)) + 1-7
(rearrange)
ap(t+ + 1)
By o5 (p' plt1) 1 1 11 )
(t)
4e'
8,41 + (M - 1) + 1)(1 - 7)
6. (M 1)mp (t) (t) 7) 15 (p' ('))'')) +
M
"I-7"
(since M 2 1-y, it follows that 7p (t + 1) 2 (p(l)/7 2 (p(t) M-11
1
Using Lemma 12 with B = 1
1 Mr It = 6z + (M- (1)(1 (1-)) 7) B o or p²), and b _e', it follows that
(t)
(()
8, < 6, +
(M (t) - 7) B o7 v5 (p" pp)
1
80 + (M - -1)m -
(0)
B 0- (0' (ap
(0) + 1-
4Mc
M
1
3C
4M
1-7 e
+
M
7
where the last step follows from &
S
2C 1-7
and (0) 2 ap()) (000) B B (p'
2 .P).
C.3 Approximate action next-state value The proof of Lemma 5 is given below.
Proof. By triangle inequality, the error a G
upper bounded by the truncation error and the estimation
error, so it suffices to bound both by half of the desired error in Eq. 35
36

---

Published in Transactions on Machine Learning Research (12/2025)
For the truncation error, observe that
po
No.t
E
re(s,,
Σ tm No.
Cr C
1-7
No.
For the estimation error of any particular (s, S A S and any E {0....,&A) t.. apply Hoeffding's
inequality with the random variable (1(),a,8') Ei=o Eie.- o a)) -- T conditioned
(so, dos 81) (s, a, s'), error tolerance ( NNG. and failure probability 8' "t
This results in
Ma. - 7)²² =
P(IX(s,0,8') ([x as) () S 2exp
= 8
2C
20t
2
2,2Nc.
2
Mc. & (211-)²
log
log
8
(1 7)2
Repeating the same procedure for all S x A S and applying union bound, obtain a failure probability
P
U Xx(s,,, a(x,(s, s')l 2c s,
Σ
s,a,8',
Σ 8' 8
5,4,8
2NG. This concludes the proof that the setting MG, (1-g)² log (2) sufficient obtain an estimation error of
at most O No. with failure probability of at most 8 across all iterations and state-action-state triplets. R
C.4 Sample complexity of Approximate TMA
The proof of Lemma is given below.
Proof. Note that it suffices to bound both parts in the RHS of Eq. 34 with e'/2.
For the first part of Eq. 34 note that requiring
(1-M) M
1
3C d'
1 1- v
(56)
implies that the number of iterations is bounded by
[1 ((1-2)) /log
M -
6C
1 S log
= log ar
60
M
c(1
-
This confirms that the setting tg 2 log I (
6C (((17))
is sufficient to satisfy Eq.
56
For the second part of Eq. 34 define e' = 20 " 1-
consistent with Eq. 32 This amounts to requiring that
4M
8MC H
/'
<6/2
(57)
(1-7)2
This implies a requirement of at most
H c log (2(1-))) /log(1) =logA
16MC
c(1 (d(1-))))
37

---

Published in Transactions on Machine Learning Research (12/2025)
Therefore the setting of 2 log;
16MC <(1-ク)²
suffices to obtain Eq. 57
With the settings of Ma. thg and H, note that 7-2H
(1)
2 fog
=(
16MC <(1->)}
Therefore
27
2- 2H
125
Mc
log
(1 ?)2
16M
2
25 Al
= 2
log
5
The total number of samples is determined by the number of state-action-state triplets, the number of iterations, the horizon, and the number of trajectories per mini-batch:
1 |A]
6C
16M
16M
5 5 A
$ AS M
log
log
6'(1 (1
(1-7)ze)
(1 (1- 7)2e'
(1 7-2
M²
6C
16M
2t 2
51252 A
log NH
log
log
e'(1 60(1-7)
(1 (1-7))46
8
(
5"
(1 (1-7)
D Supporting lemmas and proofs for Robust Sample-based PMD-PD
D.1 Analysis of the multipliers
To analyse the average regret in terms of the value directly, the lemma below provides an equivalence between the unconstrained value and the Lagrangian value at the optimum.
Lemma 13 (Complementary slackness). For any CMDP and any j E [m], the optimal constrained solution (T", has either X; = 0 or (p) = 0, such that its Lagrangian value is equal to its unconstrained value:
V=-(p: =V- Vz-(p).
(58)
Lemma (Bounds on the multipliers).. The sequence of mullipplers produced by Robust Sumple- based PMD-PD (uuskk20 j e [m] satisfy the following properties:
1. Non-negativity: for any macro step to 2 0, AE.j 2 0 for all E [m].
Positive ougmented multiplier: for any macro step l 2 A + ni Vi V.L.D. (p) for all j [m].
3. Bounded initial multiplier: for macro step 0, |Ao 1 < Iy Vi to. (p)1 for all j E [m]
4. Bounded value: for macro step > 0, 1 InxDj pr for all j E [m]
Proof. 1) Note that Ao 2 0 is trivially satisfied by the initialisation in Algorithm Via induction, if AR. 0
note that if V PEELIPE41 (p) 2 0 then Ae, J + T7 VERLLPE4s (p) 2 0; if it is negative, then -MA 1.k41 (p) 2
2) Note that 0 & AR. max max 7x V V.n. (p), -172 V., .p. (p)). This implies either a) n V Vin (p) 2
dR-1J or b) Vre.re (p) O. In case a),
Ak.j + MA
Ve ma (p) 2 0.
38

---

Published in Transactions on Machine Learning Research (12/2025)
In case b),
AEo -1Aa V2 .R.PP 2 0.
3) This follows directly from the initialisation to Ao max -17 V2 Vio.po (p)}-
4) Note that
| = maxx(xx-1e1 + 1IX Vi TR.PE (p), -17 Vi P2 (p)}
=max(1A-115 TA V
FR.PA Ina V
T..PA 12]
2 Ima P (p)12
The analysis of the dual variables focuses on the inner product between the modified Lagrangian multiplier and the constraint-costs, which represents the total constraint-penal at the end of an iteration. Due to the approximation errors E₁ Vilmm (p) Ve.pp (p), the inner product can be written
A + 7/ I. (p), Vim TaePh
I-lam (p)) (Ae.
(o))+(Aes -c) (m Velmm (p), V =t -P
Vlam (m))+(m
"A Pe+1 (p))
" sh
Th -Pt11
(59)
The inner product can be lower bounded, which leads a somewhat complex summation but a useful one that can be telescoped in the average regret analysis.
Lemma 15 (Lower bound on the inner product, Eq. 41 in Liu al. (2021b) ) For any h = 0, 1, K - 1,
Ae + 7x Th.Ph (p), Valm 11:1- (0))
2 1 (1Ast2l12 -1 (I (p)l - - (0))()
217x
+ (Ak,- -Ek-1) + ||x+1 2 11 (EE, Vllm (p)) na ||Ea|l 27d (vlm Vetti.pt (p), Exe1)) 721A B m pet1 (To+1, Tk).
(1 --- d
D.2 Analysis of the Bregman divergence
Another essential part of the average regret analysis is the pushback property, which allows a telescoping sum.
Lemma 16 (Pushback property, Lemma 2 in Liu et al. 2021b)): ). If x= arg mingee f(x) + B(x, y: h) for fized y E Int(A),, then for a > 0 and any 2 E A,
f(x') B(x", y: aa (B((,,))) B(z,z";h))
By selecting = == == nh, and x-' = n;, and using the weighted Bregman divergence, it is possible to use the property in the context of policics in the interior of the probability simplex. Lemma 17 (Pushback property, Lemma 11 in Liu et al. (0221) rephrased). For any policy a E Int(A(A)) and any p,
B V Voga(p) 1-7 Ba (p) (Baz (M, mk) (T,
The weighted Bregman divergence under the generating function P() log(p(i)) is equivalent to the KL-divergence, which bounded by log(A) the reference policy is uniform.
Lemma 18 (Bound on Bregman divergence). Let nt be wniform policy, then for any policy a and any p P.
(x >
(T) Σ (als) (al(A)())s) s log(A). 2F
8ES aEA
39

---

Published in Transactions on Machine Learning Research (12/2025)
D.3 Convergence of approximate entropy-regullrrsee NPG
Below is the supporting convergence result for approximate entropy-regullrised NPG.
Lemma 19 (Convergence of approximate entropy-regullarised NPG, Theorem 2 of Cen et al. (2022 )
Let
<> Then if -
-
c.
C2 2
Qu O
Q E.
+ 1- na
(log(TT) log(T
--
and
C² 2
2E
(1 +
2
?
110'
it follows that for all 2
0
1111 .p
CCn(1 na)² + 70
(60)
[log(=() log(mb (88(++11)l S 20ka (11 - -njo)* ' + 2a CC'
(61)
Vo. " ip |
S 330a - nja)² + 3C"
(62)
The following lemma provides settings for the number, lx2 of iterations to optimise the policy such that it has negligible error on the regularised objective (i.e. with KL-divergence and modified Lagrangian multiplier).
Lemma
20 (Number of inner loop iterations, Lemma in Liu et al. (2021b)). Let c > 0,
| Pppp
Qa Tp
S, 7 (1 7)/a, to log(3C&K), and
C2 = 27
?
7)2
It follows that
Va mp
V
1
6
(63)
K
(1 7)2
8
and
4e
[log(TT) - llg( Mog((T++1)ll.)
+
(64)
3aK
a(1 7)²
The following lemma bounds the performance difference of entropy-regularised NPG based on the approxima- tion error.
Lemma 21 (Performance difference lemma, Lemma in Cen et al. (0022) and Lemma in Liu al, (2021b)). For learning vale 1) < 7)/a and any l. 0, it holds for any starting distribution p that under entropy-regularisedd NPG,
Va (p)
Va pe (p) < Q of PP
(65)
1
D.4 Performance difference across transition kernels
In the context of robust MDPs, the performance difference lemmas below have been formulated across transition kernels, which help the analysis of changing transition dynamics RCMDPs.
Lemma (First performance difference lemma across transition kernels, Lemma 5.2 Wang et al. (2023)
For any pair of transition kernels p.p/ P and any policy I1, we have for any value function that
Vo)p(p) Varp/(1 (p)
Jr. (s)
(s)
Σ T(a|s) Σ (p()')s,a) - p'(3'1s, (c(s,a, [Va((())
aaEA
(66)
40

---

Published in Transactions on Machine Learning Research (12/2025)
Lemma 23 (Second performance difference lemma across transition kernels, Lemma 5.3 in Wang et al. (-23))) For any pair of tronsilion kernels p,p' E P and any policy TT we have for any value function that
(ap( - V= =
Σ eES
(s)
Σ
T(ass) (p(s'ss,a) ( p'(s'ss,a)) a(s,,,,s) + ,V [V
aaEd
e'ES
(67)
D.5
Value function approximation
A proof of Lemma g is provided below to demonstrate its applicability to the robust Sample-based PMD
algorithm.
Proof. a): approximation of Vi.
si (p) for all i [m].
Pick i E [m] and & [K] arbitrarily. Note that since costs and constraint-costs are in [-1, 1], the cumulative discounted constraint-cost. is bounded by Di=o (s) ar) E {-- Denoting the Nv,a-step cumulative
discounted constraint-cost as a random variable X = Ei= (,,(s,)))), and X = My. 1 My. Xn, we have by Hooffding's incquality that the number of samples required is derived
P( - [IX-B[XX122 26)
2
< 2exp
-2
My.
2
[vv.ell9))
- Nv,
exp
2
2
2
= (1os (5m") 1
My.k log
6x
(1 2)2
2
Further, note that since constraint-costs are in [-1, 1], it follows that the number of time steps is derived as
Nv.
[[ V Vi (p) 2
Σ
7 2
--
(=Nv.k
log(7) log((1 7)e/2)
Nv. log, - 7)c/2) - (1051/7 ))
(68)
thereby obtaining e-precise estimate of V nu (p) with the chosen settings of My. and Nv.
b): approximation of Qu .pe (s, a) for all (s S A. Select () E A arbitrarily. First note that č (8, a) (max {1, ||) and similarly Ver (s) = Omax (1, |)) (again omitting the division by 1- from the notation).
Define the random variable
No. Σ
r' ((s)) + E (a'ls)) log
(a'lss) (
) [1)(s))
X(s, a) c(s,a) + talog
+
(
1=1
41

---

Published in Transactions on Machine Learning Research (12/2025)
For f = 0, the regularisation term drops. Defining X
222 1 Emei X(s, obtain
Ma.k
P([X - B[X]] 2 2)
2
< 2 exp
-2
= E%
2
max 1.1 A
MQ.A
Me.
f1, 1|1.11l11 }
max {1, ||Ax 1
MQ,* log
max
=
log (5x1)
Ök
62
6²
(og()==)) max A1,1 (1..1..AA + e²
Therefore, sctting Mq.K =
is sufficient for approximating Q (8,
For any > O, note that the regularisation term bounded by
(a(sss)
Σ (a'sss) log
TT (a'ss)
Vo
Ph (s) V mi (3)
Vo.
Pn (8) + Omax (1, 11A)11)))
(from range)
t-1
Vo ma
(s) + Ommx (1, (1
+
Σ
0mp lcc
(iteratively applying Lemma 21
1-
t=
2
Omax {1, 1) +
Σ
Q Q%
(KL-divergence is zero before updates)
t=
s (max {1, [ } + 2ctx).
(69)
Since the unregularised Lagrangian is bounded by O(max {1, }x)l) and again applying Hoeffding's 's inequal- ity, it follows that Mq.K θ loog(%%)) (max 1.J Ax <tz )²)
is sufficient for approximating Q i (s, a).
2
With similar reasoning as in Eq. 68 but applied the augmented regularised Lagrangian, have
X
0h (s, (s,a)ls S
Σ
7 (O(max (1,11a11133 cla)
No
O (1, |A + Etx
1 1-7
NQ. - (188o/7
O(max (1, [|All1)) + tz
max maxxxl]|Aell]]
Note
that to
θ (log(max (1, 11 /e))
O
Therefore
No.
o (108117 max (mmx((1.1AAll1)))
By union bound, with probability at least 1 - ΣK- t4 1 - -8, the statement holds for iteration K -1 0
D.6
Sample complexity
D.6.1
Supporting lemmas
The following lemma provides constant upper bound on the cumulative regret difference induced by the LTMA update under general uncertainty sets (including non-rectangular uncertainty sets), where constant.
42

---

Published in Transactions on Machine Learning Research (12/2025)
indicates that it is independent of the number of iterations. With additional bg norm bound assumptions the uncertainty set, the constant can be reduced in rectangular and non-rectangular uncertainty sets. The improvement factor on the upper bound is 25
3y for rectangular ly sets and 2(9A2)) ctu) for non-rectangular AP
by scts, where c(g) 1 1/9 and Ap is the uncertainty budget (upper bound).
Lemma 24 (Analysis of the cumulative regret difference). Let n E arg min ((T), and define D Z - Vak-1,P-E1 (p) Vx pe41 pet1 (p) - F1 (p) (m as the difference in cumulative regret induced by the transition kernel updates in Algorithm! 3
a) For any uncerlainty set. P, & (T)) AS
b) Let P be uncertainty set contained in an eg (s, rrettanuual uncertainty set around the nominal p Pu
such that.
Pa.a S { ((S) (p((|s, - p(-1s,))ll, S vea) ((s.a)EExx
(70)
for some q 2 1, where 0 Ap maxs, Vs is the mazimal budget. Then D S Th ASLtol) A, where c(q) = 1//--
c) Let P be a non-rectangular by uncertainty set around the nominal p = po such that
p p: 1pp --lll S Ap:
p:110-
[)) =1 V(s,a) =
(71)
#EES
for some q 2 1, where 0 Ap is the budget. Then D I 2 (1-y)²
( (AS2)c(0) Ap, where c(g) 1/9.
Proof. Note that
V V.LS1.PL_(Pp) Vx
(V (p) Vnn pp (p))
V VILILIDE1100 - VILIIID (p) + Vn- (p) - Va Varmmil(
(rearranging)
T 11 (8)
Σ Talss) Σ (s px(6'(s,a)) (c(s,a, + V (a
0=
SES
REA
<ES
dT
x (als))
(p Ph+1 [c(s, + pati (s')]
#ES
REA
dES
(via Lemma 23
K-1
mk 11PK(1 (8)
Σ
π (als)
Σ
(p (s((''ss
(1 - 2
p
k=0 SES
aEA
sES
K-1
Sl
x' (als)
Σ
- (s+i(s'(s,a))
(1-7)) 7)2
k=0 #ES
aeA
s'ES
(Cauchy-Schwarz with the maximum value 1-
$ (1 7)2
1
ΣΣΣΣ
(pkt2(5'|s,0) - (a(ss'ss,))
sES REASES
K-1
ΣΣ
(pa(s'ls,a) P242(6(18,a))
(bound on probability)
21-
A=0 #ES a'ES
43

---

Published in Transactions on Machine Learning Research (12/2025)
ΣΣΣ (px(s")s,a) - po((s(s,)) 7)-
px(ss ΣΣΣ (po(5")s,0) - PK (s' 8, (s,))) #ES aEA
< (1 7)²
I9ES aEA
(telescoping)
5 (1 7)2
SA max sES,aEA
(1px(()s, po(-1s, a)Il (1po(-13,,) - PK (x(,,,))]l,
(definition norm)
< 2
SA max
[+ po(-1s,a)ll
(symmetry of the norm distance)
7)2
sES,aEd
For a), have
2 SA max [px(+(s,a) ao(-ls,))l1 (1 7)2
sES,
$ (1 - 7/² AS
For case b), we have
2
SA max [px((1ss,) - -po(-1s,a)ll
(1 - 7)2
.ES,nEA
2
$ (1 ?)2
SAS)
(1px(-(sa) -s)
< 2
AS1+du)
(definition of Ap)
(1 7)2
where the second incquality follows via Hölder's inequality, since for any X Rd, | -||1 X d/p ||Xlly for (1-1//g- ct
For case c), we have
1
ΣΣΣ
(px(5')s,a) po(s'(s,a)) (1 71-
ΣΣΣ J AE s'ES
Σ (po(5'ls,a) px(s'(s,a)) -px(((s)))
(1
7)2
sES AEA sEES
2
<
Ilp -Poll
(1 7-
S (1 7)2 (A52))(1)
|Pp - -pol,
2
< (1 7)2 (AS3) Ap
(definition of A,)
where the second inequality again makes of Hölder's inequality analogous to part b).
Since the difference of Bregman divergences the RHS of Lemma 10 has a mismatch the transition kernel index, its sum cannot be bounded by traditional telescoping. The lemma below provides bound based on alternative technique.
Lemma 25 (Analysis of the Bregman term). Let a > O be the Bregman penally parameter, let x² be the optimal deterministic policy for the RCMDP, let тo E 11 be the uniform random policy, and define > 0 according to Eq. 22 Then under Algorithm 3 the following equation holds:
K
a
d5 pa-1 (TT,, Th- 1) B or
ph-1 p
(T",, (ao)
[log(A) + 2og
1
?
1 1-7
1=
44

---

Published in Transactions on Machine Learning Research (12/2025)
Proof. Note that
K
B
B Tk-1)
B d p2- (T ,m)
(72)
7
de
K-1
α
B pp (T",, +
Σ
B
sprin in (T',, ,Tk) B dp df w2-1 (T', (Tm
Amm
(drop negative term -aB x (T TK) and rearrange)
K-1
$
log(A)
Σ
B
Bo on , B 4, -x- (TT", mTk)
(by Lemma 18
1-y
k=1
The remaining summation in the above is at most 2 log (+):
K-1
B Sp pe
(T)) - B dp .p-- --- (T" ,Ts)
K-1
x (als)
d (s) dp'
pc- (s) Σ x (als) log
Th& (als)
A=1
DEAA
K-1
d= ((8) log x
(s)(ss)
d Pk (s)
(n is deterministic)
(x)aa(s)ss)
k=1 SES
K-
log
Σ
1
Pk (s) sf
ss (s))
(via Eq. 23 U S inf inf.es Th (s)(ss))ss))
p
SES
logg
dx px (s) d0 (s)
(telescoping)
U
AES
1
< 2 log
U
The proof that the optimal dual variable is bounded by constant, potentially much lower than Bx, is given in the following lemma.
Lemma 26 (Lemma 16 of Liu et al. (2021b) rephrased). Let Ç be slack variable for a CMDP with transition dynamics p E P, and let (T" ,X) be its optimal solution. Then
2 (1)
||*
(73)
<(1
Proof. Following Assumption 4 there exists some policy म such that
(p) = Va (p) +
XV (p) S Vap + Σ Xv (p) S Va,((p) -
x
1=1
1=1
such that | < ||*I]] & Vi (o)
2
((1-7)-
The lemma below provides way to bound the ratio between the value of two transition kernels.
45

---

Published in Transactions on Machine Learning Research (12/2025)
Lemma 27 (Performance ratio of transition kernels). Let E II and p.p' E P, and let V be value function. Morcover, let M upper bound the mismalch coefficient in Eq. 21 Then il follows that
M
(x) - 1-7 V (p).
(74)
Proof. For any E 1., P, we have (s)(s) 2 (1 (1-7) (l))),ss, such that using derivations as in Theorem 4.2 of Wang et al. (2024).
M
1
d
d
- s)
2
p
p
(75)
1 1- 7 1 1
p
dp
v
dp (s)
Therefore,
(o)
P (8)
Σ c(als)
(definition of value)
BES
aEA
1
V (s) G (8)
((aas)
(division and multiplication by the same term)
7
do
J (8)
#ES
aEA
M
<
V (p).
Rgq. 75 and definition of value)
7
D.6.2 Main theorem
The full derivation of Theorem 2 is given below.
Proof. (a) The proof uses similar derivations in Theorem 3 of Liu et al. (2021b) and then accounts for the performance difference due to transition kernels.
Note that
Va mx 1. (p)
Veeti on (p) + (>x + +17 V-lmm (p), Vlm Te.pi
Te41 pe (p)) + 1-7 BB Bereiiee (TH+I,
S Vz (p) + ( 1- (Bgg on (TT", Tx) B B5 (5", Tk+1)) + olc).
B
where the last step follows from setting n" in Lemma 10 and noting that the inner product will be negative, since ÀR nx Vá
FR.DE (p) 2 by property 2 of Lemma 14 and Vi- mm (p) < 0 for any j [m].
It then follows that
V V (p) Va (p)
B
B p (x", B Brr (T", met1)) + O(c)
1 I-g
-(xre (An + a/
Vlmm na (0), Vlom pe (0))
a
B Bote a (TT41,
Filling in the lower bound on the inner product from Eq. 41 from Liu et al.
2021b) (sce also Lemma 15
Aa 7/x Neppe (p), Veem pe (0)) 2 1 (1Aetall² (1A4tall2-11Ao11)) + ?A [ (o)]12
Iim
(1)
(p)
211x
m2+1.pt
7211x B
-21A (Vlm (p),
11 B
Be
(TTE+I,
(1-7)²
46

---

Published in Transactions on Machine Learning Research (12/2025)
get
VT 1.me (p) Ve (p)
_ 1-7
a
(B De (TT xx) - B a (T" ,k+1) + +(E)
B
+
1. (12ell (iaal2-1\Aee -114+111?)
+
?1
(|rstm
xe+s P2 (0) -
-I|
(p)
20/2
2
Viim Fel1aDE (p), (p), cx+1) a(1 - --3 --011 112 B s (TT++1, Tx)) (1 7)
+ 201
1 1-7
a
B (Bar (T", xx) - Ba Bag (Tt mh+1)) , + +(c) + 1 (11ell- -11tt11ll)) +
7/2
(/ramm
Ta Pp (0)
-
-1I
1:m
(p) 1
2012
2
+ 27Tx
(Viim Fel1.pp (0),
(76)
where the last step follows because due to the parameter settings the term a(1-7)² 2 B (1-7)² dx aattimn (T&+11, Tx)) 2
0.
Due to the approximations and the above, the regret introduces a term
4 (cc) + (Ax-1, aa ( (I-11 Vllmm _ + a1 (ex 2V
murp. (p),
(77)
for each & E [K]. It follows that
(e (p) Va Vo
(78)
(Vze.pe (p) -Va Va-.pa(p (p) - Vin.Pa-i (p) Vx ve-1
V= (p)) + V=L.p--1pp (p) Vx- (p-1(p)
(decomposing)
K
< 01) +
Σ 7
B d3 Bee (
B do B (TT (1T,, , + A
k=1
11 (1
||rlupp (p) - | pp-- (p)
1 (11
+
217
(Lemma 24 and derivations above)
<0(() + a
1-7
(og(()) + +2
)
1
1
1
+
Σ
A
1=1
+
(1rtieg V (0)l? - -Ilvdim (1)](²)
+
1
[100 12
1xx11²)
(telescoping and Lemma 25
2
2mZx
K
< O(1 + ?/>
Vllm
Tx
[0)l + 2n1
1
11
+
A
(dropping negative terms)
2
A==
< 0(1 +
Ak
(1 7
where the last step follows from the fact that || 2 < mnz
(1->)= and || pk (p)ll <
(1-7)=- Note further that
m
(I=2-= O(1. Moreover, note from Eq. 77 that A O(E max 11, || Lemma 28 shows that with
Nam
probability 1 5, || < || = 0(1,, such that A = O(c) and Ek A O(1). All terms then reduce to O(e) after division by K =
(b) Denoting the approximation error iteration k E [K] and constraint, j ckji and observing that for
47

---

Published in Transactions on Machine Learning Research (12/2025)
any [m]
An.s = max -111 Ke.PE (p); A + 1/a DJ
Di
Ne (0)}
2 Ak-1. + 11 V2
Fe PP (p),
(79)
it follows that
K
K
1
V
(p)
V
TA.PA (p) - -EOW)
(80)
K
Pa
K
1=1
K
1
Ak.j - Ax- 61..)
(from Eq. 79
K
AK.j
1
Σ
Ck.j
(telescoping and non-negativity condition in Lemma
mAK
K
|
+ 1|2-
Ax
K
(sinco AKj. S | S || || - Axll)
Ch.i
maK
K
k=1
14 - +
(since by Lemma 9 K = θ (t)
and ckj O(e))
= O(I/K) + Occ)
(by Lemma 28
O(e).
(since K θ (t)
c) For any & [K], it follows from Lemma that
FAM
1/2 A
C (1(1-))
is sufficient to obtain an e e--optimal transition kernel from LTMA. Note then that via Lernaa
Σ Axe = O(e).
K
kE[K]
Using Lemma combining the errors from a) and b) for the cost and constraint-costs, and é, O(c), it follows that
1 K
( (( < Va (p; )x-1) + + + Ax, V parppu)aa-1P)) (p))
k=1
(Fx))
where FA ma Fx. Due to the results in Lemma 28 A O(1) and Fx 0(1). Moreover TA Vi ke,Pe S -ー (1) for all j [m] and all [K]. d) The scttings of Lemma guarantce an e--optimal transition kernel from LTMA. Following steps as in part c), it follows that
K Σ (W())) ( 2(T'))
< K (V.. (p: + + Ax. -V (p: (p;)==1)) O(e),
where the factor Fx does not appear since it already accounted for in the parameter sottings. Sample complexity: Following the loop in Algorithm 3 plugging in the settings from Lemma and Lemma 7 and omitting logarithmic factors and constants, the total number of calls to the generative model
48

---

Published in Transactions on Machine Learning Research (12/2025)
is given by
K
1
T= Σ
MV
+
Σ
MQ. +
Σ
Mo..N
k=1
1=
t=0
Ō
where the last step follows from e' =0
The proof that ||Ae 11 = O(1) for all k E [K] (independent of Assumption 2 is given below.
Lemma 28. Let K' 2 be a macro-iteration. Under the event that [ P (0) V for all i E [m], it follows that [|Ax+ll = 0(1).
V
(p)l S
Proof. Consider the Lagrangian with optimal parameters (x", ,P)) Note that
K' K'V** xx- (p: x0) = K'V n' (p; X*)
(complementary slackness)
K'
V Vx (p:xx'(;21")
m V V (p) Σ
X (x (p)
j=1
m
VIL.P (p)
X9
Akilt (p)
(p maximises the Lagrangian for m&))
M
Vi (p) +
VJ
pp (p)
(Lemmn 27
1=1
Σ Ekij ))
K'
K'
M
O(1) + Σ
VeL (p)
+
Aj
_xKes
1
-
(derivations Eq. 80
1-7
1=1
j=1
R=1
M
m
m
0(1) +
AK's
Nzenn
1-7
aA
Ø=1
k=1 1=1
K'
a
B de
xズ- (TT", T 1) - B d
vx- vx- (Tt" mma))) + Ax
k=1
?>
(Irtim
-11/ - -|
[1all2)) -11al))))))) (following Eq. 78 + 217a (126--112- (106-21l-11Aa11))
1
2
Applying Lemma 26 to p", it follows that |||1|| = (1) such that Σm x70(s) (()). Note then that
via Lemma 25
I E (log(A) - log( (l)gg)))))).)))))))))))) Moreover, the proconditions for a in the further derivations in Lemma 21 of Liu et al. (001b are satisfied. The remainder of the proof removes the constant I- = O(1) and then follows the derivations in Lemma of Liu et al. (2021b).
Σ <E[K]]
B (Bgr
B d ox (T", m
The lemma below bounds the error induced by the dual variable taking suboptimal values during policy optimisation and LTMA. The result bounds the instantancous additional error by a constant, and the average error O(e).
49

---

Published in Transactions on Machine Learning Research (12/2025)
Lemma 29 (Bound on dual variable induced error). Let 1,..., K define sequence of vacro-iterations Let (pk-17 xx-1) be the optimal solutions for X and in the problem
with the preconditions of Theorem
MAX sup X20 PEP (P) +
Σ 1=1
Then the error induced by the dual variable, as defined in. Lemma xx-1,) me.ii_ -..p;,,,p))) (p) sulisfies
according to Ar, -
K
A = 0(c)
(81)
K
Proof. Note that
K
m
(1-11.5
An-1 FE.D (p)
k=1
k=1 j=1
Bx v
T (p)
(non-negativity in Lemma 14 and Assumption
K
K
M
$
Bx
Vi
NR.PL (p)
(Lemma 27
1-
K
k=
= O
(Theorem 2p))
D.6.3 Non-rectangular uncertainty sets
The global performance guarantee of CPI can be expressed in terms of the degree of non-rectangularity Li et al. 2023). Note that we slightly modify the original lemma by removing the irreducibility assumption since the mismatch coefficient can also be limited using Assumption 3
Lemma 30 (Global performance guarantee of CPI, Theorem 3.8 in Li et al. (023 ). Let > O, let E II and let V S + R be value function. Then Algorithm satisfies
2 relurns within O(1/e") ileralions a solution á that
Va (p) pp) s ((2 8p),
(82)
where 8p is the degree of non-rectangularityy defined in Eq 44
E
Algorithm implementation details
All the algorithms are implemented in Pytorch. The code for RMCPMD based on the original implementa- tion, which can be found at http://tthbb..co//rerrie/aaaaaae from the StableBaselines? class. Both are modified to fit purposes by allowing to turn off and robust training and constraint-satisfaciii class conventions. All the environments are implemented in Gymnasium. For simplicity, the updates with LTMA are based on the original TMA code in performs pure Monte Carlo based TMA rather than additional function approximation as proposed in our Approximate TMA algorithm. For MDPO and PPO experiments, we use four parallel environments with four CPUs. Our longest experiments typically take no more than two hours to complete. The remainder of the section describes domain-specific hyperparameter settings.
The code for PPO is taken
Similar to PPO, MDPO is also implemented following StableBaselines?
com/JerrisonWang JMAee//MLRRRRRRRE which
50

---

Published in Transactions on Machine Learning Research (12/2025)
E.1 Hyperparameters for Cartpole experiments
Hyperparameters settings for the Carpole experiments can be found in 8 Settings for robust optimisalion, inchuding the policy architecture, transition kernel architecture, and TMA learning rate are taken from Wang ct al. (0023) with the exception that we formulate a morc challenging uncertainty set with a times larger range. The policy learning rate and GAE lambda is typical for PPO based methods so we apply these for PPO and MDPO methods. The number of policy epochs and early stopping KT. target based for PPO methods the standard repository for PPO-Lag /https://githun MDPO it is based the original paper's settings (Tomar et al. 2022). PPO obtained better results without entropy regularisation and value function clipping on initial experiments, so for simplicity we disabled these for all algorithms. The batch size, multiplier initialisation, and multiplier learning rate and scaling are obtained via limited luning procedure. For the tuning, the batch size tried was in {100, 200, 400, 1000, 2000} and the multiplier learning rate was set to {le-1, 1e 2, le 3, le transformation of the multiplier was compared to the direct (lincar) multiplier, and for the linear multiplier tested initialisations in {1,5, 10).
haam//ppnai/saati sttp://aattttttttteeeeeeeeeee starter- and for
m-le=t) 4} on partial runs. Then the use of a softplus
Table 8: Hyperparameter settings for the Cartpole experiments.
Hyperparameter
Setting
Policy architecture
ML.P Inputs Linear(128) Dropout(O.6) Linear(128) Softmax(2)
Critic architecture
MLP Inputs Linear(128) Dropout (0.6) ReLU Linear(I+m)
Policy learning rate (n)
3e-4
Policy optimiser
Adam
GAE lambda (AGAR)
0.95
Discount factor (7)
0.99
Batch and minibatch size
PPO/MDPO policy update: 400 x 4 time steps per batch, minibatch 32, episode
steps at most 100
PPO/MDPO multiplier update: 100 4 time steps per batch, minibatch 32, episode steps at most 100
LTMA: 10 x factou" Monte Carlo updates, episode steps at most 10
Policy epochs
MCPMD: 1
PPO: 50, early stopping with KL target 0.01
MDPO:
Transition kernel architecture
multi-variate Gaussian with parametrised mean in (1 + (c((ss)))))))))))))))))))))))( where d E (=0.005, 10.05, #0.005, +0.05) and covariance aI where 1c- 1e
LTMA learning rate (ng)
Dual learning rate (7a)
1
Dual epochs
MCPMD: 1
PPO: 50 with early stopping based on target-kl 0.01
MDPO:
Multiplier
initialise linear, clipping to Amax 50 for non-augmented algorithms
51

---

Published in Transactions on Machine Learning Research (12/2025)
E.2 Hyperparameters for Inventory Management experiments
Hyperparameters settings for the unidimensional Inventory Management (see Table 9 are similar to the Cartpole experiments. The key differences are the output layer, the discount factor, the transition kernel, and the TMA parameters, which follow settings the domain in Wang et al. (2024). Based on initial tuning experiments with PPO and MDPO, the learning rates are set to = le and 77 = le- a lower GAE lambda of 0.50 was chosen and PPO implemented without early stopping and with the same number of (5) epochs MDPO.
Table 9: Hyperparameter settings for Inventory Management experiments.
Hyperparameter
Setting
Policy architecture
MLP Input Linear(64) (0.6) ReLU Softmax
Critic architecture
MLP 3 Inputs Linear(128) Dropout(0.6) ReLU Linear(1+m)
Policy learning rate (1)
lc-3
Policy optimiser
Adam
GAE lambda (AGAE)
0.50
Discount factor (7)
0.95
Batch and minibatch size
PPO/MDPO policy update: 400 X 4 time steps per batch, minibatch 32, episode
steps at most 80
PPO/MDPO multiplier update: 100 x 4 time steps per batch, minibatch 32, episode steps at most 80
LTMA: 20 x factor Monte Carlo updates, episode steps at most 40
Policy epochs
MCPMD: 1
PPO: 5
MDPO: 5
Transition kernel architecture LTMA learning rate (ng)
Radial features with Gaussian mixture parametrisation le
Dual learning rate (7a) Dual epochs
le-2
MCPMD: 1
PPO and MDPO:
Multiplier
initialise to 5, linear, clipping to Amax 500 for non-augmented algorithms
52

---

Published in Transactions on Machine Learning Research (12/2025)
E.3 Hyperparameters for 3-D Inventory Management experiments
Hyperparameters set tings for the 3-D Inventory Management (see Table 9 are the same in the IM domain with few exceptions. The policy architecture is now a Gaussian MLP. The standard deviation of the policy is set to the default with Log std init equal to 0.0 alboit after some tuning effort. The optimiser is set to SGD instead of Adam based on improved preliminary results.
Table 10: Hyperparameter settings for Inventory Management experiments.
Hyperparameter
Setting
Policy architecture
Gaussian MLP 3 Inputs Lincar(128) Dropouu(0.6) ReLU Lincar(128)
RcLU Linear(3 2)
Critic architecture
MLP 3 Inputs Linear(128) Dropout(0.6) ReLU Linear(1++))
Policy learning rate (1)
1e-3
Policy optimiser
SGD
Log std init
0.0
GAE lambda (AGAE)
0.50
Discount factor (7)
0.95
Batch and minibatch size
PPO/MDPO policy update: 400 x 4 time steps per batch, minibatch 32, episode steps at most 100
PPO/MDPO multiplier update: 100 x 4 time steps per batch, minibatch 32, episode steps at most 100
LTMA: 20 x factor Monte Carlo updates, episode steps at most 40
Policy epochs
MCPMD: 1
PPO: 5
MDPO: 5
Transition kernel architecture LTMA learning rate (ng)
Radial features with Gaussian mixture parametrisation le
Dual learning rate (7a) Dual epochs
le-2
MCPMD: 1
PPO and MDPO:
Multiplier
initialise to 5, linear, clipping to Amax 500 for non-augmented algorithms
53

---

Published in Transactions on Machine Learning Research (12/2025)
F
Training performance plots
While the experiments with small and large training time steps were run independently, we report here the training development under the large training data regime (i.e. between 200,000 and 400,000 time steps) since this gives a view of both the early and late stages of training.
F.1 Cartpole
MOnO
HDV04ag
3HO0CH
(a) Reward
(b) Constraint-cost
Figure 7: Constrained MDP training development plots in the Cartpole domain, where each sample in the plot is based on 20 evaluations of the deterministic policy, The line and shaded area represent the mean and standard error across 10 seeds.
Ep code Resavd Disnourtedi
Episode Conetraiteese (Darcureed
1911 holerd
MORT
AAT PMD
10-
2000 sode 15380 (seba122inne 215000 2EA0
(a) Reward
(b) Constraint-cosl
Figure RCMDP training development plots in the Cartpole domain, where each sample in the plot is based 20 evaluations of the deterministic policy it interacts with the adversarial environment from that iteration. The line and shaded area represent the mean and standard error across 10 seeds.
54

---

Published in Transactions on Machine Learning Research (12/2025)
F.2
Inventory Management
Corstrartiost (Pscourcd
MCFMD
FRO
PRO
HO GOPodugeemsALL
50000 100890158000 330048 haaning
350000
38900 200000 25300 JOCICE
(a) Reward
(b) Constraint-cost
Figure 9: CMDP training development plots in the Inventory Management domain, where each sample in the plot is based on 20 evaluations of the deterministic policy. The line and shaded area represent the mean and standard error across 10 seeds.
sode Aeward Disooutedl
Ep Curstrarecss: (Pscoured
330-
RACTND
56800 L00990159000 230044
200000208000 332000 H0000 Tharing saps
5300E 38000c 200900 300ICE 489030
(a) Reward
(b) Constraint-cost
Figure 10: ROMDP training development plots in the Inventory Management domain, where each sample the plot is based on 20 evaluations of the deterministic policy as interacts with the adversarial environment from that iteration. The line and shaded area represent the mean and standard error across 10 seeds.
55

---

Published in Transactions on Machine Learning Research (12/2025)
F.3 3-D Inventory Management
(a) Reward
(b) Constraint-cost 1 (c) Constraint-cost 2
(d) Constraint-cost 3
Figure 11: MDP training development plots in the 3-D Inventory Management domain, where each sample in the plot is based on 20 evaluations of the deterministic policy. The line and shaded area represent the mean and standard error across 10 seeds.
Esicude Broward smoatad
Dynete Conarrate OJD
Tynacr Ceneramiinal smortod
Eracde Commranic Shateriee
Reward
(b) Coustraint-cost 1
(c) Constraint-cost 2
(d) Constraint-cost
Figure 12: RCMDP training development plots in the 3-D Inventory Management domain, where each sample in the plot is based on 20 evaluations of the deterministic policy as it interacts with the adversarial environment from that iteration. The line and shaded area represent the mean and standard error across 10
seeds.
56

---

Published in Transactions on Machine Learning Research (12/2025)
G Test performance plots with large sample budget
While the main text presents the test performance plots with small sample budgets, between 16,000 and 50,000 time steps, the section below presents the test performance plots after the larger sample budget of 200,000 to 500,000 time steps.
G.1 Cartpole
N-NO
40Poua
MOWBLI
30
Reward
(b) Constraint-cost
Figure 13: Test performance of MDP and CMDP algorithms obtained by applying the learned deterministic policy from the Cartpole domain after 200,000 time steps of training. The line and shaded area represent the mcan and standard error across the perturbations for the particular distortion level.
Edkeace (lrontttl
Eplesie Conerritticed (olonntedd)
6:0 Ronal
MOPSohessn
BMCHD
04
32
0.
25
15
0.0
0.2
35
10
(a) Reward
(b) Constraint-cost
Figure 14: Test performance of RMDP and RCMDP algorithms obtained by applying the learned deterministic policy from the Cartpole domain after 200,000 time steps of training. The line and shaded area represent the mcan and standard error across the perturbations for the particular distortion level.
57

---

Published in Transactions on Machine Learning Research (12/2025)
G.2 Inventory Management
Ejseee Reward
Eplouse Corst
106
F70
-256
20
Disation
Reward
(b) Constraint-cost
Figure 15: Test performance of MDP and CMDP algorithmss obtained by applying the learned deterministic policy from the Inventory Management domain after 400,000 time steps of training. The line and shaded area represent the mean and standard error across the perturbations for the particular distortion level.
Eidecc Roward (ilcortedl
Eplouse Constrans-ce (Uscounted)
106
100
-05
03
82
24
66
26
60
02
10
(a) Reward
(b) Constraint-com
Figure 16: Test performance of RMDP and RCMDP algorithms obtained by applying the learned deterministic policy from the Inventory Management domain after 400,000 time steps of training. The line and shaded area represent the mean and standard error across the perturbations for the particular distortion level.
58

---

Published in Transactions on Machine Learning Research (12/2025)
G.3 3-D Inventory Management
(a) Reward
(b) Constraint-cost 1
(c) Constraint-cost 2
(d) Constraint-com 3
Figure 17: Test performance of RMDP and ROMDP algorithms obtained by applying the learned deterministic policy from the 3-D Inventory Management domain after 400,000 time steps training. The line and shaded area represent the mean and standard error across the perturbations for the particular distortion level.
Dysode Sower Ereourett
Iode Oromen curt Shanenie
Ophaks Centrale And Erocurret
Pancade Conmeetice Jiireeeen sentecd
(a) Reward
(b) Constraint-cost 1
(c) Constraint-cost 2
(d) Constraint-cost 3
Figure 18: Test performance of RMDP and RCMDP algorithms obtained by applying the learned deterministic policy from the 3-D Inventory Management domain after 400,000 time steps of training, The line and shaded area represent the mean and standard error across the perturbations for the particular distortion level.
59

---

Published in Transactions on Machine Learning Research (12/2025)
H Comparison of schedules
Tomar et al. [2022) propose cither a fixed a or lincar increase across itcrations to give larger penalty at the end of the iterations (inspired by theoretical works, e.g. [Bekk & Teboulle (2003)). A polential problem with such a linear scheme is that if the LTMA update is strong and the policy cannot take sufficiently large learning steps, it may sometimes lead to a gradual loss of performance and premature convergence, espocially the context of contrained optimisation where the objective often subject to large changes due to constraints becoming active or inactive. As alternative, we also consider schedule where the penalty parameter schedule is restarted every time the LTMA update to & is larger than particular threshold. The schedule then follows the process oę I/(K-P)((K-F)) where k' indicates the restart time and K is the final time. In the experiments, the restart is done every time any dimension of the update is larger than half the maximal distance from nominal, i.e. larger than 0.5 ma,,,eu, K - - A last included schedule is the geometrically decrcasing schedule ag = 04-1 Y based on the discount factor y proposed in earlier work (iao 2022). We experiment with both epoch- based and batch- based schedules. While in the batch-based schedules we additionally experimented with the more aggressive update rule aę = a--1 M proposed in
1-7
Wang et al. (2024). However, the results under the scheme were poor, and so these results are not included.
Table 11 and 12 summarise the experiments comparing fixed schedules, restart schedules, linear schedules, and the geometric schedules for MDPO-Robust and MDPO-Robust-Lin variants. For the fixed schodule, the parameter is set to 2.0. For the geometric schedule, the starting parameter is set to epoch-based scheduling and to a = 2.0 for the less frequent batch- scheduling. The fixed setting works reasonably well while in particular cases there may be benefits from time-varying schedules. The best overall performance for robust-constrained RL is obtained by the batch-based restart schedule with MDPO-Robust-
5.0 for
BeeeRRouuus-uugnnnee-llllle Augmented-Lagg As a second top performer, the geometric schedule with MDPO-Robust-Lag also performs consistently high.
60

---

Published in Transactions on Machine Learning Research (12/2025)
Table 11: Return and penalised return statistics comparing per-epoch schedules for the penalty parameter a under the short runs (200-500 episodes x maximal number of time steps) and the long runs (2000-5000 episodes x maximal number of time steps).
Algocithu
Return
Ripen (signed)
Rye (ponitive)
Mean
SE
Min
Mear
SE
Min
Mesui 1: SE
Min
Cartpole (short runs)
MDPO-Rabus (Ezed)
68.1 su
56.4
-229.7
2610.6
-21111
2010.8
MI3OO-Rabuet (linear)
62.9 a.
-152.5
-2187.1
-514.6
-2087.1
MDPO-Robee (rostart)
63.1 2:01
55.2
-252.8
-2520.5
-304.8
-2520.6
MDPO-Rabust (gcometrie)
61.1
56.8
-148.0
-2480.3
-219.3
-2481.5
MDPO- Per00-Robss--ag (Exed)
31.1 tu
24.9
108.4 64
65.9
34.2 L1
24.9
HDDPO-Rabust-Le (Eunsur)
85.3
25.2
107.1
53.0
34.5
25.0
MI>"O-Rabiet-aag (resturs)
34.9 0.
25.7
107.2 1.49
63.1
34.3 111
25.4
MDPO Robust-Los Lag (gnometrie)
31.8 sus
25.0
109.
60.2
31.5
25.0
MD>0ORobbet-B SoPPO-RRbueeAAggeende Aobbeet-gggneeee---e (lixed)
34.6 a/
34.6
24.7
MDPO-Robast-uuge Saggee--nuggeeed--lggg (llnaar)
35.2 n.
25.4
106.6 E.
02.6
34.2 113
22.9
(restars)
36.4
25.7
107.1
45.8
34,4
21.7
MDPO- Aabbut-Angmenteel Lag (goomeeteic)
35.1 wa
24.6
109.7 34
56.4
31.7 LG
24.6
Cartpole (long runs)
MDPO Rero-R (Ezzed)
63.2 s..
56.1
-10..7 + LIwa
-2447.1
-185.5
2618.3
MDPO-Robuet (Linear)
33.7
29.2
-145.3
-5264
-165.0
-511.6
MD>O--Rabpe, (restart)
63.1 2:01
55.8
-173.6 1949
-53374
-287.1
-2538-1
MDPO-Rebust (goometrie)
60.2
16.1
-120.4
2002211
-193.7
-2662.7
MDPO Robust- Lag (Exed)
41.6
32.1
38.6 4:23
2.6
Robuet-Logg (Eansar)
32.3
22.9
72.0
38.6
15.4
-4.8
MDPO-Rabus Robust-Log (restart)
41.5
107.6
14.5
39.2
5.8
MDPO- Robuet-Lag (grometeic)
11.4 suz
31.7
103.7
8.0
33.6 4:23
1.3
MD2"O-Robuet-uugee Aebbnne-Agggeeeee-.ggg (fxxd))
41.2
31.4
106.2
13.7
38.6
5.0
HOPO-RRbbss-Augeennt
(llwaar)
30.0 o.
21.5
328 TM
-188 1.
-34.6
MDPO-Rebust- Aobouuttuggneeed-.... (restars)
40.5 o.
30.5
108.7
24.1
38,3
10.7
MDPO Robuss Angamntedd- Lag (geometric)
40.9 sua
9.2
37.8
Inventory Managestent (short runs)
MDPO Robuss (Bazed)
118.0 1.4
3350.0
3306 4
3350.0
MPDO-Rebies, (linear)
98.4 o.
-59.6
-2761.0
-2808.5 5
-2644
wa
28008.5
MPDO-Rabaer (restart)
105.1 2.3
-20.2
-3404.8
-3634.3
-34048
-9634.3
MPDO-Rebust (grometrie)
114.6 a.
49.7
-3196.4
-3207.6
-1166.5
-3207.6
MPDDO-Robist-L.n (fxorl)
60.7 1:11
-228.5
-031.
-1118.2
-832.2
-1118-2
HPDO-Robust-Lag (lmnarr)
90.2 47
-55.0
-2186.8
2.60
-2248.8
-2187.3 2.44
-2248.8
MPDO-Rabau Robust-Lag Lag (restazs)
86.3
-61.3
-188077
-0003.7
118811
-20007
MPDO- Robust- Log (geometeic)
67.2 su
-156.8
-1046.3
942
-1122.4
10488
4.
-1122.1
(lxxd))
60.9 106
-221.4
-038.6
1
-1172:2
-840.1
-1172.2
(Inwar)
91.8 444
-47.8
-2033.0
-2064.6
-2054.6
PODDO-Rebus-Aie cooburt-Aggannee--..e Lag (restart)
85.6 t.
-94.9
-1902.5 8.
-19542
-1002.7 6.
-1954.2
MPDO Angamette Lag (grometeric)
60.0
200.99
-1095.9
-1128.7
1097.2
-1128.7
Invenkory Managestent (long runs)
MDPO Robust (Ezzed)
119.7
72.4
3316.77
312.77
3416.7
-3129.7
MPDO-Robiet (linear)
114.8 a.
53.6
-3166.7 8.
3208 2
-1166.7 7 a.
-208.2
MPDOG-Rbist (restart)
119.9
74.4
-3425,2
344002
-3425 2
-3460.2
MPDO- Robust (gnometcic))
114.7 a.
6207
3116.66 a.
-2007.6
MPDO-Robeet-Lag (Uxed)
66.9 1:
-196.5
-837.4 1
-839.3
-838
-93913
OPPO-Rabust-Lag (linear)
66.88
-165.7
-837.3
-000.1
-808.0
-909.1
MPDO-Rebus-T. Robust-Lag (restars)
66.5 na
-169.1
.857.
.909.8
63360
28-3
-930.8
MPDO- Robust-Log (grometeic)
66.5
-168.9
-857.
-909.7
637.9
-939.7
MPDO-Robiet-B Row.eetAuugnnteeeeeeee (floed)
66.8 1.
-107.7
-837.2
-889.
-837.
36.6
-0330.1
HPDO-RRbbst-Auggee Aagnsss-uuugeneed-lggg (linar)
66.8
-163.4
-837.4
-800.2
-9139.2
UPDO-Robust-Auge Rabuss-Augganneedll... (restars)
66.8 mM
.837.4
.009.0
-07..
20.4
-939.0
MPDOORahhes-Augmeen Suggee--uuugnnned--gggg (gnometric)
66.9 m.
-162.6
-837.4 1
-839.2
-888
-9391.2
Inventory Management (shuet, runs)
MDPO Robus (Ezeed)
51.9 a.
-9.0
-7956.9
-1474788
9376.8
11890,3
17700-Rbbes..om (linear)
56.5 a.
-8166.
-15460.0
MPDO-E Robo- (restact)
56.3 w.a
-8.7
.393.9
1984
15500.7
9866.2
2010
-15581.6
HIPDO-Robues (gnometeic))
53.6
-11.5
-7337.6 6
-107712
6816.6
-14173.9
MPDO-RRbbeet-Lag (fxodd)
41.4 2.
-24.6
-1416.1
4461
-7726-9
-088 9
2 9511
-5560.6
MPDO-Rabust-Lag (Imear)
41.8 on
-25.5
-1584.6
-810.00
-5178.0
-8982.4
MPDO-Rabus Robust-Lag (restars)
41.9 wa
-24.9
-1668.0
.8138.0
-5308.1
2011
-8955.2
MPDO-EB Robust-Lag Log (geometeie)
11.1 ko
-28.2
-1278.3
-T871.7
5060.9
8050.8
(fixed)
38.5 a.
-325.0
.
-4967.0
mm
-8280.3
MPDG-Rabaet-Aue Rabbee-Augnnnnedd--gg (llwaar)
42.4 2.
-23.7
-1920.8
4463
-84005
-531 1.8
-920034
MPDO-Robiet-AAee Aaggmn-t-nnggnee---L..e (mesar))
10.7
-26.8
-3070.1
-747788
-5155.6 6
-8671.2
MPDO-Robuer-Anng Rawuee-Augnenrrdllle (goometrie)
42.8 6.
-25.1
-2123.5
4503
-567.3
-5507.8
-3303.0
3-D Inventory Mansgemenn (long ruus)
MDXPO-Rabuet (fixod)
87.0 2.04
-233122. : 190
-1331411
-23450.7
-3331411
MPDO-Rabust (imear)
96.3
36.0
-2772255
35906.5
.27902..6
-31806.5
MPDO-EB Robust (restazt)
90.5 w.
25169.7
32979.5
25225..0
-2979.5
MPDO-EB ReobO- (geometrie))
82.2 u.
20.0
-21022.5
-23773.
-2108 2
-28773.0
MPDDO-Rabes-L..gg (food)
32.8 a.
-32.4
2617.9
-2601.7
-1011.4
-3767.4
APDO-Rebast-Lng (lmnarr)
33.2 os
-31.9
2538.8
-2703.7
-1353.1
1974
-4804.2
MPDO- OPDDO-Rbbus-Ba
Robust-Log Lag (restact)
31.0
-91.2
2062.3
.3333.9
11177.1
4687.1
MPDO-EB POPDDORRbbe--LLe Robust-Lag (goometeic)
31.7 wa
-31.9
3269.5
371.
-2036.2
-1997.3
1993
-299.33
(fixed)
26.8
-38.6
5312.6
738.7
-1219.2
-3867.7
MPDO- Robust. Angmenned Lag (linear)
23.5
-91.1
6993.3
2238
2652.2
963.4
122.
-000.41
MPDO-Rabeet- Rubiet-Angaenteed Log (mestrt)
24.2 u.
-11.3
6811.0
2581.
-1043.3
-3775.2
Ro--Rhhee-Anggenteed (gpometric)
26.5 2.
-40.3
5494.4
-1644.2
-4586.5
61

---

Published in Transactions on Machine Learning Research (12/2025)
Table 12: Return and penalised return statistics comparing per-batch schedules for the penalty parameter a under the short runs (200-500 episodes x maximal number of time steps) and the long runs (2000-5000 episodes x maximal number of time steps).
Algoritham
Return
Pi (sigued)
Ape (positive)
Mesa A SE
Min
Mean 1: SE
Min
Mean SE
Min
Cartpole (short rans)
MDPO-Robist (Bxool)
63.1
M6.4
-220.7
-294.1
-2110.8
MDPO-Rohust (linaar)
44.4
-183.8
-5312
-214.9
-833.9
MDPO- Robust (restars)
62.5
55.0
-110.3
2150.3
-171.9
-2550.5
MDPO-Robat [xoometeic)
55.6
-286.5
-2504.8
MDPO-Robsst-laa (Avod)
34.4 2:00
24.9
108.4 4
65.9
34.2 1/10
24.9
MDPO-Robust-Lagg (linear)
35.3
25.2
107.1
53.0
34.5
25.0
MDPO-Robust-e Lag (liaear)
31.7 -:03
24.7
108.7 4.
62.1
34.1 1:12
24.7
MDPO-Rolua Ro---obut---ag (restat)
35.4
25.1
111.0
59.1
35.1
25.1
MDPO-Robist-Laag (goometrie)
34.62.0
24.3
100.4 2:47
64.0
34.3 2.11
24.3
To---Roosst-Agggenteeee (fxodd
34.6
24.7
110.8
61.6
34.6
24.7
LDDO-Robust-Ne BohrastAAugurateed
(Lnear)
24.4
64.7
34.4 1-
24.4
MDPO-Roluat- Augurettd Lag (restact)
31.4 4:
21.0
108.2 44
67.0
$1.0 1:
20.6
(pwometric))
35.00
25.0
57.1
34.6 1:
Caripole (long rums
MDPO-Robust (Ixee])
63.2
36.1
-109.7
-2647.1
-185.6
-2648.3
MDPO-Robust (linarr)
18.6 2:
15.6
-275.5 91
-630.8
-282.6 x
-640.4
MDPO-Robust (restors)
63.0
55.2
-246.4
12.00.7
-29.22
-2100.9
LIDOORRobut [geometeiic
63.1 a:
58.2
-1519
-6399 0
219.7 2962
-2660.1
MDPO-Roinat--an (fixed]
41.6 a:
32.1
105.1
9.6
38.6
2.6
MDPO-Robost-lag (liwaar)
22.2 2m
16.4
-104.5 1.5
-165.1
-137.5
11
-1901.0
MDPO-Robtst-Las (restars)
41.1 =.
30.9
112.4
30.1
39.6
16.6
SEPOORohhustLane Lag (goometric)
30.9
16.2
38.5
MDPO-Robuze AesiaatAAgguuuti Auguneteed-Lan Lag (Exed)
41.2
31.1
106.2
13.7
38.6
5.0
MDDPO-KobssttAAppmeee
(Unoar)
25.8
19.2
-21.6
-66.9
-102.0
MDPO-Robust-Augg Sesbbasst-kggnnntellllaaa (restart)
40.3 a:
30.3
111.7
33.5
39.0 1:
20.0
UDPO-Rohust-Augee AestuutttAngnenee--aaaaa (geometric)
40.9
$1.1
105.6
16.5
38.2
6.3
Inventory Management (short runs)
MDPO-Robust (froe])
118.0
72.3
-3906.4
33500
MDPO-Robust (linsar)
120.0 1*
73.6
-3425.4 14
-340.11
-3425.4 1-
-3400.1
MDPO-Robust (restars)
116.4
55.3
-320.22
3293.8
-340.2
3291..
MDPO-Robut (geometeii)
119.0 LM
72.3
-3361.8
3382.9
-33118
3382.9
MPT00-Roinnt--an (fixed]
60.7
-228. 5
-930.9
-1118/2
-9522
-1118.2
MDPO-Robest-Lag (liwear)
56.3 2.
.226.8
-030.1
153
-1175.6
.9405 1
-1177.6
HDDP.-RousstLaa
Lag [restars)
08.2
-168.2
.964.1
-1117.6
.964.5
-1117.6
MDPO-Robea Robrst- Lag (geometric)
-19..7
214
-9619
-86.9 am
MPPDO-Rbbat--nnn Aoniiat-AAguunte---aa (lxed)
60.9
-221.4
-938.6
-1172.2
-910.1
-1172.2
DDPO--Ribsst-Aggnnnn
(Unear)
-180.3
-032.
-034.2
-1118,2
MDPO-Robest- Eroobustt-ngneentellllaa (restart)
66.9 7:
-165.4
.837.6
363 .837.5
-500.1
-83.22 232
-939.1
COPP-Robuat-Angaai Lag (goometriic)
66.8
-166.0
608.8
-37.9
-33.6
Inventory Management (long runs)
MDPO-Robus (fiee)
119.7
72.4
-3416.7
3329.77
3416.7
3429.7
MDPO-Robat (liassr)
109.2 am
21.5
-2907.0 k0
2950.0
-9077.1 12
29500.6
MDPO-Robust (restors)
120.0
73.0
-3421.4
-341.4
-3421.4
-3441.4
MDPO-Robest (goometrie)
114.0 2
50.3
-3121.5 1
-313499
-3121.5 1.
3313499
MPDO.Robust-le BaobusttLaggin (fixed)
66.9
-166.5
.537.4
.09..1
.888.0
-939,3
MDPO-Rohre Roho--oobrttoo Lag (liaeuz)
231.1
-900.9
-1118.1
932.1
11118.1
RODOo-RobattLagg (restact)
66.8 1:1
-162.6
-837
-939.1
-37.8
-939.0
MDPO-Robastt-Lag (goometric)
-1637
-8374
-800.4
-83.99
RODD--Rhnst-Anggaeeee
(fxxd)
06.8 7:
-17.77
.837.2
-599.1
.87.99
-930.1
MDPO- Robust AettraatAAngennteed.. Loggnnttd-Lag (Lieer)
66.8
-168.8
-537.3
609.1
-37.8
999..1
MDPO-Robaat-Ae Rolral-Anguunntee--e (melari)
66.7 1.
-170.1
-83711
-899 5
-37.8 1.5
-930.5
PenO---obust-Appnnttee (pwometrie)
66.7
-168.4
-837.2
-930.6
-837.9
-33066
3-D Inventory Mansgementt (short runs)
MDPO-Rolee (fiee)
$1.9
:9.6
-7966.9
-14747.8
-9376.8
14536.3
MDPO-Robat (linsser
55.1 1:44
-9.5
-8112.0
-14726.5
-950799
-1433066
MDPO-Roiuutt (resturs)
54.5
-8.4
-7800.5
-14454.0
-9408.3
-14561.6
MDPO-Robest [goometrie)
55.4 2.4
-9.3
.2215.7
-19933.8
.98884
-15084.5
MPDO.Robuat Lag (fixed)
41.4
-2.6
1416699
-7726.9
5088.9
2217
-500.6
HDPO-Robuut-BB Lag (linsor)
-1575.9
-8108.3
-161.3
2217
-9733.5
MDPO-Robist-Laa (restart)
41.0 2:1
-27.1
-1239.8
-7630.5
-5350.6
1173
-80G166
MDPO-Robasst-Lag (goometric)
40.2
-26.7
-778.5
-7132.1
-5115.9
-8602.1
H.DDO-RousttAAggneeeee (fxxe)
39.5 a:
.2..6
.525.0
.6861.0
-955.0
2113
-2240.3
MDPO-Roitat-ee Me0---oouut-nnngnnteeeee Lagg (lnesr)
41.5
25.00
-177L0
7776.7
-299.1
-798.9
(resart)
40.0 200
-28.7 7
-754.8
-787.55
-1900.3
à 2008
-3300
MDPO--RibsstAAggneee Angpetttttnnnntl---lgg (gvometrie)
41.6
-24.6
-158288
8124.9
-3316.9
-S080LD
3-D Inventory Management (long rums)
MDPO-Robist (Bxod)
87.0..0
24.4
28312.
-3134.11
-334007
-31314.1
MDPO-Robust (lnear)
100.1 1.
41.1
.9655.3
-3776.00
2977888
-37776.0
MDPO- Robust (restars)
93.9
32.7
26709.0
33193.9
26815.8
-31993.9
MDPO-Robua [goometeic)
28.8
-24688.1
1217
32645.2
-24771.7
MMPDO-Robustt-aag (faodd)
32.8 2:1
-32.4
2617.9
1786
-201177
-1011.4
2 1933
-3767.4
MDPO-Rolast-Lag (lisear)
30.3
-24.
-42.11
-5798.5
-258899
-6431.7
MDPO-Robust-nn Lag (restart)
39.1 ..4
.27.4
.74.3
-5788.0
.255.22
224.
-6272.1
MDPO-RoiuattB (gsometricc
36.7
-29.0
612.2
-1823.9
-221,88
-5915.1
MPIIO-Robust-Ann Aobhsst--ggmmttt--.ng (fiodd
26.8 2:4
-38 6
5312.6
: 1493
758.7
-1219/2
1904
-3667.7
MDPO-Robsst-Augg Rohisst-nuggnntto-llag (Inear)
22.8
-43.5
7297.2
3001.8
-997.1
-3291.2
COPPO-Robut-ANie Bohust-Angueatee. (restart)
22.8 a..
7290.6
2672.1
-679.9
1267
-3116.2
MDPO-Roluut- Robuat-Anguentedd Augunented Lag (geometrie)
30.8 4.4
-33.8
3642.3
-1105.7
-1898.7
-5429.6
62


Reviews:
[{"review_id": "MpE3oTka7a", "reviewer": "Reviewer_Yek2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. The paper studies a safe RL problem, which is relatively novel and it is relevant to practical applications.\n\n2. The paper establishes state-of-the-art global convergence rates for RCMDPs in both the oracle-based and sample-based settings.  \n\n3. It covers both discrete and continuous action spaces, which enhances the generality of the proposed approach and makes the algorithm more practical for implementation across diverse environments.  \n\n4. The empirical evaluation spans three real-world applications offering a relatively comprehensive assessment that supports the effectiveness and robustness of the proposed method.\n\n**Weaknesses**\n\n1. The core methodology appears to be mainly a combination and limited extension of existing techniques from Liu et al. (2021), Tomar et al. (2022), and Wang & Petrik (2024). The paper does not convincingly demonstrate strong technical novelty beyond these prior works.  Although TMLR does not strictly require strong technical novelty, the reviewer would still encourage the authors to include more discussion on the paper’s technical novelty to better highlight its unique contributions compared to existing work. (My main concern)\n\n2. The paper’s use of abbreviations is inconsistent. For example, *Robust Constrained Markov Decision Processes* is sometimes written as **RCMDP**, sometimes as **Robust Constrained MDP**. Besides, many abbreviations are redefined multiple times in different sections of the paper\n\n3. The paper suffers from missing hyperlinks for lemmas, theorems, equations, and references.  \n\n4. The paper lacks a dedicated Related Work section, and the discussion of prior studies is somewhat unclear and inconsistent. For example, Table 1 briefly mentions Wang & Petrik (2024), but the introduction does not; conversely, Wang et al. (2023) is discussed in the introduction but omitted from the table. I recommend adding a clear Related Work section and improving Table 1 by restructuring it with articles as rows and key elements (e.g., type of MDP, algorithmic design technique, convergence rate, etc.) as columns, which would improve readability and comparison across methods.\n\n5. The Preliminaries section does not sufficiently define the paper’s key learning objectives and concepts. Terms such as regret are used without formal definitions, which may confuse non-expert readers.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a policy-gradient framework for (RCMDPs) with formal convergence guarantees. It extends the primal-mirror-descent approach of Liu et al. (2021) and Wang et al. (2023) to jointly optimise the policy as a maximizer and the transition kernel as an adversarial minimiser over the Lagrangian of a constrained MDP. Theoretical results show an **$\\mathcal{O}(1/T)$** convergence rate for the squared Bregman distance and **$\\mathcal{O}(e^{-T})$** for entropy-regularised objectives in the oracle-based setting, and an **$\\mathcal{O}(1/T^{1/3})$** rate in the sample-based RCMDP. For practical use (continuous state action space), the authors introduce MDPO-Robust-Lagrangian, a robust extension of MDPO [Tomaretal., et al., 2022] that incorporates a robust Lagrangian.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the weakness section", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "AeY03ON7ze", "reviewer": "Reviewer_brpZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. The paper tackles safety and robustness in RL, two crucial aspects for real-world deployment, especially in continuous control and high-stakes applications.\n2. The paper extends existing algorithms in purely constrained MDP or purely robust MDP to the RCMDP setting. It provides provable convergence guarantees for both oracle-based and sample-based RCMDPs and achieves competitive convergence rates. \n3. Experiments confirm theoretical insights and demonstrate robustness improvements. \n\nWeaknesses: \n1. The paper focuses heavily on technical developments of mirror descent for RCMDPs, but does not provide a sufficiently clear high-level summary of the conceptual challenges in extending from CMDP and RMDP to RCMDP. For instance, what specific difficulties arise when simultaneously handling constraints and robustness, and how the proposed approach overcomes them, could be discussed more explicitly to highlight the novelty.\n2. While the introduction cites relevant work, the paper lacks a dedicated related work section that systematically positions this work in the broader literature. In particular, although mirror descent is the main focus, the RCMDP setting has been studied with other algorithmic approaches, and these should be discussed in more detail to give readers a complete picture of existing results and limitations.\n3. The current textual summaries and tables do not clearly convey the landscape of results. A more intuitive presentation would be to provide a single structured table comparing algorithms across RMDP, CMDP, and RCMDP settings, summarising key aspects such as: algorithm type, convergence point, convergence rate, and assumptions. Using concise keywords rather than long text would make the comparisons more direct and reader-friendly.\n4. Presentation: Some technical details (e.g., long proofs) could be moved to the appendix, leaving the main text to emphasise conclusions and high-level proof sketches for accessibility. The formatting of algorithms and figures (e.g., on pages 6, 18, 21) is uneven, with some blocks occupying an entire line unnecessarily; these should be compacted for better readability and layout.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the problem of safe and robust reinforcement learning by extending mirror descent policy optimisation (MDPO) to the robust constrained Markov decision process (RCMDP) framework. The paper proposes a new algorithm, MDPO-Robust-Lagrangian, which simultaneously optimises the policy (maximiser) and the adversarial transition kernel (minimiser) over the Lagrangian. They provide theoretical convergence guarantees both in oracle-based and sample-based settings. Empirical evaluations show consistent improvements in robustness and constraint satisfaction compared to baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the last section.", "broader_impact_concerns": "This paper focuses on RL theory, and I do not see ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NWjz7xmmhT", "reviewer": "Reviewer_kh7f", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper proposes a novel integration of mirror descent based primal dual policy optimization with adversarial transition kernel updates via Transition Mirror Ascent in the RCMDP setting, extending theory from both CMDPs and RMDPs.\n\n2. This paper provides rigorous and complete convergence proofs for oracle and sample based regimes.\n\n3. This paper clearly states and justifies methodological assumptions such as bounded costs, convex and rectangular uncertainty sets, and Slater’s condition. This ensures the theoretical results are mathematically sound.\n\n\nWeaknesses:\n1. This method relies on oracle access for transition kernel updates in key theoretical results, limiting the generality of the strongest guarantees.\n\n2. This paper restricts analysis to convex and rectangular uncertainty sets.\n\n3. This paper does not fully analyze how estimation errors from the sample based setting propagate between policy and transition updates.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces Mirror Descent Policy Optimization for RCMDPs, combining primal dual policy gradient updates with robust transition kernel optimisation using Transition Mirror Ascent. It establishes convergence rates in oracle and sample based settings, with theoretical guarantees for robustness and constraint satisfaction. This paper also includes rigorous proofs and empirical evaluation against baseline robust policy optimization methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Questions and requested changes:\n\n1. Can the Transition Mirror Ascent step be adapted to a fully sample based setting without degrading the stated convergence rates?\n\n2. Could you provide a more detailed discussion of Slater’s condition, for example, whether this assumption is overly strict and how it compares with related assumptions in the literature? The current discussion below Assumption 3 is rather brief. An open question is: what modifications would be required to handle weaker feasibility assumptions than Slater’s condition in RCMDPs?\n\n3. An open question: Can this method be extended to uncertainty sets beyond the convex or rectangular structure, or to rectangular uncertainty sets defined using alternative divergences such as $\\chi^2$ or total variation divergence? Can you discuss the potential challenges for the extension?\n\n4. Explicitly acknowledge that some convergence results assume oracle access to transition dynamics and discuss potential approaches for making the Transition Mirror Ascent step fully sample based — **critical**.\n\n5. Extend the theoretical analysis to cover uncertainty sets beyond the convex or rectangular structure, or to rectangular uncertainty sets defined using alternative divergences. If this is hard and beyond the scope of this paper, you can discuss the potential challenges — **would strengthen**.\n\n6. Analyze the effect of estimation error propagation between policy and transition updates in the sample based regime — **would strengthen**.", "broader_impact_concerns": "There is no ethical concern is this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)