Decentralized Learning for Multiplayer Multiarmed Bandits
The DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
Abstract
We consider the problem of distributed online learning with multiple players in multiarmed bandit (MAB) models. Each player can pick among multiple arms. When a player picks an arm, it gets a reward. We consider both independent identically distributed (i.i.d.) reward model and Markovian reward model. In the i.i.d. model, each arm is modeled as an i.i.d. process with an unknown distribution with an unknown mean. In the Markovian model, each arm is modeled as a finite, irreducible, aperiodic and reversible Markov chain with an unknown probability transition matrix and stationary distribution. The arms give different rewards to different players. If two players pick the same arm, there is a collision, and neither of them get any reward. There is no dedicated control channel for coordination or communication among the players. Any other communication between the users is costly and will add to the regret. We propose an online index-based distributed learning policy called dUCB4 algorithm that trades off exploration versus exploitation in the right way, and achieves expected regret that grows at most as near- O(log2T). The motivation comes from opportunistic spectrum access by multiple secondary users in cognitive radio networks wherein they must pick among various wireless channels that look different to different users. This is the first distributed learning algorithm for multiplayer MABs with heterogeneous players (that have player-dependent rewards) to the best of our knowledge.
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
Concentration Inequalities: A Nonasymptotic Theory of Independence
Boucheron, S., Lugosi, G., & Massart, P. (2013) · doi:10.1093/acprof:oso/9780199535255.001.0001 · Cited by 1,768 · cited 1×
“Fact 1: Chernoff-Hoeffding inequality [19] Let X 1 , . . . , X t be random variables with a common range such that E X t | X 1 , . . . [ Then for all a ≥ 0, , X t − 1 ] = µ .”
Background
Cited by
Learning Based Content Caching and Sharing for Wireless Networks
Song, J., Sheng, M., Quek, T. Q. S., Xu, C., & Wang, X. (2017) · IEEE Transactions on Communications · doi:10.1109/tcomm.2017.2713384 · Cited by 144
Low-Latency Federated Learning Over Wireless Channels With Differential Privacy
Wei, K., Li, J., Ma, C., Ding, M., Chen, C., Jin, S., Han, Z., & Poor, H. V. (2022) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2021.3126052 · Cited by 109
Metadata
- Authors
- Kalathil, D., Nayyar, N., & Jain, R.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2014-04
- Volume
- 60
- Issue
- 4
- Pages
- 2331-2345
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2061641373
- Cited by
- 158
- References
- 2
- FWCI
- 12.32
- 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.