Добби проблема

Основные концепции обучения с подкреплением

Многорукая бандитская машина — распространенная проблема обучения с подкреплением, поэтому сначала мы дадим некоторые основные концепции обучения с подкреплением:

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

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

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

Exploration-Exploitation tradeoff

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

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

Происхождение проблемы многорукого бандита

Часть контента воспроизводится сОт выборки Томпсона к обучению с подкреплением — снова проблема многорукого бандита

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

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

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

(Bernoulli Bandit) Допустим у нас есть бандитская машина K-плеч, отдача (reward_i) каждой руки (действия) фиксирована, но агент не знает, какова эта отдача, как агент может максимизировать свою за T раундов Отдача (обратите внимание, что T здесь обычно намного больше, чем K).

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

Problem Formulation

Мы определяем здесь в простейшей форме K-вооруженную бандитскую машину, которая состоит из K распределений вероятности вознаграждения. <D_1, D_2, ..., D_K> состав, который, как ожидается, $\mu_1, \mu_2, ..., \mu_K$ , дисперсия $\sigma_1^2, \sigma_2^2, ..., \sigma_K^2$ . В каждом раунде попыток (t = 1, 2, ...) игрок выбирает руку j(t) , и получить возврат $r(t) \sim D_{j(t)}$ .

Цель алгоритма — минимизировать общее ожидаемое сожаление и определяется как:

В определенном фиксированном раунде T $R_T = T_{\mu}^* - \sum_{t = 1}^T \mu_{j(t)}$ ,в $\mu ^*$ представляет собой ожидаемую доходность руки с наибольшей доходностью.
Следовательно, мы можем выразить общее ожидаемое сожаление следующим образом: $R_T = T_{\mu}^* - \mu_{j(t)}\sum_{t = 1}^T E(T_k(T))$ .в— случайная величина, используемая для обозначения того, сколько раз k-я рука была вытянута в первом T раунде.

$\epsilon - greedy$ алгоритм

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

$\epsilon - greedy$ Алгоритм представляет собой улучшенное решение исходного жадного алгоритма, который заключается в исследовании в соответствии с эпсилон-вероятностью, выборе руки для попытки в соответствии с равномерным распределением и выборе действия с наибольшей отдачей в текущей ситуации в соответствии с вероятностью 1-эпсилон. Хотя этот подход лучше, чем чисто жадный случай, для следующего случая мы знаем из исследования, что вероятность действия 2 намного меньше, чем вероятность действия 1, но он все равно будет многократно проверять действие 2 с определенной вероятностью, увеличивая потеря.

Проще говоря, при заданном параметре $\epsilon \in (0, 1)$ , вероятность того, что алгоритм примет решение в t+1-м раунде при k, равна:

Thompson Sampling

Основная идея выборки Томпсона состоит в том, чтобы выбрать руку с наибольшей вероятностью, чтобы быть оптимальной рукой. Это байесовский алгоритм. Для простоты рассмотрим возврат Бернулли, задачу МАВ с возвратом 0 или 1. при этих обстоятельствах, Мы можем использовать бета-распределение, чтобы описать распределение вознаграждения за каждое действие, и мы задаем параметры априорной вероятности распределения альфа и бета, а затем функцию плотности вероятности вознаграждения за действие:

это здесь, $\alpha$ и $\beta$ То есть до трейла t-1, количество успехов и неудач. Тогда для Бернулли MAB алгоритм

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

И мы можем обобщить результат распределения Бернулли. Если доходность любого плеча распределена между [0, 1] и среднее значение равно $\mu_i$ , Мы получаем каждый раз $\widetilde{r_t} \in [0, 1]$ Обновите результат после награды. Мы завершаем показатель успеха $\widetilde{r_t}$ Испытания Бернулли со случайными величинами r_t Указывает результаты теста. все еще использую $\{S_i(t), F_i(t)\}$ Записывая количество успехов и неудач до текущего номера раунда, мы обновляем результаты по следующему алгоритму:

Upper Confidence Bounds(UCB)

UCB — это семейство алгоритмов, включающее множество различных алгоритмов, ядром которых является оценка UCB.

Самый простой алгоритм UCDB — UCB1. Для каждой руки он записывает число n_i(t) , представляет количество раз, когда i-я рука выбирается в первых t раундах. В начале каждая рука будет выбрана один раз. После этого в раунде t он выбирает j(t) можно выразить как $j(t) = argmax_{i=1,2,..,k} (\hat{\mu_i} + \sqrt{2lnt/n_i})$

LinUCB (Linear UCB)

Этот раздел переведен из «Контекстно-бандитский подход к рекомендации персонализированных новостных статей». LinUCB — это контекстный алгоритм MAB. Так называемый контекстный алгоритм представляет собой форму: в нашем исходном предположении ожидание результата одной руки всегда постоянно, независимо от того, какое время. Но в практических приложениях, в разных средах, преимущества, которые пользователи получают от разных элементов, часто различны. На этом этапе нам нужно использовать контекстный алгоритм обработки, то есть мы обучаем модель для каждой руки, и эта модель будет выводить разные ожидаемые результаты в соответствии с разными входными характеристиками. В LinUCB эта модель является линейной.

Ключом к LinUCB является то, что параметр определяется как d-мерный вектор. Определим параметры плеча a как $\theta_{ a}$ , а для d-мерного вектора признаков вознаграждение любой руки представляет собой линейное произведение вектора признаков и вектора параметров. Тогда для любого t в t раунде для d-мерного признака ожидание вознаграждения руки a равно $E(r_{t, a}|x_{t, a}) = x_{t, a}^T\theta_a^*$

LinUCB with disjoint Linear Models

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

Мы разрабатываем размерную матрицу m * d D_a , в раунде t, D_a Состоит из m обучающих входных данных (скажем, m предыдущих наблюдений для руки a). m-мерный вектор b_a Представляет соответствующий вектор ответа. для конкретной матрицы (D_a, b_a) , мы можем использовать гребенчатую регрессию для оценки матрицы параметров $\hat{\theta_a} = (D_a^TD_a + I_d)^{-1}D_a^Tb_a$ .

При этом условии можно показать, что по крайней мере $1 - \delta$ уверенность, $|x_{t, a}^T\hat{\theta_a} - E(r_{t, a}|x_{t, a})| \le \alpha \sqrt{x_{t, a}^T(D_a^TD_a + I_d)^{-1}x_{t,a}}$ ,в $\alpha =1 + \sqrt{ln(\delta/2)/2}$ . Это UCB под эту модель.

Поэтому в этой модели в каждом испытании t мы выбираем $a_t = argmax(x_{t, a}^T\hat{\theta_a} + \alpha \sqrt{x_{t, a}^T(A_a)^{-1}x_{t,a}})$ ,в A_a = D_a^TD_a + I_d .

LinUCB with Hybrid Linear Models

Во многих системах будут некоторые общие параметры для различных ветвей, и каждая ветвь будет иметь независимые параметры. Например, в задаче системы рекомендаций функции о пользователе и текущем времени могут иметь общие параметры, а параметры каждого элемента не зависят друг от друга. При этом определении мы по-прежнему определяем параметры независимой части как $\theta_a^*$ , и задайте параметры общей части как $\beta^*$ . следовательно $E(r_{t, a}|x_{t, a}) = x_{t, a}^T\theta_a^* + z_{t, a}^T\beta^*$ . В этом случае алгоритм такой:

hLinUCB (Hidden Linear UCB)

Этот раздел переведен из «Изучение скрытых функций для контекстных бандитов».

LinUCB построен на предположении, что мы можем наблюдать все соответствующие функции и добавлять их в модель. Но на самом деле такая ситуация почти невозможна, и должны быть скрытые и ненаблюдаемые особенности. Основанный на linUCB, hLinUCB пытается смоделировать скрытые функции. Он по-прежнему следует линейной модели, но добавляет скрытый вектор признаков и соответствующий параметр.

определение $r_{a_t,u} = (x_{a_t},v_{a_t})^T(\theta_u^x, \theta_u^v) + \eta_t$ ,в $x_{a_t} \in R^d , v_{a_t} \in R^l$ . $x_{a_t}$ и $v_{a_t}$ представляют наблюдаемый ввод и скрытый ввод, соответственно, $\theta_u^x, \theta_u^v$ является соответствующим параметром. Эти переменные удовлетворяют ограничениям $||(x_a, v_a)||_2 \le L, ||\theta_u = (\theta_u^x, \theta_u^v)||_2 \le S$ . В дополнение к этим переменным $x_{a_t}$ неизвестны, мы ставим цель гребневой регрессии как

По этой формуле можно оценить $\theta_u$ и v_a . $\hat{\theta_{u, t}} = A_{u, t}^{-1}b_{u,t}$ а также $\hat{v_{a,t}} = C_{a,t}^{-1}d_{a,t}$ ,в

В конечном итоге выбор, сделанный согласно UCB, таков: