betaFeedback

WorksComputer Science

Provably Efficient Representation Learning for Low-Rank CMDPs

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 O~(K3/4)\widetilde O(K^{3/4}) reward regret and cumulative constraint violation over KK 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.

Introduction

Safe Reinforcement Learning (SRL) has been widely studied and applied in real-world settings. For example, SRL addresses collision avoidance in autonomous driving [19] and resource allocation in healthcare [28], underscoring its importance in safety-critical domains. To address these challenges, a standard framework for SRL is the Constrained Markov Decision Processes (CMDPs). In a CMDP, the agent learns a policy that maximizes expected cumulative rewards while satisfying specified underlying constraints. Designing efficient learning-based algorithms for CMDPs has attracted considerable attention. Model-based methods [10] learn an explicit CMDP model, but incur substantial storage and computational overhead in large-scale or continuous state spaces. Model-free methods avoid this: tabular variants [26, 8] store value functions directly, while recent works adopt linear function approximation (LFA) to handle large state-action spaces [11], achieving provably near-optimal O~(K1/2)\widetilde{O}(K^{1/2}) regret and violation rates.

A central limitation of existing LFA-based methods is the assumption that the underlying features are known a priori [8, 11]. In practice, such features are typically unknown, rendering these methods inapplicable. Meanwhile, the low-rank MDP framework [3] enables representation learning without prior feature knowledge, and provably efficient algorithms exist for the unconstrained setting [29, 17, 15]. However, extending representation learning to CMDPs is non-trivial. In the unconstrained setting, representation learning and policy optimization are largely decoupled; in a CMDP, the learned representation must simultaneously support both reward maximization and constraint satisfaction, and errors in the representation propagate into both objectives in a tightly coupled manner that standard primal-dual analyses cannot accommodate.

PaperModel StructureLFAConstraintRepLearnRegret / Sample ComplexityViolation
Jin et al. [13]Linear✓✗✗O~(d3/2H2K1/2)\widetilde{O}(d^{3/2}H^{2}K^{1/2})N/A
Ghosh et al. [11]Linear✓✓✗O~(d3/2H2K1/2/γ)\widetilde{O}(d^{3/2}H^{2}K^{1/2}/\gamma)O~(d3/2H2K1/2/γ)\widetilde{O}(d^{3/2}H^{2}K^{1/2}/\gamma)
Ding and Lavaei [9]Tabular✗✓✗O~(d2/3H5/2K2/3/γ)\widetilde{O}(d^{2/3}H^{5/2}K^{2/3}/\gamma)O~(d2/3H5/2K2/3/γ)\widetilde{O}(d^{2/3}H^{5/2}K^{2/3}/\gamma)
Zhang et al. [29]Block✓✗✓O~(d8H9ϵ−4)\widetilde{O}(d^{8}H^{9}\epsilon^{-4})N/A
Modi et al. [17]Low-rank✓✗✓O~(d7H8ϵ−2)\widetilde{O}(d^{7}H^{8}\epsilon^{-2})N/A
Mhammedi et al. [15]Low-rank✓✗✓O~(d13∣A∣2H6ϵ−2)\widetilde{O}(d^{13}|\mathcal{A}|^{2}H^{6}\epsilon^{-2})N/A
This WorkLow-rank✓✓✓O~(d2H3K3/4∣A∣3/2/γ)\widetilde{O}(d^{2}H^{3}K^{3/4}|\mathcal{A}|^{3/2}/\gamma)O~(d2H3K3/4∣A∣3/2/γ)\widetilde{O}(d^{2}H^{3}K^{3/4}|\mathcal{A}|^{3/2}/\gamma)

Table 1. Comparison with existing work, where dd denotes the feature dimension, HH the horizon, KK the number of deployment rounds, γ\gamma the Slater gap, and ϵ\epsilon the target suboptimality (the learned policy’s value is within ϵ\epsilon of optimal with high probability). Rates hide polylog factors via O~(⋅)\widetilde{O}(\cdot). LFA denotes linear function approximation; ✗ in the LFA column indicates tabular or non-parametric methods. Bounds stated in terms of ϵ\epsilon are PAC sample-complexity guarantees for unconstrained problems and are not directly comparable to regret.

In this work, we bring representation learning to low-rank CMDPs and propose MFRLC, which in each round first learns representations via a minimax objective and then fits the value function using the learned features within a primal-dual LSVI-UCB framework. This constitutes the first approach for online low-rank CMDPs with unknown features. We prove that MFRLC achieves the same bound for both cumulative reward regret and cumulative constraint violation: O~(Hd2K3/4∣A∣3/2/γ)\widetilde{O}(H d^{2}K^{3/4}|\mathcal{A}|^{3/2}/\gamma), where KK is the number of deployment rounds, HH is the horizon, dd is the representation dimension, and γ\gamma is the Slater gap. The ∣A∣3/2|\mathcal{A}|^{3/2} factor arises from uniform exploration over actions in the representation learning step, and the K3/4K^{3/4} dependence arises from the accumulated statistical error of representation learning (Remark 8). Both bounds are upper bounds. No matching lower bound is known for online low-rank MDPs with unknown features, with or without constraints, so we do not claim that the K3/4K^{3/4} rate or the dependence on dd, HH, and ∣A∣|\mathcal{A}| is optimal. Known-feature CMDPs admit O~(K1/2)\widetilde{O}(K^{1/2}) regret and violation [11]; whether this rate is attainable with unknown features remains open.

Problem Formulation

CMDP Preliminaries

We consider an episodic CMDP ⟨S,A,H,r,g,P,d0⟩\langle\mathcal{S},\mathcal{A},H,r,g,\mathbb{P},d_{0}\rangle, where S\mathcal{S} is the state space (possibly infinite or continuous), A\mathcal{A} the action space (finite, with cardinality ∣A∣|\mathcal{A}|), HH the fixed episode length, r={rh}h=1Hr=\{r_{h}\}_{h=1}^{H} and g={gh}h=1Hg=\{g_{h}\}_{h=1}^{H} the collections of reward and utility functions, respectively, with rh,gh:S×A→[0,1]r_{h},g_{h}:\mathcal{S}\times\mathcal{A}\to[0,1] assumed to be deterministic, P={Ph}h=1H\mathbb{P}=\{P_{h}\}_{h=1}^{H} the collection of transition kernels with Ph(sh+1∣sh,ah):S×A×S→[0,1]P_{h}(s_{h+1}\mid s_{h},a_{h}):\mathcal{S}\times\mathcal{A}\times\mathcal{S}\to[0,1] being the probability of moving to sh+1s_{h+1} from shs_{h} under aha_{h}, and s1∼d0s_{1}\sim d_{0} the initial state of each episode. At each step h∈[H]h\in[H] of round k∈[K]k\in[K], an agent takes action ahka_{h}^{k} at state shks_{h}^{k}, receives reward rh(shk,ahk)r_{h}(s_{h}^{k},a_{h}^{k}) and utility gh(shk,ahk)g_{h}(s_{h}^{k},a_{h}^{k}), and transitions to sh+1k∼Ph(⋅∣shk,ahk)s_{h+1}^{k}\sim P_{h}(\cdot\mid s_{h}^{k},a_{h}^{k}); each episode terminates after HH steps. The policy space is Δ(A∣S,H):={{πh(⋅∣⋅)}h=1H:πh(⋅∣s)∈Δ(A), ∀s∈S,h∈[H]}\Delta(\mathcal{A}\mid\mathcal{S},H):=\{\{\pi_{h}(\cdot\mid\cdot)\}_{h=1}^{H}:\pi_{h}(\cdot\mid s)\in\Delta(\mathcal{A}),\ \forall s\in\mathcal{S},h\in[H]\}, where Δ(A)\Delta(\mathcal{A}) is the probability simplex over the action space; πk∈Δ(A∣S,H)\pi^{k}\in\Delta(\mathcal{A}\mid\mathcal{S},H) denotes the policy deployed in round kk, with πhk(⋅∣shk):S→Δ(A)\pi_{h}^{k}(\cdot\mid s_{h}^{k}):\mathcal{S}\to\Delta(\mathcal{A}) specifying the action distribution at shks_{h}^{k}. Given π={πh}h=1H\pi=\{\pi_{h}\}_{h=1}^{H}, the value function ((expected cumulative reward from sh=ss_{h}=s under π\pi)) and action-value function (from (sh=s,ah=a)(s_{h}=s,a_{h}=a)) are:

Vr,hπ(s)=Eπ[∑i=hHri(si,ai)∣sh=s],Qr,hπ(s,a)=Eπ[∑i=hHri(si,ai)∣sh=s,ah=a].V_{r,h}^{\pi}(s)=\mathbb{E}_{\pi}\left[\sum_{i=h}^{H}r_{i}(s_{i},a_{i})\mid s_{h}=s\right],\qquad Q_{r,h}^{\pi}(s,a)=\mathbb{E}_{\pi}\left[\sum_{i=h}^{H}r_{i}(s_{i},a_{i})\mid s_{h}=s,a_{h}=a\right].

where the expectation is over ai∼πi(⋅∣si)a_i \sim\pi_i(\cdot\mid s_i) and si+1∼Pi(⋅∣si,ai)s_{i+1} \sim P_i(\cdot\mid s_i,a_i). The utility value and action-value functions Vg,hπ(s),Qg,hπ(s,a)V^\pi_{g,h}(s), Q^\pi_{g,h}(s,a) are defined analogously by replacing rr with gg; for brevity, we write Vj,hπ(s)V^\pi_{j,h}(s) and Qj,hπ(s,a)Q^\pi_{j,h}(s,a) for j∈{r,g}j \in\{r,g\}.

We say a policy π\pi is feasible if Vg,1π(s1)≥bV^\pi_{g,1}(s_1) \ge b. The agent aims to learn the optimal feasible policy π⋆\pi^\star by solving the following optimization problem:

max⁡π∈Δ(A∣S,H)Vr,1π(s1),subject toVg,1π(s1)≥b,(1)\max_{\pi\in\Delta(\mathcal{A} \mid\mathcal{S},H)} V^\pi_{r,1}(s_1), \qquad\text{subject to}\qquad V^\pi_{g,1}(s_1) \ge b, \tag*{(1)}

where the threshold b∈[0,H]b \in[0,H]. Under the online learning setting of an episodic CMDP, the agent interacts with the environment over a sequence of rounds, and the learning performance is measured by regret and constraint violation as follows:

Regret⁡(K)=∑k=1K(Vr,1π⋆(s1)−Vr,1πk(s1)),Violation⁡(K):=(∑k=1K(b−Vg,1πk(s1)))+,\operatorname{Regret}(K)=\sum_{k=1}^{K}\left(V^{\pi^\star}_{r,1}(s_1)-V^{\pi^k}_{r,1}(s_1)\right),\qquad\operatorname{Violation}(K):=\left(\sum_{k=1}^{K}\left(b-V^{\pi^k}_{g,1}(s_1)\right)\right)_+,

References

  1. [1]Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
  2. [2]Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In ICML, 2017. URL https://proceedings.mlr.press/v70/achiam17a/achiam17a.pdf.arxiv.org/abs/1705.10528
  3. [3]Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. FLAMBE: Structural complexity and representation learning of low rank MDPs. Advances in neural information processing systems, 33:20095–20107, 2020.arxiv.org/abs/2006.10814
  4. [4]Sanae Amani, Christos Thrampoulidis, and Lin Yang. Safe reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 243–253. PMLR, 2021.arxiv.org/abs/2106.06239
  5. [5]Kamyar Azizzadenesheli, Emma Brunskill, and Animashree Anandkumar. Efficient exploration through Bayesian deep Q-networks. In 2018 Information Theory and Applications Workshop (ITA), pages 1–9. IEEE, 2018.arxiv.org/abs/1802.04412
  6. [6]Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In 21st Annual Conference on Learning Theory, number 101, pages 355–366, 2008.
  7. [7]Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo Jovanovic. Natural policy gradient primal-dual method for constrained Markov decision processes. Advances in Neural Information Processing Systems, 33:8378–8390, 2020.
  8. [8]Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. In International Conference on Artificial Intelligence and Statistics, pages 3304–3312. PMLR, 2021.
  9. [9]Yuhao Ding and Javad Lavaei. Provably efficient primal-dual reinforcement learning for CMDPs with non-stationary objectives and constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 7396–7404, 2023.
  10. [10]Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitation in constrained MDPs. arXiv preprint arXiv:2003.02189, 2020.arxiv.org/abs/2003.02189
  11. [11]Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Provably efficient model-free constrained RL with linear function approximation. Advances in Neural Information Processing Systems, 35:13303–13315, 2022.
  12. [12]Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Achieving sub-linear regret in infinite horizon average reward constrained MDP with linear function approximation. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=zZhX4eYNeEh.
  13. [13]Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory, pages 2137–2143. PMLR, 2020.
  14. [14]Francisco S Melo and M Isabel Ribeiro. Q-learning with linear function approximation. In International Conference on Computational Learning Theory, pages 308–322. Springer, 2007.DOI
  15. [15]Zak Mhammedi, Adam Block, Dylan J Foster, and Alexander Rakhlin. Efficient model-free exploration in low-rank MDPs. Advances in Neural Information Processing Systems, 36:66782–66817, 2023.arxiv.org/abs/2307.03997
  16. [16]Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstraction and provably efficient rich-observation reinforcement learning. In International conference on machine learning, pages 6961–6971. PMLR, 2020.
  17. [17]Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank MDPs. Journal of Machine Learning Research, 25(6):1–76, 2024.
  18. [18]Angelina Nedić and Asuman Ozdaglar. Subgradient methods for saddle-point problems. Journal of optimization theory and applications, 142:205–228, 2009.DOI
  19. [19]Masahiro Ono, Marco Pavone, Yoshiaki Kuwata, and J Balaram. Chance-constrained dynamic programming with application to risk-aware robotic space exploration. Autonomous Robots, 39:555–571, 2015.DOI
  20. [20]Santiago Paternain, Luiz Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained reinforcement learning has zero duality gap. Advances in Neural Information Processing Systems, 32, 2019.arxiv.org/abs/1910.13393
  21. [21]Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, New York, 1994.
  22. [22]Alex Ray, Joshua Achiam, and Dario Amodei. Benchmarking safe exploration in deep reinforcement learning, 2019. URL https://cdn.openai.com/safexp-short.pdf.
  23. [23]Tongzheng Ren, Tianjun Zhang, Csaba Szepesvári, and Bo Dai. A free lunch from the noise: Provable and practical exploration for representation learning. In Uncertainty in Artificial Intelligence, pages 1686–1696. PMLR, 2022.arxiv.org/abs/2111.11485
  24. [24]Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline RL in low-rank MDPs. arXiv preprint arXiv:2110.04652, 2021.arxiv.org/abs/2110.04652
  25. [25]Honghao Wei, Xin Liu, and Lei Ying. A provably-efficient model-free algorithm for constrained Markov decision processes. arXiv preprint arXiv:2106.01577, 2021.arxiv.org/abs/2106.01577
  26. [26]Honghao Wei, Arnob Ghosh, Ness Shroff, Lei Ying, and Xingyu Zhou. Provably efficient model-free algorithms for non-stationary CMDPs. In International Conference on Artificial Intelligence and Statistics, pages 6527–6570. PMLR, 2023.arxiv.org/abs/2303.05733
  27. [27]Tengyu Xu, Yingbin Liang, and Guanghui Lan. CRPO: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, pages 11480–11491. PMLR, 2021.arxiv.org/abs/2011.05869
  28. [28]Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin. Reinforcement learning in healthcare: A survey. ACM Computing Surveys (CSUR), 55(1):1–36, 2021.arxiv.org/abs/1908.08796
  29. [29]Xuezhou Zhang, Yuda Song, Masatoshi Uehara, Mengdi Wang, Alekh Agarwal, and Wen Sun. Efficient reinforcement learning in block MDPs: A model-free representation learning approach. In International Conference on Machine Learning, pages 26517–26547. PMLR, 2022.arxiv.org/abs/2202.00063

Paper details

vlnc:W_p752x3zd
Version
v2 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 13

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents