The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
Regret in the On-Line Decision Problem
Open accessAbstract
At each point in time a decision maker must make a decision. The payoff in a period from the decision made depends on the decision as well as on the state of the world that obtains at that time. The difficulty is that the decision must be made in advance of any knowledge, even probabilistic, about which state of the world will obtain. A range of problems from a variety of disciplines can be framed in this way. In this paper we survey the main results obtained, as well as some of their applications. Journal of Economic Literature Classification Numbers: C70, C73.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
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
(2015) · Adversarial Risk Analysis · doi:10.1201/b18653-3 · Cited by 3,632
Approximation Algorithms for NP-Hard Problems
(1997) · ACM SIGACT News · doi:10.1145/261342.571216 · Cited by 3,103
The Weighted Majority Algorithm
Littlestone, N., & Warmuth, M. K. (1994) · Information and Computation · doi:10.1006/inco.1994.1009 · Cited by 1,975
Contributions to the theory of games.
(1960) · Journal of the Franklin Institute · doi:10.1016/0016-0032(60)90366-5 · Cited by 1,824
A Simple Adaptive Procedure Leading to Correlated Equilibrium
Hart, S., & Mas-Colell, A. (2000) · Econometrica · doi:10.1111/1468-0262.00153 · Cited by 1,088
Cover, T. M. (1991) · Mathematical Finance · doi:10.1111/j.1467-9965.1991.tb00002.x · Cited by 898
Gambling in a rigged casino: The adversarial multi-armed bandit problem
Auer, P., Cesa-Bianchi, N., Freund, Y., & Schapire, R. E. (2002) · Proceedings of IEEE 36th Annual Foundations of Computer Science · doi:10.1109/sfcs.1995.492488 · Cited by 742
An analog of the minimax theorem for vector payoffs
Blackwell, D. (1956) · Pacific Journal of Mathematics · doi:10.2140/pjm.1956.6.1 · Cited by 740
Vovk, V. G. (1990) · Conference on Learning Theory · doi:10.5555/92571.92672 · Cited by 551
Cited by
Prediction, Learning, and Games
Cesa-Bianchi, N., & Lugosi, G. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546921 · Cited by 3,162
(2002) · doi:10.1137/s0097539701398375 · Cited by 2,275
Multiagent systems: algorithmic, game-theoretic, and logical foundations
(2009) · Choice Reviews Online · doi:10.5860/choice.46-5662 · Cited by 1,756
(2003) · Cited by 1,733
Foundations of Machine Learning
Mohri, M., Rostamizadeh, A., & Talwalkar, A. (2018) · doi:10.7551/mitpress/10290.001.0001 · Cited by 1,122
A Simple Adaptive Procedure Leading to Correlated Equilibrium
Hart, S., & Mas-Colell, A. (2000) · Econometrica · doi:10.1111/1468-0262.00153 · Cited by 1,088
Concentration of Measure for the Analysis of Randomized Algorithms
Dubhashi, D. P., & Panconesi, A. (2009) · Cambridge University Press eBooks · doi:10.1017/cbo9780511581274 · Cited by 945
Introduction to Multi-Armed Bandits
Slivkins, A. (2019) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000068 · Cited by 780
Opinion Dynamics and Learning in Social Networks
Acemoglu, D., & Ozdaglar, A. (2011) · Dynamic Games and Applications · doi:10.1007/s13235-010-0004-1 · Cited by 705
“These include fictitious play (e.g., [38, 78]) where individuals form beliefs about future play based on past patterns and regret-based update rules (e.g., [36, 37 , 56]), where individuals choose actions that perform well in the sense of minimizing regret, relative to the history of play.”
BackgroundEfficient algorithms for online decision problems
Kalai, A., & Vempala, S. (2005) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2004.10.016 · Cited by 591
Adaptive Game Playing Using Multiplicative Weights
Freund, Y., & Schapire, R. E. (1999) · Games and Economic Behavior · doi:10.1006/game.1999.0738 · Cited by 515
Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms
Besbes, O., & Zeevi, A. (2009) · Operations Research · doi:10.1287/opre.1080.0640 · Cited by 506
If multi-agent learning is the answer, what is the question?
Shoham, Y., Powers, R., & Grenager, T. (2007) · Artificial Intelligence · doi:10.1016/j.artint.2006.02.006 · Cited by 410
Young, H. P. (2009) · Games and Economic Behavior · doi:10.1016/j.geb.2008.02.011 · Cited by 286
Bault, N., Joffily, M., Rustichini, A., & Coricelli, G. (2011) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1100892108 · Cited by 162
Metadata
- Authors
- Foster, D. P., & Vohra, R.
- Venue
- Games and Economic Behavior
- Publisher
- Elsevier BV
- Published
- 1999-10
- Volume
- 29
- Issue
- 1-2
- Pages
- 7-35
- ISSN
- 0899-8256 (ISSN-L)
- OpenAlex
- W2135730283
- Cited by
- 302
- References
- 27
- FWCI
- 12.32
- Type
- journal article
- Language
- en
- Open access
- hybrid
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.