Yahel David

PAC Lower Bounds and Efficient Algorithms for The Max K-Armed Bandit Problem

We consider the Max K-Armed Bandit problem, where a learning agent is faced with several stochastic arms, each a source of i.i.d. rewards of unknown distribution. At each time step the agent chooses an arm, and observes the reward of the obtained sample. Each sample is considered here as a separate…