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..
Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems
Authors: Utkarsh Chavan, Prashant Trivedi, Nandyala Hemachandra
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main contribution is the first regret lower bound for this setting based on the construction of hard-to-learn instances for any number of agents, n. Our regret lower bound of Ω( K), over K episodes, highlights the inherent learning difficulty in Dec-MASSPs. These insights clarify the learning complexity of decentralized control and can further guide the design of efficient learning algorithms in multi-agent systems. |
| Researcher Affiliation | Academia | Utkarsh U. Chavan Department of Mechanical Engineering Indian Institute of Technology Bombay Mumbai India 400076 EMAIL Prashant Trivedi Computer Science and Information Systems BITS Pilani, Pilani Campus Rajasthan 333031 EMAIL Nandyala Hemachandra Industrial Engineering and Operations Research Indian Institute of Technology Bombay Mumbai India 400076 EMAIL |
| Pseudocode | No | The paper defines a general Dec-MARL algorithm in Section 2.2 as "Algorithm. Analogous to [10, 15], we define a general (possibly randomized) Dec-MARL algorithm as a sequence of deterministic functions π = {πt} t=1, where at each time step t, the algorithm specifies a policy πt = (πt 1, . . . , πt n)." However, this is a definition of a general class of algorithms, not a specific pseudocode or algorithm block for the methodology proposed in this paper, which focuses on theoretical lower bounds. |
| 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: The paper does not include experiments requiring code. |
| Open Datasets | 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: The paper does not include experiments requiring code. |
| 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: The experimental results are not provided, since we are providing the regret lower bounds, that require a construction of hard-to-learn instance. |
| 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: The paper does not include experiments. |
| Software Dependencies | No | Question: Does the paper provide SPECIFIC ANCILLARY SOFTWARE DETAILS (e.g., library or solver names with version numbers like Python 3.8, CPLEX 12.4) needed to replicate the experiment? Answer: [NA] Justification: Our work is theoretical, and hence there are no computational 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: Our work is theoretical, and hence there are no computational experiments. |