CS Paper Radar

Instance-Dependent Regret for CMDPs with Step-Wise Constraints

Qian Zuo, Francesco Emanuele Stradi, Leyang Xue, Sattar Vakili

cs.LG cs.AI ·submitted 2026-10-01 21:49 UTC · v1
theory

Abstract

We study online learning in episodic tabular constrained Markov decision processes with step-wise safety constraints. In such a setting, the constraints induce a safe subgraph that shapes the variance of cumulative rewards under feasible policies and, consequently, the difficulty of learning. Exploiting this structure, however, requires learning which actions are safe while controlling constraint violations. We propose Safe Variance-Adaptive Exploration (SVAE), an efficient algorithm that learns candidate safe subgraphs and performs variance-adaptive optimistic planning within them. With high probability, SVAE achieves cumulative regret of order $\widetilde{\mathcal{O}}(\sqrt{SAH\min\{\mathbb{V}_Σ,K\mathrm{Var}^{\star}\}}+S\sqrt{AH^3\min\{K,\mathcal{C}\}}+S^2AH^2)$ over $K$ episodes, where $H$ is the horizon of a single episode, while $S$ and $A$ are the numbers of states and actions, respectively. Here, $\mathrm{Var}^{\star}$ is the maximum return variance among safe policies, $\mathbb{V}_Σ$ is the variance accumulated before the first unsafe action is encountered, and $\mathcal{C}$ captures the statistical complexity of eliminating actions incorrectly considered potentially safe. SVAE additionally attains $\widetilde{\mathcal{O}}(H\sqrt{SAK}+S^2AH^2)$ step-wise constraint violation and a gap-dependent violation bound that is polylogarithmic in $K$. Finally, we establish a lower bound showing that dependence on these instance-specific quantities is unavoidable.

Closest papers

Nearest neighbours by meaning across the whole index.

Closing the Log Gap: Minimax-Optimal Regret for Episodic RL

cs.LG stat.ML ·2026-10-29 ·Guy Zamir, Victor Boone, Matthew Zurek, Yudong Chen
theory similarity 0.70
Abstract

In this paper, we study the regret minimization problem in episodic tabular MDPs. Our algorithm achieves the first expected regret bound scaling as $\sqrt{H^3 S A K}$ for sufficiently large $K$, where $H$ is the episode length, $K$ is the number of episodes, and $S$ and $A$ are the numbers of states and actions, respectively. Our method is the first to match the minimax lower bound \emph{without extra polylog factors}. We introduce a variant of UCBVI which does not maintain strictly optimistic estimates, and uses MOSS-style exploration bonuses whose logarithmic terms adapt to both visit counts and estimated variances. A key challenge is controlling the propagation of errors caused by under-optimism, which we accomplish in an occupancy-weighted way, avoiding logarithmic overhead that would be incurred by uniform-over-rows concentration. Our analysis develops time-uniform and variance-aware concentration bounds that may be of independent interest. As a corollary we also develop an algorithm for $(\varepsilon, δ)$-PAC best-policy identification, which is the first to match the $Ω\big(H^3 SA\log(\frac{1}δ)\varepsilon^{-2}\big)$ minimax lower bound up to constants in some regimes.

0.13

Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation

cs.LG ·2026-09-30 ·Kihyun Yu, Seoungbin Bae, Dabeen Lee
similarity 0.69
Abstract

We study infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the weakly communicating assumption. Existing high-probability guarantees for this setting either require computationally inefficient algorithms or have suboptimal dependence on the number of interactions $T$. We propose, to the best of our knowledge, the first computationally efficient algorithm that achieves $\widetilde{\mathcal{O}}(\sqrt{T})$ regret and cumulative constraint violation with high probability in the tabular setting. The $\sqrt{T}$ dependence is optimal up to logarithmic factors. Our approach incorporates cumulative constraint violation into the state and defines a reshaped reward through differences of a Huber potential. The added state determines the penalty on further violations while the reward function remains fixed on the augmented state space. Since the added state has known deterministic dynamics, only the original transition kernel needs to be estimated. The bounded slope of the Huber potential keeps the per-step reward bounded, and the potential differences telescope to relate the reshaped return to the original cumulative reward and the terminal potential. These properties allow us to apply finite-horizon approximation and optimistic value iteration with clipping, as used in unconstrained average-reward MDPs, without worsening the regret rate in $T$.

0.25

Safe Multi-Objective Reinforcement Learning: Zero Constraint Violation and Primal-Averaging Convergence

cs.LG cs.AImath.OCstat.ML ·2026-10-29 ·Chenxi Li, Yao Shu, Siyang Gao, Shuang Qiu, Guangxin Jiang
similarity 0.68
Abstract

Many applications of multi-objective reinforcement learning (MORL) require policies that balance conflicting objectives while satisfying safety constraints. We study safe MORL with zero constraint violation throughout learning, covering both cumulative and stepwise constraints. A key challenge is to explore sufficiently under unknown dynamics and constraint costs without violating the constraints. For a given preference over objectives, we develop an algorithm to learn a safe Pareto optimal policy by combining optimistic reward estimates with pessimistic cost bounds. With high probability, every policy executed over $T$ episodes incurs zero constraint violation. The algorithm returns a safe Markov policy induced by the averaged occupancy measure and achieves an $\widetilde{O}(1/\sqrt{T})$ suboptimality gap under smooth Tchebycheff scalarization. We further develop a preference-free algorithm that first explores safely without a prespecified preference and then computes a safe policy for any given preference without further interaction. Over $T$ exploration episodes and $K$ planning iterations, it retains the same safety guarantee and achieves an $\widetilde{O}(1/\sqrt{T}+1/\sqrt{K})$ suboptimality gap. Both algorithms require knowledge of a policy that strictly satisfies the constraints and its costs. We then relax these requirements, incurring at most constant cumulative violation. To our knowledge, we provide the first sample-efficient MORL algorithms that guarantee safety for every executed policy.

0.15

Toward Optimal Regret in Adversarial MDPs with Stochastic Hard Constraints

cs.LG ·2026-10-08 ·Qian Zuo, Francesco Emanuele Stradi
theory similarity 0.68
Abstract

We study episodic constrained Markov decision processes with adversarial losses under stochastic hard constraints. Specifically, starting from a known strictly feasible policy with margin $d$, we seek to obtain optimal regret while satisfying the expected cost constraints in every episode. In this setting, Stradi et al. (2025) show that a carefully designed mixing rule attains regret of order $\widetilde{\mathcal{O}}(\sqrt{T}/\min\{d,d^2\})$. Interestingly, they also provide a lower bound of order $Ω(\sqrt{T}/ρ)$ for the same setting, where $ρ$ is the Slater margin of the offline problem and can be much larger than $d$. In this work, we build on their approach to obtain optimal regret dependence on these margins. Specifically, we propose MA-OPS, an algorithm that combines an optimistic search for the Slater margin with a pessimistic evaluation of the selected policies to safely learn a policy with a large feasibility margin. This policy is then used to minimize regret while satisfying the constraints at every episode. In particular, we show that MA-OPS attains regret $\widetilde{\mathcal{O}}(\sqrt{T}/ρ+ 1/(dρ))$. Finally, we provide a matching lower bound, showing that the dependence on $T$, $d$, $ρ$ in the regret bound is optimal up to logarithmic factors.

0.20

Improved Regret via Variance-Aware Policy Optimization in Adversarial MDPs

cs.LG ·2026-11-12 ·Ofir Schlisselberg, Alon Cohen, Yishay Mansour
theory similarity 0.68
Abstract

We study episodic adversarial MDPs with unknown dynamics and full-information rewards and achieve regret with leading term $\widetilde O(\sqrt{H^3SAK})$. Here $H$ is the horizon, $S$ the total number of states across decision layers, $A$ the number of actions, and $K$ the number of episodes. This improves the two incomparable prior leading terms by factors $\sqrt{S/H}$ and $\sqrt{H^3}$, leaving a factor $\sqrt H$ to the lower-bound scale. We give a reduction from unknown to known dynamics for \emph{downstream-dependent} algorithms, whose policy at step $h$ is computed only from information at steps $h+1$ and onward. This reduces the remaining leading-order gap to finding a downstream-dependent known-dynamics algorithm with $\widetilde O(H\sqrt K)$ regret, which would yield the tight $\widetilde O(H\sqrt{SAK})$ leading term for unknown dynamics. We instantiate the reduction with VOPO, a policy optimization (PO) algorithm. Its improved guarantees follow from a variance-aware analysis enabled by a novel bonus, which we call the Stability-Matching Bonus (SMB). VOPO achieves $\widetilde O(\sqrt{H^3K})$ regret under known dynamics with full information; its $\sqrt H$ gap to the target $H\sqrt K$ rate is inherited by our unknown-dynamics guarantee. We also show that with known dynamics and trajectory bandit feedback, VOPO achieves $\widetilde O(\sqrt{H^2SAK})$ regret. Both known-dynamics guarantees improve the corresponding state-of-the-art PO bounds by a factor $\sqrt H$. A matching lower bound establishes that the full-information rate is tight in one parameter regime.

0.09

Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling

cs.LG stat.ML ·2026-10-19 ·Victor Boone, Cyrille Kone, Waris Radji, Odalric-Ambrym Maillard, Dorian Baudry
theory similarity 0.67
Abstract

We study regret minimization in finite-horizon episodic Markov Decision Processes (MDPs). While minimax-optimal algorithms are known, tractable approaches to instance-dependent optimality are still lacking. Motivated by this gap, we introduce $π_0$-PSRL, a variant of PSRL that uses posterior samples to decide when exploration is needed, while following a fixed reference policy $π_0$ during exploration episodes. This decouples the test for exploration, triggered when the sampled and empirical MDPs have different optimal policies, from the choice of the policy used to gather information. The resulting design addresses a limitation of standard PSRL, where the sampled optimal policy may not be the optimal choice for exploration. We prove instance-dependent regret bounds for $π_0$-PSRL, identifying the logarithmic exploration cost induced by $π_0$ and taking a step toward matching asymptotic lower bounds for episodic RL. Our proof techniques showcase a novel proof structure to derive problem-dependent regret bounds in episodic MDPs, and concentration results for Dirichlet random variables, that may be of independent interest.

0.12

Closing the Horizon Gap in Policy Optimization for Adversarial MDPs

cs.LG stat.ML ·2026-10-08 ·Mingyi Li, Taira Tsuchiya
similarity 0.66
Abstract · 17 pages, 2 tables

We consider policy optimization for online episodic tabular Markov decision processes (MDPs) with adversarial losses and bandit feedback. Policy optimization updates the policy locally at each state and avoids optimization over the occupancy-measure polytope, but its existing regret bounds are larger by a factor of the horizon $H$ than those of occupancy-measure-based algorithms. We close this gap by using regularized $Q$-functions, which allow us to control the stability of the local updates jointly over all state-action pairs rather than separately at each state. The resulting algorithm attains high-probability regret bounds of $\widetilde O(\sqrt{HS(H+A)T})$ for known transitions and $\widetilde O(HS\sqrt{AT})$ for unknown transitions, where $S$ is the number of states, $A$ the number of actions, and $T$ the number of episodes. Both bounds improve the horizon dependence of existing policy optimization bounds, and the latter matches the best-known bound. We further extend the algorithm to adversarial linear-mixture MDPs and obtain the same improvement in the horizon dependence.

0.24

Beyond Monotonicity: Stochastic Online Optimization under Semi-Bandit Feedback

cs.LG ·2026-11-02 ·Tsubasa Harada, Yasushi Kawase, Hanna Sumita
theory similarity 0.66
Abstract · 44 pages, 1 figure

We study stochastic online optimization (SOO) under semi-bandit feedback: in each of $T$ rounds, a policy adaptively observes $n$ independent random variables with unknown distributions, learning only from observed values. First-order stochastic dominance (FSD) monotonicity enables general reductions for learning SOO, but can fail when observations change future feasibility, resource use, or reference points. Our algorithm runs the dynamic program for the optimal policy, replacing each expectation by its most optimistic value over a confidence set of distributions. Its regret depends on the level-set complexity $s_i$ of the computed values as functions of the $i$th variable: the number of intervals needed to describe their superlevel sets. For rewards in $[0,1]$, the regret is $\tilde{O}(\sqrt{ST})$ without this monotonicity, where $S=\sum_{i=1}^n\min\{s_i,k_i\}$ and $k_i$ is the support size of the $i$th distribution, which may be infinite when $s_i$ is finite. For constant level-set complexities, regret is $\tilde{O}(\sqrt{nT})$, even for continuous distributions. The algorithm requires no knowledge of $s_i$, $k_i$, or the supports, and it also achieves regret $\tilde{O}(\sqrt{nkT})$ for supports of size at most $k$ without any level-set condition, which improves the previous bound $\tilde{O}(n(\sqrt{kT}+k))$ for FSD-monotone problems. We also prove a lower bound of $Ω(\min\{T,\sqrt{ST}\})$ for all positive integers $s_1,\ldots,s_n$ with $k_i=2s_i+1$, which holds even under full feedback and matches the upper bound up to logarithmic factors. We obtain $\tilde{O}(\sqrt{nT})$ regret for these problems, all nonmonotone under FSD: stochastic Boolean function evaluation, the full-information secretary problem, optimal stopping with loss aversion, scheduling with deadlines and correlated stochastic knapsack with unimodal rewards, and overbooking with group reservations.

0.16