Выборка Томпсона

Конкретный пример отбора проб Томпсона, примененного для моделирования оценки эффективности лечения

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

Описание

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

Элементы выборки Томпсона следующие:

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

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

$\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 ,$

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

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

История

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

Связь с другими подходами

Вероятностное сопоставление

См. также: Сопоставление вероятностей.

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

Правило байесовского управления

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

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

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

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

$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$,

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

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

Алгоритмы с верхней доверительной границей (UCB)

Алгоритмы выборки Томпсона и алгоритмы верхней доверительной границы имеют общее фундаментальное свойство, которое лежит в основе многих их теоретических гарантий. Грубо говоря, оба алгоритма распределяют исследовательские усилия на действия, которые могут быть оптимальными и в этом смысле являются «оптимистическими». Используя это свойство, можно перевести границы сожаления, установленные для алгоритмов UCB, в байесовские границы сожаления для выборки Томпсона. или унифицировать анализ сожалений для обоих этих алгоритмов и многих классов проблем.