Мое баловство с Q-learning или ML + Python + Pygame

Q-learning (калькированный термин — Q-обучение) — это один из алгоритмов реализации метода машинного обучения с подкреплением (reinforcement learning, RL).
Рассмотренный далее пример «Q-learning in action» может оказаться полезным для новичков в этой области.
Человечек (агент, agent) агентный подход живет в плоском мире размером 11 на 11 клеток (environment):
q-learning
Агент может пошагово совершать действия, а каждое действие (action) заключается в попытке перемещения на соседнюю клетку по любому из 8 направлений:
машинное обучение
(«попытке», так как выход за границы мира запрещен — можно считать, что граница «выталкивает» агента в прежнюю позицию):
В мире агента имеются стены , которые не пускают агента на занятые ими клетки, и ловушки , «телепортирующие» агента в начальную позицию.
Состояние (state) агента на каждом шаге (step) описывается его позицией — порядковым номером клетки:

Стартовая позиция агента в начале эпизода (episode) — верхний левый угол, цель агента — достичь конечной позиции — правого нижнего угла по кратчайшему пути.
Вся прелесть алгоритма Q-learning в том, что он работает тогда, когда агент даже и не знает КАК добиться желаемого результата («model-free»).

Выбор оптимальных действий агента в этом случае описывается Марковским процессом принятия решений (MDP Markov Decision Process).
Для успешного применения такого метода необходим механизм обратной связи агента со средой — вознаграждение (reward), которое может быть положительным, отрицательным или нулевым.
За каждый ход агент получает отрицательную награду (-1) — стимулирует агента сокращать число сделанных ходов, а за достижение конечной точки — положительную награду (+100) — стимулирует агента перейти в эту точку.
При достаточно длительном процессе обучения алгоритм обучения с подкреплением позаботится о максимизации вознаграждения, получаемого агентом.
Этот механизм похож на механизм формирования условного рефлекса.

Я реализовал проект на Python в связке с Pygame для большей зрелищности процесса обучения.
Исходный код проекта доступен на GitHub под лицензией GNU GPL 3https://github.com/Dreamy16101976/QL .
Текст программы, обильно снабженный комментариями, содержится в файле ql.py.
Настройки описаны в файле settings.py:
гиперпараметры:

ALPHA = 1.0 # скорость обучения
GAMMA = 0.95 # коэффициент учета последующих наград

стены:

WALLS = {(2,4), (3,4), (4,4), (5,4), (6,4), (10,8), (9,8), (10,6), (9,6), (8,6), (7,6), (6,6), (5,6), (1,7), (1,8), (1,9)}

ловушки:

TRAPS = {(2,2), (3,6), (5,8)}

После запуска программа запрашивает количество реализуемых эпизодов:

Затем начинается обучение агента, в процессе которого точки, где побывал агент, помечаются следами :
обучение с подкреплением

При обучении происходит заполнение ячеек Q-таблицы. Q-таблица ставит в соответствие действиям, которые выполняются в том или ином состоянии агента, число (q-value), характеризующее «полезность» этого действия для агента. При этом учитывается не только сиюминутная награда за это действие, но и награды, получаемые агентом в дальнейшем. После каждого шага обновляется ячейка таблицы, соответствующая выполненному действию, с помощью уравнения Белмана (Bellman equation).

В конце каждого эпизода в консоли отображаются оптимальные варианты действий:

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

После обучения в течение 99 эпизодов агент уверенно находит оптимальный маршрут:
q-обучение

Англоязычная версия статьи — https://www.reddit.com/r/Python/comments/e4isiy/qlearning_in_action_or_machine_learning_with/

Продолжение следует



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

Ваш e-mail не будет опубликован. Обязательные поля помечены *