The Epoch-Greedy Algorithm for Multi-armed Bandits with Side Information
We present Epoch-Greedy, an algorithm for multi-armed bandits with observable 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. The regret scales as $O(T^{2/3} S^{1/3})$ or better (sometimes, much better). Here $S$ is the complexity term in a sample complexity bound for standard supervised learning.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Armed BanditsSimilar Papers 제목 키워드 기반
Multi-Armed Bandits for Correlated Markovian Environments with Smoothed Reward Feedback
We study a multi-armed bandit problem in a dynamic environment where arm rewards evolve in a correlated fashion according to a Markov chain. Different than much of the work on related problems, in our formulation a learn…
Multi-Armed BanditsQ-LearningOn the Robustness of Epoch-Greedy in Multi-Agent Contextual Bandit Mechanisms
Efficient learning in multi-armed bandit mechanisms such as pay-per-click (PPC) auctions typically involves three challenges: 1) inducing truthful bidding behavior (incentives), 2) using personalization in the users (con…
Adapting multi-armed bandits policies to contextual bandits scenarios
This work explores adaptations of successful multi-armed bandits policies to the online contextual bandits scenario with binary rewards using binary classification algorithms such as logistic regression as black-box orac…
Binary ClassificationClassificationGeneral ClassificationMulti-Armed Bandits+2Budgeted Combinatorial Multi-Armed Bandits
We consider a budgeted combinatorial multi-armed bandit setting where, in every round, the algorithm selects a super-arm consisting of one or more arms. The goal is to minimize the total expected regret after all rounds …
Multi-Armed BanditsUnreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms
We study the structure of regret-minimizing policies in the {\em many-armed} Bayesian multi-armed bandit problem: in particular, with $k$ the number of arms and $T$ the time horizon, we consider the case where $k \geq \s…
Multi-Armed Bandits