Сэмплирование Томпсона

Рассмотрим множество контекстов ${\displaystyle {\mathcal {X}}}$, множество действий ${\displaystyle {\mathcal {A}}}$ и награды в ${\displaystyle \mathbb {R} }$. Цель игрока — выполнять действия в различных контекстах таким образом, чтобы максимизировать накопленное вознаграждение. В каждом раунде игрок получает контекст ${\displaystyle x\in {\mathcal {X}}}$, выбирает действие ${\displaystyle a\in {\mathcal {A}}}$ и получает награду ${\displaystyle r\in \mathbb {R} }$, распределение которой зависит от выбранного контекста и действия.^[1]

Основные элементы сэмплирования Томпсона включают:

1. Функцию вероятности ${\displaystyle P(r|\theta ,a,x)}$;
2. Множество ${\displaystyle \Theta }$ параметров ${\displaystyle \theta }$ распределения ${\displaystyle r}$;
3. Априорное распределение ${\displaystyle P(\theta )}$ на эти параметры;
4. Совокупность прошлых наблюдений в виде троек ${\displaystyle {\mathcal {D}}=\{(x;a;r)\}}$;
5. Апостериорное распределение ${\displaystyle P(\theta |{\mathcal {D}})\propto P({\mathcal {D}}|\theta )P(\theta )}$, где ${\displaystyle P({\mathcal {D}}|\theta )}$ — функция правдоподобия.

Сэмплирование Томпсона заключается в выборе действия ${\displaystyle a^{\ast }\in {\mathcal {A}}}$ с вероятностью того, что оно максимизирует ожидаемое вознаграждение; действие ${\displaystyle a^{\ast }}$ выбирается с вероятностью

${\displaystyle \int \mathbb {I} \left[\mathbb {E} (r|a^{\ast },x,\theta )=\max _{a'}\mathbb {E} (r|a',x,\theta )\right]P(\theta |{\mathcal {D}})d\theta ,}$

где ${\displaystyle \mathbb {I} }$ — индикаторная функция.

На практике этот подход реализуется сэмплированием. В каждом раунде параметры ${\displaystyle \theta ^{\ast }}$ выбираются сэмплированием из апостериорного распределения ${\displaystyle P(\theta |{\mathcal {D}})}$, и выбирается действие ${\displaystyle a^{\ast }}$, максимизирующее ${\displaystyle \mathbb {E} [r|\theta ^{\ast },a^{\ast },x]}$, то есть ожидаемое вознаграждение при данных сэмплированных параметрах, действии и текущем контексте. Концептуально это означает, что игрок случайным образом формирует свои представления в каждом раунде согласно апостериорному распределению и действует по ним оптимально. Во многих практических случаях вычисление и сэмплирование из апостериорного распределения затруднительно, поэтому сэмплирование Томпсона часто применяется совместно с приближенными методами сэмплирования.^[2]

Сэмплирование Томпсона было первоначально описано Томпсоном в 1933 году. Позднее оно было независимо повторно открыто неоднократно в контексте задачи о многоруком бандите. Первое доказательство сходимости для задачи многорукого бандита было представлено в 1997 году. Первое применение к марковским процессам принятия решений появилось в 2000 году. Связанный подход (баесовское правило управления) был опубликован в 2010 году. В том же году было показано, что сэмплирование Томпсона мгновенно самокорректируется. Результаты по асимптотической сходимости для контекстуальных бандитов появились в 2011 году. Сэмплирование Томпсона широко применяется во многих задачах онлайн-обучения, включая A/B-тестирование в проектировании веб-сайтов и интернет-рекламе, а также для ускоренного обучения при децентрализованном принятии решений. Для дуэльных бандитов, разновидности классических многоруких бандитов с обратной связью в виде парных сравнений, был предложен алгоритм Double Thompson Sampling (D-TS).

Стратегия сопоставления вероятностей — это способ принятия решений, при котором прогнозируемое членство в классе пропорционально базовой частоте класса. Например, если в обучающей выборке положительные примеры встречаются в 60% случаев, а отрицательные — в 40% случаев, наблюдатель, применяющий стратегию сопоставления вероятностей, для новых примеров будет выбирать метку «положительный» с 60% вероятностью и «отрицательный» с 40% вероятностью.

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

Постановка задачи следующая. Пусть ${\displaystyle a_{1},a_{2},\ldots ,a_{T}}$ — действия агента до момента времени ${\displaystyle T}$, а ${\displaystyle o_{1},o_{2},\ldots ,o_{T}}$ — соответствующие наблюдения. Тогда действие ${\displaystyle a_{T+1}}$ выбирается с вероятностью:

${\displaystyle P(a_{T+1}|{\hat {a}}_{1:T},o_{1:T}),}$

где обозначение ${\displaystyle {\hat {a}}_{t}}$ указывает, что ${\displaystyle a_{t}}$ является причинной интервенцией (см. Причинность), а не обычным наблюдением. Если агент делает апостериорные предположения ${\displaystyle \theta \in \Theta }$ о своих типах поведения, тогда баесовское правило управления принимает вид

${\displaystyle P(a_{T+1}|{\hat {a}}_{1:T},o_{1:T})=\int _{\Theta }P(a_{T+1}|\theta ,{\hat {a}}_{1:T},o_{1:T})P(\theta |{\hat {a}}_{1:T},o_{1:T})\,d\theta ,}$

где ${\displaystyle P(\theta |{\hat {a}}_{1:T},o_{1:T})}$ — апостериорное распределение параметра ${\displaystyle \theta }$ по действиям ${\displaystyle a_{1:T}}$ и наблюдениям ${\displaystyle o_{1:T}}$.

На практике баесовское управление реализуется так: на каждом временном шаге из апостериорного распределения ${\displaystyle P(\theta |{\hat {a}}_{1:T},o_{1:T})}$, вычисленного по правилу Байеса только по (причинным) правдоподобиям наблюдений ${\displaystyle o_{1},\ldots ,o_{T}}$ (игнорируя правдоподобия действий ${\displaystyle a_{1},\ldots ,a_{T}}$), сэмплируется параметр ${\displaystyle \theta ^{\ast }}$, после чего действие ${\displaystyle a_{T+1}^{\ast }}$ выбирается из распределения ${\displaystyle P(a_{T+1}|\theta ^{\ast },{\hat {a}}_{1:T},o_{1:T})}$.

Сэмплирование Томпсона и алгоритмы верхней доверительной границы (UCB) обладают фундаментальным свойством, лежащим в основе их теоретических гарантий. Вкратце, оба метода направляют исследовательские усилия на варианты действий, которые могут быть оптимальными, то есть проявляют своего рода «оптимизм». Благодаря этой особенности можно переносить оценки регрета для UCB-алгоритмов на байесовский регрет для сэмплирования Томпсона и унифицировать анализ регрета для этих методов и широкого класса задач.