Требуются эволюции: теория игр и AI

1656620439 trebuyutsya evolyuczii teoriya igr i ai

Елена Нисиоти

pzctD1W7x3JbZ8LbZMgRLAQhDMOR4qEMZWu1

Искусственный интеллект (ИИ) полон вопросов, на которые невозможно ответить, и ответов, которые невозможно назначить к правильным вопросам. В прошлом он платил за свою устойчивость к неправильным практикам периодами стагнации, известными как зима AI. Однако календарь ИИ только наступил весной, а программы преуспевают.

Тем не менее, существует отрасль ИИ, которой долго пренебрегали. Речь идет об обучении с подкреплением, которое недавно показало впечатляющие результаты в таких играх как AlphaGo и Atari. Но давайте будем честны: это не были победы в учебе с подкреплением. В этих случаях глубже стали глубокие нейронные сети, а не наше понимание обучения с подкреплением, которое сохраняет глубину, достигнутую десятилетиями назад.

Еще хуже случай обучения с подкреплением, когда его применяют к проблемам реальной жизни. Если научить работа балансировать на веревке звучит тяжело, попробуйте научить команду роботов выигрывать футбольный матч или команду дронов, чтобы следить за движущейся целью.

Прежде чем потерять ветку или, что еще хуже, дерево, мы должны обострить наше понимание этих применений. Теория игр является наиболее распространенным подходом к изучению команд игроков, имеющих общие цели. Это может предоставить нам инструменты для управления алгоритмами обучения в этих настройках.

Но давайте посмотрим, почему общий подход не является подходом здравого смысла.

Уничтожить ошибку — это такая же хорошая услуга, как иногда даже лучше, чем установление новой истины или факта. – Чарльз Дарвин

Сначала загрязним руки некоторой терминологией и основами этих сфер.

Теория игр

Некоторые полезные термины

  • Игра: как игры в общем смысле, это может быть любая среда, где игроки выполняют действия и результат будет зависеть от них.
  • Игрок: лицо, принимающее стратегические решения в игре.
  • Стратегия: полный план действий игрока, учитывая совокупность обстоятельств, которые могут возникнуть в игре.
  • Расплачиваться: выигрыш, который получает от достижения конкретного результата игры.
  • Равновесие: точка в игре, когда оба игрока приняли свои решения и достигнут результат.
  • Равновесие Нэша: равновесие, в котором ни один игрок не может получить преимущество, изменив свою стратегию, если стратегии других игроков остаются неизменными.
  • Доминирующая стратегия: возникает, когда одна стратегия лучше другой для одного игрока, независимо от того, как играют его оппоненты.

Дилемма заключенного

Это, пожалуй, самая известная игра в литературе. На рисунке ниже представлена ​​его матрица выплат. Теперь матрица выплат стоит тысячи слов. Опытному глазу достаточно предоставить всю информацию, необходимую для описания игры. Но давайте будем чуть менее лаконичными.

3C9rRuM6lrhidno7Ihm5g82g2CLkNPSMrD0R
Матрица выплат дилеммы заключенного

Полиция арестовывает двух преступников, преступника А и преступника Б. Хотя преступники достаточно печально известны, они не могут быть заключены за расследуемое преступление из-за отсутствия доказательств. Но их можно задержать за меньшую плату.

Продолжительность их заключения будет зависеть от того, что они скажут в допросной комнате, ведущей к игре. Каждый преступник (игрок) имеет возможность либо умолчать, либо донести до другого преступника (игрока). Матрица выплат показывает, сколько лет каждый игрок будет заключён в зависимости от результата. К примеру, если игрок А молчит, а игрок В достучал их, игрок А будет служить 3 года (-3), а игрок В не будет служить ни одного (0).

Если вы внимательно проанализируете матрицу выплат, то увидите, что логическое действие игрока состоит в том, чтобы изменить другому человеку или, говоря теоретикой игры, предательство является доминирующей стратегией. Это приведет к равновесию Нэша в игре, где каждый игрок имеет выплату –2.

Чувствуется ли что-то странное? Да, или по крайней мере, так должно быть. Если оба игрока каким-то образом согласились молчать, они оба получат высшее вознаграждение -1. Дилемма заключенного является примером игры, где рациональность приводит к худшему результату, чем сотрудничество.

Теория игр возникла в экономике, но сегодня междисциплинарной сферой исследования. Ее отец, Джон фон Нейман (вы заметите, что Джонс имеет серьезные карьерные перспективы в этой сфере), первым дал строгую формулировку общепринятому представлению об игре. Он ограничил обучение играм двух игроков, поскольку их было легче анализировать.

Затем он вместе с Оскаром Моргенштерном написал книгу, которая заложила основы теории ожидаемой полезности и сформировала курс теории игр. Приблизительно в то время Джон Нэш ввел концепцию равновесия Нэша, помогающую описать результат игры.

Обучение с подкреплением

Не потребовалось много времени, чтобы понять, насколько широким может быть применение теории игр. От игр до биологии, философии и, ждите, искусственного интеллекта. Сегодня теория игр тесно связана с настройками, где несколько игроков учатся посредством подкрепления, называемого обучением с подкреплением с несколькими агентами. Примером применения в этом случае являются команды роботов, где каждый игрок должен научиться вести себя в пользу своей команды.

Некоторые полезные термины

  • Агент: эквивалент игрока.
  • Награда: эквивалентный выплате.
  • состояние: вся информация, необходимая для описания ситуации, в которой находится агент.
  • Действие: эквивалент хода в игре.
  • Политика: Подобно стратегии он определяет действие, которое агент осуществит в определенных состояниях
  • Окружающая среда: все, с чем агент взаимодействует при обучении.

Приложения

Представьте следующий сценарий: команда беспилотников запускается в лес, чтобы спрогнозировать и локализовать пожар достаточно рано, чтобы пожарные могли среагировать. Беспилотники автономны и должны исследовать лес, узнавать, какие условия могут повлечь за собой пожар, и сотрудничать друг с другом, чтобы охватить широкие территории леса, используя небольшое количество аккумуляторов и связи.

Эта программа относится к области мониторинга окружающей среды, где ИИ может предоставить свои навыки прогнозирования человеческому вмешательству. В технологическом мире, который становится все сложнее, а физический мир под угрозой, мы можем перефразировать цитату Киплинга: «Человек не мог быть везде, и потому он создал дроны».

Еще одной интересной областью применения являются децентрализованные архитектуры. Такие технологии, как Интернет вещей и блокчейн, создают огромные сети. Информация и обработка распределяются между разными физическими лицами, что, как было признано, обеспечивает конфиденциальность, эффективность и демократизацию.

Независимо от того, хотите ли вы использовать датчики, чтобы минимизировать потребление энергии в домохозяйствах страны, или заменить банковскую систему, децентрализованная – это новая сексуальность.

Однако сделать эти сети разумными является сложной задачей, поскольку большинство алгоритмов ИИ, которыми мы гордимся, нуждаются в данных и вычислениях. Алгоритмы обучения с подкреплением можно использовать для эффективной обработки данных и предоставления адаптивной сети к изменениям в своей среде. В этом случае интересно и в пользу общей эффективности изучить, как будут взаимодействовать отдельные алгоритмы.

RcvtMhf4sDKByN00Jncb2s9aMCNZ5cB39fmv
Глубокое или коллективное обучение? Исследования ИИ базируют свой урожай на все более глубоких сетях, но возможно ответы на сложные проблемы поступают от коллективных знаний, а не от глубоко укорененных индивидов. Мы скучали по лесу?

Не просто игра

Перевод проблем ИИ на простые игры, как дилемма заключенного, соблазнительный. Это обычная практика при тестировании новых методов, поскольку предлагает дешевый и интуитивно понятный тестовый стенд. Тем не менее, важно не игнорировать влияние, которое практические характеристики задачи, такие как шум, задержки и конечная память, имеют на алгоритм.

Пожалуй, самое обманчивое предположение в исследовании ИИ – это представление взаимодействия с повторяющимися статическими играми. Например, алгоритм может применять игру с дилеммой заключенного всякий раз, когда он хочет принять решение, формулировка, предполагающая, что агент не научился или не изменился на этом пути. Но как насчет влияния обучения на поведение агента? Не повлияет ли взаимодействие с другими на его стратегию?

Исследования этой области были сосредоточены на эволюции сотрудничества, а Роберт Аксельрод изучал оптимальные стратегии, возникающие в повторяющейся версии дилеммы заключенного. Турниры, организованные Аксельродом, показали, что стратегии, которые адаптируются со временем и взаимодействием, даже настолько просты, как это может показаться, очень эффективны. Сообщество ИИ недавно исследовало обучение с помощью последовательная дилемма заключенного, но исследования в этой области пока еще в раннем состоянии.

Чем отличается многоагент от одноагентного обучение является повышенной сложностью. Обучение одной глубокой нейронной сети уже достаточно трудно, а добавление новых сетей, как частей агентов, значительно усложняет проблему.

Одной менее очевидной, но более важной проблемой является отсутствие теоретических свойств такого рода задач. Обучение по подкреплению с одним агентом – это хорошо понятная область, поскольку Ричард Беллман и Кристофер Уоткинс предложили алгоритмы и доказательства, необходимые для обучения. Однако в случае с многими агентами доказательства теряют свою действительность.

Просто чтобы проиллюстрировать некоторые непонятные возникающие трудности: агент выполняет алгоритм обучения, чтобы научиться оптимально реагировать на окружающую среду. В нашем случае среда включает другие агенты, также выполняющие алгоритм обучения. Таким образом, алгоритм должен рассмотреть эффект своего действия, прежде чем действовать.

Ранние беспокойства

Беспокойство начинается там, где началась теория игр: в экономике. Начнём с некоторых предположений, сделанных при изучении системы в рамках классической теории игр.

Рациональность: как правило, в теории игр, и для того, чтобы вывести равновесие Нэша, предполагается совершенная рациональность. Это примерно означает, что агенты всегда действуют ради себя.

Полная информация: каждый агент знает все об игре, включая правила, которые знают другие игроки и каковы их стратегии.

Общие знания: общеизвестны факта с в группе агентов, когда: все агенты знают сони все знают, что знают все агенты сони все знают, что все знают, что знают все агенты си так дальше до бесконечности. Есть интересные головоломки, такие как голубоглазые островяне, описывающие влияние общеизвестных на проблему.

В 1986 году Кенн Эрроу выразил свои оговорки относительно классической теории игр.

В этой работе я хочу раскрыть некоторые смыслы, в которых гипотеза рациональности используется в экономической теории. В частности, хочу подчеркнуть, что рациональность не является свойством отдельной личности, хотя обычно ее так представляют. Напротив, он набирает не только свою силу, но и сам смысл из социального контекста, в который он встроен. Это наиболее вероятно при идеальных условиях. Когда эти условия перестают выполняться, предположения о рациональности становятся напряженными и, возможно, даже противоречивыми.

Если вы считаете, что Arrow немного строго относится к классической теории игр, насколько рациональными, по вашему мнению, были ваши последние покупки? Или сколько сознаний и усилий вы приложили сегодня к своей трапезе?

Но Стрелка не так сильно волнует предположение о рациональности. Его беспокоят последствия этого. Чтобы агент был рациональным, вам нужно предоставить ему всю информацию, необходимую для принятия решений. Это требует всезнающих игроков, что плохо в двух аспектах: во-первых, это создает непрактичные требования к хранению и обработке информации игроков. Во-вторых, теория игр больше не является теория игрпоскольку вы можете заменить всех игроков центральной линейкой (и где в этом весело?).

Ценность информации с этой точки зрения является еще одним интересным моментом. Мы уже обсуждали, что владеть всей информацией невозможно. Но как насчет игроков с ограниченными знаниями? Это поможет?

Вы можете спросить любого, кто занимается этой сферой, но достаточно сказать, что оптимизация в условиях неопределенности тяжелая. Да, все еще существует старое доброе равновесие Нэша. Проблема в том, что они нескончаемы. Теория игр не дает вам аргументов для их оценки. Итак, даже если вы достигнете такого, вы не должны делать это таким большим.

Проблемы обучения с подкреплением

К этому моменту вы должны подозревать, что программы AI гораздо сложнее, чем примеры, которыми занимается классическая теория игр. Вспомним лишь несколько препятствий на пути применения подхода к равновесию Нэша в робототехническом приложении: представьте себе, что вы капитан команды роботов, играющих в футбол в RoboCup. Насколько быстры, сильны и умны ваши игроки и соперники? Какие стратегии употребляет команда соперника? Как вы должны вознаграждать своих игроков? Является ли гол единственной причиной для поздравлений, аплодирование хорошему пасу также улучшит поведение команды? Очевидно, просто ознакомление с правилами футбола не выиграет вам игру.

Если теория игр вызвала дебаты в течение десятилетий, если она была основана на нереалистических предположениях и, для реалистических задач, если она предлагает сложные и малопонятные решения, почему мы все еще идем на это? Ну, разумеется, это единственное, что у нас есть, когда дело доходит до группового соображения. Если бы мы действительно поняли, как группы взаимодействуют и сотрудничают для достижения своих целей, психология и политика были бы гораздо понятнее.

Исследователи в области многоагентного обучения с подкреплением либо полностью обсуждают теоретические свойства своих алгоритмов (и тем не менее часто демонстрируют хорошие результаты), либо традиционно изучают существование равновесия Нэша. Последний подход кажется глазам молодого исследователя в этой области как борьба за доказательство, строгих, нереалистичных предположений, теоретического существования решений, которые — будучи бесконечными и имеют сомнительную ценность — никогда не будут использованы на практике.

Эволюционная теория игр

Теория эволюционных игр зародилась не недавно, но ее дальновидное применение в области ИИ потребовало много времени, чтобы признать. Возникая в биологии, она была введена в 1973 году Джоном М. Смитом и Джорджем Р. Прайсом как альтернатива классической теории игр. Изменения настолько глубоки, что мы можем говорить о совершенно новом подходе.

Предметом рассуждений есть уже не сам игрок, а популяция игроков. Таким образом, вероятностные стратегии определяются как процент игроков, делающих выбор, а не вероятность того, что один игрок выберет действие, как в классической теории игр. Это устраняет необходимость рациональных, всезнающих агентов, поскольку стратегии развиваются как модели поведения. Процесс эволюции напоминает теорию Дарвина. Игроки воспроизводят, соблюдая принципы выживания сильнейших и случайных мутаций, и могут быть элегантно описаны набором дифференциальных уравнений, которые называются динамика репликатора.

На иллюстрации ниже мы находим три важные части этой системы. Популяция представляет команду агентов и характеризуется сочетанием стратегий. Правила игры определяют выплаты популяции, которые можно рассматривать как значение пригодности эволюционного алгоритма. Наконец правила репликатора описывают, как будет развиваться популяция на основе значений пригодности и математических свойств процесса эволюции.

pcZhSDCQhuD1w4AMlmVxdNV-M0cymDbheIM8
Автор изображения: автор HowieKor[CCBY-SA30(сWikimediaCommons[CCBY-SA30(fromWikimediaCommons)[CCBY-SA30(зWikimediaCommons[CCBY-SA30(fromWikimediaCommons

Понятие и стремление к равновесию Нэша заменено на эволюционно стабильные стратегии. Стратегия может иметь такую ​​характеристику, если она невосприимчива к вторжению популяции агентов, придерживающихся другой стратегии, при условии, что популяция вторжения невелика. Таким образом, поведение команды можно изучать в рамках хорошо понятной области устойчивости динамических систем, например устойчивости по Ляпунову.

Для достижения равновесия необходим процесс нарушения равновесия. Что означает рациональное поведение при наличии неравновесия? Спеккулируют ли люди на процессе уравновешивания? Если да, то можно ли считать нарушение равновесия в определенном смысле равновесным процессом высшего порядка?

В вышеприведенном отрывке Стрелка, кажется, пытается определить динамические свойства игры. Может ли теория эволюционных игр ответить на его вопросы?

Совсем недавно по этому новому подходу были изучены известные алгоритмы обучения с подкреплением, такие как Q-обучение, и были сделаны важные выводы. Как используется этот новый инструмент зависит от программы.

Мы можем придерживаться прямого подхода, чтобы получить динамическую модель алгоритма обучения. Или обратное, когда мы исходим из некоторых желаемых динамических свойств и разрабатываем демонстрирующий их алгоритм обучения.

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

Вывод

Нетрудно проследить, когда и почему пути теории игр и ИИ запутались. Но труднее не заметить ограничений, с которыми приходится столкнуться ИИ, и, в частности, многоагентное обучение с подкреплением, соблюдая классические подходы теории игр.

Эволюционная теория игр звучит многообещающе, предлагая как теоретические инструменты, так и практические преимущества, но мы этого не узнаем, пока не попробуем. В этом случае эволюция возникнет не естественным путем, а из сознательной борьбы исследовательского сообщества за усовершенствование. Но разве это не сущность эволюции?

Нужны определенные усилия, чтобы отклониться от того, где вас толкает инерция, но обучение с подкреплением, несмотря на общие успехи в ИИ, требует серьезного подъема.

Добавить комментарий

Ваш адрес email не будет опубликован.