Представьте себя в поисках сокровищ в лабиринте. Игра выглядит следующим образом:
Вы начинаете с заданной позиции, исходного состояния. Из любого состояния вы можете идти влево, вправо, вверх или вниз или оставаться в том же месте, если вы не пересекаете территорию лабиринта. Каждое действие переводит вас в ячейку сетки (другое состояние). Теперь в одном из состояний (состояние цели) есть сундук с сокровищами. Кроме того, в лабиринте есть яма со змеями в определенных положениях / состояниях. Ваша цель - перейти от начального состояния к целевому, следуя по пути, на котором нет змей.
Когда вы помещаете агента в сетку (мы будем называть его нашей средой), он сначала исследует. Он не знает, что такое змеи, и не знает, что и где находится сокровище. Итак, чтобы дать ему представление о змеях и сундуке с сокровищами, мы дадим ему вознаграждение за каждое действие. За каждую змеиную яму, на которую она ступит, мы дадим ей -10 наград. За клад дадим награду +10. Теперь мы хотим, чтобы наш агент выполнил задачу как можно быстрее (выбрал кратчайший путь). За это мы дадим остальным состояниям награду -1. Затем мы скажем ему, чтобы получить максимальное количество очков. Теперь, когда агент исследует, он узнает, что змеи вредны для него, сокровище ему полезно, и он должен получить сокровище как можно быстрее. Путь «-» на рисунке показывает кратчайший путь с максимальным вознаграждением.
Q-Learning пытается понять ценность пребывания в данном состоянии и выполнения в нем определенных действий.
Что мы сделаем, так это разработаем таблицу. Где строки будут состояниями, а столбцы - действиями, которые он может предпринять. Итак, у нас есть пары 16x5 (80 возможных состояний-действий), где каждое состояние является одной ячейкой сетки лабиринта.
Мы начинаем с инициализации таблицы, чтобы она была единообразной (все нули), а затем, наблюдая за наградами, которые мы получаем за различные действия, мы соответствующим образом обновляем таблицу. Мы обновим таблицу, используя уравнение Беллмана.
«S» представляет текущее состояние. «A» представляет действие, которое агент выполняет в текущем состоянии. «S» представляет состояние, возникшее в результате действия. «R» - это вознаграждение, которое вы получаете за действие, а «γ» - коэффициент скидки. Таким образом, значение Q для состояния «S», выполняющего действие «a», представляет собой сумму мгновенного вознаграждения и дисконтированного будущего вознаграждения (значение результирующего состояния). Коэффициент дисконтирования «γ» определяет, насколько большое значение вы хотите придать будущим вознаграждениям. Скажем, вы переходите в состояние, которое дальше от целевого состояния, но из этого состояния шансы встретить состояние со змеями меньше, поэтому здесь будущее вознаграждение больше, даже если мгновенное вознаграждение меньше.
Мы будем называть каждую итерацию (попытку агента) эпизодом. Для каждого эпизода агент будет пытаться достичь целевого состояния и при каждом переходе будет обновлять значения таблицы Q.
Давайте посмотрим, как рассчитать таблицу Q:
Для этого мы для удобства возьмем лабиринт-сетку меньшего размера.
Исходная Q-таблица будет выглядеть (состояния по строкам и действия по столбцам):
U - вверх, D - вниз, L - влево, R - вправо
Таблица вознаграждений будет выглядеть так:
Здесь E представляет собой NULL, т.е. таких переходов быть не может.
Алгоритм:
- Инициализировать Q-матрицу всеми нулями. Установите значение для «γ». Заполните матрицу вознаграждений.
- Для каждой серии. Выберите случайное начальное состояние (здесь мы ограничим наше начальное состояние до состояния-1).
- Выберите одно из всех возможных действий для текущего состояния (S).
- Перейти в следующее состояние (S ’) в результате этого действия (а).
- Для всех возможных действий из состояния (S ’) выберите то, которое имеет наибольшее значение Q.
- Обновите Q-таблицу, используя уравнение 1.
- Установите следующее состояние как текущее.
- Если состояние цели достигнуто, то конец.
Пример: допустим, мы начинаем с состояния 1. Мы можем выбрать D или R. Скажем, мы выбрали D. Затем дойдем до 3 (змеиная яма). Итак, тогда мы можем выбрать U или R. Итак, принимая γ = 0,8, имеем:
Q (1, D) = R (1, D) + γ * [max (Q (3, U) & Q (3, R))]
Q(1,D) = -10 + 0.8*0 = -10
Здесь max (Q (3, U) & Q (3, R)) = 0, поскольку Q-матрица еще не обновлена. -10 - наступление на змей. Итак, новая Q-таблица выглядит так:
Теперь 3 - это начальное состояние. Допустим, мы идем от 3 к R. Итак, переходим к 4. Из 4 мы можем перейти на U или L.
Q (3, R) = R (3, R) + 0,8 * [max (Q (4, U) & Q (4, L))]
Q(3,R) = 10 + 0.8*0 = 10
Итак, теперь мы достигли целевого состояния 4. Итак, мы завершаем и выполняем несколько проходов, чтобы наш агент понимал значение каждого состояния и действия. Продолжайте делать проходы, пока значения не останутся постоянными. Это означает, что ваш агент опробовал все возможные пары состояние-действие.
Реализация на питоне:
Вывод для последней q_matrix:
В следующей статье я расскажу об использовании нейронных сетей для Q-Learning и о недостатках табличного подхода. Также мы будем работать над играми из тренажерного зала Open-AI для тестирования. А пока, пока.
