PaperlayerView exact revision on arXiv

Source-linked AI summary

Rate-Optimal Algorithm for Adversarial Linear CMDPs

Kihyun Yu, Honghao Wei, Dabeen Lee

arXiv:2610.00927v1cs.LG

TL;DR

Prior work left a gap in adversarial linear CMDPs between computational efficiency and statistically optimal episode dependence. This paper proposes a primal-dual algorithm with rate-optimal regret and cumulative constraint-violation guarantees, without Slater’s condition.

  • Problem

    Prior approaches did not jointly provide computational efficiency for large state spaces and statistically optimal episode dependence in adversarial linear CMDPs.

    Source: §1 · p. 2

  • Method

    The primal-dual method combines adaptive FTRL and dual-variable clipping with drift analysis that avoids policy mixing.

    Source: §1 · p. 3, §6 · p. 12

  • Results

    The algorithm achieves rate-optimal regret and cumulative constraint-violation guarantees without Slater’s condition.

    Source: §6 · p. 12

  • Takeaways & Limitations

    Avoiding policy mixing resolves its conflict with controlling the value-function covering number in linear CMDPs.

    Source: §1 · p. 2, §6 · p. 12

    Achieving optimal dependence on d and H remains future work.

    Source: §4.2 · p. 10

Abstract

from arXiv · show

We study episodic adversarial linear constrained Markov decision processes (CMDPs) with unknown transitions, where both the loss and constraint functions may vary adversarially across episodes. The best previous algorithm achieves $\widetilde{\mathcal{O}}(K^{3/4})$ regret and cumulative constraint violation, leaving a gap to the optimal $\widetilde{\mathcal{O}}(\sqrt{K})$ dependence on the number of episodes $K$. We close this gap by proposing a new primal dual algorithm that achieves $\widetilde{\mathcal{O}}(\sqrt{K})$ regret and cumulative constraint violation without assuming Slater's condition. The main challenge is that learning linear CMDPs requires uniform concentration over a value function class with a controlled covering number, whereas standard techniques in constrained online learning, such as policy mixing, can make this class more complex. Our algorithm combines adaptive Follow the Regularized Leader (FTRL), contracted value estimation, and an exponential Lyapunov function. An adaptive dual regularizer offsets the dependence on the dual weights in the primal regret bound, removing the need for policy mixing. We further show that the normalization in the FTRL update bounds the policy parameters independently of the magnitudes of the dual weights, which explains why the resulting policy class remains compatible with uniform concentration. Under feature access, the computational complexity is independent of the size of the state space.

1 Introduction

The introduction identifies a gap in adversarial linear CMDPs: prior approaches are either computationally inefficient or statistically suboptimal. It presents a rate-optimal algorithm that avoids policy mixing and does not require Slater’s condition.

1 Introduction

  • Linear CMDP research addresses fixed function distributions, while adversarial CMDP work has been limited to tabular settings.Linear CMDP methods for stochastic losses and constraints do not handle changing environments; tabular adversarial methods do not handle large state spaces.Source: §1 · p. 2
  • Existing adversarial linear CMDP algorithms are either computationally inefficient or statistically suboptimal in K.Yu et al. (2026b) are computationally efficient but have suboptimal K dependence; Yu et al. (2026a) become intractable when the state space is arbitrarily large.Source: §1 · p. 2
  • The proposed model-free algorithm is rate-optimal and computationally efficient even when the state space is large.The paper identifies controlling the value-function class’s covering number as a key challenge.Source: §1 · p. 2
  • Policy mixing can enlarge the value-function class’s covering number, loosening concentration bounds for linear CMDPs.The paper identifies this as a source of the trade-off behind suboptimal guarantees in prior work.Source: §1 · p. 2
  • The algorithm does not require Slater’s condition or guarantees that depend on its positive feasibility margin.The paper contrasts this with prior linear CMDP algorithms that were computationally inefficient or had suboptimal guarantees without that condition.Source: §1 · p. 3
  • An adaptive dual regularizer and exponential Lyapunov function yield drift control without policy mixing.Adaptive FTRL avoids a bounded KL-diameter requirement for the policy update, and clipping the dual variable at a polynomial threshold avoids an exponentially growing bound without affecting dual dynamics.Source: §1 · p. 3

2 Problem Setting

The problem setting models episodic CMDPs with finite state and action spaces for simplicity, linear function and transition representations, and episode-varying feedback. It evaluates regret and constraint violation under a nonempty feasible-policy assumption and does not impose Slater’s condition.

2 Problem Setting

  • The setting uses finite state and action spaces, a horizon H, K episodes, an initial state, and a constraint threshold b.The finite-state assumption is for simplicity; the paper states that guarantees and computational complexity do not depend on the state-space size.Source: §2 · p. 4
  • Loss and constraint functions are revealed after each episode, while the transition kernel remains unknown to the learner.The setting assumes full-information feedback; the algorithm can also be applied to stochastic constraints under bandit feedback with modifications.Source: §2 · p. 4
  • Performance is measured by regret and constraint violation, with a nonempty feasible-policy region assumed.The paper notes that an alternative comparator based on aggregate feasibility does not permit both measures to be sublinear for any algorithm.Source: §2 · pp. 4–5
  • A known feature mapping represents the loss and constraint functions linearly, and the transition kernel is represented using the same features.The passage specifies a linear transition representation through a feature vector and a state-dependent vector function.Source: §2 · p. 5
  • The guarantees do not assume Slater’s condition or depend on its positive feasibility margin.The paper states that the guarantees hold independently of the Slater constant ξ.Source: §2 · p. 5

3 Difficulty and Our Approach

The covering-number requirement needed for concentration in linear CMDPs makes standard constrained-online-learning techniques difficult to use. The approach avoids policy mixing through a new Lyapunov drift analysis, adaptive regularization, and adaptive FTRL.

Difficulty and Our Approach

  • Policy mixing stabilizes the dual process but makes the policy class more complex, enlarging the covering number and loosening concentration bounds.This is identified as the source of the previous algorithm's suboptimal guarantees.Source: §3 · pp. 5–6
  • The proposed Lyapunov drift analysis avoids mixing: its bound has no KL-divergence term, allowing dual-process stability without perturbing the policy.The approach uses an adaptive dual regularizer with an exponential Lyapunov function.Source: §3 · p. 6
  • The approach targets two technical obstacles: unbounded primal-space diameter and potentially exponential growth of the dual variable under the exponential Lyapunov function.A naive exponential bound on the dual variable could make the covering number large and weaken guarantees.Source: §3 · p. 6
  • Adaptive FTRL addresses the unbounded KL diameter of the policy space; its regret bound depends on log |A| rather than the diameter parameter D.The paper applies adaptive FTRL to the MDP setting and reports that it can be combined with feature contraction for value estimation.Source: §3 · p. 7
  • Clipping the dual variable at a polynomial in K reduces the log covering-number bound from d^2K to d^2 log K.The analysis shows clipping is not activated for a sufficiently large clipping parameter, preserving the violation analysis.Source: §3 · p. 7

4 Algorithm

Algorithm 1 combines epoch-wise policy updates and value estimation with adaptive primal and dual updates. The stated comparison highlights improved guarantees, support for adversarial constraints, and no Slater-condition requirement; the paper also leaves optimal dependence on d and H open.

4.1 Description of Algorithm

  • Algorithm 1 proceeds through epoch-wise policy updates and value estimation, using contracted features and avoiding explicit clipping of value estimates.The simpler policy parameterization is described as important for covering-number analysis.Source: §4 · p. 7, §4.1 · pp. 7–8
  • Adaptive FTRL updates the policy without requiring a bounded KL diameter, and the analysis combines it with feature contraction for value estimation.The adaptive dual regularizer stabilizes the dual process while yielding a drift bound without KL-divergence terms.Source: §4.1 · p. 9
  • The dual update clips Φ′(Zk+1) at K^8 to keep an exponential bound out of the covering-number analysis; the paper says clipping is not activated with high probability.This lets the violation analysis proceed with the original, unclipped dual dynamics.Source: §4.1 · p. 9
  • Algorithm 1 has computational complexity O(d^3HK + d^2|A|HK^2), independent of the state-space size |S|.The paper attributes the terms to determinant calculations and feature contraction with value estimation, respectively.Source: §4.1 · p. 9

4.2 Main Result

  • Theorem 4 states regret and constraint-violation guarantees with probability at least 1 − δ.The paper leaves achieving optimal dependence on d and H as future work.Source: §4.2 · pp. 9–10
  • The comparison reports improved guarantees over Yu et al. (2026b), while handling adversarial constraints without requiring Slater’s condition.The prior algorithm is described as limited to e O(K3/4), requiring Slater’s condition, and handling only stochastic constraints.Source: §4.2 · p. 10

5 Analysis

The analysis combines a regret bound with a Lyapunov bound on the terminal proxy dual variable to derive regret and constraint-violation guarantees. Adaptive FTRL, an adaptive dual regularizer, and dual-variable clipping address the policy-space and covering-number challenges.

5 Analysis

  • Dual-variable clipping keeps the dual variable polynomially bounded, helping control the value-estimate covering number.The analysis addresses the discrepancy between clipped Yk and Φ′(Zk) with a lemma showing that clipping does not occur under its stated conditions.Source: §5 · pp. 10, 12
  • Bounding regret plus the terminal Lyapunov value yields the regret and violation bounds.The analysis uses Φ(x) = e^γx − 1 and bounds on bias terms, the terminal proxy dual variable, and the sum of adaptive regularizers.Source: §5 · pp. 10–11
  • The central bound follows by combining weighted regret and optimistic constraint violation with an upper bound on Lyapunov drift.Summing the drift inequality bounds Φ(ZK+1) by the dual-weighted regularizer sum, which combines with the other ingredient to establish the key relation.Source: §5 · pp. 10–11
  • The adaptive dual regularizer cancels the dual-weight dependence in the primal regret bound.The choice of Rk makes the corresponding terms cancel when the bounds are combined.Source: §5 · p. 11
  • Adaptive FTRL avoids requiring a uniform bound on the primal feasible set, despite the policy space's unbounded KL diameter.This avoids relying on policy mixing to bound KL divergence, a technique that conflicts with controlling the value-function covering number in linear CMDPs.Source: §5 · pp. 11–12

6 Conclusion

The paper concludes that its model-free algorithm gives rate-optimal guarantees for adversarial linear CMDPs without Slater’s condition, while identifying cumulative rather than hard constraint violation as a limitation. It also situates this result among prior tabular, stochastic linear, and adversarial linear CMDP work.

6 Conclusion

  • The model-free algorithm achieves rate-optimal regret and constraint-violation guarantees without Slater’s condition, but handles cumulative rather than hard violation.The conclusion identifies developing efficient algorithms with hard-violation guarantees as future work.Source: §6 · p. 12

A Notation

  • Table 2 summarizes notation including the contracted-CMDP quantities, adaptive FTRL terms, dual variables, and Lyapunov function.The notation passage defines Φ(x) = e^γx − 1 and distinguishes the proxy dual variable Zk from the dual variable Yk.Source: Table 2 · p. 18, A Notation · p. 18

B Related Work

  • Prior CMDP research spans tabular settings, stochastic linear function approximation, and safety guarantees under varied violation criteria.The cited work includes tabular adversarial objectives and constraints, as well as linear CMDP algorithms with differing assumptions and guarantees.Source: B Related Work · pp. 18–19

Adversarial and Non-Stationary CMDPs with Linear Function Approximation

C Additional Discussions

The discussion explains why policy mixing is needed in a prior analysis, why hard constraint violation is difficult in this setting, and reviews contracted MDPs and adaptive FTRL.

C Additional Discussions

  • In Yu et al. (2026b)'s analysis, policy mixing bounds KL terms needed for uniform dual control; without mixing, the dual process can become unstable.A naïve upper bound on the dual variable can make the OMD regret term eO(K), so telescoping KL terms does not by itself recover sublinear guarantees.Source: C Additional Discussions · p. 20
  • The algorithm guarantees cumulative, not hard, constraint violation, because deriving the modified bound is difficult after positive-part truncation breaks linearity.The authors leave hard-violation guarantees as future work.Source: C Additional Discussions · pp. 20–21

D.1 Contracted MDP

  • A contracted MDP scales both the loss and transition kernel by ρ, yielding a transition measure whose total mass can be at most one.The passage calls this a sub-probability measure.Source: §D.1 · p. 21

D.2 Adaptive FTRL

  • Adaptive FTRL is suited to policy spaces because its regret bound uses log n rather than the unbounded maximum KL divergence over the simplex.The passage contrasts this with AdaOMD, whose stated regret bound over the probability simplex is unbounded.Source: §D.2 · pp. 22–23

D.2.1 Proof of Lemma 11

The proof develops regularizer and minimizer relations for Lemma 11, then introduces parameterizations used in covering-number analysis. The proof overview of Eq. (15) applies the update rule and telescoping.

D.2.1 Proof of Lemma 11

  • The proof of Lemma 11 combines Lemmas 12 and 13, with Lemma 13 providing three statements under the condition L_1 > 0.The supplied passages do not expose the statements’ full bounds.Source: §D.2.1 · pp. 24, 27
  • Strong convexity of the regularizer and the minimizer property of x_k yield relations used to bound successive iterates in the proof of Lemma 11.The proof also uses that the regularization parameters are nondecreasing and that the iterates lie in the simplex.Source: §D.2.1 · p. 25

D.2.2 Proof Overview of Eq. (15)

  • For Eq. (15), the proof applies the update rule, sums over episodes, and uses telescoping to obtain the stated bound.The supplied proof fragments cite Hölder’s and Pinsker’s inequalities in the intermediate step.Source: §D.2.2 · pp. 27–28

E Parameterization and Covering Number

  • The covering-number section parameterizes Q-function estimates, policies, and value estimates, and defines corresponding function classes for the analysis.It notes that the policy-mixing step is not applied in this work.Source: E Parameterization and Covering Number · pp. 28–29

F Good Event

The section defines a good event for the analysis and establishes that it holds with probability at least 1 − δ. Its proof combines concentration bounds with induction-based boundedness arguments.

F Good Event

  • The probability argument combines a covering-number concentration bound for value estimates with a separate bound for the second event, then applies a union bound.The two probability bounds are each at least 1 − δ/2.Source: F Good Event · pp. 30–31
  • Induction arguments establish boundedness of the Q-function estimates and policies used to show that the proxy good event implies the good event.The proof proceeds by backward induction over the horizon for Q estimates and by induction over episodes within epochs for policies.Source: F Good Event · pp. 31, 33, 35
  • The good event E_g holds with probability at least 1 − δ when 1 ≤ β_ϕ ≤ K and H ≥ 2.The proof first establishes a proxy event with probability at least 1 − δ, then shows that it implies E_g.Source: F Good Event · pp. 30, 33, 35

G.1 Proof of Lemma 5

The section proves Lemma 5 under a good-event assumption and a lower bound on the number of episodes K. The displayed bound involves the problem dimensions and logarithmic terms.

G.1 Proof of Lemma 5

  • Lemma 20 restates Lemma 5 under the good-event assumption, with H ≥ 2 and a stated lower bound on K.The threshold depends on d, H, |A|, and δ.Source: §G.1 · p. 35
  • The proof’s displayed expressions include terms involving d, H, K, and log |A|.The supplied passages do not preserve enough of the expressions to report their full bounds.Source: §G.1 · pp. 35–36
  • Intermediate steps invoke Cauchy–Schwarz, a positive-sequence bound, an upper bound on Y_k, and telescoping.These steps are identified in the proof’s inequality explanations.Source: §G.1 · p. 36

G.2 Proofs of Lemma 6 and Eq. (7)

The section establishes the adaptive-FTRL regret bound over the policy space and bounds bias and optimism terms. It combines these results with the value difference lemma to establish Eq. (7).

G.2 Proofs of Lemma 6 and Eq. (7)

  • The proof establishes the adaptive-FTRL regret bound over the policy space, then combines it with bias and optimism bounds and the value difference lemma to establish Eq. (7).The section identifies the regret result as Lemma 6 and Eq. (7) as a formal statement of the combined bound.Source: §G.2 · pp. 36, 40
  • Under good event Eg, Lemma 22 covers every (s, a, h, k, ℓ) ∈ S × A × [H] × [K] × {f, g}, while Lemma 23 covers every (k, ℓ) ∈ [K] × {f, g} and introduces an absolute constant cbias.Source: §G.2 · p. 38
  • The proof of Eq. (7) decomposes the target term and applies Lemma 11 to the estimated action values over episodes and epochs.The proof also uses the boundedness of the estimated value functions under the good event.Source: §G.2 · pp. 37, 41

G.3 Proofs of Lemmas 7 and 8

The appendix controls the exponential potential and proves that the truncated potential agrees with its target. These bounds support the proof of Theorem 4.

G.3 Proofs of Lemmas 7 and 8

  • The proof controls exponential-potential terms using e^z ≤ 1 + z + z^2 and bounds on the estimated constraint value and dual variables.The argument invokes the good event and restrictions on γ to control the squared terms.Source: §G.3 · p. 43
  • The contradiction argument establishes Φ′(Z_k) = Y_k for every k ∈ [K + 1] under the stated lower bound on K.It considers the first episode where equality fails and uses the preceding episode bounds to derive a contradiction.Source: §G.3 · pp. 43, 44, 46

G.4 Proof of Theorem 4

  • Lemma 27 bounds Regret(k), Y_{k+1}, and Z_{k+1} for every episode under the good event.Its stated regime requires H ≥ 2 and a lower bound on K.Source: §G.4 · p. 46
  • Theorem 4 separates small-K cases from the main regime, where the proof bounds cumulative regret and violation using Lemma 27 and the accumulated potential.For the small-K cases, the proof notes the trivial HK bounds.Source: §G.4 · pp. 47–48

H Numerical Experiments

The experiments compare the method with a baseline on a chain CMDP over 5,000 episodes. The appendix also collects supporting lemmas and reports the authors’ use of generative AI tools.

H Numerical Experiments

  • The comparison uses a chain CMDP with unknown transitions, full-information loss feedback, and five paired-seed simulations; its practical parameter settings differ from those covered by Theorem 4.Each simulation runs for K = 5,000 episodes.Source: H Numerical Experiments · pp. 48–49
  • The method achieves lower cumulative regret and constraint violation than Yu et al. (2026b) over later episodes, while the baseline grows approximately linearly.Figure 1 reports averages over five seeds with 95% confidence intervals.Source: Figure 1 · p. 49, H Numerical Experiments · p. 49

I Auxiliary Lemmas

  • The auxiliary lemmas include value-function covering-number results, an epoch-count bound, and a concentration result for bounded random variables.The section also states inequalities used in the analysis.Source: I Auxiliary Lemmas · p. 50

AI use statement

  • The authors report using generative AI for polishing, checking mathematical arguments, and assisting with numerical-experiment implementation, with author review of AI-assisted work.They state that AI was not used to write complete proofs or manuscript drafts.Source: AI use statement · p. 51
Loading 2610.00927v1…