Computer Science – Data Structures and Algorithms
Scientific paper
2009-07-23
Computer Science
Data Structures and Algorithms
Scientific paper
In a multi-armed bandit (MAB) problem, an online algorithm makes a sequence of choices. In each round it chooses from a time-invariant set of alternatives and receives the payoff associated with this alternative. While the case of small strategy sets is by now well-understood, a lot of recent work has focused on MAB problems with exponentially or infinitely large strategy sets, where one needs to assume extra structure in order to make the problem tractable. In particular, recent literature considered information on similarity between arms. We consider similarity information in the setting of "contextual bandits", a natural extension of the basic MAB problem where before each round an algorithm is given the "context" -- a hint about the payoffs in this round. Contextual bandits are directly motivated by placing advertisements on webpages, one of the crucial problems in sponsored search. A particularly simple way to represent similarity information in the contextual bandit setting is via a "similarity distance" between the context-arm pairs which gives an upper bound on the difference between the respective expected payoffs. Prior work on contextual bandits with similarity uses "uniform" partitions of the similarity space, which is potentially wasteful. We design more efficient algorithms that are based on adaptive partitions adjusted to "popular" context and "high-payoff" arms.
No associations
LandOfFree
Contextual Bandits with Similarity Information does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Contextual Bandits with Similarity Information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Contextual Bandits with Similarity Information will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-354511