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 \texttt{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, \texttt{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. \texttt{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 \texttt{MFRLC} achieves both regret and cumulative constraint violation of order $\widetilde 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.