Resumen:Este artículo investiga la complejidad computacional del aprendizaje por refuerzo en un nuevo régimen de aproximación de funciones lineales, denominado realizabilidad parcial $q^{pi}$. En este marco, el objetivo es aprender una política $epsilon$-óptima con respecto a un conjunto de políticas predefinido $Pi$, bajo el supuesto de que todas las funciones de valor para las políticas en $Pi$ son linealmente realizables. Los supuestos de este marco son más débiles que los de $q^{pi}$-realizabilidad, pero más fuertes que los de $q^*$-realizabilidad, lo que proporciona un modelo práctico donde la aproximación de funciones surge naturalmente. Demostramos que aprender una política $epsilon$-óptima en este entorno es computacionalmente difícil. Específicamente, establecemos la dureza NP bajo un conjunto de políticas codiciosas parametrizadas (argmax) y mostramos que, a menos que NP = RP, se cumple un límite inferior exponencial (en la dimensión del vector de características) cuando el conjunto de políticas contiene políticas softmax, bajo la Hipótesis del tiempo exponencial aleatorio. Nuestros resultados de dureza reflejan aquellos en $q^*$-realizabilidad y sugieren que la dificultad computacional persiste incluso cuando $Pi$ se expande más allá de la política óptima. Para establecer esto, reducimos de dos problemas de complejidad, $delta$-Max-3SAT y $delta$-Max-3SAT(b), a instancias de GLinear-$kappa$-RL (política codiciosa) y SLinear-$kappa$-RL (política softmax). Nuestros hallazgos indican que los resultados computacionales positivos son generalmente inalcanzables en la realizabilidad $q^{pi}$ parcial, en contraste con la realizabilidad $q^{pi}$ bajo un modelo de acceso generativo.
Publicado originalmente en export.arxiv.org el 27 de octubre de 2025.
Ver fuente original
