Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Near-Optimal Sample Complexity for Online Constrained MDPs
Authors: Chang Liu, Yunfan Li, Lin F. Yang
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | For relaxed feasibility, we prove that our algorithm returns an ε-optimal policy with ε-bounded violation with arbitrarily high probability, requiring e O SAH3 ε2 learning episodes, matching the lower bound for unconstrained MDPs. For strict feasibility, we prove that our algorithm returns an ε-optimal policy with zero violation with arbitrarily high probability, requiring e O SAH5 ε2ζ2 learning episodes, where ζ is the problem-dependent Slater constant characterizing the size of the feasible region. This result matches the lower bound for learning CMDPs with access to a generative model. |
| Researcher Affiliation | Academia | Chang Liu University of California, Los Angeles EMAIL Yunfan Li University of California, Los Angeles EMAIL Lin F. Yang University of California, Los Angeles EMAIL |
| Pseudocode | Yes | Algorithm 1: Model-based algorithm for online CMDP |
| Open Source Code | No | Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: This paper does not include experiments. |
| Open Datasets | No | Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [NA] Justification: This paper does not include experiments. |
| Dataset Splits | No | Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [NA] Justification: This paper does not include experiments. |
| Hardware Specification | No | Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [NA] Justification: This paper does not include experiments. |
| Software Dependencies | No | Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [NA] Justification: This paper does not include experiments. |
| Experiment Setup | No | Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [NA] Justification: This paper does not include experiments. |