Weighted-majority algorithm

From Theory

Jump to: navigation, search

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

The setting is the repeated n-decision game.


The weighted majority algorithm is very simple. It is as follows: 

  Parameter: ε > 0
  On period t=1,2,\ldots,T:
  * Let P^t=p^1+p^2+\ldots+p^{t-1} be the total payoff vector.
  * Let x^t = \left(\frac{e^{\epsilon P^t_1}}{Z^t},\frac{e^{\epsilon P^t_2}}{Z^t},\ldots,\frac{e^{\epsilon P^t_n}}{Z^t}\right), where Z^t = \sum_{i=1}^n e^{\epsilon P^t_i}.
     // or simple update: x^t_i =x^{t-1}_i e^{\epsilon x^t_i}/\sum_{j=1}^n x^{t-1}_j e^{\epsilon x^t_j}.

Be sure to take a look at the Weighted majority theorem and its proof.

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