Многорукие бандиты

Онлайн-решения в условиях неопределённости: исследование против эксплуатации, ε-greedy, UCB и когда бандит лучше фиксированного A/B-сплита.

Открыть тему в роадмапе →

6 вопросов

JuniorТеорияЧасто

Почему чисто жадный многорукий бандит может застрять на неверной ручке и как это исправляет ε-greedy?

Жадная стратегия всегда тянет ручку с лучшим средним на текущий момент, поэтому ранняя удача забирает все попытки, а другие ручки больше не измеряются. ε-greedy отдаёт долю ε попыток случайным ручкам, и все оценки уточняются.

Типичные ошибки

✗Считать, что жадная стратегия сойдётся при достаточном числе попыток: ручка, которую перестали тянуть, не получает данных, и неудачная ранняя оценка лучшей ручки не исправится.
✗Принимать ε за скорость обучения: в ε-greedy это вероятность потянуть случайную ручку вместо текущей лучшей.

Уточняющие вопросы

→Зачем уменьшать ε со временем, а не держать его постоянным?
→Чего стоит постоянный ε, когда лучшая ручка уже известна?

JuniorТеорияЧасто

Что выведет эта программа?

0.8

Открыть задачу →

Типичные ошибки

✗Ждать 3.2, сумму вероятностей вытянутых ручек: regret складывает разрывы с лучшей ручкой, 0.8 минус вероятность вытянутой, и три вытягивания ручки 2 ничего не добавляют.
✗Ждать 0.16, средний разрыв: regret складывает потери по всем шагам, 0.5 + 0.3 = 0.8, и растёт, пока стратегия ещё тянет более слабую ручку.

Уточняющие вопросы

→Как растёт regret со временем у фиксированного сплита 50/50 и у стратегии, которая перестаёт тянуть слабые ручки?
→Почему regret можно посчитать в симуляции, но нельзя в живом тесте?

JuniorТеорияЧасто

Что выведет эта программа?

0.67 3

Открыть задачу →

Типичные ошибки

✗Ждать 0.5 3, две награды на все четыре шага: у каждой ручки свой счётчик, ручку 0 тянули 3 раза, поэтому её среднее — 2 / 3, после округления 0.67.
✗Ждать 2.0 3, сумму наград: обновление сдвигает среднее на 1 / count от разрыва с новой наградой, поэтому means[0] остаётся средним, а не суммой.

Уточняющие вопросы

→Зачем бандиту пошаговое среднее по каждой ручке вместо хранения всех наград?
→Что сломается, если увеличивать counts[arm] после обновления среднего, а не до него?

JuniorТеорияЧасто

Что выведет эта программа?

1 0

Открыть задачу →

Типичные ошибки

✗Ждать 0 0, будто бонус не может перебить большее среднее: у ручки 1 всего 2 вытягивания, её бонус около 1.76 против 0.56 у ручки 0, и её оценка выше.
✗Ждать, что бонус наказывает редко вытянутую ручку: его прибавляют к среднему, и он больше там, где вытягиваний меньше; поэтому UCB и идёт исследовать ручку 1.

Уточняющие вопросы

→Какую ручку UCB предпочтёт после многих вытягиваний обеих, и почему?
→Как UCB поступает с ручкой, которую ещё ни разу не тянули?

JuniorТеорияЧасто

Как бандитная стратегия UCB (верхняя доверительная граница) выбирает, какую ручку тянуть дальше?

UCB оценивает ручку как среднюю награду плюс бонус за неопределённость, убывающий с числом попыток, и тянет лучшую. У редко пробованной ручки бонус велик, и её пробуют: оптимизм при неопределённости, без случайности.

Типичные ошибки

✗Думать, что UCB выбирает наибольшее наблюдаемое среднее: он добавляет бонус, большой у редко пробованных ручек, и именно бонус заставляет его исследовать.
✗Думать, что UCB исследует случайно, как ε-greedy: его выбор детерминирован и задаётся уменьшающимся бонусом, а не подбрасыванием монетки.

Уточняющие вопросы

→Почему бонус UCB медленно растёт с общим числом попыток?
→Как поведёт себя UCB с ручкой, которую тянули всего один раз?

JuniorТеорияЧасто

Что вы выигрываете и что теряете, запуская бандит вместо A/B-теста с фиксированным сплитом?

Бандит по ходу теста переводит трафик на лидера, и худший вариант видят меньше пользователей: потерь меньше. Цена — менее чистая оценка эффекта: проигрывающая ручка получает мало данных. Фиксированный сплит даёт несмещённую.

Типичные ошибки

✗Считать бандит ускоренным A/B-тестом с теми же гарантиями: адаптивное распределение морит проигрывающую ручку голодом и смещает её оценку, и p-value уже не как у фиксированного сплита.
✗Выбирать бандит, когда нужен сам размер эффекта: чтобы честно отчитаться о приросте, нужен фиксированный сплит.

Уточняющие вопросы

→В каких продуктовых ситуациях бандит лучше A/B-теста?
→Почему адаптивный сплит смещает оценку проигрывающей ручки?

Ответь сам — Quiz

Все темы

Многорукие бандиты

Открыть тему в роадмапе →

6 вопросов

JuniorТеорияЧасто

Почему чисто жадный многорукий бандит может застрять на неверной ручке и как это исправляет ε-greedy?

Типичные ошибки

✗Считать, что жадная стратегия сойдётся при достаточном числе попыток: ручка, которую перестали тянуть, не получает данных, и неудачная ранняя оценка лучшей ручки не исправится.
✗Принимать ε за скорость обучения: в ε-greedy это вероятность потянуть случайную ручку вместо текущей лучшей.

Уточняющие вопросы

→Зачем уменьшать ε со временем, а не держать его постоянным?
→Чего стоит постоянный ε, когда лучшая ручка уже известна?

JuniorТеорияЧасто

Что выведет эта программа?

0.8

Открыть задачу →

Типичные ошибки

✗Ждать 3.2, сумму вероятностей вытянутых ручек: regret складывает разрывы с лучшей ручкой, 0.8 минус вероятность вытянутой, и три вытягивания ручки 2 ничего не добавляют.
✗Ждать 0.16, средний разрыв: regret складывает потери по всем шагам, 0.5 + 0.3 = 0.8, и растёт, пока стратегия ещё тянет более слабую ручку.

Уточняющие вопросы

→Как растёт regret со временем у фиксированного сплита 50/50 и у стратегии, которая перестаёт тянуть слабые ручки?
→Почему regret можно посчитать в симуляции, но нельзя в живом тесте?

JuniorТеорияЧасто

Что выведет эта программа?

0.67 3

Открыть задачу →

Типичные ошибки

✗Ждать 0.5 3, две награды на все четыре шага: у каждой ручки свой счётчик, ручку 0 тянули 3 раза, поэтому её среднее — 2 / 3, после округления 0.67.
✗Ждать 2.0 3, сумму наград: обновление сдвигает среднее на 1 / count от разрыва с новой наградой, поэтому means[0] остаётся средним, а не суммой.

Уточняющие вопросы

→Зачем бандиту пошаговое среднее по каждой ручке вместо хранения всех наград?
→Что сломается, если увеличивать counts[arm] после обновления среднего, а не до него?

JuniorТеорияЧасто

Что выведет эта программа?

1 0

Открыть задачу →

Типичные ошибки

✗Ждать 0 0, будто бонус не может перебить большее среднее: у ручки 1 всего 2 вытягивания, её бонус около 1.76 против 0.56 у ручки 0, и её оценка выше.
✗Ждать, что бонус наказывает редко вытянутую ручку: его прибавляют к среднему, и он больше там, где вытягиваний меньше; поэтому UCB и идёт исследовать ручку 1.

Уточняющие вопросы

→Какую ручку UCB предпочтёт после многих вытягиваний обеих, и почему?
→Как UCB поступает с ручкой, которую ещё ни разу не тянули?

JuniorТеорияЧасто

Как бандитная стратегия UCB (верхняя доверительная граница) выбирает, какую ручку тянуть дальше?

Типичные ошибки

✗Думать, что UCB выбирает наибольшее наблюдаемое среднее: он добавляет бонус, большой у редко пробованных ручек, и именно бонус заставляет его исследовать.
✗Думать, что UCB исследует случайно, как ε-greedy: его выбор детерминирован и задаётся уменьшающимся бонусом, а не подбрасыванием монетки.

Уточняющие вопросы

→Почему бонус UCB медленно растёт с общим числом попыток?
→Как поведёт себя UCB с ручкой, которую тянули всего один раз?

JuniorТеорияЧасто

Что вы выигрываете и что теряете, запуская бандит вместо A/B-теста с фиксированным сплитом?

Типичные ошибки

✗Считать бандит ускоренным A/B-тестом с теми же гарантиями: адаптивное распределение морит проигрывающую ручку голодом и смещает её оценку, и p-value уже не как у фиксированного сплита.
✗Выбирать бандит, когда нужен сам размер эффекта: чтобы честно отчитаться о приросте, нужен фиксированный сплит.

Уточняющие вопросы

→В каких продуктовых ситуациях бандит лучше A/B-теста?
→Почему адаптивный сплит смещает оценку проигрывающей ручки?

Ответь сам — Quiz