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 [1].
Navigating to the Best Policy in Markov Decision Processes
Authors: Aymen Al Marjani, Aurélien Garivier, Alexandre Proutiere
NeurIPS 2021 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We propose a problem-dependent lower bound on the average number of steps required before a correct answer can be given with probability at least 1 δ. We further provide the first algorithm with an instance-specific sample complexity in this setting. Our contributions. [MP21] recently proposed an information-theoretical complexity analysis for MDPs in the case of access to a generative model. Here we extend their results to the online setting. Our main goal is to understand how the online learning scheme affects the sample complexity compared to the easier case where we have a generative model. Section 5 contains our main results along with a sketch of the analysis. |
| Researcher Affiliation | Academia | Aymen Al Marjani UMPA, ENS Lyon Lyon, France EMAIL Aurélien Garivier UMPA, CNRS, INRIA, ENS Lyon Lyon, France EMAIL Alexandre Proutiere EECS and Digital Futures KTH Royal Institute of Technology, Sweden EMAIL |
| Pseudocode | Yes | Algorithm 1: MDP Navigate and Stop (MDP-Na S) |
| Open Source Code | No | The paper does not provide any statement or link indicating the release of open-source code for the described methodology. |
| Open Datasets | No | The paper is a theoretical work focusing on algorithm design, sample complexity analysis, and lower bounds for MDPs. It does not conduct empirical studies on a dataset, thus no dataset information is provided. |
| Dataset Splits | No | The paper is a theoretical work and does not describe experiments that would involve training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is a theoretical work and does not describe empirical experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers used for implementation or experimentation. |
| Experiment Setup | No | The paper describes an algorithm (MDP-Na S) and its theoretical components, including mathematical formulations for parameters like εt and δ. However, it does not detail a specific experimental setup with hyperparameters for an empirical evaluation, as it is a theoretical work. |