В этом разделе в основном сделаны некоторые заметки о соответствующем содержании книги Саттона «Обучение с подкреплением» и кратко представлено решение проблемы бандитов.

описание проблемы

Задача о многоруких бандитах называется «Многорукие бандиты». Это классическая задача обучения с подкреплением.

Многорукий игровой автомат произошел от азартных игр, и описание проблемы выглядит следующим образом:

Игрок хочет пойти в казино, чтобы поиграть в игровые автоматы.Он обнаруживает, что в казино есть ряд игровых автоматов.Они выглядят совершенно одинаково, но вероятность выигрыша на каждом игровом автомате различна.Он не знает, что такое Распределение вероятности выигрыша каждого игрового автомата таково.Так что для этого игрока, который хочет разбогатеть, какой игровой автомат он должен выбирать каждый раз, чтобы максимизировать вознаграждение?

Мы рассматриваем выбор игрового автомата как действие $a$ , каждому действию соответствует значение $q(a)$ , выраженное ожиданием вознаграждения, производимого действием. Тогда задачу можно записать в математической форме:

q(a)=E[R_t|A_t=a]

в, $A_t$ представляет действие, выполненное в момент времени t, $R_t$ Указывает на награду. Как оценить это ожидание? Самый простой способ сделать это — рассчитать среднее значение фактических вознаграждений:

Q_t(a)=\dfrac{Сумма выгод, полученных от выполнения действия a до момента времени t}{Количество раз, когда действие a выполняется до момента времени t}

Этот метод оценки также называется методом выборочного среднего. Потому что каждая оценка представляет собой среднее значение соответствующих вознаграждений. Далее рассматриваем только действия $a$ , для упрощения записи положим $R_i$ Указывает, что действие было выполнено $i$ Награды, полученные позже, $Q_n$ Указывает, что действие выбрано для выполнения $n-1$ После первого $n$ оценка стоимости второго исполнения, то есть

\begin{aligned} Q_{n+1}&= \dfrac{1}{n}\sum_{i=1}^n R_i \\ &= \dfrac{1}{n}( R_n+(n-1)\dfrac{1}{n-1}\sum_{i=1}^{n-1} R_i) \\ &= \dfrac{1}{n}( R_n+(n-1)Q_n) \\ &=Q_n+\dfrac{1}{n}[R_n-Q_n] \\ &=Q_n+\alpha[R_n-Q_n] \end{aligned}

размер шага здесь $\alpha$ это $\frac{1}{n}$ . Размер шага фиксированный и равномерный, то есть метод выборочного среднего, который может устранить отклонение выборки. Кроме того, размер шага может быть и другими параметрами в интервале [0,1].

Выбор действия

В выборе действия есть две важные концепции: одна — исследование, а другая — эксплуатация. Когда мы выбираем действия, мы часто оцениваем каждое действие, чтобы легко измерить качество действия. Действия с высокой ценностью называются жадными действиями. Эксплуатация — это выбор всего, что вы в настоящее время знаете о ценности действия, то есть выбор жадного действия, а эвристика — выбор нежадного действия.

В процессе исследования краткосрочное вознаграждение может быть ниже, но в долгосрочной перспективе, когда будет обнаружено все более и более эффективное действие, выгоды будут больше, чем выгоды от разработки действий в соответствии с текущей стратегией. Но у искушения есть и тот недостаток, что оно занимает много времени. Невозможно разрабатывать и исследовать одновременно в одном выборе действия, поэтому баланс между исследованием и развитием также является важным вопросом при выборе действия.

$\epsilon-greedy$

При выборе упомянутых выше действий используется жадный алгоритм, который собственно и называется $\epsilon-greedy$ алгоритм.

A_t=\arg\max_a Q_t(a)

В частности, чтобы максимизировать текущее вознаграждение, в большинстве случаев жадный выбор действия только с очень небольшой вероятностью $\epsilon$ Только прыгать из жадности и выбирать случайным образом среди других действий.

UCB-алгоритм

Существует также алгоритм выбора действия, называемый алгоритмом UCB (верхняя граница достоверности), который представляет собой метод, основанный на верхней границе достоверности. Из-за того, что жадные действия всегда сосредоточены на самой большой награде перед ними, а недостаточное исследование долгосрочных действий, они могут упустить оптимальное действие, и $\epsilon-greedy$ Исследование является случайным, на самом деле некоторые действия были выбраны много раз, и неопределенность относительно мала, и эти неопределенные действия необходимо исследовать много раз. UCB учитывает это, а также учитывает неопределенность значения вознаграждения и действия в следующей форме:

A_t=\arg\max_a [Q_t(a)+c\sqrt{\dfrac{lnt}{N_t(a)}}]

где c представляет собой константу больше 0, которая управляет степенью эвристики, $N_t(a)$ Представляет количество раз, когда действие a выбирается до времени t. как $N_t(a)=0$ , то a — действие, удовлетворяющее максимизации. Основная идея UCB заключается во введении доверительных интервалов. Параметр c определяет уровень достоверности, который, говоря простым языком, определяет степень неопределенности. Квадратный корень в правой части уравнения является мерой неопределенности для оценки действия a. По мере того, как увеличивается количество раз, когда a выбирается, т. е. $N_t(a)$ Увеличится, правильный член уменьшится, доверительный интервал сузится, а неопределенность уменьшится, т. е. а уже не так просто выбрать, и действие с большим средним, т. е. имеет тенденцию быть избранным. Кроме того, если а выбирается не каждый раз, а с увеличением времени t, числитель правого члена также увеличивается, доверительный интервал становится шире, а неопределенность а увеличивается при более позднем выборе, то есть a также может быть выбран снова.

Алгоритм игрового автомата Gradient

Приведенные выше алгоритмы рассматривают значение каждого действия для выбора действия.Алгоритм градиентного игрового автомата имеет другую идею.Вместо непосредственного рассмотрения значения действия для каждого действия вводится числовая функция предпочтения a. $H_t(a)$ , рассмотрим относительное предпочтение одного действия над другим. $H_t(a)$ Чем крупнее действие, тем больше вероятность того, что оно будет выбрано. Однако стоит отметить, что $H_t(a)$ Это не имеет ничего общего с ценностью вознаграждения, это только сравнение одного действия с другим. $t$ момент действия $a$ Вероятность быть выбранным может быть представлена распределением softmax:

Pr(A_t=a)=\dfrac{e^{H_t(a)}}{\sum^k_{b=1}e^{H_t(b)}}=\pi_t(a)

Стохастическое градиентное восхождение обновляет функцию предпочтения:

H_{t+1}(A_t)=H_t(A_t)+\alpha(R_t-\overline{R}_t)(1-\pi(A_t)) \\ H_{t+1}(a)=H_t(a)+\alpha(R_t-\overline{R}_t)\pi(a) \;for\; all\;a\neq A_t

$\overline{R}_t$ Представляет среднее значение вознаграждения в момент времени t, если выбрано действие $A_t$ Если вознаграждение за пост больше текущего среднего, вероятность того, что действие будет выбрано в следующий момент, будет увеличиваться, а вероятность других действий, которые не были выбраны, будет обновляться в противоположном направлении, в противном случае вероятность будет уменьшаться. Эта часть может относиться к подробному выводу в книге.

Существует также байесовский метод (также называемый выборкой Томпсона, апостериорной выборкой), который предполагает начальное распределение известных значений действия, а затем обновляет распределение после выбора каждого действия.

резюме

Как сбалансировать разведку и разработку — важный вопрос. $\epsilon-greedy$ Жадный алгоритм заключается в случайном выборе действий без учета теста; алгоритм UCB учитывает неопределенность действия и реализует тест, предпочтительно выбирая те действия с меньшим количеством выборок в каждый момент времени. Алгоритм градиентного игрового автомата имеет другую идею, не оценивает ценность действия, вводит функцию предпочтения и использует распределение softmax для вероятностного выбора действий.

Ссылаться на