Statistical Inference
By Arnaud Autef - March 9, 2021
In our discussion this week, we review Daniel Russo's paper on Simple Bayesian Algorithms for Best Arm Identification. This paper presents very simple algorithms for sequential decision-making problems where the goal is to identify, as quickly as possible, the best variant out of possible designs.
Setup
Assumptions
Algorithms
Results
No algorithm can do better than exponential convergence
Top-two algorithms reach this exponential rate with a proper parameter
Top-two algorithms with an adaptive also attain this exponential rate
Top-two algorithms with a fixed converge exponentially, with a rate "not too far" from the optimal rate
Raw Notes
If you like applying these kinds of methods practical ML problems, join our team.