{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,3]],"date-time":"2026-09-03T15:54:32Z","timestamp":1788450872979,"version":"build-2803163510"},"reference-count":44,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T00:00:00Z","timestamp":1738108800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CNS 2214940"],"award-info":[{"award-number":["CNS 2214940"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CPS 2128378"],"award-info":[{"award-number":["CPS 2128378"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CNS 2107014"],"award-info":[{"award-number":["CNS 2107014"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CNS 2150152"],"award-info":[{"award-number":["CNS 2150152"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Network"],"abstract":"<jats:p>Sequential decision-making in dynamic and interconnected environments is a cornerstone of numerous applications, ranging from communication networks and finance to distributed blockchain systems and IoT frameworks. The multi-armed bandit (MAB) problem is a fundamental model in this domain that traditionally assumes independent and identically distributed (iid) rewards, which limits its effectiveness in capturing the inherent dependencies and state dynamics present in some real-world scenarios. In this paper, we lay a theoretical framework for a modified MAB model in which each arm\u2019s reward is generated by a hidden Markov process. In our model, each arm undergoes Markov state transitions independent of play in a way that results in varying reward distributions and heightened uncertainty in reward observations. The number of states for each arm can be up to three states. A key challenge arises from the fact that the underlying states governing each arm\u2019s rewards remain hidden at the time of selection. To address this, we adapt traditional index-based policies and develop a modified index approach tailored to accommodate Markovian transitions and enhance selection efficiency for our model. Our proposed proposed Markovian Upper Confidence Bound (MC-UCB) policy achieves logarithmic regret. Comparative analysis with the classical UCB algorithm reveals that MC-UCB consistently achieves approximately a 15% reduction in cumulative regret. This work provides significant theoretical insights and lays a robust foundation for future research aimed at optimizing decision-making processes in complex, networked systems with hidden state dependencies.<\/jats:p>","DOI":"10.3390\/network5010003","type":"journal-article","created":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T03:26:10Z","timestamp":1738121170000},"page":"3","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Modified Index Policies for Multi-Armed Bandits with Network-like Markovian Dependencies"],"prefix":"10.3390","volume":"5","author":[{"given":"Abdalaziz","family":"Sawwan","sequence":"first","affiliation":[{"name":"Department of Computer and Information Science, Temple University, Philadelphia, PA 19122, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jie","family":"Wu","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science, Temple University, Philadelphia, PA 19122, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2025,1,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"994","DOI":"10.1109\/TMLCN.2024.3421170","article-title":"Fair Probabilistic Multi-Armed Bandit with Applications to Network Optimization","volume":"2","author":"Guo","year":"2024","journal-title":"IEEE Trans. Mach. Learn. Commun. Netw."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/s10614-021-10119-4","article-title":"Reinforcement learning in economics and finance","volume":"62","author":"Charpentier","year":"2021","journal-title":"Comput. Econ."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"3025","DOI":"10.1109\/TAC.2023.3247982","article-title":"Distributed Multiarmed Bandits","volume":"68","author":"Zhu","year":"2023","journal-title":"IEEE Trans. Autom. Control"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Sawwan, A., and Wu, J. (2024, January 17). A Combinatorial Multi-Armed Bandit Approach for Stochastic Facility Allocation Problem. Proceedings of the 2024 Workshop on Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating algorithms for Distributed systems, Nantes, France.","DOI":"10.1145\/3663338.3663677"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Xu, Z., Zhang, Z., Wang, S., Hu, X., Jia, Y., and Ren, B. (2024). Energy-Constrained Distributed MAC in CR-IoT Networks: A Budgeted Multi-Player Multi-Armed Bandit Approach. IEEE Trans. Cogn. Commun. Netw.","DOI":"10.1109\/TCCN.2024.3510559"},{"key":"ref_6","first-page":"6343","article-title":"Combination of auction theory and multi-armed bandits: Model, algorithm, and application","volume":"22","author":"Gao","year":"2022","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"133472","DOI":"10.1109\/ACCESS.2021.3114430","article-title":"Multi-armed bandits for spectrum allocation in multi-agent channel bonding WLANs","volume":"9","author":"Chiumento","year":"2021","journal-title":"IEEE Access"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Tariq, Z.U.A., Baccour, E., Erbad, A., Guizani, M., and Hamdi, M. (2022, January 17\u201318). Network intrusion detection for smart infrastructure using multi-armed bandit based reinforcement learning in adversarial environment. Proceedings of the 2022 International Conference on Cyber Warfare and Security (ICCWS), Albany, NY, USA.","DOI":"10.1109\/ICCWS56285.2022.9998440"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1090\/S0002-9904-1952-09620-8","article-title":"Some aspects of the sequential design of experiments","volume":"58","author":"Robbins","year":"1952","journal-title":"Bull. Amer. Math. Soc."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1016\/0196-8858(85)90002-8","article-title":"Asymptotically efficient adaptive allocation rules","volume":"6","author":"Lai","year":"1985","journal-title":"Adv. Appl. Math."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Ou, H.C., Siebenbrunner, C., Killian, J., Brooks, M.B., Kempe, D., Vorobeychik, Y., and Tambe, M. (2022). Networked restless multi-armed bandits for mobile interventions. arXiv.","DOI":"10.21203\/rs.3.rs-2061577\/v1"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1137\/S0097539701398375","article-title":"The nonstochastic multiarmed bandit problem","volume":"32","author":"Auer","year":"2002","journal-title":"SIAM J. Comput."},{"key":"ref_13","unstructured":"Jiang, B., Jiang, B., Li, J., Lin, T., Wang, X., and Zhou, C. (2023, January 23\u201329). Online restless bandits with unobserved states. Proceedings of the International Conference on Machine Learning, Honolulu, HI, USA."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Sawwan, A., and Wu, J. (2023, January 17\u201320). A new framework: Short-term and long-term returns in stochastic multi-armed bandit. Proceedings of the IEEE INFOCOM 2023-IEEE Conference on Computer Communications, New York, NY, USA.","DOI":"10.1109\/INFOCOM53939.2023.10228899"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Tekin, C., and Liu, M. (October, January 29). Online algorithms for the multi-armed bandit problem with markovian rewards. Proceedings of the 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA.","DOI":"10.1109\/ALLERTON.2010.5707118"},{"key":"ref_16","unstructured":"Sawwan, A., and Wu, J. (2024, January 2\u20134). Budget-Constrained and Deadline-Driven Multi-Armed Bandits with Delays. Proceedings of the 21st Annual IEEE International Conference on Sensing, Communication, and Networking (SECON), Phoenix, AZ, USA."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/s11134-022-09737-y","article-title":"On the Whittle index of Markov modulated restless bandits","volume":"102","author":"Duran","year":"2022","journal-title":"Queueing Syst."},{"key":"ref_18","first-page":"15616","article-title":"Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints","volume":"38","author":"Wang","year":"2024","journal-title":"Proc. Aaai Conf. Artif. Intell."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"732","DOI":"10.26599\/TST.2024.9010053","article-title":"Diversity-based recruitment in crowdsensing by combinatorial multi-armed bandits","volume":"30","author":"Sawwan","year":"2024","journal-title":"Tsinghua Sci. Technol."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"5029","DOI":"10.1109\/TAC.2020.3043431","article-title":"Learning in restless multiarmed bandits via adaptive arm sequencing rules","volume":"66","author":"Gafni","year":"2020","journal-title":"IEEE Trans. Autom. Control."},{"key":"ref_21","unstructured":"Zhao, Q. (2022). Multi-Armed Bandits: Theory and Applications to Online Learning in Networks, Springer Nature."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Bouneffouf, D., Rish, I., and Aggarwal, C. (2020, January 19\u201324). Survey on applications of multi-armed and contextual bandits. Proceedings of the 2020 IEEE Congress on Evolutionary Computation (CEC), Glasgow, UK.","DOI":"10.1109\/CEC48606.2020.9185782"},{"key":"ref_23","unstructured":"Burtini, G., Loeppky, J., and Lawrence, R. (2015). A survey of online experiment design with the stochastic multi-armed bandit. arXiv."},{"key":"ref_24","unstructured":"Mazumdar, E., Dong, R., Royo, V.R., Tomlin, C., and Sastry, S.S. (2017). A multi-armed bandit approach for online expert selection in markov decision processes. arXiv."},{"key":"ref_25","unstructured":"Denisov, D., and Walton, N. (2020). Regret analysis of a markov policy gradient algorithm for multi-arm bandits. arXiv."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Bout, E., Brighente, A., Conti, M., and Loscri, V. (2022, January 23\u201326). Folpetti: A novel multi-armed bandit smart attack for wireless networks. Proceedings of the 17th International Conference on Availability, Reliability and Security, Vienna, Austria.","DOI":"10.1145\/3538969.3539001"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"119160","DOI":"10.1016\/j.eswa.2022.119160","article-title":"A reinforcement learning model for the reliability of blockchain oracles","volume":"214","author":"Taghavi","year":"2023","journal-title":"Expert Syst. Appl."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1356","DOI":"10.1109\/TCCN.2024.3366908","article-title":"Multi-Agent Multi-Armed Bandit Learning for Grant-Free Access in Ultra-Dense IoT Networks","volume":"10","author":"Raza","year":"2024","journal-title":"IEEE Trans. Cogn. Commun. Netw."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"968","DOI":"10.1109\/TAC.1987.1104491","article-title":"Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-part IId rewards","volume":"32","author":"Anantharam","year":"1987","journal-title":"IEEE Trans. Autom. Control"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1111\/j.2517-6161.1979.tb01068.x","article-title":"Bandit processes and dynamic allocation indices","volume":"41","author":"Gittins","year":"1979","journal-title":"J. R. Stat. Soc. Ser. Stat. Methodol."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.2307\/1427934","article-title":"Sample mean based index policies by o (log n) regret for the multi-armed bandit problem","volume":"27","author":"Agrawal","year":"1995","journal-title":"Adv. Appl. Probab."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1023\/A:1013689704352","article-title":"Finite-time analysis of the multiarmed bandit problem","volume":"47","author":"Auer","year":"2002","journal-title":"Mach. Learn."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Garivier, A., and Moulines, E. (2011). On upper-confidence bound policies for switching bandit problems. International Conference on Algorithmic Learning Theory, Springer.","DOI":"10.1007\/978-3-642-24412-4_16"},{"key":"ref_34","first-page":"1","article-title":"Stochastic multi-armed-bandit problem with non-stationary rewards","volume":"27","author":"Besbes","year":"2014","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"4385","DOI":"10.1109\/TSP.2021.3093261","article-title":"Multi-player multi-armed bandits with collision-dependent reward distributions","volume":"69","author":"Shi","year":"2021","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Mohamed, E.M., Hashima, S., Aldosary, A., Hatano, K., and Abdelghany, M.A. (2020). Gateway selection in millimeter wave UAV wireless networks using multi-player multi-armed bandit. Sensors, 20.","DOI":"10.3390\/s20143947"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"103283","DOI":"10.1016\/j.adhoc.2023.103283","article-title":"Massive multi-player multi-armed bandits for IoT networks: An application on LoRa networks","volume":"151","author":"Dakdouk","year":"2023","journal-title":"Ad Hoc Netw."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Ortner, R. (2007, January 1\u20134). Pseudometrics for state aggregation in average reward Markov decision processes. Proceedings of the Algorithmic Learning Theory: 18th International Conference, Sendai, Japan. Proceedings 18.","DOI":"10.1007\/978-3-540-75225-7_30"},{"key":"ref_39","unstructured":"Raj, V., and Kalyani, S. (2017). Taming non-stationary bandits: A Bayesian approach. arXiv."},{"key":"ref_40","first-page":"11997","article-title":"Networked restless bandits with positive externalities","volume":"37","author":"Herlihy","year":"2023","journal-title":"AAAI Conf. Artif. Intell."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"5547","DOI":"10.1109\/TIT.2010.2068950","article-title":"Indexability of restless bandit problems and optimality of whittle index for dynamic multichannel access","volume":"56","author":"Liu","year":"2010","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"101919","DOI":"10.1016\/j.sysarc.2020.101919","article-title":"Distributed learning dynamics of multi-armed bandits for edge intelligence","volume":"114","author":"Chen","year":"2021","journal-title":"J. Syst. Archit."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1203","DOI":"10.1137\/S0097539794268765","article-title":"A Chernoff bound for random walks on expander graphs","volume":"27","author":"Gillman","year":"1998","journal-title":"SIAM J. Comput."},{"key":"ref_44","unstructured":"Sheikh, C. (2025, January 15). Upper Confidence Bound Dataset. Available online: https:\/\/www.kaggle.com\/datasets\/chaandsheikh\/upper-confidence-bound-dataset."}],"container-title":["Network"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2673-8732\/5\/1\/3\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T10:38:04Z","timestamp":1759919884000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2673-8732\/5\/1\/3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,29]]},"references-count":44,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,3]]}},"alternative-id":["network5010003"],"URL":"https:\/\/doi.org\/10.3390\/network5010003","relation":{},"ISSN":["2673-8732"],"issn-type":[{"value":"2673-8732","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,29]]}}}