Skyline Identification in Multi-Armed Bandits

Albert Cheu, Ravi Sundaram, Jonathan Ullman

We introduce a variant of the classical PAC multi-armed bandit problem. There is an ordered set of $n$ arms $A[1],\dots ,A[n]$, each with some stochastic reward drawn from some unkn…