Identificación Óptima del Mejor Brazo con Múltiples Fidelidades

En la identificación del mejor brazo en el problema del bandido, se le asigna a un algoritmo la tarea de encontrar el brazo con la mayor recompensa media con una precisión especificada lo más rápido posible. Estudiamos la identificación del mejor brazo con múltiples fidelidades, en la cual el algoritmo puede optar por muestrear un brazo a una fidelidad más baja (estimación media menos precisa) por un costo menor. Se han propuesto varios métodos para abordar este problema, pero su optimalidad sigue siendo evasiva, notablemente debido a límites inferiores lazos en el costo total necesario para identificar el mejor brazo. Nuestra primera contribución es un límite inferior ajustado y dependiente de la instancia sobre la complejidad del costo. El estudio del problema de optimización presentado en el límite inferior proporciona nuevas perspectivas para idear algoritmos computacionalmente eficientes, y nos lleva a proponer un enfoque basado en gradientes con complejidad de costo asintóticamente óptima. Demostramos los beneficios del nuevo algoritmo en comparación con métodos existentes en experimentos. Nuestros hallazgos teóricos y empíricos también iluminan un concepto intrigante de fidelidad óptima para cada brazo.