Выборка Томпсона для задачи о многоруком бандите
В этой статье мы рассмотрим выборку Томпсона, ее алгоритм и реализацию. Также будет обсуждаться бета-распределение, используемое в алгоритме выборки Томпсона.
Проблема многорукого бандита в двух словах
Задача многорукого бандита — это классическая задача обучения с подкреплением, в которой игрок заходит в казино и ставит свои деньги на несколько игровых автоматов с одной рукой. Сначала он пытается исследовать машины, чтобы найти лучшую машину, дающую вознаграждение, и после некоторого начального раунда он использует машину, которая дает максимальные награды.
Томпсон Сэмплинг
Выборка Томпсона — это рандомизированный алгоритм, который наиболее эффективно используется для решения этой классической задачи о многоруком бандите. Он выполняет исследование, выбирая машину с лучшим средним значением выборки (сгенерированным из бета-распределения) среди других машин. Бета-распределение становится все более и более сконцентрированным вокруг эмпирического среднего по мере увеличения количества раундов азартных игр.
Если вы мало что поняли, просто помните, что основная идея состоит в том, чтобы выбрать машину в соответствии с вероятностью того, что она будет лучшей машиной, дающей вознаграждение.
Если вы уже знакомы с бета-версией, вы можете пропустить эту часть, в противном случае продолжайте.
Бета-распределение
Бета-распределение — это непрерывное распределение, которое определяется с точки зрения
тета θ, которая является функцией двух параметров a и b.
Математически
P(θ | a, b) = (θ ^(a-1)) *((1 — θ)^(b-1)) / B(a, b)
Здесь B(a, b) – константа нормализации, представляющая собой бета-функцию
от a и b. Этот знаменатель не является функцией переменной θ.
Он просто гарантирует, что распределение вероятностей интегрируется до 1.
Итак, мы можем сказать, что P(θ | a, b) ∝ θ ^(a-1) * (1-θ) ^ (b-1)где θ ∈ [0,1].
Как бета-распределение зависит от параметров a и b?
Случай 1: когда a = 0,5 и b = 0,5
P(θ | a, b) = (θ ^(a -1)) *((1 — θ)^(b-1)) / B( a, b )
=> P(θ | 0.5,0.5) ∝ θ ^(0.5–1) * (1-θ) ^ (0.5–1)
=> P(θ |0.5,0.5) ∝ θ ^ (-0.5) * (1-θ)^(-0.5)
=> P(θ |0.5,0.5) ∝ 1 / θ ^ (0.5) * (1-θ)^(0.5)
Мы можем ясно видеть, что для θ = 0 или 1 бета-распределение стремится к ∞ (бесконечность).
Случай 2: когда a = 0,5 и b = 1
P(θ | a, b) = (θ ^(a -1)) *((1 — θ)^(b-1)) / B( a, b )
=> P(θ | 0.5,1) ∝ θ ^(0.5–1) * (1-θ) ^ (1–1)
=> P(θ |0.5,1) ∝ θ ^ (-0.5) * 1
=> P(θ |0.5,1) ∝ 1 / θ ^ (0.5)
Мы можем ясно видеть, что если θ = 0, бета-распределение стремится к ∞ (бесконечность), а если тета = 1, бета-распределение пропорционально константе 1.
Случай 2: когда a = 1 и b = 1
P(θ | a, b) = (θ ^(a -1)) *((1 — θ)^(b-1)) / B( a, b )
=> P(θ | 1,1) ∝ θ ^(1–1) * (1-θ) ^ (1–1)
=> P(θ |1,1) ∝ 1 * 1
=> P(θ |1,1) ∝ 1
Мы можем ясно видеть, что для любого значения θ бета-распределение пропорционально константе 1.
Случай 4: когда a › 1,b › 1 и a = b
P(θ | a, b) = (θ ^(a-1)) *((1 — θ)^(b-1)) / B(a, b)
Распределение имеет максимальное значение 0,5. Даже если мы еще больше увеличим a и b еще
, то распределение будет ближе к 0,5.
Случай 5: когда a › 1,b › 1 и a != b
P(θ | a, b) = (θ ^(a-1)) *((1 — θ)^(b-1)) / B(a, b)
Нам не нужно увеличивать и a, и b. Если мы вычислим среднее
бета-распределение, то ожидаемое значение тета,
E[тета] = а / (а + b)
Итак, если мы увеличим b, то распределение сдвинется влево. Если мы увеличим
a, то распределение сдвинется вправо.
Алгоритм выборки Томпсона
Шаг 1: В каждом раунде n рассмотрим два числа для каждой машины m
→ Nᵢ¹(n) — количество раз, когда машина m получала вознаграждение 1 до раунда n
→ Nᵢ⁰(n) — сколько раз машина m получала вознаграждение от 0 до раунда n
Шаг 2: Для каждой машины m мы выбираем случайным образом из следующего распределения:
θᵢ(n) = β( Nᵢ¹(n) + 1, Nᵢ⁰(n) + 1)
Шаг 3: Выберите машину с наибольшим значением θᵢ(n).
Реализация алгоритма выборки Томпсона для решения проблемы многорукого бандита
Предположим, что в казино есть 5 игровых автоматов, и игрок приходит со 100 монетами, чтобы играть и максимизировать вознаграждение от автоматов.
Я использовал этот набор данных MultiArmedBandit.csv и следующий код:
Я получил следующую визуализацию:
Хорошо видно, что если игрок поставит свои деньги на Автомат 5, то он получит максимальное вознаграждение.
Как это произошло на самом деле?
Разбираемся шаг за шагом. Перед этим я хочу, чтобы вы открыли шаги алгоритма в другой вкладке.
- Метод __init__:
В этом методе мы выполнили шаг 1 алгоритма и определили определенные атрибуты.
self.__N → общее количество раундов
self.__m → общее количество машин
self.__machine_selected → список из 100 машин, выбранных по одной в каждом раунде
self.__number_of_rewards_0→ количество раз, когда машина m получала вознаграждение 1 до раунда n.
self.__number_of_rewards_1 →сколько раз машина m получила вознаграждение 1 до раунда n. - Метод implement_thompson_sampling.
В этом методе мы объединили шаги 2 и 3.
В строке 21 будет сгенерировано значение бета от 0 до 1. Это шаг 2.
В строке 22 мы выбираем машину с самым высоким значением бета, что является шагом 3.
Так реализуется сэмплинг Томпсона. Может быть несколько способов реализации. Не стесняйтесь поделиться, если вы решите другим способом.
Ссылки:
