Timezone: »

 
Poster
Adaptive Concentration Inequalities for Sequential Decision Problems
Shengjia Zhao · Enze Zhou · Ashish Sabharwal · Stefano Ermon

Tue Dec 06 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #160
in Tuesday Posters »

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.

Keywords: (Other) Statistics · Learning Theory · Stochastic Methods · Active Learning

Author Information

Shengjia Zhao (Tsinghua University)
Enze Zhou (Tsinghua University)
Ashish Sabharwal (Allen Institute for AI)
Stefano Ermon (Stanford)

More from the Same Authors