Багатоагентне навчання з підкріпленням

Дві ворогуючі команди агентів зіткнулися в БАНП експерименті
Частина з циклу
Машинне навчання
та добування даних
Ілюстрація нейронної мережі з темним
Парадигми
Задачі

Кластерування
Знижування розмірності
Структурове передбачування
Виявляння аномалій
Штучна нейронна мережа
Навчання з підкріпленням
Навчання з людьми
Діагностування моделей
Математичні засади
Місця машинного навчання
Пов'язані статті

Багатоагентне навчання з підкріпленням (БАНП, Multi-agent reinforcement learning, MARL) — це підгалузь навчання з підкріпленням. Вона зосереджена на вивченні поведінки декількох агентів навчання, які перебувають у спільному середовищі[1]. Кожен агент мотивується власною винагородою і виконує дії для просування власних інтересів; в деяких середовищах ці інтереси протилежні інтересам інших агентів, що призводить до виникнення складної групової динаміки.

Багатоагентне навчання з підкріпленням тісно пов'язане з теорією ігор, особливо з повторюваними іграми[en], а також з багатоагентними системами. Метою дослідження є пошук ідеальних алгоритмів, які максимізують винагороду, з використанням більш соціологічного набору концепцій. У той час як дослідження в одноагентному навчанні з підкріпленням стосуються пошуку алгоритму, який отримує найбільшу кількість балів для одного агента, дослідження в багатоагентному навчанні з підкріпленням оцінюють і кількісно визначають соціальні показники, такі як співпраця[2], взаємність[3], рівність[4], соціальний вплив[5], мова[6], та дискримінація[7].

Визначення

Подібно до одноагентного навчання з підкріпленням, багатоагентне навчання з підкріпленням моделюється як певна форма марковського процесу прийняття рішень (МППР). Наприклад,

  • Множина станів середовища.
  • Множина дій для кожного з агентів .
  •  — це ймовірність переходу (в момент часу ) від стану в стан при спільній дії .
  •  — це миттєва спільна винагорода після переходу з до зі спільними діями .

В умовах гри з повною інформацією, таких як ігри в шахи та Го, МППР був би повністю доступним для спостереження. В умовах недосконалої інформації, особливо в реальних застосунках, таких як безпілотні автомобілі, кожен агент має доступ до спостереження, яке містить лише частину інформації про поточний стан. В умовах часткового спостереження основною моделлю є частково спостережувана стохастична гра в загальному випадку і децентралізований частково спостережуваний марковський процес вирішування[en] в кооперативному випадку.

Співпраця та конкуренція

Коли кілька агентів діють у спільному середовищі, їхні інтереси можуть як збігатися, так і не співпадати. БАНП дозволяє дослідити всі можливі варіанти узгодження інтересів і те, як вони впливають на поведінку агентів:

  • В умовах чистої конкуренції винагороди агентів прямо протилежні одна одній, і тому вони грають один проти одного.
  • Чиста співпраця — це інша крайність, у якій агенти отримують абсолютно однакові винагороди, а отже, вони співпрацюють один з одним.
  • Умови зі змішаною сумою охоплюють усі ігри, які поєднують елементи як співпраці, так і конкуренції.

В умовах чистої конкуренції

Коли два агенти грають у гру з нульовою сумою, вони змагаються один з одним. Багато традиційних ігор, таких як шахи та го, підпадають під цю категорію, як і варіанти сучасних ігор для двох гравців, як-от StarCraft. Оскільки кожен агент може виграти лише за рахунок іншого агента, багато ускладнень, які потрібно враховувати, наприклад, при співправці, усувається. Немає шансів на взаємодію чи виникнення соціальних дилем, оскільки жоден з агентів не зацікавлений у діях, які приносять користь його опоненту.

Проекти Deep Blue[8] і AlphaGo демонструють, як оптимізувати продуктивність агентів в умовах чистої конкуренції.

Однією зі складностей, яку не можна усунути в умовах чистої конкуренції, є самонавчання. В міру того, як стратегії агентів вдосконалюються за допомогою гри проти себе[en], може утворитися багато рівнів навчання.

В умовах чистої співпраці

БАНП використовується для дослідження того, як окремі агенти з ідентичними інтересами можуть спілкуватися і працювати разом. Чисті умови співпраці досліджуються в розважальних кооперативних іграх, таких як Overcooked[9], а також у сценаріях реального світу в робототехніці.[10]

В умовах чистої співпраці всі агенти отримують ідентичні винагороди, що означає, що соціальних дилем не виникає.

В умовах чистої співпраці часто існує довільна кількість стратегій координації, і агенти приходять до певних «конвенцій», узгоджуючи свої дії один з одним. Поняття конвенцій вивчалося в лінгвістиці[11], а також згадувалося в більш загальних завданнях спільної роботи декількох агентів.[12][13][14][15]

В умовах змішаної суми

У моделі зі змішаною сумою кожен з чотирьох агентів намагається досягти власної мети. Успіх кожного агента залежить від того, чи звільнять йому шлях інші агенти, навіть якщо вони не мають прямих спонукань допомагати один одному.[16]

Більшість реальних сценаріїв із залученням кількох агентів мають елементи як співпраці, так і конкуренції. Наприклад, коли кілька безпілотних автомобілів планують свій маршрут, у кожного з них є інтереси, які відрізняються, але не виключають один одного: кожен автомобіль намагається мінімізувати час, який йому потрібен, щоб дістатися до пункту призначення, але всі автомобілі мають спільний інтерес — уникнути зіткнення на дорозі.[17]

Моделі з нульовою сумою з трьома або більше агентами часто демонструють властивості, подібні до моделей зі змішаною сумою, оскільки кожна пара агентів може мати ненульову суму їхніх спільних вигод.

Умови зі змішаною сумою можна дослідити за допомогою класичних матричних ігор, таких як дилема в'язня, складніших послідовних соціальних дилем, а також розважальних ігор, таких як Among Us[18], Diplomacy[en][19] та StarCraft II.[20][21]

Умови зі змішаною сумою можуть спричинити комунікаційні та соціальні дилеми.

Соціальні дилеми

Як і в теорії ігор, велика частина досліджень обертається навколо соціальних дилем[en], таких як дилема в'язня,[22] яструби і голуби і полювання на оленя.[23]

У той час як дослідження теорії ігор можуть фокусуватися на рівновазі Неша та на тому, якою була б ідеальна стратегія для агента, дослідження МАНП зосереджені на тому, як агенти вивчали б ці ідеальні стратегії за допомогою процесу спроб і помилок. Алгоритми навчання з підкріпленням, які використовуються для навчання агентів, максимізують власну винагороду агента; конфлікт між потребами агентів і потребами групи є предметом активного дослідження.[24]

Були досліджені різні методи, щоб спонукати агентів до співпраці: зміна правил середовища,[25] додавання внутрішніх винагород[4] тощо.

Послідовні соціальні дилеми

Соціальні дилеми, такі як дилема ув'язненого, полювання на оленя та яструби і голуби, є «матричними іграми». Кожен агент виконує лише одну дію з двох можливих дій, а для опису винагороди, яку отримає кожен агент, враховуючи дії, які він здійснив, використовується проста матриця 2х2.

У людей та інших живих істот соціальні дилеми, як правило, складніші. Агенти здійснюють кілька дій протягом певного часу, і різниця між співпрацею та порушенням не така чітка, як у матричних іграх. Концепція послідовної соціальної дилеми (ПСД) була введена в 2017 році[26] як спроба змоделювати цю складність. Наразі тривають дослідження, спрямовані на визначення різних типів ПСД та демонстрацію кооперативної поведінки агентів, які в них діють.[27]

Самонавчальні програми

Самонавчання (autocurriculum)[28] — це концепція навчання з підкріпленням, яка є ключовою в багатоагентних експериментах. Коли агенти покращують свої показники, вони змінюють середовище в якому перебувають; ці зміни в середовищі впливають на них самих та інших агентів. Цикл зворотного зв'язку призводить до кількох окремих фаз навчання, кожна з яких залежить від попередньої. Накладені шари навчання називаються самонавчанням. Самонавчання особливо помітне в умовах суперництва[29], коли кожна група агентів намагається протидіяти поточній стратегії протилежної групи.

Гра «Хованки» є зрозумілим прикладом самонавчання в умовах змагання. У цьому експерименті команда шукачів змагається з командою тих, хто ховається. Щоразу, коли одна з команд вивчає нову стратегію, команда суперника адаптує свою стратегію, щоб протидіяти їй у найкращій спосіб. Коли ті, хто ховається, вчаться використовувати ящики для будівництва схованки, шукачі відповідають тим, що навчаються використовувати рампу, щоб проникнути у цю схованку. У відповідь ті, хто ховається, блокують пандуси, роблячи їх недоступними для використання шукачами. Тоді шукачі відповідають «серфінгом по ящику», використовуючи збій у грі, щоб проникнути у схованку. Кожен «рівень» навчання є явищем, передумовою якого є попередній рівень. Це призводить до появи цілої низки моделей поведінки, кожна з яких залежить від попередньої.

Автонавчання в експериментах з підкріплювального навчання порівнюють з етапами еволюції життя на Землі та розвитку людської культури. Основний етап еволюції стався 2-3 мільярди років тому, коли фотосинтезуючі форми життя почали виробляти величезну кількість кисню, чим змінили баланс газів в атмосфері[30]. На наступних етапах еволюції розвинулися форми життя, здатні дихати киснем, що врешті-решт призвело до появи наземних ссавців і людини. Ці пізніші етапи могли відбутися лиш після того, як етап фотосинтезу зробив кисень широко доступним. Так само людська культура не змогла б пережити промислову революцію у 18 столітті без ресурсів і знань, отриманих в результаті сільськогосподарської революції близько 10 000 років до нашої ери[31].

Застосування

Багатоагентне навчання з підкріпленням було застосовується в різних сферах в науці та промисловості:

Контроль ШІ

Багатоагентне навчання з підкріпленням використовується в дослідженнях з контролю ШІ[en]. Взаємодію між різними агентами в середовищі БАНП можна порівняти з відносинами між людиною і агентом зі ШІ. Дослідницькі зусилля на перетині цих двох областей намагаються змоделювати можливі конфлікти між намірами людини і діями агента зі ШІ, а потім дослідити, які змінні потрібно відкоригувати, щоб запобігти цим конфліктам.[45][46]

Обмеження

Існують деякі невід'ємні труднощі багатоагентного глибокого навчання з підкріпленням[en][47]. Середовище більше не є стаціонарним, тому властивість Маркова порушується: переходи та винагороди залежать не лише від поточного стану агента.

Програмне забезпечення

Існують різні інструменти та платформи для роботи з багатоагентними середовищами навчання з підкріпленням:

Подальше читання

  • Stefano V. Albrecht, Filippos Christianos, Lukas Schäfer. Multi-Agent Reinforcement Learning: Foundations and Modern Approaches. MIT Press, 2024. https://www.marl-book.com
  • Kaiqing Zhang, Zhuoran Yang, Tamer Basar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Studies in Systems, Decision and Control, Handbook on RL and Control, 2021. [1]
  • Yang, Yaodong; Wang, Jun (2020). An Overview of Multi-Agent Reinforcement Learning from Game Theoretical Perspective. arXiv:2011.00583 [cs.MA]. 

Примітки

  1. ↑ Stefano V. Albrecht, Filippos Christianos, Lukas Schäfer. Multi-Agent Reinforcement Learning: Foundations and Modern Approaches. MIT Press, 2024. https://www.marl-book.com/
  2. ↑ Lowe, Ryan; Wu, Yi (2020). Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments. arXiv:1706.02275v4 [cs.LG]. 
  3. ↑ Baker, Bowen (2020). Emergent Reciprocity and Team Formation from Randomized Uncertain Social Preferences. NeurIPS 2020 proceedings. arXiv:2011.05373. 
  4. ↑ а б Hughes, Edward; Leibo, Joel Z. та ін. (2018). Inequity aversion improves cooperation in intertemporal social dilemmas. NeurIPS 2018 proceedings. arXiv:1803.08884. 
  5. ↑ Jaques, Natasha; Lazaridou, Angeliki; Hughes, Edward та ін. (2019). Social Influence as Intrinsic Motivation for Multi-Agent Deep Reinforcement Learning. Proceedings of the 35th International Conference on Machine Learning. arXiv:1810.08647. 
  6. ↑ Lazaridou, Angeliki (2017). Multi-Agent Cooperation and The Emergence of (Natural) Language. ICLR 2017. arXiv:1612.07182. 
  7. ↑ Duéñez-Guzmán, Edgar (2021). Statistical discrimination in learning agents. arXiv:2110.11404v1 [cs.LG]. 
  8. ↑ Campbell, Murray; Hoane, A. Joseph Jr.; Hsu, Feng-hsiung (2002). Deep Blue. Artificial Intelligence. Elsevier. 134 (1–2): 57—83. doi:10.1016/S0004-3702(01)00129-1. ISSN 0004-3702. 
  9. ↑ Carroll, Micah та ін. (2019). On the Utility of Learning about Humans for Human-AI Coordination. arXiv:1910.05789 [cs.LG]. 
  10. ↑ Xie, Annie; Losey, Dylan; Tolsma, Ryan; Finn, Chelsea; Sadigh, Dorsa (November 2020). Learning Latent Representations to Influence Multi-Agent Interaction (PDF). CoRL. 
  11. ↑ Clark, Herbert; Wilkes-Gibbs, Deanna (February 1986). Referring as a collaborative process. Cognition. 22 (1): 1—39. doi:10.1016/0010-0277(86)90010-7. PMID 3709088. 
  12. ↑ Boutilier, Craig (17 березня 1996). Planning, learning and coordination in multiagent decision processes. Proceedings of the 6th Conference on Theoretical Aspects of Rationality and Knowledge: 195—210. 
  13. ↑ Stone, Peter; Kaminka, Gal A.; Kraus, Sarit; Rosenschein, Jeffrey S. (July 2010). Ad Hoc Autonomous Agent Teams: Collaboration without Pre-Coordination. AAAI 11. 
  14. ↑ Foerster, Jakob N.; Song, H. Francis; Hughes, Edward; Burch, Neil; Dunning, Iain; Whiteson, Shimon; Botvinick, Matthew M; Bowling, Michael H. Bayesian action decoder for deep multi-agent reinforcement learning. ICML 2019. arXiv:1811.01458. 
  15. ↑ Shih, Andy; Sawhney, Arjun; Kondic, Jovana; Ermon, Stefano; Sadigh, Dorsa. On the Critical Role of Conventions in Adaptive Human-AI Collaboration. ICLR 2021. arXiv:2104.02871. 
  16. ↑ Bettini, Matteo; Kortvelesy, Ryan; Blumenkamp, Jan; Prorok, Amanda (2022). VMAS: A Vectorized Multi-Agent Simulator for Collective Robot Learning. The 16th International Symposium on Distributed Autonomous Robotic Systems. Springer. arXiv:2207.03530. 
  17. ↑ Shalev-Shwartz, Shai; Shammah, Shaked; Shashua, Amnon (2016). Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving. arXiv:1610.03295 [cs.AI]. 
  18. ↑ Kopparapu, Kavya; Duéñez-Guzmán, Edgar A.; Matyas, Jayd; Vezhnevets, Alexander Sasha; Agapiou, John P.; McKee, Kevin R.; Everett, Richard; Marecki, Janusz; Leibo, Joel Z.; Graepel, Thore (2022). Hidden Agenda: a Social Deduction Game with Diverse Learned Equilibria. arXiv:2201.01816 [cs.AI]. 
  19. ↑ Bakhtin, Anton; Brown, Noam та ін. (2022). Human-level play in the game of Diplomacy by combining language models with strategic reasoning. Science. Springer. 378 (6624): 1067—1074. Bibcode:2022Sci...378.1067M. doi:10.1126/science.ade9097. PMID 36413172. 
  20. ↑ Samvelyan, Mikayel; Rashid, Tabish; de Witt, Christian Schroeder; Farquhar, Gregory; Nardelli, Nantas; Rudner, Tim G. J.; Hung, Chia-Man; Torr, Philip H. S.; Foerster, Jakob; Whiteson, Shimon (2019). The StarCraft Multi-Agent Challenge. arXiv:1902.04043 [cs.LG]. 
  21. ↑ Ellis, Benjamin; Moalla, Skander; Samvelyan, Mikayel; Sun, Mingfei; Mahajan, Anuj; Foerster, Jakob N.; Whiteson, Shimon (2022). SMACv2: An Improved Benchmark for Cooperative Multi-Agent Reinforcement Learning. arXiv:2212.07489 [cs.LG]. 
  22. ↑ Sandholm, Toumas W.; Crites, Robert H. (1996). Multiagent reinforcement learning in the Iterated Prisoner's Dilemma. Biosystems. 37 (1–2): 147—166. doi:10.1016/0303-2647(95)01551-5. PMID 8924633. 
  23. ↑ Peysakhovich, Alexander; Lerer, Adam (2018). Prosocial Learning Agents Solve Generalized Stag Hunts Better than Selfish Ones. AAMAS 2018. arXiv:1709.02865. 
  24. ↑ Dafoe, Allan; Hughes, Edward; Bachrach, Yoram та ін. (2020). Open Problems in Cooperative AI. NeurIPS 2020. arXiv:2012.08630. 
  25. ↑ Köster, Raphael; Hadfield-Menell, Dylan; Hadfield, Gillian K.; Leibo, Joel Z. Silly rules improve the capacity of agents to learn stable enforcement and compliance behaviors. AAMAS 2020. arXiv:2001.09318. 
  26. ↑ Leibo, Joel Z.; Zambaldi, Vinicius; Lanctot, Marc; Marecki, Janusz; Graepel, Thore (2017). Multi-agent Reinforcement Learning in Sequential Social Dilemmas. AAMAS 2017. arXiv:1702.03037. 
  27. ↑ Badjatiya, Pinkesh; Sarkar, Mausoom (2020). Inducing Cooperative behaviour in Sequential-Social dilemmas through Multi-Agent Reinforcement Learning using Status-Quo Loss. arXiv:2001.05458. 
  28. ↑ Leibo, Joel Z.; Hughes, Edward та ін. (2019). Autocurricula and the Emergence of Innovation from Social Interaction: A Manifesto for Multi-Agent Intelligence Research. arXiv:1903.00742v2 [cs.AI]. 
  29. ↑ Baker, Bowen та ін. (2020). Emergent Tool Use From Multi-Agent Autocurricula. ICLR 2020. arXiv:1909.07528. 
  30. ↑ Kasting, James F; Siefert, Janet L (2002). Life and the evolution of earth's atmosphere. Science. 296 (5570): 1066—1068. Bibcode:2002Sci...296.1066K. doi:10.1126/science.1071184. PMID 12004117. S2CID 37190778. 
  31. ↑ Clark, Gregory (2008). A farewell to alms: a brief economic history of the world. Princeton University Press. ISBN 978-0-691-14128-2. 
  32. ↑ а б в г д е ж и Li, Tianxu; Zhu, Kun; Luong, Nguyen Cong; Niyato, Dusit; Wu, Qihui; Zhang, Yang; Chen, Bing (2021). Applications of Multi-Agent Reinforcement Learning in Future Internet: A Comprehensive Survey. arXiv:2110.13484 [cs.AI]. 
  33. ↑ Le, Ngan; Rathour, Vidhiwar Singh; Yamazaki, Kashu; Luu, Khoa; Savvides, Marios (2021). Deep Reinforcement Learning in Computer Vision: A Comprehensive Survey. arXiv:2108.11510 [cs.CV]. 
  34. ↑ Moulin-Frier, Clément; Oudeyer, Pierre-Yves (2020). Multi-Agent Reinforcement Learning as a Computational Tool for Language Evolution Research: Historical Context and Future Challenges. arXiv:2002.08878 [cs.MA]. 
  35. ↑ Killian, Jackson; Xu, Lily; Biswas, Arpita; Verma, Shresth та ін. (2023). Robust Planning over Restless Groups: Engagement Interventions for a Large-Scale Maternal Telehealth Program. AAAI. 
  36. ↑ Krishnan, Srivatsan; Jaques, Natasha; Omidshafiei, Shayegan; Zhang, Dan; Gur, Izzeddin; Reddi, Vijay Janapa; Faust, Aleksandra (2022). Multi-Agent Reinforcement Learning for Microprocessor Design Space Exploration. arXiv:2211.16385 [cs.AR]. 
  37. ↑ Li, Yuanzheng; He, Shangyang; Li, Yang; Shi, Yang; Zeng, Zhigang (2023). Federated Multiagent Deep Reinforcement Learning Approach via Physics-Informed Reward for Multimicrogrid Energy Management. IEEE Transactions on Neural Networks and Learning Systems. PP: 1—13. arXiv:2301.00641. doi:10.1109/TNNLS.2022.3232630. PMID 37018258. S2CID 255372287. 
  38. ↑ Ci, Hai; Liu, Mickel; Pan, Xuehai; Zhong, Fangwei; Wang, Yizhou (2023). Proactive Multi-Camera Collaboration for 3D Human Pose Estimation. International Conference on Learning Representations. 
  39. ↑ Vinitsky, Eugene; Kreidieh, Aboudy; Le Flem, Luc; Kheterpal, Nishant; Jang, Kathy; Wu, Fangyu; Liaw, Richard; Liang, Eric; Bayen, Alexandre M. (2018). Benchmarks for reinforcement learning in mixed-autonomy traffic (PDF). Conference on Robot Learning. 
  40. ↑ Tuyls, Karl; Omidshafiei, Shayegan; Muller, Paul; Wang, Zhe; Connor, Jerome; Hennes, Daniel; Graham, Ian; Spearman, William; Waskett, Tim; Steele, Dafydd; Luc, Pauline; Recasens, Adria; Galashov, Alexandre; Thornton, Gregory; Elie, Romuald; Sprechmann, Pablo; Moreno, Pol; Cao, Kris; Garnelo, Marta; Dutta, Praneet; Valko, Michal; Heess, Nicolas; Bridgland, Alex; Perolat, Julien; De Vylder, Bart; Eslami, Ali; Rowland, Mark; Jaegle, Andrew; Munos, Remi; Back, Trevor; Ahamed, Razia; Bouton, Simon; Beauguerlange, Nathalie; Broshear, Jackson; Graepel, Thore; Hassabis, Demis (2020). Game Plan: What AI can do for Football, and What Football can do for AI. arXiv:2011.09192 [cs.AI]. 
  41. ↑ Chu, Tianshu; Wang, Jie; Codec├á, Lara; Li, Zhaojian (2019). Multi-Agent Deep Reinforcement Learning for Large-scale Traffic Signal Control. arXiv:1903.04527 [cs.LG]. 
  42. ↑ Belletti, Francois; Haziza, Daniel; Gomes, Gabriel; Bayen, Alexandre M. (2017). Expert Level control of Ramp Metering based on Multi-task Deep Reinforcement Learning. arXiv:1701.08832 [cs.AI]. 
  43. ↑ Ding, Yahao; Yang, Zhaohui; Pham, Quoc-Viet; Zhang, Zhaoyang; Shikh-Bahaei, Mohammad (2023). Distributed Machine Learning for UAV Swarms: Computing, Sensing, and Semantics. arXiv:2301.00912 [cs.LG]. 
  44. ↑ Xu, Lily; Perrault, Andrew; Fang, Fei; Chen, Haipeng; Tambe, Milind (2021). Robust Reinforcement Learning Under Minimax Regret for Green Security. arXiv:2106.08413 [cs.LG]. 
  45. ↑ Leike, Jan; Martic, Miljan; Krakovna, Victoria; Ortega, Pedro A.; Everitt, Tom; Lefrancq, Andrew; Orseau, Laurent; Legg, Shane (2017). AI Safety Gridworlds. arXiv:1711.09883 [cs.AI]. 
  46. ↑ Hadfield-Menell, Dylan; Dragan, Anca; Abbeel, Pieter; Russell, Stuart (2016). The Off-Switch Game. arXiv:1611.08219 [cs.AI]. 
  47. ↑ Hernandez-Leal, Pablo; Kartal, Bilal; Taylor, Matthew E. (1 листопада 2019). A survey and critique of multiagent deep reinforcement learning. Autonomous Agents and Multi-Agent Systems (англ.). 33 (6): 750—797. arXiv:1810.05587. doi:10.1007/s10458-019-09421-1. ISSN 1573-7454.