Искусственный интеллект (ИИ) полон вопросов, на которые невозможно ответить, и ответов, которые нельзя отнести к правильным вопросам. В прошлом за свое упорство в неправильных методах он расплачивался периодами застоя, известными как зимы ИИ. Однако в календаре AI только что наступила весна, и количество приложений процветает.
Тем не менее, есть ветвь ИИ, которой долгое время не уделялось должного внимания. Речь идет об обучении с подкреплением, которое недавно показало впечатляющие результаты в таких играх, как AlphaGo и Atari. Но давайте будем честными: это были не победы в обучении с подкреплением. В этих случаях глубже стали глубокие нейронные сети, а не наше понимание обучения с подкреплением, которое сохраняет ту глубину, которую оно достигло десятилетия назад.
Еще хуже обстоит дело с обучением с подкреплением в применении к реальным жизненным проблемам. Если обучение робота балансировать на веревке кажется трудным, попробуйте обучить команду роботов, чтобы выиграть футбольный матч, или команду дронов, чтобы следить за движущейся целью.
Прежде чем мы потеряем ветвь или, что еще хуже, дерево, мы должны углубить наше понимание этих приложений. Теория игр - наиболее распространенный подход к изучению команд игроков, разделяющих общую цель. Он может предоставить нам инструменты для управления алгоритмами обучения в этих условиях.
Но давайте посмотрим, почему общий подход не является подходом здравого смысла.
Устранение ошибки - такая же хорошая услуга, как установление новой истины или факта, а иногда даже лучше. - Чарльз Дарвин
Во-первых, давайте разберемся с терминологией и основами в этих областях.
Теория игры
Некоторые полезные термины
- Игра. Как и игры в популярном понимании, это может быть любая среда, в которой игроки совершают действия, и от них будет зависеть ее результат.
- Игрок: лицо, принимающее стратегические решения в игре.
- Стратегия: полный план действий, которые игрок предпримет с учетом набора обстоятельств, которые могут возникнуть в игре.
- Выплата: выигрыш, который игрок получает от достижения определенного результата игры.
- Равновесие: момент в игре, когда оба игрока приняли свои решения и достигнут результат.
- Равновесие по Нэшу: равновесие, при котором ни один игрок не может выиграть, изменив свою собственную стратегию, если стратегии других игроков остаются неизменными.
- Доминирующая стратегия: возникает, когда одна стратегия лучше, чем другая для одного игрока, независимо от того, как могут играть оппоненты этого игрока.
Дилемма заключенного
Это, наверное, самая известная игра в литературе. На рисунке ниже представлена его матрица выплат. Матрица выплат стоит тысячи слов. Опытному глазу достаточно предоставить всю информацию, необходимую для описания игры. Но давайте будем немного менее лаконичными.
Полиция арестовывает двух преступников, преступника А и преступника Б. Несмотря на свою печально известность, преступники не могут быть заключены в тюрьму за расследуемое преступление из-за отсутствия доказательств. Но их можно задержать за меньшее обвинение.
Срок их заключения будет зависеть от того, что они скажут в комнате для допросов, что дает начало игре. Каждому преступнику (игроку) дается возможность либо промолчать, либо стучать против другого преступника (игрока). Матрица выплат показывает, на сколько лет в тюрьме будет находиться каждый игрок в зависимости от результата. Например, если игрок A хранит молчание, а игрок B настучивает на них, игрок A будет служить 3 года (-3), а игрок B не будет служить ни одного (0).
Если вы внимательно изучите матрицу выплат, вы обнаружите, что логическое действие игрока состоит в том, чтобы предать другого человека или, с точки зрения теории игр, предательство является доминирующей стратегией. Это приведет к равновесию по Нэшу в игре, где каждый игрок имеет выигрыш -2.
Что-то кажется странным? Да, по крайней мере, должно. Если бы оба игрока каким-то образом согласились хранить молчание, они оба получили бы более высокую награду - -1. Дилемма заключенного - это пример игры, в которой рациональность приводит к худшему результату, чем сотрудничество.
Некоторые исторические замечания
Теория игр зародилась в экономике, но сегодня является междисциплинарной областью изучения. Ее отец, Джон фон Нейман (вы заметите, что у Джонса серьезные карьерные перспективы в этой области), был первым, кто дал строгую формулировку общепринятому понятию игры. Он ограничил свои исследования играми двух игроков, так как их было легче анализировать.
Затем он в соавторстве с Оскаром Моргенштерном написал книгу, которая заложила основы теории ожидаемой полезности и сформировала курс теории игр. Примерно в то же время Джон Нэш представил концепцию равновесия по Нэшу, которая помогает описать результат игры.
Обучение с подкреплением
Не потребовалось много времени, чтобы осознать, насколько обширными могут быть приложения теории игр. От игр до биологии, философии и, подождите, искусственного интеллекта. В настоящее время теория игр тесно связана с условиями, в которых несколько игроков обучаются посредством подкрепления, и эта область называется многоагентным обучением с подкреплением. Примерами приложений в этом случае являются команды роботов, где каждый игрок должен научиться вести себя в пользу своей команды.
Некоторые полезные термины
- Агент: эквивалент игрока.
- Вознаграждение: эквивалент выплаты.
- Состояние: вся информация, необходимая для описания ситуации, в которой находится агент.
- Действие: эквивалент хода в игре.
- Политика. Подобно стратегии, она определяет действие, которое агент будет выполнять, когда в определенных состояниях
- Среда: все, с чем агент взаимодействует во время обучения.
Приложения
Представьте себе следующий сценарий: команда дронов запускается в лес, чтобы предсказать и определить местонахождение пожара достаточно рано, чтобы пожарные смогли отреагировать. Дроны автономны и должны исследовать лес, узнавать, какие условия могут вызвать пожар, и взаимодействовать друг с другом, чтобы покрывать обширные участки леса, используя небольшую батарею и связь.
Это приложение относится к области мониторинга окружающей среды, где ИИ может использовать свои навыки прогнозирования вмешательства человека. В технологическом мире, который становится все более сложным, а физический мир находится под угрозой, мы можем перефразировать цитату Киплинга следующим образом: Человек не может быть везде, поэтому он создал дроны.
Еще одна интересная область применения - децентрализованные архитектуры. Такие технологии, как Интернет вещей и Блокчейн, создают огромные сети. Информация и обработка распределяются между различными физическими объектами, что, как было признано, обеспечивает конфиденциальность, эффективность и демократизацию.
Независимо от того, хотите ли вы использовать датчики для минимизации энергопотребления в домашних хозяйствах страны или заменить банковскую систему, децентрализация - это новая привлекательность.
Однако сделать эти сети умными - непростая задача, поскольку большинство алгоритмов искусственного интеллекта, которыми мы гордимся, требуют больших объемов данных и вычислений. Алгоритмы обучения с подкреплением могут использоваться для эффективной обработки данных и адаптации сети к изменениям в ее среде. В этом случае интересно и с точки зрения общей эффективности изучить, как отдельные алгоритмы будут взаимодействовать.
Не просто игра
Заманчиво переносить проблемы ИИ в простые игры вроде дилеммы заключенного. Это обычная практика при тестировании новых методов, поскольку она предлагает дешевую в вычислительном отношении и интуитивно понятную тестовую среду. Тем не менее, важно не игнорировать влияние, которое практические характеристики проблемы, такие как шум, задержки и ограниченная память, оказывают на алгоритм.
Возможно, наиболее вводящим в заблуждение предположением в исследованиях искусственного интеллекта является представление взаимодействия с повторяющимися статическими играми. Например, алгоритм может применять игру дилеммы заключенного каждый раз, когда он хочет принять решение, формулировка, которая предполагает, что агент не узнал или не изменился на этом пути. Но как насчет влияния обучения на поведение агента? Не повлияет ли взаимодействие с другими на его стратегию?
Исследования в этой области были сосредоточены на эволюции сотрудничества, и Роберт Аксельрод изучил оптимальные стратегии, которые возникают в повторяющейся версии дилеммы заключенного. Турниры, организованные Аксельродом, показали, что стратегии, которые адаптируются со временем и взаимодействием, даже такие простые, как может показаться око за око, очень эффективны. Сообщество ИИ недавно исследовало обучение в рамках дилеммы последовательного заключенного. ,, но исследования в этой области все еще преждевременны.
Что отличает многоагентное обучение от обучения с одним агентом , так это повышенная сложность. Обучение одной глубокой нейронной сети уже достаточно проблематично, в то время как добавление новых сетей в качестве частей агентов значительно усложняет задачу.
Менее очевидной, но более важной проблемой является отсутствие теоретических свойств для такого рода проблем. Одноагентное обучение с подкреплением - хорошо изученная область, поскольку Ричард Беллман и Кристофер Уоткинс предложили алгоритмы и доказательства, необходимые для изучения. Однако в случае с несколькими агентами доказательства теряют свою силу.
Просто чтобы проиллюстрировать некоторые из возникающих непостижимых трудностей: агент выполняет алгоритм обучения, чтобы узнать, как оптимально реагировать на окружающую среду. В нашем случае среда включает в себя других агентов, которые также выполняют алгоритм обучения. Таким образом, алгоритм должен учитывать эффект своего действия, прежде чем действовать.
Первые проблемы
Проблемы начинаются там, где зародилась теория игр: в экономике. Начнем с некоторых предположений, сделанных при изучении системы в рамках классической теории игр.
Рациональность: обычно в теории игр и для получения равновесия по Нэшу предполагается совершенная рациональность. Это примерно означает, что агенты всегда действуют ради самих себя.
Полная информация: каждый агент знает все об игре, включая правила, то, что знают другие игроки, и каковы их стратегии.
Общее знание: существует общее знание факта p в группе агентов, когда: все агенты знают p, все они знают, что все агенты знают p, все они знают, что все они знают, что все агенты знают p, и так далее до бесконечности . Есть интересные загадки, вроде голубоглазых островитян, которые описывают влияние общих знаний на проблему.
В 1986 году Кенн Эрроу выразил сомнения в отношении классической теории игр.
В этой статье я хочу раскрыть некоторые смыслы, в которых гипотеза рациональности используется в экономической теории. В частности, я хочу подчеркнуть, что рациональность - это не только свойство индивида, хотя обычно ее так преподносят. Скорее, он черпает не только свою силу, но и само значение из социального контекста, в который он встроен. Это наиболее вероятно при идеальных условиях. Когда эти условия перестают выполняться, предположения о рациональности становятся натянутыми и, возможно, даже внутренне противоречивыми.
Если вы обнаружите, что Arrow немного резок с классической теорией игр, насколько рациональными, по вашему мнению, были ваши последние покупки? Или сколько осознанности и усилий вы вложили сегодня в свой обед?
Но Эрроу не так сильно беспокоит предположение о рациональности. Он обеспокоен последствиями этого. Чтобы агент был рациональным, вам необходимо предоставить ему всю информацию, необходимую для принятия решений. Это требует всеведущих игроков, что плохо с двух сторон: во-первых, это создает непрактичные требования к хранению и обработке информации об игроках. Во-вторых, теория игр больше не является теорией игр, поскольку вы можете заменить всех игроков центральным правителем (и где в этом веселье?).
Еще один интересный момент - ценность информации с этой точки зрения. Мы уже обсуждали, что обладать всей информацией невозможно. Но как насчет того, чтобы предположить игроков с ограниченными знаниями? Это поможет?
Вы можете спросить любого, кто занимается этой областью, но достаточно сказать, что оптимизация в условиях неопределенности - непростая задача. Да, все еще существует старое-доброе равновесие по Нэшу. Проблема в том, что они бесконечны. Теория игр не дает аргументов для их оценки. Так что, даже если вы его достигнете, вы не должны делать это таким большим делом.
Проблемы с обучением с подкреплением
К этому моменту вы должны подозревать, что приложения ИИ намного сложнее, чем примеры классической теории игр. Просто упомяну несколько препятствий на пути применения подхода равновесия Нэша в роботизированном приложении: представьте, что вы капитан команды роботов, играющих в футбол в RoboCup. Насколько быстры, сильны и умны ваши игроки и ваши противники? Какие стратегии использует команда соперника? Как следует вознаграждать своих игроков? Является ли гол единственной причиной для поздравления, или аплодисменты также улучшат поведение команды? Ясно, что простое знакомство с правилами футбола не принесет вам победы.
Если теория игр вызывает споры на протяжении десятилетий, если она основана на нереалистичных предположениях и для реалистичных задач, если она предлагает сложные и малоизученные решения, почему мы все еще идем к ней? Совершенно очевидно, что это единственное, что у нас есть, когда дело доходит до группового мышления. Если бы мы действительно поняли, как группы взаимодействуют и сотрудничают для достижения своих целей, психология и политика были бы намного яснее.
Исследователи в области многоагентного обучения с подкреплением либо полностью обсуждают теоретические свойства своих алгоритмов (и, тем не менее, часто демонстрируют хорошие результаты), либо традиционно изучают существование равновесий по Нэшу. Последний подход кажется молодому исследователю в этой области как борьба за доказательство при строгих, нереалистичных предположениях теоретического существования решений, которые - будучи бесконечными и сомнительной ценностью - никогда не будут использованы на практике.
Эволюционная теория игр
Эволюционная теория игр зародилась не недавно, но признание ее далеко идущих приложений в области ИИ потребовало много времени. Возникнув в биологии, она была введена в 1973 году Джоном М. Смитом и Джорджем Р. Прайсом в качестве альтернативы классической теории игр. Изменения настолько глубоки, что можно говорить о совершенно новом подходе.
Предметом рассуждений является уже не сам игрок, а совокупность игроков. Таким образом, вероятностные стратегии определяются как процент игроков, которые делают выбор, а не вероятность того, что один игрок выберет действие, как в классической теории игр. Это устраняет необходимость в рациональных, всеведущих агентах, поскольку стратегии развиваются как модели поведения. Процесс эволюции напоминает дарвиновскую теорию. Игроки размножаются, следуя принципам выживания наиболее приспособленных и случайных мутаций, и их можно элегантно описать набором дифференциальных уравнений, называемых динамикой репликатора.
На иллюстрации ниже мы видим три важные части этой системы. Популяция представляет собой команду агентов и характеризуется сочетанием стратегий. Правила игры определяют выплаты населения, которые также можно рассматривать как значения приспособленности эволюционного алгоритма. Наконец, правила репликатора описывают, как популяция будет развиваться на основе значений приспособленности и математических свойств процесса эволюции.
Идея равновесия по Нэшу и стремление к нему заменяются эволюционно стабильными стратегиями . Стратегия может иметь эту характеристику, если она невосприимчива к вторжению со стороны популяции агентов, которые следуют другой стратегии, при условии, что вторгающееся население невелико. Таким образом, поведение команды можно изучать в хорошо изученной области устойчивости динамических систем, такой как устойчивость по Ляпунову.
Достижение равновесия требует неравновесного процесса. Что означает рациональное поведение при наличии неравновесия? Размышляют ли люди о процессе уравновешивания? Если да, может ли нарушение равновесия в некотором смысле рассматриваться как равновесный процесс более высокого порядка?
В приведенном выше отрывке Стрела, кажется, изо всех сил пытается определить динамические свойства игры. Может ли эволюционная теория игр стать ответом на его вопросы?
Совсем недавно в рамках этого нового подхода были изучены известные алгоритмы обучения с подкреплением, такие как Q-learning, и были сделаны важные выводы. Как использовать этот новый инструмент, в конечном итоге зависит от приложения.
Мы можем следовать прямому подходу, чтобы получить динамическую модель алгоритма обучения. Или наоборот, когда мы начинаем с некоторых желаемых динамических свойств и разрабатываем алгоритм обучения, который их демонстрирует.
Мы можем использовать динамику репликатора описательно, чтобы визуализировать конвергенцию. Или предписательно настроить алгоритм так, чтобы он сходился к оптимальным решениям. Последнее может значительно снизить сложность обучения глубоких сетей для решения сложных задач, с которыми мы сталкиваемся сегодня, за счет устранения необходимости слепой настройки.
Заключение
Нетрудно проследить, когда и почему пути теории игр и ИИ стали запутанными. Однако труднее упустить из виду ограничения, с которыми приходится сталкиваться ИИ, и в частности многоагентному обучению с подкреплением, при следовании классическим теоретико-игровым подходам.
Эволюционная теория игр звучит многообещающе, предлагая как теоретические инструменты, так и практические преимущества, но мы ничего не узнаем, пока не попробуем. В этом случае эволюция возникнет не естественным образом, а в результате сознательной борьбы исследовательского сообщества за улучшение. Но разве не в этом суть эволюции?
Требуются определенные усилия, чтобы отклониться от того, куда вас толкает инерция, но обучение с подкреплением, несмотря на общие успехи в области ИИ, серьезно нуждается в подъеме.
