что такое epsilon / k как это получилось в жадном алгоритме epsilon

Question

Как было сказано, он выберет руку, имеющую наивысшее эмпирическое среднее значение с вероятностью 1-эпсилон, как прибавила к ней эпсилон / k (а также эпсилон / k для случайного выбора вероятности) в уравнении, написанном для вероятности на странице №: 6 статьи Алгоритмы для многоруких бандитов . Что означает запись в уравнение

epsilon / k?

Answer 1

Позвольте мне попытаться высказать свою точку зрения здесь.Давайте рассмотрим аналогичный пример 3 машин: A, B и C и предположим, что B имеет самую высокую выплату.

Если эпсилон равен 0,1, то какова вероятность выбора B?

ВспомнитьЭпсилон Жадный алгоритм, он говорит:

 r = random() # any random number between 0 and 1(uniform distribution)
 if r > epsilon:
    choose "Best pay out at current time" #(currently it is B)
 else:
    choose randomly between three machines

так, каково вероятное количество шансов на выбор B из 100 шансов: Это будет сумма из следующих двух: 1) 90 шансов из 100 (если условие) 2) треть шансов из оставшихся 10 (еще условие), поскольку есть 3 машины (равная вероятность выбора каждой из них)

Таким образом, общие шансы могут быть 90 + 10 * (1/3) (приблизительно) = 93,33

Но подождите, что, если эпсилон равен 0,5?Тогда общие шансы будут 95 + 5 * (1/3) = 96,67

То есть, мы говорим, вероятность выбора машины с самой высокой текущей средней выплатой с вероятностью = (1 - эпсилон) + (эпсилон /k).

Надеюсь, это поможет.

Answer 2

Этот ответ был взят из здесь :

Предположим, вы стоите перед k = 3 игровыми автоматами.Каждая машина рассчитывается в соответствии с различным распределением вероятностей, и эти распределения вам неизвестны.И предположим, что вы можете сыграть в общей сложности 100 раз.

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

Эпсилон-жадный почти слишком прост.Играя на машинах, вы отслеживаете среднюю выплату каждой машины.Затем вы выбираете машину с наибольшей текущей средней выплатой с вероятностью = (1 - эпсилон) + (эпсилон / k), где эпсилон - это небольшое значение, например 0,10.И вы выбираете машины, которые не имеют наибольшую текущую среднюю выплату с вероятностью = epsilon / k.Это гораздо проще понять на конкретном примере.Предположим, что после ваших первых 12 попыток вы играли на машине № 1 четыре раза и выигрывали $ 1 два раза и $ 0 два раза.Среднее значение для машины № 1 составляет $ 2/4 = $ 0,50.

И предположим, что вы играли на машине № 2 пять раз и выиграли $ 1 три раза и $ 0 два раза.Средняя выплата для машины № 2 составляет $ 3/5 = $ 0,60.

Предположим, вы играли на машине № 3 три раза и выиграли $ 1 один раз и $ 0 два раза.Средняя выплата для машины № 3 составляет $ 1/3 = $ 0,33.

Теперь вам нужно выбрать машину для игры на попытке № 13. Вы генерируете случайное число p от 0,0 до 1,0.Предположим, вы установили epsilon = 0.10.Если p> 0,10 (что будет 90% времени), вы выбираете машину № 2, потому что она имеет самую высокую текущую среднюю выплату.Но если p <0,10 (что будет составлять только 10% времени), вы выбираете случайную машину, поэтому у каждой машины есть шанс выбора 1/3. </p>

Обратите внимание, что машина # 2 может получитьвыбран в любом случае, потому что вы выбираете случайным образом из всех машин.

Со временем лучшая машина будет играть все чаще и чаще, потому что она будет выплачиваться чаще.Короче говоря, эпсилон-жадный означает, что большую часть времени выбирает лучший вариант («жадный»), но иногда выбирает случайный вариант с малой (эпсилон) вероятностью.

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