Towards Differentially Private Reinforcement Learning with General Function Approximation

Resumen Técnico: Hacia el Aprendizaje por Refuerzo con Privacidad Diferencial y Aproximación de Funciones General

Enunciado del Problema
Este artículo aborda el desafío de lograr un Aprendizaje por Refuerzo (RL) en línea eficiente en muestras bajo garantías formales de privacidad, cuando el entorno se modela con aproximación de funciones general. Si bien trabajos teóricos previos sobre RL con Privacidad Diferencial (DP) han establecido cotas de arrepentimiento sublineales, estos resultados están en gran medida restringidos a entornos tabulares o configuraciones de aproximación de funciones lineales. Los autores identifican una brecha crítica: extender estas garantías a clases de funciones generales y no lineales (por ejemplo, redes neuronales o clases de hipótesis complejas) sigue siendo un problema abierto. La pregunta central es si el arrepentimiento sublineal es alcanzable para RL privado con aproximación de funciones general bajo Privacidad Diferencial Conjunta (JDP), una relajación de la DP estándar adecuada para RL personalizado donde las acciones individuales de los usuarios deben permanecer privadas mientras se aprende una política global.

Metodología
Los autores proponen un marco de RL sin modelo que integra tres componentes algorítmicos clave para manejar la tensión entre la exploración, la aproximación de funciones general y la privacidad:

1. Objetivo de Optimización Sin Restricciones: A diferencia del RL no privado estándar, que a menudo depende de una optimización restringida basada en conjuntos de confianza (por ejemplo, métodos de Límite Superior de Confianza), el enfoque propuesto adopta un objetivo de optimización sin restricciones. Este objetivo equilibra explícitamente el valor estimado (optimismo) y el error estadístico (pérdida de Bellman). Esta formulación evita la dificultad de privatizar conjuntos de confianza complejos y dependientes de los datos.
2. Mecanismo Exponencial para la Selección de Políticas: Para privatizar la selección de la función de valor (y consecuentemente la política) de una clase de funciones $\mathcal{F}$, el algoritmo emplea el Mecanismo Exponencial. En lugar de seleccionar determinísticamente la función que maximiza la puntuación (lo cual filtraría datos sensibles), el algoritmo muestrea una función $f^{(k)}$ con una probabilidad proporcional a $\exp(\beta \cdot S(f))$, donde $S(f)$ es una función de puntuación que combina el valor optimista y la pérdida de Bellman.
3. Actualizaciones de Política por Lotes: Para controlar la pérdida de privacidad acumulada (composición) a lo largo de $K$ episodios, el algoritmo actualiza la política solo al comienzo de lotes de tamaño fijo de tamaño $B$. Dentro de un lote, la política permanece fija. Esta estrategia limita el número de veces que un solo punto de datos participa en una actualización privada, permitiendo una acumulación sublineal de pérdida de privacidad en lugar de una lineal.

El artículo presenta dos algoritmos específicos:

• Algoritmo 1: Diseñado para MDP estocásticos generales. Requiere completitud de Bellman (la clase de funciones debe estar cerrada bajo el operador de Bellman) y utiliza una pérdida de error de Bellman con una corrección de ínfimo para manejar problemas de doble muestreo.
• Algoritmo 2: Diseñado para MDP deterministas con recompensas de resultado (un escenario motivado por aplicaciones de Modelos de Lenguaje Grande). Esta variante relaja el requisito a realizabilidad (la función Q óptima existe en la clase) y reemplaza la pérdida de error de Bellman con una pérdida de residual de Bellman basada en resultados, eliminando la necesidad de optimización max-min.

Contribuciones Clave

1. Primeras Garantías Teóricas para Aproximación de Funciones General: El artículo establece las primeras cotas de arrepentimiento sublineales para RL en línea con aproximación de funciones general bajo JDP.
2. Cotas de Arrepentimiento:
   • Para MDP estocásticos generales (Algoritmo 1), el arrepentimiento escala como $\tilde{O}(K^{3/5})$, dependiendo del parámetro de cobertura $C_{cov}$, que caracteriza la dificultad de exploración.
   • Para MDP deterministas con recompensas de resultado (Algoritmo 2), se logra una cota similar de $\tilde{O}(K^{3/5})$ bajo la suposición más débil de realizabilidad.
   • Estas cotas igualan los resultados del estado del arte para el caso de aproximación de funciones lineal en el entorno sin modelo, a pesar de la mayor complejidad de las clases de funciones generales.
3. Subproductos No Privados: El análisis produce nuevas cotas de arrepentimiento para RL no privado bajo restricciones de adaptabilidad (agrupación en lotes de tamaño fijo). Específicamente, muestra que un arrepentimiento de $\tilde{O}(\sqrt{K})$ es alcanzable con $\sqrt{K}$ actualizaciones bajo la condición de cobertura, complementando los resultados existentes basados en la clase de Condición Eluder.
4. Clarificación de la Literatura sobre MDP Lineales: Los autores identifican brechas fundamentales en las afirmaciones recientes de cotas de arrepentimiento mejoradas de $\tilde{O}(\sqrt{K})$ para RL privado con MDP lineales. Argumentan que las pruebas existentes que dependen de la "conmutación de políticas rara" y trucos de determinante fallan bajo restricciones de privacidad porque la monotonía necesaria de la matriz de diseño se rompe por la inyección de ruido de privacidad.

Resultados y Análisis
El análisis teórico se basa en la constante de cobertura, una medida de complejidad introducida por Xie et al. [XFBJK22], que generaliza el concepto de dificultad de exploración más allá de los entornos lineales. El bosquejo de la prueba implica:

• Descomponer el arrepentimiento en un término relacionado con el "error de entrenamiento" (pérdida de Bellman) y un error "en política" (prueba).
• Utilizar el Mecanismo Exponencial para acotar la desviación entre la función seleccionada y la óptima (costo de privacidad).
• Derivar una nueva desigualdad para relacionar el error en política con el error de entrenamiento en presencia de agrupación en lotes, utilizando la constante de cobertura para acotar el desplazamiento de distribución entre la política de recolección de datos y la política actual.
• Optimizar el tamaño del lote $B$ y el parámetro de temperatura $\eta$ para equilibrar la compensación entre la frescura de la información (arrepentimiento) y el costo de privacidad.

El artículo incluye una simulación de concepto en un escenario determinista de recompensas de resultado. Los resultados demuestran la compensación esperada entre privacidad y utilidad: una privacidad más fuerte (menor $\epsilon$) conduce a una convergencia más lenta (episodios de meseta más altos), mientras que la agrupación en lotes introduce un retraso moderado en comparación con el aprendizaje no privado y sin lotes.

Significado
El artículo afirma proporcionar la primera base teórica fundamentada para el RL privado en escenarios que reflejan aplicaciones modernas, como aquellos que involucran Modelos de Lenguaje Grande (LLM) y aproximadores de funciones complejos y no lineales. Al demostrar que la escala de arrepentimiento $\tilde{O}(K^{3/5})$ alcanzable en entornos lineales se extiende a clases de funciones generales bajo JDP, el trabajo cierra una brecha significativa entre la teoría de preservación de privacidad y los sistemas prácticos de RL. Además, al exponer fallos en la literatura reciente sobre MDP lineales, el artículo busca clarificar el panorama del RL privado, asegurando que los avances teóricos futuros se construyan sobre fundamentos analíticos sólidos. El marco se presenta como un enfoque modular que puede adaptarse a diversos mecanismos de privacidad y clases de funciones.