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

CREATORMax Buckley 0* Konstantinos Papathanasiou 0* Andreas Spanopoulos 0* Google ETH Zurich ETH Zurich [email protected] [email protected] [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE108 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-06751

Browse the full library · About the Tower of Babel