Navigating to the Best Policy in Markov Decision Processes
Authors: Aymen Al Marjani, Aurélien Garivier, Alexandre Proutiere
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | 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 aymen.al_marjani@ens-lyon.fr Aurélien Garivier UMPA, CNRS, INRIA, ENS Lyon Lyon, France aurelien.garivier@ens-lyon.fr Alexandre Proutiere EECS and Digital Futures KTH Royal Institute of Technology, Sweden alepro@kth.se |
| 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. |