BL-WoLF: A Framework For Loss-Bounded Learnability In Zero-Sum Games
  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.
