Aprendizaje por refuerzo offline: papel de la agregación de estados y datos de trayectoria

Revisitamos el problema del aprendizaje por refuerzo offline con realizabilidad de la función de valor pero sin completitud de Bellman. Trabajos previos de Xie y Jiang (2021) y Foster et al. (2022) dejaron abierta la pregunta de si un coeficiente de concentrabilidad acotado junto con datos offline basados en trayectorias admite una complejidad de muestra polinómica. En este trabajo, proporcionamos una respuesta negativa a esta pregunta para la tarea de evaluación de políticas offline. Además de abordar esta cuestión, ofrecemos una imagen bastante completa para la evaluación de políticas offline con solo realizabilidad de la función de valor. Nuestros hallazgos principales son tres: 1) La complejidad de la muestra de la evaluación de políticas offline está gobernada por el coeficiente de concentrabilidad en un Modelo de Transición de Markov agregado determinado conjuntamente por la clase de funciones y la distribución de datos offline, en lugar de en el MDP original. Esto unifica y generaliza las ideas de Xie y Jiang (2021) y Foster et al. (2022), 2) El coeficiente de concentrabilidad en el Modelo de Transición de Markov agregado puede crecer exponencialmente con la longitud del horizonte, incluso cuando el coeficiente de concentrabilidad en el MDP original es pequeño y los datos offline son admisibles (es decir, la distribución de datos es igual a la medida de ocupación de alguna política), 3) Bajo la realizabilidad de la función de valor, hay una reducción genérica que puede convertir cualquier instancia difícil con datos admisibles en una instancia difícil con datos de trayectoria, implicando que los datos de trayectoria no ofrecen beneficios adicionales sobre los datos admisibles. Estas tres piezas resuelven conjuntamente el problema abierto, aunque cada una de ellas podría ser de interés independiente.