Este estudio investiga el aprendizaje en línea con conjuntos de acciones estructurados por similitud codificados mediante árboles enraizados, demostrando que la retroalimentación estándar de un solo punto no puede explotar estas similitudes. Los autores proponen algoritmos unificados para modelos de retroalimentación más ricos que reemplazan el número de acciones por un conteo efectivo consciente de la similitud para mejorar los límites de arrepentimiento.
- Las acciones se codifican mediante un árbol enraizado donde los niveles cuantifican la cercanía de la relación y las pérdidas son compatibles con el árbol.
- Se demuestra que la retroalimentación estándar de bandit de un solo punto no puede aprovechar la similitud inducida por el rango o el árbol bajo restricciones fuertes.
- Los algoritmos se adaptan a modelos de retroalimentación que van desde semi-bandit hasta protocolos mínimos de dos puntos.
- Los límites de arrepentimiento reemplazan el conteo de acciones K con un número efectivo de acciones consciente de la similitud, K_eff.
- El enfoque logra un arrepentimiento de sqrt(T) en bandits Lipschitz con dimensión d <= 2 bajo retroalimentación de dos puntos.
Estos algoritmos explotan demostrablemente las similitudes de las acciones adaptándose a varios modelos de retroalimentación, ofreciendo garantías del mejor de ambos mundos y un rendimiento mejorado en configuraciones específicas de alta dimensión.