Adaptive Concentration Inequalities for Sequential Decision Problems
Authors: Shengjia Zhao, Enze Zhou, Ashish Sabharwal, Stefano Ermon
NeurIPS 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We introduce Hoeffding-like concentration inequalities that hold for a random, adaptively chosen number of samples. Our inequalities are tight under natural assumptions and can greatly simplify the analysis of common sequential decision problems. In particular, we apply them to sequential hypothesis testing, best arm identification, and sorting. The resulting algorithms rival or exceed the state of the art both theoretically and empirically. |
| Researcher Affiliation | Collaboration | Shengjia Zhao Tsinghua University zhaosj12@stanford.edu Enze Zhou Tsinghua University zhouez_thu_12@126.com Ashish Sabharwal Allen Institute for AI Ashish S@allenai.org Stefano Ermon Stanford University ermon@cs.stanford.edu |
| Pseudocode | Yes | Algorithm 1 Adaptive Hoeffding Race (set of arms A, K = |A|, parameter δ) |
| Open Source Code | No | The paper does not provide an explicit statement or link for open-source code for the described methodology. |
| Open Datasets | No | The paper describes using synthetic data from a "Bernoulli distribution over {-1/2, 1/2}" and "Gaussian with 1/4 variance" but does not refer to a publicly available or open dataset with access information. |
| Dataset Splits | No | The paper does not specify explicit training, validation, or test dataset splits. It mentions experiments are "averaged across 100 independent runs" on generated data. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used to run the experiments. |
| Software Dependencies | No | The paper does not provide specific version numbers for any software dependencies used in the experiments. |
| Experiment Setup | Yes | The confidence level δ is set to 0.05, and the results are averaged across 100 independent runs. For this experiment and other experiments in this section, we set the parameters a = 0.6 and c = 1.1. |