Comprender el papel del factor de descuento en el aprendizaje por refuerzo

Me estoy enseñando sobre el aprendizaje por refuerzo y estoy tratando de entender el concepto de recompensa con descuento. Entonces, la recompensa es necesaria para decirle al sistema qué pares de estado-acción son buenos y cuáles son malos. Pero lo que no entiendo es por qué es necesaria la recompensa con descuento. ¿Por qué debería importar si se alcanza un buen estado lo antes posible?

Entiendo que esto es relevante en algunos casos específicos. Por ejemplo, si está utilizando el aprendizaje por refuerzo para negociar en el mercado de valores, es más beneficioso obtener ganancias más temprano que tarde. Esto se debe a que tener ese dinero ahora le permite hacer cosas con ese dinero ahora, lo cual es más deseable que hacer cosas con ese dinero más adelante.

Pero en la mayoría de los casos, no veo por qué el descuento es útil. Por ejemplo, supongamos que desea que un robot aprenda a navegar por una habitación para llegar al otro lado, donde hay penalizaciones si choca con un obstáculo. Si no hubiera un factor de descuento, entonces aprendería a llegar al otro lado perfectamente, sin chocar con ningún obstáculo. Puede llevar mucho tiempo llegar allí, pero eventualmente llegará allí.

Pero si le damos un descuento a la recompensa, entonces se alentará al robot a llegar al otro lado de la habitación rápidamente, incluso si tiene que chocar con objetos en el camino. Claramente, este no es un resultado deseable. Claro, desea que el robot llegue al otro lado rápidamente, pero no si esto significa que tiene que chocar con objetos en el camino.

Entonces, mi intuición es que cualquier forma de factor de descuento, en realidad conducirá a una solución subóptima. Y la elección del factor de descuento a menudo parece arbitraria: muchos métodos que he visto simplemente lo establecen en 0.9. Esto parece ser muy ingenuo para mí, y parece dar una compensación arbitraria entre la solución óptima y la solución más rápida, mientras que en realidad esta compensación es muy importante.

Por favor, ¿alguien puede ayudarme a entender todo esto? Gracias :)

TL; DR.

El hecho de que la tasa de descuento sea menor que 1 es un truco matemático para hacer una suma infinita finita. Esto ayuda a probar la convergencia de ciertos algoritmos.

En la práctica, el factor de descuento podría usarse para modelar el hecho de que el tomador de decisiones no está seguro de si en el próximo instante de decisión el mundo (por ejemplo, entorno / juego / proceso ) va a terminar.

Por ejemplo:

Si el que toma las decisiones es un robot, el factor de descuento podría ser la probabilidad de que el robot se apague en el próximo instante (el mundo termina en la terminología anterior). Esa es la razón por la cual el robot es miope y no optimiza la recompensa de suma sino la recompensa de suma con descuento .

Factor de descuento menor que 1 (en detalle)

Para responder de manera más precisa, por qué la tasa de descuento tiene que ser menor que uno, primero presentaré los Procesos de decisión de Markov (MDP).

$\mathcal{S}$$\mathcal{A}$

En su entorno básico, el tomador de decisiones toma una acción y obtiene una recompensa del entorno, y el entorno cambia su estado. Luego, el tomador de decisiones percibe el estado del medio ambiente, toma una acción, recibe una recompensa, etc. Las transiciones de estado son probabilísticas y dependen únicamente del estado real y la acción tomada por el tomador de decisiones. La recompensa obtenida por el tomador de decisiones depende de la acción tomada, y tanto del estado original como del nuevo del entorno.

$R_{a_i}(s_j,s_k)$$a_i$$s_j$$s_k$$a_i$$\pi$ $\pi(\cdot):\mathcal{S}\rightarrow\mathcal{A}$$s_j \in \mathcal{S}$$a_i \in \mathcal{A}$$\pi$

$\pi$

$$\begin{equation} \label{eq:1} \max_{\pi:S(n)\rightarrow a_i} \lim_{T\rightarrow \infty } E \left\{ \sum_{n=1}^T \beta^n R_{x_i}(S(n),S(n+1)) \right\} (1), \end{equation}$$ $\beta$$\beta<1$

Tenga en cuenta que el problema de optimización anterior tiene un horizonte de tiempo infinito ( ) y el objetivo es maximizar la suma de la recompensa (la recompensa se multiplica por ). Esto generalmente se llama un problema MDP con un criterio de recompensa con descuento de horizonte infinito .$T\rightarrow \infty$$discounted$$R$$\beta^n$

El problema se llama descontado porque . Si no se tratara de un problema con descuento la suma no convergería. Todas las políticas que han obtenido en promedio una recompensa positiva en cada instante de tiempo sumarían hasta el infinito. Sería un criterio de recompensa de suma de horizonte infinito , y no es un buen criterio de optimización.$\beta<1$$\beta=1$

Aquí hay un ejemplo de juguete para mostrarle lo que quiero decir:

Suponga que solo hay dos acciones posibles y que la función de recompensa es igual a si y si (la recompensa no depende del estado).$a={0,1}$$R$$1$$a=1$$0$$a=0$

Está claro que la política que obtiene más recompensa es tomar siempre la acción y nunca la acción . Llamaré a esta política . Compararé con otra política que tome la acción con una probabilidad pequeña , y la acción caso contrario.$a=1$$a=0$$\pi^*$$\pi^*$$\pi'$$a=1$$\alpha << 1$$a=0$

En el horizonte infinito, la ecuación de criterios de recompensa con descuento (1) se convierte en (la suma de una serie geométrica) para la política mientras que para la política ecuación (1) se convierte en . Como , decimos que es una política mejor que . En realidad, es la política óptima.$\frac{1}{1-\beta}$$\pi^*$$\pi '$$\frac{\alpha}{1-\beta}$$\frac{1}{1-\beta} > \frac{\alpha}{1-\beta}$$\pi^*$$\pi '$$\pi^*$

En el criterio de recompensa de suma de horizonte infinito ( ) la ecuación (1) no converge para ninguna de las políticas (suma hasta el infinito). Entonces, mientras que la política alcanza mayores recompensas que ambas políticas son iguales de acuerdo con este criterio. Esa es una razón por la cual el criterio de recompensa de suma de horizonte infinito no es útil.$\beta=1$$\pi$$\pi'$

Como mencioné antes, hace el truco de hacer que la suma en la ecuación (1) converja.$\beta<1$

Otros criterios de optimización

Existen otros criterios de optimización que no imponen que :$\beta<1$

El criterio de horizonte finito es que el objetivo es maximizar la recompensa con descuento hasta el horizonte temporal$T$

$$\begin{equation} \label{eq:2} \max_{\pi:S(n)\rightarrow a_i} E \left\{ \sum_{n=1}^T \beta^n R_{x_i}(S(n),S(n+1)) \right\}, \end{equation}$$

para y finito.$\beta \leq 1$$T$

En el criterio de recompensa promedio de horizonte infinito, el objetivo es

$$\begin{equation} \max_{\pi:S(n)\rightarrow a_i} \lim_{T\rightarrow \infty } E \left\{ \sum_{n=1}^T \frac{1}{T} R_{x_i}(S(n),S(n+1)) \right\}, \end{equation}$$

Nota final

Dependiendo de los criterios de optimización, se usaría un algoritmo diferente para encontrar la política óptima. Por ejemplo, las políticas óptimas de los problemas de horizonte finito dependerían tanto del estado como del instante de tiempo real. La mayoría de los algoritmos de aprendizaje de refuerzo (como SARSA o Q-learning) convergen con la política óptima solo para los criterios de recompensa de horizonte infinito con descuento (lo mismo ocurre con los algoritmos de programación dinámica). Para los criterios de recompensa promedio, no se ha demostrado que ningún algoritmo converja con la política óptima, sin embargo, se puede utilizar el aprendizaje en R que tiene un buen rendimiento, aunque no una buena convergencia teórica.

Tiene razón en que el factor de descuento (llamado - tenga en cuenta que esto es diferente de de TD- ) actúa como una "urgencia de vida" y, por lo tanto, es parte del problema , al igual que en vidas humanas: algunas personas viven como si fueran a vivir para siempre; Algunas personas viven como si fueran a morir mañana.$\gamma$$\lambda$$\lambda$

TL; DR: los factores de descuento están asociados con los horizontes temporales. Los horizontes de tiempo más largos tienen mucha más variación, ya que incluyen información más irrelevante, mientras que los horizontes de tiempo corto están sesgados hacia ganancias a corto plazo.

El factor de descuento determina esencialmente cuánto se preocupan los agentes de aprendizaje de refuerzo por las recompensas en el futuro distante en relación con las del futuro inmediato. Si , el agente será completamente miope y solo aprenderá sobre las acciones que producen una recompensa inmediata. Si , el agente evaluará cada una de sus acciones en función de la suma total de todas sus recompensas futuras.$\gamma = 0$$\gamma = 1$

Entonces, ¿por qué no siempre querrías hacer más alto posible? Bueno, la mayoría de las acciones no tienen repercusiones duraderas. Por ejemplo, suponga que el primer día de cada mes decide deleitarse con un batido, y debe decidir si obtendrá un batido de arándanos o de fresa. Como buen aprendiz de refuerzo, usted juzga la calidad de su decisión según cuán grandes sean sus recompensas posteriores. Si su horizonte de tiempo es muy corto, solo tendrá en cuenta las recompensas inmediatas, como cuán sabroso es su batido. Con un horizonte de tiempo más largo, como unas pocas horas, también puede tener en cuenta cosas como si tiene malestar estomacal o no. Pero si su horizonte temporal dura todo el mes, entonces cada cosa que lo hace sentir bien o mal durante todo el mes$\gamma$tendrá en cuenta su juicio sobre si tomó o no la decisión correcta de batido. Estará teniendo en cuenta mucha información irrelevante y, por lo tanto, su juicio tendrá una gran variación y será difícil de aprender.

Elegir un valor particular de es equivalente a elegir un horizonte de tiempo. Ayuda a reescribir la recompensa con descuento de un agente como donde me identifico y . El valor muestra explícitamente el horizonte de tiempo asociado con un factor de descuento; corresponde a , y cualquier recompensa que sea mucho más que$\gamma$$G$

$$G_t = R_{t} + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots \\ = \sum_{k=0}^{\infty} \gamma^k R_{t+k} = \sum_{\Delta t=0}^{\infty} e^{-\Delta t / \tau} R_{t+\Delta t}$$ $\gamma = e^{-1/\tau}$$k \rightarrow \Delta t$$\tau$$\gamma = 1$$\tau = \infty$$\tau$los pasos de tiempo en el futuro se suprimen exponencialmente. En general, debe elegir un factor de descuento tal que el horizonte temporal contenga todas las recompensas relevantes para una acción en particular, pero ya no.