Позвольте сделать проблему немного более… сложной!

Резюме

Это продолжение оригинального поста, я настоятельно рекомендую сначала пройти его, где мы поняли интуицию многорукого бандита и попытались применить электронные жадные алгоритмы для решения типичной проблемы. Но мир не так прост. Есть несколько факторов, при введении которых проблема полностью меняется, и решение необходимо пересматривать. Мы выберем место, где мы остановились, представим новую проблему, покажем, как наш любимый алгоритм дает сбой, и попытаемся интуитивно понять, что может помочь в этом случае.

Нестационарные задачи

Если мы вспомним проблему из первого поста, мы определили несколько порталов с фиксированным распределением вознаграждения и попытались приблизить нашу оценочную ценность действия к ожидаемой ценности действия или распределению вознаграждения. Теперь основная часть определений остается прежней, но мы просто настроим часть фиксированного распределения вознаграждения. В исходной задаче мы определили функцию распределения вознаграждения, значения которой не менялись на протяжении всего процесса, но что, если они изменяются? Что делать, если ожидаемая ценность действия непостоянна? Что касается игры с домашним порталом, что, если домашний портал постепенно становится океаном или наоборот, или просто колеблется достаточно, чтобы вызвать серьезную путаницу. В таком случае будет ли работать наш простой алгоритм e-greedy? Что ж, давай попробуем выяснить.

Во-первых, при запуске исходного кода для генерации оптимального процента выбора действия наш график выглядит так, как ожидалось, даже при увеличении шагов до 10k, эпсилон-значение 0,01 превосходит настройку контрастности e = 0 или 1. И производительность постоянно, без признаков снижения в будущем.

Теперь нам нужна небольшая модификация, чтобы преобразовать стационарную задачу в нестационарную. Согласно определению, распределение вознаграждений может быть изменено. Давайте определим срок изменения, скажем, после каждого шага, с помощью нормального распределения со средним значением 0 и отклонением 0,01. Итак, после каждого шага мы будем вычислять случайные числа на основе определенного нормального распределения и добавлять его к предыдущему ожидаемому значению действия. Теперь это будет новое распределение наград. Это можно легко сделать, добавив несколько строк в исходный код, а затем мы сможем вычислить последний процент выбора оптимального действия.

# define a function to update the expected_action_value
>>> def update_expected_action_value(expected_action_value):
>>>    expected_action_value += np.random.normal(0, 0.01, arms) 
>>>    return(expected_action_value)
# inside the multi_arm_bandit_problem function add, 
>>> estimate_action_value = update_estimate_action_value(estimate_action_value)

Что ж, сравнивая, мы могли бы сказать, что производительность электронных жадных алгоритмов начала снижаться через определенный период. Обратите внимание: хотя e = 0,01 по-прежнему показывает хорошие результаты, но это резкое снижение производительности видно даже при небольшом случайном приращении (отклонение 0,01), что, если бы коэффициент изменения был более высоким? Как оказалось, снижение было бы более заметным. Возникает вопрос, в чем могла быть проблема?

Оценка распределения вознаграждения

Давайте попробуем вспомнить функцию оценки истинного распределения вознаграждения, она выглядит примерно так:

куда,

  1. Первое уравнение дает формулу для расчетного значения вознаграждения в t, которое представляет собой простое среднее всех вознаграждений, полученных нами до временного шага t-1.
  2. Второе уравнение - это просто хороший способ записать то же самое. Предположим, что оценка для шага n+1 будет средней для всех наград до шага n.
  3. Третий - это то, что вы получите, если развернете второе уравнение и вставите формулы Qn, которые аналогичны формуле Qn+1, только на один шаг меньше (замените n на n-1). Здесь Qn+1 - новая оценка для n+1 шагов, Qn - старая оценка, т. Е. Оценка до этапа _12 _, _ 13_ - вознаграждение за nth шаг, а 1/n - размер шага, на который мы хотим обновить новую оценку.

Для ясности, согласно этой формулировке, если конкретное действие было выбрано, скажем, 5 раз, то каждое из 5 вознаграждений (n действий приводит к n наградам) будет разделено на 1/5, а затем добавлено для получения оценки до шага 5. Если вы присмотритесь, вы увидите, что мы придаем равные веса всем наградам, независимо от времени их возникновения, что означает, что мы хотим сказать, что каждая награда одинаково важна для нас и, следовательно, равные веса. Это верно для стационарных задач, но как насчет более новой задачи? С изменением распределения вознаграждений лучшая оценка истинного распределения вознаграждений - не последнее. Так не следует ли нам просто придавать большее значение новым наградам и меньше - старым? Что ж, эта мысль определенно заслуживает внимания. А это означало бы просто изменить весовые коэффициенты вознаграждения, что можно сделать, заменив среднюю оценку вознаграждения экспоненциально-взвешенным средним. В дальнейшем мы можем сделать этот процесс универсальным, предоставив вариант того, должны ли новые или старые награды иметь больший вес, или средний обходной путь, заключающийся в уменьшении веса со временем. Как оказалось, это можно легко сделать, заменив ступенчатую функцию 1/n в старой формулировке на константу, скажем 𝛂. Это обновляет функцию оценки до

куда,

  1. Если 𝛂 = 1; Rn т.е. самая последняя награда будет иметь максимальный вес 1, а остальные будут иметь 0. Поэтому, если отклонение вашего значения исключенного действия слишком велико, мы можем использовать эту настройку.
  2. Если 𝛂 = 0; Q1 т.е. самая старая оценка вознаграждения будет иметь максимальный вес 1, а остальные будут иметь 0. Мы можем использовать это, когда мы хотим рассматривать только начальные значения оценки.
  3. Если 0 ‹𝛂‹ 1; вес уменьшается экспоненциально в соответствии с показателем 1-𝛂. В этом случае самая старая награда будет иметь меньший вес, а последняя награда - выше. И это то, что мы хотим попробовать.

Нестационарное решение

Давайте формализуем решение, просто обновив код, заменив размер шага константой значения, скажем 0,1, и оставив остальные параметры такими же. Это реализует экспоненциально убывающий вес. Позже мы вычислим оптимальный процент выбора действий и задумаемся над ним.

# update the estimation calculation
>>> estimate_action_value[action] = estimate_action_value[action] + 0.1 * (reward - estimate_action_value[action])

Что ж, мы снова в деле. Мы можем заключить,

  1. Параметр e = 0,01 превосходит своего конкурента, и производительность достигает максимума после нескольких шагов. Здесь мы не видим никакого снижения производительности из-за нашей модифицированной функции оценки, которая учитывает меняющийся характер распределения вознаграждения.
  2. Функция оценки дает представление о состоянии окружающей среды, на основе которого нам нужно будет разработать функцию. Что касается стационарной задачи, мы смогли обойтись базовым средним, но для сложной среды с изменяющимся распределением вознаграждения нам пришлось применить экспоненциально убывающее среднее значение вознаграждения.
  3. Это дает интуитивное представление о том, как математически, просто изменив один параметр размера шага, мы смогли учесть сложное поведение новой среды, которое на самом деле было очень похоже на проблемы реального мира.

Заключение

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

Ваше здоровье.

Ссылка

[1] Обучение с подкреплением - Введение; Ричард С. Саттон и Эндрю Дж. Барто