Bandidos no paramétricos por lotes a través de k-Vecinos más Cercanos UCB

Estudiamos la toma de decisiones secuencial en bandidos contextuales no paramétricos por lotes, donde las acciones se seleccionan sobre un horizonte finito dividido en un pequeño número de lotes. Motivados por restricciones en dominios como la medicina y el marketing -- donde la retroalimentación en línea es limitada -- proponemos un algoritmo no paramétrico que combina la regresión adaptativa de k-vecinos más cercanos (k-NN) con el principio de límite superior de confianza (UCB). Nuestro método, BaNk-UCB, es completamente no paramétrico, se adapta a la dimensión del contexto y es simple de implementar. A diferencia de trabajos anteriores que dependen de estimadores paramétricos o basados en agrupamientos, BaNk-UCB utiliza la geometría local para estimar recompensas y equilibra de manera adaptativa la exploración y la explotación. Proporcionamos garantías de remordimiento casi óptimas bajo suposiciones estándar de suavidad de Lipschitz y márgenes, utilizando un calendario de lotes motivado teóricamente que equilibra el remordimiento entre lotes y logra tasas minimax óptimas. Evaluaciones empíricas en conjuntos de datos sintéticos y del mundo real demuestran que BaNk-UCB supera consistentemente las líneas base basadas en agrupamiento.