Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916647951925248 |
|---|---|
| author | Buckley, Max Papathanasiou, Konstantinos Spanopoulos, Andreas |
| author_facet | Buckley, Max Papathanasiou, Konstantinos Spanopoulos, Andreas |
| contents | This paper addresses the challenge of solving Constrained Markov Decision Processes (CMDPs) with $d > 1$ constraints when the transition dynamics are unknown, but samples can be drawn from a generative model. We propose a model-based algorithm for infinite horizon CMDPs with multiple constraints in the tabular setting, aiming to derive and prove sample complexity bounds for learning near-optimal policies. Our approach tackles both the relaxed and strict feasibility settings, where relaxed feasibility allows some constraint violations, and strict feasibility requires adherence to all constraints. The main contributions include the development of the algorithm and the derivation of sample complexity bounds for both settings. For the relaxed feasibility setting we show that our algorithm requires $\tilde{\mathcal{O}} \left( \frac{d |\mathcal{S}| |\mathcal{A}| \log(1/δ)}{(1-γ)^3ε^2} \right)$ samples to return $ε$-optimal policy, while in the strict feasibility setting it requires $\tilde{\mathcal{O}} \left( \frac{d^3 |\mathcal{S}| |\mathcal{A}| \log(1/δ)}{(1-γ)^5ε^2{ζ_{\mathbf{c}}^*}^2} \right)$ samples. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_06751 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints Buckley, Max Papathanasiou, Konstantinos Spanopoulos, Andreas Machine Learning 68T05, 68T05 F.2.2; I.2.6; G.1.6 This paper addresses the challenge of solving Constrained Markov Decision Processes (CMDPs) with $d > 1$ constraints when the transition dynamics are unknown, but samples can be drawn from a generative model. We propose a model-based algorithm for infinite horizon CMDPs with multiple constraints in the tabular setting, aiming to derive and prove sample complexity bounds for learning near-optimal policies. Our approach tackles both the relaxed and strict feasibility settings, where relaxed feasibility allows some constraint violations, and strict feasibility requires adherence to all constraints. The main contributions include the development of the algorithm and the derivation of sample complexity bounds for both settings. For the relaxed feasibility setting we show that our algorithm requires $\tilde{\mathcal{O}} \left( \frac{d |\mathcal{S}| |\mathcal{A}| \log(1/δ)}{(1-γ)^3ε^2} \right)$ samples to return $ε$-optimal policy, while in the strict feasibility setting it requires $\tilde{\mathcal{O}} \left( \frac{d^3 |\mathcal{S}| |\mathcal{A}| \log(1/δ)}{(1-γ)^5ε^2{ζ_{\mathbf{c}}^*}^2} \right)$ samples. |
| title | Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints |
| topic | Machine Learning 68T05, 68T05 F.2.2; I.2.6; G.1.6 |
| url | https://arxiv.org/abs/2503.06751 |