Primal-Dual Representation Learning for Low-Rank Constrained MDPs
Representation learning has improved sample efficiency in unconstrained MDPs, but extending it to constrained settings with unknown dynamics remains largely open. This paper studies low-rank constrained MDPs with continuous states where latent transition features must be learned online while controlling cumulative constraint violations. The authors propose two primal-dual algorithms that combine maximum-likelihood feature learning, uncertainty bonuses, and decaying $\epsilon$-greedy auxiliary probing to obtain the first sublinear regret and violation guarantees for this setting, with an explicit tradeoff between return-policy optimality and the safety cost of exploratory execution.
The paper delivers a genuine first step—sublinear regret and soft or hard violation bounds for low-rank CMDPs with unknown features—by coupling representation learning with primal-dual optimism and a lower-confidence certificate. The separation between return and execution policies is well motivated for safety-critical domains. Nevertheless, the guarantees rest on strong, impractical assumptions including finite realizable model classes, exact oracles, and a positive action-gap condition for the hard result, so the work functions more as a theoretical benchmark than a deployable algorithm.
The tertiary decaying-$\epsilon$-greedy design is a technically sound resolution of the coverage-deployment tension in constrained representation learning. The merged-covariance bonus construction and the explicit schedule tradeoff between return-policy rate and execution-policy cost are cleanly characterized, and the optimistic Lagrangian formulation gives a principled mechanism for soft-violation control. The distinction between policies whose exploratory actions are charged versus those that are not is especially relevant for safety-critical applications.
The analysis assumes a finite realizable model class ($|\mathcal{M}|<\infty$ and $P^\star\in\mathcal{M}$), which is standard in low-rank RL theory but severely limits applicability to genuinely continuous state spaces despite the paper's framing. \n\n The algorithms also require exact MLE and exact optimistic planning, both computationally intractable for continuous or large action spaces. For hard-violation control, an additional positive optimistic-score-gap assumption is introduced solely to bound the softmax approximation during the capped dual search.
The tabular and linear CMDP comparisons in Tables 1 and 2 are directionally fair: the authors correctly note that prior methods require known features, whereas they remove that assumption at the cost of a $|\mathcal{A}|d^2$ factor and $(1-\gamma)^{-2}$ horizon dependence. The lower-confidence utility certificate for hard violation is a reasonable theoretical device, but it receives no empirical validation; the paper explicitly states that experiments illustrate the soft-violation mechanism rather than the hard certification.
No code or data repository is provided. The occupancy oracle abstracts away roll-in sampling costs, and the stated bounds count outer oracle rounds rather than raw environment transitions. Hyperparameters in Theorems 3.1 and 4.1 depend on unknown problem constants ($\theta$, $\bar{b}$, $\gamma$), and the exact MLE and planning oracles are not implementable in practice, so independent reproduction would require substantial algorithmic approximation not covered by the theory.
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-$\epsilon$-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-$\epsilon$-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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.