Provably Efficient Representation Learning for Low-Rank CMDPs

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 uniquely learns the mapping from representations to value functions directly through representation learning. We prove that MFRLC achieves both regret and cumulative constraint violation of order $\tilde{O}(H^3{d}^2{K}^{3/4}|\mathcal{A}{|}^{3/2}/\gamma )$, making it provably sample-efficient and highly adaptable to complex environments due to the reliance on function approximation.