Добро пожаловать обратно в эту серию, во второй части мы перейдем к хорошо известной проблеме обучения с подкреплением (RL) — многорукий бандит. Эта проблема представляет собой особый случай, когда существует только одно состояние, и представляет собой фундаментальную дилемму в RL, которая заключается в компромиссе между разведкой и эксплуатацией.
Если вы новичок в этой серии, я настоятельно рекомендую прочитать часть 1 этой серии, чтобы узнать, подходит ли она вам.
Давайте начнем!
Содержание:
- Табличный метод решения
- Метод действия-ценности
- Инкрементальные вычисления
- Нестационарная задача
- Оптимистичная начальная стоимость
- Верхняя доверительная граница
- Bandit Gradient — метод предпочтения действий
- Ассоциативный поиск — множественное состояние
1. Табличный метод решения
Помните, что в задачах RL агент будет пытаться максимизировать совокупное вознаграждение от начального состояния S₀. Это кумулятивное вознаграждение S₀ во многих случаях зависит от кумулятивного вознаграждения следующего состояния S₁, а вознаграждение S₁ зависит от S₂ и так далее.
По этой причине нам часто нужно хранить совокупные вознаграждения S₁, S₂…В задаче, где пространство состояний (которое содержит все возможные состояния) или пространство состояний-действий (которое содержит все пары состояний и действий в это состояние) достаточно малы, мы часто храним их в таблице. Поэтому этот метод называется табличным.
В задаче о многоруком бандите нам дается несколько попыток и набор игровых автоматов, вероятность выигрыша которых неизвестна, и нам нужно максимизировать общую награду после того, как мы потратим все наши попытки.
Существует множество способов определить состояние, например, цвета игровых автоматов. Однако наше состояние не меняется после того, как мы выполняем какое-либо действие (вытягивание игрового автомата точно не меняет его цвет).
Кроме того, допустим, у нас есть n игровых автоматов, при каждой попытке у нас есть n вариантов, которые представлены n действиями aᵢ (i от 1 до n). Поэтому пространство состояний-действий очень мало (всего 1xn), что делает табличные методы решения подходящими для этой задачи.
Исследование и эксплуатация
Во-первых, мы не знаем ожидаемую награду (среднюю награду) от каждой руки, мы должны их попробовать. Это называется разведкой. После того, как у нас есть несколько раз, у нас есть некоторая информация (хотя и не очень определенная) об этих руках, и мы выбираем руку, которая дает наибольшую награду на основе этой информации. Это называется эксплуатацией. Проблема в том, что вам дается только несколько попыток, поэтому вы должны балансировать между исследованием и эксплуатацией.
2. Метод ценности действия
Чтобы сравнить, какая рука лучше, мы должны сравнить их ожидаемое вознаграждение (которое мы можем беспристрастно оценить только на основе прошлых наблюдений). Метод сравнения ожидаемого вознаграждения каждой руки или ожидаемого вознаграждения от каждого действия называется метод действия и ценности.
Буква Q представляет качество выбора действия a, это качество оценивается на временном шаге t (все еще в этой статье, пожалуйста, просто поймите, что временной шаг — это единица времени). «1_Aᵢ» = возврат 1, если Aᵢ = a, и 0 в противном случае.
По сути, это означает, что оценочное вознаграждение (оценочное значение) действия a равно общему вознаграждению за выполнение действия a, деленному на количество раз, когда мы выбираем действие. а. Это довольно просто.
Как мы используем это значение действия для выбора действия?
Классический метод использует ε-жадный (эпсилон-жадный) метод. В этом методе каждый раз, когда агент должен выбрать действие, он будет использовать его с вероятностью (1-ε) и исследовать с вероятностью ε.
Допустим, мы установили ε = 0,1, тогда с вероятностью 0,1 все действия будут выбраны с равной вероятностью, а с вероятностью 0,9 агент выберет действие aᵢ, имеющее наилучшее значение Qₜ(a). Если есть m действий с одинаковой наилучшей ценностью, то все они имеют равные шансы быть выбранными в случае эксплуатации.
Упражнение: если есть 5 действий и ε = 0,1. В настоящее время Qₜ(а₁) = 0,63, Qₜ(а₂) = 0,36, Qₜ(а₃) = 0,31, Qₜ(а₄) = 0,27, Qₜ(а₅) = 0,66. Какова вероятность того, что каждый из них будет выбран на временном шаге t?
3. Инкрементное вычисление.
Вам не нужна эта часть для реализации собственного алгоритма решения задачи о многоруком бандите. Однако метод, упомянутый в этой части, помогает значительно повысить эффективность вычислений.
Было бы заманчиво обновлять значение каждого действия каждый раз, взяв среднее значение всех вознаграждений с самого начала. Однако эта реализация потребует линейной сложности времени и пространства каждый раз, когда вам нужно обновить действие.
Чтобы эффективно использовать вычислительные ресурсы, мы можем вычислить среднее вознаграждение за каждое обновление следующим образом:
Эту формулу очень легко доказать. Используя эту версию, нам нужно только сохранить значение Qₜ, а временная и пространственная сложность остаются постоянными.
4. Что если мы столкнемся с нестационарной задачей?
До сих пор мы предполагаем, что вероятность получения вознаграждения в каждой руке остается неизменной, пока мы выполняем все наши попытки (действия). Допустим, эта вероятность постепенно меняется со временем, есть ли способ с этим бороться?
Интуитивно мы хотим, чтобы чем более поздней была награда, тем больший вес она должна вносить в ценность действия. Удивительно, но нам просто нужна небольшая модификация, подобная этой.
Где α - константа. Обратите внимание, что в предыдущей версии Rₜ умножается на вес 1/t, который будет меньше и меньше по мере того, как у нас будет больше вознаграждений, но в этой версии константа α заставляет новое вознаграждение Rₜ на любом временном шаге вносить постоянную пропорцию к значение действия a. На самом деле вы можете доказать, что вес вознаграждения со временем будет уменьшаться в геометрической прогрессии.
Как выбрать правильный размер шага α?
Обозначение α часто называют размером шага и эквивалентно скорости обучения в обучении с учителем, поэтому его также часто называют скоростью обучения в RL. При выборе α согласно теории стохастической аппроксимации должны выполняться два условия:
Интуитивно первое условие гарантирует, что α будет достаточно большим, чтобы алгоритм смог преодолеть любое начальное предположение (в нашей задаче начальное значение действия, которое мы должны присвоить действию, равно Q₁(a), это значение мы можем только предположить). Второе условие гарантирует, что α будет достаточно малым для сходимости.
В нашей стационарной задаче выбор α = 1/t удовлетворяет обоим условиям и, таким образом, гарантирует сходимость. В нестационарном случае α — константа, которая не удовлетворяет второму условию, а ценность действия все равно будет меняться (а это то, что нам нужно, поскольку истинная ценность действия — вероятность выигрыша вознаграждения меняется со временем).
5. Оптимистичная начальная стоимость
Этот метод используется для поощрения начального исследования.
Чтобы наш агент RL выбрал действие в начале, когда никакое действие не было предпринято, нам нужно присвоить начальное значение Q₁(aᵢ) каждому действию. Выбор этого начального значения не сильно повлияет на истинное значение действия, пока это действие выполняется достаточное количество раз (закон больших чисел). Почему мы не делаем благоприятный выбор?
Допустим, мне сказали, что есть 2 игровых автомата, и все они дадут вам действительно высокую прибыль, но на самом деле это не так. Я бы с удовольствием попробовал первый, понял, что это невыгодно, а потом попробовал бы второй. В конце концов, мне требуется всего 2 попытки, чтобы попробовать все машины. Та же идея здесь используется в этом оптимистичном начальном значении.
Поскольку этот метод в значительной степени фокусируется на начальном значении, чтобы помочь в исследовании, всякий раз, когда изменяется окружающая среда (нестационарная проблема), этот метод не будет полезен.
В самом деле, любой метод, фокусирующийся на начальных условиях особым образом, вряд ли поможет в общем нестационарном случае.
- Обучение с подкреплением: введение.
6. Выбор действия с верхней доверительной границей
Это еще один метод, помогающий исследованию, но он может помочь с нестационарными проблемами.
Нам нужен какой-то механизм, побуждающий агента выполнять действия, которые не выбираются часто.
Здесь Nₜ(a) обозначает количество раз, когда действие a было выбрано до времени t, а c — параметр, определяющий степень исследования. Интуитивно предпочтение выбора действия будет увеличиваться с его ценностью, степенью исследования, прошедшим временем и обратно пропорционально количеству раз, когда оно было выбрано.
Обратите внимание, что эта формула предназначена только для выбора действия, но не для обновления значения действия Qₜ(a) (мы по-прежнему обновляем Q по среднему вознаграждению для стационарных задач или постоянному весу для нового вознаграждения в нестационарных задачах).
7. Gradient Bandit — метод не требует значения действия.
Этот метод присваивает действию значение предпочтения. Чем больше значение предпочтения, тем больше вероятность того, что это действие будет выбрано. значение предпочтения часто обозначается как Hₜ(a) и не обязательно интерпретирует значение действия. Одним из распространенных способов выбора действия на основе предпочтительных значений является использование распределения soft-max.
Нам нужен способ скорректировать ценность предпочтения этого действия в зависимости от вознаграждения, которое оно приносит. Теоретически это можно сделать по следующей формуле:
По сути, α здесь снова является скоростью обучения, мы берем производную ожидаемого вознаграждения по отношению к значению предпочтения действия a. Для полного объяснения этого метода потребуется несколько слов, поэтому я просто оставлю его там, мы еще встретимся с этим методом в части, посвященной градиенту политики.
На данный момент вы можете просто понять, что это чем-то похоже на подъем по градиенту, когда мы следуем градиенту (увеличиваем или уменьшаем значение предпочтения Hₜ), чтобы ожидаемое вознаграждение при следовании новому скорректированному значению предпочтения увеличивалось.
8. Ассоциативный поиск (Contextual Bandit) — несколько состояний.
На протяжении всей этой статьи мы рассматривали нашу бандитскую проблему только с одним состоянием. Однако в задачах RL у нас обычно будет более одного состояния, например. Проблема доставки муки. Цель агента RL также состоит в том, чтобы изучить политику, которая сопоставляет состояния с действиями в этих состояниях.
Давайте рассмотрим вариант этой задачи о многоруком бандите из «Обучение с подкреплением: введение», чтобы вы были знакомы с общим случаем, когда существует несколько состояний. Допустим, есть 4 игровых автомата соответствующих цветов: красный (M1), синий (M2), зеленый (M3), фиолетовый (M4) и соответствующие вероятности выигрыша 0,7 (M1), 0,2 (M2), 0,1 (M3) и 0,8. (М4). Теперь в любой момент агенту будет либо задан набор M1 слева и M2 справа, либо M3 слева и M4 справа.
Мы рассматриваем первый случай, когда есть игровые автоматы M1 и M2, как состояние S₀, а другой случай с M3 и M4 как состояние S₁. В каждом состоянии есть только два действия влево или вправо, если агент выбирает влево, он вытянет M1 или M3, в противном случае он вытянет M2 или M4. На каждом временном шаге агент будет находиться в состоянии S₀ или S₁ одинаково случайно и независимо от его действий.
Не существует оптимальной политики выбора только левого или правого действия в обоих состояниях, каждое из них должно рассматриваться отдельно. Теперь, если агент сталкивается с красным и синим цветом, он должен ассоциировать этот цвет с чем-то и после нескольких попыток должен знать, что он находится в состоянии S₀ и оптимальное действие — «налево». Точно так же, если агент сталкивается с зелеными и фиолетовыми машинами, он должен знать, что находится в состоянии S₁ и оптимальное действие в этом состоянии — «правильное».
В этом случае агент должен ассоциировать некоторую информацию, предоставленную средой, а не просто слепо выбирать действие влево или вправо.
Подведение итогов
Из этой статьи все может стать сложнее, и вам, возможно, придется в какой-то момент сделать паузу и записать формулы, чтобы доказать их.
Вы узнали о проблеме многорукого бандита и, что более важно, о некоторых методах решения этой проблемы из класса action-value (эпсилон-жадный) и предпочтительного значения (бандитский градиент ).
Кроме того, существуют некоторые методы, такие как оптимистическое начальное значение и верхняя доверительная граница для поощрения исследования и постепенных вычислений. для повышения вычислительной эффективности.
В следующей статье мы узнаем больше об известном фреймворке в RL, Markov Decision Process. После этого у нас будет достаточно базовых знаний, чтобы узнать больше о нескольких методах, включая динамическое программирование, Монте-Карло или временную разницу (SARSA и Q-обучение).
Спасибо, что прочитали эту статью. Если у вас есть какие-либо вопросы, исправления или рекомендации, пожалуйста, не стесняйтесь оставлять комментарии ниже. Ваше мнение очень ценится.
