Learning Kernel-Based MDPs from Episodic Preferential Feedback

Resumen Técnico: Aprendizaje de MDPs Basados en Núcleos a partir de Retroalimentación Preferencial Episódica

Formulación del Problema
Este trabajo aborda el problema del Aprendizaje por Refuerzo a partir de Retroalimentación Humana (RLHF) en el contexto de Procesos de Decisión de Markov (MDP) episódicos. A diferencia del RL estándar, donde los agentes reciben recompensas escalares, aquí el aprendiz recibe únicamente retroalimentación preferencial binaria. En cada episodio $k$, el aprendiz despliega dos políticas, $\pi$ y $\pi'$, desde un estado inicial común para generar dos trayectorias, $\tau_k$ y $\tau'_k$. La retroalimentación consiste en una única etiqueta binaria $y_k \in \{0, 1\}$ que indica qué trayectoria es preferida. Esta preferencia se modela mediante una función de enlace Bradley–Terry–Luce (BTL) aplicada a la diferencia de recompensas acumuladas (no observadas):
$$y_k \sim \text{Ber}\left(\sigma\left(\sum_{h=1}^H r_h(z^k_h) - \sum_{h=1}^H r_h(z'^k_h)\right)\right)$$
donde $\sigma$ es la función sigmoide. El objetivo es aprender una política que maximice la función de valor $V^\pi_1$ mientras minimiza el arrepentimiento acumulado, definido como la diferencia entre el valor óptimo y el valor promedio de las políticas desplegadas.

El escenario asume una estructura de MDP basado en Núcleos, donde la función de recompensa $r_h$ y el operador de transición $P_h$ son elementos de un Espacio de Hilbert de Funciones de Núcleo Reproductivo (RKHS) $\mathcal{H}_k$ inducido por un núcleo conocido $k$. Específicamente, los autores se centran en la familia de núcleos Matérn, que captura estructuras no lineales y es equivalente en norma a los espacios de Sobolev, ofreciendo una generalización más allá de los MDPs lineales.

Metodología: Algoritmo PROSTO
Los autores proponen PROSTO (Optimización Regularizada Basada en Preferencias mediante Trayectorias Muestreadas inducidas por Optimismo). El algoritmo opera en episodios y utiliza un enfoque de iteración de valores adaptado para la retroalimentación preferencial y la aproximación de funciones de núcleo.

1. Estimación de Recompensas mediante Regresión Logística de Núcleo Regularizada (KLRR):
   Dado que la retroalimentación es a nivel de trayectoria y binaria, el vector de recompensas $\theta$ se estima mediante máxima verosimilitud con una penalización ponderada por norma. El estimador $\hat{\theta}_k$ minimiza el log-verosimilitud negativo de las preferencias observadas más un término de regularización $\tau \|\theta\|^2_{\mathcal{H}_k}$. Las covariables para esta regresión son las características de diferencia de trayectoria $\phi_i = \sum_{h=1}^H \phi(z^i_h) - \phi(z'^i_h)$.

2. Exploración mediante Perturbación Aleatoria de GP:
   Para garantizar una exploración suficiente a nivel de trayectoria sin conocer de antemano la dinámica de transición (lo que impide bonificaciones elípticas deterministas), PROSTO emplea exploración aleatoria. Un vector de ruido de exploración $\epsilon_k$ se muestrea de un Proceso Gaussiano (GP) con una estructura de covarianza dependiente de la covarianza empírica de las diferencias de trayectoria. Este ruido se añade a la estimación de recompensa para inducir optimismo.

3. Estimación de la Función de Valor mediante Regresión de Cresta de Núcleo (KRR):
   La función de valor se estima de forma recursiva. El valor esperado del siguiente estado se aproxima utilizando la regresión de crestas de núcleo estándar sobre muestras de transición. La estimación final de la función Q, $\hat{Q}^k_h$, combina la estimación de recompensa (KLRR + ruido GP) y la estimación de transición (KRR), sujeta a recorte para garantizar acotación.

4. Ejecución de la Política:
   El aprendiz selecciona dos políticas, $\pi$ y $\pi'$, que son codiciosas con respecto a sus respectivas estimaciones de funciones Q optimistas. Estas políticas se ejecutan para generar las trayectorias y la retroalimentación preferencial del siguiente episodio.

Contribuciones Técnicas Clave y Desafíos
El artículo identifica tres desafíos técnicos principales específicos de la combinación de MDPs basados en núcleos con retroalimentación preferencial a nivel de trayectoria y proporciona soluciones novedosas:

• Control de Números de Cubrimiento Logarítmicos: En los MDPs basados en núcleos, el número de cubrimiento logarítmico de la clase de funciones de valor escala polinomialmente con el inverso de la malla de cubrimiento $\epsilon$ y depende de las normas RKHS de los estimadores. A diferencia de los MDPs lineales, donde los números de cubrimiento son logarítmicos en el número de episodios, los entornos de núcleo pueden conducir a límites de arrepentimiento vacuos si las normas de los estimadores crecen demasiado.

  • Solución: Los autores ajustan cuidadosamente el parámetro de regularización $\tau$ en la KLRR para controlar explícitamente la norma RKHS del estimador de recompensa. Esto mantiene pequeño el número de cubrimiento de la clase de funciones inducida, permitiendo límites de confianza significativos.

• Exploración a Nivel de Trayectoria con Ruido No Suave: Las bonificaciones de exploración estándar (bonificaciones elípticas) requieren conocimiento de la trayectoria completa, lo cual no está disponible en el momento de la decisión. Se utiliza exploración aleatoria mediante muestreo GP, pero las trayectorias de muestra GP de un núcleo Matérn generalmente no pertenecen al RKHS correspondiente (son menos suaves). Esto hace inaplicables los límites de cubrimiento estándar.

  • Solución: Los autores derivan nuevos límites de cubrimiento gaussiano de alta probabilidad para las trayectorias de muestra del GP posterior. Aprovechan resultados de van der Vaart y van Zanten [2008] para mostrar que, aunque las trayectorias GP se encuentran fuera de la bola RKHS, se encuentran dentro de una vecindad $\epsilon$ (en norma $\ell_\infty$) de una bola RKHS adecuadamente ampliada con alta probabilidad. Esto permite la derivación de límites de cubrimiento necesarios para el análisis de arrepentimiento.

• Equilibrio entre Parámetros de Regularización y de Cubrimiento: Ajustar los parámetros de regularización ($\tau$ para recompensa, $\lambda$ para transición) y la malla de cubrimiento $\epsilon$ no es trivial. Un $\epsilon$ pequeño reduce el error de especificación incorrecta pero infla el número de cubrimiento; un $\epsilon$ grande hace lo contrario.

  • Solución: Los autores optimizan conjuntamente $\tau$, $\lambda$ y $\epsilon$ como funciones del número de episodios $K$ y del parámetro de suavidad del núcleo $\beta_p$. Este equilibrio asegura que las anchuras de confianza permanezcan lo suficientemente ajustadas para un arrepentimiento sublineal, al tiempo que se controla la complejidad de la clase de funciones.

Resultados y Límites de Arrepentimiento
El artículo demuestra que PROSTO logra un límite de arrepentimiento acumulado sublineal para todos los núcleos de la familia Matérn. Específicamente, el arrepentimiento $R(K)$ escala como:
$$R(K) \leq \tilde{O}\left( \kappa_Z \max\left( H^{2.5} K^{1 - \frac{(\beta_p-1)^2}{2\beta_p(\beta_p+1)}}, H^3 K^{1 - \frac{\beta_p-1}{2(\beta_p+1)}} \right) \right)$$
donde $\beta_p > 1$ es el parámetro de decaimiento de autovalores del núcleo, $H$ es el horizonte y $\kappa_Z$ es el gradiente inverso máximo del enlace. El exponente de $K$ es estrictamente menor que 1, lo que implica convergencia a la política óptima cuando $K \to \infty$.

Además, el algoritmo es computacionalmente eficiente, con un tiempo de ejecución polinomial en el número de episodios $K$. Esto lo distingue de trabajos anteriores sobre MDPs basados en núcleos con recompensas estándar (por ejemplo, Maran et al. [2024b]), que, aunque logran arrepentimiento sublineal, dependen de particiones de dominio u oráculos de optimización que no se sabe que sean tratables computacionalmente en tiempo polinomial para configuraciones de núcleo generales.

Significado y Afirmaciones
Los autores afirman que este trabajo proporciona el primer algoritmo para RL basado en preferencias en MDPs basados en núcleos que logra un arrepentimiento sublineal demostrable para toda la familia de núcleos Matérn siendo computacionalmente eficiente.

• Novedad Teórica: El trabajo cierra la brecha entre el RL basado en preferencias (que típicamente maneja configuraciones tabulares o lineales) y la aproximación de funciones basada en núcleos (que maneja configuraciones no lineales). Introduce nuevas técnicas para manejar la falta de suavidad en el ruido de exploración GP dentro del contexto de la iteración de valores.
• Eficiencia Computacional: A diferencia de algoritmos anteriores sin arrepentimiento para MDPs suaves que pueden requerir optimización intratable, PROSTO ofrece una implementación en tiempo polinomial.
• Limitaciones: Los autores reconocen que el límite de arrepentimiento puede no ser óptimo en orden. Señalan que los enfoques de partición de dominio, que actualmente ofrecen límites óptimos en orden en algunas configuraciones de núcleo, son incompatibles con la retroalimentación a nivel de trayectoria debido a la estocasticidad de las transiciones que impide la estimación localizada del operador de Bellman.

El artículo concluye que, aunque el límite de arrepentimiento derivado es sublineal, lograr un límite óptimo en orden sigue siendo una pregunta abierta, que probablemente requiera técnicas fundamentalmente diferentes más allá de las actuales particiones de dominio o métodos de cubrimiento uniforme.