Timezone: »

 
Poster
Robust Pure Exploration in Linear Bandits with Limited Budget
Ayya Alieva · Ashok Cutkosky · Abhimanyu Das

Wed Jul 21 09:00 PM -- 11:00 PM (PDT) @
in Poster Session 4 »

We consider the pure exploration problem in the fixed-budget linear bandit setting. We provide a new algorithm that identifies the best arm with high probability while being robust to unknown levels of observation noise as well as to moderate levels of misspecification in the linear model. Our technique combines prior approaches to pure exploration in the multi-armed bandit problem with optimal experimental design algorithms to obtain both problem dependent and problem independent bounds. Our success probability is never worse than that of an algorithm that ignores the linear structure, but seamlessly takes advantage of such structure when possible. Furthermore, we only need the number of samples to scale with the dimension of the problem rather than the number of arms. We complement our theoretical results with empirical validation.

Keywords: Bandits · Unsupervised Learning · Algorithms · Adversarial Learning · Reinforcement Learning and Planning

Author Information

Ayya Alieva (Stanford University)
Ashok Cutkosky (Boston University)
Abhimanyu Das (Google)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors