Динамическое программирование - это решение большой рекурсивной проблемы путем разделения ее на подзадачи. Везде, где мы видим рекурсивное решение, которое имеет повторяющиеся вызовы для одних и тех же входных данных, мы можем оптимизировать его с помощью динамического программирования. Идея состоит в том, чтобы просто сохранить результаты подзадач, чтобы нам не приходилось повторно вычислять их, когда это понадобится позже. Машинное обучение - это заставить компьютер учиться самостоятельно, не будучи явно запрограммированным. Возникает вопрос, как мы можем оптимально решить большую проблему, используя концепцию машинного обучения наряду с динамическим программированием? Что ж, ответ - Q-Learning, который является одним из лучших алгоритмов обучения с подкреплением.
В этом сообщении блога я покажу, как можно оптимально решить одну из проблем динамического программирования, используя обучение с подкреплением, и реализовать Q-обучение в Python с нуля. Некоторое базовое понимание обучения с подкреплением требуется в качестве предварительного условия, например, что такое состояния, действия, политика и награды.
Содержание: -
- Постановка задачи
- Решение с использованием динамического программирования
- Решение с использованием обучения с подкреплением
- Результаты
- Заключение и ссылка на GitHub для кода
Цель состоит в том, чтобы рассчитать минимальное количество прыжков для достижения конца, учитывая, что разрешено максимум до K прыжков. Рассмотрим среду, в которой человек должен добраться до конца пути, состоящего из N пропускаемых стен. Задача состоит в том, чтобы получить минимальное количество прыжков,
необходимое для достижения конца из начальной позиции. Человек может пропустить максимум K стенок за один раз. Необходимым условием является достижение конечного положения, а не его выхода, и если он действительно выходит за пределы конечного положения, он должен начать заново из исходного положения.
Наивный рекурсивный подход
Наивный подход заключается в рекурсивном вызове всех позиций, доступных с первой позиции. Минимальное количество прыжков для достижения конца с первого можно рассчитать, используя минимальное количество прыжков, необходимое для достижения конца из позиций, достижимых с первого.
minJumps (start, end) = Min (minJumps (k, end)), для всех k достижимых с начала
2. Решение с использованием динамического программирования
Мы видим, что есть частично совпадающие подзадачи. Например, minJumps (3, 9) будет вызываться два раза, поскольку позиция [3] достижима из позиции [1] и позиции [2]. Таким образом, эта проблема имеет оба свойства (оптимальная подструктура и перекрывающиеся подзадачи) динамического программирования.
В этом методе мы строим массив jumps [] слева направо, так что jumps [i] указывает минимальное количество прыжков, необходимых для достижения позиции [i] из позиции [0]. Наконец, мы возвращаем прыжки [n-1].
3. Решение с помощью обучения с подкреплением
Выше приведена типичная установка RL. Основная цель агента - максимизировать определенное числовое вознаграждение, выполняя определенную последовательность действий в окружающей среде, путешествуя по различным состояниям. Где следующее состояние и награда полностью зависят от действия агента. Самая большая проблема в RL - это отсутствие надзора (маркированных данных) для руководства агентом. Он должен исследовать и учиться самостоятельно. Агент начинает с произвольного выполнения действий и наблюдения за вознаграждениями, которые приносит каждое действие, и учится предсказывать наилучшее возможное действие при столкновении с аналогичным состоянием окружающей среды. В нашем случае мы можем определить настройку обучения с подкреплением, как показано ниже:
Окружение: состоит из пути, имеющего N стен.
Агент: Человек, который должен перепрыгивать через стены.
Переводчик : Наблюдает, достигнута ли конечная позиция.
Состояния: расстояние между конечной точкой и текущим положением человека после каждого прыжка.
Actions: Количество стен, перескочивших за один раз, максимум до K стен. Например:
Действие 1: пропустить 1 стену.
Действие 2: пропустить 2 стены.
Действие 3: пропустить 3 стены.
Действие 4: пропустить 4 стены.
Награда: за каждый прыжок взимается стоимость -1, а при достижении конечной позиции дается награда в размере 0.
Q-обучение - это безмодельная реализация обучения с подкреплением, в которой поддерживается таблица значений Q для каждого состояния, предпринятого действия и полученного вознаграждения. Он действует как справочная таблица для нашего агента, чтобы выбрать лучшее действие на основе q-значения. Приведенный ниже пример Q-таблицы может дать нам представление о том, как структурированы данные:
Следовательно, Q-обучение - это метод RL, в котором мы пытаемся аппроксимировать специальную функцию, которая управляет политикой выбора действий для любой последовательности состояний среды и, следовательно, сходится и дает нам максимально возможное вознаграждение.
Проблема Исследование против эксплуатации возникает, когда наша модель имеет тенденцию придерживаться одних и тех же действий во время обучения. Введем ɛ, который определяет случайность действий. Мы постепенно уменьшаем его ценность, чтобы уменьшить случайность по мере продвижения, а затем используем полезные действия. В нашем случае начальное значение ɛ составляет 0,9, а скорость распада - 0,9998 за эпизод.
Коэффициент скидки γ - это параметр, который определяет, как далеко в будущее смотрит наша модель при выполнении действия, т.е. как ранее совершенное неправильное действие может повлиять на текущее вознаграждение. Таким образом, γ решает проблему присвоения кредита косвенно. В нашем случае модель узнала, что случайные прыжки будут препятствовать ее способности прыгать в будущем, когда мы установили γ = 0,95.
Ниже приведены некоторые дополнительные параметры, которые мы будем использовать позже:
Следующим шагом является создание среды для нашего агента. В приведенном ниже коде конструктор класса Utils находит агент в начальной позиции и определяет две функции, а именно a ction () и move (). Функция move () заставляет агента прыгать на k шагов. где k определяется функцией action (), которая вызывает функцию move () на основе выбора действия агента. Например, если выбор действия равен 2, агент прыгнет на 2 стены в прямом направлении. Q-таблица, имеющая 10 состояний и 4 действия, инициализируется случайными значениями.
Следующим и последним шагом является Обучение агента. Для каждого эпизода мы заставим агента начать с начальной позиции и дойти до конца, сделав не более k прыжков. Значение k будет изменяться для каждого эпизода случайным образом от 1 до 4 (MAX_SKIPS). Например, если k = 3, то это означает, что агент может выполнять действия / может перепрыгивать только через 1, 2 и 3 стены. Это сделано для того, чтобы агент был устойчивым и хорошо обучался в различных сценариях.
Для каждой итерации / шага в эпизоде агент будет взаимодействовать с окружающей средой и собирать награды. Эти награды хранятся в списке под названием «Episode_reward []», который добавляется к основному списку общих наград «Episode_rewards []» в конце каждого эпизода. Агент будет действовать в зависимости от значения ɛ. То есть агент выберет действие, которое имеет наивысшее значение Q для этого состояния с вероятностью 1-(эксплуатация) и случайное действие с вероятностью (разведка).
Здесь «obs» - текущее состояние, а «new_obs» - следующее состояние, которое представляет собой не что иное, как оставшееся расстояние между текущим и конечным положением. В зависимости от текущей должности агента выдаются награды (END_REWARD или MOVE_PENALTY).
Теперь для обновления значений Q рассмотрим следующую формулу:
max_future_q захватывается после того, как мы уже выполнили свое действие, а затем мы обновляем наши предыдущие значения, частично основываясь на наилучшем значении Q для следующего состояния («new_obs»).
Со временем, как только мы достигли цели один раз, это значение вознаграждения медленно возвращается, шаг за шагом, для каждого эпизода.
4. Результаты
Для целей оценки было рассчитано скользящее среднее вознаграждений для 30 эпизодов, а на графике ниже показано схождение во времени.
5. Заключение и ссылка на GitHub для кода
У динамического программирования есть два свойства для решения сложной проблемы: Оптимальная подструктура и Перекрывающиеся подзадачи. Марковские процессы принятия решений удовлетворяют обоим этим свойствам:
- Уравнение Беллмана дает рекурсивное разложение, которое говорит нам, как разбить функцию оптимального значения на две части. т.е. оптимальное поведение одного шага, а затем оптимальное значение остальных шагов.
- Q-Learning хранит и повторно использует решения. Кэш со всей полезной информацией MDP, которая сообщает вам оптимальное вознаграждение, которое вы можете получить в этом состоянии и в дальнейшем.
Следовательно, мы можем сделать вывод, что RL может оптимально решать задачи DP в хорошо спроектированной среде в форме марковского процесса принятия решений. Следует позаботиться о том, чтобы по мере увеличения количества состояний или усложнения среды требовалось больше вычислительной мощности для исследования всех состояний и обновления значений Q / таблицы Q.
Ниже приведена ссылка на GitHub для приведенного выше кода.
Спасибо за чтение. Поделитесь, прокомментируйте и аплодируйте, если вам понравился пост.
По вопросам фриланса или для получения идей и кода крупных или второстепенных проектов в сфере B-Tech, M-Tech обращайтесь к моей команде по адресу [email protected]. Мы будем рады вам помочь.
