Многорукий бандит для общего распределения наград

11

Я работаю над проблемой многорукого бандита, где у нас нет никакой информации о распределении наград.

Я нашел много работ, которые гарантируют оценки сожаления для распределения с известной оценкой и для общих распределений с поддержкой в ​​[0,1].

Я хотел бы выяснить, есть ли способ добиться хороших результатов в среде, где распределение вознаграждений не дает никаких гарантий относительно его поддержки. Я пытаюсь вычислить непараметрический предел допуска и использую это число для масштабирования распределения вознаграждений, чтобы я мог использовать алгоритм 2, указанный в этом документе ( http://jmlr.org/proceedings/papers/v23/agrawal12/agrawal12.pdf ). Кто-нибудь думает, что этот подход будет работать?

Если нет, может кто-нибудь указать мне на правильное место?

Огромное спасибо!

references multiarmed-bandit гость
источник

Ответы:

6

Исследование алгоритмов MAB тесно связано с теоретическими гарантиями производительности. Действительно, возрождение интереса к этим алгоритмам (напомним, выборка Томпсона была предложена в 30-х годах) действительно произошло только после того, как в статье Ауэра 2002 года было доказано, что сожалеет о границах для различных UCB и -greedy. алгоритмы. Таким образом, мало интересны проблемы, в которых распределение вознаграждений не имеет известной границы, поскольку теоретически почти ничего нельзя сказать.O(log⁡(T))ϵ

Даже простой алгоритм выборки Томпсона, о котором вы упомянули, требует распределенных вознаграждений Бернулли, и даже на то, чтобы доказать логарифмическую оценку сожаления, потребовалось 80 лет!

На практике, однако, в случаях, когда вы точно не знаете распределение вознаграждений, вы можете просто увеличить его до путем деления на большое число , а если вы наблюдаете вознаграждение выше просто удвойте значение, . Тем не менее, нет никаких гарантий сожаления при использовании этого подхода, но обычно он работает довольно хорошо.[0,1]SSS:=2S

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

fairidox
источник
1
Большое спасибо за ответ! Я очень ценю это! У меня был вопрос, хотя. Я думаю, что алгоритм 2 на бумаге (в верхней части страницы 39.4), о котором я упоминал, не требует ничего о распределении наград, НО тот факт, что его поддержка находится в [0,1]. Может быть, вы смотрели на алгоритм 1?
Гость
Да, круто, довольно интересный трюк для преобразования реальных значений в сэмплы Бернулли, спасибо за указание, что детали ускользнули от меня. В любом случае, как вы говорите, вам все еще нужны ограниченные переменные, вы можете сделать это с помощью дешевого двойного трюка, который я упомянул, и использовать эту версию выборки Томпсона. Но вам может быть лучше сформулировать метод, который использует гауссовский апостериор.
fairidox
Я более подробно остановлюсь на гауссовском апостериорном методе, но что вы подразумеваете под «плоским» в терминах гауссовского? Я бы предположил, что будет соответствовать что-то вроде бета (1,1) (униформа) до, правильно?
Гость
верно, но вы не можете иметь единый априор в неограниченной области. Итак, если у вас есть задняя гауссовская модель, скорее всего, у вас будет предшествующий гауссовский тип, поэтому вы обычно хотите, чтобы она была «плоской» или неинформативной, насколько это возможно. Как правило, это означает, что дисперсия настолько велика, насколько вы можете выдержать. Я не эксперт, но есть целая область исследований о том, как создавать неинформативные и потенциально неподходящие априоры, на которые вы, возможно, захотите взглянуть. Кроме того, если у вас есть строго положительные вознаграждения, вы можете рассмотреть другую модель.
fairidox