Что такое Thompson sampling и UCB?

Thompson Sampling и UCB (Upper Confidence Bound) — это алгоритмы для решения задачи многорукого бандита, часто применяемые в онлайн-экспериментах и A/B тестах для балансировки между исследованием (exploration) и использованием (exploitation).

• Thompson Sampling — вероятностный метод, который выбирает действие, основываясь на случайной выборке из апостериорного распределения вознаграждений для каждого варианта. Таким образом, он естественно балансирует между изучением новых вариантов и использованием уже успешных.

• UCB — метод, который выбирает вариант с максимальной верхней доверительной границей оценки вознаграждения. Он учитывает среднее вознаграждение и неопределённость (вариативность), отдавая предпочтение вариантам с высокой потенциальной выгодой и/или недостаточно изученным.

Оба алгоритма помогают эффективно находить оптимальные варианты в условиях неопределённости, минимизируя потери от выбора неоптимальных действий.