Pure Exploration with Feedback Graphs
This work addresses a gap in pure exploration for online learning with feedback graphs, which is incremental as it extends prior regret minimization studies to this setting.
The paper tackles the problem of pure exploration in online learning with feedback graphs, deriving an instance-specific lower bound on sample complexity for finding the best action with fixed confidence, even with unknown stochastic graphs, and presents an asymptotically optimal algorithm, TaS-FG, that demonstrates efficiency across various graph configurations.
We study the sample complexity of pure exploration in an online learning problem with a feedback graph. This graph dictates the feedback available to the learner, covering scenarios between full-information, pure bandit feedback, and settings with no feedback on the chosen action. While variants of this problem have been investigated for regret minimization, no prior work has addressed the pure exploration setting, which is the focus of our study. We derive an instance-specific lower bound on the sample complexity of learning the best action with fixed confidence, even when the feedback graph is unknown and stochastic, and present unidentifiability results for Bernoulli rewards. Additionally, our findings reveal how the sample complexity scales with key graph-dependent quantities. Lastly, we introduce TaS-FG (Track and Stop for Feedback Graphs), an asymptotically optimal algorithm, and demonstrate its efficiency across different graph configurations.