# Game theory, on-line prediction and boosting

@inproceedings{Freund1996GameTO, title={Game theory, on-line prediction and boosting}, author={Yoav Freund and Robert E. Schapire}, booktitle={COLT '96}, year={1996} }

We study the close connections between game theory, on-line prediction and boosting. After a brief review of game theory, we describe an algorithm for learning to play repeated games based on the on-line prediction methods of Littlestone and Warmuth. The analysis of this algorithm yields a simple proof of von Neumann’s famous minmax theorem, as well as a provable method of approximately solving a game. We then show that the on-line prediction model is obtained by applying this gameplaying… Expand

#### Topics from this paper

#### 393 Citations

An Experiment in Game-Based Classifier Selection

- 2008

We present a two-player game against nature for the study of classifier combination. The game is an extension of the prediction with expert advice framework developed by Cesa Bianchi et al.. In the… Expand

Ensembles and Multiple Classifiers: A Game-Theoretic View

- Computer Science
- MCS
- 2011

In repeated games, by examining the history of past opponent moves, the player acquires information about the opponent’s behavior and can adapt to it, in order to achieve a better payoff than that guaranteed by the minimax strategy. Expand

No-Regret Boosting

- Computer Science, Mathematics
- ICANNGA
- 2007

The "weighted majority" boosting algorithm is proved to belong to the class of H-boosting procedures, which are based on Hannan-consistent game playing strategies and tend to minimize the regret of a player. Expand

Interpretable preference learning: a game theoretic framework for large margin on-line feature and rule learning

- Computer Science, Mathematics
- AAAI
- 2019

In this work, game theory notions are injected into a preference learning framework and an algorithm is proposed to incrementally include new useful features into the hypothesis, leveraging on the natural analogy between features and rules. Expand

Adaptive game playing using multiplicative weights

- Mathematics
- 1999

Abstract We present a simple algorithm for playing a repeated game. We show that a player using this algorithm suffers average loss that is guaranteed to come close to the minimum loss achievable by… Expand

Game theory and optimization in boosting

- Computer Science
- 2011

This thesis identifies for the first time the minimum assumptions under which boosting the accuracy is possible in the multiclass setting, and designs boosting algorithms using these minimal assumptions, which work in more general situations than previous algorithms that assumed too much. Expand

Learning to Play Network Games

- Mathematics
- 1998

The idea of learning to play equilibrium strategies in repeated games is an active area of research in the game-theoretic community. Game theorists are primarily concerned with the equilibrium… Expand

Competing Against Equilibria in Zero-Sum Games with Evolving Payoffs

- Mathematics, Computer Science
- ArXiv
- 2019

An algorithm with small NE regret is designed--that is, it is ensured that the long-term payoff of both players is close to minimax optimum in hindsight, and achieves near-optimal dependence with respect to the number of rounds and depends poly-logarithmically on thenumber of available actions of the players. Expand

A decision-theoretic generalization of on-line learning and an application to boosting

- Computer Science
- EuroCOLT
- 1995

The model studied can be interpreted as a broad, abstract extension of the well-studied on-line prediction model to a general decision-theoretic setting, and the multiplicative weightupdate Littlestone Warmuth rule can be adapted to this model, yielding bounds that are slightly weaker in some cases, but applicable to a considerably more general class of learning problems. Expand

A Game-Theoretic Approach to Apprenticeship Learning

- Computer Science
- NIPS
- 2007

A new algorithm is given that is computationally faster, is easier to implement, and can be applied even in the absence of an expert, and it is shown that this algorithm may produce a policy that is substantially better than the expert's. Expand

#### References

SHOWING 1-10 OF 25 REFERENCES

A decision-theoretic generalization of on-line learning and an application to boosting

- Computer Science
- EuroCOLT
- 1995

The model studied can be interpreted as a broad, abstract extension of the well-studied on-line prediction model to a general decision-theoretic setting, and the multiplicative weightupdate Littlestone Warmuth rule can be adapted to this model, yielding bounds that are slightly weaker in some cases, but applicable to a considerably more general class of learning problems. Expand

A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting

- Computer Science, Mathematics
- COLT 1997
- 1997

The model studied can be interpreted as a broad, abstract extension of the well-studied on-line prediction model to a general decision-theoretic setting, and it is shown that the multiplicative weight-update Littlestone?Warmuth rule can be adapted to this model, yielding bounds that are slightly weaker in some cases, but applicable to a considerably more general class of learning problems. Expand

An analog of the minimax theorem for vector payoffs.

- Mathematics
- 1956

for all i, j . Thus in the (two-person, zero-sum) game with matrix Λf, player I has a strategy insuring an expected gain of at least v, and player II has a strategy insuring an expected loss of at… Expand

Consistency and Cautious Fictitious Play

- Economics
- 1995

We study a variation of fictitious play, in which the probability of each action is an exponential function of that action's utility against the historical frequency of opponents' play. Regardless of… Expand

The Weighted Majority Algorithm

- Computer Science, Mathematics
- Inf. Comput.
- 1994

A simple and effective method, based on weighted voting, is introduced for constructing a compound algorithm, which is robust in the presence of errors in the data, and is called the Weighted Majority Algorithm. Expand

How to use expert advice

- Mathematics, Computer Science
- STOC '93
- 1993

This work analyzes algorithms that predict a binary value by combining the predictions of several prediction strategies, called `experts', and shows how this leads to certain kinds of pattern recognition/learning algorithms with performance bounds that improve on the best results currently known in this context. Expand

Predicting a binary sequence almost as well as the optimal biased coin

- Mathematics, Computer Science
- COLT '96
- 1996

It is shown that for the case of the logarithmic loss, the derived algorithm is equivalent to the Bayes algorithm with Jeffreys prior, that was studied by Xie and Barron under probabilistic assumptions. Expand

Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm

- Mathematics
- 28th Annual Symposium on Foundations of Computer Science (sfcs 1987)
- 1987

Valiant (1984) and others have studied the problem of learning various classes of Boolean functions from examples. Here we discuss incremental learning of these functions. We consider a setting in… Expand

A Randomization Rule for Selecting Forecasts

- Mathematics, Computer Science
- Oper. Res.
- 1993

We propose a randomized strategy for selecting/combining forecasts that is better than the forecasts used to produce it in a sense made precise in this paper. Unlike traditional methods this approach… Expand