Вариация на тему multi-armed bandits

luherstag

Есть два игровых автомата. Игры на любом из автоматов выдают независимые одинаково распределённые действительные числа. У каждого автомата своё распределение. Распределения неизвестны, но если очень хочется, можно предположить какие-нибудь удобные свойства.
Игроку предстоит сыграть 100 игр в общей сложности. После этого на основе своих наблюдений для каждого автомата он должен выбрать знак. Его выигрыш - сумма истинных матожиданий этих двух распределений, каждое берётся с соответствующим знаком.
Цель игрока - максимизировать выигрыш. Не уверен что именно это значит (недостаток информации о распределениях не позволяет говорить о матожидании выигрыша, например).
У этой задачи есть название?
Как её принято формализовывать?
Какие есть оптимальные или хотя бы хорошие стратегии?

BSCurt

Игроку предстоит сыграть 100 игр в общей сложности. После этого на основе своих наблюдений для каждого автомата он должен выбрать знак. Его выигрыш - сумма истинных матожиданий этих двух распределений, каждое берётся с соответствующим знаком
В смысле если реальные мат ожидания a1 и a2
а выбраны знаки + + то выигрыш a1+a2
для - + выигрыш -a1+a2?
Так что ли?

luherstag

Да.

griz_a

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

kravecnata

> Игроку предстоит сыграть 100 игр в общей сложности.
Это выглядит как budget-limited (or budget-constrained) bandits – активная тема последние лет пять.
> После этого на основе своих наблюдений для каждого автомата он должен выбрать знак.
Это уже выглядит как некоторый вариант off-policy evaluation for bandits. Тоже есть недавние результаты, но вроде бы там изучают, как выбирать после фиксированного числа случайных дерганий ручки (пишут они так, что я это прочитать не могу).
За пять минут я не придумал тривиального способа эти две задачи скрестить на халяву; возможно, это действительно нетривиально и не изучалось (но я по бандитам не специалист).

luherstag

Можно например добавить что значения принадлежат известному интервалу. Если поможет, можно сказать что функция плотности непрерывная или даже липшиц-непрерывная.
Или вообще как альтернатива я не чужд баесовскому подходу, пусть распределения даже всегда нормальные, с параметрами которые независимым образом берутся из каких-нибудь удобных priors, и максимизировать надо именно матожидание выигрыша. Тогда существование оптимальной стратегии вроде как очевидно, но всё равно совершенно непонятно как её аппроксимировать.

griz_a

Я так понимаю, вся задача в том, чтобы распределить, какую выборку брать на каждом шаге?
При фиксированных выборках задача распадается на две одинаковых - максимизировать прибыль у одного автомата тем же образом. А это, видимо, как-то брать знак на основе знаков среднего или медианы, смотря насколько у меня робастно себя ведут распределения.
В качестве первой итерации можно взять что-нибудь такое.
Беру условно по 20 элементов из каждой выборки.
Считаю [math]$\overline{X}$, $S^2$[/math].
Беру в качестве меры достоверности определения знака число [math]$|\sqrt{n}\overline{X}|/S$[/math] - на сколько стандартных отклонений я должен промазать от матожидания, если [math]$\overline{X}$[/math] не того знака, что [math]$EX$[/math].
Следующий элемент беру в ту выборку, у которой это число меньше (она менее достоверна). И так далее.
Эта стратегия уязвима против
а) распределений с тяжелыми хвостами, где выборочная дисперсия ведет себя фу как
б) случаев, когда у одной выборки среднее близко к 0, а у второй большое. Тогда мне лучше бы все ресурсы на второй кинуть, потому что первое все равно малый вклад дает.
Под пункт б) можно чего-нибудь поменять навроде наблюдения не только за достоверностью, но и за выборочным средним. Т.е. чем больше модуль выборочного среднего, тем больше достоверности я жажду.
Конкретные соотношения опять же зависят от того, как себя распределения ведут.

luherstag

На (а) для удобства забиваем, а вот (б) действительно важный аспект исходной задачи, как комбинировать достоверность с важностью.
Наиболее теоретически обоснованным и наименее магическим мне представляется способ, который назначает денежное значение информации, получаемой из очередной игры. Типа, разница между матожиданием выигрыша если мы прекращаем играть и принимаем решение о знаках сейчас и матожиданием выигрыша если мы играем ещё одну партию на данном автомате (по крайней мере о таком можно говорить в баесовской модели).
Но остаётся ещё один вопрос: какие есть основания полагать что жадный алгоритм не поведёт себя ужасно? Не может ли получиться, что основной эффект очередного эксперимента не в том, что он может заставить нас сразу поменять мнение о знаке, а в том что он делает проще (или сложнее) поменять мнение о знаке в будущем?

griz_a

Если байесовский подход, то у меня есть плотности, матожидания, априорные и апостериорные плотности [math]$f^{(i)}_{\theta}(x \mu^{(i)} (\theta \pi^{(i)} (\theta \pi^{(i)}(\theta|x_1,..,x_n)$[/math], [math]$i=1,2$[/math]. [math]$f^{(i)}(x) = \int f^{(i)}_{\theta}(x) \pi(\theta)d\theta$[/math].
 [math]$\Theta^{(i)}_+, \Theta^{(i)}_-$[/math] - множества, где матожидания имеют соответствующий знак, [math]$\mu^{(i)}_{+},\mu^{(i)}_{-}$[/math] - интегралы от [math]$\mu^{(i)}(\theta)$[/math] по этим множествам, [math]$\mu^{(i)} = \mu_+^{(i)} + \mu_-^{(i)}$[/math]
1) Найдем байесовскую оценку для одного автомата. Получается, что наш выбор определяется критическим множеством D, при попадании в которое мы выберем знак плюс. Байесовский риск при этом
[math]$$\int_{\Theta^+} \mu(\theta) \pi(\theta) P_{\theta}X_1,..,X_n)\not \in D) d\theta + \int_{\Theta^-} (-\mu(\theta \pi(\theta) P_{\theta}X_1,..,X_n) \in D) d\theta = \mu_+ - \int_{\Theta} \mu(\theta) \pi(\theta)  P_{\theta}X_1,...,X_n)\in D) d\theta.$$[/math]
Первое константа [math]$\mu^+$[/math], второе надо минимизировать. Но это легко, так как
[math]$$\int_{\Theta} \mu(\theta) \pi(\theta)  P_{\theta}X_1,...,X_n)\in D) d\theta = \int_{\mathbb{R}^n} I_{(x_1,..,x_n)\in D} \int_{\Theta} L(x_1,...,x_n;\theta) \mu(\theta) \pi(\theta) d\theta dx_1...dx_n,$$[/math]
а тогда понятно, что надо брать
[math]$$D = \left\{x_1,...,x_n: = \int_{\Theta} L(x_1,...,x_n;\theta) \mu(\theta) \pi(\theta) d\theta > 0\right\}$$[/math]
То же множество переписывается в виде [math]$$D = \left\{x_1,...,x_n: I(\vec{x}) = \int_{\Theta} \pi(\theta|x_1,...,x_n) \mu(\theta) d\theta> 0\right\} $$[/math]
Собственно, логично - надо брать знак апостериорного среднего
Хорошая задачка для темы "Байесовские оценки" получилась. Возьму :)
2) Если известны [math]$x_1,...,x_n$[/math] то мы можем подсчитать нашу априорную потерю:
[math]$\mu^+ - (I(\vec{x}^+. $[/math]
Тогда мы можем подсчитать ожидаемую потерю, если мы уже знаем [math]$k$[/math] элементов и берем наугад [math]$k+1$[/math]-й. Там есть невосполнимые потери [math]$\mu^+ $[/math] и возможная флюктуация
[math]$   H(x_1,...,x_n) = \int_{\Theta} P_{\theta} x_1,...,x_k, X_{k+1})\in D)\mu(\theta) \pi(\theta|x_1,...,x_k) d\theta = \int_{x_{k+1}: I(\vec{x})>0} \int_{\Theta} \mu(\theta) f_{\theta}(x_{k+1}) \pi(\theta|x_1,...,x_k) d\theta dx_{k+1} = \int_{\mathbb{R}}  f(x_{k+1}) I(x_1,...,x_{k+1})^+ dx_{k+1}  $  [/math]
Соответственно, засчет узнавания [math]$x_{k+1}$[/math] наш риск меняется на
[math]$ G(x_1,...,x_k)  = \int_{\mathbb{R}}  f(x_{k+1}) (I(x_1,...,x_{k+1})^+ - I(x_1,...,x_k)^+) dx_{k+1}$[/math]
3) Жадный алгоритм предлагает, зная [math]$x_1,..,x_k$[/math] из первого автомата и [math]$y_1,...,y_l $[/math] из второй, нам на следующем шаге сравнивать
[math]$$G^{(1)}(x_1,...,x_k) $$[/math] и [math]$$G^{(2)}(y_1,...,y_l)$$[/math]. Кто больше, того и берем.
4) Нежадный алгоритм строить сложно
P.S. [math]$I^+ $[/math] - это положительная часть, [math]$\max(I,0)$[/math]

natunchik

> Но остаётся ещё один вопрос: какие есть основания полагать что жадный алгоритм не поведёт себя ужасно?
А у тебя есть другие варианты кроме жадного алгоритма который тупо ставит на то, что максимизировало бы его прибыль на имеющихся данных?
Типа, да, у тебя есть выбор: взвешенный выбор между жадным алгоритмом и твоим вытащенным из попы prior distribution as of a fair coin or something. Ну, насколько ты доверяешь своему приору, настолько подвигай ставку. Если понимаешь что у тебя ноль причин доверять ему, то иди 100% на жадный алгоритм, чё, лучше-то ничего нет после того как ты приор выкинул. Поппер про это всё буквально сто лет назад сказал, чтож ты пытаешься левой философией поправить математику?

luherstag

Спасибо, я глянул мельком off-policy evaluation, действительно вроде похоже, но там они фокусируются на Markov decision processes, а у меня топорные decision processes.

luherstag

Забавно, мне с самого начала казалось очевидным что надо брать знак апостериорного среднего, но формальные выкладки я бы не осилил сам провести, и когда я смотрю на них некоторые шаги интуитивных аналогов в моих прикидках не имеют. Так что наверное случайно угадал.
Кстати, с одной стороны надо признать что я давно отвык читать формулы, и сейчас их распаршиваю буквально по слогам. С другой стороны - трэш же какой-то, джава вперемешку с перлом! Может вам не хватает эйнштейна, чтобы придумал вменяемую нотацию? Или может уже есть какие-нибудь высокоуровневые формы записи?

griz_a

Во-первых, можно открыть какой-нибудь онлайн тех и сунуть туда, например, overleaf.com
Во-вторых, можно поставить скрипт math: /user/upload/js/23985.js

luherstag

Я ничего не понял.
Жадный vs дальновидный же ортогонально вопросу насколько сильный приор использовать и откуда его вытаскивать.
Но при этом как ты себе представляешь жадный вообще без приора?
Ну ок, в качестве знака допустим берём знак выборочного среднего, хотя я не уверен что этот выбор получится обосновать если вообще ничего не известно о распределениях. Разве что симметрией отбрехаться может быть.
А как выбирать какой из автоматов тестировать на каждом шаге?
И в целом я не думаю что можно вообще без приора. Можно с анынформатив приором. Или можно с анынформатив приором и кучей удобных в вычислительном плане аппроксимаций типа метода максимального правдоподобия, получится классическая статистика.
Либо можно сказать что неопределённость в данном случае надо моделировать не случайностью, а противником, и оптимизировать худший случай. Но в первом ответе показывает что это не особо плодотворный подход в данном случае.

luherstag

Я не про то как набирать формулы, а про сами формулы. Я согласен что способность посмотреть на ассемблерный листинг матан и понять что там происходит важна, но это не значит что все выкладки оправданно вести на этом уровне. Пока что лингвистические достижения теорвера это стандартизация букв, вертикальная палочка и полуформальные соглашения по омиссии некоторых переменных. Интегралы торчат наружу. В моих мечтах не должны.

griz_a

Я мог бы писать E с разными индексами вместо интегралов, но так нагляднее, на мой взгляд.
Типа
[math]$$E_{\pi} \left(E_{\theta} I_{\vec{X}\in D} (E_{\theta} X_1)^+\right) ,$$[/math]
которое потом расшифровывать придется хз сколько времени
Оставить комментарий
Имя или ник:
Комментарий: