The DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
Combinatorial Network Optimization With Unknown Variables: Multi-Armed Bandits With Linear Rewards and Individual Observations
Abstract
We formulate the following combinatorial multi-armed bandit (MAB) problem: There areNrandom variables with unknown mean that are each instantiated in an i.i.d. fashion over time. At each time multiple random variables can be selected, subject to an arbitrary constraint on weights associated with the selected variables. All of the selected individual random variables are observed at that time, and a linearly weighted combination of these selected variables is yielded as the reward. The goal is to find a policy that minimizes regret, defined as the difference between the reward obtained by a genie that knows the mean of each random variable, and that obtained by the given policy. This formulation is broadly applicable and useful for stochastic online versions of many interesting tasks in networks that can be formulated as tractable combinatorial optimization problems with linear objective functions, such as maximum weighted matching, shortest path, and minimum spanning tree computations. Prior work on multi-armed bandits with multiple plays cannot be applied to this formulation because of the general nature of the constraint. On the other hand, the mapping of all feasible combinations to arms allows for the use of prior work on MAB with single-play, but results in regret, storage, and computation growing exponentially in the number of unknown variables. We present new efficient policies for this problem that are shown to achieve regret that grows logarithmically with time, and polynomially in the number of unknown variables. Furthermore, these policies only require storage that grows linearly in the number of unknown parameters. For problems where the underlying deterministic problem is tractable, these policies further require only polynomial computation. For computationally intractable problems, we also present results on a different notion of regret that is suitable when a polynomial-time approximation algorithm is used.
Overview
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
Verification
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.
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 note on two problems in connexion with graphs
Dijkstra, E. W. (1959) · Numerische Mathematik · doi:10.1007/bf01386390 · Cited by 24,043
The Hungarian method for the assignment problem
Kuhn, H. W. (1955) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800020109 · Cited by 13,120
Network Flows: Theory, Algorithms, and Applications.
Smith, D. K., Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1994) · The Journal of the Operational Research Society · doi:10.2307/2583863 · Cited by 8,034
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
On the shortest spanning subtree of a graph and the traveling salesman problem
Kruskal, J. B. (1956) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1956-0078686-7 · Cited by 5,088
Shortest Connection Networks And Some Generalizations
Prim, R. C. (1957) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1957.tb01515.x · Cited by 4,565
Bellman, R. (1958) · Quarterly of Applied Mathematics · doi:10.1090/qam/102435 · Cited by 2,758
Edmonds, J. (1965) · Canadian Journal of Mathematics · doi:10.4153/cjm-1965-045-4 · Cited by 2,428
Asymptotically 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
Convergence of Stochastic Processes.
Robinson, P. M., & Pollard, D. (1985) · Economica · doi:10.2307/2553898 · Cited by 2,184
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (2011) · Cited by 2,083
Edmonds, J. (2009) · Classic Papers in Combinatorics · doi:10.1007/978-0-8176-4842-8_26 · Cited by 1,517
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
(2006) · Algorithms and Combinatorics 21 · doi:10.1007/3-540-29297-7 · Cited by 1,156
On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem
Kruskal, J. B. (1956) · Proceedings of the American Mathematical Society · doi:10.2307/2033241 · Cited by 1,117
Combinatorial optimization: Theory and algorithms
(2001) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(01)90023-9 · Cited by 600
(2008) · ScholarlyCommons (University of Pennsylvania) · Cited by 581
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
Linearly Parameterized Bandits
Rusmevichientong, P., & Tsitsiklis, J. N. (2010) · Mathematics of Operations Research · doi:10.1287/moor.1100.0446 · Cited by 427
Distributed Learning in Multi-Armed Bandit With Multiple Players
Liu, K., & Zhao, Q. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2010.2062509 · Cited by 385
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
Self-citationAdaptive routing with end-to-end feedback: distributed learning and geometric approaches
Awerbuch, B., & Kleinberg, R. D. (2004) · Proceedings of the thirty-sixth annual ACM symposium on Theory of computing · doi:10.1145/1007352.1007367 · Cited by 190
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
An adaptive algorithm for selecting profitable keywords for search-based advertising services
Rusmevichientong, P., & Williamson, D. P. (2006) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/1134707.1134736 · Cited by 145
Anantharam, V., Varaiya, P., & Walrand, J. C. (1987) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1987.1104485 · Cited by 111
Online learning in opportunistic spectrum access: A restless bandit approach
Tekin, C., & Liu, M. (2011) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2011.5935068 · Cited by 97
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
Decentralized Online Learning Algorithms for Opportunistic Spectrum Access
Gai, Y., & Krishnamachari, B. (2011) · Globecom · doi:10.1109/glocom.2011.6134253 · Cited by 76
Self-citationThe non-Bayesian restless multi-armed bandit: A case of near-logarithmic regret
Dai, W., Gai, Y., Krishnamachari, B., & Zhao, Q. Q. (2011) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2011.5946273 · Cited by 50
Self-citationLogarithmic weak regret of non-Bayesian restless multi-armed bandit
Liu, H., Liu, K., & Zhao, Q. Q. (2011) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2011.5946895 · Cited by 37
Cited by
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401 · Cited by 976
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
Efficient Prompt Optimization Through the Lens of Best Arm Identification
Shi, C., Yang, K., Chen, Z., Li, J., Yang, J., & Shen, C. (2024) · Advances in Neural Information Processing Systems 37 · doi:10.52202/079017-3161 · Cited by 3
Metadata
- Authors
- Gai, Y., Krishnamachari, B., & Jain, R.
- Venue
- IEEE/ACM Transactions on Networking
- Published
- 2012-10
- Volume
- 20
- Issue
- 5
- Pages
- 1466-1478
- ISSN
- 1063-6692 (ISSN-L)
- 1558-2566
- OpenAlex
- W2093562354
- Cited by
- 413
- References
- 32
- FWCI
- 25.47
- 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.