método de gradiente de política

Los métodos de gradiente de política son una clase de algoritmos de aprendizaje por refuerzo y una subclase de métodos de optimización de políticas. A diferencia de los métodos basados en valores, que aprenden una función de valor para derivar una política, los métodos de optimización de políticas aprenden directamente una función de política. $\pi$ que selecciona acciones sin consultar una función de valor. Para que se aplique el gradiente de política, la función de política $\pi _{\theta }$ está parametrizado por un parámetro diferenciable $\theta$ . ^{[ 1 ]}

Descripción general

En el aprendizaje por refuerzo basado en políticas, el actor es una función de política parametrizada. $\pi _{\theta }$ , dónde $\theta$ son los parámetros del actor. El actor toma como argumento el estado del entorno. $s$ y produce una distribución de probabilidad $\pi _{\theta }(\cdot \mid s)$ .

Si el espacio de acción es discreto, entonces $\sum _{a}\pi _{\theta }(a\mid s)=1$ . Si el espacio de acción es continuo, entonces $\int _{a}\pi _{\theta }(a\mid s)\mathrm {d} a=1$ .

El objetivo de la optimización de políticas es encontrar alguna $\theta$ que maximiza la recompensa episódica esperada $J(\theta )$ : $J(\theta )=\mathbb {E} _{\pi _{\theta }}\left[\sum _{t=0}^{T}\gamma ^{t}R_{t}{\Big |}S_{0}=s_{0}\right]$ dónde $\gamma$ es el factor de descuento , $R_{t}$ es la recompensa en el paso $t$ , $s_{0}$ es el estado inicial, y $T$ es el horizonte temporal (que puede ser infinito).

El gradiente de política se define como $\nabla _{\theta }J(\theta )$ Los diferentes métodos de gradiente de política estiman estocásticamente el gradiente de política de diferentes maneras. El objetivo de cualquier método de gradiente de política es maximizar iterativamente $J(\theta )$ mediante ascenso de gradiente . Dado que la parte clave de cualquier método de gradiente de política es la estimación estocástica del gradiente de política, también se estudian bajo el título de "estimación de gradiente de Monte Carlo". ^{[ 2 ]}

REFORZARSE

Gradiente de políticas

El algoritmo REINFORCE , introducido por Ronald J. Williams en 1992, fue el primer método de gradiente de política. ^{[ 3 ]} Se basa en la identidad para el gradiente de política. $\nabla _{\theta }J(\theta )=\mathbb {E} _{\pi _{\theta }}\left[\sum _{t=0}^{T}\nabla _{\theta }\ln \pi _{\theta }(A_{t}\mid S_{t})\;\sum _{t=0}^{T}(\gamma ^{t}R_{t}){\Big |}S_{0}=s_{0}\right]$ que se puede mejorar mediante el "truco de causalidad", es decir, ponderando cada acción únicamente por las recompensas a partir de ese paso de tiempo, ^{[ 1 ]} $\nabla _{\theta }J(\theta )=\mathbb {E} _{\pi _{\theta }}\left[\sum _{t=0}^{T}\nabla _{\theta }\ln \pi _{\theta }(A_{t}\mid S_{t})\sum _{\tau =t}^{T}(\gamma ^{\tau }R_{\tau }){\Big |}S_{0}=s_{0}\right]$

Lema : La esperanza de la función de puntuación es cero, condicionada a cualquier estado presente o pasado. Es decir, para cualquier $0\leq i\leq j\leq T$ y cualquier estado $s_{i}$ , tenemos $\mathbb {E} _{\pi _{\theta }}[\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j})|S_{i}=s_{i}]=0.$

Además, si ${\textstyle \Psi _{i}}$ es una variable aleatoria que es independiente de ${\textstyle A_{i},S_{i+1},A_{i+1},\dots }$ , entonces $\mathbb {E} _{\pi _{\theta }}[\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j})\cdot \Psi _{i}|S_{i}=s_{i}]=0.$

Pruebas

Demostración del lema

Utilice el truco de reparametrización .

${\begin{aligned}\mathbb {E} _{\pi _{\theta }}[\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j})|S_{i}=s_{i}]&=\sum _{s}Pr(S_{j}=s|S_{i}=s_{i})\sum _{a}\pi _{\theta }(a|s)\nabla _{\theta }\ln \pi _{\theta }(a|s)\\&=\sum _{s}Pr(S_{j}=s|S_{i}=s_{i})\sum _{a}\pi _{\theta }(a|s){\frac {\nabla _{\theta }\pi _{\theta }(a|s)}{\pi _{\theta }(a|s)}}\\&=\sum _{s}Pr(S_{j}=s|S_{i}=s_{i})\sum _{a}\nabla _{\theta }\pi _{\theta }(a|s)\\&=\sum _{s}Pr(S_{j}=s|S_{i}=s_{i})\nabla _{\theta }\sum _{a}\pi _{\theta }(a|s)\end{aligned}}$ Desde la política $\pi _{\theta }(a|s)$ es una distribución de probabilidad sobre las acciones para un estado dado, ${\textstyle \sum _{a}\pi _{\theta }(a|s)=1}$ . ${\begin{aligned}\mathbb {E} _{\pi _{\theta }}[\nabla _{\theta }\ln \pi _{\theta }(A|S)]&=\sum _{s}Pr(S_{j}=s|S_{i}=s_{i})\nabla _{\theta }(1)\\&=\sum _{s}Pr(S_{j}=s|S_{i}=s_{i})0\\&=0\end{aligned}}$

Por la ley de la torre y el lema anterior.

${\begin{aligned}\mathbb {E} _{\pi _{\theta }}\left[\Psi _{i}\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j}){\Big |}S_{i}=s_{i}\right]&=\mathbb {E} _{\pi _{\theta }}\left[\mathbb {E} _{\pi _{\theta }}[\Psi _{i}\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j})|S_{j}]{\Big |}S_{i}=s_{i}\right]\\&=\mathbb {E} _{\pi _{\theta }}\left[\Psi _{i}\mathbb {E} _{\pi _{\theta }}[\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j})|S_{j}]{\Big |}S_{i}=s_{i}\right]\\&=\mathbb {E} _{\pi _{\theta }}\left[\Psi _{i}0{\Big |}S_{i}=s_{i}\right]\\&=0\end{aligned}}$

Prueba de las dos identidades

Aplicando el truco de reparametrización ,

${\begin{aligned}\nabla _{\theta }J(\theta )&=\nabla _{\theta }\mathbb {E} _{\pi _{\theta }}\left[\sum _{i\in 0:T}\gamma ^{i}R_{i}{\Big |}S_{0}=s_{0}\right]\\&=\mathbb {E} _{\pi _{\theta }}\left[\left(\sum _{i\in 0:T}\gamma ^{i}R_{i}\right)\nabla _{\theta }\ln(\pi _{\theta }(A_{0},A_{1},\dots ,A_{T}|S_{0},S_{1},\dots ,S_{T})){\Big |}S_{0}=s_{0}\right]\\&=\mathbb {E} _{\pi _{\theta }}\left[\left(\sum _{i\in 0:T}\gamma ^{i}R_{i}\right)\sum _{j\in 0:T}\nabla _{\theta }\ln(\pi _{\theta }(A_{j}|S_{j})){\Big |}S_{0}=s_{0}\right]\\&=\mathbb {E} _{\pi _{\theta }}\left[\sum _{i,j\in 0:T}(\gamma ^{i}R_{i})\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j}){\Big |}S_{0}=s_{0}\right]\end{aligned}}$ que es la primera ecuación.

Por el lema, $\mathbb {E} _{\pi _{\theta }}\left[(\gamma ^{i}R_{i})\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j}){\Big |}S_{0}=s_{0}\right]=0$ para cualquier ${\textstyle 0\leq i<j\leq T}$ . Sustituyendo esto en la fórmula anterior, ponemos a cero todo un triángulo de términos, para obtener ${\begin{aligned}\nabla _{\theta }J(\theta )&=\mathbb {E} _{\pi _{\theta }}\left[\sum _{0\leq j\leq i\leq T}(\gamma ^{i}R_{i})\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j}){\Big |}S_{0}=s_{0}\right]\\&=\mathbb {E} _{\pi _{\theta }}\left[\sum _{j\in 0:T}\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j})\sum _{i\in j:T}(\gamma ^{i}R_{i}){\Big |}S_{0}=s_{0}\right]\end{aligned}}$ que es la segunda ecuación.

Por lo tanto, tenemos un estimador insesgado del gradiente de la política: $\nabla _{\theta }J(\theta )\approx {\frac {1}{N}}\sum _{n=1}^{N}\left[\sum _{t=0}^{T}\nabla _{\theta }\ln \pi _{\theta }(A_{t,n}\mid S_{t,n})\sum _{\tau =t}^{T}(\gamma ^{\tau -t}R_{\tau ,n})\right]$ donde el índice $n$ abarca $N$ trayectorias de despliegue utilizando la política $\pi _{\theta }$ .

La función de puntuación $\nabla _{\theta }\ln \pi _{\theta }(A_{t}\mid S_{t})$ puede interpretarse como la dirección en el espacio de parámetros que aumenta la probabilidad de tomar acción. $A_{t}$ en el estado $S_{t}$ El gradiente de política, entonces, es un promedio ponderado de todas las direcciones posibles para aumentar la probabilidad de tomar cualquier acción en cualquier estado, pero ponderado por señales de recompensa, de modo que si tomar cierta acción en cierto estado está asociado con una alta recompensa, entonces esa dirección se reforzará en gran medida, y viceversa.

Algoritmo

El algoritmo REINFORCE es un bucle:

Despliegue $N$ trayectorias en el entorno, utilizando $\pi _{\theta _{t}}$ como función de política.
Calcular la estimación del gradiente de la política: $g_{i}\leftarrow {\frac {1}{N}}\sum _{n=1}^{N}\left[\sum _{t=0}^{T}\nabla _{\theta _{t}}\ln \pi _{\theta }(A_{t,n}\mid S_{t,n})\sum _{\tau =t}^{T}(\gamma ^{\tau }R_{\tau ,n})\right]$
Actualizar la política mediante ascenso de gradiente: $\theta _{i+1}\leftarrow \theta _{i}+\alpha _{i}g_{i}$

Aquí, $\alpha _{i}$ es la tasa de aprendizaje en el paso de actualización $i$ .

Reducción de la varianza

REINFORCE es un algoritmo on-policy , lo que significa que las trayectorias utilizadas para la actualización deben muestrearse a partir de la política actual. $\pi _{\theta }$ Esto puede generar una alta varianza en las actualizaciones, ya que los retornos $R(\tau )$ pueden variar significativamente entre trayectorias. Se han introducido muchas variantes de REINFORCE, bajo el título de reducción de varianza .

REFORZAR con línea de base

Una forma común de reducir la varianza es el algoritmo REINFORCE con línea base , basado en la siguiente identidad: $\nabla _{\theta }J(\theta )=\mathbb {E} _{\pi _{\theta }}\left[\sum _{t=0}^{T}\nabla _{\theta }\ln \pi _{\theta }(A_{t}|S_{t})\left(\sum _{\tau =t}^{T}(\gamma ^{\tau }R_{\tau })-b(S_{t})\right){\Big |}S_{0}=s_{0}\right]$ para cualquier función $b:{\text{States}}\to \mathbb {R}$ Esto se puede demostrar aplicando el lema anterior.

El algoritmo utiliza el estimador de gradiente modificado. $g_{i}\leftarrow {\frac {1}{N}}\sum _{n=1}^{N}\left[\sum _{t=0}^{T}\nabla _{\theta _{t}}\ln \pi _{\theta }(A_{t,n}|S_{t,n})\left(\sum _{\tau =t}^{T}(\gamma ^{\tau }R_{\tau ,n})-b_{i}(S_{t,n})\right)\right]$ y el algoritmo REINFORCE original es el caso especial donde $b_{i}\equiv 0$ .

Métodos actor-crítico

Si ${\textstyle b_{i}}$ se elige bien, de tal manera que ${\textstyle b_{i}(S_{t})\approx \sum _{\tau =t}^{T}(\gamma ^{\tau }R_{\tau })=\gamma ^{t}V^{\pi _{\theta _{i}}}(S_{t})}$ Esto podría disminuir significativamente la varianza en la estimación del gradiente. Es decir, la línea base debería estar lo más cerca posible de la función de valor. $V^{\pi _{\theta _{i}}}(S_{t})$ en la medida de lo posible, acercándose al ideal de: $\nabla _{\theta }J(\theta )=\mathbb {E} _{\pi _{\theta }}\left[\sum _{t=0}^{T}\nabla _{\theta }\ln \pi _{\theta }(A_{t}|S_{t})\left(\sum _{\tau =t}^{T}(\gamma ^{\tau }R_{\tau })-\gamma ^{t}V^{\pi _{\theta }}(S_{t})\right){\Big |}S_{0}=s_{0}\right]$ Tenga en cuenta que, como política $\pi _{\theta _{t}}$ actualizaciones, la función de valor $V^{\pi _{\theta _{i}}}(S_{t})$ Las actualizaciones también son necesarias, por lo que la línea base también debería actualizarse. Un enfoque común consiste en entrenar una función independiente que estime la función de valor y utilizarla como línea base. Este es uno de los métodos actor-crítico , donde la función de política es el actor y la función de valor es el crítico.

La función Q $Q^{\pi }$ También puede utilizarse como crítico, ya que $\nabla _{\theta }J(\theta )=E_{\pi _{\theta }}\left[\sum _{0\leq t\leq T}\gamma ^{t}\nabla _{\theta }\ln \pi _{\theta }(A_{t}|S_{t})\cdot Q^{\pi _{\theta }}(S_{t},A_{t}){\Big |}S_{0}=s_{0}\right]$ mediante un argumento similar utilizando la ley de la torre.

Restando la función de valor como línea base, encontramos que la función de ventaja $A^{\pi }(S,A)=Q^{\pi }(S,A)-V^{\pi }(S)$ También puede utilizarse como crítico: $\nabla _{\theta }J(\theta )=E_{\pi _{\theta }}\left[\sum _{0\leq t\leq T}\gamma ^{t}\nabla _{\theta }\ln \pi _{\theta }(A_{t}|S_{t})\cdot A^{\pi _{\theta }}(S_{t},A_{t}){\Big |}S_{0}=s_{0}\right]$ En resumen, existen muchos estimadores insesgados para ${\textstyle \nabla _{\theta }J_{\theta }}$ , todo ello en forma de: $\nabla _{\theta }J(\theta )=E_{\pi _{\theta }}\left[\sum _{0\leq t\leq T}\nabla _{\theta }\ln \pi _{\theta }(A_{t}|S_{t})\cdot \Psi _{t}{\Big |}S_{0}=s_{0}\right]$ dónde ${\textstyle \Psi _{t}}$ es cualquier suma lineal de los siguientes términos:

${\textstyle \sum _{0\leq \tau \leq T}(\gamma ^{\tau }R_{\tau })}$ : nunca usado.
${\textstyle \gamma ^{t}\sum _{t\leq \tau \leq T}(\gamma ^{\tau -t}R_{\tau })}$ : utilizado por el algoritmo REINFORCE.
${\textstyle \gamma ^{t}\sum _{t\leq \tau \leq T}(\gamma ^{\tau -t}R_{\tau })-b(S_{t})}$ : utilizado por REINFORCE con algoritmo de línea base.
${\textstyle \gamma ^{t}\left(R_{t}+\gamma V^{\pi _{\theta }}(S_{t+1})-V^{\pi _{\theta }}(S_{t})\right)}$ Aprendizaje TD en 1 paso.
${\textstyle \gamma ^{t}Q^{\pi _{\theta }}(S_{t},A_{t})}$ .
${\textstyle \gamma ^{t}A^{\pi _{\theta }}(S_{t},A_{t})}$ .

Algunos más posibles ${\textstyle \Psi _{t}}$ son las siguientes, con demostraciones muy similares.

${\textstyle \gamma ^{t}\left(R_{t}+\gamma R_{t+1}+\gamma ^{2}V^{\pi _{\theta }}(S_{t+2})-V^{\pi _{\theta }}(S_{t})\right)}$ : Aprendizaje TD en 2 pasos.
${\textstyle \gamma ^{t}\left(\sum _{k=0}^{n-1}\gamma ^{k}R_{t+k}+\gamma ^{n}V^{\pi _{\theta }}(S_{t+n})-V^{\pi _{\theta }}(S_{t})\right)}$ : aprendizaje TD de n pasos.
${\textstyle \gamma ^{t}\sum _{n=1}^{\infty }{\frac {\lambda ^{n-1}}{1-\lambda }}\cdot \left(\sum _{k=0}^{n-1}\gamma ^{k}R_{t+k}+\gamma ^{n}V^{\pi _{\theta }}(S_{t+n})-V^{\pi _{\theta }}(S_{t})\right)}$ : Aprendizaje TD(λ), también conocido como GAE (estimación de ventaja generalizada) . ^{[ 4 ]} Esto se obtiene mediante una suma que decae exponencialmente de los n pasos del aprendizaje TD.

Gradiente de política natural

El método de gradiente de política natural es una variante del método de gradiente de política, propuesto por Sham Kakade en 2001. ^{[ 5 ]} A diferencia de los métodos de gradiente de política estándar, que dependen de la elección de parámetros $\theta$ (haciendo que las actualizaciones dependan de las coordenadas), el gradiente de política natural tiene como objetivo proporcionar una actualización independiente de las coordenadas , que es geométricamente "natural".

Motivación

Actualizaciones estándar del gradiente de política $\theta _{i+1}=\theta _{i}+\alpha \nabla _{\theta }J(\theta _{i})$ resolver un problema de optimización con restricciones: ${\begin{cases}\max _{\theta _{i+1}}J(\theta _{i})+(\theta _{i+1}-\theta _{i})^{T}\nabla _{\theta }J(\theta _{i})\\\|\theta _{i+1}-\theta _{i}\|\leq \alpha \cdot \|\nabla _{\theta }J(\theta _{i})\|\end{cases}}$ Si bien el objetivo (mejora linealizada) tiene un significado geométrico, la restricción euclidiana $\|\theta _{i+1}-\theta _{i}\|$ introduce dependencia de coordenadas. Para abordar esto, el gradiente de política natural reemplaza la restricción euclidiana con una restricción de divergencia de Kullback-Leibler (KL): ${\begin{cases}\max _{\theta _{i+1}}J(\theta _{i})+(\theta _{i+1}-\theta _{i})^{T}\nabla _{\theta }J(\theta _{i})\\{\bar {D}}_{KL}(\pi _{\theta _{i+1}}\|\pi _{\theta _{i}})\leq \epsilon \end{cases}}$ donde la divergencia KL entre dos políticas se promedia sobre la distribución estatal bajo la política $\pi _{\theta _{i}}$ . Eso es, ${\bar {D}}_{KL}(\pi _{\theta _{i+1}}\|\pi _{\theta _{i}}):=\mathbb {E} _{s\sim \pi _{\theta _{i}}}[D_{KL}(\pi _{\theta _{i+1}}(\cdot |s)\|\pi _{\theta _{i}}(\cdot |s))]$ Esto garantiza que las actualizaciones sean invariantes a las transformaciones de parámetros afines invertibles.

aproximación de información de Fisher

Para pequeños $\epsilon$ La divergencia KL se aproxima mediante la métrica de información de Fisher : ${\bar {D}}_{KL}(\pi _{\theta _{i+1}}\|\pi _{\theta _{i}})\approx {\frac {1}{2}}(\theta _{i+1}-\theta _{i})^{T}F(\theta _{i})(\theta _{i+1}-\theta _{i})$ dónde $F(\theta )$ es la matriz de información de Fisher de la política, definida como: $F(\theta )=\mathbb {E} _{s,a\sim \pi _{\theta }}\left[\nabla _{\theta }\ln \pi _{\theta }(a|s)\left(\nabla _{\theta }\ln \pi _{\theta }(a|s)\right)^{T}\right]$ Esto transforma el problema en un problema de programación cuadrática , lo que produce la actualización natural del gradiente de la política: $\theta _{i+1}=\theta _{i}+\alpha F(\theta _{i})^{-1}\nabla _{\theta }J(\theta _{i})$ El tamaño del paso $\alpha$ se ajusta normalmente para mantener la restricción KL, con ${\textstyle \alpha \approx {\sqrt {\frac {2\epsilon }{(\nabla _{\theta }J(\theta _{i}))^{T}F(\theta _{i})^{-1}\nabla _{\theta }J(\theta _{i})}}}}$ .

Invertir $F(\theta )$ Requiere una gran capacidad de cálculo, especialmente para parámetros de alta dimensionalidad (por ejemplo, redes neuronales). Las implementaciones prácticas suelen utilizar aproximaciones.

Optimización de la política de la región de confianza (TRPO)

La optimización de políticas de región de confianza (TRPO) es un método de gradiente de políticas que extiende el enfoque de gradiente de políticas natural al imponer una restricción de región de confianza en las actualizaciones de políticas. ^{[ 6 ]} Desarrollado por Schulman et al. en 2015, TRPO mejora el método de gradiente de políticas natural.

El descenso de gradiente natural es teóricamente óptimo si la función objetivo es realmente una función cuadrática, pero esto es solo una aproximación. La búsqueda lineal y la restricción KL de TRPO intentan limitar la solución a una "región de confianza" dentro de la cual esta aproximación no falla. Esto hace que TRPO sea más robusto en la práctica.

Formulación

Al igual que el gradiente de política natural, TRPO actualiza iterativamente los parámetros de la política. $\theta$ resolviendo un problema de optimización con restricciones especificado sin coordenadas: ${\begin{cases}\max _{\theta }L(\theta ,\theta _{i})\\{\bar {D}}_{KL}(\pi _{\theta }\|\pi _{\theta _{i}})\leq \epsilon \end{cases}}$ dónde

$L(\theta ,\theta _{i})=\mathbb {E} _{s,a\sim \pi _{\theta _{i}}}\left[{\frac {\pi _{\theta }(a|s)}{\pi _{\theta _{i}}(a|s)}}A^{\pi _{\theta _{i}}}(s,a)\right]$ es la ventaja sustituta , que mide el rendimiento de $\pi _{\theta }$ en relación con la antigua política $\pi _{\theta _{i}}$ .
$\epsilon$ es el radio de la región de confianza.

Cabe señalar que, en general, son posibles otras ventajas indirectas: $L(\theta ,\theta _{i})=\mathbb {E} _{s,a\sim \pi _{\theta _{i}}}\left[{\frac {\pi _{\theta }(a|s)}{\pi _{\theta _{i}}(a|s)}}\Psi ^{\pi _{\theta _{i}}}(s,a)\right]$ dónde $\Psi$ es cualquier suma lineal del tipo mencionado anteriormente. De hecho, OpenAI recomendó utilizar la Estimación de Ventaja Generalizada, en lugar de la ventaja simple. $A^{\pi _{\theta }}$ .

La ventaja del sustituto $L(\theta ,\theta _{t})$ está diseñado para alinearse con el gradiente de política $\nabla _{\theta }J(\theta )$ . Específicamente, cuando $\theta =\theta _{t}$ , $\nabla _{\theta }L(\theta ,\theta _{t})$ es igual al gradiente de política derivado de la función de ventaja: $\nabla _{\theta }J(\theta )=\mathbb {E} _{(s,a)\sim \pi _{\theta }}\left[\nabla _{\theta }\ln \pi _{\theta }(a|s)\cdot A^{\pi _{\theta }}(s,a)\right]=\nabla _{\theta }L(\theta ,\theta _{t})$ Sin embargo, cuando $\theta \neq \theta _{i}$ Esto no es necesariamente cierto. Por lo tanto, es un "sustituto" del objetivo real.

Al igual que con el gradiente de política natural, para pequeñas actualizaciones de política, TRPO aproxima la ventaja sustituta y la divergencia KL utilizando expansiones de Taylor alrededor de $\theta _{t}$ : ${\begin{aligned}L(\theta ,\theta _{i})&\approx g^{T}(\theta -\theta _{i}),\\{\bar {D}}_{\text{KL}}(\pi _{\theta }\|\pi _{\theta _{i}})&\approx {\frac {1}{2}}(\theta -\theta _{i})^{T}H(\theta -\theta _{i}),\end{aligned}}$ dónde:

$g=\nabla _{\theta }L(\theta ,\theta _{i}){\big |}_{\theta =\theta _{i}}$ es el gradiente de política.
$F=\nabla _{\theta }^{2}{\bar {D}}_{\text{KL}}(\pi _{\theta }\|\pi _{\theta _{i}}){\big |}_{\theta =\theta _{i}}$ es la matriz de información de Fisher.

Esto reduce el problema a una optimización cuadrática, lo que produce la actualización natural del gradiente de la política: $\theta _{i+1}=\theta _{i}+{\sqrt {\frac {2\epsilon }{g^{T}F^{-1}g}}}F^{-1}g.$ Hasta ahora, esto es esencialmente lo mismo que el método del gradiente natural. Sin embargo, TRPO lo mejora mediante dos modificaciones:

Utilice el método del gradiente conjugado para resolver $x$ en $Fx=g$ iterativamente sin inversión explícita de la matriz.
Utilice la búsqueda lineal con retroceso para garantizar que se cumpla la restricción de la región de confianza. Específicamente, retrocede el tamaño del paso para garantizar la restricción KL y la mejora de la política. Es decir, prueba cada una de las siguientes soluciones de prueba. $\theta _{i+1}=\theta _{i}+{\sqrt {\frac {2\epsilon }{x^{T}Fx}}}x,\;\theta _{i}+\alpha {\sqrt {\frac {2\epsilon }{x^{T}Fx}}}x,\;\theta _{i}+\alpha ^{2}{\sqrt {\frac {2\epsilon }{x^{T}Fx}}}x,\;\dots$ hasta que encuentre uno que satisfaga la restricción KL. ${\bar {D}}_{KL}(\pi _{\theta _{i+1}}\|\pi _{\theta _{i}})\leq \epsilon$ y da como resultado una mayor $L(\theta _{i+1},\theta _{i})\geq L(\theta _{i},\theta _{i})$ . Aquí, $\alpha \in (0,1)$ es el coeficiente de retroceso.

Optimización de políticas proximales (PPO)

Una mejora adicional es la optimización de políticas proximales (PPO), que evita incluso el cálculo $F(\theta )$ y $F(\theta )^{-1}$ mediante una aproximación de primer orden utilizando razones de probabilidad recortadas. ^{[ 7 ]}

Específicamente, en lugar de maximizar la ventaja sustituta $\max _{\theta }L(\theta ,\theta _{t})=\mathbb {E} _{s,a\sim \pi _{\theta _{t}}}\left[{\frac {\pi _{\theta }(a|s)}{\pi _{\theta _{t}}(a|s)}}A^{\pi _{\theta _{t}}}(s,a)\right]$ bajo una restricción de divergencia KL, inserta directamente la restricción en la ventaja sustituta: $\max _{\theta }\mathbb {E} _{s,a\sim \pi _{\theta _{t}}}\left[{\begin{cases}\min \left({\frac {\pi _{\theta }(a|s)}{\pi _{\theta _{t}}(a|s)}},1+\epsilon \right)A^{\pi _{\theta _{t}}}(s,a)&{\text{ if }}A^{\pi _{\theta _{t}}}(s,a)>0\\\max \left({\frac {\pi _{\theta }(a|s)}{\pi _{\theta _{t}}(a|s)}},1-\epsilon \right)A^{\pi _{\theta _{t}}}(s,a)&{\text{ if }}A^{\pi _{\theta _{t}}}(s,a)<0\end{cases}}\right]$ y PPO maximiza la ventaja del sustituto mediante el descenso de gradiente estocástico, como de costumbre.

En otras palabras, ascender el gradiente de la nueva función de ventaja sustituta significa que, en algún estado $s,a$ , si la ventaja es positiva: $A^{\pi _{\theta _{t}}}(s,a)>0$ , entonces el gradiente debería dirigir $\theta$ hacia la dirección que aumenta la probabilidad de realizar la acción $a$ bajo el estado $s$ Sin embargo, tan pronto como $\theta$ ha cambiado tanto que $\pi _{\theta }(a|s)\geq (1+\epsilon )\pi _{\theta _{t}}(a|s)$ , entonces el gradiente debería dejar de apuntar en esa dirección. Y de manera similar si $A^{\pi _{\theta _{t}}}(s,a)<0$ De este modo, PPO evita forzar demasiado la actualización de parámetros y evita modificar demasiado la política.

Para ser más precisos, para actualizar $\theta _{t}$ a $\theta _{t+1}$ requiere múltiples pasos de actualización en el mismo lote de datos. Inicializaría $\theta =\theta _{t}$ , luego aplicar repetidamente el descenso de gradiente (como el optimizador Adam ) para actualizar $\theta$ hasta que la ventaja sustituta se haya estabilizado. Luego asignaría $\theta _{t+1}$ a $\theta$ y hazlo de nuevo.

Durante este bucle interno, la primera actualización de $\theta$ no golpearía el $1-\epsilon ,1+\epsilon$ límites, pero como $\theta$ se actualiza cada vez más lejos de $\theta _{t}$ , eventualmente comienza a alcanzar los límites. Por cada alcance de límite, el gradiente correspondiente se vuelve cero y, por lo tanto, PPO evita actualizar $\theta$ demasiado lejos de $\theta _{t}$ .

Esto es importante, porque la pérdida sustituta supone que el par estado-acción $s,a$ se toma como muestra de lo que el agente vería si ejecutara la política. $\pi _{\theta _{t}}$ , pero el gradiente de política debería estar en la política. Entonces, como $\theta$ cambios, la pérdida sustituta se aleja cada vez más de la política. Por eso es importante mantener $\theta$ próximo a $\theta _{t}$ es necesario.

Si existe una política de referencia $\pi _{\text{ref}}$ que la política entrenada no debería desviarse demasiado, entonces se puede agregar una penalización adicional por divergencia KL: $-\beta \mathbb {E} _{s,a\sim \pi _{\theta _{t}}}\left[\log \left({\frac {\pi _{\theta }(a|s)}{\pi _{\text{ref}}(a|s)}}\right)\right]$ dónde $\beta$ ajusta la fuerza de la penalización. Esto se ha utilizado en el entrenamiento de modelos de lenguaje de razonamiento con aprendizaje por refuerzo a partir de retroalimentación humana . ^{[ 8 ]} El término de penalización de divergencia KL se puede estimar con menor varianza utilizando la forma equivalente (ver f-divergencia para más detalles): ^{[ 9 ]} $-\beta \mathbb {E} _{s,a\sim \pi _{\theta _{t}}}\left[\log \left({\frac {\pi _{\theta }(a|s)}{\pi _{\text{ref}}(a|s)}}\right)+{\frac {\pi _{\text{ref}}(a|s)}{\pi _{\theta }(a|s)}}-1\right]$

Optimización de políticas relativas de grupo (GRPO)

La optimización de políticas relativas de grupo (GRPO) es una variante menor de PPO que omite el estimador de la función de valor. $V$ En cambio, para cada estado $s$ , muestrea múltiples acciones $a_{1},\dots ,a_{G}$ de la política $\pi _{\theta _{t}}$ , luego calcular la ventaja relativa del grupo ^{[ 9 ]} $A^{\pi _{\theta _{t}}}(s,a_{j})={\frac {r(s,a_{j})-\mu }{\sigma }}$ dónde $\mu ,\sigma$ son la media y la desviación estándar de $r(s,a_{1}),\dots ,r(s,a_{G})$ Es decir, es la puntuación estándar de las recompensas.

Luego, maximiza el objetivo PPO, promediado sobre todas las acciones: $\max _{\theta }{\frac {1}{G}}\sum _{i=1}^{G}\mathbb {E} _{(s,a_{1},\dots ,a_{G})\sim \pi _{\theta _{t}}}\left[{\begin{cases}\min \left({\frac {\pi _{\theta }(a_{i}|s)}{\pi _{\theta _{t}}(a_{i}|s)}},1+\epsilon \right)A^{\pi _{\theta _{t}}}(s,a_{i})&{\text{ if }}A^{\pi _{\theta _{t}}}(s,a_{i})>0\\\max \left({\frac {\pi _{\theta }(a_{i}|s)}{\pi _{\theta _{t}}(a_{i}|s)}},1-\epsilon \right)A^{\pi _{\theta _{t}}}(s,a_{i})&{\text{ if }}A^{\pi _{\theta _{t}}}(s,a_{i})<0\end{cases}}\right]$ Intuitivamente, cada paso de actualización de la política en GRPO hace que sea más probable que la política responda a cada estado con una acción que haya tenido un rendimiento relativamente mejor que otras acciones probadas en ese estado, y menos probable que responda con una que haya tenido un rendimiento relativamente peor.

Como antes, el término de penalización KL se puede aplicar para incentivar a la política entrenada a mantenerse cerca de una política de referencia. GRPO fue propuesto por primera vez en el contexto del entrenamiento de modelos de lenguaje de razonamiento por investigadores de DeepSeek . ^{[ 9 ]}

Optimización de políticas y la perspectiva del descenso en espejo (MDPO)

Métodos como TRPO, PPO y el gradiente de política natural comparten una idea común: si bien la política debe actualizarse en la dirección del gradiente de política, la actualización debe realizarse de manera segura y estable, generalmente medida por cierta distancia con respecto a la política anterior a la actualización.

Una noción similar de estabilidad de actualización se encuentra en técnicas de optimización convexa proximal como Mirror Descent . ^{[ 10 ]} Allí, ${\textstyle \mathbf {x} }$ , el minimizador propuesto de ${\textstyle f}$ en algún conjunto de restricciones ${\textstyle {\mathcal {C}}}$ , se actualiza iterativamente en la dirección del gradiente ${\textstyle \nabla f}$ , con una penalización por proximidad respecto al actual ${\textstyle \mathbf {x} _{t}}$ medido por cierta divergencia de Bregman ${\textstyle B_{\omega }}$ , que puede formalizarse mediante la siguiente fórmula: $\mathbf {x} _{t+1}\in \arg \min _{\mathbf {x} \in {\mathcal {C}}}\nabla f(\mathbf {x} _{t})^{T}(\mathbf {x} -\mathbf {x} _{t})+{\frac {1}{\eta _{t}}}B_{\omega }(x,x_{t}),$ dónde ${\textstyle \eta _{t}}$ Controla la proximidad entre iteraciones consecutivas, de forma similar a la tasa de aprendizaje en el descenso de gradiente.

Esto lleva a reconsiderar el procedimiento de actualización de políticas como un procedimiento de optimización destinado a encontrar una política óptima, en el paisaje de optimización (no convexo) del proceso de decisión de Markov (MDP) subyacente. Este punto de vista de optimización que utiliza el gradiente de la política se denomina Optimización de Políticas de Descenso Espejo (MDPO), ^{[ 11 ]}^{[ 12 ]} lo que conduce a la siguiente actualización cuando la KL es la divergencia de Bregman elegida: $\pi _{t+1}\in \arg \max _{\pi }\mathbb {E} _{s,a\sim \pi }\left[A^{\pi _{t}}(s,a)\right]+{\frac {1}{\eta _{t}}}D_{KL}(\pi ||\pi _{t})$ Con una política parametrizada ${\textstyle \pi _{\theta }}$ , la pérdida de MDPO se convierte en: $\max _{\theta }L(\theta ,\theta _{t})=\mathbb {E} _{s,a\sim \pi _{\theta _{t}}}\left[{\frac {\pi _{\theta }(a|s)}{\pi _{\theta _{t}}(a|s)}}A^{\pi _{\theta _{t}}}(s,a)\right]+{\frac {1}{\eta _{t}}}D_{KL}(\pi _{\theta }||\pi _{\theta _{t}})$ Este objetivo puede utilizarse junto con otras técnicas comunes, como el recorte realizado en PPO. De hecho, la penalización por divergencia KL también aparece en el artículo original de PPO, ^{[ 7 ]} lo que sugiere que la perspectiva MDPO constituye una unificación teórica de los principales conceptos de derivación que subyacen a muchas técnicas concurrentes de gradiente de política.

Véase también

Referencias

1 2 Sutton, Richard S; McAllester, David; Singh, Satinder; Mansour, Yishay (1999). "Métodos de gradiente de política para el aprendizaje por refuerzo con aproximación de funciones" . Avances en sistemas de procesamiento de información neuronal . 12. MIT Press.
↑ Mohamed, Shakir; Rosca, Mihaela; Figurnov, Michael; Mnih, Andriy (2020). "Estimación del gradiente de Monte Carlo en aprendizaje automático" . Journal of Machine Learning Research . 21 (132): 1– 62. arXiv : 1906.10652 . ISSN 1533-7928 .
↑ Williams, Ronald J. (mayo de 1992). "Algoritmos estadísticos simples de seguimiento de gradiente para el aprendizaje por refuerzo conexionista" . Machine Learning . 8 ( 3–4 ): 229–256 . doi : 10.1007/BF00992696 . ISSN 0885-6125 .
↑ Schulman, John; Moritz, Philipp; Levine, Sergey ; Jordan, Michael; Abbeel, Pieter (2018-10-20). "Control continuo de alta dimensión mediante estimación de ventaja generalizada". arXiv : 1506.02438 [ cs.LG ].
↑ Kakade, Sham M (2001). "Un gradiente de política natural" . Avances en sistemas de procesamiento de información neuronal . 14. MIT Press.
↑ Schulman, John; Levine, Sergey; Moritz, Philipp; Jordan, Michael; Abbeel, Pieter (06-07-2015). "Optimización de la política de región de confianza" . Actas de la 32.ª Conferencia Internacional sobre Aprendizaje Automático . 37. Lille, Francia: JMLR.org: 1889–1897 .
1 2 Schulman, John; Wolski, Filip; Dhariwal, Prafulla; Radford, Alec; Klimov, Oleg (2017-08-28). "Algoritmos de optimización de políticas proximales". arXiv : 1707.06347 [ cs.LG ].
↑ Nisan Stiennon; Long Ouyang; Jeffrey Wu; Daniel Ziegler; Ryan Lowe; Chelsea Voss; Alec Radford; Dario Amodei; Paul F. Christiano (2020). "Aprender a resumir con retroalimentación humana" . Avances en sistemas de procesamiento de información neuronal . 33 .
1 2 3 Shao, Zhihong; Wang, Peiyi; Zhu, Qihao; Xu, Runxin; Canción, Junxiao; Bi, Xiao; Zhang, Haowei; Zhang, Mingchuan; Li, YK (27 de abril de 2024). "DeepSeekMath: superando los límites del razonamiento matemático en modelos de lenguaje abierto". arXiv : 2402.03300 [ cs.CL ].
↑ Arkadi Nemirovsky y David Yudin. Complejidad del problema y eficiencia del método en optimización. John Wiley & Sons, 1983.
↑ Shani, Lior; Efroni, Yonathan; Mannor, Shie (2020-04-03). "Optimización de políticas de región de confianza adaptativa: convergencia global y tasas más rápidas para MDPS regularizados" . Actas de la Conferencia AAAI sobre Inteligencia Artificial . 34 (4): 5668– 5675. arXiv : 1909.02769 . doi : 10.1609/aaai.v34i04.6021 . ISSN 2374-3468 .
^ Tomar, Manán; Shani, Lior; Efroni, Yonatán; Ghavamzadeh, Mohammad (20 de mayo de 2020). "Optimización de la política de descenso del espejo". arXiv : 2005.09814v5 [ cs.LG ].

Sutton, Richard S.; Barto, Andrew G. (2018). Aprendizaje por refuerzo: una introducción . Serie de computación adaptativa y aprendizaje automático (2.ª ed.). Cambridge, Massachusetts: The MIT Press. ISBN 978-0-262-03924-6.
Bertsekas, Dimitri P. (2019). Aprendizaje por refuerzo y control óptimo (2.ª ed.). Belmont, Massachusetts: Athena Scientific. ISBN 978-1-886529-39-7.
Grossi, Csaba (2010). Algoritmos para el aprendizaje por refuerzo . Conferencias de síntesis sobre inteligencia artificial y aprendizaje automático (1.ª ed.). Cham: Springer International Publishing. ISBN 978-3-031-00423-0.
Mohamed, Shakir; Rosca, Mihaela; Figurnov, Michael; Mnih, Andriy (2020). "Estimación del gradiente de Monte Carlo en aprendizaje automático" . Journal of Machine Learning Research . 21 (132): 1– 62. arXiv : 1906.10652 . ISSN 1533-7928 .

Enlaces externos

Weng, Lilian (2018-04-08). "Algoritmos de gradiente de política" . lilianweng.github.io . Recuperado el 25 de enero de 2025 .
"Vanilla Policy Gradient — Spinning Up documentation" . spinningup.openai.com . Consultado el 25 de enero de 2025 .

[suttonetal-1] 1 2 Sutton, Richard S; McAllester, David; Singh, Satinder; Mansour, Yishay (1999). "Métodos de gradiente de política para el aprendizaje por refuerzo con aproximación de funciones" . Avances en sistemas de procesamiento de información neuronal . 12. MIT Press.

[2] Mohamed, Shakir; Rosca, Mihaela; Figurnov, Michael; Mnih, Andriy (2020). "Estimación del gradiente de Monte Carlo en aprendizaje automático" . Journal of Machine Learning Research . 21 (132): 1– 62. arXiv : 1906.10652 . ISSN 1533-7928 .

[3] Williams, Ronald J. (mayo de 1992). "Algoritmos estadísticos simples de seguimiento de gradiente para el aprendizaje por refuerzo conexionista" . Machine Learning . 8 ( 3–4 ): 229–256 . doi : 10.1007/BF00992696 . ISSN 0885-6125 .

[4] Schulman, John; Moritz, Philipp; Levine, Sergey ; Jordan, Michael; Abbeel, Pieter (2018-10-20). "Control continuo de alta dimensión mediante estimación de ventaja generalizada". arXiv : 1506.02438 [ cs.LG ].

[5] Kakade, Sham M (2001). "Un gradiente de política natural" . Avances en sistemas de procesamiento de información neuronal . 14. MIT Press.

[:3-6] Schulman, John; Levine, Sergey; Moritz, Philipp; Jordan, Michael; Abbeel, Pieter (06-07-2015). "Optimización de la política de región de confianza" . Actas de la 32.ª Conferencia Internacional sobre Aprendizaje Automático . 37. Lille, Francia: JMLR.org: 1889–1897 .

[:0-7] 1 2 Schulman, John; Wolski, Filip; Dhariwal, Prafulla; Radford, Alec; Klimov, Oleg (2017-08-28). "Algoritmos de optimización de políticas proximales". arXiv : 1707.06347 [ cs.LG ].

[summarizationpaper-8] Nisan Stiennon; Long Ouyang; Jeffrey Wu; Daniel Ziegler; Ryan Lowe; Chelsea Voss; Alec Radford; Dario Amodei; Paul F. Christiano (2020). "Aprender a resumir con retroalimentación humana" . Avances en sistemas de procesamiento de información neuronal . 33 .

[:1-9] 1 2 3 Shao, Zhihong; Wang, Peiyi; Zhu, Qihao; Xu, Runxin; Canción, Junxiao; Bi, Xiao; Zhang, Haowei; Zhang, Mingchuan; Li, YK (27 de abril de 2024). "DeepSeekMath: superando los límites del razonamiento matemático en modelos de lenguaje abierto". arXiv : 2402.03300 [ cs.CL ].

[10] Arkadi Nemirovsky y David Yudin. Complejidad del problema y eficiencia del método en optimización. John Wiley & Sons, 1983.

[11] Shani, Lior; Efroni, Yonathan; Mannor, Shie (2020-04-03). "Optimización de políticas de región de confianza adaptativa: convergencia global y tasas más rápidas para MDPS regularizados" . Actas de la Conferencia AAAI sobre Inteligencia Artificial . 34 (4): 5668– 5675. arXiv : 1909.02769 . doi : 10.1609/aaai.v34i04.6021 . ISSN 2374-3468 .

[12] Tomar, Manán; Shani, Lior; Efroni, Yonatán; Ghavamzadeh, Mohammad (20 de mayo de 2020). "Optimización de la política de descenso del espejo". arXiv : 2005.09814v5 [ cs.LG ].

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 8 ]

[ 10 ]

[ 11 ]

[ 12 ]