Верхняя граница достоверности для задачи о многоруких бандитах
В этой статье мы обсудим верхнюю доверительную границу и этапы ее алгоритма.
Как мы видели в статье Задача многоруких бандитов, у нас есть 5 или более игровых автоматов, в которых мы ставим свои деньги таким образом, чтобы наша прибыль была максимальной.
Каждая машина имеет свое распределение, по которому определяется ваша прибыль. Мы сбалансированно используем комбинацию методов разведки и эксплуатации, чтобы увеличить нашу прибыль. У нас не может быть только разведки или только эксплуатации, поскольку они могут не дать нам оптимального решения нашей проблемы.
Верхняя доверительная граница
UCB — это детерминированный алгоритм обучения с подкреплением, который фокусируется на исследовании и эксплуатации на основе доверительной границы, которую алгоритм назначает каждой машине в каждом раунде. разведки. Эти границы уменьшаются, когда машина используется больше по сравнению с другими машинами.
Шаги, выполняемые в верхней доверительной границе
- В каждом раунде n мы рассматриваем два числа для машины m.
-›Nₘ(n) = количество раз, когда машина m выбиралась до раунда n. .
-> Rₘ(n) = количество наград автомата m до раунда n. - На основании этих двух чисел мы должны вычислить,
а. Среднее вознаграждение машины m до раунда n: rₘ(n) = Rₘ(n) / Nₘ(n).
b. Доверительный интервал [rₘ(n) — Δₘ(n), rₘ(n)+Δₘ(n)] в раунде n с Δₘ(n)= sqrt( 1,5 * log(n) / Nₘ(n )) - Мы выбираем машину m с максимальной UCB,(rₘ(n)+Δₘ(n))
Я знаю, что это очень математически, но давайте разберем это на примере:
Предположим, у вас есть 5 игровых автоматов, и с каждым из них связано определенное количество раздач. Если кто-то знает заранее об этих распределениях, он может легко максимизировать прибыль. Предположим, что мы знаем априорные распределения всех этих машин, например, машина M1 имеет распределение D1, M2 имеет распределение D2, M3 имеет распределение D3, M4 имеет распределение D4 и M5 имеет распределение D5.
Как мы можем ясно видеть, что Машина 3 имеет самое высокое распространение. Но, как и в реальной жизни, вы не знаете дистрибутивы заранее, поэтому мы будем считать, что наши дистрибутивы одинаковы для всех машин.
Формула в алгоритме создает доверительную границу, и предполагается, что доверительная граница содержит фактическое распределение.
Эти доверительные границы представлены в виде прямоугольника на рисунке выше. Прямо сейчас каждый из них имеет одинаковую доверительную границу, поэтому мы берем машину 1 с распределением 1. Теперь в раунде 1 после применения алгоритма UCB ее доверительная граница становится немного ниже.
Теперь мы снова пройдемся по всем машинам и найдем, какая из них имеет более высокую доверительную границу. Кроме D1, каждое другое распределение имеет такую же доверительную границу, которая больше, чем D1. Итак, в данном случае мы можем взять любую из машин, кроме М1. В этом прелесть этого алгоритма. Даже если одна из машин работает лучше, чем другие, алгоритм не начинает использовать только эту машину. Это дает возможность исследовать и другие машины.
Скажем, во втором раунде вы получаете что-то вроде этого:
И, скажем, после 5-го раунда граница уверенности выглядит так:
После каждого раунда доверительная граница для выбранной машины будет сокращаться, тем самым избегая предвзятости по отношению к одной машине и давая шанс другим. Наконец, машина, которая может дать большую прибыль (в данном случае ее машина 3), всегда будет иметь более высокую границу доверия, чем другие, тем самым используя ее для получения максимального вознаграждения.
Так работает алгоритм верхней доверительной границы. Это началось с изучения всех машин, которые имеют наивысшую степень достоверности, тем самым найдя лучшую машину после некоторого исследования, а затем начали пожинать плоды, чтобы максимизировать прибыль.
Ссылки:
