Game theory, on-line prediction and boosting
Open accessAbstract
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 algorithm to an appropriate choice of game and that boosting is obtained by applying the same algorithm to the "dual" of this game.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
If the Learner's regret is bounded by ε_L and the Auditor's by ε_A, then the average plays of both players over time form an (ε_L+ε_A)-approximate minimax equilibrium of the game.
“Theorem 4.9 (Freund and Schapire [1996]) . Let D 1 ; D 2 ; : : : ; D T 2 H ( S ) be a sequence of distributions played by the Learner, and let 1 ; 2 ; : : : ; T 2 pure be the Auditor's sequence of approximate best responses against these distributions respectively. Let D = 1 T P T t =1 D t and = 1 T P T t =1 t be the two players' empirical distributions over their strategies. Suppose that the reg”
From Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness (2017) · cites this paper as Freund and Schapire [1996]
Section 2.4 bounds the learner’s average loss relative to the best fixed strategy. Sections 2.5–2.6 show that averaging the learner’s plays and an environment’s exact best responses yields approximate minmax and maxmin strategies. Our copy does not state the more general result with separate Learner and Auditor regret bounds of ε_L and ε_A, or their sum as the equilibrium error. (LLM, conf=0.84)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
A decision-theoretic generalization of on-line learning and an application to boosting
Freund, Y., & Schapire, R. E. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1504 · Cited by 20,466 · see citing works
Self-citationThe Strength of Weak Learnability
Schapire, R. E. (1990) · Machine Learning · doi:10.1007/bf00116037 · Cited by 4,600 · see citing works
Self-citationBoosting a Weak Learning Algorithm by Majority
Freund, Y. (1995) · Information and Computation · doi:10.1006/inco.1995.1136 · Cited by 1,674 · see citing works
Self-citation
Flagged first, then by citations
Research works printed but not linked: 6
- David Blackwell. An analog of the minimax theorem for vector payoffs. Paci$c Journal of Mathematics, 6(l): 1-8, Spring 1956.
- Nicolb Cesa-Bianchi, Yoav Freund, David P. Helmbold, David Haussler, Robert E. Schapire, and Manfred K. Warmuth. How to use expert advice. In Proceedings of the Twenty-Fifih AnnualACM Symposium on the Theory of Computing, pages 382-391, 1993.
- Thomas S. Ferguson. Mathematical Statistics: A Deci- sion Theoretic Approach. Academic Press, 1967.
- Dean P. Foster and Rakesh V. Vohra. A randomiza- tion rule for selecting forecasts. Operatioms Research, 41 (4):704-709, July-August 1993.
- Yoav Freund. Predicting a binary sequence almost as well as the optimal biased coin. In Proceedings of the Ninth Annual Conference on Computational Learning Theory, 1996.
- Second European Conference, EuroCOLT '95, pages 23-37. Springer-Verlag, 1995. A draft of the journal version is available electronically (on our web pages, or by email request).
Cited by
Sorted by citations
A decision-theoretic generalization of on-line learning and an application to boosting
Freund, Y., & Schapire, R. E. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1504 · Cited by 20,466 · see citing works
Self-citationBig data deep learning: Challenges and perspectives
Chen, X.-W., & Lin, X. (2014) · IEEE Access · doi:10.1109/access.2014.2325029 · Cited by 1,255 · see citing works
A Review on Fairness in Machine Learning
Pessach, D., & Shmueli, E. (2023) · ACM Computing Surveys · doi:10.1145/3494672 · Cited by 598 · see citing works
Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness
Kearns, M., Neel, S., Roth, A., & Wu, Z. S. (2017) · arXiv · doi:10.48550/arxiv.1711.05144 · Cited by 381 · see citing works
“By the result of Freund and Schapire [1996], the average plays of both players over time converge to an approximate equilibrium of the game, as long as the Learner has low regret.”
BackgroundThe Rhetoric and Reality of Anthropomorphism in Artificial Intelligence
Watson, D. (2019) · Minds and Machines · doi:10.1007/s11023-019-09506-6 · Cited by 148 · see citing works
On the Compatibility of Privacy and Fairness
Cummings, R., Gupta, V., Kimpara, D., & Morgenstern, J. (2019) · Adjunct Publication of the 27th Conference on User Modeling, Adaptation and Personalization · doi:10.1145/3314183.3323847 · Cited by 133 · see citing works
Performative Reinforcement Learning
Mandal, D., Triantafyllou, S., & Radanovic, G. (2022) · arXiv · doi:10.48550/arxiv.2207.00046
- Authors
- Freund, Y., & Schapire, R. E.
- Affiliations
- AT&T (United States) (US)
- Venue
- Proceedings of the ninth annual conference on Computational learning theory - COLT '96
- Publisher
- ACM Press
- Published
- 1996
- Pages
- 325-332
- OpenAlex
- W2097477220
- Cited by
- 383
- References
- 3
- Citations by year
- 2026: 3 · 2025: 10 · 2024: 12 · 2023: 15 · 2022: 12 · 2021: 15 · 2020: 18 · 2019: 23 · 2018: 14 · 2017: 9 · 2016: 3 · 2015: 15 · 2014: 15 · 2013: 16 · 2012: 13
- FWCI
- 18.28
- Type
- conference paper
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Conference on Learning Theory (publishedVersion)
- RePEc: Research Papers in Economics (submittedVersion)
- Topics
- Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
- Social Sciences › Decision Sciences › Management Science and Operations Research › Game Theory and Applications
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Keywords
- game theory, online prediction, boosting, repeated games, John von Neumann
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
