The DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
Distributed Learning in Multi-Armed Bandit With Multiple Players
Open accessAbstract
We formulate and study a decentralized multi-armed bandit (MAB) problem. There are M distributed players competing for N independent arms. Each arm, when played, offers i.i.d. reward according to a distribution with an unknown parameter. At each time, each player chooses one arm to play without exchanging observations or any information with other players. Players choosing the same arm collide, and, depending on the collision model, either no one receives reward or the colliding players share the reward in an arbitrary way. We show that the minimum system regret of the decentralized MAB grows with time at the same logarithmic order as in the centralized counterpart where players act collectively as a single entity by exchanging observations and making decisions jointly. A decentralized policy is constructed to achieve this optimal order while ensuring fairness among players and without assuming any pre-agreement or information exchange among players. Based on a time-division fair sharing (TDFS) of the M best arms, the proposed policy is constructed and its order optimality is proven under a general reward model. Furthermore, the basic structure of the TDFS policy can be used with any order-optimal single-player policy to achieve order optimality in the decentralized setting. We also establish a lower bound on the system regret for a general class of decentralized polices, to which the proposed policy belongs. This problem finds potential applications in cognitive radio networks, multi-channel communication systems, multi-agent systems, web search and advertising, and social networks.
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
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
A Survey of Dynamic Spectrum Access
Zhao, Q., & Sadler, B. M. (2007) · IEEE Signal Processing Magazine · doi:10.1109/msp.2007.361604 · Cited by 2,698
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
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
Anantharam, V., Varaiya, P., & Walrand, J. (1987) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1987.1104491 · Cited by 358
Distributed Algorithms for Learning and Cognitive Medium Access with Logarithmic Regret
Anandkumar, A., Michael, N., Tang, A. K., & Swami, A. (2011) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2011.110406 · Cited by 242
Gai, Y., Krishnamachari, B., & Jain, R. (2010) · 2010 IEEE Symposium on New Frontiers in Dynamic Spectrum (DySPAN) · doi:10.1109/dyspan.2010.5457857 · Cited by 224
Opportunistic Spectrum Access with Multiple Users: Learning under Competition
Anandkumar, A., Michael, N., & Tang, A. (2010) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2010.5462144 · Cited by 168
The Robustness of Lognormal-Based Estimators of Abundance
Myers, R. A., & Pepin, P. (1990) · Biometrics · doi:10.2307/2532460 · Cited by 99
Decentralized multi-armed bandit with multiple distributed players
Liu, K., & Zhao, Q. Q. (2010) · Information Theory and Applications Workshop (ITA) · doi:10.1109/ita.2010.5454071 · Cited by 52
Self-citationProbability: The Science of Uncertainty with Applications to Investments, Insurance, and Engineering
Bean, M. A. (2000) · Cited by 28
Cited by
Spectrum Sensing for Cognitive Radio : State-of-the-Art and Recent Advances
Axell, E., Leus, G., Larsson, E. G., & Poor, H. V. (2012) · IEEE Signal Processing Magazine · doi:10.1109/msp.2012.2183771 · Cited by 1,116
Spectrum Sensing for Cognitive Radio
Haykin, S., Thomson, D. J., & Reed, J. H. (2009) · Proceedings of the IEEE · doi:10.1109/jproc.2009.2015711 · Cited by 812
Introduction to Multi-Armed Bandits
Slivkins, A. (2019) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000068 · Cited by 780
Gai, Y., Krishnamachari, B., & Jain, R. (2012) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2011.2181864 · Cited by 413
Multi-Armed Bandit-Based Client Scheduling for Federated Learning
Xia, W., Quek, T. Q. S., Guo, K., Wen, W., Yang, H. H., & Zhu, H. (2020) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2020.3008091 · Cited by 313
Metadata
- Authors
- Liu, K., & Zhao, Q.
- Venue
- IEEE Transactions on Signal Processing
- Published
- 2010-11
- Volume
- 58
- Issue
- 11
- Pages
- 5667-5681
- ISSN
- 1053-587X (ISSN-L)
- 1941-0476
- OpenAlex
- W2140571193
- Cited by
- 385
- References
- 11
- FWCI
- 38.37
- Type
- journal article
- Language
- en
- Open access
- green
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.