Primal-Dual RL

RL: Reinforcement Learning

Follow this topic Ask about this topic

Latest papers

8 papers2 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

Provably Efficient Representation Learning for Low-Rank CMDPs
Nov 5, 2026Kaixuan Liu, Guojun Xiong, Shengpu Tang +2Primal-Dual RL Markov Decision Processes
Emory University · Shanghai Jiao Tong University · University of Wisconsin-Madison +1
Structural Dual Adaptation for Safe Reinforcement Learning
Oct 31, 2026Runsheng Yu, Zhuoyang Song, Zengde Deng +3Primal-Dual RL Constrained RL
China Merchants Research Institute of Advanced Technology, China Merchants Group, Hong Kong, China · The Chinese University of Hong Kong, Hong Kong, China · Generative AI Lab, College of Computing and Data Science, Nanyang Technological University, Singapore +1
Finite-Time Guarantees for Constrained Reinforcement Learning under Partial Observability
Oct 15, 2026Valentina Zaccaria, Philip Jordan, Tingting Ni +2Primal-Dual RL Reinforcement Learning
University of Padova · SYCAMORE, EPFL
Markovian Nonconvex ADMM for Reinforcement Learning: Bellman-Resolvent Stability Beyond Smooth Blocks
Sep 29, 2026Zhaojun PengPrimal-Dual RL Alternating Direction Method of Multipliers
Last-Iterate Guarantees for Online Reinforcement Learning in Structured Constrained MDPs
Sep 26, 2026Nam Phuong Tran, Trinh Ha Mai Huynh, Tuyen Pham Le +3Primal-Dual RL Function Approximation in RL
Inria centre at the University of Lille Lille, France · Vin Motion Vietnam · Department of Computer Science University of Warwick Coventry, United Kingdom
CSPO: Constraint-Sensitive Policy Optimization for Safe Reinforcement Learning
Jun 12, 2026Ayoub Belouadah, Sylvain Kubler, Yves Le TraonPrimal-Dual RL Constrained RL
SnT, University of Luxembourg
Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret
May 12, 2026Kihyun Yu, Beomhan Baek, Dabeen LeeRegret Minimization in RL Markov Decision Processes
1KAIST · 2Seoul National University
Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards
Mar 29, 2026Kihyun Yu, Seoungbin Bae, Dabeen LeePrimal-Dual RL Adversarial MARL
Department of Industrial and Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University · Research Institute of Mathematics, Seoul National University +2

Nov 5, 2026J/K move · Enter open · S save

Provably Efficient Representation Learning for Low-Rank CMDPs

Kaixuan Liu, Guojun Xiong, Shengpu Tang, Wanyun Si+1

Emory University · Shanghai Jiao Tong University · University of Wisconsin-Madison+1

Primal-Dual RL Markov Decision Processes Constrained RL Representation Learning for RL Low-Rank Representation Learning Model-Free RL

Open paper AskPDF arXiv

We study representation learning in low-rank Constrained Markov Decision Processes (CMDPs), where both value and reward functions are approximated by a set of unknown representation vectors, and the transition dynamics admit a low-rank factorization. The objective is to maximize expected cumulative rewards while complying with constraints on the expected cumulative utility. To achieve this, we propose MFRLC (Model-Free Representation Learning for Low-Rank CMDP), a model-free algorithm that uses a primal-dual scheme to effectively balance reward regret and constraint violations. To the best of our knowledge, MFRLC is the first representation-learning method for low-rank CMDPs that combines the Least-Squares Value Iteration with Upper Confidence Bound (LSVI-UCB) and primal-dual techniques. MFRLC further enhances value function estimation with bonuses for function approximation and learns the mapping from representations to value functions directly, avoiding explicit estimation of the transition kernel. We prove that, with high probability, MFRLC achieves

\widetilde O(K^{3/4})

reward regret and cumulative constraint violation over

K

deployment rounds, independent of the size of the state space. To our knowledge, these are the first sublinear regret and violation guarantees for CMDPs with unknown features.