Bandits with an Edge

Details Bandits with an Edge Bandits with an Edge

2011-09-11

arxiv.org/abs/1109.2296v1

Computer Science

Learning

Scientific paper

We consider a bandit problem over a graph where the rewards are not directly observed. Instead, the decision maker can compare two nodes and receive (stochastic) information pertaining to the difference in their value. The graph structure describes the set of possible comparisons. Consequently, comparing between two nodes that are relatively far requires estimating the difference between every pair of nodes on the path between them. We analyze this problem from the perspective of sample complexity: How many queries are needed to find an approximately optimal node with probability more than $1-\delta$ in the PAC setup? We show that the topology of the graph plays a crucial in defining the sample complexity: graphs with a low diameter have a much better sample complexity.

Affiliated with

Also associated with

No associations

Rating

Bandits with an Edge 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 Bandits with an Edge, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bandits with an Edge will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-19998