Solving Atari Games Using Fractals And Entropy 

В чем понт

Алгоритм, использующий фрактальную теорию ИИ, бьющую sota в 49 из 55 играх атари. 

Подробности

Агент, среда, временной горизонт.

Статья относится к разделу reinforcement learning. У нас есть агент, среда, и наша задача выучить политику - вероятность каждого действия в каждом состоянии. Допустим, наше начальное состояние -это x(0). Запустим для нашего агента рой ходоков- стохастический процесс. Этот процесс нарисует дерево возможных траекторий состояний во времени до момента t (временной горизонт). Мы получим конус (рис 1). Чем больше покрытие всех возможный состоящий в пределах этого конуса, тем больше энтропия наших траекторий. Также мы можем вносить априорные знания и создавать в конусе запрещённые зоны-области состояний, куда нам не нужно ходить. Мы можем влиять на максимальный объём вычислений - он будет зависеть от количества произведения частиц в рое на временной горизонт.

Политика

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

Алгоритм

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

Что в итоге

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