Beyond the Best: Distribution Functional Estimation in Infinite-Armed Bandits
Authors: Yifei Wang, Tavor Baharav, Yanjun Han, Jiantao Jiao, David Tse
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We consider a general class of distribution functionals beyond the maximum, and propose unified meta algorithms for both the offline and online settings, achieving optimal sample complexities. We propose unified meta algorithms for both offline and online settings, and provide matching upper and lower bounds for the sample complexity of estimating the aforementioned functionals in Table 1. We additionally proved information theoretic lower bounds in these settings, which show that our algorithms are optimal up to εc where c is a fixed constant arbitrarily close to zero. |
| Researcher Affiliation | Academia | Yifei Wang Department of Electrical Engineering Stanford University Stanford, CA 94305 wangyf18@stanford.edu, Tavor Z. Baharav Department of Electrical Engineering Stanford University Stanford, CA 94305 tavorb@stanford.edu, Yanjun Han Institute for Data, Systems, and Society Massachusetts Institute of Technology Cambridge, MA 02142 yjhan@mit.edu, Jiantao Jiao Department of Electrical Engineering and Computer Sciences and Department of Statistics University of California, Berkeley Berkeley, CA 94720 jiantao@eecs.berkeley.edu, David Tse Department of Electrical Engineering Stanford University Stanford, CA 94305 dntse@stanford.edu |
| Pseudocode | Yes | Algorithm 1 Meta Algorithm |
| Open Source Code | No | The paper states '[N/A]' for 'Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)?' in its author checklist, and does not provide any links or explicit statements about open-source code. |
| Open Datasets | No | The paper is theoretical and focuses on algorithms and proofs for sample complexity, and does not mention the use of any datasets, public or otherwise. |
| Dataset Splits | No | The paper is theoretical and focuses on algorithms and proofs for sample complexity, and does not mention any training, validation, or test data splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware specifications used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not list any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not provide details about an experimental setup, hyperparameters, or system-level training settings. |