Неявно нормализованный прогнозист с клиппированием для линейных и нелинейных многоруких бандитов с тяжёлыми хвостами

Алгоритм Implicitly Normalized Forecaster (INF) считается оптимальным решением для состязательных задач многоруких бандитов (MAB). Однако большинство существующих результатов о сложности INF опираются на ограничительные предположения, такие как ограниченность наград. Недавно был предложен родственный алгоритм, работающий как в состязательной, так и в стохастической постановке MAB с тяжёлыми хвостами. Однако этот алгоритм не использует доступные данные в полной мере. В этой работе мы предлагаем новую версию INF — Implicitly Normalized Forecaster with clipping (INF-clip) — для задач MAB с распределениями награды с тяжёлыми хвостами. Мы устанавливаем результаты сходимости при мягких предположениях о распределении награды и демонстрируем, что INF-clip оптимален для линейных стохастических задач MAB с тяжёлыми хвостами и хорошо работает для нелинейных. Кроме того, мы показываем, что INF-clip превосходит алгоритм best-of-both-worlds в случаях, когда различные «руки» трудно различить.