Сколько усилий нужно потратить на разведку и эксплуатацию

Каждый день каждый день сталкивается с одной и той же дилеммой: следует ли мне продолжать делать то, что я делаю, или я должен попробовать что-то еще. Например, следует ли мне пойти в предпочтительный ресторан или попробовать новый, сохранить ли я текущую работу или найти новую и т. Д.

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

Естественно, возникает вопрос, сколько использовать и сколько исследовать.

Однако проблема разведки заключается в том, что мы не знаем, каков будет результат: он может быть лучше, чем текущая ситуация, или может быть хуже.

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

Понятие сожаления

По логике вещей, когда мы пробуем что-то новое, а результат неудовлетворительный, мы сожалеем о своем решении. Если новый ресторан был плохим, мы сожалеем о том, что поехали туда, и считаем, какую бы сумму мы ни заплатили, как полную потерю. Поэтому мы сожалеем об этой сумме.

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

Сможем ли мы это сделать?
Ответ: да, это возможно, по крайней мере, в RL.

Сожаление в обучении с подкреплением

Сначала нам нужно определить сожаление в RL. Для этого мы начнем с определения оптимального действия a * как действия, дающего наибольшее вознаграждение.

Таким образом, мы определяем сожаление L в течение T попыток как разницу между вознаграждением, генерируемым оптимальным действием a *, умноженным на T, и суммой от 1 до T каждой награды за произвольное действие.

Можно доказать, что по мере того, как T стремится к бесконечности, сожаление стремится к нижней границе C. журнал T.

Жадный и Эпсилон Жадный

Методы исследования Greedy и Epsilon Greedy довольно просты для понимания и реализации, но они страдают от серьезной неудачи, заключающейся в неоптимальном сожалении. На самом деле сожаление и Greedy, и Epsilon Greedy линейно растет со временем.

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

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

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

Однако задача состоит в том, чтобы иметь возможность осуществить правильный процесс разложения.

Оптимизм перед лицом неопределенности

Оптимизм перед лицом неопределенности - это подход, позволяющий улучшить исследования и минимизировать общее сожаление.

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

Распределение зеленого Q (a3) ​​имеет довольно узкую основу из-за малого интервала [1.8, 3.2], красный Q (a2) имеет больший интервал [0, 4], и, наконец, синий Q (a1) имеет наибольший интервал [ -1.8, 5.2].
Итак, вопрос в том, какое действие выбрать следующим.

Согласно принципу оптимизма перед лицом неопределенности, мы выбираем действие, которое дает более высокую награду, чем другие, даже если оно имеет более высокую неопределенность. Глядя на график, мы легко обнаруживаем, что Q (a1) может иметь более высокое вознаграждение (5,2), чем другие, поэтому мы выбрали его, даже если он имеет более высокую неопределенность (это может быть 5,2, а может быть -1,8).

Предположим, что было предпринято действие a1, и распределения выглядят следующим образом:

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

Это принцип, но как он будет реализован на практике?
В этом суть UCB1.

UCB1

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

Один из способов сделать это - оценить это, добавив термин, называемый верхней доверительной границей U 𝑡 (a), к Q 𝑡 (a) для каждого действия, затем выберите действие с максимумом Q 𝑡 (a) + U 𝑡 (a).

Само собой разумеется, что U 𝑡 (a) не является постоянным, но должно меняться со временем и опытом.
Мы имеем в виду, что время идет, и мы часто выбираем действие (a), мы становимся все более и более уверенными в том, чего ожидать от Q (a), которое само по себе является средним, поэтому U 𝑡 (a) должно уменьшаться по мере того, как мы становимся более уверенными в Q (a).

Формула U 𝑡 (a) выглядит следующим образом

где t - общее количество попыток, а N 𝑡 (a) - количество раз, когда было выбрано действие (a).
Эта формула ясно показывает, что по мере увеличения t числитель также увеличивается, но логарифмически (например, медленно), в то время как при выборе действия (a) N 𝑡 (a) увеличивается на единицу, однако U 𝑡 (a) резко уменьшается.

Вот пример:

Мы можем видеть, что при изменении t от 100 до 1000 и N 𝑡 (a), равном 1, тогда U 𝑡 (a) очень медленно увеличивается от 2 до 2,45, но когда N 𝑡 (a) увеличилось на 1, U 𝑡 (a) резко упало до 1,73.

Итак, U 𝑡 (a) - это способ регулировать выбор действия (a) на основании того, что мы уже много раз выбирали это действие в прошлом. Другими словами, это дает нам больше уверенности в том, какую награду он может вернуть.

Окончательный алгоритм предусматривает, что для каждой итерации мы вычисляем Q 𝑡 (a) + U 𝑡 (a) для всех действий и выбираем действие с наибольшим Q 𝑡 (a) + U 𝑡 (a) значение:

Такой подход «исследовать против эксплойта» гарантирует логарифмическое сожаление.

ВАЖНО: UCB1 ничего не предполагает относительно типов распределения, хотя на графиках выше они выглядят как гауссовы, но могут быть любыми.

Гауссово распределение

Предположим, мы знаем, что распределение вознаграждений гауссово:
ℛ (r) = 𝒩 (r, μ, σ)

Алгоритм превращается в выбор действия, которое максимизирует стандартное отклонение Q (a)

Сэмплинг Томпсона

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

Конечно, для этого нужно больше объяснений.

Рассмотрим игру в кости, о которой мы не знаем, является она предвзятой или нет, на самом деле у нас нет никакой информации о ней. Поэтому для начала мы предполагаем, что это честная игра в кости и все вероятности выпадения любого числа равны 1/6.
Итак, исходное убеждение состоит в том, что распределение вероятностей равномерно и равно 1/6. Это называется априорным распределением, и оно представляет собой убеждение или предположение (оно может быть ложным), которое у нас есть относительно основного распределения вероятностей игральных костей.
Теперь мы начинаем бросать кости и собирать результаты, и с каждый результат мы обновляем предыдущее распределение, чтобы он отражал реальность эксперимента. Новое распределение теперь называется апостериорным. Мы продолжаем повторять этот процесс большое количество итераций, в которых апостериор на итерации (i) становится апостериорным на итерации (i + 1), пока мы не достигнем стадии, на которой окончательное апостериорное распределение очень близко к реальному базовому распределению. < br /> Например, если мы замечаем, что после большого количества бросков у нас есть одно число, которое преобладает над другими, это означает, что распределение не может быть равномерным, и, скорее всего, игра в кости смещена.

Теперь возникает вопрос: как обновить априорное распределение, чтобы получить апостериорное распределение?

Чтобы ответить на этот вопрос, давайте начнем с определения бета-распределения:
Бета-распределение - это семейство непрерывных распределений вероятностей, определенных на интервале [0, 1], параметризованных двумя положительными параметрами α и β, которые определяют форму распределения. .

Вы можете думать о бета-распределении как о семействе распределений, в котором каждый член отличается от другого согласно значениям параметров 𝝰, β.

Ниже приведены некоторые образцы форм, которые может иметь бета-распределение после значений, которые могут иметь 𝝰, β.

Как пробовать?

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

Например, возьмите третий график во второй строке из приведенного выше набора графиков. Это распределение достигает максимума около 0,84. Таким образом, при выборке из этого распределения оно с большей вероятностью будет иметь значение около 0,84, чем, например, значение менее 0,4.

Теперь предположим, что у вас есть несколько действий, каждое с неизвестным распределением вознаграждения. Мы используем выборку Томпсона, чтобы определить, какое действие является лучшим (оно максимизирует среднее вознаграждение). Мы начинаем с предположения об определенном распределении, таком как Beta (1,1), которое является равномерным распределением для каждого действия, затем мы производим выборку этих распределений и выбираем действие, которое имеет наибольшее значение выборки.
После того, как выбранное действие является выполняется и награда собирается, распределение выбранного действия обновляется.

Возьмем следующий пример многоруких бандитов (игровых автоматов).
Пример состоит из трех многоруких бандитов: синего, красного и фиолетового.
Поскольку мы ничего не знаем о лежащих в основе Распределение этих бандитов мы предполагаем равномерным. Мы производим выборку из этих распределений и получаем следующие результаты: синий = 0,4, красный = 0,5, фиолетовый = 0,7
Оказывается, фиолетовый цвет имеет наибольшее значение выборки, поэтому мы тянем за руку фиолетовой машины. Предположим, что мы не выиграли, поэтому нам нужно обновить наше мнение о пурпурном распределении, увеличив параметр β на единицу, чтобы стать бета-версией (1, 2), что даст первый график ниже.

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

Заключение

В этой статье представлены некоторые из наиболее часто используемых методов исследования, применяемых в обучении с подкреплением. Главный вывод из этого - знать, что изучение действий, которые имеют низкий приоритет от оптимальности, - это пустая трата времени и ресурсов. По этой причине важно использовать методы исследования, которые сводят к минимуму сожаления, чтобы этап обучения стал более быстрым и эффективным.