2016
NIPS
NeurIPS 2016
Adaptive Concentration Inequalities for Sequential Decision Problems
Abstract
A key challenge in sequential decision problems is to determine how many samples are needed for an agent to make reliable decisions with good probabilistic guarantees. 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.
🌉
Interdisciplinary Bridge
— Machine Learning and Mathematics & Optimization
📈
Trend Setter
— Exploration-Exploitation
🐣
Hot Topic Early Bird
— sequential decision making
🐝
Cross-Pollinator
— Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics, Security & Privacy, Speech & Audio
Authors
Topics
Machine Learning > Optimization & Theory > Learning Theory
Machine Learning > Optimization & Theory > Stochastic Processes
Mathematics & Optimization > Optimization > Online Algorithms
Mathematics & Optimization > Probability > Stochastic Processes
Machine Learning > Learning Types > Exploration-Exploitation
Machine Learning > Optimization & Theory > Sample Complexity