Gradient Ascent for Active Exploration in Bandit Problems

About

We present a new algorithm based on an gradient ascent for a general Active Exploration bandit problem in the fixed confidence setting. This problem encompasses several well studied problems such that the Best Arm Identification or Thresholding Bandits. It consists of a new sampling rule based on an online lazy mirror ascent. We prove that this algorithm is asymptotically optimal and, most importantly, computationally efficient.

Pierre Ménard · 2019

Related benchmarks

Task	Dataset	Result
Multi-fidelity ranking-and-selection	Synthetic Instance 2	Expected Stopping Cost17215	6
Multi-fidelity ranking-and-selection	Synthetic Instance 1	Expected Stopping Cost77602	6
Multi-fidelity ranking-and-selection	Synthetic Instance 3	Expected Stopping Cost8938	6
Multi-fidelity ranking-and-selection	Synthetic Instance 4	Expected Stopping Cost28922	6