Provably Efficient Representation Learning for Low-Rank CMDPs

Kaixuan Liu; Guojun Xiong; Shengpu Tang; Wanyun Si; Jian Li

cs.LGNov 5, 2026

Provably Efficient Representation Learning for Low-Rank CMDPs

Authors: Kaixuan Liu, Guojun Xiong, Shengpu Tang, Wanyun Si, Jian Li

Organizations: Emory University · Shanghai Jiao Tong University · University of Wisconsin-Madison · Stony Brook University

Abstract

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.

Figures & tables

Paper	Model Structure	LFA	Constraint	RepLearn	Regret / Sample Complexity	Violation
Jin et al. [13]	Linear	✓	✗	✗	$\widetilde{\mathcal{O}}(d^{3/2}H^{2}K^{1/2})$	$N/A$
Ghosh et al. [11]	Linear	✓	✓	✗	$\widetilde{\mathcal{O}}(d^{3/2}H^{2}K^{1/2}/\gamma)$	$\widetilde{\mathcal{O}}(d^{3/2}H^{2}K^{1/2}/\gamma)$
Ding and Lavaei [9]	Tabular	✗	✓	✗	$\widetilde{\mathcal{O}}(d^{2/3}H^{5/2}K^{2/3}/\gamma)$	$\widetilde{\mathcal{O}}(d^{2/3}H^{5/2}K^{2/3}/\gamma)$
Zhang et al. [29]	Block	✓	✗	✓	$\widetilde{\mathcal{O}}\big(d^{8}H^{9}\,\varepsilon^{-4}\big)$	$N/A$
Modi et al. [17]	Low-rank	✓	✗	✓	$\widetilde{\mathcal{O}}\big(d^{7}H^{8}\,\varepsilon^{-2}\big)$	$N/A$
Mhammedi et al. [15]	Low-rank	✓	✗	✓	$\widetilde{\mathcal{O}}\big(d^{13}\|\mathcal{A}\|^{2}H^{6}\,\varepsilon^{-2}\big)$	$N/A$

Table 1: Comparison with existing work, where

d

denotes the feature dimension,

H

the horizon,

K

the number of deployment rounds,

\gamma

the Slater gap, and

\varepsilon

the target suboptimality (the learned policy’s value is within

\varepsilon

of optimal with high probability). Rates hide polylog factors via

\widetilde{O}(\cdot)

. LFA denotes linear function approximation; ✗ in the LFA column indicates tabular or non-parametric methods. Bounds stated in terms of

\varepsilon

are PAC sample-complexity guarantees for unconstrained problems and are not directly comparable to regret.

Figure 1: Constrained Latent ComboLock

Figure 2: Reward and Cost vs. iteration on CLCL (H=6)

Setting	Method	Best $R$	Viol.
$H=6$ , $\|\mathcal{A}\|=5$	MFRLC	$\mathbf{0.567}\pm 0.174$	$\mathbf{711.9}\pm 30.8$
	BRIEE	$0.105\pm 0.099$	$1063.1\pm 26.3$
	LAG-PG	$0.008\pm 0.005$	$1614.7\pm 137.7$
$H=8$ , $\|\mathcal{A}\|=3$	MFRLC	$\mathbf{0.692}\pm 0.136$	$207.4\pm 13.0$
	BRIEE	$0.505\pm 0.005$	$683.4\pm 2.7$
	LAG-PG	$0.017\pm 0.004$	$747.4\pm 191.5$

Table 2: Additional CLCL settings (mean

\pm

s.e., 5 seeds). Best

R

: maximum reward per run; Viol.: cumulative violation. Compare within each setting.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Hyperparameter	MFRLC	BRIEE	HOMER	CPO	LAG-PG
Replay Buffer Capacity	60,000	60,000	60,000	N/A (on-policy)	N/A (on-policy)
Episodes per Iteration	48	48	48	48	48
Batch Size	512	512	512	N/A (full batch)	N/A (full batch)
Learning Rate (LR)	3e-4	3e-4	3e-4	3e-4	3e-4
Dual LR ( $\eta$ )	0.05	0.05	0.05	0.02	0.05
Feature Dimension	64	64	256 (hidden)	64 (encoder)	64 (encoder)

Appendix

Table 3: Hyperparameters for all algorithms.

Primal-Dual RL

See all 8 papers

Primal-Dual Representation Learning for Low-Rank Constrained MDPs
Oct 22, 2026Chenhao Zhou, Chao Zhang, Wensong Bai +2Markov Decision Processes Constrained RL
College of Computer Science and Technology, Zhejiang University
Rate-Optimal Algorithm for Adversarial Linear CMDPs
Oct 1, 2026Kihyun Yu, Honghao Wei, Dabeen LeeRegret Minimization in RL Markov Decision Processes
KAIST · Washington State University · Seoul National University
Near-Optimal Sample Complexity for Online Constrained MDPs
Feb 16, 2026Chang Liu, Yunfan Li, Lin F. YangConstrained RL Safe RL
University of California, Los Angeles

Oct 22, 2026J/K move · Enter open · S save

Primal-Dual Representation Learning for Low-Rank Constrained MDPs

Chenhao Zhou, Chao Zhang, Wensong Bai, Hanbin Zhao+1

College of Computer Science and Technology, Zhejiang University

Markov Decision Processes Constrained RL Representation Learning for RL Model-Based RL

Open paper AskPDF arXiv

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.

Abstract

Primal-Dual RL

Explore similar work

Primal-Dual Representation Learning for Low-Rank Constrained MDPs

Rate-Optimal Algorithm for Adversarial Linear CMDPs

Near-Optimal Sample Complexity for Online Constrained MDPs