CS Paper Radar

Last-Iterate Guarantees for Online Reinforcement Learning in Structured Constrained MDPs

Nam Phuong Tran, Trinh Ha Mai Huynh, Tuyen Pham Le, Van-Truong Nguyen, Quan Nguyen, Long Tran-Thanh

cs.LG ·submitted 2026-09-26 20:45 UTC · v1

Abstract

In safety-critical applications, deployment uses a single policy, whose performance and constraint satisfaction should hold directly rather than only for an average or mixture of training policies. This motivates last-iterate guarantees in constrained reinforcement learning. Recent progress has established such guarantees in exact-gradient or tabular online settings, yet scalable results for structured large-state problems remain open. We develop a general, statistically efficient framework for last-iterate convergence in structured Constrained MDPs (CMDPs). Our analysis separates contraction of the regularised primal-dual dynamics from actor approximation and statistical errors in policy evaluation under online exploration. This enables model-free on- and off-policy learning with structured function approximation: optimistic policy evaluation avoids explicit transition-model construction, while a compact parametric actor avoids maintaining mixtures or histories of past policies. We instantiate the framework for linear CMDPs and general function approximation, obtaining representation-dependent complexity and improved target-accuracy dependence over prior optimistic regularised primal-dual analyses. We further validate the stabilising effect predicted by our theory on a synthetic linear CMDP: the regularised method exhibits stable last-iterate behaviour, whereas its unregularised counterpart shows larger oscillations.

Closest papers

Nearest neighbours by meaning across the whole index.

Provable Zeroth-Order Safe Exploration for Reinforcement Learning from Human Feedback

cs.LG ·2026-11-05 ·Weiqin Chen, Xinmeng Huang, Dongsheng Ding, Santiago Paternain
theory similarity 0.75
Abstract

Safe reinforcement learning from human feedback (Safe-RLHF) seeks to improve helpfulness while satisfying harmlessness constraints. Existing primal-dual approaches can converge to feasible policies but do not prevent constraint violations during training. We study a stronger requirement, safe exploration for RLHF, under which every policy executed during training, including auxiliary exploration policies, remains feasible. We propose Zeroth-Order Log-Barrier Policy Gradient (ZO-LBPG), a reward-model-free method that optimizes a log-barrier objective using zeroth-order estimates derived directly from human preferences. To ensure safety under noisy feedback, we combine conservative constraint margin estimates with coupled rollouts and an adaptive step size that prevents updates from crossing constraint boundaries. We prove that, with high probability, all iterates and exploration policies remain strictly feasible, and that ZO-LBPG globally converges to an approximately optimal constrained policy. We establish a sample complexity of $\widetilde{\mathcal O}(\varepsilon^{-6}+d^3\varepsilon^{-5})$ trajectories and $\widetilde{\mathcal O}(\varepsilon^{-8}+d^5\varepsilon^{-7})$ human queries. Experiments on a synthetic CMDP and a language-model alignment task corroborate the training-time safety guarantees.

0.16

Safe Offline Reinforcement Learning using Behavior Regularisation and Latent Feasibility Guidance

cs.LG ·2026-11-07 ·Mahesh Keswani, Parth Bhardwaj, Ankur Kumar, Raunak P. Bhattacharyya
top venuebenchmark similarity 0.75
Abstract · Accepted to NeurIPS 2026

Safe offline reinforcement learning (RL) seeks to learn policies that maximize return while satisfying safety constraints, using a static dataset. To characterize state-wise safety, reachability analysis identifies the feasible region, defined as the set of states from which constraints can be satisfied at every future step. Policies are commonly extracted from learned value functions with advantage-weighted regression (AWR). However, AWR relies on exponentiated weights that amplify value estimation errors, whereas behavior-regularized policy gradient methods directly utilize the action gradient of the value function and often make more effective use of learned critics. We propose Feasibility-Optimized Conditional Actor Learning (FOCAL), a method that incorporates behavior-regularized policy gradients into a conditional variational autoencoder (CVAE) actor. FOCAL optimizes this policy using a first-order objective partitioned by feasibility, updating the actor to increase return on transitions estimated to be feasible and to reduce constraint violations on transitions estimated to be infeasible. During inference, FOCAL dynamically adjusts the scale of the latent prior according to the estimated feasibility of the state to adjust the conservatism of action sampling. Theoretically, we show that for AWR, the policy update variance depends exponentially on the advantage error, whereas for FOCAL it scales linearly with the variance of the value estimation error. Across the DSRL benchmark, FOCAL satisfies the constraints on all evaluated tasks while achieving competitive or higher returns compared to baselines.

0.29

Primal-Dual Representation Learning for Low-Rank Constrained MDPs

cs.LG ·2026-10-22 ·Chenhao Zhou, Chao Zhang, Wensong Bai, Hanbin Zhao, Hui Qian
top venuetheory similarity 0.73
Abstract · Accepted at NeurIPS 2026

Representation learning has substantially improved the efficiency of unconstrained continuous-state Markov Decision Processes (MDPs), but its extension to Constrained MDPs (CMDPs) is difficult because the transition representation must be learned while constraint violation is controlled. In this paper, we study representation learning for low-rank CMDPs with continuous state spaces, and propose REP-PD-TEG for the soft cumulative-violation setting. In the feature learning period, the algorithm interacts with the environment using a decaying-$ε$-greedy mixture execution policy, and uses the collected samples to learn transition features by maximum likelihood. Based on the learned features, it constructs uncertainty bonuses and plans with an optimistic Lagrangian objective to obtain the return policy. We prove regret and soft-violation guarantees for the return policies, and quantify the influence of the decaying-$ε$-greedy exploration. In particular, REP-PD-TEG achieves the optimal $\widetilde O(\sqrt K)$ return policy bound, and gives a $\widetilde O(K^{3/4})$ overall sample bound when exploratory actions are charged. For the stricter hard cumulative violation, where feasibility must be verified episode by episode, we propose REP-PD-H-TEG. It plans under a bonus-corrected lower-confidence utility certificate with the learned representation, and performs a stabilized dual search to obtain the return policy, yielding regret and hard-violation bounds. Together, these results give the first theoretically guaranteed representation-learning method for low-rank continuous-state CMDPs with both soft cumulative guarantees and certified hard-violation control.

0.24

Structural Dual Adaptation for Safe Reinforcement Learning

cs.LG ·2026-10-31 ·Runsheng Yu, Zhuoyang Song, Zengde Deng, Qixin Zhang, Li Shen +1 more
similarity 0.73
Abstract · Preprint

Primal-dual methods enforce safety constraints in reinforcement learning through Lagrangian relaxation. For a fixed policy, the exact bounded multiplier response exhibits bang-bang switching at the constraint boundary. Practical gradient updates can oscillate through coupling with policy optimization. We propose Structural DuaL Adaptation (SDLA), which replaces this bang-bang response with a unique continuous response through current-cost centering, trajectory weighting, and quadratic regularization. We characterize activation thresholds and response sensitivity. Ternary search computes multipliers without a dual gradient stepsize. For entropy-regularized tabular policies, we bound equilibrium constraint violations alongside reward gaps. We establish convergence of delayed updates under mild assumptions. Neural PPO/SAC experiments on OmniSafe and HASARD demonstrate competitive rewards with improved constraint tracking. On HASARD, PPO-SDLA achieves higher reported mean reward than the human baseline in six of eighteen settings while meeting the respective mean-cost budgets, including four with lower mean cost. To the best of our knowledge, this is the first report of higher mean reward at lower mean cost than the human baseline across multiple HASARD settings.

0.09

Off-policy Learning with Excursion Policies

cs.LG cs.AI ·2026-11-09 ·Jiamin He, Mark Rowland, Zhaohan Daniel Guo, Hado van Hasselt, Diana Borsa
top venue similarity 0.72
Abstract · Accepted to NeurIPS 2026 (camera-ready)

Off-policy reinforcement learning (RL) tries to learn the value of a target policy while data comes from a different behavior policy. This often requires trading off bias for variance or stability. One way to trade these off is to linearly interpolate between the behavior and target policies, but this represents only one point in a broader space of interpolation mechanisms. We introduce excursion policies--a structured alternative where the agent follows the target policy for a multi-step "excursion" before reverting to the behavior policy. We derive dynamic programming results for these policies, establishing the theoretical basis for their use in RL. We further develop provably sound off-policy temporal-difference (TD) algorithms for excursion value estimation. We find that excursion policies provide an efficiency-stability trade-off comparable to mixture policies in continuous control benchmarks, and our analysis illustrates conceptual differences in their behavior.

0.22

Q-learning Penalized Transformer for Safe Offline Reinforcement Learning

cs.LG ·2026-09-28 ·Shengchao Hu, Peng Wang, Jifeng Hu, Qiyang Zhou, Anning Hu +3 more
publishedbenchmark similarity 0.72
Abstract · ICML submission

This paper addresses the problem of safe offline reinforcement learning, which involves training a policy to satisfy safety constraints using an offline dataset. This problem is inherently challenging as it requires balancing three highly interconnected and competing objectives: satisfying safety constraints, maximizing rewards, and adhering to the behavior regularization imposed by the offline dataset. To tackle this trilogy challenge, we propose Q-learning Penalized Transformer policy (QPT), a \emph{training--inference consistent} framework that bridges conditional sequence modeling with constraint-aware value estimation. QPT trains a Transformer policy that generates actions conditioned on trajectory context and target return/cost, retaining strong behavior regularization. To inject explicit safety semantics during learning, we augment sequence-model training with a Q-shaped penalty using learned reward and cost Q-functions to favor high return under low constraint violation. At inference, the same Q-functions enforce the cost threshold and choose the highest-reward feasible action, closing the loop between training and deployment. We provide a principled analysis under stylized near-deterministic CMDPs, characterizing how Q-penalized conditional generation improve safety and performance. Empirically, QPT consistently outperforms strong safe offline RL baselines across 38 tasks on the DSRL benchmark, and exhibits robust zero-shot adaptation to different constraint thresholds.

0.27

Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluation

cs.LG stat.ML ·2026-08-25 ·Claire Chen, Shuze Daniel Liu, Licheng Luo, Rohan Chandra, Nan Jiang +1 more
similarity 0.72
Abstract

In reinforcement learning policy evaluation, classic on-policy methods often suffer from high variance when estimating policy performance. To mitigate this issue, behavior policy search has been proposed to learn data-collecting policies tailored to reduce online evaluation variance. However, these approaches do not account for uncertainties in the transition functions. In practice, simulator transitions often differ from the real world due to modeling errors or approximation limitations. As a result, behavior policies trained in simulation may still yield high variance when deployed in real environments, leading to costly reliance on real-world evaluation samples. In this work, we propose a double-loop gradient-based algorithm for learning behavior policies that are both efficient and robust to transition uncertainty. Theoretically, we derive novel transition-variance gradient expressions and establish global convergence guarantees for the algorithm. Numerically, we demonstrate that our method is less sensitive to transition perturbations than existing approaches, providing supportive evidence for its practical utility.

0.32

Interactive Distributionally Robust Multi-Agent Learning with General Function Approximation

cs.LG cs.AI ·2026-09-25 ·Debamita Ghosh, George K. Atia, Yue Wang
similarity 0.72
Abstract · 62 pages, 3 figures

Model misspecification poses a fundamental challenge in multi-agent reinforcement learning, where transition uncertainty can be amplified by strategic interactions among agents. Distributionally robust Markov games (DRMGs) provide a principled framework for addressing such uncertainty, yet existing methods often rely on restrictive assumptions or scale poorly to large state and joint action spaces. We study online learning in general-sum DRMGs with general function approximation and $φ$-divergence uncertainty sets. We propose RoMEX-$φ$, a model-free framework that integrates equilibrium-based exploration with dual fitted learning. Through a functional dual representation of the robust multi-agent Bellman operator, RoMEX-$φ$ enables tractable worst-case value estimation from nominal interaction data using a centered empirical robust discrepancy. We introduce the robust Multi-Agent Decoupling Coefficient (robust MADC) to characterize the intrinsic exploration complexity arising from strategic interactions and adversarial transition uncertainty. We establish sublinear robust regret guarantees governed by the robust MADC rather than explicitly by the state and joint action space sizes, replacing tabular dependence with intrinsic function-class complexity. Numerical experiments on a scalable general-sum DRMG under total variation uncertainty show that RoMEX-$φ$ is substantially more resilient to transition shifts than its non-robust counterpart while remaining competitive with an exact tabular robust baseline. Our results provide a scalable framework for distributionally robust multi-agent reinforcement learning with general function approximation.

0.28