Weighted majority theorem

From Theory

Jump to: navigation, search

Notes for CS 8803 - Game Theory and Computer Science. Spring 2008

Recall that n is the number of possible decisions in the repeated n-decision game.

Theorem. For any n,T\geq 1, M \geq 0, and for any p^1,p^2,\ldots,p^t \in [-M,M]^n, the weighted-majority algorithm run with \epsilon=\frac{1}{2M}\sqrt{\frac{\log(n)}{T}} achieves,
\mathrm{regret} \leq 4M\sqrt{\frac{\log(n)}{T}}.

See the proof of the weighted majority theorem.

The production of this material was supported in part by NSF award SES-0734780.

Retrieved from "http://wiki.cc.gatech.edu/theory/index.php/Weighted_majority_theorem"
Personal tools