Toward Optimal Regret in Adversarial MDPs with Stochastic Hard Constraints

1 Introduction

• A small input margin d can require many baseline episodes, even when that baseline incurs large losses.The largest attainable common slack, denoted by ρ, may exceed the supplied margin.Source: §1 · p. 1
• The central question is whether regret can depend optimally on both the known initial margin d and unknown Slater margin ρ while constraints hold in every episode.Source: §1 · pp. 1–2
• MA-OPS safely searches for a large-margin policy, then uses it as the baseline for loss minimization.The paper states that MA-OPS learns a margin of at least ρ/2 within O-tilde(1/(dρ)) episodes while maintaining safety.Source: §1 · p. 2, §1.1 · p. 2

1.1 Original Contribution

• The paper also improves S-OPS’s regret dependence on d from quadratic to linear when d < 1.The earlier comparison is with Stradi et al. (2025a).Source: §1.1 · p. 2

1 Introduction

• MA-OPS achieves sublinear regret with a leading term proportional to 1/ρ and an additive safe-search cost proportional to 1/(dρ), while maintaining feasibility in every episode.The additive term is independent of T, including its logarithmic factors.Source: §1.1 · p. 2

1.2 Related Work

• The lower bound matches MA-OPS’s dependence on T, d, and ρ up to logarithmic factors.The work also positions its approach against prior hard-constraint results and related CMDP and bandit settings.Source: §1.1 · p. 2, §1.2 · p. 3

2 Preliminaries

• The setting has episodic adversarial losses and stochastic constraint costs, with unknown transitions and expected costs.The learner knows the state and action spaces, episode length, and constraint thresholds.Source: §2 · p. 3
• The CMDP is loop-free, with states partitioned into L + 1 layers and transitions only between consecutive layers.A finite-horizon CMDP can be represented this way by duplicating states across time steps.Source: §2 · p. 3

2.1 Online CMDPs with Hard Constraints

• The learner aims for regret sublinear in T while ensuring every expected constraint cost stays below its threshold in every episode, with high probability.Regret is measured against the best feasible policy in hindsight.Source: §2.1 · p. 4
• The learner knows a strictly feasible policy and upper bounds on its expected costs; these determine the known initial margin d, while the Slater margin ρ is unknown.The supplied assumption implies 0 < d ≤ ρ ≤ L.Source: §2.1 · p. 4

3 Improving The Margin Dependence of S-OPS

• When d is small, frequent baseline use can limit execution of the exploration policy; weighting its constraint-violation bound by its execution probability links baseline regret to uncertainty in observed trajectories.This relation supports the linear 1/d dependence while preserving per-episode feasibility.Source: §3 · p. 4

3.1 Safe Optimistic Policy Search (S-OPS)

• S-OPS searches for low-loss policies under optimistic constraints, then mixes them with the baseline using pessimistic cost bounds.It uses online mirror descent to maintain an occupancy measure over policies induced by transition kernels in a confidence set.Source: §3.1 · pp. 4–5

3.2 Regret Guarantee

• S-OPS guarantees per-episode feasibility with sublinear regret and improves the dependence on the baseline margin from quadratic to linear in 1/d when d < 1.The analysis also reduces the dependence on episode length L in the leading term.Source: §3.2 · p. 5

3.3 Proof Sketch

• Retaining execution weights in the regret analysis avoids the extra 1/d factor introduced by bounding errors without those weights.The proof controls baseline-use regret through weighted constraint violations and cumulative upper-occupancy error.Source: §3.3 · p. 6

4 MA-OPS: How to Safely Learn the Slater Margin

• MA-OPS combines optimistic margin search with pessimistic policy evaluation to safely learn a baseline with margin comparable to unknown ρ.The search stops when either the initial margin d or the selected policy’s pessimistic margin estimate reaches at least half the optimistic estimate of ρ.Source: §4 · p. 6
• Optimistic search uses cost lower bounds and transition confidence sets to estimate the largest attainable margin, while pessimistic evaluation uses cost upper bounds to assess the selected policy.The pessimistic evaluation accounts for cost and transition uncertainty.Source: §4 · pp. 6–7
• The algorithm compares the known initial margin d and the selected policy’s pessimistic margin with half the optimistic margin estimate, and returns a baseline with margin at least ρ/2.It can omit the search when 2d ≥ L; testing the initial baseline first avoids unnecessary policy evaluation.Source: §4 · p. 8
• During search, MA-OPS mixes the initial baseline and the candidate policy so that constraints hold in every episode with high probability, even when the candidate is infeasible.It then runs S-OPS for the remaining episodes using the selected baseline and its cost upper bounds.Source: §4 · p. 8

5.1 Main Result

• Theorem 2 guarantees per-episode feasibility and sublinear regret, with a leading term proportional to 1/ρ and an additive search term independent of T.The leading term follows from the known-margin guarantee after finding a baseline with margin at least ρ/2.Source: §5.1 · p. 8

5 Theoretical Guarantees

• The regret bound separates learning with a large-margin baseline from the cost of finding one safely, and its additive search term does not grow with T.The main theorem’s regret and feasibility guarantees hold with probability at least 1 − δ.Source: §5.1 · p. 8

5.2 Proof Analysis

• The proof bounds cumulative margin gaps to control exploration trajectories, then bounds baseline episodes through the same gap and combines search regret with the known-margin guarantee.When the search ends before T, the returned baseline’s margin supports applying Theorem 1 to the remaining episodes.Source: §5.2 · pp. 9–10
• Theorem 3 bounds safe baseline search by e O(L^2|X|^2|A|/(dρ)) episodes and e O(L^2|X|^2|A|/ρ^2) exploration trajectories, while returning a baseline with margin at least ρ/2.All search episodes satisfy the constraints with probability at least 1 − δ.Source: §5.2 · p. 9

6 Regret Lower Bound

• For every-episode-safe algorithms, Theorem 4 gives a regret lower bound matching the dependence on T, d, and ρ up to logarithmic factors.The result holds for 0 < d ≤ ρ ≤ 1/8 and T ≥ 1/(dρ); its construction uses one constraint and three actions.Source: §6 · p. 10
• When d ≤ ρ/4, safe exploration from the initial baseline incurs an unavoidable additive regret cost of order 1/(dρ).The lower-bound argument uses two instances whose cost distributions differ; safety and limited information keep the learner in a common feasible set for order 1/(dρ) episodes.Source: §6 · pp. 10–11

A Additional Related Work

• Unlike sample-complexity guarantees that need not keep data-collection policies feasible, this work bounds regret while maintaining feasibility in every search episode.The related-work discussion contrasts those guarantees with its bound on learning a larger-margin baseline under episode-wise feasibility.Source: A Additional Related Work · p. 17

B Occupancy Measures and Confidence Bounds

• The appendix establishes confidence and occupancy error bounds used in the analyses of S-OPS and baseline search.For a fixed policy, its occupancy under any kernel in the confidence set is bounded relative to the true occupancy.Source: B Occupancy Measures and Confidence… · p. 18

B.1 Occupancy Measures

• Every feasible occupancy in the fixed-policy confidence set is induced by that policy and some kernel in the set, making the fixed-policy cost maximization a linear program.The occupancy representation uses state-action marginals and full transition occupancies for flow and confidence constraints.Source: §B.1 · p. 18

B.2 Estimators and Confidence Bounds

• Cost estimates use Hoeffding bounds and transition estimates use empirical Bernstein bounds; a union bound controls their joint failure probability.The confidence bounds are applied at fixed visit counts, with the resulting event holding with probability at least 1 − δ/8.Source: §B.2 · p. 20

B.3 Occupancy Error Bounds

• The upper occupancy bound takes the maximum state-action occupancy over kernels in the confidence set for the fixed policy.The section uses this bound alongside the fixed-policy occupancy error bound.Source: §B.3 · p. 21
• For a fixed policy, every kernel in the confidence set changes its occupancy by at most L b⊤q in ℓ1 norm; the upper occupancy bound differs from the true occupancy by at most |X| b⊤q.Here b summarizes the transition confidence widths at state-action pairs.Source: §B.3 · p. 21
• During baseline search, the cumulative-visit bound is applied to the n exploration episodes.The passage identifies the search-phase sequence to which the visit-count bound applies.Source: §B.3 · p. 22

C Analysis of S-OPS

• The analysis first establishes zero constraint violation on the confidence event, then combines estimation bounds with mirror descent to prove the regret guarantee.The appendix states these as the two steps in the S-OPS analysis.Source: C Analysis of S-OPS · p. 22

C.1 Algorithm Details

• Each episode mixes the baseline policy with the selected policy, and the next episode’s baseline probability is set using pessimistic cost bounds.Loss estimation uses an upper occupancy bound for the mixture, and observations update the estimates and confidence sets.Source: §C.1 · pp. 22–23

C.2 Zero Constraint Violation

• On the confidence event, S-OPS guarantees G⊤q_t ≤ α at every episode and retains baseline probability at least d/L.The lemma also bounds the selected occupancy by (L/d)u_t.Source: §C.2 · p. 24

C.3 Occupancy-Weighted Estimation Errors

• The proof combines weighted occupancy-error bounds with cumulative cost-confidence widths to establish the estimation-error guarantee.The bounds are combined on an event where the confidence event and concentration bounds hold together.Source: §C.3 · pp. 24, 28
• The weighted-occupancy analysis considers a mixture of two Markov policies and builds confidence sets from observations across episodes.For each component policy, it uses an upper occupancy over kernels in the preceding confidence set.Source: §C.3 · p. 24
• For transition errors, the proof expands occupancies across layers and retains execution weights and squared-width terms.The resulting estimates are uniform over kernels in the confidence set.Source: §C.3 · pp. 25–26

C.4 Proof of Theorem 1

• The regret decomposition separates transition estimation, online mirror descent, baseline use, and policy and comparator loss-estimation errors.The online mirror-descent analysis sums and telescopes divergence terms.Source: §C.4 · p. 30
• The loss-estimation analysis bounds policy and comparator errors, including a martingale fluctuation and conditional bias for policy error.The policy-error martingale is bounded by L2/d, and Azuma–Hoeffding supplies a high-probability event.Source: §C.4 · pp. 29, 31, 32

L T |X||A| log 8m|X|2|A|T

• With probability at least 1 − δ, both regret bounds hold for every feasible occupancy measure and G⊤qt ≤ α in every episode.The proof obtains this by intersecting the events from Lemmas C.2, C.3, C.4 and the martingale bound.Source: L T |X||A| log 8m|X|2|A|T · p. 32

D.1 Exploration Episodes

• Each selected exploration policy executes in finite time almost surely, with execution probability at least d/L and conditional expected visit counts matching its occupancy.The search keeps the selected policy and its execution probability fixed until that policy runs.Source: §D.1 · p. 33

D.2 Margin Bounds and Constraint Violation

• On the stated event, every randomized search policy satisfies the constraints, and the expected number of baseline episodes before an exploration policy executes is at most its margin gap divided by d.The bound is µn ≤ ∆n/d.Source: §D.2 · p. 33

D.3 Number of Exploration Episodes

• At termination, the search returns either the baseline or a searched policy whose margin is at least ρ/2 and whose cost bounds satisfy the stated guarantee.The two stopping tests determine which policy is returned.Source: §D.3 · p. 35

D.4 Number of Baseline Episodes

• A nonnegative supermartingale and Ville’s inequality give a high-probability control for cumulative baseline waiting across search prefixes.The stated failure probability is at most δ/4.Source: §D.4 · p. 36

D.5 Proof of Theorem 3

• With failure probability at most 5δ/8, the search terminates, satisfies its exploration-count bound, and returns a policy with the stated guarantee.The same event ensures the search constraints hold through episode τ.Source: §D.5 · p. 36
• The termination episode τ is bounded by combining the baseline-wait and exploration-count estimates.The proof substitutes the baseline-episode estimate into the exploration-count bound.Source: §D.5 · p. 36
• The proof’s combined failure probability, 5δ/8, is less than δ.This completes the stated high-probability guarantee.Source: §D.5 · p. 36

E Proof of Theorem 2

• The search phase satisfies the constraints, bounds its termination episode, and returns cost bounds with margin bρ ≥ ρ/2.The proof can extend the search beyond T with zero losses when needed for analysis.Source: E Proof of Theorem 2 · p. 37
• After early termination, S-OPS restarts conditionally on the search history with the remaining horizon and a new confidence parameter.The proof applies Theorem 1 to this conditional continuation.Source: E Proof of Theorem 2 · p. 37
• With probability at least 1 − δ, MA-OPS satisfies the constraints in every episode and the stated regret bound holds.The search guarantee and the conditional S-OPS guarantee are combined across the two phases.Source: E Proof of Theorem 2 · p. 37

• In the first construction, only action a1’s cost distribution differs between instances, while a1 is feasible and has zero loss in M2.Safety in M1 forces a constraint on the probability of choosing a1; the KL and Pinsker argument transfers the resulting event to M2, where it implies regret.Source: F Proof of Theorem 4 · p. 38
• The construction extends Stradi et al. (2025a, Appendix F) by setting the initial baseline margin separately from the Slater margin.The proof uses one baseline action with deterministic cost 1/2 − d and considers pairs of instances that differ only in their cost distributions.Source: F Proof of Theorem 4 · p. 38
• In the second construction, a stopping time marks the first policy infeasible in either instance, and policies before it are feasible in both.The proof bounds the stopped histories’ total variation using the per-action cost divergences, then uses the shared-feasibility event to bound the action mixture through episode n.Source: F Proof of Theorem 4 · p. 39
• Both constructions establish the stated lower bound with probability at least 3/4 − 2δ.The first construction yields a bound in instance M2, and the second in instance M1.Source: F Proof of Theorem 4 · p. 39