Adaptive game playing using multiplicative weights
type: Item
instance of: scholarly article
title: Adaptive game playing using multiplicative weights
zbMATH Open document ID: 0964.91007
author: Yoav Freund
author: Robert E. Schapire
published in: Games and Economic Behavior
publication date: 2000-02-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 91A10
Mathematics Subject Classification ID: 91A20
zbMATH DE Number: 1383772
zbMATH Keywords: repeated game
zbMATH Keywords: multiplicative weights algorithm
zbMATH Keywords: asymptotic optimality
reviewed by: K. Chandrasekhara Rao
MaRDI profile type: Publication
full work available at URL: game.1999.0738
OpenAlex ID: W2106887613
cites work: Fast probabilistic algorithms for Hamiltonian circuits and matchings
cites work: Q4252717
cites work: An analog of the minimax theorem for vector payoffs
cites work: Q5829371
cites work: How to use expert advice
cites work: Universal Portfolios
cites work: Universal portfolios with side information
cites work: Q4023085
cites work: Present Position and Potential Developments: Some Personal Views: Statistical Theory: The Prequential Approach
cites work: Universal prediction of individual sequences
cites work: Q5532825
cites work: Prediction in the worst case
cites work: A Randomization Rule for Selecting Forecasts
cites work: Asymptotic calibration
cites work: Regret in the on-line decision problem
cites work: Consistency and cautious fictitious play
cites work: A sublinear-time randomized approximation algorithm for matrix games
cites work: Q3245635
cites work: On‐Line Portfolio Selection Using Multiplicative Updates
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Q4263721
cites work: The weighted majority algorithm
cites work: Q5545175
cites work: Fast Approximation Algorithms for Fractional Packing and Covering Problems
cites work: Universal sequential coding of single messages
cites work: A game of prediction with expert advice
cites work: Q4886046
cites work: Coding theorems for individual sequences
DOI: 10.1006/GAME.1999.0738
description: scientific article; zbMATH DE number 1383772