The Epoch-Greedy Algorithm for Multi-armed Bandits with Side Information

Epoch-Greedy has the following properties: No knowledge of a time horizon $T$ is necessary. The regret incurred by Epoch-Greedy is controlled by a sample complexity bound for a hypothesis class. Here $S$ is the complexity term in a sample complexity bound for standard supervised learning. Papers published at the Neural Information Processing Systems Conference.