BL-WoLF: A Framework For Loss-Bounded Learnability In Zero-Sum Games

Details BL-WoLF: A Framework For Loss-Bounded Learnability In Zero-Sum Games BL-WoLF: A Framework For Loss-Bounded Learnability In Zero-Sum Games

2003-07-03

arxiv.org/abs/cs/0307006v1

In Proceedings of the 20th International Conference on Machine Learning (ICML-03), Washington, DC, USA, 2003

Computer Science

Computer Science and Game Theory

Scientific paper

We present BL-WoLF, a framework for learnability in repeated zero-sum games where the cost of learning is measured by the losses the learning agent accrues (rather than the number of rounds). The game is adversarially chosen from some family that the learner knows. The opponent knows the game and the learner's learning strategy. The learner tries to either not accrue losses, or to quickly learn about the game so as to avoid future losses (this is consistent with the Win or Learn Fast (WoLF) principle; BL stands for ``bounded loss''). Our framework allows for both probabilistic and approximate learning. The resultant notion of {\em BL-WoLF}-learnability can be applied to any class of games, and allows us to measure the inherent disadvantage to a player that does not know which game in the class it is in. We present {\em guaranteed BL-WoLF-learnability} results for families of games with deterministic payoffs and families of games with stochastic payoffs. We demonstrate that these families are {\em guaranteed approximately BL-WoLF-learnable} with lower cost. We then demonstrate families of games (both stochastic and deterministic) that are not guaranteed BL-WoLF-learnable. We show that those families, nevertheless, are {\em BL-WoLF-learnable}. To prove these results, we use a key lemma which we derive.

Affiliated with

Also associated with

No associations

Rating

BL-WoLF: A Framework For Loss-Bounded Learnability In Zero-Sum Games 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 BL-WoLF: A Framework For Loss-Bounded Learnability In Zero-Sum Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and BL-WoLF: A Framework For Loss-Bounded Learnability In Zero-Sum Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-654844