UCB при большом action space
Почему UCB может быть плохой идеей при 1000 actions и горизонте 2000 или 20 шагов? Что делать вместо этого?
Короткий ответ
Tabular UCB плохо масштабируется: нужно много pulls на каждую руку. При большом числе actions нужны priors, contextual sharing, embeddings, Thompson sampling или ограничение candidate set.
Полный разбор
UCB добавляет optimistic bonus для малоисследованных действий. При 1000 arms и horizon 2000 на каждую руку приходится очень мало наблюдений, поэтому оценки шумные, а exploration budget огромный. При horizon 20 tabular exploration почти бессмысленен: все руки попробовать невозможно.
Нужны способы переносить информацию между действиями: contextual bandits, embeddings действий, model-based priors, clustering arms, candidate generation, Thompson sampling с информативным prior, offline pretraining или simulator. Если actions имеют структуру, ее нужно использовать; если структуры нет, задача статистически плохо определена.
В production также можно ограничить exploration безопасными top-k кандидатами и использовать conservative rollout.
Теория
Sample efficiency в bandits зависит от того, можем ли мы обобщать между actions. Без структуры large action space быстро становится неразрешимым.
Типичные ошибки
- Говорить "просто используем UCB" без оценки horizon/action count.
- Не отличать 2000 и 20 шагов.
- Не предложить contextual/generalization подход.
Как отвечать на собеседовании
- Сразу посчитай budget per arm.
- Скажи, что нужна структура действий или prior.