Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints
Max Buckley 0* Konstantinos Papathanasiou 0* Andreas Spanopoulos 0* Google ETH Zurich ETH Zurich [email protected] [email protected] [email protected] · 2025
Read Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints by Max Buckley 0* Konstantinos Papathanasiou 0* Andreas Spanopoulos 0* Google ETH Zurich ETH Zurich [email protected] [email protected] [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-06751.txt.
Description
Max Buckley, Konstantinos Papathanasiou, and Andreas Spanopoulos bound how many samples a safe learning agent needs when it faces several limits at once, in a 2025 paper. Such agents learn by trial in a Markov decision process whose dynamics are unknown, drawing samples from a simulator. The team gives a model based algorithm and proves its sample needs in two regimes.
When small limit breaches are allowed, the needed samples grow gently with the number of constraints. When every limit must hold strictly, the cost rises steeply and leans on a slack measure. The bounds cover endless horizon tasks in the table based setting.
Catalog record
| CREATOR | Max Buckley 0* Konstantinos Papathanasiou 0* Andreas Spanopoulos 0* Google ETH Zurich ETH Zurich [email protected] [email protected] [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 108 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-06751