Один автомат виграє в 60% спроб, другий у 50%, але який із них кращий, невідомо. План простий: смикнути кожен по 10 разів, а решту з сотні спроб грати на тому, що виграв більше. Як часто такий план застрягне на гіршому автоматі? Зафіксуйте відповідь, а потім перевірте її в грі, на симуляції і в поясненнях.
Десять спроб замало, щоб відрізнити 60% від 50%: кращий автомат часто програє тест або ділить нічию. Тест 10 + 10 обирає гірший автомат у 32,8% випадків, і ця помилка вже не виправляється. Як грати краще, показують гра, симуляція і пояснення нижче.
Ігровий автомат з ручкою збоку англійською звуть «одноруким бандитом». Коли автоматів кілька, а кращий треба знайти під час гри, виходить «багаторукий бандит», одна з головних задач теорії рішень.
Один автомат виграє в 60% спроб, другий у 50%. Кожна спроба незалежна, як кидок монети. Котрий із них кращий, вам не кажуть.
Ви смикаєте кожен автомат по 10 разів і рахуєте виграші.
Решту 80 спроб із сотні ви віддаєте автомату, який виграв більше. Якщо нічия, обираєте кидком монети.
Як часто цей план віддасть 80 спроб гіршому автомату?
«Різниця 10 пунктів чимала. За 10 спроб кращий майже завжди вирветься вперед»
Насправді кращий автомат виграє тест лише в 59% випадків, у 16% буде нічия, а в 25% попереду опиниться гірший. Разом із половиною нічиїх план обирає гірший автомат у 32,8% випадків.
По 10 спроб на кожен автомат, далі граємо на лідері, нічию розв'язує монета. У якій частці таких тестів лідером виявиться автомат на 50%?
Оберіть відповідь. Тут з'явиться точний розрахунок і симуляція 20 000 тестів.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
Скільки виграшів з 10 ви чекаєте від автомата на 60%, а скільки від автомата на 50%? Наскільки велика ця різниця?
Рахунок за 10 спроб легко відхиляється від очікуваного на 1–2 виграші в будь-який бік. Що буде, якщо кращий автомат відхилиться вниз, а гірший угору?
Порахуйте три випадки: кращий попереду, гірший попереду і нічия, яку монета ділить навпіл. Нічиїх тут чимало, а половина з них дістається гіршому.
Один автомат виграє в 60% спроб, другий у 50%. Комп'ютер навмання вирішив, котрий де. Смикайте будь-який, скільки хочете: розвідуйте, коли сумніваєтеся, і грайте на лідері, коли впевнені. Після сотої спроби автомати відкриються.
| Виграшів зі 100 |
|---|
Графік показує, скільки виграшів у середньому втрачає кожна стратегія порівняно з тим, хто від початку знає кращий автомат і смикає лише його. Лінії пораховано точно, точки беруться із симуляції. Повзунком змініть довжину розвідки в плані «N + N».
Кожна спроба робить дві справи одразу: приносить виграш і дає знання про автомат. Що більше розвідуєш, то менше заробляєш зараз. Що менше розвідуєш, то частіше заробляєш не там.
Шар «На пальцях» приховано на всіх задачах.
Від автомата на 60% чекаєш 6 виграшів з 10, від автомата на 50% чекаєш 5. Але випадок легко зсуває кожен рахунок на 1–2 виграші в будь-який бік. Різниця в один виграш тоне в цьому шумі, тому тест так часто помиляється. Ця картка пояснює лише, чому помиляється тест; що з цим робити, розповідають наступні.
Після тесту план більше не дивиться на гірший автомат. Якщо обрали не той, усі 80 спроб ідуть туди, де виграш на 10 пунктів менший: це 8 втрачених виграшів. Так стається в третині ігор, і саме тут план втрачає найбільше.
Жадібна стратегія, яка грає на лідері з першої ж спроби, гірша: один невдалий початок кращого автомата, і вона може більше до нього не повернутися.
Можна смикати обидва автомати навпіл усі 100 разів і ніколи не помилитися з вибором, бо вибору немає. Тоді 50 спроб гарантовано йдуть гіршому автомату: це 5 втрачених виграшів, більше, ніж у плану 10 + 10.
Найкраща довжина тесту для 100 спроб лежить посередині: 16 + 16. Але й вона втрачає 3,5 виграшу, і щоб її знайти, треба заздалегідь знати, що автомати відрізняються саме на 10 пунктів.
Семплювання Томпсона не ділить гру на тест і заробіток. Перед кожною спробою воно оцінює, наскільки ймовірно, що кращий саме лівий автомат, і смикає його з такою ймовірністю. Поки даних мало, автомати отримують спроби майже порівну. Коли лідер упевнено відривається, гірший отримує дедалі менше, але ніколи не нуль.
Помилку на старті воно виправляє: якщо гірший автомат випадково вирвався вперед, кращий час від часу ще отримує спроби і повертає лідерство. Тому гірший автомат отримує понад половину спроб лише у 22% ігор, а не в 33%.
Шар «Строго» приховано на всіх задачах.
Шанс отримати рівно k виграшів з 10. Стовпчики двох автоматів майже повністю накладаються: найчастіший результат кращого автомата (6 виграшів) трапляється в 25% тестів, а гіршого (5 виграшів) у 25%. Щоб тест помилився, досить, щоб кожен автомат відхилився на один виграш назустріч іншому.
| N | Гірший попереду | Нічия | Обрано гірший | Втрати |
|---|
«Обрано гірший» дорівнює частці «гірший попереду» плюс половина нічиїх. Втрати зі 100 спроб рахують так: кожна спроба гіршого автомата коштує 0,1 виграшу, а він отримує N спроб у розвідці і ще 100 − 2N, якщо його обрали. Довша розвідка рідше помиляється, але дорожче коштує сама. Мінімум втрат при N = 16.
Шанс k виграшів з n спроб автомата з імовірністю p.
Шанс обрати гірший автомат: гірший попереду плюс половина нічиїх. Кращий має рахунок i, гірший j.
Втрати плану N + N за T спроб при різниці Δ = 0,1 між автоматами.
Правило Томпсона: після w виграшів і l програшів незнайома ймовірність автомата описується розподілом Beta(w + 1, l + 1). Беремо з кожного по випадковому числу і смикаємо автомат з більшим. Так кожен автомат отримує спробу з тією ймовірністю, з якою він кращий.
Шар «Глибше» приховано на всіх задачах.
Першим задачу поставив Вільям Томпсон 1933 року в журналі Biometrika. Його цікавило, як ділити пацієнтів між двома методами лікування, коли один із них, можливо, кращий, а котрий, ще невідомо. Його відповідь, давати кожен метод з тією ймовірністю, з якою він кращий, сьогодні звуть семплюванням Томпсона.
1952 року Герберт Роббінс у статті «Some aspects of the sequential design of experiments» сформулював задачу строго: як послідовно обирати, що вимірювати далі, щоб у довгій грі середній виграш наближався до найкращого. Звідти пішла сучасна теорія.
Найкраща стратегія мала б урахувати всі можливі майбутні рахунки, а їх кількість росте лавиноподібно. Довгий час вважали, що точного простого рішення немає. 1979 року Джон Гіттінс показав, що для нескінченної гри, де майбутні виграші поступово знецінюються, достатньо порахувати для кожного автомата одне число, індекс Гіттінса, і смикати автомат з найбільшим. Для скінченної гри, як наші 100 спроб, такого простого правила немає.
Точні числа на цій сторінці пораховано перебором усіх можливих рахунків (виграші й програші кожного автомата): для 100 спроб це близько 4,6 мільйона станів.
Що буде, якщо спроб не 100, а 100 000; де ця дилема трапляється в житті; і чому бандит, який заробляє більше за A/B-тест, знає менше.
| Стратегія | 100 | 1 000 | 10 000 |
|---|---|---|---|
| Навпіл 50/50 | 5 | 50 | 500 |
| Жадібна | 3,9 | ≈ 37 | ≈ 370 |
| Найкраща розвідка N + N | 3,5 | 16,2 | 36,1 |
| Семплювання Томпсона | 3,3 | ≈ 12 | ≈ 21 |
Ті самі автомати на 60% і 50%, стовпчики означають кількість спроб. Для 100 спроб числа точні, для 1 000 і 10 000 «найкраща розвідка» точна (N = 99 і N = 276), а решта взята із симуляції від 1 000 до 4 000 ігор.
Жадібна стратегія застрягає на гіршому автоматі приблизно в кожній третій грі, тому її втрати ростуть пропорційно довжині гри: удесятеро більше спроб, удесятеро більші втрати. Найкраща розвідка N + N росте повільніше, але для неї треба заздалегідь знати різницю між автоматами.
Семплювання Томпсона нічого не знає наперед, а втрачає найменше: від 1 000 до 10 000 спроб його втрати зростають приблизно на 9 виграшів, а в жадібної стратегії більш ніж на 300. 1985 року Тзе Леунг Лай і Герберт Роббінс довели, що жодна стратегія не може в довгій грі втрачати менше, ніж пропорційно логарифму числа спроб. Кожне множення гри на 10 додає приблизно однакову порцію втрат. Семплювання Томпсона досягає цієї межі.
Та сама дилема щодня: замовити улюблену страву чи спробувати нову, піти в перевірений ресторан чи в новий, взяти на роботу знайомого чи шукати далі. Кожен вибір і приносить задоволення, і дає знання на майбутнє.
Ключ у тому, скільки гри лишилося. Для 100 спроб найкраща розвідка займає 16 + 16, для 1 000 вже 99 + 99. Хто щойно переїхав у нове місто, тому варто пробувати нове; хто їде звідти за тиждень, тому краще йти в перевірене місце. Схожу логіку має задача про вибір найкращого кандидата: правило 37% теж каже спершу розвідувати, а потім обирати.
І ще одне: жадібна стратегія, яка завжди йде на поточного лідера, застрягає найчастіше. «Мені там раз не сподобалося, більше не піду» — це саме вона.
Ті самі два варіанти на 60% і 50%, 1 000 відвідувачів. A/B-тест ділить їх навпіл: 550 конверсій, а різниця між варіантами відома з точністю ±6,1 пункту (95%). Бандит із семплюванням Томпсона дає в середньому близько 588 конверсій, на 38 більше. Але гірший варіант бачить мало людей: у половині запусків менше ніж 90, а в кожному десятому запуску не більше ніж 23. Тож у типовому запуску різницю відомо лише з точністю близько ±11 пунктів: бандит знає, хто кращий, але погано знає, наскільки.
Питання до сервісу, що продає «оптимізацію штучним інтелектом»: чи покаже він різницю між варіантами з похибкою? Що буде, якщо конверсія змінюється за днями тижня чи через новизну? Чи є мінімальна частка трафіку для кожного варіанта? Детальніше про бандитів у тестах на сторінці «Підглядання в A/B-тест», а про шум у тестах на сторінці «Дві однакові сторінки».
Стаття Вільяма Томпсона в Biometrika (том 25, 1933) мала назву «Про ймовірність того, що одна невідома ймовірність перевищує іншу, з огляду на дві вибірки». Про автомати там немає ні слова: Томпсон думав про вибір між методами лікування.
Герберт Роббінс виклав задачу в статті «Some aspects of the sequential design of experiments» у Bulletin of the American Mathematical Society (том 58, 1952). Вона виросла з доповіді, яку він прочитав у листопаді 1951 року в Оберні, Алабама.
Пітер Віттл в обговоренні статті Гіттінса 1979 року згадав, що над задачею про бандита билися науковці союзників під час Другої світової війни. Вона так їх виснажила, що хтось запропонував скинути її над Німеччиною як найдосконалішу інтелектуальну диверсію.
Джон Гіттінс опублікував «Bandit processes and dynamic allocation indices» у Journal of the Royal Statistical Society, Series B. Він показав, що в нескінченній грі зі знеціненням майбутніх виграшів кожному автомату можна приписати одне число й завжди смикати автомат з найбільшим.
1985 року група Роберта Бартлетта випробовувала ЕКМО, апарат штучного кровообігу для новонароджених, за схемою «грай на переможця»: що краще працює метод, то більше пацієнтів йому дістається. ЕКМО отримали 11 немовлят, і всі вижили; звичайне лікування отримала одна дитина, і вона померла. Через одного пацієнта в контрольній групі результату мало хто повірив, і знадобилися нові дослідження.
Майже 80 років метод Томпсона лишався в тіні. 2011 року Олів'є Шапель і Лігун Лі з Yahoo! Research показали на виборі реклами й рекомендаціях новин, що він на рівних змагається з найкращими сучасними методами. Відтоді його використовують у рекламі, рекомендаціях і тестуванні сайтів.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Рівень «Поглиблено» відповідає задачі?
Дякуємо! Це допоможе точніше ставити рівні.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.