Часть 1: Определение среды, поиск оптимальной политики с помощью итераций значений и введение Q-Learning
Резюме
В этой статье я представлю новый проект, который пытается помочь тем, кто изучает обучение с подкреплением, путем полного определения и решения простой задачи в записной книжке Python. Среда и основные методы будут объяснены в этой статье, а весь код опубликован на Kaggle по ссылке ниже. Кроме того, я создал записную книжку «Мета», которую можно легко разветвлять и которая содержит только определенную среду, чтобы другие могли попробовать, адаптировать и применить свой собственный код.
Контекст
Когда я впервые начал изучать обучение с подкреплением, я сразу начал копировать онлайн-руководства и проекты, но обнаружил, что теряюсь и сбиваюсь с толку. «Почему результаты показывают это? Что делает этот параметр? Что окружающая среда действует таким образом? » вот некоторые из вопросов, которые я начал задавать себе. И только после того, как я сделал шаг назад и начал с основ полного понимания того, как определяется вероятностная среда, и создания небольшого примера, который я мог решить на бумаге, все стало иметь больше смысла. Однако мне было трудно найти среды, в которых я мог бы применить свои знания, которые не нужно было импортировать из внешних источников.
Поэтому я поставил перед собой задачу:
Могу ли я полностью определить и найти оптимальные действия для среды задач, полностью автономных в записной книжке Python?
Я надеюсь, что, следя за моей работой, другие смогут использовать это как базовую отправную точку для обучения самих себя.
Этап 1: определение среды
Задание
Проще говоря, я хочу знать, как лучше всего выбросить лист бумаги в корзину (мусорное ведро) из любого места в комнате. Я могу бросать бумагу в любом направлении или двигаться по одному шагу за раз.
Хотя это просто для человека, который может судить о местонахождении бункера по зрению и имеет огромное количество предварительных знаний о расстоянии, на котором робот должен учиться ни на чем.
Это определяет среду, в которой вероятность успешного броска рассчитывается на основе направления, в котором брошена бумага, и текущего расстояния от корзины.
Например, на изображении ниже у нас есть три человека, обозначенные A, B и C. Оба игрока A и B бросают в правильном направлении, но человек A находится ближе, чем B, и поэтому у него будет более высокая вероятность попадания.
Человек C ближе, чем человек B, но бросает в совершенно неправильном направлении, поэтому вероятность попасть в мусорное ведро очень мала. Это может показаться нелогичным, что человек C бросит в этом направлении, но, как мы покажем позже, алгоритм должен сначала попробовать ряд направлений, чтобы выяснить, где находятся успехи, и не будет иметь визуального руководства относительно того, где находится корзина. .
Чтобы создать среду на Python, мы преобразуем диаграмму в двумерные измерения значений x и y и используем математику пеленга для вычисления брошенных углов. Мы использовали нормализованные целочисленные значения x и y, поэтому они должны быть ограничены -10 и 10.
Вероятность окружающей среды
Вероятность успешного броска зависит от расстояния и направления, в котором он был брошен. Следовательно, нам нужно рассчитать две меры:
- Расстояние, на котором текущая позиция находится от корзины
- Разница между углом, под которым была брошена бумага, и истинным направлением в корзину
Измерение расстояния
Как показано на графике выше, положение человека A установлено равным (-5, -5). Это их текущее состояние, и их расстояние от корзины можно рассчитать с помощью меры евклидова расстояния:
Для окончательных расчетов мы нормализуем это и меняем значение, чтобы высокий балл указывал, что человек находится ближе к целевой ячейке:
Поскольку мы зафиксировали наши двумерные измерения между (-10, 10), максимально возможное расстояние, на котором может находиться человек, составляет sqrt {(100) + (100)} = sqrt {200} от корзины. Следовательно, наша оценка расстояния для человека A:
Направление
Затем человек А должен принять решение, двигаться ли он или бросать в выбранном направлении. А пока представьте, что они решили бросить бумагу, их первый бросок составляет 50 градусов, а второй - 60 градусов относительно северного направления. Направление корзины от человека А можно вычислить с помощью простой тригонометрии:
Следовательно, первый бросок отклоняется от истинного направления на 5 градусов, а второй - на 15 градусов.
Если учесть, что хорошие броски ограничены 45 градусами по обе стороны от фактического направления (т.е. не в неправильном направлении), то мы можем использовать следующее, чтобы вычислить, насколько хорошо это выбранное направление. Любое направление, выходящее за пределы 45 градусов, даст отрицательное значение и будет сопоставлено с вероятностью 0:
Оба довольно близки, но их первый бросок с большей вероятностью попадет в мусорное ведро.
Расчет вероятности
Поэтому мы рассчитываем нашу вероятность успешного броска относительно обоих этих показателей:
Создание обобщенной функции вероятности
Хотя предыдущие расчеты были довольно простыми, необходимо принять во внимание некоторые соображения, когда мы обобщаем их и начинаем считать, что корзина или текущее положение не являются фиксированными.
В нашем предыдущем примере человек A находится к юго-западу от контейнера, поэтому угол был простым вычислением, но если бы мы применили то же самое, чтобы сказать, что человек находится на северо-востоке, это было бы неверно. Кроме того, поскольку контейнер можно разместить в любом месте, нам нужно сначала найти, где находится человек относительно него, а не только в начале координат, а затем использовать это для определения требуемого угла.
Это показано на диаграмме ниже, где мы обобщили все тригонометрические вычисления на основе относительного положения человека по отношению к корзине:
Имея в виду эту диаграмму, мы создаем функцию, которая вычисляет вероятность успеха броска только для заданной позиции относительно корзины.
Затем мы вычисляем азимут от человека к мусорному ведру, следуя предыдущему рисунку, и вычисляем оценку в пределах диапазона +/- 45 градусов. Броски, наиболее близкие к истинному пеленгу, получают больше очков, в то время как дальние броски получают меньше очков, все, что больше 45 градусов (или меньше -45 градусов), является отрицательным, а затем устанавливается нулевое значение вероятности.
Наконец, общая вероятность связана как с расстоянием, так и с направлением с учетом текущего положения, как показано ранее.
Примечание. В качестве границы я выбрал 45 градусов, но вы можете изменить это окно или вручную масштабировать расчет вероятности, чтобы по-другому взвесить измерение расстояния и направления.
Мы пересчитываем предыдущие примеры и получаем те же результаты, что и ожидалось.
Построение вероятностей для каждого состояния
Теперь, когда у нас есть это как функция, мы можем легко вычислить и построить график вероятностей всех точек в нашей двумерной сетке для фиксированного направления броска.
Вероятности определяются углом, который мы установили в предыдущей функции, в настоящее время он составляет 45 градусов, но при желании его можно уменьшить или увеличить, и результаты будут соответственно меняться. Мы также можем захотеть по-разному масштабировать вероятность для расстояний.
Например, вероятность того, что бумага будет брошена под углом 180 градусов (на юг) для каждого положения x / y, показана ниже.
Анимированный график для всех направлений броска
Чтобы продемонстрировать это дальше, мы можем перебрать несколько направлений броска и создать интерактивную анимацию. Код становится немного сложным, и вы всегда можете просто использовать предыдущий фрагмент кода и вручную изменить параметр «throw_direction», чтобы исследовать различные позиции. Однако это помогает исследовать вероятности и может быть найдено в записной книжке Kaggle.
Этап 2: поиск оптимальной политики для среды, вероятности которой известны
Модельные методы
Наша цель - найти оптимальное действие в каждом состоянии, бросая или двигаясь в заданном направлении. Поскольку нам известны вероятности, мы действительно можем использовать методы, основанные на модели, и сначала продемонстрируем это, а также можем использовать итерацию значений для достижения этого с помощью следующей формулы:
Итерация значений начинается с произвольной функции V0 и использует следующие уравнения, чтобы получить функции для k + 1 этапов, чтобы перейти от функций для k этапов (https://artint.info/html/ArtInt_227.html).
Расчет действий MOVE довольно прост, потому что я определил гарантированную вероятность успеха перемещения (равную 1). Следовательно, значение Q, например, действия (1,1) из состояния (-5, -5) равно:
Q ((- 5, -5), MOVE (1,1)) = 1 * (R ((- 5, -5), (1,1), (- 4, -4)) + гамма * V ( -4, -4)))
на данный момент все вознаграждения также равны 0, поэтому значение для этого первого расчета просто:
Q ((- 5, -5), (1,1)) = 1 * (0 + гамма * 0) = 0
Все действия по перемещению в первом обновлении будут рассчитываться аналогично. В результате успешных бросков в систему добавляется ценность. Следовательно, мы можем рассчитать значение Q для конкретного действия броска. Ранее мы обнаружили, что вероятность направления броска на 50 градусов из (-5, -5) равна 0,444. Следовательно, значение Q для этого действия соответственно обновляется:
Q ((- 5, -5), БРОСИТЬ (50)) =
0,444 * (R ((- 5, -5), (50), bin) + гамма * V (bin +))) +
(1–0,444) * (R ((- 5, -5), (50), bin) + гамма * V (bin-)))
Опять же, вознаграждения устанавливаются на 0, положительное значение корзины равно 1, а отрицательное значение корзины равно -1. Таким образом, мы имеем:
Q ((- 5, -5), БРОСИТЬ (50)) =
0,444 * (0 + гамма * 1) +
(1–0,444) * (0 + гамма * 1) = 0,3552–0,4448 = -0,0896
Становится ясно, что хотя перемещение после первого обновления не отличается от инициализированных значений, бросок на 50 градусов хуже из-за расстояния и вероятности промаха.
После вычисления каждого Q (s, a) для всех состояний и действий значение каждого состояния, V (s), обновляется как максимальное значение Q для этого состояния. Процесс повторяется взад и вперед, пока результаты не сойдутся.
Не установлено предела, сколько раз это нужно повторять, и это зависит от проблемы. Поскольку наша среда настолько проста, она фактически сводится к оптимальной политике всего за 10 обновлений.
Сначала мы покажем лучшее действие, основанное на броске или перемещении, с помощью простого цветного разброса, показанного ниже.
Улучшение визуализации оптимальной политики
Хотя диаграмма показывает, является ли оптимальным действием бросок или движение, она не показывает нам, в каком направлении они находятся. Поэтому мы сопоставим каждое оптимальное действие с вектором u и v и будем использовать их для создания графика колчана ( Https://matplotlib.org/api/_as_gen/matplotlib.axes.Axes.quiver.html).
Мы определяем масштаб стрелок и используем его для определения горизонтальной составляющей, обозначенной u. Для движущихся действий мы просто умножаем движение в направлении x на этот коэффициент, а для направления броска мы перемещаемся на 1 единицу влево или вправо (с учетом отсутствия горизонтального движения на 0 или 180 градусов и отсутствия вертикального движения на 90 или 270 градусов). .
Затем горизонтальный компонент используется для вычисления вертикального компонента с помощью некоторой базовой тригонометрии, где мы снова учитываем определенные углы, которые могут вызвать ошибки в расчетах.
Мы видим, что в некоторых штатах есть несколько лучших действий. Те, кто находится прямо на севере, востоке, юге от запада, могут двигаться в нескольких направлениях, тогда как состояния (1,1), (1, -1), (- 1, -1) и (-1,1) могут двигаться или бросать в сторону мусорное ведро.
Наконец, я решил показать изменение оптимальной политики при каждом обновлении, экспортируя каждый сюжет и передавая небольшую анимацию.
Этап 3: поиск оптимальной политики с помощью обучения с подкреплением, где вероятности скрыты
Алгоритм Q-обучения
Теперь представим, что вероятности неизвестны человеку, и поэтому необходим опыт, чтобы найти оптимальные действия.
Во-первых, давайте попробуем найти оптимальное действие, если человек начинает в фиксированном положении, а корзина фиксируется на (0,0), как и раньше.
Мы будем применять Q-обучение и инициализировать все пары состояние-действие значением 0 и использовать правило обновления:
Мы даем алгоритму выбор: бросить в любом направлении на 360 градусов (на целый градус) или переместиться в любую позицию, окружающую текущую. Таким образом, есть 8 мест, куда он может перемещаться: север, северо-восток, восток и т. Д.
Когда он решает бросить бумагу, он получит либо положительную награду +1, либо отрицательную -1 в зависимости от того, попадет ли она в корзину или нет, и эпизод закончится.
Путем нескольких попыток проб и ошибок необходимо будет установить, где находится корзина, а затем, лучше ли сначала переместиться или бросить из текущей позиции.
Псевдокод Q-Learning
Сначала, как и раньше, инициализируем Q-таблицу произвольными значениями 0.
На данный момент позиция начала эпизода будет привязана к одному состоянию, и мы также введем ограничение на количество действий в каждом эпизоде, чтобы оно случайно не продолжалось бесконечно.
Каждый эпизод заканчивается естественным образом, если брошен лист бумаги, действие, выполняемое алгоритмом, определяется процедурой выбора эпсилон-жадного действия, при которой действие выбирается случайным образом с эпсилон-вероятностью и жадно (текущий максимум) в противном случае. Чтобы немного сбалансировать случайный выбор между действиями движения или броска (так как есть только 8 действий движения, но 360 действий броска), я решил дать алгоритму шанс 50/50 движения или броска, а затем впоследствии выберет действие случайным образом из них.
Как и раньше, действие случайного движения не может выходить за пределы комнаты, и, обнаружив, мы обновляем текущий Q (s, a) в зависимости от максимального Q (s ’, a) для всех возможных последующих действий. Например, если мы перейдем от -9, -9 к -8, -8, Q ((-9, -9), (1,1)) будет обновляться в соответствии с максимумом Q ((-8, -8 ), а) для всех возможных действий, в том числе и бросковых.
Если алгоритмы бросают бумагу, вероятность успеха рассчитывается для этого броска, и мы моделируем, был ли в этом случае успешным и получением положительного терминального вознаграждения или неудачным и получением отрицательного терминального вознаграждения.
Алгоритм продолжает обновлять значения Q для каждой пары состояние-действие, пока результаты не сойдутся.
Мы проанализируем влияние различных параметров в следующем сообщении, а пока просто представим некоторые произвольные варианты выбора параметров:
- num_episodes = 100
- alpha = 0.5
- гамма = 0,5
- epsilon = 0,2
- max_actions = 1000
- pos_terminal_reward = 1
- neg_terminal_reward = -1
Запустив алгоритм с этими параметрами 10 раз, мы производим следующее «оптимальное» действие для состояний -5, -5:
Ясно, что они не согласованы, что в значительной степени предполагает, что действия на самом деле не оптимальны. Следовательно, нам необходимо рассмотреть, как выбранные нами параметры влияют на результат и что можно сделать для улучшения результатов.
Заключение
Мы с нуля ввели среду на Python и нашли оптимальную политику. Кроме того, я начал знакомить с методом поиска оптимальной политики с помощью Q-обучения.
Я продолжу это в следующем посте и улучшу эти первоначальные результаты, варьируя параметры. На данный момент я надеюсь, что этого достаточно для того, чтобы вы начали опробовать свои собственные алгоритмы на этом примере.
Если у вас есть какие-либо вопросы, не стесняйтесь оставлять комментарии ниже или на страницах Kaggle.
Спасибо
Фил
