Глубокое обучение с подкреплением виртуального менеджера в игре против неэффективности

DQN использовался для обучения AlphaGo проигрыванием тысяч партий в одиночку. Когда это ещё не было модным, в 2015 году, предчувствуя развитие данного тренда, руководство Phobos в лице Алексея Спасского, заказало отделу Research & Development провести исследование. Необходимо было рассмотреть существующие технологий машинного обучения на предмет возможности использования их для автоматизации победы в играх управленческих. Таким образом, в данной статье пойдёт речь о проектирование самообучающегося алгоритма в игре виртуального управленца против живого коллектива за повышение производительности.

Прикладная задача анализа данных машинного обучения классически имеет следующие этапы решения:

• формулировка проблемы;
• сбор данных;
• подготовка данных;
• формулировка гипотез;
• построение модели;
• валидация модели;
• представление результатов.

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

Выбор алгоритма

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

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

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

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

Гипотеза и модель

Чтобы эффективно использовать Q-learning для управления коллективом, мы должны максимально уменьшить размерность состояний среды и действий.
Наши решения:

• Первое инженерное решение заключалось в том, чтобы представить управленческую деятельность в виде совокупности мини-игр. Каждая из них имеет дискретные количества состояний и действий таких, что порядок комбинаций сопоставим с успешно решенными игровыми задачами. Таким образом, не нужно строить алгоритм, который будет искать оптимальную управляющую стратегию в многомерном пространстве, но множество агентов превосходят игрока-человека в тактических играх. Пример такой игры — управление задачей в YouTrack. Состояния среды (грубо) — время в работе и статус, а действия — открытие, переоткрытие таска, назначение ответственного. Подробнее ниже.

Пример онлайн-обучения простой игре:
https://cs.stanford.edu/people/karpathy/convnetjs/demo/rldemo.html

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

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

На схеме представлены состояния трёх игровых сред для трёх агентов, управляющих ходом работы над таском.

Состояния:

• Задача зарегистрирована (backlog);
• Задача открыта;
• В работе;
• Разработка завершена, задача открыта для тестирования (QA);
• Открыта для тестирования;
• Тестируется;
• Готова, протестирована;
• Закрыта.

Список действий для каждого из трёх агентов свой. Project Manager — Agent назначает исполнителя и тестировщика, время и приоритет задачи. Агенты, работающие с Dev и QA, персональны для каждого исполнителя и тестировщика. Если происходит переход таска дальше, агенты получают награды, если таск возвращается назад — наказания.

Наибольшую награду все агенты получают при закрытии таска. Также для Q-обучения DF и LF (фактор дисконтирования и обучения соответственно) подбирались таким образом, чтобы агенты были ориентированы именно на закрытие таска. Расчёт подкрепления в общем случае происходит по формуле оптимального управления учитывающей, помимо прочего, разницу в оценке времени и реальными затратами, количество возвратов задачи итд. Плюсом данного решения является его возможность масштабируемости на больший коллектив.

Заключение

Железо на котором выполнялись расчеты — GeForce GTX 1080.

Для приведённой выше мини-игры с постановкой и ведением задачи в Youtrack, управляющие функции сошлись на значения выше средних (продуктивность сотрудника возросла относительно работы с менеджером-человеком) для 3 человек из 5. Общая производительность (в часах) выросла почти вдвое. Довольных экспериментом сотрудников из тестовой группы не было; недовольных 4; один воздержался от оценок.

Тем не менее, мы для себя сделали выводы, что для применения метода «на бою» необходимо вносить в модель экспертные знания по психологии. Общая продолжительность разработки и тестирования — более года.