А.Н. Алфимцев МУЛЬТИАГЕНТНОЕ ОБУЧЕНИЕ С ПОДКРЕПЛЕНИЕМ о,~ о 0 000 0 ooQ о {у) о !"' ё) ИЗДАТЕЛЬСТВО "'w 1в МГТУ им. Н.Э. БАУМАНА Федеральное государственное бюджетное образовательное учреждение высшего образования «Московский государственный технический университет имени Н.Э. Баумана (национальный исследовательский университет)» А.Н. Алфимцев Мультиагентное обучение с подкреплением Учебное пособие Мос ква ИЗДАТЕЛЬСТВО МГТУ им . Н. Э . Баума на 2 О 21 УДКОО4.85 А53 Издание доступно в электронном виде по адресу Факультет <<Информатика и системы управлениЯ>> Кафедра <<Информационные системы и телекоммуникации>> Рекомендовано Научно-методическим советом МГТУ им. Н. Э. Баумана в качестве учебного пособия Алфимцев, А. Н. А53 Мультиагентное обучение с подкреплением: учебное пособие/ А. Н. Алфимцев. - Москва: Издательство МПУ им. Н. Э . Баумана, 2021. - 222, [2] с. : ил. Рассмотрены современные и классические алгоритмы одновременного машинного обучения множества агентов, основанные на теории игр, таблич ных , нейросетевых , эволюционных и роевых технологиях . Представлено по следовательное развитие теоретической модели алгоритмов , базирующееся на марковских процессах принятия решений. Реализация алгоритмов выполнена на языке программирования Python с использованием библиотеки глубокого обучения PyTorch. Средой машинного обучения является компьютерная игра StarCraft 11 с интерфейсом кооперативного мулътиагентного обучения SMAC. Для магистрантов и аспирантов направления подготовки << Информатика и вычислительная техн ика ». ~ Р.) Уважаемые читатели! Пожелания, предложения, а также сообщения о за.11еченных ~ f8:i I В :\" 97 опечатках и неточностях Издательство просит направлять по электронной почте: - 03 -56 16- 1 © МГГУ 1~-•- Н . Э. Ба) . 1ана , 2021 © Офор. 1.1.е ние . пательство ;Ч ПУ 11_t. Н . З. Ба ) . 1ана , 2021 Предисловие Учебное пособие предназначено для самостоятельного изучения ма гистрантами и аспирантами основных разделов дисциплины « Мультиа гентные интеллектуальные системы>> и имеет практико-ориентированный характер , обеспечивая возможность решения конкретных профессиональ ных задач . Цель изучения дисциплины - формирование профессиональных ком петенций, связанных с разработкой программного обеспечения для мульти агентного обучения, а также общепрофессиональных компетенций, необхо димых для применения на практике новых научных принципов и методов машинного обучения. В учебном пособии сформированы внутридисциплинарные и междис циплинарные связи , обеспечивающие преемственность знаний, полученных при изучении предшествующих дисциплин по основам программирования , а также непрерывность отдельных видов математической и технологической подготовки разработчика программного обеспечения. Системность изложения материала обеспечена логической последова тельностью и аргументированностью приводимых положений . Новые поло жения базируются на ранее изученных. Учебное пособие состоит из пяти глав, каждая из которых включает де вять типизированных разделов: <<Классификация>> , <<Модель>>, <<Алгоритм>>, << Карта>> , <<Технология>> , << Код>>, <<Эксперимент>>, <<Выводы>>, <<Задачи для са моконтроля>> . В последовательном изложении по принципу <<ОТ просто го к сложному» объединены теория и технология , поскольку для изучения и развития современного мультиагентного обучения недостаточно ограни чиваться теоретическими исследованиями либо заниматься только програм мированием чужих изысканий. В разделе « Классификация>> рассматриваются общая идея главы и раз личные алгоритмы мультиагентного обучения , определяется место пред ставляемых алгоритмов в системе научных координат . В разделе « Модель>> приводится основной используемый в главе матема тический аппарат . В разделе <<Алгоритм» анализируется основной алгоритм мультиагент ного обучения , рассматриваемый в данной главе . Псевдокод алгоритма да ется в авторской редакции , которая бол ьше соответствует его реальной реа л изации . В разделе << Карта>> описывается карта игры StarCraft II, на материа ле которой проводится мультиагентное обучение в каждой главе . Раздел Предисловие <<Технология» посвящен особенностям настройки компьютерной игры и ис пользуемых программных библиотек. В разделе <<Код>> дается оригинальная реализация основного алгоритма, рассматриваемого в главе, на языке программирования Python. В разделе «Эксперименты>> приводятся результаты применения рассма триваемых в главе алгоритмов. В разделе <<Выводы>> тезисно подводятся некоторые итоги. В конце каждой главы в разделе «Задачи для самоконтроля» представ лены задачи по программированию мультиагентного обучения которые позволят закрепить рассмотренный в главе теоретический материал прак тическими навыками. Задачи даны по возрастанию сложности в порядке, соответствующем основным тезисам глав. Гл. 1 учебного пособия посвящена независимому табличному Q-обу чению. Алгоритмы обучения с подкреплением одними из первых были при менены для мультиагентного обучения. Показаны основные преимущества и недостатки классического алгоритма Q-обучения . В гл. 2 рассматривается мультиагентное обучение в матричных и стоха стических играх с использованием теории игр . Несмотря на то что алгорит мы на основе теории игр объективно уступают современным алгоритмам, многие созданные в этот период фундаментальные концепции развиваются до сих пор. В гл. 3 рассматриваются сильнейшие на сегодняшней день алгорит мы мультиагентноrо обучения, основанные на теории искусственных ней ронных сетей. Показано, как алгоритмы IQN и МADDPG помогают до биться высоких результатов в микроменеджменте действий агентов в игре StarCraft П. Считается, что агент может быть по -настоящему автономным , если он способен не просто достигать целей функционирования , но и создавать их. В гл. 4 анализируется современные принципы эволюционного и коэволю ционного обучения . Заключительная глава - гл. 5 - посвящена гомогеннш,1}' кооператив ному мультиагентному обучению, для которого иногда пр и 1еняется термин <<роевое обучение>>. Предполагается, что вдохновленные живой природой алгоритмы роевого обучения являются наиболее перспективной альтерна тивой алгоритмам нейросетевого обучения. Каждую главу, а также введение и заключение пре.Jваряют эпиграфы, взятые из написанного в жанре фэнтези романа американско го математи ка и писателя Юн Ха Ли << Гамбит девятихвостого .111 а В книге нестандартно спрогнозированы р азвитие Jf.: Эксмо, 2018) . . rу.1ьтиагентных техно логий и роль человека в техногенном мире бу.=rушего. Г.1авный герой ро мана учится эффективно использовать р ее рсы и HcL о..1ить оптимальные стратегии действий, что отвечает основной 11...:Iee п е..1 пособия. ав..1е нного учебного использовать игру в качестве педагогического инструмента. Юн Ха Ли. Гамбит девятихвостого лиса В Национальной стратегии развития искусственного интеллекта одной из приоритетных целей является создание технологий распределенных кол лективных систем. Для достижения этой цели необходимо решить задачи разработки програмУiного обеспечения, математических моделей и алгорит мов мультиагентного обучения с подкреплением. Мультиагентная система (англ. multi-agent system) - система, состоя щая из нескольких взаимодействующих агентов. Агент - компьютерная программа , которая расположена в некоторой среде и способна автономно действовать и обучаться в этой среде для дости жения своих целей. Под средой обычно понимается все физическое и вир туальное пространство, находящееся вне агента . Машинное обучение (англ. machine learning) - совокупность алгорит мов и моделей , которые по зволяют агенту для достижения цели без пред варительного программирования находить закономерности в данных , делать прогнозы, самостоятельно принимать и улучшать решения на основе полу ченного опыта взаимодействия . Обучение с подкреплением (англ. reinforcement learning) - один из спосо бов машинного обучения, особенностью которого является обучение агента в процессе взаимодействия со средой. Мультиагентное обучение с подкреплением (англ . Multi-agent Reinforcement Learning, MARL) - совокупность алгоритмов и моделей машинного обуче ния с подкреплением , которые дают возможность обучать мультиагентные системы . Мультиагентные системы как отдельная область дисциплины <<Инфор матика и вычислительная техника>> начала развиваться в конце ХХ в . В по следние 20 лет интерес к этой области постоянно возрастает, о чем свиде тельствуют более полумиллиона поисковых результатов в системе <<Академия Google>>. С одной стороны, этот рост связан с убеждением , что мультиагент ные системы являются одной из перспективных парадигм разработки программного обеспечения . Смещение акцента с разработки приложений для персональных рабочих станций на разработку распределенных систем, вз аимодействующих друг с другом дистанционно , привело к усложнению этих систем и приобретению ими свойств, характерных для мультиагент ных систем. С другой стороны , ключевым свойством агента, функционирующего в незнакомой среде, является способность к обучению на основе получен ного опыта взаимодействия с этой средой или с другими агентами. Очевид ные успехи глубокого одноагентного обучения в распознавательных и игро вых задачах, достигнутые в последние годы, мотивируют исследователей и разработчиков использовать потенциал этих методов для мультиагентного обучения. Мультиагентное обучение в настоящее время - фундаментальный ком понент мультиагентной системы. С научной точки зрения исследование взаимодействия между множеством одновременно обучающихся агентов позволяет получить новые знания, которые могут быть полезны при анализе социальных структур общества, экономических конкурентных сред, в тео рии управления. С инженерной точки зрения одновременно обучающееся множество агентов может предоставить концептуально новый способ раз работки коммуникационных систем, робототехники, транспортных систем, человеко-машинных интерфейсов, программного обеспечения. В целом мультиагентный подход при построении системы в сложной, т. е. недетерминированной , динамической, непрерывной, среде дает следу ющие преимущества. • Робастность. Мультиагентная система способна продолжить функци онирование при сбоях в работе отдельных агентов. • Эффективность. Параллельная обработка данных в мультиагентной системе автономными агентами ускоряет функционирование системы. • Адаптивность . Децентрализованная мультиагентная система может динамически изменять свое поведение при изменениях в среде. • Инкапсулируемость. Мультиагентная система модульна по своей при роде, что позволяет гибко изменять ее структуру, абстрагировать данные и защищать внутренние реализации. • Масштабируемость. При восприятии информаuии и пр инятии реше ния мультиагентная система не имеет ограничений по uентрализов анному контролю данных , что дает возможность лучше справляться с увеличением рабочей нагрузки при добавлении ресурсов . Однако применение методов одноагентного маш1 [иного к мультиагентным системам приводит и к появлению но выJ обучения выз овов. Во-первых, мультиагентное обучение подвержено <<П . ок~ятию размер ности>>, вызванному экспоненциальным ростом про транства состояний действий при увеличении числа агентов. Так, при таб.1.нчно:.\r опноагентном обучении с подкреплением семи агентов с шестью воз..Lожными действи ями для каждого состояния среды необхо.J.и~ю хранить Q-значения. А при мультиагентном обучении совместныы .J.еi1ств.оо I нужно будет учесть 279 936 Q-значений . Во - вторых, многие теоретические га анn 1. 'ото ые существовали и формально доказывались при олноаге нтно. 1 об _ -ч н а . при многоагент ном обеспечении не действуют . Так, 1сшс ич _ u a.:-iro итмом Q- обучения с подкреплением гарантируется сходимость к оптимальной стратегии для конечного марковского процесса принятия решений. Но при мультиагент ном обучении агентам приходится довольствоваться не оптимальной страте гией, а некоторым усредненным равновесием, которого они достигли в дей ствиях друг с др угом и со средой. В-третьих, выбор цели мультиагентного обучения, которую можно фор мально описать и автоматически проверить, не является столь очевидным решением, как при одноагентном обучении. На достижение цели максими зации награды агента при мультиагентном обучении с подкреплением мо гут влиять, например, результаты обучения других агентов. В связи с этим в практических задачах для формулирования цели мультиагентного обуче ния требуются отдельные, иногда уникальные, решения, касающиеся кон троля стабильности обучения, адаптируемости к изменению поведения дру гих агентов, устойчивости внутренней мотивации. В-четвертых, нестационарность машинного обучения при мультиагент ном обучении проявляется с иной стороны. Когда одновременно обучается несколько агентов, они постоянно подстраивают свои действия под дей ствия других агентов, которые , в свою очередь, подстраиваются под них . От дельной проблемой здесь является определение оптимальности стратегии , так как стратегия должна постоянно меняться в соответствии с изменяющи мися стратегиями других агентов. В-пятых , проблема эксплуатации -исследования также значительно ус л ожняется при мультиагентном обучении. В случае, когда принять р еше ние должен один агент, достаточно исследовать среду и можно начинать действовать, эксплуатировать полученный опыт. Но при обучении мно жества агентов этот индивидуальный переход одного агента от исследова ния к эксплуатации или наоборот неявно влияет на стратегии всех других агентов. И наконец, шестой вызов связан с координацией действий агентов. Эффект от каждого действия агента зависит от действия или бездействия других агентов. В решении проблемы координации приходится постоянно балансировать между поиском эффективных совместных действий агентов и поиском оптимальных стратегий. Несмотря на то что эта проблема боль ше характерна для кооперативного мультиагентного обучения , отсутствие координации негативно влияет и на независимо обучающихся агентов. В последние годы главные ре зультаты машинного обучения обуча ющихся агентов достигнуты в компьютерных играх. Иногда результаты игроков-агентов сопоставимы результатами игры профессиональных игроков-людей или даже их превосходят. Такие компьютерные игры, как стратегическая компьютерная игра StarCraft II, с точки зрения машин ного обучения представляет собой сложную среду, в которой встречают ся все актуальные вызовы мультиагентного обучения; в ней также можно безопасно промоделировать ситуации реального мира: информации, кооперативность или некооперативность частичный обзор взаимодействия, децентрализованный микроменеджмент, большой объем входных данных , тысячи возможных действий, разнообразный набор сценариев, нестаuио нарность обучения . В связи с этим технологическая часть учебного пособия построена на базе компьютерной игры StarCraft II, разработанной кампанией Blizzard, и программной библиотеки мультиагентного обучения SМАС, разработанной исследовательской лабораторией Whiteson Оксфордского университета. Это множество библиотек, которые выложены в открытом доступе на платформе Github . Пpимepы , приведенные в данном учебном пособии , также опубликованы в открытом виде , чтобы была возможность не только повто рить рассматриваемые алгоритмы, но и провести модификацию предлагае мого решения, сравнить полученные результаты с результатами , приведен ными в пособии. Независимое табличное обучение Календарная война - война сердец. Однако числа способны влиять на сердца при условии, что и те, и другие верные. Юн Ха Ли. Гамбит девятихвостого лиса 1.1. Классификация Первые методы мультиагентного обучения базировались на алгоритмах обучения с подкреплением. Особенностью обучения с подкреплением является обучение агента в процессе взаимодействия со средой. Алгоритмы обучения с подкреплением не требуют априорной информации о среде или какой-ли бо дополнительной модели среды. Агенты i = 1, 2, ... , п обучаются в процессе взаимодействия, получая от среды положительные или отрицательные под- крепляющие сигналы r,1,r,2, ... ,r/ и новые состояния s;+ 1,s12+ 1, ••• ,s;+ 1, зави1 сящие от деиствии а, ,а , ••• ,а агентов рис. . . Среда Гt , Sr+l Гt , St+l Агент 1 Агент 2 Гt , St+l Агент п Рис. 1.1. Схема независимого мульти агентного обучения с подкреплением Подкрепляющий сигнал менее информативен, чем в алгоритмах обу чения с учителем, но все же дает некоторую информацию, в то время как в алгоритмах обучения без учителя такой сигнал отсутствует. При исполь зовании алгоритмов обучения с подкреплением для мультиагентного обу чения появляется возможность естественно совместить преимущество двух