Інженери з лабораторії штучного інтелекту Uber AI Labs розробили сімейство алгоритмів Go-Explore, заснованих на навчанні з підкріпленням, які перевершують за ефективністю більшість існуючих алгоритмів у тестах на іграх Atari 1980-х років. Go-Explore пройшов 11 вважаються найбільш складними для навчання з підкріпленням ігор, включаючи Montezuma's Revenge і Pitfall, обійшовши за набраними в них очками більшість інших алгоритмів і середній людський результат. Основною особливістю Go-Explore стала здатність запам'ятовувати попередні перспективні стани і повертатися в них, здійснюючи звідти подальшу розвідку, що дозволяє підвищити ефективність алгоритму навчання з підкріпленням. Розробники продемонстрували можливе практичне застосування Go-Explore для робототехніки в завданні управління маніпулятором робота. Крім того в майбутньому алгоритм може бути корисний у вирішенні безлічі інших завдань від обробки природних мов до створення нових ліків, йдеться в роботі, опублікованій в журналі
Навчання з підкріпленням - один з варіантів машинного навчання, в якому програма або частина алгоритму, звана агентом, вчиться взаємодіяти з навколишнім її середовищем. Дії агента призводять до відгуку середовища, яке реагує на прийняті рішення агента зміною значення величини, що відіграє роль нагороди. Одні дії її збільшують, і будуть вважатися більш вигідними з точки зору агента, а інші - зменшують величину винагороди, а отже, будуть розцінюватися агентом як небажані. Таким чином, задаючи функцію корисності, що визначає нагороду агента за його дії, можна навчити його взаємодіяти з середовищем так, щоб максимізувати цю функцію, тобто агент буде воліти виконувати комбінації дій, що дають найвищу сумарну нагороду.
Алгоритми, засновані на цьому підході, показують значні успіхи останнім часом. Так, наприклад самонавчальні програми сімейства AlphaGo і AlphaGo Zero від компанії DeepMind здатні обігравати кращих гравців в настільних іграх го, сегі і шахах, а алгоритм від OpenAI перемагає професійних гравців в Dota 2.
Системи, засновані на навчанні з підкріпленням, можуть навчитися не тільки грати в ігри, а й потенційно виконувати будь-які завдання. Однак часто дуже важко підібрати правильну функцію корисності, від якої багато в чому залежить ефективність алгоритму. Наприклад, для того щоб направити робота з одного кінця кімнати в інший до дверей, можна задати функцію корисності, яка буде винагороджувати робота, коли він підійде впритул до дверей, але така функція корисності буде занадто «розрідженою», тобто винагорода буде надходити занадто рідко. Якщо для досягнення мети необхідно виконати багато дій і робот не отримує постійний зворотний зв'язок, то він не зможе зрозуміти які дії привели його до успіху, а які заважають досягненню мети. З іншого боку, якщо в якості нагороди вибрати, наприклад, відстань до дверей, то незважаючи на безперервний зворотний зв'язок, винагороджуючий алгоритм за наближення до об'єкта, наївне прямування по найкоротшому маршруту може привести робота в глухий кут або до зіткнення з перешкодою.
Розробники з лабораторії штучного інтелекту компанії Uber під керівництвом Джеффа Клюна (Jeff Clune) створили сімейство алгоритмів навчання з підкріпленням під назвою Go-Explore, які менш схильні до проблем рідкісної винагороди і неправильних локальних мінімумів, завдяки здатності запам'ятовувати попередні перспективні стани і повертатися до них. Як вважають розробники, це дозволяє алгоритму більш ефективно дослідити простір станів і вирішує дві ключові проблеми навчання з підкріпленням. Перша полягає у втраті алгоритмом здатності повертатися до більш ранніх вже пройдених станів, навіть незважаючи на їх високу «перспективність», тобто великої ймовірності привести до нових, недоступних раніше областей у процесі дослідження. Алгоритм, обстежуючи одну область може раптово переключитися на дослідження іншої і забути дорогу назад. Друга проблема пов'язана з тим, що сам процес дослідження може перешкоджати поверненню до більш ранніх станів алгоритму, відводячи його далеко від стартової точки через безліч випадкових дій.
В якості середовища для тестування можливостей свого алгоритму інженери Uber використовували популярний бенчмарк, що складається з класичних ігор Atari, відібравши з них найбільш складні і раніше погано піддавалися алгоритмам машинного навчання, наприклад, стали вже еталоном Montezuma's Revenge і Pitfall. Обидві ці гри відрізняються особливою складністю для алгоритмів навчання з підкріпленням через дуже розріджену винагороду. Тобто між моментами отримання агентом винагороди, що підкріплює правильність його дій, алгоритм може вчинити сотні дій, в результаті чого буде важко зрозуміти, які ж дії призвели до успіху або невдачі.
Щоб обійти цю проблему, Go-Explore запам'ятовує статки, які він відвідує в середовищі, щоб повернутися до них пізніше. Процес побудови «архіву» станів відбувається ітеративно. Оскільки станів занадто багато, щоб зберігати кожне з них окремо в явному вигляді, алгоритм групує схожі стани в комірки. Спочатку циклу Go-Explore вибирає зі збережених комірок, на підставі присвоєних їм вагам і віддаючи перевагу нещодавно знайденим ту, в яку він повернеться, а потім повертається в цей стан (крок go to state) і досліджує з нього прилеглі області, здійснюючи випадкові дії. Після чого архів оновлюється, зберігаючи інформацію про кількості відвідувань комірок, отриману в них винагороду і траєкторії. Таким чином, запам'ятовуючи статки і повертаючись до них, Go-Explore не пропускає найбільш цікаві стани, не допускає перевченості областей поблизу стартової точки і не застрягає поблизу помилкових мінімумів як у наведеному вище прикладі з роботом, що потрапив у глухий кут.
Далі, якщо необхідно, після фази дослідження Go-Explore може виконати робастифікацію знайдених рішень, щоб підвищити стійкість до можливих шумів для знайдених у фазі дослідження траєкторій. Справа в тому, що на відміну від реального світу ігрове оточення в емуляторі Atari досить детерміновано, тобто одні і ті ж дії призводять до одних і тих же результатів, а повернення до попереднього стану для простоти проводиться відновленням раніше збереженого стану емулятора. Однак у разі внесення випадковостей в оточення ми повинні бути впевнені, що після повернення в один з колишніх станів зможемо скористатися раніше знайденим шляхом і що він приведе нас в задану область. Для підвищення робастості розробники використовують алгоритм зворотного ходу, запускаючи його ітераційно і послідовно переміщуючи агент від кінця траєкторії до її початку. Також, для зменшення детермінованості в роботу алгоритму вводилися випадкові затримки, що імітують людський стиль гри.
Вихідні кадри екрану гри, отримані з емулятора Atari, проходять попередню обробку. Зображення перетворюється в відтінки сірого, а роздільна здатність зменшується. Параметри обробки кадрів динамічно змінюються, оскільки кількість деталей, що відображаються на екрані, може змінюватися навіть у рамках однієї гри. Кількість оброблених алгоритмом кадрів у кожній грі становить близько 30 мільярдів, що можна порівняти з іншими алгоритмами, що використовують бенчмарк від Atari.
Незважаючи на те, що Go-Explore показує хороші результати навіть коли агент нічого не знає про оточення, розробники додали в інформацію про стан знання про оточення, одержувані з вихідних кадрів з емулятора Atari, що надходять на вхід алгоритму, такі, наприклад, як поточні координати агента на кадрі, поточну кімнату, рівень і наявні предмети у персонажа (ключі в Montezuma s Reens). Очікувано застосування такого вдосконаленого уявлення призводить до суттєвого зростання кількості набраних у грі очок.
Результати тестування на 11 найбільш складних іграх з бенчмарка Atari показують, що Go-Explore обходить за набраними ігровими балами більшість існуючих алгоритмів з помітним відривом, в тому числі і MuZero від DeepMind, про який ми писали раніше. У грі Montezuma's Revenge Go-Explore зміг набрати більше 1.73 мільйонів очок, тоді як рекорд, поставлений людиною, становить близько 1.22 мільйонів. Так само автори відзначають, що їх алгоритм зміг перевершити середній рівень очок, що набирається людиною в грі Pitfall, хоча до останнього часу це не вдавалося жодному з існуючих алгоритмів. Схожу з Go-Explore ефективність показав тільки алгоритм від DeepMind під назвою Agent57. Як і Go-Explore він зміг перевершити середній людський рівень і навіть обійти алгоритм від розробників з Uber в чотирьох іграх з одинадцяти за очками. Однак, як стверджують автори, порівнювати результати Go-Explore і Agent57 не зовсім коректно, оскільки результати останнього були отримані в більш простих і детермінованих умовах. Наприклад, на відміну від Go-Explore в Agent57 не проводилася імітація «людської» затримки при грі.
Окрім тестування Go-Explore на іграх Atari, інженери змогли успішно застосувати той самий підхід у роботі маніпулятора робота. Алгоритм успішно впорався з керуванням роборукою в симуляторі, переміщуючи віртуальні предмети на полиці, навіть якщо вони спочатку перебували за дверцятами із замками.
Фахівці в галузі машинного навчання намагаються навчити алгоритми не тільки успішно грати в ігри, а й передбачати майбутнє. Так британські інженери з Імперського коледжу Лондона розробили алгоритм, здатний прогнозувати майбутні події, використовуючи концепції спеціальної теорії відносності і простору-часу Мінківського.