Adaptive game playing using multiplicative weights (Q1818286)

This paper is devoted to the algorithm MW (Multiplicative Weights). The main theorem concerning this algorithm is the following: Theorem. For any matrix \(M\) with \(n\) rows and entries in \([0,1]\), and for any sequence of mixed strategies \(Q_1,\dots, Q_T\) play by the environment, the sequence of mixed strategies \(P_1,\dots, P_T\) produced by the algorithm MW satisfies \[ \sum_{t=1}^T M(P_t,Q_t)\leq \min_P \Biggl[ a_\beta \sum_{t=1}^T M(P,Q_t)+ c_\beta RE(P\parallel P_1)\Biggr], \] where \(a_\beta= \frac{\ln(1/\beta)} {1-\beta}\) and \(c_\beta= \frac{1}{1-\beta}\). The authors show how this algorithm can be used to give a simple proof of von Neumann's min-max theorem. A possible application of the algorithm to solve linear programming problems is also noted. A version of the algorithm whose distributions are guaranteed to converge to an optimal mixed strategy is also given. The authors show that the convergence rate of the second version of the algorithm is asymptotically optimal.