Scalable Reinforcement Learning for Multiagent Networked Systems

References

• Agarwal A, Kakade SM, Lee JD, Mahajan G (2021) On the theory of policy gradient methods: Optimality, approximation, and distribution shift. J. Machine Learn. Res. 22(98):1–76.Google Scholar
• Ahn HJ (2014) Random propagation in complex systems: Nonlinear matrix recursions and epidemic spread. PhD thesis, California Institute of Technology, Pasadena.Google Scholar
• Azizan Ruhi N, Ahn HJ, Hassibi B (2016a) Analysis of exact and approximated epidemic models over complex networks. Preprint, submitted September 30, https://arxiv.org/abs/1609.09565.Google Scholar
• Azizan Ruhi N, Thrampoulidis C, Hassibi B (2016b) Improved bounds on the epidemic threshold of exact SIS models on complex networks. Proc. 55th IEEE Conf. on Decision and Control (IEEE, New York), 3560–3565.Google Scholar
• Bamieh B, Paganini F, Dahleh MA (2002) Distributed control of spatially invariant systems. IEEE Trans. Automated Control 47(7):1091–1107.Crossref, Google Scholar
• Bertsekas DP (2005) Dynamic Programming and Optimal Control. Athena Scientific Optimization and Computation Series, 3rd ed. (Athena Scientific, Belmont, MA).Google Scholar
• Bertsekas DP, Tsitsiklis JN (1996) Neuro-Dynamic Programming, vol. 5 (Athena Scientific, Belmont, MA).Google Scholar
• Bhandari J, Russo D (2019) Global optimality guarantees for policy gradient methods. Preprint, submitted June 5, 2019, updated October 29, 2020, https://arxiv.org/abs/1906.01786.Google Scholar
• Block R, Van Houdt B (2016) Spatial fairness in multi-channel CSMA line networks. Performance Evaluation 103:69–85.Crossref, Google Scholar
• Blondel VD, Tsitsiklis JN (2000) A survey of computational complexity results in systems and control. Automatica J. IFAC 36(9):1249–1274.Crossref, Google Scholar
• Britton T (2010) Stochastic epidemic models: A survey. Math. Biosci. 225(1):24–35.Crossref, Google Scholar
• Busoniu L, Babuska R, De Schutter B (2008) A comprehensive survey of multiagent reinforcement learning. IEEE Trans. Systems Man Cybernetics C 38(2):156–172.Crossref, Google Scholar
• Chakrabarti D, Wang Y, Wang C, Leskovec J, Faloutsos C (2008) Epidemic thresholds in real networks. ACM Trans. Inform. Systems Security. 10(4):1.Crossref, Google Scholar
• Claus C, Boutilier C (1998) The dynamics of reinforcement learning in cooperative multiagent systems. AAAI Conf. Artificial Intelligence, Madison, WI (AAAI, Palo Alto, CA), 746–752. https://www.aaai.org/Library/AAAI/aaai98contents.php.Google Scholar
• Duan Y, Chen X, Houthooft R, Schulman J, Abbeel P (2016) Benchmarking deep reinforcement learning for continuous control. Balcan MF, Weinberger KQ, eds. Proc. Internat. Conf. on Machine Learn. (PMLR, New York), 1329–1338. http://proceedings.mlr.press/v48/.Google Scholar
• Gamarnik D (2013) Correlation decay method for decision, optimization, and inference in large-scale networks. Theory Driven by Influential Applications (INFORMS), 108–121. https://pubsonline.informs.org/doi/abs/10.1287/educ.2013.0119.Link, Google Scholar
• Gamarnik D, Goldberg DA, Weber T (2014) Correlation decay in random decision networks. Math. Oper. Res. 39(2):229–261.Link, Google Scholar
• Guestrin C, Koller D, Parr R, Venkataraman S (2003) Efficient solution algorithms for factored MDPs. J. Artificial Intelligence Res. 19:399–468.Crossref, Google Scholar
• Hu J, Wellman MP (2003) Nash Q-learning for general-sum stochastic games. J. Machine Learn. Res. 4(11):1039–1069.Google Scholar
• Jin C, Allen-Zhu Z, Bubeck S, Jordan MI (2018) Is Q-learning provably efficient? Proc. 32nd Internat. Conf. on Neural Information Processing Systems, 4868–4878. https://dl.acm.org/doi/proceedings/10.5555/3326943.Google Scholar
• Kar S, Moura JM, Poor HV (2013) QD-learning: A collaborative distributed strategy for multi-agent reinforcement learning through consensus + innovations. IEEE Trans. Signal Processing 61(7):1848–1862.Crossref, Google Scholar
• Kearns M, Koller D (1999) Efficient reinforcement learning in factored MDPs. Proc. 16th Internat. Joint Conf. Artificial Intelligence (IJCAI’99), vol. 2 (Morgan Kaufmann Publishers Inc., San Francisco), 740–747. https://dl.acm.org/doi/abs/10.5555/1624312.1624325.Google Scholar
• Kim TH, Ni J, Srikant R, Vaidya NH (2011) On the achievable throughput of CSMA under imperfect carrier sensing. 2011. Proc. IEEE INFOCOM (IEEE, New York), 1674–1682.Google Scholar
• Konda VR, Tsitsiklis JN (2000) Actor-critic algorithms. Proc. 12th Internat. Conf. Neural Inform. Processing Systems (NIPS’99) (MIT Press, Cambridge, MA), 1008–1014.Google Scholar
• Kuznetsov YA, Piccardi C (1994) Bifurcation analysis of periodic SEIR and SIR epidemic models. J. Math. Biology 32(2):109–121.Crossref, Google Scholar
• Li D, Zhao D, Zhang Q, Chen Y (2019) Reinforcement learning and deep learning based lateral control for autonomous driving. IEEE Comput. Intelligence Magazine 14(2):83–98.Crossref, Google Scholar
• Li G, Wei Y, Chi Y, Gu Y, Chen Y (2020) Sample complexity of asynchronous q-learning: Sharper analysis and variance reduction. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Advances in Neural Information Processing Systems, vol. 33 (Curran Associates, Inc.), 7031–7043. https://proceedings.neurips.cc/paper/2020/file/4eab60e55fe4c7dd567a0be28016bff3-Paper.pdf.Google Scholar
• Lin Y, Qu G, Huang L, Wierman A (2021) Multi-agent reinforcement learning in stochastic networked systems. Adv. Neural Inform. Processing Systems. https://proceedings.neurips.cc/paper/2021/hash/412604be30f701b1b1e3124c252065e6-Abstract.html.Google Scholar
• Littman ML (1994) Markov games as a framework for multi-agent reinforcement learning. Proc. Machine Learn. (Elsevier, New York), 157–163.Crossref, Google Scholar
• Littman ML (2001) Value-function reinforcement learning in Markov games. Cognitive Systems Res. 2(1):55–66.Crossref, Google Scholar
• Llas M, Gleiser PM, López JM, Díaz-Guilera A (2003) Nonequilibrium phase transition in a model for the propagation of innovations among economic agents. Phys. Rev. E 68(6):066101.Crossref, Google Scholar
• Lokhov AY, Mézard M, Zdeborová L (2015) Dynamic message-passing equations for models with unidirectional dynamics. Phys. Rev. E 91:012811.Crossref, Google Scholar
• Lowe R, Wu Y, Tamar A, Harb J, Abbeel OP, Mordatch I (2017) Multi-agent actor-critic for mixed cooperative-competitive environments. Guyon I, Luxburg UV, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 30 (Curran Associates, Inc.), 6379–6390. https://proceedings.neurips.cc/paper/2017/file/68a9750337a418a86fe06c1991a1d64c-Paper.pdf.Google Scholar
• Macua SV, Chen J, Zazo S, Sayed AH (2015) Distributed policy evaluation under multiple behavior strategies. IEEE Trans. Automated Control 60(5):1260–1274.Crossref, Google Scholar
• Magnússon S, Shokri-Ghadikolaei H, Li N (2020) On maintaining linear convergence of distributed learning and optimization under limited communication. IEEE Trans. Signal Process ing 68:6101–6116.Crossref, Google Scholar
• Mathkar A, Borkar VS (2017) Distributed reinforcement learning via gossip. IEEE Trans. Automated Control 62(3):1465–1470.Crossref, Google Scholar
• Matignon L, Laurent GJ, Le Fort-Piat N (2012) Independent reinforcement learners in cooperative Markov games: A survey regarding coordination problems. Knowledge Engrg. Rev. 27(1):1–31.Crossref, Google Scholar
• Mei W, Mohagheghi S, Zampieri S, Bullo F (2017) On the dynamics of deterministic epidemic propagation over networks. Annu. Rev. Control 44:116–128.Crossref, Google Scholar
• Meuleau N, Hauskrecht M, Kim KE, Peshkin L, Kaelbling LP, Dean TL, Boutilier C (1998) Solving very large weakly coupled Markov decision processes. (AAAI, Palo Alto, CA), 165–172.Google Scholar
• Mezard M, Montanari A (2009) Information, Physics, and Computation (Oxford University Press, Oxford, UK).Crossref, Google Scholar
• Mnih V, Kavukcuoglu K, Silver D, Rusu AA, Veness J, Bellemare MG, Graves A, et al. (2015) Human-level control through deep reinforcement learning. Nature. 518(7540):529.Crossref, Google Scholar
• Morris DH, Rossine FW, Plotkin JB, Levin SA (2021) Optimal, near-optimal, and robust epidemic control. Commun. Phys. 4:78.Google Scholar
• Nair R, Varakantham P, Tambe M, Yokoo M (2005) Networked distributed POMDPs: A synthesis of distributed constraint optimization and POMDPs. Proc. 20th Natl. Conf. Artificial Intelligence, AAAI’05, Pittsburgh, vol. 1 (AAAI Press, Palo Alto, CA), 133–139.Google Scholar
• Oliehoek FA, Amato C (2016) A Concise Introduction to Decentralized POMDPs (Springer, Berlin).Crossref, Google Scholar
• Osband I, Van Roy B (2014) Near-optimal reinforcement learning in factored MDPs. Ghahramani Z, Welling M, Cortes C, Lawrence N, Weinberger KQ, eds. Advances in Neural Information Processing Systems, vol. 24 (Curran Associates, Inc.), 604–612. https://proceedings.neurips.cc/paper/2014/file/0deb1c54814305ca9ad266f53bc82511-Paper.pdf.Google Scholar
• Papadimitriou CH, Tsitsiklis JN (1999) The complexity of optimal queuing network control. Math. Oper. Res. 24(2):293–305.Link, Google Scholar
• Preciado VM, Zargham M, Enyioha C, Jadbabaie A, Pappas G(2013) Optimal vaccine allocation to control epidemic outbreaks in arbitrary networks. Proc. 52nd IEEE Conf. on Decision and Control (IEEE, New York), 7486–7491.Google Scholar
• Qu G, Li N (2019) Exploiting fast decaying and locality in multi-agent MDP with tree dependence structure. Proc. IEEE 58th Conf. on Decision and Control (IEEE, New York), 6479–6486.Google Scholar
• Qu G, Lin Y, Wierman A, Li N (2020a) Scalable multi-agent reinforcement learning for networked systems with average reward. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Advances in Neural Information Processing Systems, vol. 33 (Curran Associates, Inc.), 2074–2086. https://proceedings.neurips.cc/paper/2020/file/168efc366c449fab9c2843e9b54e2a18-Paper.pdf.Google Scholar
• Qu G, Yu C, Low S, Wierman A (2020b) Combining model-based and model-free methods for nonlinear control: A provably convergent policy gradient approach. Preprint, submitted June 12, 2020, https://arxiv.org/abs/2006.07476.Google Scholar
• Roberts L (1975) ALOHA packet system with and without slots and capture. ACM SIGCOMM Comput. Comm. Rev. 5:28–42.Crossref, Google Scholar
• Rotkowitz M, Lall S (2005) A characterization of convex problems in decentralized control. IEEE Trans. Automated Control 50(12):1984–1996.Google Scholar
• Silver D, Huang A, Maddison CJ, Guez A, Sifre L, Van Den Driessche G, Schrittwieser J, et al. (2016) Mastering the game of go with deep neural networks and tree search. Nature 529(7587):484.Crossref, Google Scholar
• Srikant R, Ying L (2019) Finite-time error bounds for linear stochastic approximation and TD learning. Beygelzimer A, Hsu D, eds. Proc. 32nd Conf. on Learn. Theory, Proceedings of Machine Learning Research, vol. 99 (PMLR), 2803–2830. http://proceedings.mlr.press/v99/srikant19a/srikant19a.pdf.Google Scholar
• Sutton RS, Barto AG, et al. (1998) Introduction to Reinforcement Learning, vol. 135 (MIT Press, Cambridge, MA). https://mitpress.mit.edu/books/reinforcement-learning-second-edition.Crossref, Google Scholar
• Sutton RS, McAllester DA, Singh SP, Mansour Y (2000) Policy gradient methods for reinforcement learning with function approximation. Solla S, Leen T, Müller K, eds. Advances in Neural Information Processing Systems, vol. 12 (MIT Press, Cambridge, MA), 1057–1063. https://proceedings.neurips.cc/paper/1999/file/464d828b85b0bed98e80ade0a5c43b0f-Paper.pdf.Google Scholar
• Tan M (1993) Multi-agent reinforcement learning: Independent vs. cooperative agents. Proc. of the 10th Internat. Conf. on Machine Learn. (Morgan Kaufmann, San Francisco), 330–337. https://www.sciencedirect.com/science/article/pii/B9781558603073500496.Google Scholar
• Tassiulas L, Ephremides A (1990) Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. Proc. 29th IEEE Conf. on Decision and Control (IEEE, New York), 2130–2132.Google Scholar
• Tsitsiklis JN, Van Roy B (1997) Analysis of temporal-diffference learning with function approximation. Mozer MC, Jordan M, Petsche T, eds. Adv. Neural Inform. Processing Systems, vol. 9 (MIT Press, Cambridge, MA), 1075–1081. https://proceedings.neurips.cc/paper/1996/file/e00406144c1e7e35240afed70f34166a-Paper.pdf.Google Scholar
• Tsitsiklis JN, Van Roy B (1999) Average cost temporal-difference learning. Automatica J. IFAC 35(11):1799–1808.Crossref, Google Scholar
• Tsitsiklis JN, Van Roy B (2002) On average vs. discounted reward temporal-difference learning. Machine Learn. 49(2):179–191.Crossref, Google Scholar
• Tu S, Recht B (2019) The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint. Proc. Conf. on Learn. Theory (PMLR), 3036–3083.Google Scholar
• Van Roy B, Tsitsiklis JN (1995) Stable linear approximations to dynamic programming for stochastic control problems with local transitions. Proc. 8th Internat. Conf. on Neural Inform. Processing Systems, NIPS’95, Denver (MIT Press, Cambridge, MA), 1045–1051.Google Scholar
• Varaiya P (2013) Max pressure control of a network of signalized intersections. Transportation Res., Part C Emerging Tech. 36:177–195.Crossref, Google Scholar
• Vogels W, van Renesse R, Birman K (2003) The power of epidemics: Robust communication for large-scale distributed systems. SIGCOMM Comput. Comm. Rev. 33(1):131–135.Crossref, Google Scholar
• Wai HT, Yang Z, Wang Z, Hong M (2018) Multi-agent reinforcement learning via double averaging primal-dual optimization. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Proc. 32nd Internat. Conf. on Neural Inform. Processing Systems. Advances in Neural Information Processing Systems, vol. 31 (Curran Associates, Inc.), 9672–9683. https://proceedings.neurips.cc/paper/2018/file/5a378f8490c8d6af8647a753812f6e31-Paper.pdf.Google Scholar
• Whittle P (1988) Restless bandits: Activity allocation in a changing world. J. Appl. Probability 25(A):287–298.Crossref, Google Scholar
• Wu Z, Jia QS, Guan X (2016) Optimal control of multiroom HVAC system: An event-based approach. IEEE Trans. Control Systems Tech. 24(2):662–669.Google Scholar
• Yun SY, Yi Y, Shin J, Eun DY (2012) Optimal CSMA: A survey. 2012 IEEE Internat. Conf. Comm. Systems (ICCS) (IEEE, New York), 199–204.Google Scholar
• Zhang R, Pavone M (2016) Control of robotic mobility-on-demand systems: A queueing-theoretical perspective. Internat. J. Robotics Res. 35(1-3):186–203.Crossref, Google Scholar
• Zhang K, Yang Z, Başar T (2021) Multi-agent reinforcement learning: A selective overview of theories and algorithms. Vamvoudakis KG, Wan Y, Lewis FL, Cansever D, eds. Handbook of Reinforcement Learning and Control, vol. 325 (Springer, Cham, Switzerland), 321–384. https://doi.org/10.1007/978-3-030-60990-0_12.Google Scholar
• Zhang X, Shi W, Yan B, Malkawi A, Li N (2017) Decentralized and distributed temperature control via HVAC systems in energy efficient buildings. Preprint, submitted February 10, 2017, https://arxiv.org/abs/1702.03308.Google Scholar
• Zhang K, Yang Z, Liu H, Zhang T, Basar T (2018) Fully decentralized multi-agent reinforcement learning with networked agents. Proc. Internat. Conf. on Machine Learn. (PMLR), 5872–5881.Google Scholar
• Zocca A (2019) Temporal starvation in multi-channel CSMA networks: An analytical framework. Queueing Systems 91(3-4):241–263.Crossref, Google Scholar
• Zou S, Xu T, Liang Y (2019) Finite-sample analysis for SARSA with linear function approximation. Wallach H, Larochelle H, Beygelzimer A, d’Alch’e-Buc F, Fox E, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 32 (Curran Associates, Inc.), 8665–8675. https://proceedings.neurips.cc/paper/2019/file/9f9e8cba3700df6a947a8cf91035ab84-Paper.pdf.Google Scholar