В данном исследовании рассматривается онлайн-обучение с множествами действий, структурированными по сходству и закодированными корневыми деревьями, показывая, что стандартная одноточечная обратная связь не может использовать эти сходства. Авторы предлагают унифицированные алгоритмы для более богатых моделей обратной связи, которые заменяют количество действий на эффективное число с учётом сходства для улучшения границ регрета.
- Действия кодируются корневым деревом, где уровни количественно определяют близость отношений, а потери совместимы с деревом.
- Доказано, что стандартная одноточечная бандитная обратная связь не способна использовать сходство диапазона или индуцированное деревом при строгих ограничениях.
- Алгоритмы адаптируются к моделям обратной связи, от полубандитных до минимальных двухточечных протоколов.
- Границы регрета заменяют количество действий K на эффективное число действий с учётом сходства, K_eff.
- Подход достигает регрета sqrt(T) в липшицевых бандитах с размерностью d <= 2 при двухточечной обратной связи.
Эти алгоритмы доказуемо используют сходства действий, адаптируясь к различным моделям обратной связи, обеспечивая гарантии «лучшего из обоих миров» и улучшенную производительность в конкретных высокомерных настройках.