Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses
Authors: Kihyun Yu
Seoungbin Bae
Dabeen Lee
Venue: ICLR 2026 Poster (2026)
Keywords: Safe Reinforcement Learing
Adversarial Linear Constrained MDP
Policy Optimization
Primary area: reinforcement learning

Abstract: Existing work on linear constrained Markov decision processes (CMDPs) has primarily focused on stochastic settings, where the losses and costs are either fixed or drawn from fixed distributions. However, such formulations are inherently vulnerable to adversarially changing environments. To overcome this limitation, we propose a primal-dual policy optimization algorithm for online finite-horizon {adversarial} linear CMDPs, where the losses are adversarially chosen under full-information feedback and the costs are stochastic under bandit feedback. Our algorithm is the \emph{first} to achieve sublinear regret and constraint violation bounds in this setting, both bounded by $\widetilde{\mathcal{O}}(K^{3/4})$, where $K$ denotes the number of episodes. The algorithm introduces and runs with a new class of policies, which we call weighted LogSumExp softmax policies, designed to adapt to adversarially chosen loss functions. Our main result stems from the following key contributions: (i) a new covering number argument for the weighted LogSumExp softmax policies, and (ii) two novel algorithmic components---periodic policy mixing and a regularized dual update---which allow us to effectively control both the covering number and the dual variable. We also report numerical results that validate our theoretical findings on the performance of the algorithm.

Published as a conference paper at ICLR 2026
PRIMAL-DUAL POLICY OPTIMIZATION FOR LINEAR CMDPS WITH ADVERSARIAL LOSSES
Kihyun Yu, Seoungbin Bae
Dabeen Lee Department of Mathematical Sciences Scoul National University dabeenl @esnuacc..
Department of Industrial and Systems Engineering KAIST (khyu99, s sbbae31 3 jekaist.actc..... kr.
ABSTRACT
Existing work linear constrained Markov decision processes (CMDPs) has pri- marily focused on stochastic settings, where the losses and costs are either fixed or drawn from fixed distributions. However, such formulations are inherently vulnerable to adversarially changing environments, To overcome this limitation, we propose primal-dual policy optimization algorithm for online finite-horizon adversarial linear CMDPs, where the losses are adversarially chosen under full- information feedback and the costs are stochastic under bandit feedback. Our algorithm is the first to achieve sublinear regret and constraint violation bounds in this setting, both bounded by (K33/4) where K denotes the number of episodes. The algorithm introduces and runs with a new class of policies, which we call weighted LogSumExp softmax policies, designed adapt adversarially chosen loss functions. Our main result stems from the following key contributions: (i) new covering number argument for the weighted LogSumExp softmax policies, and (ii) two novel algorithmic components periooint--pprioiicc policy mixing and regular- ized dual update- -whch which allow us effectively control both the covering number and the dual variable. We also report numerical results that validate our theoretical findings on the performance the algorithm.
INTRODUCTION
Safe reinforcement learning (RL) studies sequential decision-making under safety constraints through interaction with an unknown environment. Many real-world applications have been explored under the safe RL framework, including autonomous driving (Isele et al., 2018), robotics (Achiam et al., 2017), and healthcare (Coronato et al., 2020). A common modeling frame- work for safe RL is the online constrained Markov decision process (CMDP) formulation, where the agent seeks a policy that minimizes (or maximizes) cumulative expected loss (or reward), while ensuring that the expected cumulative cost does not exceed a given budget (Altman. 2021).
To better capture realistic scenarios, it is often necessary to model adversarial environments, where components may vary arbitrarily over time. For instance, in autonomous driving, the loss may re- flect safety risks such as sudden braking, but it can also increase drastically due to unexpected traffic or hazardous weather. In service robotics, the loss may correspond to task failures or user dissat- isfaction, which fluctuate with human preferences or rapidly changing tasks. In such applications, assuming a fixed loss signal overly restrictive. Therefore, to model these scenarios, essential to consider CMDPs under adversarial settings.
Online adversarial CMDPs assume that the loss or cost functions can change arbitrarily across episodes, rather than being drawn from fixed stochastic distributions. Recently, adversarial CMDPs have been investigated under the tabular setting (Qiu et al., 2020; Stradi et al., 2024; 2025a;c; Zhu al., 2025). Although these works achieved sublinear regret and constraint violation bounds, they focused only on environments where the state space is finite and relatively small. As a result, their algorithmic guarantees may not extend settings with large state spaces. Such algorithms are often unsatisfactory in real-world applications, where the number of states is typically extremely large.
Additional Affiliations: Research Institute of Mathematics, Scoul National University: Interdisciplinary Program in Artificial Intelligence, Scoul National University; Korea Institute for Advanced Study

---

Published as a conference paper at ICLR 2026
To capture settings with large state space, safe RL with linear function approximation has been studied. Ding et al. (2021) proposed a primal-dual policy optimization algorithm for linear mixture CMDPs, where the dynamics
mixture of finite set of basis kernels. For linear CMDPs, assuming linear structure in the loss and cost functions as well as in the dynamics, Ghosh al. (2022; 2024) designed primal-dualttype optimistic value iteration algorithm with softmax policy. For the same setting, Kitamura et al. (2025) developed an algorithm achieving zero constraint violation under the assumption of known safe policy. Although these algorithms can handle large state spaces, they considered only stochastic settings, where the loss and cost functions are fixed or drawn from underlying distributions. That said, they fail to capture the aforementioned applications, where taking into account adversarial environments is essential when modeling safe RL algorithms.
expressed
To overcome these limitations, this paper proposes an algorithm for adversarial linear CMDPs. To handle adversarial losses with constraints, as online primal-dual mirror descent type algorithms be- come a standard choice, is natural consider primal-dual policy optimization for our setting (Chen et al., 2021; Ding et al., 2021). However, when applying primal-dual policy optimization to adver- sarial linear CMDPs, additional challenges arise-most notably in bounding the covering number of the value function class (Jin et al., 2020).
To elaborate on this challenge, frimal-dual policy optimization induces a more intricate policy class, necessitating new covering number argument. In particular, slightly perturbing the primal variable before optimizing it it-namely, the policy in our case-is commonly used in various settings (Wei al., 2020; Qiu et al., 2020; Ding al., 2021; Stradi al., 2025c). The purpose of this step is to derive a compact dual variable bound, which is essential for regret and violation analyses. However, this step breaks the recursive structure of policy optimization, so the resulting policy cannot be represented as a typical sofumax policy. As a consequence, the covering number argument becomes non-trivial. In other words, while policy mixing is simple and common, it poses a critical issue for covering number arguments in linear CMDPs. Despite these challenges, we aim to answer the following question:
Can we design a primal-dual policy optimization algorithm for adversarial linear CMDPs that ensures sublinear regret and violation bounds?
Main Contributions We answer the question affirmatively with Algorithm I, designed for finite- horizon adversarial linear CMDPs, where the losses are adversarially chosen under full-information feedback, and the costs are stochastic under bandit feedback. We summarize our main contributions.
We present a primal-dual policy optimization algorithm (Algorithm 1) for adversarial lin- ear CMDPs that achieves regret and constraint violation upper bounds of ((K3/4), where K is the number of episodes. Our algorithm is the first algorithm that achieves sublinear regret and violation in the adversarial linear CMDP setting. Moreover, the algorithm devel- ops new class of policies, which we refer to as weighted LogSumExp softmax policies, designed to adapt to adversarially chosen loss functions.
We establish a covering number argument for the novel class of weighted LogSumExp soft- max policies, induced by primal-dual policy optimization algorithms. The main technical difficulty arises from the fact that the weight parameters across policies may differ, prevent- ing direct application of standard properties of the LogSumExp function. Nevertheless, our analysis shows that the covering number under this policy class bounded by Ō(n²d²) where n is the maximum number of mixing steps, and d is the feature dimension of the linear CMDP.
Another challenge designing a sublinear algorithm for adversarial linear CMDPs lies in the need to simultancously control both the covering number and the dual variable. To address this, our algorithm incorporates two novel components: (i) periodic policy mixing and (ii) regularized dual updates. Since the covering number grows with the number of mixing steps, the purpose of periodic policy mixing is to regulate the frequency of mixing steps by applying it once in every specified mixing period, rather than in every episode. To incorporate periodic policy mixing, our dual update has to introduce an additional reg- ularization term in order to obtain a compact bound on the dual variable. Together, these algorithmic components allow us to effectively control both the covering number and the dual variable, establishing sublinear algorithm.
2

---

Published as a conference paper at ICLR 2026
A more detailed review of related work is deferred to the appendix.
2 PROBLEM SETTING
Finite-Horizon Adversarial CMDP A finite-horizon adversarial CMDP is defined by the tuple M - A, (Pa)==1 1f [==) $1, b), where H is the finite horizon, S is the finite state space', and A is the finite action space. {PA is a collection of transition kernels for each step h E [ where (s' s, a) denotes the probability of transitioning from state s to state s' the sequences of loss and cost functions hh and g = } Jh-i satisfy fh gh S x A [0, 1].
when action is taken at step h. {
jk=1 and {g*] jk=
over episodes & E [K], where fh { Th
H
$1 E is the fixed initial state, and b E [0, H| is the cost budget.
We consider setting where the loss functions are adversarial, while the cost functions are stochastic. Specifically, at the beginning of each episode it E [K], an adversary chooses the loss function f", which can be selected arbitrarily (i.e., not drawn from distribution). In contrast, the cost function ge is sampled i..dd from a fixed distribution G, satisfying [[gg (s, a) 18 a] = 9n
The interaction between the agent and the environment proceeds as follows. At the beginning of each episode & E [K], f is adversarially chosen, which is not revealed to the agent. Next, the agent selects collection of policies {T^)) where Th. (a 8) denotes the probability of taking action given state s at step h. Once the episode begins, at each step h E [H]. the agent samples an action an ~ [- s).. Upon taking as, the agent observes fh and g (8), az),, which are full-information feedback for the adversarial loss and bandit feedback for the stochastic cost, respectively. Lastly, the
next state sampled as 84+1 ~ P- 8h, ax).
We define the value function and the Q-function. Let V2,,, (s) denote the value function at state s and step with respect to a function
1f and policy æ, which is written as V (s) Ep jE (j( Sh = s]. Similarly, the Q-function (7, a) is defined as Q7,,, (s, 8h 8, a).
Ep.- C
We define the performance metrics regret and constraint violation as follows. Given se- quence of policies x! x'....,"" RK generated by the agent, the regret and constraint violation for K episodes are defined as Regret(K) = Σ
(V (V7 (x1) - (s1)) and Violation(K) = E (VTT((s) - b)] where |++ denotes max 03. Here, is an optimal policy, de- fined a solution to the following optimization problem over the set of all policies 11: arg min, enl Σ (x1) s.t. (s))
Linear CMDP We consider class of CMDP instances with underlying linear structure, re- ferred to as linear CMDP (Ghosh et al., 2022). Let Φ : S x A + Rd denote the known feature mapping. With the feature é, the transition kernel defined where 4y (s') E Rd is an unknown signed measure. Similarly, the loss and cost functions are as- sumed to be linear in & and are defined as f/ a) = a(s, a) 04,, and gn a) ((s, (), 0ggh. @h j.A. 9g.h E Id are unknown parameters. Moreover, we further assume that the parame- ters for linear CMDPs are all bounded as follows. For all (s, a, h, k) E S x A x [H] x [K], we 11l [10,. (1,,),,) S Vd. where (s.((s))) denotes
(s' |s. a) ő(s, a) (s')s)
where
have [|0(s, a) 1 and (1Ex /tb. (i.l(((')))))))))(()))) (
(1(v) (s') 1. (s))2.. .... 1( (sl)) T E Rdd.
Next, we introduce the Slater condition, which is a mild assumption commonly made in the CMDP literature (Efroni et al., 2020; Liu al., 2021; Ding et al., 2021: Ghosh et al., 2022).
Assumption 1 (Slater Condition). We assume that there exists Slater policy ã E IT such that 9.1 (51) + b for some Slater constant 7 > 0.
For simplicity, we assume that the state space is finite. However, the state space may be arbitrarily large, as discussed in Cassel et al. (2024), since the computational complexity of our algorithm-as well as the regret and constraint violation does not scale with [S], which will be presented in the following section.
3

---

Published as a conference paper at ICLR 2026
3 CHALLENGES AND NOVEL TECHNIQUES
Novelty 1: Analysis for Weighted LxgSumExp Softmax We construct a covering number ar- gument with new policy srtuctree-eeigheee LogSumExp softmax policies-which arises from combining policy optimization with policy mixing. This policy is given by the weighted sum of exponentials of sums of Q-function estimates?: given step size a, weight parameters Çi, and Q- function estimates Q²,
C exp
Σ
Q'
(I)
j=k-1
Let us explain how (1) arises in primal-dual policy optimization. Perturbing the primal variable be- fore optimizing it is a simple yet effective technique for controlling the scale of the dual variable (Wei et al., 2020; Qiu et al., 2020). In the context of policy optimization, this technique translates into the following update: given a uniform policy Tunif over A and mixing parameter 6,
(1 0)*h + Owanif and then
- * x π
Policy Mixing
Policy Optimization
Here, the additive relation (Policy Mixing) breaks the recursion in the proportional relation (Policy Optimization). As a consequence, the resulting policy takes the form of the weighted LogSumExp softmax. In particular, (1) may assign different weights G to partial sums Ljzk- Q' for i E [M] This yields a more expressive policy compared to the case without policy mixing, where the update simplifies to ** exp(-a E/= )²).
Our first contribution is to provide new covering number argument for the value function class, where the policy is given by (1). For comparison, Jin et al. (2020) studied the greedy policy, where the policy is defined as arg max Q* Then the covering number can be analyzed since the max operation is a contraction mapping. Moreover, the simple softmax policy has been studied in several works, e.g., Ghosh et al. (2022). In that case, leveraging well-established Lipschitz properties of the softmax function is sufficient to analyze the covering number.
We note that constructing a covering number argument for (1) is non-trivial. The main difficulty is that the weight parameters {G) depend not only the mixing parameter 0 but also on Q- function estimates. This means that different policies have different weight parameters { i= and thus, well-known properties of LogSumExp cannot be applied. Despite these challenges, our analysis shows that the logarithm of the covering number under (1), denoted by log.N. grows quadratically with n, where n is the maximum number of mixing steps during the learning process:
log N₂ Ö(n ))
(2)
Novelty 2: Periodic Policy Mixing However, deriving an upper bound on the covering number alone is not sufficient to guarantee sublinear regret and violation. In particular, if mixing is applied in every episode, then log NV grows to the order of (()2d)). which is too large to yield a sublinear guarantee. On the other hand, if mixing is performed insufficiently, then the dual variable cannot be bounded, which is critical for violation analysis. These observations highlight an inherent trade-off between the covering number and the size of dual variables, both of which heavily depend on the frequency of mixing. This necessitates a new algorithmic component to balance the two.
The aforementioned trade-off motivates second contribution-periii applies the policy mixing every K episodes?, where B is period parameter between 0 and 1. The purpose of the periodic policy mixing is balance the covering number and the size of dual variables. The covering number can be easily observed from (2), since the number of mixing steps most K1-B (i.e., the number of episodes divided by the mixing period). However, it remains unclear whether periodic policy mixing is effective in controlling the dual variable. To address this, in the next paragraph, we show that the dual variable can indeed be bounded when periodic policy mixing is combined with a new dual update rule.
policy mixing-whieh
We call this formulation the weighted LogSumExp softmax, as it is equivalent to #t x exp(log(E, & Geep(=a Σ, )))) softmax of weighted LogSumExp with respect to -a E, Qi. Foor simplicity, we assume that R k1 are integers avoid additional notation such as K
4

---

Published as a conference paper at ICLR 2026
Novelty 3: Regularized Dual Update Our third contribution is another algorithmic component a new dual update rule with additional regularization. When combined with periodic policy mixing, the dual variable Yx is bounded by Ö(nk B), where 1) is the step size and K B is the mixing period. For clarity, this bound omits the dependence on 7, H highlight the impact of the mixing period.
To elaborate on our dual update method, it takes the following form: given regularization parameters C1, 22 > 0 and the cost value function estimate 1/ 9.1-
Y + [Y + (V 9,
g, - b) + (-aYa -2)]
Regulatization
For interpretation, Y2 + (1 b) corresponds to the standard online gradient ascent step for dual updates in primal-dual algorithms, while the regularization term (-c Vi - c2) pulls the dual
variable towards 0, keeping it compact. The regularization parameters c1, C2 will be specified in the following paragraph, along with the intuition for our design.
The intuition behind our regularization is that it serves crucial ingredient for drift-based anal- ysis, a well-known method for bounding dual variables (see, e.g., Yu al. (2017); Wei et al. (2020) in constrained online convex optimization). To enable drift analysis, these works typically incorpo- rate an inner product term in the dual update, determined by the decision variables and the gradient, i.., (#441 Fi, V.). In primal-dual policy optimization, we realize that this translates to term involving the transition kernel, i.e., [p((=*+1 7* [-)]. However, since the transition kernel is unknown, this term cannot be directly incorporated into our algorithm. Instead, we take lower bound on this term, which becomes our regularizing component with the choice of c = H33 and C2 4an/1 + 40m/122 In this way, our dual update can be viewed as a key adaptation that enables drift analysis in primal-dual policy optimization for adversarial linear CMDPs.
ALGORITHM
We present Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses(Algorine 1). The algorithm consists of four main components: epoch initialization (lines 2-7), policy execution and estimation (lines 8-19), policy optimization with periodic policy mixing (lines 20-26), and updating the dual variable (line 27).
In lines 2-7, the algorithm initializes new epoch when the determinant of the design matrix A& decreases by a multiplicative factor compared to that of AA: for some nt. Once the initialization procedure begins, the algorithm sets the policy to the uniform policy and initializes the dual variable to O. Furthermore, it defines a contracted feature oke by shrinking the original feature o. The multi- plicative contraction factor is determined by o- ( (A + log K), where a denotes the sigmoid function, and || : > quantifies the current uncertainty of least-squares estimators.
This contracted feature is then used in the estimation of Q-functions. Remark 1.
The feature contraction-oriiinne originally proposed by Cassel & Rosenberg (2024) for ad- versarial linear (unconstrained) MDPs-is necessary for the following reason. Specifically, it pro- vides simpler expression for the policy, which is useful in covering number arguments, via a low- dimensional representation of the sum of Q-function estimates. For this, they omitted a clipping operation in the definition of Q-function estimates, the sum collapses into simple inner prod- uct with an optimistic bonus. Instead of clipping, they properly contracted the feature to prevent Q-function estimates from expanding uncontrollably. This technique can be replaced with other ap- proaches with the same purpose, such as Sherman et al. (2024), but it may lead to higher dependence on d, H in regret and violation bounds.
In lines 8-10, the algorithm takes action of ~ (-1s)) for each step h E [H] and observes 8 /.h. of (sf ). and $ ~ (. ())) In lines 11-14, the design matrix A/+ is updated, and the parameters for the loss and cost functions are estimated, denoted by 0i., and 02. respectively. Based on these, in lines 15-19, for each é = f. f.g. it computes the Q-function estimates Q A a) using the contracted feature and the value function estimates 1 (s), which are defined by the inner product of 2े (-1s) and Q (8, :) for each E S.
5

---

Published as a conference paper at ICLR 2026
Algorithm Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses
Input: 5 (0. 3
+ 50(K + 1)dH Vlog(HHH (|]/()((())))).... Bv
1og K, ---I----//// 1] -= 11 1 K-1
Initialization: Y1 t 0, e e 0, A I, VL (H)
v(h,k,,, [ [ x x {f.g}
1: for == 1....... K do
2:
if = 1 3h' E [H] such that det (et(A 2 2 dct then
3:
e c + and lig t k
ske (- (1) + Tunir(: 8) wh E [H]
4:
"h
5:
Yg. 6 0
6:
The (..) = -((.)) a Ø(; (ate) log K) vh [M]]
D Feature Contraction
7:
end if
8:
for 1..... H do
9:
Take d
T s and observe ofmm gf (sh ah), sh4t Pa(. s aft)
10:
end for
11:
for
H,.... 1 do
A
I ΣTERh (88
Pi, - -0/,,
gg + (AA))
"Ere(k-1) (s5 (5)
15:
for E { do
16:
J.V 1,1+1 = (A/)) " E 055 a7) V.t
e (5
(t,)) t 2h (:-)T 0ū + 4/h V.
2hh+1 [
3 1o112h (-))llatt))
18:
V.A (.) + -aEEA (a
11 (:aa)
19:
end for
20:
if k
0) mod K3/4 then
Periodic Policy Mixing
21:
( 8) t (1 0) 8) Owuiit (ss)
22:
else
23:
7/( (8) + xt x)
24:
end
25:
* (. 8) x .- $) exp
>> Policy Optimization
26:
end for
Yk+1 (1 4am 4aml1 + (V/1 - b- ---11113- 40113-40113)
27:
Dual Update
end for
In lines 20-24, the algorithm applies the policy mixing every K3// episodes. Here, the mixed policy obtained by taking a convex combination of 77 and Tunit with coefficients 1-0 and f, respectively. After this, the algorithm performs policy with Kullback-Leibler (KL) divergence over the policy space.
earrtttioonnnuivllleettt... online mirror descent step
In line 27, the algorithm updates the dual variable, Yg. First, it scales down the dual variable by y. (s1) - b da1l3-40113) Finally, it takes [+ to ensure factor of 1 / and then adds ([Vk
that the dual variable remains nonnegative.
The computational complexity of Algorithm is O d'AAHH?),, which independent of (S). Specifically, in lines 2-7, computing determinants simply takes H(d" and contracting features takes (dd² K H)), since the inverse of the design matrices can be computed in O(d by applying the Sherman-Moriae formula. In lines 8-29, the dominant step is function estimation: lines 16-18 take ((()).
4.1 COMPARISON DUAL UPDATES
Since algorithm is designed for adversarial linear CMDPs, is worth comparing dual update with that of algorithms for (i) stochastic linear CMDPs (Ghosh et al., 2022) and (ii) tabular CMDPs with adversarial losses (Qiu et al., 2020).

---

Published as a conference paper at ICLR 2026
First, we compare with Ghosh al. (2022), which focused stochastic linear CMDPs. The key difference comes from the way the dual variable is regularized. Specifically, while both approaches adopt the standard online gradient ascent procedure, their update rule truncates the dual variable at 2 to ensure that it never exceeds this threshold. In contrast, our update incorporates an extra regularization term to keep the dual variable compact. Although their update is simple and effective in the stochastic setting, it cannot be extended to the adversarial setting, since their analysis relies on the fact that the loss and cost functions are fixed over episodes. This justifies the need for our design of dual update steps in handling adversarial losses.
Second, we compare with Qiu et al. (2020), which proposed an occupancy measure- measure-based algorithm for adversarial tabular CMDPs. The main difference in the dual updates arises from the choice of primal variable: policy-based mirror descent versus occupancy measure-based mirror descent. Before elaborating on this, we recall a dual update from the constrained online convex optimization literature, proposed by Wei et al. (2020) with minor modifications: given convex cost function e: [2d + IR and primal variables x² -xtt1 1 E Rd.
Y&+1 (Y 17 (A(x*) - b+
x11)]+--
Based on this update, let us show how the dual update for occupancy measure-based algorithms can be derived. Since the occupancy measure serves as the primal variable, we take x² < "g, where q² denotes an occupancy measure in episode k. Furthermore, in CMDPs, note that the expected cost is given by (g. gh where g E R. S|x [A| denotes a vector representation of the cost function. Then we can take {(=*) + (g. g²) and v((x*) + g. This leads to Yx+1 [Yr + ((gg.g 6)]++ which is the key intuition behind the dual update in Qiu et al. (2020).
However, this argument does not apply to policy-based mirror descent. This is because even if we take _² +- n² the expected cost is not linear in n² unlike in the occupancy measure case. That said, the dual updates for occupancy measure- measure-based algorithms can be extended from the online convex optimization literature, whereas extending this to policy-based algorithms is non-trivial. This highlights the significance of our proposed design.
4.2 MAIN RESULT
Finally, we present upper bounds on regret and constraint violation under Algorithm 1.
Theorem 1. Let H2 < K and Assumption hold. Suppose that we run Algorithm 1. Given 5 > 0, with probability at least 1 25, then have
Regret (K) = (
H
dH 22
d3343/14 HH
k1/4
72
Violation =ō (dHs 3/4 V -
=(1r))
HH1/111
where (.) hides fact in log(dHK]AA/(m))
5 ANALYSIS
In this section, we present the proof outline of Theorem where the details of the proofs can be found in the appendix. As a first step. we introduce two key ingredients: (i) a high-probability good event and (ii) bounding the dual variable. We note that our covering number argument plays central role in showing that the good event holds with high probability. Furthermore, to bound the dual variable, the key part to consider periodic policy mixing and the regularized dual update.
Good Event We first introduce a giggh-rrbbbblity event, denoted by Eg. whose formal definition provided in the appendix. Basically, the event captures estimation errors for the loss, the cost, and the transition kernel. In addition, it guarantees the boundedness of Q-function estimates, reflecting the usefulness of the feature contraction. The following lemma shows that E, holds with high probability.
Forr simplicity, we assume that g deterministic and known, and q" is induced by the true transition kerne..

---

Published as a conference paper at ICLR 2026
Lemma 1. Let Bw I K. Then for any 8 E (0,1), Pr(Eg] 2 8.
In the proof of Lemma 1, the main distinction from previous works arises in our covering number argument. Specifically, our case incorporates weighted LogSumExp softmax policies, induced by mixing the policy. Then we have to derive a Lipschitz property of the policies that have been mixed times, as the number of mixing steps is key factor in determining the policy structure. Note that the Lipschitzness of policies is fundamentally required in most covering number arguments.
To attain this property, we prove the following recursion in n, presented here in simplified form: || 2 1 c|
"2 - 11++1PP - -P2 ll2
where RT, T denote the policies that have been mixed times, PT. P3 denote the subsets of the corresponding parameters, and is a constant. By applying this recursion repeatedly, we can bound the difference between policies using the sum of differences in their parameters, establishing the Lipschitzness. Based on this,
show that the covering number is bounded as O(?dd).
Dual Variable Bound Under the good event Egg. we can establish another ingredient of our analysis drift analysis for bounding the dual variable.
Lemma 2. Assume that the good event Fg holds. Let H² < K. Let Ys be the dual variable generated by Algorithm I for each E [K]. For any 8 E (0,1) and k [K], with probability at least 1- 8, we have Yx = ((H21))))))
Let us briefly explain our proof strategy for Lemma Although the regularization in our dual update enables drift analysis, we cannot directly apply the previous proofs proposed by Wei et al. (2020); Qiu al. (2020). This because their analyses rely on applying policy mixing in every episode, whereas our algorithm applies it only sparsely. To exploit this sparse structure, we instead consider a subsequence of dual variables corresponding to the mixing episodes, denoted by {Za)xz) where Zn, YE, t for each epoch We first bound Zn for all n. and consequently extend the result to derive a bound on Y3 for all k.
Next, we introduce decompositions of both Regret (K) and Violation(K). Let E be the set of all epochs, and let Ke be the set of episodes in epoch e E E. We have
Regret(K) S
(i
(11(
Yx b
(s1)
(
K
Vh (11) + D. (x1)
V - Yo Ye 9.1
(51)
(3)
(m
K
K
Violation(K) K) <
Vx" (81) DK (81)
+
De 9.1
(81) -b)
Terms (I), (IV) arise from the difference between the true value function and its optimistic estimates, which are closely related to the optimistic bonus -3, 1 (., (.-))lla Since our parameter for op- timistic bonus set as 3b ((K)/AdH) where 1/4 comes from the covering number argument, these terms are bounded by (KK3/4), as stated in the following lemma.
Lemma 3. Let 112 <. K. Suppose that Eg holds. For all é {f.g).
Σ (VVz)(s) - =
(V -
+ +
Term (II) arises from the dual update in the sense that if the dual variable is not updated (i.e., Y₁ = for all k), then this term vanishes. It can be bounded using the following lemma.
8

---

Published as a conference paper at ICLR 2026
Lemma 4. Let H < K. Suppose that Eg and the statement of Lemma 2 hold. Then have
Σ Ya (s1)) = 3 K1/4
dH
722
To bound term (III) further decompose it into two parts optimism terms and an online mirror descent term verm-and then bound each individually. This leads to the following lemma. Lemma 5. Let H22 K. Suppose that Eg and the statement of Lemma 2 hold. Then have
V (s1( + V. (81) - (VT + V.V.i = =6 (aH² +
H
1/44
dHs
72
k=1
Finally, term (V) be bounded via the dual variable bound. This is because niVk g. (51) b) accumulates in the dual variable, as it is repeatedly added in the dual update. Based on this idea, we show the following lemma, which bounds term (V).
Lemma 6. Let 2 S K. Suppose that Eg and the statement of Lemma 2 hold. Then we have
d
H K k2/4)
Σ (P (81) - 6)
K3/
+
NUMERICAL EXPERIMENT
We evaluate Algorithm 1 on job-scheduling CMDP (Ghosh et al., 2022), modified to incorporate adversarial losses. We conduct 10 sinulations with different random seeds, each running for K 10 episodes. Additional details about the experimental setup are deferred to the appendix.
Viaettin
2.0
0.5-
0.0-
20000
40000
50000
80000
100000
20000
40000
50000
80000
100000
Episode
Episode
(a) Regret
(b) Constraint Violation
Figure 1: Plots of regret and constraint violation for K = 100,000 episodes. Each plot represents the average over 10 trials with random seeds, and shaded regions indicate 95% confidence intervals.
Figure summarizes the results. As shown in Figure Ia, the regret grows sublinearly in K, and Figure lb shows that while the constraint violation grows rapidly in the early phase, it eventually converges These results support our theoretical claims.
CONCLUSION
This paper studies adversarial linear CMDPs, where the losses adversarially chosen under full- information feedback and the costs are stochastic under bandit feedback. We propose a primal-dual policy optimization algorithm- the first provably efficient algorithm for safe RL with linear function approximation in adversarial settings. We establish new covering number argument for weighted LogSumEXp softmax policies, along with novel algorithmic components that jointly control the covering number and the dual variable. Building on these, we show that the proposed algorithm achieves O ((33/4) regret and violation bounds. Moreover, our numerical experiments support this. As directions for future work, it remains open to investigate the following challenges: (i) whether Ō(VK) regret and violation bounds can achieved in our setting, and (ii) whether a sample- efficient algorithm can be designed for linear CMDPs with adversarial losses under bandit feedback.

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
We would like thank the review team for their careful review and valuable feedback. This work was supported by the National Research Foundation of Korea (NRF) grant (No. RS-2024-00350703) and the Institute of Information communications Technology Planning & evaluation (ITPP) grants and (No. RS-2021- 1343, Artificial Intelligence Graduate School Program (Seoul National University)) funded by the Korea government (MSIT).
(No.
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International conference on machine learning, pp. 22-31. PMLR, 2017.
Eitan Altman. Constrained Markov decision processes. Routledge, 2021.
Sanae Amani, Christos Thrampoulidis, and Lin Yang. Safe reinforcement learning with linear func- tion approximation. In International Conference on Machine Learning, pp. 243-253. PMLR, 2021.
Archana Bura, Aria HasanzadeZomuzy Dileep Kalathil, Srinivas Shakkottai, and Cran-Francois Chamberland. Dope: Doubly optimistic and pessimistic exploration for safe reinforcement learn- ing. Advances in neural information processing systems, 35:1047-1059, 2022.
Asaf Cassel and Aviv Rosenberg. Warm-up free policy optimization: Improved regret in linear markov decision processes. Advances in Neural Information Processing Systems, 37:3275-3303, 2024.
Asaf Cassel, Haipeng Luo, Aviv Rosenberg, and Dmitry Sotnikov. Near-optimal regret in linear mdps with aggregate bandit feedback. In International Conference Machine Learning, pp- 5757-5791. PMLR, 2024.
Liyu Chen, Rahul Jain, and Haipeng Luo. Learning infinite-horizon average-reward markov decision process with constraints. In International Conference on Machine Learning, pp. 3246-322 3270. PMLR, 2022.
Yi Chen, Jing Dong, and Zhaoran Wang. A primal-dual approach to constrained markov decision processes, arXiv preprint arXiv:2101.10895 2021.
Antonio Coronato, Muddasar Naeem, Giuseppe De Pietro, and Giovanni Paragliola. Reinforcement learning for intelligent healthcare applications: A survey. Artificial intelligence in medicine, 109: 101964, 2020.
Yan Dai, Haipeng Luo, Chen-Ye Yu Wei, and Julian Zimmert. Refined regret for adversarial mdps with linear function approximation. International Conference on Machine Learning, pp. 6756- PMLR, 2023.
Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. In International conference on artificial intelligence and statistics, pp.
PMLR, 2021.
Yuhao Ding and Javad Lavaei. Provably efficient primal-dual reinforcement learning for emdps with non-stationary objectives and constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 7396-7404, 2023.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Explovation-exploiaatio constrained mdps. arXiv preprint arXi::2003.02/88 2020.
Arno Ghosh, Xingyu Zhou, and Ness Shroff. Provably efficient model-free constrained rl with linear function approximation. Advances in Neural Information Processing Systems, 35:13303- 13315, 2022.
10

---

Published as a conference paper at ICLR 2026
Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Achieving sub-linear regret in infinite horizon aver- age reward constrained MDP with linear function approximation. In The Eleventh International Conference Learning Representations, 2023. URLhttps: http:///pppeeeeeeeeeeeeeeeeeeeee net forum? idd=zZXX4eYNeeh.
Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Towards achieving sub-linear regret and hard con- straint violation in model-free rl. In International Conference on Artificial Intelligence and Statis- tics, pp. 1054-1062. PMLR, 2024.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Opti- mization, 2(3-4):157-333 2016.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Near-optimal policy optimization algorithms for learning adversarial linear mixture mdps. In International Conference on Artificial Intelligence and Statistics, pp. 4259 4280. PMLR, 2022.
David Isele, Alireza Nakhaei, and Kikuo Fujimura. Safe reinforcement learning on autonomous vehicles. In 2018 JEEE/RSJ International Conference Intelligent Robots and Systems (IROS), pp. 1-6. IEEE, 2018.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference learning theory, pp. 2137-2143. PMLR, 2020.
Toshinori Kitamura, Arnob Ghosh, Tadashi Kozuno, Wataru Kumagai, Kazumi Kasaura, Kenta Hoshino, Yohei Hosoe, and Yutaka Matsuo. Provably efficient rl under episode-wise safety in constrained mdps with linear function approximation. arXiv preprint arXiv:2502. 10138, 2025.
Fang Kong, XiangCheng Zhang, Baoxiang Wang, and Shuai Li. Improved regret bounds for linear adversarial MDPs via linear optimization. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL https: wwtp///peeeeeeeeeeeeeeeeee net forumm Beerummid-Koann dd=KmmWsk533..
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Haolin Liu, Chen-Yu Yu Wei, and Julian Zimmert. Towards optimal regret in adversarial linear MDPs with bandit feedhack. In The Twelfth International Conference on Learning Representations, 2024. URL https:/ pettps://openeevee....
Tao Liu, Ruida Zhou, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained mdps. Advances in Neural Information Processing Systems, 34:17183-171923 2021.
Xingtu Liu, Lin F Yang, and Sharan Vaswani. Sample complexity bounds for linear constrained mdps with a generative model. arXiv preprint arXiv:2507.02088 2025.
Haipeng Luo, Chen-Yo Yu Wei, and Chung-Wei Lee. Policy optimization adversarial mdps: Im- proved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34: 22931-22942, 2021.
Adrian Müller, Pragnya Alatur, Giorgia Ramponi, and Niao He. Cancellation-free regret bounds for lagrangian approaches in constrained markov decision processes. arXiv preprint arXiv:2306.07000, 2023.
Adrian Müller, Pragnya Alatur, Volkan Cevher, Giorgia Ramponi, and Niao He. Truly no-regret learning in constrained mdps. International Conference on Machine Learning, pp. 36605 36653, PMLR, 2024.
Gergely Neu and Julia Olkhovskaya. Online learning in mdps with linear function approximation and bandit feedback. Advances in Neural Information Processing Systems, 34:10407-10417, 2021.
Shuang Qiu, Xiaohan Wei, Zhuoran Yang. Jieping Ye, and Zhaoran Wang. Upper confidence primal- dual reinforcement learning for emdp with adversarial loss. Advances in Neural Information Processing Systems, 33:15277-15287, 2020.

---

Published as a conference paper at ICLR 2026
Amirhossein Roknilamouki, Arnob Ghosh, Ming Shi, Fatemeh Nourzad, Eylem Ekici, and Ness Shroff. Provably efficient RL for linear MDPs under instantaneous safety constraints in non- convex feature spaces. In Forty-second International Conference Machine Learning, 2025. URL /ttp::////ppeeeeeeeeeee wwt...neefoorunnnee//eeeeeo forum? d= Aq.srQ
nnt.
Aviv Rosenberg. Alon Cohen, Yishay Mansour, and Haim Kaplan. Near-optimal regret bounds for stochastic shortest path. In International Conference on Machine Learning, pp. 8210-8219. PMLR, 2020.
Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. International Conference on Machine Learning, pp. 8604-8613, PMLR, 2020.
Uri Sherman, Tomer Koren, and Yishay Mansour. Improved regret for efficient online reinforcement learning with linear function approximation. In International Conference on Machine Learning, pp. 31117 11117-31150 150. PMLR, 2023.
Uri Sherman, Alon Cohen, Tomer Koren, and Yishay Mansour. Rate-optimal policy optimization for linear markov decision processes. In International Conference on Machine Learning, pp- 44815-44837. PMLR, 2024.
Ming Shi, Yingbin Liang, and Ness Shroff. A near-optimal algorithm for safe reinforcement learning under instantaneous hard constraints. In International Conference on Machine Learning, pp- 31243-31268. PMLR, 2023.
Francesco Emanuele Stradi, Jacopo Germano, Gianmarco Genalti, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Online learning in emdps: Handling stochastic and adversarial con- straints. In Forty-first International Conference on Machine Learning, 2024.
Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Learning ad- versarial MDPs with stochastic hard constraints. In Forty-second International Conference net/ o Dww.idddsssswwoocomme
Machine Learning, 2025a. URL
Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Optimal strong regret and violation in constrained MDPs via policy optimization. In The Thirteenth Interna- tional Conference on Learning Representations, 2025b. URL https: pettpss:/cpenrreiieet net/ forum? Satimm?iddeeNexk55yr
Francesco Emanuele Stradi, Anna Lunghi, Matteo Castiglioni. Alberto Marchesi, and Nicola Gatti. Policy optimization for emdps with bandit feedback: Learning stochastic and adversarial con- straints. In Forty-second International Conference on Machine Learning. 2025c.
Tian Tian, Lin Yang, and Csaba Szepesvári. Confident natural policy gradient for local planning in 4ar reallizable constrained mdps. Advances in Neural Information Processing Systems, 37:76139- 76176, 2024.
Honghao Wei, Xin Liu, and Lei Ying. A provably-efficient model-free algorithm for infinite-horizon average-reward constrained markov decision processes. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 3868-3876, 2022a.
Honghao Wei, Xin Liu, and Lei Ying. Triple-q: A model-free algorithm for constrained reinforce- ment learning with sublinear regret and zero constraint violation. In International Conference on Artificial Intelligence and Statistics, pp. 3274-3307. PMLR, 2022b.
Honghao Wei, Arnob Ghosh, Ness Shroff, Lei Ying, and Xingyu Zhou. Provably efficient model- free algorithms for non-stationary emdps. In International Conference Artificial Intelligence and Statistics, pp. 6527-6570. PMLR, 2023.
Honghao Wei, Xin Liu, and Lei Ying. Safe reinforcement learning with instantaneous constraints: the role of aggressive exploration. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 38, pp. 11708-217166 2024.
12

---

Published as a conference paper at ICLR 2026
Xiaohan Wei, Hao Yu, and Michael Neely. Online primal-dudl mirror descent under stochastic constraints. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(2): 1-36, 2020.
Hao Yu, Michael Neely, and Xiaohan Wei. Online convex optimization with stochastic constraints. Advances in Neural Information Processing Systems, 30, 2017.
Kihyun Yu, Duksang Lee, William Overman, and Dabeen Lee. Improved regret bound for safe reinforcement learning via tighter cost pessimism and reward optimism. Reinforcement Learning Journal, 2025.
Han Zhong and Tong Zhang. A theoretical analysis of optimistic proximal policy optimization in linear markov decision processes. Advances in Neural Information Processing Systems, 36: 73666-73690, 2023.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learn- ing for linear mixture markov decision processes. In Conference on Learning Theory, pp. 4532- 4576. PMLR, 2021.
Jiahui Zhu, Kihyun Yu, Dabeen Lee, Xin Liu, and Honghao Wei. optimistic algorithm for online CMDPS with anytime adversarial constraints. In Forty-second International Conference Machine Learning, 2025. URL https: http:///eeeeeeeeettetoorounmmaaa fftee//oooooomiddd-aaaaaa-a E.
13

---

Published as a conference paper at ICLR 2026
A
NOTATION
Table I: Summary of notation
NOTATION
DEFINITION
H, A,K
The finite-horizon, the state and action spaces, and the number of episodes
d
The feature dimension
The transition kernel The loss and the cost functions The budget The set of epochs The first episode epoch & E The feature
f.9
E
The contracted feature step h in epoch
The estimate of 6
The design matrix at step h in episode Eves V (s') for V S - R
V
The estimate of t/% at step h in episode
m
The set {1, 2, ................................ n for a positive integer n The {0, ..
R.
The set {z E 2 0}
The f--norm for vectors and the operator norm for matrices The -orm
111100
|+||
The Frobenius norm
MA
| vx.7 Az for >
(AA)
The probability simplex over A
The x d identity matrix Kullback-Leibe divergence The sigmoid function
D(I))
The Slater constant and the Slater policy
(s,()
The Q-function
Q (s.
The Q-function estimate
(z)(s)
The value function
Vk (s)
the value function estimate
The value function with respect to a p-contracted MDP
#k
The policy at step in episode kt
Tanif
Tuuif s) = 1/| for all (s, a)
The dual variable in episode k
KB
The mixing period, 3/4
The mixing parameter,
-1
The step size for the mirror descent, a - The step size for the dual update, 17 - 3/4 2 222d log (6K
17
8r
Bp
50(K1/1 + 1)dH (log(5H=<2(A1/6))
36
3, + 3p
Bw
43, log K
8Q.b
2(H h +1
No
The e-covering number of 10 with respect to the fo norm
B LIMITATIONS OF PRIOR WORK AND NAIVE EXTENSION
In this section, we clarify why previous works and their naive extensions fail in our setting, where the losses adversarially chosen in each episode. In particular, address the following
14

---

Published as a conference paper at ICLR 2026
two questions: (i) why the algorithm of Ghosh et al. (2022) fails in the adversarial setting; and (ii) why simply adapting a mirror-descent update is insufficient for adversarial linear CMDPs.
Limitation of Prior Work While Ghosh et al. (2022) proposed a primal-dual algorithm for linear CMDPs, their analysis is limited to the setting with stochastic losses and constraints. The funda- mental reason is that their algorithm is value-based, whose policy is determined solely by the current Q-function estimates in each episode; that is (- 8) x exp( exp(-a(*=1) -. Such a policy cannot adapt to time-varying environments, and in particular, cannot handle adversarially chosen losses.
Another limitation is that the dual update of Ghosh al. (2022) fails handle adversarial envi- ronments. Their key technique is a dual clipping technique-eutting off the dual variable when it exceeds 2/1/n-which enables them leverage the strong duality of CMDPs. Moreover, to lever- age strong duality in their analysis, they reformulate the weighted sum of regret and violation into simple Lagrangian form (e.g., Appendix D of Ghosh et (2022)). i... there exists policy x such that
K <E +Y
+
E (Vg - -b) (V + -). -b.
In case, when losses adversarially chosen in each episode, reformulating the sum into simple Lagrangian form is not allowed, i.c.,
Σ (V V7. +
(V 9.1
b)) + (V - - +Y b).
K
In turn, leveraging strong duality in our setting is non-trivial.
Naïve Extension To overcome the limitations of value-based algorithms in adversarial settings, natural approach is to adopt a mirror-descent update, whose regularizer is given by a KL divergence. In our case, this corresponds a policy optimization, i.e.,
arg min (x, Q*-1)) a D(m[|=*=1)
x a exp (-aQt-1)
=
Due to its recursive formulation, we can see that the resulting policy depends on the sum of all pre- vious Q-function estimates, namely ** xx exp(-a > )²). This is the key difference compared with value-based based algorithms.
More technically, let us attempt to adapt the algorithm of Wei et (2020) to the linear CMDP set- ting. Their method is mirror-descent type algorithm-in our case, policy appimization-desipee for constrained online convex optimization with adversarial losses and stochastic constraints. Be- yond policy optimization, there are two additional distinctions compared with Ghosh et al. (2022);
(Drift Analysis) As previously mentioned, since strong duality is difficult to in the adversarial setting, the dual clipping technique may not works in the adversarial setting. To address this, Wei et al. (2020) came up with dual update that admits a Lyapunov drift analysis. In particular, Lyapunov drift analysis is standard tool for bounding the dual variable. For this, we first derive an upper bound on the Lyapunov drift term defined as A(k) := (Y2+1 / and then utilize it to bound Y,. The key point is to make Akk) small enough so that Ys stays stable, as A(k) captures the difference between successive dual variables.
(Policy Mixing) Another key technique of Wei et al. (2020) is policy the policy before applying the policy optimization update. The motivation behind this tech- nique is to make (k) small. In particular, typical bound on A(k) in policy optimization involves KL divergence terms as follows:
(kk) < -c +2 D(* - D(m
The key issue is that D (( can become arbitrarily large when मे (a) 0 for some A, because the KL divergence is unbounded near the simplex boundary. In contrast, when a mixing step is applied, mixing. In this case, the mixing step guarantees that the KL term remains bounded, which turn prevents the dual variable from blowing up.
ensure that 75 (a) 2 0/| for all a, where 9 denotes the level of easily show that ( (+))) Log([AA// (Lemma 26). Hence,
15

---

Published as a conference paper at ICLR 2026
Insufficiency of Naive Extension While policy mixing is essential to keep the dual variable stable, it becomes problematic in the linear CMDP setting, where the main difficulty arises in the covering number argument. In particular, the covering number of the weighted LogSumExp softmax policy. Establishing such a bound is one of our key challenges and is highly non-trivial. Thus, although adapting Wei et al. (2020) to the framework of Ghosh et al. (2022) is a natural step toward handling adversarial losses, obtaining sublinear regret and constraint violation bounds becomes unclear.
described in Section 3, we have to derive an upper bound on
C ADDITIONAL DISCUSSIONS
Intuition on Covering Number We provide an intuition on why the weighted LxgSumExp soft- max policy yields )n?)d), where n denotes the number of mixing steps, while the covering number under greedy or softmax policies is just (dd)) Before explaining this, we note that the covering number of a function class depends on (i) how many parameters are required and (ii) how close these parameters must be for the functions to be sufficiently similar. Based on this high-level idea, the number of parameters needed to determine a weighted LogSumExp softmax policy is Ondd), as each Σ, Q' requires (d²) parameters once the feature contraction is applied. Furthermore, we observe that the impact of parameters decreases exponentially as mixing continues, meaning that the parameters must be chosen increasingly close (see the proof of Lemma 11). This leads to an additional multiplicative factor n, resulting in dn?
To justify the choice of K3/4, we first clarify how Regret(K) and Violation () depend on the mixing period KB Note that the covering number is closely related to terms (I) and (IV) of the decompositions in (3), and the dual variable directly affects term (V). This yields the following simplified regret and constraint violation bounds.
Choice of Mixing Period
Regret (K) = Ö( K log.N.) Violation(K] K) = Ö(V K N. + Ya/n).
We emphasize that Violation K) can be bounded by Ō(VK3-2B + KB). This is because the log covering number is bounded by Ö O(K222B (2))) and the dual variable is bounded by Ö(n Thus, to minimize the dependency on K, we set = 3/4.
Discussion on Lower Bound We note that the regret lower bound of Ω ([VHHdd also applies to our setting, which is for stochastic linear unconstrained MDPs (Zhou et al., 2021; He et al., 2022). This is because by taking the loss to be fixed across episodes and using a trivial constraint (i.e., taking b = H), our problem reduces to a stochastic linear unconstrained MDP. Therefore, we conjecture that there remains room for improving our regret bound by factor of Ö(K1/4).
Additionally, we outline a promising direction toward achieving ((V K)) regret and violation in our setting. The main challenge is analyzing the constraint violation without relying on mixing steps. In our current analysis, the mixing step is inevitable to mitigate KL divergence terms in the drift upper bound (Lemma 17); these KL divergence terms arise from mirror-descent type updates to control adversarial losses. However, mixing becomes problematic for linear CMDPs because it enlarges the covering number. If one can design an approach that controls the dual variable without mixing, then achieving optimal bounds may become possible.
D RELATED WORK
Online Tabular CMDP Starting from the seminal work of Efroni al. (2020), minimizing regret and constraint violation in online tabular CMDPs has been studied under various settings. Several works (Liu et al., 2021; Bura et al., 2022: Yu et al., 2025) considered the case of zero constraint violation under the assumption of known safe policy. Under the same assumption, Müller et al. (2023) studied hard constraint violation the sum of only positive constraint violations. Without this assumption, the hard constraint violation was studied by Müller et al. (2024); Stradi et al. (2025b). Moreover, Wei et al. (2022b) proposed a model-frr algorithm for finite- horteehorzzon CMDPs, and Wei al. (2022a); Chen et al. (2022) proposed algorithms for
average-reward CMDPs.
16

---

Published as a conference paper at ICLR 2026
However, these works assume stationary environments. To relax this assumption, Qiu et al. (2020) studied adversarial losses under full-information feedback. For both adversarial losses and costs, Stradi et al. (2024; 2025c) considered full-information feedback and bandit feedback, respectively. More recently, several papers proposed algorithms for adversarial CMDPs with hard constraint vio- lation guarantees. Stradi al. (2025a) proposed an algorithm for adversarial losses and stochastic costs under bandit feedback, and Zhu et al. (2025) studied stochastic losses and adversarial costs under full-information feedback.
Online Linear CMDP For finite-horizon linear CMDPs, Ghosh et al. (2022; 2024) studied cumu- lative and hard constraint violations, respectively. Similarly, Ghosh et al. (2023) developed several algorithms for the infinite-horizon average-reward setting. Kitamura et al. (2025) studied achiev- ing zero constraint violation under the assumption of a known safe policy, and Liu et al. (2025) studied sample complexity under the assumption of generative model. Wei et al. (2023) studied non-stationary CMDPs, where components of the environment may change subject to bounded total variation. However, this setting differs from adversarial settings, in which the variation of functions not assumed to be bounded by some factor. Amani et al. (2021); Wei et al. (2024); Roknilamouki et al. (2025) investigated hard instantaneous constraints, where unsafe actions must not be taken in each step. We also note additional works that are not linear CMDPs but incorporate linear function approximation. There are several works for linear mixture CMDPs with various settings (Ding et al., 2021; Ding & Lavaei, 2023; Shi et al., 2023). More generally, the 4 rearlzzzal setting was studied by Tian et al. (2024), which only assumes that value functions can be represented an inner product of a given feature. However, adversarial environments have not been considered in these settings.
Online Adversarial Linear MDP Online adversarial linear MDPs have been studied under full- information feedback (Zhong& & Zhang, 2023; Sherman et al., 2024; Cassel & Rosenberg. 2024) and bandit feedback (Neu & Olkhovskaya, 2021; Luo al., 2021; Dai et al., 2023; Sherman al., 2023; Kong et al., 2024; Liu et al., 2024). Specifically, in the full-information feedhack setting, Zhong & Zhang (2023) proposed a butti-batcche policy optimization algorithm, achieving ((33/4) regret bound. Sherman et al. (2024) achieved ((vK) regret bound, adopting warm-up phase obtain a simple expression for policies. In addition, Cassel & Rosenberg (2024) proposed a warm-up free policy optimization algorithm with improved regret bound. In the bandit feedback setting, Luo et al. (2021) introduced the notion of dilated bonus, and Liu et al. (2024) proposed two algorithms: one achieved Ō(v regret bound but was computationally inefficient, and the other achieved Ō(K3/4) and was computationally efficient.
E CONTRACTED MDP
In this section, we explain the notion of a contracted MDP (Cassel & Rosenberg, 2024), which is essential for deriving our main results. A contracted MDP is defined by the tuple M = (H, S, A. {P {4, 1 1 s1, Here, S A x [H] + [0, 1] specifies the level of con- traction. In particular, the loss function and transition kernel are defined as
a)) = p(s, a, (s, Pn(s' ss - p(s, a, h)P ss)))
Since a(s,a,h) [0, 1], it follows that E a) [0, 1]. meaning that the contraction preserves the boundedness of the original loss function. On the other hand, Er's Ps s,a) S 1, which implies that P defines a sub-probability measure. Although this does not satisfy the definition of a probability measure, it is sufficient for our purposes, as the contracted transition kernel only used in the amalysis. Furthermore, it is often called Sub because its transition kernel is sub-prod bubb-robability measure.
Accordingly, VT, (s; denotes the p-contracted value function with respect to a policy a and contracted MDP M. Given V (i:++((s:)) p) for all E S, V.T. (s: is defined recursively as ]
и Σ
VG, (s: = EE,r
(5(5,,,;))8 = s (a
(n(, EPn(s ss
e'ES
17

---

Published as a conference paper at ICLR 2026
We next introduce lemma that highlights key property of contracted MDPs, which states p- contracted value function is less than or equal to its original value function.
Lemma 7 (Lemma 2 of Cassel & Rosenberg (2024)). For any : S x A x [H] - 10, 11 IT, h [H] E S, and e A x [H] - [0, 1]. we have V p) S VE, (s).
Since PP is sub-probability, we note that Ex applied constant 0 could be less than itself. Although this is trivial, we state it formally below for completeness, as this relation is used frequently in our analysis.
Ep | = = S Lc 81 = =|== =c E
(5)
Proof of (5). First, we prove p, 1 hell ((s,a))81 = s] S R EnEMH] (1,8 a)ls s] for any 8 E S and { where la : S x A + Rt, using induction on h. For the base case, h H. Ep [& (SH, [s}[sH] = Er, leu (SH, aH)[sH] Bagaz((an) ( ax)). Assuming the statement is true for + 1, we have
Eppx
Σ (((8,,a))== =
= Ba
la (sh; +
Σ
Pa(s' 8h, Bp,
Σ s=
E)(3)
e'ES
H Σ
$ Ba (s)
en Cn(sn; + Σ
Pi(s's 8hh Bp,r
s'ES
j
" Σ
Ep,x
(y(s,, =
This completes the induction. Furthermore, by taking la (s, a) c/ H for all (s, a) E Ax [H] we have Enei (x a) = c, and thus [c|s]] s Ee, for any s E S. Since P is not contracted, we know that [g,:[c|s] This completes the proof.
The following lemma is an extension of well-known value difference lemma to incorporate con- tracted MDPs.
Lemma (Lemma of Shani et al. (2020) and Lemma 14 of Cassel & Rosenberg (2024)). Let π be two policies, and let M (H, (Pr) ( 81) be a (possibly sub) MDP. For all
h [H), let Qr. S x A R be an arbitrary function, and let Ve,(()) (Qr.1( ,) Fx (1)) for all a E S. Then,
H
(x1) Ves(s1) = Ee,5
Σ
| sn) - #n( (ossss)) 81
H
+ Ep,
Σ
(ah, an) + IP D... - De, (on, [1)
where Vž, is the value function of n, and IP, Ve, a) = Eves (n s, a) Ven+.
Since we assume that the initial state is fixed, we omit it when clear from the context for simplic- ity.
F PARAMETERIZATIONS AND FUNCTION CLASSES
In this section, we introduce the parameterizations of and न. Following this, we define the function classes which the value function estimates and policies belong.
18

---

Published as a conference paper at ICLR 2026
Parameterization
For the parameterization of Q given 3 E R, E R A Raxd define
Q1:3,,u W, A) as
(G, w, (o(:-) -loo-B - ol-Buell((: ))I Illa+log log K).
(6)
Next, we consider the parameterization of Let n E 2, denote the number of mixing steps.
For the parameterization of स, given n, (Bi, ui wi]]=oo A and mixing parameter (0, 1), we first generate policies (R. {= recursively, and define the final policy as ([|1:; {P,, ue; A))
Generate ū. #o(- s) Funit (1)s),
(- (s) i .,..., T.(- s) = -11 (1-0)TT(- (s 0T oTui
#++1( (- () x
exp ((s, Bi, wz, (s, A)) i = O,....n.
Define #(- [3,, w. w.))=o A) Fn+1(.
We keep the policy parameterization in its recursive form for the following reason. Although easily show that (-I-: {B,, w;
wi A) follows the weighted LSE softmax, i.e., E; Si exp(E; Q5), the weight parameters Si depend on {,B,, we 3= and A, which makes analyzing this form difficult. Thus, obtaining the closed form of (-1:: (3,, ws o A) is intractable, as specifying exact Çi is difficult.
Since 1. s) induces probability distribution over A for each s E S, (7) indeed defines valid policy. Furthermore, the following lemma shows that Q-function estimates and policies generated by Algorithm can be parameterized using (6), (7).
Lemma For any e E E, consider lo E Ke- For some n 2 0, let ke + nKB be the last index that the mixing is applied before episode k; i.e., max [(k (k-1- ke)/KB) Let
The 10',, f.c Lg 1k11 j=kk, be the policy and Q-function estimates generated by Algorithm 1, respec- rively. Let Sy be the index set defined as
=={(ke (kk i Ke + (i 1)K R_ like + nKB .................. - 11
for O...., for = n.
S -
k-1 A such that for j kee. k -- 1. Then there exists {w',n ynr w jj
p(,((,))=) Q(. Bo, w/ A), (g((())== = ((, wid
g.h A).
Furthermore, we have
= (3,, wi
for = O,..., and Y, is the where -a3 E Ejes, (1+ Yy),,, w; = -aa -aE (wf, + +Yzw for dual variable in episode j.
Proof. Note that for any j. by algorithm
Pp((:-)) ( (i D M Boll(: (1())))))))))))))))))) - Bullo(s (0lll((s log K).
Then we can take w/in pin + V MM++ and A ) Here, it is clear that (2K)-1) -
(A T. Also, we can apply the same argument to Ø 2g Then the first statement is proved.
Let us prove the second statement. By the definition of n, the mixing is not applied from episode ke nk* 1 to k 1. Then we have
# 8) x Th -ketnk+ (xp))exp (a E(@iaee))+
JES
Furthermore, since (k. + nk hic =0 mod KB we know that 7, tnk is mixed. Then we have
tkk 4A
(. (-1s)= -
tnk" (. (s) + 0 (118).
19

---

Published as a conference paper at ICLR 2026
Similarly, we can deduce क.. tnk (n (n-1)KB ke nk"
using the fact that the mixing is not applied from episode Kg +
nk- (.) x mh
(n- 1)K (x -a E
( +Yj
jESn-1
We repeatedly apply these steps until episode kg. Then we have for i 0, ....,, 1.
(-1s) (1 ( tikk (-1 OTunit(- 8),
( h
(.18)
the +ik 1
(-18)
Σ
SES;
Note that Tht = Tunif. Then we have मे = Antl. where #n+1 is recursively defined as
an(- 8) Tunir(: |8)
a s) = =1 (- + OTunir(: (s) Vi = .,...,
क (-1s) x ( exp
-a ((Tr, +Y, (.ngn((())))
Vi O,...,n.
jES.
Note that
(0) (s.
JES,
Σ
(w + +Y - B6(1 a))la) (1t.l:o..0llllltt-.Bloloooooooo0 K)
= a
jES;
(0(s, a) wi - Be 1a www-BBlllssc/llladd-llllllllll
log K)
= (s. 0; Bi, ws A)
where 3 = - 3 EeS,, (1 + Yj), w; = aa Ejes, (w) h + Yywg This completes the proof for the second statement.
Now, we define the function classes as follows. Given some boundedness con- stants CB, Cuu Cq 0,
Function Class
(CCg, Cw, Ca)
{ (,. w, 1815 Cg, |/ll|2 Car, 1244
CoJ.
Unlike 2, the class of policies has to defined based on number of mixing steps, since the formulation determined by this number. Let îī, denote the set of policies that involve exactly n mixing operations. Furthermore, we consider boundedness constant Cy to incorporate the scale of the dual variable. Given n E 2, and some boundedness constants Cj. Cw. Co. Cy 2 0.
ñ, (Ca. Cw. Co. Cr)
|8.15 (1 + Cy) ||w]|2
7(
(Be o A)
(1 A)lloo Cy) i O,....
Similar to IIn since V is defined by Q and म. we define the function class of V for each n.
Q @(Co, Cw. Co), a in KC KCq, Cn)
(r Cw, Cx) 0 V0:DC P()
Σ a(a (), asA
Note that if we apply the policy mixing every KB episodes, then the number of mixing steps is at most K1-B K2, where L == B. Thus, define (CC,, C.., Co, Cy), fi(C,, C.., Cr)
20

---

Published as a conference paper at ICLR 2026
as the unions over O..... K follows.
kt Cw: Cw. Cq. Cy) Cw, Co, Can
==
kt Cw: U
[Cg Cwv Cq. Cy).
a=0
G COVERING NUMBER
In this section, we show an upper bound on the covering number of (C Cw. Co. Cy), which is crucial to analyze linear CMDPs. As a first step, we show that any Q E i(Cs, Cw. CQ) is Lipschitz, i.e., the -nom between Q-function estimates is bounded by the f2-norm between their parameters. We closely follow the proof of Lemma 10 of Cassel & Rosenberg (2024).
Lemma 10 (Lipschitz Q). Let 1 I Ba:: Cwu Cp. For any Q,, wt, ,A ,,,,,( ,2²) E
ÕCCs, Cw. Cq), we have
188 w A Q(,,, :B² w (o,,A) I B max C3} ||(8), w² ,,,) (B2, w² ,A2)
where ((0)), ,,A) - (32, w² (e,,>>)l is defined in (9).
Proof. Consider
(0s a; 8¹ w ,A') - (s, a; 8², w,, .A))
s (2s o; 3 w A ((s, B², w , ((s, a; 82, w w,',')) ((,, a; ,2 R,u?,A
(1)
(m)
+ (s, a: f w² A (s, a: 83 wu.A3))
(m)
We bound each term individually. Note that (2K) 11 1-k) |K a) S 1 and (o)) < for any E R,
A 1 I. For (I), since ()
(I) | [|lllss.ellloo---BBllleelt/++-- K) < | 321.
For (II), by the
inequality.
(II) l0(s, aw - K)
(w
| w²112
For (III), by the triangle inequality.
(II) @(s, a; 8², w² AA) @ a;
a; ,², w A3)]
S (ss a) T
log K) - a (0(s, a) a)l log K)
+ B1 a) | a K)
+ 3
K) - a-BBullob6 a) a)) log K)]-
Note that the sigmoid function is 1-Lipschitz on R. and the triangle inequality implies that IIlØ(s, - a)llxa < II(A)) 1/112/ Then we can deduce that
(s, a; 32, ( - ((,, a; 3
Bw. - + Call(A))
(12)""111++_88811))))11 -
< max Cp, C3
Ca (|( (A2)2/2112
1
3 ma Cg C3
JAA - A
2/1)(22)
(3/V2)VK3) K3 max Ca) |A' -A2
21

---

Published as a conference paper at ICLR 2026
where the third inequality is due to Lemma 32, and the last inequality is because we assumed that 3w 2 1. Note that we know ||A| - 12 ||A
-A2 where ||-I| denotes the Frobenius norm.
Finally, we show that for any (s, E S x A,
(Qss, a; 8¹, w", , - a; w² A²)
1 - -
max Co -A211
S / 33 w|3
3 max (C Co))21A11 - - S Kr [ax Cs} ((3), wn , - (3² w² 1
where the second inequality follows from the Cauchy-Schward inequality, and the last inequal- ity is due to 1 < (3/v2)
(8/v2)KK3 KK3, max(Cu. Cgl, as we assumed that 1 I Sw Cws Cg. Here,
(1 w" A') (8², 2 AA) denotes
||(B), wn, A² (82 u2 .A)
-B9-+++ w² 111 - A F.
(9)
Now, we have show that the policy parameterization given in (7) satisfies a Lipschitz property, i.e. l f--orrm between any two policies is bounded by the fn-norm between their parameters.
Lemma 11 (Lipschitz 7). Let S B Cw CB and I Cy. Suppose that two policies #1 E [n, Cw. Co. Cr) are parameterized by {8), wt Pio, A² and { wf A re- spectively. Then the following holds for any E S.
|| (-10)= 2 8)]1
(8A1) "
n
S 322 + 1)K + Cy) (a C3}
[(3)) wt A1) (5,, u²? AB)
Proof. & S. Let (#), ). (7) 22 a1+1
Ji-n be the sequences of policies recursively generated
by (7) to define #l 2², respectively. Then it follows that
#1( 8) = # 8) x 7t( 8) (xp Bh, wh, A A²)), #- s) = # 8) x C. 8) (s, Rh w A 2²))
Note that (a | s). (a 5) > for all E A, since they are perturbed. Then we can define
log (a 8), log 7 (a s). and it leads
+ () x exp [lo ( s) Q ; :1 wh A')) 2 (: 8) x exp (log |. 5) Q (s. : 3h wā A3))
(10)
By Lemma 24,
| ( 5) 22 x |s)l
<
8 log m 8) + Q(s, : 3/ wi A llog मे () Q(s. Sh. wā A2)
< log { (- 8) - log b5( 1) + = - 3/h why 2 (0, ;; 82 w. 13)
Note that (a s), o (a 8) > 0/|A| for all A due to the definition. Then utilize the Lipschitzness of log function in [0/|A|, oa) |7| Thus, by Lemma 21,
IA
|log ( (-1 8) - log (- |)
<
8) - 2 ( s)]l1 |
0
A
(1 0)| (11s) () - I-)+
(II)
0
A
| 18) (1111s))
0
22

---

Published as a conference paper at ICLR 2026
where the equality is due to [. 5) (1-0) s) u-ii |s) and (- (1) = (1 (1-10) (.
s) + umui s). Plugging (11) into (10), we have a recursive relation, and it leads to
| ++++ (- s) x (- s)]l
8 ||
|| (- -) (- r)|ا +8 [[(s Pn A (s,, u A3)
0
8 8|LA|
|| (- (-1 s (-
0
8 Σ ( ((LAA) ) 1165,
A') - - -
1=0
8 8|AA|
n+1
| |s) --6 [s)]]
0
(|A1) ) |005, 10 wh A2) - (18,,188... w A2)
1=0
n
8|A1) ) [Q(s. P2 -n At) (; : Ph
8
Σ
w _ A2)
where the equality is due to Schwarz inequality.
C. |) R-( 8) = (. | s). Furthermore, by the Cauchy-
|| ||
(. 8)
. 8)11
8|,41 8
(ss.:1 w! u33
1=0
2=
8|.A]
2n
<8
(n 1)
Σ 1=0
1(s, : A1) :8,
0
Note that (s wi,
, A),, (ss ;8, w, A?) e @(( @([ Cy)+ (1 Cly)))
Cy)Co).
By the Lipschitzness of Q (Lemma 10),
|| (. (1)) 7- (- |s]ll
2n
4V + Cr) max Co3)² [1(3), A1) - (88,
s 8/ (n (n+1) 1)
(8|A| "
-32 + (1 Bw (1 + Cr) max maxxCuus Cs}
Σ [13) A1) (82, w3,,w,,3))11 A2)
as desired.
Based on the Lipschitz properties that we have shown, we show Lipschitz property of V, and it leads to an upper bound on the covering number of V,, (Cp, Cwn Co, Cy).
Lemma 12.
Let 1 < Bm. C3. C.,, Co and 0 I Cy. Given e > O, let N. N..VV. Cw. Cq. Cv)) denote the e-covering number of Vn Ow, Co, Cr) with respect to the loo norm. Then we have log 1o,,N.(..CC,, Cu,, Co, Cv < 3(n + 2)² log((8))A1())) + 22/Ce))))
where
C 91 (n + 1)K3 Br max C2) Cr); C2 = (n + 21 CC)) +Cw) (n+ 2
(12)
23

---

Published as a conference paper at ICLR 2026
Proof. Recall that V E Pn Cw. Co. Cr) can be expressed V1()) =cGed 7(a ((((aa), where Q E i(Cp, Cw. CQ), & E (KC,, KCw, KC2, Cy). Then consider 11, 122 E Cr,C Cwv Co, Cr) such that (.)
Eoen (a -)2" and v2 EBEA A9(a
(A)).. Suppose that each of those are parameterized as follows.
म¹ = = (0 .w; w. 1 Jizo: AT.I) E (n(K3, KC2, Cr),
3 2² #(11: (8TT2 w 1i=0 AT.2 E (KC,, KC KC Cy);
Q' = Q(33891 89. w E ((C Can Co),
@² 06,3388 w 02 10:2 E 2(C2,, Can Cq)-
Then for any 8 S.
(s) - (s)
Σ (a 8)
Σ
(a (s) (s,,a)
aEd
Σ (a (s) Σ (a 8) 77 (0)
Σ x (a 8) (s)
E aa 8) (s,
+
aEA
aEA
aEA
aEd
| (118))111111 |)
6)
7- (1)s)1111** (s. )1b
= 1I@ (s.-) @2 (s. 117 ()
7 $) (s) ||
where the first inequality is due to the triangle inequality, and the second inequality is due to Hölder's inequality. By Lemma 10,
(1, ) - - = 4v KB, max C3} [1(3911, 0. .A911 - (39.2 22 19.) lg.
Furthermore, for the second term,
| (- 8) - (- () I Cq (- ((ss) 1 (-1- (-(1))
< CQ 32 (n + 1)K3 (1 Cy) max KCW, (8]A1)
II .uf. AT.2) (87 w. 22 )
where the first inequality due to |0 Co for any @ @(CB, Cwn Co), and the second incquality is due to Lemma 11. Then we deduce that
max (((s) - (())
#ES
I 4VK3, maxx(Cur C3} (S 0.1 1A111 - -6892 2.2 AA92)11
+ (1 Cz} [8/4|
(3 _. T.1 A - (87 , u AA22)13
$ V (4VK3, Ca) + 1)K3 + Cy) max Cw. C=](8LA1/8)))
[[89,1, w w00.,,,we.1,coom AQ.1) (80.2,8300,0000 0222 19.2)11 + > [(37 _up ,A.1) (8772 w. n. A
< 333 (n 1)K33, Cy) max Cw,, C2 (|AA| 1
n
(1891,w991 ( (39.2, 02. + Σ [1 ... (AA1) - -88T 2
x
24

---

Published as a conference paper at ICLR 2026
where the second inequality is due to the Cauchy-Schree -chwwaz inequality, and the last inequality is due to the assumption that S Cq and & E (0,1).
Note that
||58:11 8.2 ,A 115 w A oolll $ ||10
Σ (1 (12
S CB + C + vd (n + 1)(1 + Cy) + Cw) + +n
$ (n+ 2) + Cy) C() + Cw) + (n + 2)vd.
Note that (38.1, w..1, AQ.1, (..50) w; 1 can be viewed as a (n 2) + + d²)-
dimensional vector. Since + d d S 3d by Lemma 27,
Iog.N.(P Cw. Co Cy)) 3(n 2)d log (1 2(844//0))C
where
C = 33 + 1)K3) + Cv) max Cs}:
C2 (n + 2) + Cr) + Cie) (n +2)vd.
Furthermore, the log term contains exponential term in n, we further deduce as follows.
log (1 + [1+2 & n log((8)A1/0) + log(1 + CC/C2/e)
S (n + ((0+))))((((///00011+22202
Finally, we have
log, (Vg,N((P Cw. Cq. Cy)) < 3(n + 2) 1o(($84//0011333CC;/)))
Finally, we show an upper bound on the covering number of (C Car, Co. Cv).
Lemma 13. Let 1 Bw: Op, Cwe Cq and 0 Cy. Given > O. let N.VV Own Co Cv)) denote the e-covering number of V(C,, Cw,, Co2 Cv) with respect to the norm where kL (C Cw, Cw, Cr) = U (C Cwe Cq. Cy). Then we have
log lo Cw,, Co, Cr)) S 3(K² + 2) log (K+ (1++1)-0 +1)8141 (1+ 20102)
8|A1
where C1, C2 are defined in (12) with n = KL.
0, K4, let Cn S (n Own Cq,Cr) be an e-cover of V., (Cp, Cwn Co. Cr) with respect to the lo norm. By Lemma 12, suppose that the covers satisfy log|C,|s 3(n + d log((8) AI/0)( + 2C/C2/e)
Proof. For each
Vn 0, O...., KL
where C1, C2 are defined in (12) with = KL. Furthermore, let
C en.
==0
Then claim that C is e-cover of (C Ow, Co, Cr). For any VC Cw, Co. Cy), since DCC, Ow. Co. Cy) ) is defined as the union, there exists m E (O...., [.....,)) such that
V E (m Cw. Co. Cy).
Since Cm is an e-cover of Dm, (Co, Cw, Co, Cy), there exists Vi E C. C C such that
|I 5m
25

---

Published as a conference paper at ICLR 2026
This implies that C' is an e-cover of (CC,, Cw Cq. Cy) with respect to the norm. Furthermore, we have
k
3(K"+2)2''
cal s (K* +1) (1) (1+ 20102)
[8/A]
Cu.
c
Σ 7=0
3(Kx +2)=
(K+ 1) 8| (1+ 201C2)
where the second inequality is true because S nd for any 2, 1. Finally, by taking log on both sides, we have
81A log.N. Cw, Cr) 3(K+ + of log (k+ + 1) 0
(1 20102))
as desired.
H GOOD EVENT
In this section, we introduce a high probability good event, denoted by Eg. which simplifies our analysis. We begin by presenting the formal definition of Eg. We define Eg as
Eg = E1 n E2 n Es.
(13)
E1, Eg, Es are defined as
E (v) E [K]
x H 100 0Z 1llll Br, 11 - 1gllllng S 8.)
(14)
F2 (VK,,,, E [K] H x (. 11(// - -0) Sp, 12 Bq. Y. S
11
K
(15)
6K
Es
Σ KE[K]
Ep [Wa] 2 Σ
W, + 413333 + (B233) log 8
(16)
KE(K
where
8. 2 2d log(66K//5)
P 50 1/4 + 1)dH (oog(5H2222//10))
3Q 2H,
P. 3, + Bpp
BN = 4,3, log K,
W₂ = Σ
a +
(33ol1(s
10s2 o (1
NE[H]
We note that one of the key differences from Cassel & Rosenberg (2024) is that Eg involves an upper bound of Yg. This is because (possibly polynomial in d, H, K) upper bound of Ye is required to prove that Eg holds with high probability. In contrast, since we do not truncate Q% its trivial upper bound cannot be obtained. Thus, avoid circular logic, we include it in Eg, and use induction to show (Step 3-2 of Lemma 16).
However, since directly proving Eg holds with high probability is difficult, we instead consider proxy good event and then show that implies Eg. Here, we define the proxy good event E,
Eg = E1 n Ea Es.
(17)
where Eg is defined as
Eg A, V) E [K] X [M] x V(s, 2K Bo, 11gHH*)) [1( - }
Based on the upper bound of the covering number of (C C.,, Co. Cr), we prove that E, holds with high probability.
26

---

Published as a conference paper at ICLR 2026
Lemma 14 (Proxy Good Event, Eg). Let Bw I K, and let n, 1. Then Pr(Eg) 6 for any (0,1)
Proof. We prove the statement by showing Pr[Ei] 2 1 - 5/3. Pr[E2] 2 1- 5/3, and Pr[Es] 2 8/3. For E1, by Lemma 30, we have for all [H] with probability at least 6/3.
10g, g.h I.llll 2d : B..
Furthermore, it is clear that 100,, - 0)lll = I Br because we take 87,1 = 8%,1- Then for any h, k, E (S.g), En holds with probability at least - 6/3.
Now consider Eg. By Lemma 31, for all V (,,,,, 2K 3Q. I K), with probability at least 1 5533.
11(1% - VIlA 48q, dlog( K + +) 2log(3H2/8) + 2lo. (V 2K Sq. 11n
(18)
The parameters in Algorithm I satisfy S 3b. 2K,2KKQQq. BQ. Then Lemma 13 can be applied to deduce the covering number. follows that
lo (V(3,, 2K 3o, (1nH²K)) < 3(K= + 2) (Kt + 8|A| (1
20102)
Since assume 1 < Bu K, 3o < 2H, 11a S and KL < K, have the following bounds on C1 C2 with KL.
Ci = 33 (KL + 11)33
+ 11yH*K)
< 4481H $K K
C2 (K" + 2) + ())3 (K- + +2
< 242v "
By Lemma 31, we can take v2/(2K), and thus the covering number is bounded as log (V 2K 8Q. 1 Applying this to (18), since
2 K)) 36(K* + d (og(HHK\A|/0),
K-1
[1 VIl I 811 / dlog(K 1) 2log(3112/)) + 2) (og5 s 50(K" ||HH
3p.
Thus, showed that Pr[Ea] holds.
holds. For Ea, note that for any (s, a) S A.
Σ
(3)10(s. 1o(s l H (33, 83)
AE(M]
Furthermore, * a are generated under P, * Then, by Lemma 29 with probability at least 1 18/3.
6K
Ep. | 2
Σ
W₂ - 4H333, + 8,3 log
5
KE[K
kE[K]
Consequently, by union bound, we have Pr[Eg] 2 1-8.
Before proving that Eg holds with high probability, show the following lemma, which is modification of Lemma 12 of Cassel & Rosenberg (2024) to our CMDP setting. This lemma plays crucial role in establishing the connection between F.g and F.g.
27

---

Published as a conference paper at ICLR 2026
Lemma 15. Suppose that Ey holds. Given & E [K], if i [i(K3, 2K2 (q. K K9q. 11 K)
for all E [H) then 2% Qb E 1(3, 3K 9Q.h), and VE Vk Lho g.
(S,, 2K BK, BQ. K1mH1*) for all h e +1.
Proof. To show the statement, we apply induction on h for fixed k. For the base case, consider Vř f V V 1 = 0
h = H + 1. As we initialize as Q (f, a) = 12, for all (8,a). it is clear that Q H1 29. E 2(3, 2K BQ: (Q.1++) and V/ Vk 9.8+1 E ((,, 2K 9Q, K)) Next, we assume that the statement is true for h + 1, i.e.,
Of, Q4,,41 29 1 2K30, (Q, Vftt2 V ghtt1 E VBe, 2K3q, SQ 11nH K). It
follows that for any E (J,9).
(2,(6, - T (s,
(0th + + ViVEttt) - Bo | (s, (3,a))(ax3))
hh ke (s,a) (otn + + V((n+1))
66 + 100:h 022 aa.. + +1|000 (/a - WWn) 1ate @0% (s, (3, lus
Ah ke (s,a) T (0th + 1/a V2intt)
Bb + |0 - -Ei + 110A wha VW l1,s) 10% (s, 1lat
where the first inequality is due to the triangle incquality and the Cauchy-Schwand inequality, and the second inequality is due to the fact that A A
We bound each term individually. For the first term, for all E E (1,g).
The a) (0hn + sh V2 (2++1) (-BullÓ(s,)) (a log k) (6(3,o) T + tn (2htt)) S (s) (os.a)(((8 (0t + vha V.t Wintttt)
a)) + EPn( ss ( (5))
d'ES
where the first and second equality are due to the definition of Jhe and linear MDPs, respectively. Next, we can bound the second term, since the proxy good event Ey is assumed.
(00 ( + 0h 02.01 + (
Vn
4nn Ven+
lktt)
bo (s,a) a))
(Bs + Br + 3p) (0%%% ( (ayg (Bs
(
Ax
Recall that 11 (s, a)) - I| a) ( -u 10( (esss,)))ll -1 log K) S maxy20 y a--Brot + log K). It follows that
s 1 + 11 al ((6 + 3r + 3,) o (s, (s, (ate)-1
< 1 + 11 c bo + (B0 + 3r + 3p) max (v (- + log K)]
420
1 1 + [V + 2log K
(3, + 8p 3b)
Bu
= 2 + 11
< 2 + $Q,
BQ.h
where the third inequality follows from Lemma 28, the equality is due to Brn = 2(3, + B, + 96) log K, and the last inequality holds because of the induction hypothesis.
28

---

Published as a conference paper at ICLR 2026
So far, we have shown that 1o BQ. To show Qi, @( 2K (Q.)). show that the corresponding parameters are upper bounded. Recall that 24, h is defined as
) it remains to
(s, 2h (s) (e,aaTTfr wwe Bb 11% (s, (3. leN
where w²,n = 0i + 0/ E,++1- Note that
V.
10 11.1
(A
((sh (S an)
$ (AA))
Σ rE|K-11
( (5) 07)
S K.
Furthermore, the induction hypothesis implies that
Th V ph
c ch++1
1/=
(A/)-1 (a/))*
Σ
SBQN+iK.
TE(K-1]
follows that
| 1125 110 11
V.
2 ||3 s 23
Furthermore, we have (2K)-11= 3 ) 31. Thus, have
Qh E (1%, 90, (Q.1))
By definition, since we have V2 (s) = Eeca (a 8) s) and the assumption #
fi(K 9, 2K² KB H K), it follows that
V E VB,, 2K 8Q, 1lnH*))
This completes the proof.
Finally, we prove that E, holds with high probability. The proof closely follows Lemma 6 of Cassel & Rosenberg (2024), with modifications for the CMDP setting.
Lemma 16 (Restatement of Lemma 1). Let 1 B K, let n S and 4om11 < 1. Then Pr[Eg] 2 1 - 8 for any E 1).
Proof. We assume Eg. which holds with probability at least 1 - 8 by Lemma 14. Next, under Eg. we focus on showing Fzz. As first step, we show that Tे E TTK,,, 2K K K3q,n; 11 K) and Ya E [0, 11n/f*k] for all k; h using induction on & E Ke for each epoch e E E. Finally, based on this induction, we prove that Ey holds.
Step 1: Base Case First, let us fix e E E. For the base case, consider À = kic. Since #/ Munif for all h, it follows that # [i(KB, 2K2 K 1 K), as Tunif can be viewed as (a s; 0, 0, 1) with O. Furthermore, initialize Yk. = 0. Thus, the base case holds.
Step 2:
Induction Hypothesis For k E Ke, we assume that a e Īī(K 3,, 2K2 BQ k)) and Yu E [0,ll for all and Ke < k < k. Then, by Lemma 15, it follows that for all (h, K', [H] x (Ke....,k x-11 x ff.gh
Q E 2(3, 2K 2KB BQ.)).
DK E ((8,, 2K3 SQ 11nH*K).
(19)
Furthermore, let Bo, w A denote the parameters that specify Q i.e. for all h K (f.9). Q.a())) Q(:;; Bb, w wh A).
k. f
29

---

Published as a conference paper at ICLR 2026
Step 3-1: Induction Step (T)) Next, show that t. E TI(K3. 2K 22232. K BQ
11nHaK)) K) for
all h. By Lemma 9,
- f/,,, w/ Pi A)
where Wi = -a E Jes, (w + Yyungh h.)), B, = 3 Ejes, (1 + Yy). Note that j E St satisfies
j < k for each i, thus we can use (19) to bound the parameters. For wi.
|10 l|
Σ
Ilury,1
Vjug.tll
JES.
<
Σ
11,2 ll
JES;
(20)
Σ
(1 + 11m K22K
JES;
$ (1 K12
where the first inequality is due to |a|s 1. and the third inequality is due to the induction hypothesis (Yw < 1lnlf for all K' k) and that (19) implies 1 2K Bq. Similarly,
1 (1 + 11m11 K)K3.
(21)
Again, by (19), have 11 a1.0 BQ. Then, for any (s, E x A and O,...,m,
a ( (10)alts,))xx(((00 S (1+ 11m K)kllK
(22)
JES,
Note that n = max [(k - ke)/KB < |K/K]] < K1-B K4. Furthermore, its parameters are bounded by (20), (21), and (22), and the same argument can be applied for all h e [H]. Thus, for all E [H].
Πi(K So 2k² KBQm, 11nl1
Step 3-2: Induction Step (Ya) To bound Ys.
Y4 (1 - (amH)))yaa + 17
p 9.1 (s1) - b - -4 40H²)
+
$ (1 H + 17
( (81) b 4o H 40H²
$ (1 40m Y2-1 +1) p (s1) - -b 4o. 40H²
$ Y p (s1) - b H - -
111Hf 1) 11nH
11nH3*
where the first inequality due to the fact that max 2} < |2| for all E I, the second and third inequality follows from the triangle inequality and 0 < Hom < 1, and the fourth inequality due the induction hypothesis, i.e., Yv < 1lmH'K and 1 11 2H for all k < k.
These complete the induction, i.e., #े îN(K 8r, 2K3Bq. KBQaa 11nH1*K and Ys [0, 11mH*)]] for all (h, k) E [H] x Ke. Furthermore, we can apply the same argument for all e E E. Thus, holds for all (h, k)) E [H] x [K].
Step 4: Showing Eg By Lemma 15, we have for all h, k.
Si Qi E (33, 2K3q, BQ,N) VAAn D.t E V( 2K Bq, SQ 11nH K).
As result, since Eg is assumed, we have (1 - T2 e aly S 3p- Thus, Eg holds, Furthermore, Fi, Eg hold by F.y. This completes the proof.
30

---

Published as a conference paper at ICLR 2026
I LYAPUNOV DRIFT ANALYSIS
In this section, we upper bound the dual variable based Lyapunov drift analysis. As a first step, we bound the Lyapunov drift (Y //2
Lemma 17. Assume that the good event Eg holds. For all E E and l., k + Ke. the Lyapunov drift is bounded as
Y2 1+1
7 S -777
Σ
D(
(-1sh)
2
a
ME(H]
+ m2aHH + 4H²0
16a2 193 + 160 H²).
Proof. Recall that the dual variable follows Y&+1 = [(1 -am n(Vg, - - 4a 20H²)] It can be rewritten
Y YE + 17 (DR (1 - 40xH + Y&) - 40H2)
Note that max(0, 2}² & x² for any E R. Then, we square both sides, we have
k++ Y 2Ymm (Vr1((0) 4aH4 V2) -0113) 1²² (1)) (81) - -40HH3 VE) -40H² 2
It can be rewritten as
Y2 E+1 Y
2
S Yun (De (81)
4aHH311 Yx) - 40H2)
1/2
( 9.1
(81) - 41 + Yv) - 40H? 2
2
(23)
(II) can be bounded as follows.
7
(I s
4((
9.
b)² (4all3)² + (2) (40H2)2)
2
< 499112 + H + 16a H H²
2
n2
< 2
4(9H² + 16a Hd 1936 H2 160 H
where the first inequality follows from the Cauchy-Schward inequality, the second and third inequal- ities follow from that F. implies | (s1)ss 2H and 0 < Y, < 11y for all k.
Next, we bound (I). To obtain negative drift, first deduce bound Yı *t11 satisfies
k ( (-19%)
()))))n), (sn, )). Since we assumed k; k + E Kas m *k+1 + Tunif. Then Th
* (+1s)= arg min (n, Qi + Y2Qu + 1 D( ((-1))EA(A)
Applying Lemma 23 and letting u we have for any E S,
(+ (-1sh), (-1sh). (sm. YaQu (shr
1
D( ((1m)))((((s>)))
a
< <( (/ (sh.) + Ya Y2 (sk, )) + - (+ (-1sm)))))))
(( (-1sw)
31

---

Published as a conference paper at ICLR 2026
where स is the Slater policy satisfying ((1(s)) $ b for some 0. Next, summing over h and rearranging terms yield
Y
Σ
(-Isn)
(-1sa) (g,h(on:)))
he[H]
Σ
D( ((FA((1o))
Σ
((TT(-18a)1155 (111
0 he(M]
a
he(m
(24)
+
Σ (#)(s))))= - (-19g) (..n(sn.))
Σ
D( (-|sn) (-1ss)
he[m]
(-n(-)))) - (+1sn): (.,n + Yk
(mn((18h) - (-1on) (gn(
kE(m
NE(M
Now, we take Ex which is taken over (s under Ph: for fixed $1. Note that since P a transition kernel a contracted MDP, it could be E. Tpk (s'1s, a) S 1. However, taking Eps. be viewed as linear combination, where its coefficients is in the form of sub-probe sub-probability measure defined as Pr[si 8,. = =s 81, Toke #] E [0, 1]. This implies that taking Ept., guarantees monotonicity, i.e..
Σ NE|HY
(-1s))))))) (-18a) - (11sh) Dr (8h.
< EEpre it
Σ D(Tx(-1s)) ((TA(1s))) ((*x(11sH)) [ ((1ss)
ME(H]
Σ (#))))))) - -an))-=(t+(( (+(ss) Qt., (sns 1 D s (1
+ Epke, *
a
AE(M]
(25)
aM
+ E E
Σ (Ta()1sh)) - (-(ss))), (sh,
NE(H]
+ Y ERke
Σ
- #h(ss))), (sh.
hE(H]
We bound (III). By the third statement of Lemma 22, for any 8n E S, we have
(-|sn)) (-1ss-)) + h (-1sx). Q7 (sh. -) D
s 2al2 + 4HO.
Thus, summing over h E [H] and taking Ez x we have
(III) E E [2aH1 + 4H²0 < 2aH3 + 4H20
where the second inequality is due to (5). To bound (IV),
(IV) Ept., .
Σ
Il loo
hE[H]
< Epr,, a
14H2
< 4H²
where the first inequality is due to Hölder's inequality, and the last inequality is due to (5).
32

---

Published as a conference paper at ICLR 2026
To bound (V), observe the following. Let V ( denote the p-contracted value function, where a h) o Bullo(s, I log K). By Lemmas 7 and 8, we have
9,1 (81) V (s1) 2 Vo,1 (. (81) ( (81)
(s1)
(ān(- sh) - ( sh), 2g.
(ss))) shi)
hE(H]
+ Esae 5
Σ he(m
[nh an) + Σ
Ph (s' sh. an) Vir - Oggnlon
s'ES
To bound the latter term, we have for any (sh, ap) 8 x A.
Ih (Sh, an) +
' Pa(s' 8h: (h,aa)) Voh+i Qt 1s
3'E8
5he (sh: Tn)T.g, + oh (on, an) th DA g.++1 - Tbt (sh, an) ( + T. e. + Bol (sh. an an)llate
-000 n 0g piilll x/ 110% (sh, an an)alaa -1lihh -b%) V/. g. llage 1108% (onr an W Boll0% ( (aaas
110g 22 1g1107 10 (sh. - - T g. ll ag 10 (sh an +
50610%% (sh. an an)ll
1ol (sn, an 1 - 1111%% (sn, an) a (sh, an) an)l
where the first equality is due to the definition of contracted MDP, the first inequality due to the Cauchy-Schwarz inequality, the second inequality is due A AA the third inequality due to Eg. and the last equality is due to 3h = 3, + 3p- This implies that the latter term is nonnegative, as Epae [0] O. Thus, it follows that
(V) YulEare,
(mn(-189) - sp), 22 (-1 sn))
NE(H]
< (V
g.1 (s:))
< Yb 7 7 -itt(s1))
where the last inequality is due to the Slater condition and Yg 2 0. Finally, plugging the bounds on (III,,IV), and (V) into (25), we have
Y1 Epec,
Σ he(m
(
+ (-18n) - (h(ss))). Q% (sn.
< - Eprr *
Σ ((Fa((lon)) - (107a( (-1sn))
kE[Z]
+ 2 + 44H2 4H² + Ye(b 7 - VR (s1)).
33

---

Published as a conference paper at ICLR 2026
Then can bound (I) as follows.
(I Yun
1 9.1 (81) 41H + (1) - 40H²)
1 (-1st) - (+(sss) P (gn 1)
$ Yon
F (51) -b+ b+Epue i
Σ hE[H]
$ Von(V - -6) + 77 Bpre,
(-1sn))
a
hE(H]
+ + + + A + -
- -
-
" Bgg,, #
((( (+1ss)
ME(M]
+ (2a2H + 4 + 2
Here, the first incquality true as follows. For any $1...., SH E S.
Σ A (+( (-)6)) (g,n(sn)
S
c++1 (+ (-1sa) (o.n
hE(m)
he(m)
$ (4aH2 + Yv. + 48H)
b
4aH (1 + Y2) + 40H²
where the first inequality due the triangle inequality, and the second inequality is due to the second statement of Lemma 22. Note that the second inequality holds regardless of whether मे. is perturbed, because when Tे is not perturbed, it can be viewed as f = O. It follows that
Epte, .
Σ AC(M
( (-Iss), :)
2 E |4a Yv) + 40H2
2 - (4 Yx) + 40H2)
where the second inequality is due to (5).
Consequently, plugging the bounds on (I) and (II) into (23), the Lyapunov drift is bounded as
Y2 1++1
Y < n777
Epte, a
7
Σ
(15x (-1sh) D (+1s:) (+sxs)
2
NE[H]
1936a 12 + 160 H + m2aH' + 4H20 4H²) 2 16a"
11
Lemma 18 (Restatement Lemma 2). Assume that the good event Eg holds. Let H² < K. For any 8 (0,1) and k [K], with probability least - 6, we have
2C4 BK
BKB m log
3282 (17))8
Ys
+2K
8max
"
where 8max and C2 are given in (26) and (32), respectively. choice of Algorithm 1, we have
Furthermore, under the parameter
Y, Ō(H2
Proof. For ease of notation, let N, = maxin E Z, kr + nk E K.). and
7m Y Yk.
34

---

Published as a conference paper at ICLR 2026
To show the lemma, apply Lemma 25 to (Zn)n Let Eo 0, and let be the set of all random variables until episode ke + mk 1, i.e.,
5n = {( a/. f. 9h of) (ee rellM
Let Fn, denote the o-algebra generated by &n for ....., N₂. Then (Fn Fy forms a filtration.
Note that Zo = Yk. = and thus Zo is Fomeeauurabl.. Furthermore, Zn tnkk is determined by information up to episode ke + nKB B - I, which implies that Zn -eaasuruable.. Hence, {Zn N.V adapted [
z2| for any 21 E R and E R4. Then it follows that Note that [m1, 0} 22 |-
|x+1 - Val - - Ho + n g.1 (81) 4oH4 40H12)
(1 K) + 3nH + 4naH 4
(26)
6max.
where the second inequality is due to the triangle inequality and the fact that Ys s 11gH and |i 1 2H under Eg. Thus, by the triangle inequality,
Re (n+
Zn+1 Zu|=
Σ
(Y+11- Y7)
<K" 8max.
(27)
T=ketnk
By Lemma 17, we deduce the Lyapunov drift of Z, as
ket (m++11))
72
72
V-2
Y
n+
Σ
2
2
#=k tnkB
k (n++))1)=_1
Σ
T=ke
ho (x++1))
Exne,
(1sn) ((=)(( (.(sx))
takB
BBCa
(28)
where
C. n= + 4 4H²) 2n (9H
16a H
1936a
22 R 160 H*) (29)
35

---

Published as a conference paper at ICLR 2026
To bound (I),
Ret (n+1)K==-
(I)
Σ
-,
rkkttkk"
(n+(++))x=11
Σ
Yke Yk.-nk*+ +
Σ
117
T=ketnkB
t'kketnka
bnt(++1jk==1
S 5 kk yYrKKKkkkk +,y
Σ
Σ
y - -Gr
Tek
r'=ketnk
(30)
S S kotnK m
Σ
Σ
6max
-i= -'= tnk
(c+(n+))
-r
BY ke tnkB + mn
Σ
(T- ke nk B)0max
B
KB KBKKBL -1)
- K By kotn + 07
where the second inequality due the fact that = S |z| for any = R and the triangle inequality, the second incquality follows from (26), and the last equality is because the sum of O...., equals z(z 1)/2 for any Z+.
To bound (II),
Re (n+(n+1)==11 Σ T=ketnkB
(II)
Epsc,#
((Ta((ba))1 - D( (-1sn) (1 (-1on)
bE[H]
D(F((18a)) I (-18)) (118))) D(F +0+1)) (-1sx))
Epsr,# ,
bE[l]
(o+()+))K=
+ "
Σ
D(TA(1s))1 - (n
hE[H]
Σ bE|l]
Epsc,a .
[((t(1s6))1 (-1sw) - D( +0+ (1ss))
E Ep [log(IAA/0) bE[H]
H log(1AA//))
where the last equality because मे. R% for all such that - -- $ O mod KB by algorithm. The first inequality because the KL divergence is nonnegative, and we apply Lemma 26, as we know Th tnk = (1 f) + 0Tuiif by algorithm. The last inequality is due to (5). Thus, plugging the bounds on (I) and (II) into (28),
Z2 2 ZZ
K BB(KB -1) + a
S ~ + pypmmax
" h log((A)/0) + KBC
(31)
2
2
For case of notation, let C₁ denote
KB BB(KB- -1
C= : mymmax
(A/00) + KBCs " H Hog((AA/0)
(32)
2
Consider Zn 2 20/ (nk B7). Then (31) becomes
72 .+
72
< -Csi
36

---

Published as a conference paper at ICLR 2026
which implies that Zn+1 Zn In this case, it follows that
Lut+ 2 Zn+1 + Zn
Lutt 22
E Zn+
Fx, = I2
F
E
[F,,
2Zn
Z
Z
E
FF
Z
1
E
1-1yKB 7. C(
Zn
- + +C+
Zn
CankB
S Bn1KB B/+
2C4
nk*
2
where the first inequality is due Zn+1 Zno the second inequality is due (31), and the last The first and second equalities are because
incquality is because we consider Z, 2 Zn is F.-eeasurabl.. As a result, we have
12n+1 2n15 K 8max.
2C4
K R5 6max
if Zn 5
1
B BiZn+1 Zn|Fnls
2k
if Zn 2 KK By
2Cs
Note that Zo = and JK JK.
I K max Thus, by Lemma 25 with no = 1, with probability at least
2
1 6, for all 0,.............. ......1 N₂
2Ca
+ RB8 + 4K2B max log yk 4
8K2B 52
Vketnkn = 7n <
max
BKBa
nn 51 )20
Furthermore, for any & E (ke + nK
,.K.,...,k.. lie + (n + 1)K 1). we have Y2 S Yk--nK +
kk=1 tr=k [Y+1 YrIS Vk.nnkn KB Fmax- Finally, implies that for any A [K].
2C4
8K max log
3262
Y& < R By
+ BK 8 +
max
(17))2
This completes the first statement. Next, we carefully plug our parameter choice into the upper bound on Yg. Recall that the definitions of C3, C4, Smax, and our parameter choice such that
3 17 H K a -==--1 B 000 1-
B
4
8mxx is bounded as
6max = (1 (1 K) + 3n + H + 4n0H²
4A7 K + 31 + 4nall + 4n0
-4HK 3B+1 - + 4K 2B + 4k -1-
=ō - 5/4 1 3/4
1/2 < 1. Then have Since assumed 112 K, it follows that -K
8max = o K (K43
C3 is bounded as
16x C3 4 16 7
1936 K2 1602
2B + 41-1 - -88
32K + 3872H 2-66B
+32K
37

---

Published as a conference paper at ICLR 2026
(C,/mnk*7) is bounded
2C4 BK
S 6mank 2H log(1A 2C'
K Kyya +
TTY
-B++ + +H3 1 + 4K- + 4K-1
2 112 log((A[k)
+
7
+ 12H2K-*
+ +22H2 3B 3872H 5B -2H2
o 11 HKK 17).
Since we assumed H² < K, we have H-K-7/4 S H². Then we can drop Õ( K-7/// -7/4/7). 2K B Omax is bounded
2K 8 8max 88HK 2B+1 + +6H + 8K--K-2 + 8K-
= H/K
(8KB (177)) log(328 max/ (1)²>20) is bounded
8K 82 max log
328
(m)))2 = Ō (H²m))
Finally, Y& is bounded as
Y4 = =z=ō(H11
J DETAILED PROOFS FOR THE ANALYSIS
In this section, we first introduce lemmas, which bound an online mirror descent term and optimism terms, and these useful to prove Lemma 5. Then present the proofs of Lemmas 3, 4, 5, 6. Then we conclude the section by providing the proof of Thcorem
The following lemma is bound the regret due to online mirror descent. Here, the main difference with the standard online mirror descent lemma (e.g., Hazan et al. (2016); Lattimore & Szepesvári (2020)) comes from the periodic policy mixing, which requires modified analysis.
Lemma 19. Let H <
K. Suppose that Eg and the statement of Lemma 18 hold. Then have
Σ eEE KEK.
Eipe 17
Σ
(s
+ Yr (s 2, (x) o,6 sn))
hE(m
= (0("r1R33
11
dHs
+ 1144 +
22
Proof. Consider e E E. For any & E and & K. such that o, 7 + Tunir (i.e., hi = h.,.1
2), we have
1 arg min (s,)) Ya Dg (s. (. (s)]s))))-)))))))))) D(T(:1 ()][(() ss).
sk+1 A
(+
a(()))A(A)
For ease of notation, we omit (s, -) and (. 8). By Lemma 23, for any policy n
1 (( D D
(2tn + Yn gg + T) <
k
38

---

Published as a conference paper at ICLR 2026
By adding (²,, + hr o
* on both sides, we have for ls = ker.... het1 2,
12,,A A + Y2 h.h R x)
$ Q
( 1
1
D
(2), + Y&O, g.h. - |
a
1
$ D(
D |
|
|
-
&
2a
1
D( [()))))
D क |(]
|
Y&O 11 |
k
a
20
+ 109,n + Yx g.hl
11 |7 - #
1
(( - D( (+ + D(T
- -
D
- a
a
1 |
+
+ 11 &g
7 (33)
2a
where the second inequality follows from Pinsker's inequality and Hölder's inequality, and the last inequality is due to the triangle inequality. By taking Σkek, on both sides, we have
Σ kEKe
Q2,, + Ye 2 m)
1
Re-1-
(D(+| - D(
(D(T|(AA) - ((T||
Cx
k=k.
k=
(I)
kel 2
1
|
#
+1 + Y2 1 1o
+
Σ
1 + Y2
2a
Amm
(II
(V
-1111- 1Q//1111 Qhe
g.h
n
T)-
akat1-1 R) is added, as (33) does not holds for k.+1 1, i.e. " the last episode in epoch e. Furthermore, this term can be bounded by 211@ Qhe 1100 using Hölder's inequality.
Note that @Q/x1-++ +
+Y
9.
g.h
To bound (I), we observe the following. k ke # mod K then मे = -- Thus, D(T (
D(T ( = Otherwise, since / = (1 t + BTunifs we can apply Lemma 26, and thus D(T ( - ( < logl AA, i.e.
Ologg|A|
k ke = 0 mod KB
(( - D ( <
0
otherwise.
It follows that
0 Kg log|AA
log|[A
(I)
Σ
0 Olog
aKB
kEK, K0 modk a
where the second incquality is due to [k E Ke : k he mod K [T]|<
[|Kl//K S
|Kal/ KB + Furthermore, since (II) is in the form of a telescoping sum and k. Kunif, we have
D( < log|A
(I) <
To bound (III), since ax? + bæ 6z (A/( for b. x 2 we have
(III < a K.
2
39

---

Published as a conference paper at ICLR 2026
where C3 is constant such that 11 + Y2 lo C3 for all h, k. Again, by definition of 7f. we have
(IV) =
Σ
10 + YE 9.h 1oc x
kek Kutk cik
K.=0 modk 8
E
11 f.h + Ys 9.h 10ll0001lmmmm O|| #
keK, -, 20 Kg Css
+ 28Cg.
KB
Finally, we have for any policy x and 8 E S,
Σ Qh
Yv g.h ( (8, ),, M [) (-|1)))
kEK.
0 Ke |log
(1 +1+ 0) log A
alKr|C3
28 Kc
aK + 200s + 20s.
aKg
2
Let us take
n for each h E [H]. Then, by taking Ene(m and Bū p it follows that
Ex x
Σ
(Q) g. (sh, :) . s1) - 7. |sh))
hE[HI MEKe
(0| [0K,,llog/A
+ (1 01+ log|AA
a/Ko|Co
20|Ko|Cs KB
+ +00ss + +20s ]
S Epre,a-
H
aKB
2
Kg log/Al
+ (1+ (1+
log/AA
+ a|Ko|C
28 KelCs + +8Cs + 2C3
< H
+
aKB
KB
Finally, by Eg and Lemma 18, we have C3 = 0(H3/ /7). Furthermore, by Lemma 34, the number of epochs is at most OdH)). Then, by taking EeEF E to the above inequality, it follows that
ΣΣ Eçke, KEK,
Σ
(i +YY a (sh, 1), 2) (h) 7 sn))
ME(M]
H
dH
6 K3/4
K
722
The next lemma claims that the regret terms associated with optimism are nonpositive, highlighting the effectiveness of our bonus terms. We closely follow the proof of Lemma 4 of Cassel & Rosenberg (2024).
Lemma 20. Let H K. Suppose that Eg and the statement of Lemma 18 hold. For all (8, h k) E S x A H x [K]x x {S,9).
(s, The (8,a) (00, t/n Vik Vilne) 00
Proof. By definition, we have
(i, (s, a) (0 + tha Dik (,6+1)
The (s) (022 - o + Th: (s, a) T (w0) th V - (s, a)la)))))))
10 02 1 (8, a) [() +1(08
Vn) A 15 (s, a) (1))) BBll (s, a))l
I 100 1 ( (s. a) 1)) +1(0) vh V.. - |1 10th (s, a) - -210, (s, ())a)))))))
+ 11111 (s, a) - < Brllot (s, -
(s, -bll a) (1
where the first inequality is due to the Cauchy-Sehwarz Schwarz inequality, the second inequality follows from Ale < A/. and the last equality is because B, Bp-
40

---

Published as a conference paper at ICLR 2026
Proof of Lemma By Lemma 8,
(( - V2.1 (51) Er,
Σ AE[H]
oish (0E, +4 V.. V(n+2) ( ah)
E
Σ
The hh (8 a T T0 + th V. V2h+1) (h at)
hE[m
Ep
Σ
कx (s a) (0h, + + (0(5))
NE(H!
(
To bound (I), we have
Th (sh, att (0 + dn (. - 02,1
= Th (sh a (0),, - N7 + 3/ (sh a (th - Wi + Bol10% (sh (l. (alto
S 1 (sh, ())l((s))) + B.lllo%%
Th. (s/i a (aN))
where the inequality is due to the Cauchy- Schwarz inequality. Furthermore, since Kg must hold (et) I det (A otherwise would belong to epoch + 1. As is obvious that (A - 3 ) we can apply Lemma 35 for nonzero The (sh a4)) as follows.
10% (5 d MAtt S de(((A))))))
oo (s% 1 1 det((A)) S
This implies that B. (sh a (
(a y
is 28, 10 (5% (la))))> for nonzero oh (s af)). If
Th: (sh at) O, then the inequality is trivial. Then it follows that
(I) S Ep,a+
Σ hE|l]
38bll (sh o
$ Ep,
Σ NE(H
3,861 a Dlll
where the second inequality is due to lo (st, a ( 110(sh at Mb)ala To bound (II), by Lemma 33, we have
(0(s,, at) 3h (sh, axt) T (0t, + thn Vehntt
< (4 - "oo(ss at) (0t, in (n
< 16 ((ag) 118HK-1
where the second inequality follows from the fact that for any E (f,g).
(lst, dt) T (0) thh DK 1 = th ( at)
Pa(s'
sh a Ve (8') & 1+| DA 1looo 4H.
e'ES
This implies that (II) 16H 1 a ( +8H -1 Finally, we have
Vii (s1) - V/2 (81) Ep,z*
Σ
3,8 (s a 167
1l 1 Mal +8H²K-1
AE(N
41

---

Published as a conference paper at ICLR 2026
Taking k== on both sides,
K Σ k=1
K
(VE) (81) (s1))
V.
pp
3 1 o Ablla 1
+ 8H²
1=1
hE|H]
K
k= KE(M)
6K
(33, + 16H 16H log 5 + 8H1
where the second inequality follows from Egg By Lemma 36, have
2 de S 2d + det(A))
Σ
(1
kE|K]
where the second inequality follows from
|I + Erej 0(5% (h)((s a7)) a Tiles 1
k. and thus (At))) z (K 1)d, Furthermore, the Cauchy-Schware inequality implies that [kE at d)))(())-- /2dK log(K + 1). Then we deduce that
Σ Evva (s1) Vii - 63,H 2dK K + + 64dH² log( K +
6K + 833 + 161 log
+ 8H22
- -V "
where the last equality follows from Bb, 3r δ (K1/4
Proof of Lemma
Given c E, for any Ke, the dual variable Y2, is updated as
0
k ker
Ys41 -11 + (s))( b 4aH43 - 40Hrr)]
otherwise.
Then it follows that
0 < y2 1-
k
Σ (Y2+1 - -22)
k=ke
ket1-2
[[1-4antt)) Yr +1 (Vi)(s1) - b 4aH3 - 40H2) )² - x22
k=ke
k2+1-2
+1 [Ix++
Yxx (D (s1) - b 4al13 - 4011- - 4all3 1² x2
k=ko
ke11-2
2Yn (Vi - 4 2 - 4aH2 +n² (ver (s1) - b 4aH -40H2 40HHYY) 2)
kmnk
where the first equality is due to Ys. 0, and the last inequality is due to the fact that max(0, z² for any z E R. This can be rewritten as
2
Ya V (s1))
k=
ket1-2 -2
ket1-2
Σ
Ya(-4aHF - -0H² 4aH +
Σ
(pk (51) -
4aH 40H² 4a HoH )²
0.1
k km
k
(34)
42

---

Published as a conference paper at ICLR 2026
Note that the first term is nonpositive. Furthermore, the second term can be bounded as
I0% (51) -b b 4aH² -0H² 44H - |V% g.1 (s1) - + + 4o +
b|
33H + 4H/² K +
4 x
- 3H 411 + 4 1-1
< 11H + K 3/yY,
where the second inequality follows from Eg the third inequality is because we assumed that H < K. Thus, (34) bounded
1e11-2
1 2
Yu(b-
DA
(31))
S
(I + +HH++ (HPK-3//y,) 2
A
kutt
17
2(121H + 16H --/-/K33/ 3/2
2
k=
where the second inequality is due to the Cauchy-Schwarz inequality. Then we have
kul1-2
Σ KE K
Yu(b - Vrh (s1))
Σ
Yu(b
1 (s1)) + Yk.4 1b v -1
-1 (s1))
kim
R
2(121H + K-32yy3) 33H 3HH k+t1-1
k=
het1-2
< 121nH| K.nnn K-3/2 3/2
Y2 + 3HY
-1
By Lemma 18, we have Y 0(112/7) for all k E [K]. Furthermore, by Lemma 34, the number of epochs is at most (dH)). By taking EeEg, it follows that
Σ KE[K]
Yo(b PK (b1))
Σ Σ Yu(b DE (81))
CEE KEK.
dHH
=ō K1/44 + 72
Proof of Lemma 5
Note that
(o1(s)) + +Y. D* (s1) - ( - Y2VVi( (61)
(P)((s)) + +Tnn)+YyDb. (81)
- ((1 (s1) -V&V (81)
KEE
43

---

Published as a conference paper at ICLR 2026
where V fk Vg are the value functions with respect to contracted MDP. Furthermore, by Lemma 8, it follows that
ΣE REE
(i((s1) Y& (s1) (s1) Yy V (s1))
Σ Σ
Σ Σ
(5 a) +R (5th a)) s/) - ab(a oti))
CEEkEK,
hE[H] aEA
Eptc
Σ Oo . - (s att
Σ
(s') sht a (h)
KEE.
AE(M]
NEES
Phi 1 oh: ( 1ol
Eptc,
Σ Yu AE(M)
(nh Σ
CEE KEK.
R'ES
Note that by the definition of the contracted MDP, we have (s, a) = कh ()) To)T.)... an(o,a)=
Th (s, a) (a)Tog ggh and TPt (s') s, a) Th (s,a) (s'). Then it follows that
Fa a + Σ (s' sh fi = - a (00, + 1h V f.nt2),
(sh
EEES
(n ah) + EP (s' (s' sh V. (5') = (sh, T (0g.1 n + th D v.)+)).
(0
SESS
We deduce that
K
(si) + Ya (81) (s1) (s1) YVV, (s1))(ss)
(i((s))) + +(ls))+\rDx)))) (01) Y/ YaVgi (51)
KEE
Σ Eptc,T
() ΣΣ EECra(thh - Y2 o5 st) - = sf:)
a))
KEK.
AE(N] DEA
ΣΣ KEEK
E Ezzre ix
Σ hE(M
Oialoh ahd - Th. (sh. (0f, + the Vi Finte)
(1)
Esne,
Σ Yv (0 at) - Th (sh,at)) ( Un Vn V (gth+1))
EE KEK
hE(M)
(I1)
By Lemma 19,
(1) -1= K3/4 + K1/4 + dH.
H
72
Note that Y2 2 for all k. Then, by Lemma 20, for any (s, a, h, k) A x [H] [K], we have
(s, 5 (s, a) (0),, + vh V2 / S 0,
Yu @ (s, 2 (s. a) TT (00,. + Φh D vgt+tt)) < 0.
This implies that
(II) (III < 0.
44

---

Published as a conference paper at ICLR 2026
Finally, we have
(i((s)) + +Y2 (51) voVi((ss) = =ō (dIr2
+ 72 -
H
K1/4
dH
+
7
k=1
Proof of Lemma
Note that the dual update is
(0
kf kee
Y&+1 {[1 4on + 1) (D (51) ( -4HH²) ]
otherwise.
Then it follows that for any e E E,
[1 44m 1 1 8.1
(p ( (81) - 1--4ah 4-4H 40H1)
11
2 (1 - 4anlt ) 1 + Pha-11 (51) - -b- -aal3* 4011
= Ykot1 +1 piict1 -2 - (s1) - - 4aH (1 + Y Yke41-2) - 40H2)
ket1-2
2 1k, +
nR (11) - 4aH3 + Yx) - -4HH)
k= Re
Note that Vx_ = 0. Then we have
Re-1-1
h-11-2
(V21(51)-D) -b) E
( -1 ((1)) -b)
A Re
kmke
het1-2
Mlet1-1
(4aH + Yι) + 40H²) + 3H.
7
k kmm
By Lemma 18, have Y, 3(H² /7) for all & [K]. Then it follows that
H (1+ + 40H2 4H² 3/4 Y2) + - =6( H
(TT K-3/4 --3/4+H²* 222 -f2-1
Furthermore, by Lemma 34, the number of epochs is at most Ö(dH). By taking EeE it follows that
Vh (5)) (b)) -)) - ddH5
H kVn)
Σ B KEK.
3/4
7
Proof of Theorem 1 If K By,, cannot use Lemma 16. Nevertheless, in this case, we have the following upper bounds for regret and violation.
Regret(K) HK 18 - 3 =1B
(dIPPKIA).
Violation (K) < HK H3 = - ((HHHK/1/)
Otherwise, it is trivial that the conditions of Lemma 16 hold, i.e., Eg holds with probability least 1 1- 8. Furthermore, under Ey. we have the upper bound on Y₁ as in Lemma 18 with probability at least 1 5, i.e.,
V8 = δ H
(35)
45

---

Published as a conference paper at ICLR 2026
Thus, with probability at least 28, Eg and (35) hold, which can be shown by union bound.
Now, we begin with the proof of the regret upper bound. Note that an optimal policy x² satisfies Var (s1) S b. Since Yx 2 for all k, it follows that
(eg
K
K
K
Σ
( - -V/((01)
+
Σ
Yulb
DA (1())) +
Σ
VA (s1)s) + (. V - -Yab)
R=1
K
K
(V (51())))
+
Σ
Yb - V (s1)) +
(s1) Y Y2 g.1 (51) - VT= Yo,g (81)
(
(1)
(II)
By Lemma 3,
(1) = 1 V
By Lemma 4,
(1)= = δ [K1A+ (KV dHo
(II)
722
By Lemma 5,
(III) = δ [anf
H K1/4 dHb
Thus, we have the following regret upper bound.
Regret K) = T (V KH + KH
H +
k1/4
dH
72
72
Next, we show the violation upper bound. If constraint violation is O, the statement is trivial. Other- wise, we decompose it as
K
Violation K) S
Vir (81) 1 (81)
+
Dk (81) -b) b).
(v)
By Lemma 3,
(V) (V) = ō (VØH*K" V COCHH*K'**HHHHC +HH
By Lemma 6,
(V) δ d
33/4
K1/4
Thus, have the following violation upper bound.
Violation(K) 5 ddH
(4#2² K 3/1 + V. 3/1 / -2/2
K AUXILIARY LEMMAS
Lemma 21. Let c > 0. For [c, 2 let log (log æ1. .... .........o.... Tog For any x, y E (c, 0o)",
we have
|loog x - log vlloo - 1| ---- 2/11
46

---

Published as a conference paper at ICLR 2026
Proof.
Fix 2. E [c, oc) and i {l,...,d} d}. Consider the scalar function p: [0, ++ R defined
as
(t( == log(y) t(x; - -1)) Since (c, 00) is convex, have y/ (1:; y1) 2 min vi) 2 for all [0. 11. so ps is continuously differentiable and
(t())
22 V
y/ + t(a yi)
Hence, for all E [0,
[ts Vil
ar Vi
lp((t)
y/ + t(xi - y1)
c
By the fundamental theorem of calculus,
llog x; - -log yal = lp:(1) - p.(()) = 11/² pt((t dt S J. ('Iicoiaat S
12 yi
Taking the maximum over i and using |= ||=|| for all E TR yields
1 max [ vils isisd
1 c
1 x =11
|logæ log voloo= max log x; log Isi
22 yi
Lemma 22. Let 7th S S + A(A) be any policies. For 8 E [0, 1]. let 7h(-1s) (1 0- +
OTuiit (-1st (-18). For Q/,,. 2i,n :S x A + (-
Y& E R2,, and a > 0, ler kk- (. 8) α
8) exp( -appaaa(() @+ (2,,, (s, +YxQu
g.h (s, )). For any s E S, we have
1. 1
1 (.1 s) - - s)ll 2aH Yk),
2. (#*+1 (-|s) - (1ss) (s,
(s, :)) < 4all Yv) + 40H
3. - (+ss) Hf (s, ( S 2a + 4H0.
Proof. (Proof of the first statement) We show the first statement. Given & E S, we omit (. 8) in notation for simplicity. Note that 7/+1 can be viewed as an optimal solution for min, (T,, 2 f.h + YrO + (() Due to the pushback lemma (Lemma 23), by taking = = ( -0,m + Y2Q D < (7h, Qj. + Y2 + D I
Note that D( (7)) = 0. This can be rewritten as
1 - + a
D (म)) 7 1/ + Ya
To lower bound the left-hand side, Pinsker's incquality implics that
h |
D(*) (
| - - म D(
To upper bound the right-hand side, Hölder's inequality implies that
क - क
Qi.n + YrQ S | - +111") + Ys Y
As a result, we deduce that
x 2 <
+ + Y2Q0%
47

---

Published as a conference paper at ICLR 2026
If || T 1|122 O, then the statement is trivial. Otherwise, it follows that
| ++
* ||| 1 al| + Vo
Since 100, 2H and Y 2 0, we have
b # 2aH Ys).
(Proof of the second statement) Now, we show the second statement. By Hölder's inequality and the triangle inequality,
( the 252n) - am
1 g.h. 1 | -
llo 121l g.h 1o.0
By the first statement,
12++1 - नلل ||||| all (11,)).1,,))) Yoo (8, )loo.
Furthermore, we have
| 7 [1(1 - + OF # - 011 Tunit |11 S.S. 20.
Finally, we have
( k++ - tho 0b. S <all@),(ss))) + + llcc.
Since 11 lo,, 11 1100 2H and Y₁ 2 0,
(#kt1 म 0g,n S 21 Yv) 40H1
(Proof of the third statement) Note that
1
( R *k+1 (F,a)
S
1/
1
1:0
2a
1
2H | - 7
1
20
1
< 2H
pk+1 Ah
#
k+++
2 - -
20
< 2al2 + +2H
where the first inequality is due to Hölder's inequality and Pinsker's 's inequality, the third inequality is due to the triangle inequality, and the last inequality follows from the fact that -ax² + br I 62 /(4a) for a b, x > 0, i.e. a = 1/ 1(2)), b = 2H, x = || 7//l1- The following is true.
| - 1 : mmmit < 0(1 Il +| Juiit (11) s 29.
Finally, we have
( 2 */+1 2),w)
1 a
D (( S 2 + 4H0
as desired.
Lemma 23 (Lemma 1 of Wei et al. (2020), Lemma C.3 of Qiu al. (2020) Let A, int(A) be the probability simplex and its interior, respectively, and let f C + R be a convex function. Fix 0. y E int(A). Suppose x= E arg min f(z) + (1/a)D(x1ly) and x int then, for any z E A.
f(x*) + - D(x* S fz() + 1 (2 1 D(2)lz²))
Lemma 24 (Lemma 33 of Kitamura et al. (2025)). Let Q1. Q2 A - R be two functions. For 0, let n x ixp(aQ1), T2 x exp(aQ2). Then we have
|| T2l11 S 80x|( Q1 Q2lloo-
48

---

Published as a conference paper at ICLR 2026
Lemma 25 (Lemma 5 of Yu al. (2017)). Let [ be discrete time stochastic process
adapted to a filrrtiion {F [Fnhnze h22 with Zu and Fu = {0, R}. Suppose that there exists an integer no > 0, real constants p > 0, 6 max 0, and 0 Ç Ómax such that
1Z Zn 15 Ómax
Nodmaxx
nn <p P in 2 P
B BiZn+no Zn Fn]
-noo.
hold for all E (1,2...)) Then the following holds:
48
80
E|Z.] S p nodmax + r10
log
Vn (1,2,...].
C
Moreover, with probability at least 8,
46 max log
86
46
Zn S p ngdmax +
max ç²
+
max log Vn E f1.2....}
Lemma (Lemma of Wei et al. (2020)). Let mi, n2 be two probability distributions in ((A)). Let u22 (1 8) + A/| where (0, 1). Then,
D(=1 (2) ((T=]|=2) S 0 log|AA, D( ((2)) S log(1A)/0).
Lemma 27 (Lemma 24 of Cassel Rosenberg (2024)). Ler (V(:6) ||0ll W} denote
class of functions V S - R. Suppose that any V E V is L-Lipschitz with respect to O and the supremum distance, i.e.,
IV(:;)) V-:: ((::2))l L110, 0211. 110 112 W.
Let No be the e-covering number of V with respect to the supremum distance. Then
log s d d'log(1 + 2W L/e).
Lemma 28 (Lemma 18 of Cassel & Rosenberg (2024)). For any K 2 1, 8 0, we have that max [y o0-By + log K)] v20
log K
<
B
Lemma 29 (Lemma D.4 of Rosenberg et (2020)). Let {Xete21 be sequence of random vari-
ables with expectation adapted to a filtration F,. Suppose that 0 < X, S C almost surely. Then with probability at least
2T
Σ Fe-1l S Σ
x, + +444 4Clog
1=1
Lemma 30 (Lemma 21 of Cassel & Rosenberg (2024)). Let Øh ognn be in line 14 of Algorithm 1. With probability least 1 - 8, for all k 2 1. h E [H].
11g.h
Tth AlA S 2 2
Lemma 31 (Lemma 22 of Cassel & Rosenberg (2024)). Let o RISI - Rd be the linear operator defined in line 16 of Algorithm 1. For all h [H), let 1/ Ri be of mappings V S R such that | $q and Bo 1. With probability at least 8. for all [H], V Vn- and k 221,
11(vA. V 4.2 K + +1) - (lll))llg((e) logg(HN./5).
where S 3Vd/(2K), N. Ne and N.(Vx) is the e-covering number of Vn with respect the to -nom.
Lemma 32 (Lemma 17 of Cassel & Rosenberg (2024)). For any X > 0 and matrices A, E pddd satisfying A, A' XI, we have that
1
|| - 1/2
A - A'
2vA
49

---

Published as a conference paper at ICLR 2026
Lemma 33 (Lemma 3 of Cassel & Rosenberg (2024)). For any [E] and E R4, we have that
(0(s), (h)) - The (sh, an)
- (4 0h (x)x)))))))))->-->>->)))>>>>))>) + (8(s), ol.
Lemma 34 (Lemma 8 of Cassel & Rosenberg (2024)). The number of epochs |E| is bounded by (3/2)dH 12g(
Lemma 35 (Lemma 12 of Abbasi- Yadkori et al. (2011)). Let B, be positive semi-definite matrices such that A = B + C. Then, we have that
I Ax
I (A)
sup #$0 2
Bx
del(B)
Lemma 36 (Lemma D.2 of Jin et al. (2020)). Let {or h20 be a bounded sequence in R satisfying suprzollor|| & Let Ao E ikd be a positive definite matrix. For any 2 0, define
A Do +
O50
Then, if the smallest eigenvalue of Ao satisfies Amiu (Au) 2 1, we have
(ee((A)) dcp(
det((A))
log
$ A 03 S 2 log
det(Ao)
L NUMERICAL EXPERIMENT
We evaluate Algorithm on a finite-horizon job-scheduling CMDP closely following the setup of Ghosh et al. (2022) with modifications incorporate adversarial losses. The number of episodes and the horizon are set to K = 100,000 and H = 10, respectively, and the state space is S = (0, ........99. 9}. At step sa denotes the number of remaining jobs in the stack, and each episode begins with the initial state 81 = 9. The agent chooses ад E AA= = {0, 1}. where = 1 corresponds to processing the current job and ag 0 corresponds Sh++1 max - 2, 0} with probability 0.8, Sh+1 = max s 1, 0} with probability 0.1, and 84+1 $, otherwise. a, = 0, then $4+1
idling. Specifically, az 1, then
Sh-
The loss and cost functions are defined as follows. To simulate an adversarial setting, in each episode k. the loss is chosen between two functions, f(1) and f(2), with probabilities 0.9 - (k 1) 1) and 0.1 + [K 1), respectively. These functions are defined
an = 0, an = 1 and h (3,,,5,6) (2) (ax) =
4h = 0,
(1) (a))
0.55
0.6
an = 1 and h E (4,5, 6),
0.2 an and h & (3,4,5,6),
0.2 ah 1 and h & (4,5, 6).
The cost defined as gb (8h, Oh, 81+1)
(sh - 1/+1)/2 for all h, and the cost budget set to
b = 5.6.
Figure summarizes the results of running Algorithm for 100,000 episodes. To promote learning, we the parameters as a 0.1, 3,, K// and B.. A, log K, while keeping the other parameters same as in the setup of Algorithm 1. As shown in Figure la, the regret grows sub- linearly in K, despite the fact that the losses are not sampled from fixed distribution. Furthermore, Figure 1b shows that while the constraint violation grows rapidly in the early phase, it eventually converges approximately after episode 45,000. These results support our main claim that both regret and constraint violation are bounded by sublinear terms.
M THE USE OF LARGE LANGUAGE MODELS
Portions of the text were polished using ChaiGPT-5, which was employed for grammar checking and sentence refinement.
50


Reviews:
[{"review_id": "Bgyt6MJpEo", "reviewer": "Reviewer_Zk7f", "summary": "The paper studies online finite-horizon adversarial linear CMDPs where per-episode losses are chosen adversarially with full-information feedback, costs are i.i.d. stochastic with bandit feedback, and the dynamics, loss, and cost all admit a linear feature structure as in linear MDPs. The authors propose a policy-based primal–dual algorithm that, for the first time in this setting, attains simultaneous sublinear regret and sublinear constraint violation, both of order $O(K^{\\frac{3}{4}})$ where $K$ is the number of episodes. To get there, they introduce a nonstandard weighted LogSumExp softmax policies, which arises because they must occasionally mix the current policy with a uniform policy to keep the dual variable under control, and that mixing destroys the simple softmax recursion. The main technical work is (1) proving a new covering-number bound for this mixed policy class, and (2) combining periodic policy mixing with a regularized dual update so that the policy class does not blow up too fast, and the dual variable stays $O(1)$ rates, which together leads to $O(K^{\\frac{3}{4}})$ regret. Experiments on a job-scheduling CMDP with adversarial losses confirm sublinear growth of both metrics.", "questions": "Can you show in the synthetic CMDP that (1) removing periodic mixing makes the dual blow up, or (2) forcing mixing every episode makes the regret curve worse? Right now the experiment doesn’t validate the two key algorithmic ideas.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper gives the first sublinear result in this exact setting. Prior CMDP work with linear function approximation handled stochastic losses/costs, prior adversarial CMDP work handled tabular state spaces. This paper is the first to get both linear function approximation and adversarial losses and constraints with provable sublinear regret and violation. \n\nTechnically, the paper propose analysis to the covering number of weighted logSumExp softmax policy class and periodic mixing to control the dual. Through this way, it is possible to balance statistical complexity and constraint control.\n\nA lot of adversarial/safe CMDP papers fall back to occupancy-measure mirror descent but this paper is policy-based.", "weaknesses": "The paper consider full-information losses, leaving more challenging bandit feedback setting unsolved. \n\nThe regret bound is still suboptimal due to the mixing technique but this is the cost for the additional constraint.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1anwhkHKa3", "reviewer": "Reviewer_j4Sg", "summary": "This paper studies adversarial linear CMDPs. The authors propose a primal-dual policy optimization algorithm that achieves $O(K^{3/4})$ regret bounds for both the objective and constraint violations. (The constraint-violation bound allows error cancellation, though.)\n\nSection 3 presents three technical challenges and their solutions, primarily focused on controlling the dual variable.\n\nNote: I am not an expert in adversarial linear CMDPs, although I am familiar with stochastic linear CMDPs. My comments below may therefore contain misunderstandings.", "questions": "1. Would you explain why controlling the dual variable is necessary for regret analysis in this setting?\n2. Would you describe how naive approaches fail to control the dual variable in adversarial CMDPs?\n3. Would you provide an intuitive explanation of why the mixing technique addresses these failures?\n\nWould you provide a high-level motivation for the algorithm? For example, how it differs from standard primal-dual algorithms for linear CMDPs and which components are critical for handling adversarial environments?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper obtains the first sublinear regret bounds for adversarial linear CMDPs. The authors provide a rigorous analysis of their algorithm; while I did not check every proof detail, the high-level arguments appear reasonable.", "weaknesses": "The writing has some room to be improved. Particularly, the motivation behind the technical challenges and the algorithm is not sufficiently clear. It would be nice if the paper briefly describes natural or \"naive\" approaches for linear CMDPs, and then explain why those approaches fail in the adversarial setting.\n\nFor example,\n- It is nice to state what existing algorithms (e.g., stochastic linear CMDPs) can achieve and why they are inadequate here. Then, it becomes easier for readers to appreciate the contributions. Section 3 currently assumes familiarity with prior work and jumps into technical fixes.\n- Novelty 1 introduces a policy-mixing technique to control the dual variable. It would be nice to explain in Section 3 why mixing is necessary instead of simply using the upper bound implied by a Slater condition (e.g., Ghosh 2022). This point becomes clearer later (around page 7), but until then it was unclear.\n- It would be nice to briefly explain what \"drift analysis\" mentioned in Novelty 3 is. The authors refer to it as a \"well-known method for bounding dual variables,\" but readers would appreciate if it is explained how the method can be applied here or why bounding the dual variable is essential for their regret bounds.\n\nIt appears that many technical challenges and the main contributions stem from the mixing technique. Because the paper does not provide an early, intuitive explanation of that technique, its significance is hard to assess.\n\nOverall, due to the lack of clear motivation and context, I score \"weak reject\" for this paper. However, I'm happy to reconsider my score if the authors can address these concerns.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jtJVLwIxys", "reviewer": "Reviewer_6Wqt", "summary": "This paper presents a novel primal-dual policy optimization algorithm for learning in finite-horizon adversarial CMDPs with linear function approximation, where the reward (loss) functions may vary adversarially and the cost functions are stochastic but constrained. The proposed method is model-free and policy-based, operating directly in the parameter space of policies (e.g., softmax). The authors provide rigorous theoretical guarantees: the algorithm achieves $\\widetilde{O}(K^{3/4})$ regret and $\\widetilde{O}(K^{3/4})$ constraint violation against the best fixed feasible policy in hindsight. This work claims to be the first to provide sublinear regret and hard violation guarantees for adversarial CMDPs with generalization via linear features and policy-based learning.", "questions": "Q1: Could the proposed approach be extended to fully adversarial cost functions (not just stochastic)? What obstacles arise in doing so?\n\nQ2: Is the $\\widetilde{O}(K^{3/4})$ bound tight under your assumptions, or do you believe a $\\widetilde{O}(\\sqrt{K})$ rate is possible with more sophisticated analysis or algorithm design?\n\nQ3: Would the method generalize to nonlinear function approximation (e.g., neural network policies) under similar assumptions?\n\nQ4: Have you considered empirical validation to support the theoretical findings? other than synthetic numerical task?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Novel setting: The paper addresses a previously open setting—adversarial losses with linear CMDPs using policy optimization—for which no prior sublinear regret and violation guarantees existed.\n\nTheoretical rigor: The analysis is sound and carefully done, with clear derivation of the regret and violation bounds under realistic assumptions (e.g., smoothness, realizability).\n\nPolicy-based algorithm: Unlike prior works that rely on occupancy measure optimization or LPs, this work develops a computationally efficient policy-based method applicable to large-scale problems.\n\nNo Slater assumption: The algorithm does not require prior knowledge of a strictly feasible policy, increasing practical applicability.\n\nHard constraint violation: The results hold for non-compensated violation metrics, making the guarantee stronger than many earlier results.", "weaknesses": "W1: Partial adversariality: While the rewards are adversarial, the costs are assumed to be i.i.d. stochastic. The title and claims could more explicitly reflect this partial adversariality to avoid potential misinterpretation.\n\nW2: Gap to optimal rate: The $\\widetilde{O}(K^{3/4})$ regret and violation are not optimal; prior works in simpler settings (e.g., tabular CMDPs) achieved $\\widetilde{O}(\\sqrt{K})$. A discussion of whether this gap is fundamental in the linear function setting is missing.\n\nW3: Limited empirical evaluation (if any): The submission does not include experiments, which makes it difficult to assess the practical effectiveness and convergence behavior of the algorithm, though the paper focuses on theory.\n\nW4: Suggestion for the preliminary: the structure that overviews the strength in the earlier part is quite understandable, however, there appears some terms without mathmatical definition such as dual variables and primal-dual algorithm. It would be better to explain them in the preliminary to enhance the readability of the non-experts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "r8Z1QmGMeu", "reviewer": "Reviewer_Nuny", "summary": "The paper initiates the study of adversarial linear CMDPs by proposing an efficient primal-dual policy optimization method for linear CMDPs with adversarial losses and stochastic constraints. The algorithm assumes full feedback on the loss and bandit feedback on the constraints. This method attains $\\widetilde{O}(K^{3/4})$ regret and violation where $K$ is the number of episodes of the learning dynamic. Slater's condition is assumed, while the algorithm does not need the knowledge of the Slater's parameter $\\gamma$.", "questions": "See weaknesses.\n\nMoreover, I am curious about what would happen to the bounds of the algorithm assuming the knowledge of the Slater's parameter $\\gamma$. Specifically, assuming $\\gamma$ is known, I believe that the space of the dual variables che be optimally bonded to something of order $H/\\gamma$, and no policy mixing/fixed shared approaches are needed. In such a case, can $\\sqrt K$ regret and violation bounds be attained by the algorithm?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main contribution of the work is the setting studied. Indeed, the literature on adversarial CMDPs, up to now, mainly focuses on tabular CMDPs, while linear ones may be more useful in many real world applications. Moreover, while I am not an expert on linear MDPs settings, the algorithm seems to have sufficient technical novelties. To conclude, the overall contribution of the work seems sufficient for acceptance, even if there are many weaknesses that I will highlight in the following.", "weaknesses": "1. The different feedback for losses and constraints is not particularly reasonable in practice. I understand that the choice is made since bandit feedback and adversarial settings were too challenging while full feedback and stochastic settings are generally trivial. Still, I see it as a weakness of the work.\n2. A similar reasoning can be done for the nature of losses and constraints. Nonetheless, given the well known impossibility result on learning with adversarial constraints, this is not the first work on CMDPs focusing on the adversarial losses and stochastic constraints setting. \n3. No lower bounds are provided. Thus, the tightness of the bounds cannot be inferred.\n4. In tabular CMDPs, $K^{3/4}$ regret and violation can be attained without the dependence on the Slater's parameter $\\gamma$. Differently, in this work, the algorithm attains $K^{3/4}/\\gamma$ violation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)