Проблема Уоррена Баффета

Вот абстракция проблемы онлайн обучения / бандита, над которой я работал летом. Я не видел подобной проблемы раньше, и это выглядит довольно интересно. Если вы знаете о любой связанной работе, я был бы признателен за ссылки.

Проблема Параметр для многоруких бандитов. У тебя есть N рук. У каждой руки есть неизвестное, но фиксированное распределение вероятностей по наградам, которые можно заработать, сыграв на ней. Для конкретности предположим, что каждая рука i выплачивает вознаграждение в 10 долларов с вероятностью p [i] и вознаграждение в 0 долларов с вероятностью. 1-р .

В каждом раунде t вы выбираете набор S [t] оружия для игры. За каждую выбранную руку вы платите 1 доллар . За каждую выбранную руку вы получаете вознаграждение, полученное из (неизвестного) распределения вероятности вознаграждения этой руки. Все вознаграждения зачисляются на ваш банковский счет, и все комиссии удерживаются с этого счета. Кроме того, вы получаете кредит в размере 1 $ в начале каждой итерации.

Проблема состоит в том, чтобы разработать политику выбора подмножества оружия для игры на каждой итерации, чтобы максимизировать прибыль (то есть вознаграждение за вычетом сборов за игру) в течение достаточно длительного горизонта, при условии, что он должен поддерживать неотрицательный баланс счета на уровне все время.

Я не уточнил, будут ли распределения вознаграждений за руку выбраны из предыдущего распределения или выбраны противником. Оба варианта имеют смысл. Формулировка противника более привлекательна для меня, но, вероятно, труднее добиться прогресса. Здесь противник выбирает вектор (D1, D2, .., DN) распределений. Учитывая распределение, оптимальная сбалансированная бюджетная политика заключается в том, чтобы разыгрывать все руки, ожидаемое вознаграждение которых превышает 1 доллар. Пусть P - прибыль за шаг этой оптимальной всезнающей политики. Я хочу, чтобы моя политика в Интернете сводила к минимуму сожаление (т. Е. Упущенную выгоду за промежуток времени T) в отношении этой всезнающей политики.

Я предполагаю, что есть много возможных подходов к этой проблеме (многие из которых я уверен, что вы рассмотрели) - вот несколько идей / ссылок.

• $N$
• $O(2^{N/2} T^{1/2})$
• В готовящейся публикации NIPS 2010 года Сатен Кейл, Роб Шапире и я рассмотрим случай, когда каждый раз играет на грифу. В нашей работе, однако, размер листа остается неизменным. В этой статье также рассматривается аналогичная проблема. Еще одна похожая работа появилась в ALT 2010. Возможно, некоторые идеи переносятся.
• $2^N$$O(N\sqrt{T})$$O(2^N T)$

РЕДАКТИРОВАТЬ ниже:

$0$$1$$(n-1)/n$$T$$T$$(n-1)T/n$

$B$$0$$2B$$1/B$