The DOI matches its Crossref record; 39 of the 39 references it cites were found in a registry or an index.
Linearly Parameterized Bandits
Abstract
We consider bandit problems involving a large (possibly infinite) collection of arms, in which the expected reward of each arm is a linear function of an r-dimensional random vector Z ∈ ℝ r, where r ≥ 2. The objective is to minimize the cumulative regret and Bayes risk. When the set of arms corresponds to the unit sphere, we prove that the regret and Bayes risk is of order Θ(r √T), by establishing a lower bound for an arbitrary policy, and showing that a matching upper bound is obtained through a policy that alternates between exploration and exploitation phases. The phase-based policy is also shown to be effective if the set of arms satisfies a strong convexity condition. For the case of a general set of arms, we describe a near-optimal policy whose regret and Bayes risk admit upper bounds of the form O(r √T log 3/2 T).
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
(1995) · Cited by 10,558
A Stochastic Approximation Method
Robbins, H., & Monro, S. (1951) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729586 · Cited by 9,643
Finite-time Analysis of the Multiarmed Bandit Problem
Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002) · Machine Learning · doi:10.1023/a:1013689704352 · Cited by 6,033
(2012) · Encyclopedia of the Sciences of Learning · doi:10.1007/978-1-4419-1428-6_5086 · Cited by 3,515
THOMPSON, W. R. (1933) · Biometrika · doi:10.1093/biomet/25.3-4.285 · Cited by 2,712
Introduction to linear optimization
Bertsimas, D., & Tsitsiklis, J. N. (1997) · Cited by 2,705
Self-citationAsymptotically efficient adaptive allocation rules
Lai, T. L., & Robbins, H. (1985) · Advances in Applied Mathematics · doi:10.1016/0196-8858(85)90002-8 · Cited by 2,406
Some aspects of the sequential design of experiments
Robbins, H. (1952) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1952-09620-8 · Cited by 2,184
Stochastic Estimation of the Maximum of a Regression Function
Kiefer, J., & Wolfowitz, J. (1952) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729392 · Cited by 2,133
Neuro-Dynamic Programming: NDP
Bertsekas, D. P. (2001) · Encyclopedia of Optimization · doi:10.1007/0-306-48332-7_333 · Cited by 1,466
Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix
Sherman, J., & Morrison, W. J. (1950) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729893 · Cited by 1,402 · cited 1×
“It follows from Equation (4) and the Sherman-Morrison Formula (see Sherman and Morrison, 1950) that Ct = ( H+Nu(z, t)uu′ )−1 = H−1 − N u(z, t)H−1uu′H−1 1 +Nu(z, t)u′H−1u , which implies that ‖u‖2 Ct = u′Ctu = u ′H−1u− N u(z, t) ( u′H−1u )2 1 +Nu(z, t)u′H−1u = u′H−1u 1 +Nu(z, t)u′H−1u ≤ 1 Nu(z, t)…”
Using confidence bounds for exploitation-exploration trade-offs
Auer, P. L. (2003) · Journal of Machine Learning Research · doi:10.5555/944919.944941 · Cited by 1,229
Bhatia, R. (2009) · Princeton University Press eBooks · doi:10.1515/9781400827787 · Cited by 1,027
Uniform Central Limit Theorems
Dudley, R. M. (1999) · Cambridge University Press eBooks · doi:10.1017/cbo9780511665622 · Cited by 785
Berry, D. A., & Fristedt, B. (1985) · Springer eBooks · doi:10.1007/978-94-015-3711-7 · Cited by 633
(2008) · ScholarlyCommons (University of Pennsylvania) · Cited by 581
Bandit Problems, Sequential Allocation of Experiments.
Jones, P. W., Berry, D. A., & Fristedt, B. (1987) · The Journal of the Operational Research Society · doi:10.2307/2582852 · Cited by 566
Online convex optimization in the bandit setting: gradient descent without a gradient
Flaxman, A. D., Kalai, A. T., & McMahan, H. B. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0408007 · Cited by 546
Sample mean based index policies by O(log n) regret for the multi-armed bandit problem
Agrawal, R. (1995) · Advances in Applied Probability · doi:10.2307/1427934 · Cited by 540
Multidimensional Stochastic Approximation Methods
Blum, J. R. (1954) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177728659 · Cited by 523
Dynamic Programming and Optimal Control. Volume 1: Dynamic Programming and Optimal Control. Volume 2
Smith, D. K. (1996) · Journal of the Operational Research Society · doi:10.1057/jors.1996.103 · Cited by 448
Multi-armed bandits in metric spaces
Kleinberg, R., Slivkins, A., & Upfal, E. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374475 · Cited by 396
Nearly Tight Bounds for the Continuum-Armed Bandit Problem
Kleinberg, R. (2004) · Cited by 294
Adaptive Treatment Allocation and the Multi-Armed Bandit Problem
Lai, T. L. (1987) · The Annals of Statistics · doi:10.1214/aos/1176350495 · Cited by 279
Improved Rates for the Stochastic Continuum-Armed Bandit Problem
Auer, P. L., Ortner, R., & Szepesvári, C. (2007) · Springer eBooks · doi:10.1007/978-3-540-72927-3_33 · Cited by 178
Online linear optimization and adaptive routing
Awerbuch, B., & Kleinberg, R. (2007) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2007.04.016 · Cited by 177
Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary
McMahan, H. B., & Blum, A. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-27819-1_8 · Cited by 172
Multi-armed bandit problems with dependent arms
Pandey, S., Chakrabarti, D., & Agarwal, D. (2007) · Proceedings of the 24th international conference on Machine learning · doi:10.1145/1273496.1273587 · Cited by 161
Algorithms for Infinitely Many-Armed Bandits
Wang, Y., Audibert, J.-Y., & Munos, R. (2008) · Cited by 160
Bandit problems with side observations
Wang, C.-C., Kulkarni, S. R., & Poor, H. V. (2005) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2005.844079 · Cited by 154
Online Optimization in X-Armed Bandits
Bubeck, S., Stoltz, G., Szepesvári, C., & Munos, R. (2008) · Cited by 132
Contributions to the "Two-Armed Bandit" Problem
Feldman, D. (1962) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177704454 · Cited by 128
Stochastic approximation: invited paper
Lai, T. L. (2003) · The Annals of Statistics · doi:10.1214/aos/1051027873 · Cited by 128
A Structured Multiarmed Bandit Problem and the Greedy Policy
Mersereau, A. J., Rusmevichientong, P., & Tsitsiklis, J. N. (2009) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2009.2031725 · Cited by 92
Self-citationBroadie, M. N., Cicek, D. M., & Zeevi, A. J. (2011) · Operations Research · doi:10.1287/opre.1110.0970 · Cited by 84
Robbing the bandit: less regret in online geometric optimization against an adaptive adversary
Dani, V., & Hayes, T. P. (2006) · doi:10.5555/1109557.1109660 · Cited by 66
Associative Reinforcement Learning using Linear Probabilistic Concepts
Abe, N., & Long, P. M. (1999) · Cited by 60
Woodroofe’s one-armed bandit problem revisited
Goldenshluger, A., & Zeevi, A. J. (2009) · The Annals of Applied Probability · doi:10.1214/08-aap589 · Cited by 48
Arbitrary side observations in bandit problems
Wang, C.-C., Kulkarni, S. R., & Poor, H. V. (2005) · Advances in Applied Mathematics · doi:10.1016/j.aam.2004.10.004 · Cited by 28
Cited by
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
Bubeck, S. (2012) · now publishers, Inc. eBooks · doi:10.1561/9781601986276 · Cited by 1,404
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401 · Cited by 976
Introduction to Multi-Armed Bandits
Slivkins, A. (2019) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000068 · Cited by 780
Online learning: A comprehensive survey
Hoi, S. C. H., Sahoo, D., Lu, J., & Zhao, P. (2021) · Neurocomputing · doi:10.1016/j.neucom.2021.04.112 · Cited by 746
Learning to Optimize via Posterior Sampling
Russo, D., & Van Roy, B. (2014) · Mathematics of Operations Research · doi:10.1287/moor.2014.0650 · Cited by 493
Metadata
- Authors
- Rusmevichientong, P., & Tsitsiklis, J. N.
- Venue
- Mathematics of Operations Research
- Published
- 2010-05
- Volume
- 35
- Issue
- 2
- Pages
- 395-411
- ISSN
- 0364-765X (ISSN-L)
- 1526-5471
- OpenAlex
- W2061753713
- Cited by
- 427
- References
- 39
- FWCI
- 22.67
- Type
- journal article
- Language
- en
- Open access
- closed
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.