11.5 Generalización en Aprendizaje por Refuerzo

Hasta ahora hemos asumido que se tiene una representación explícita en forma de tabla (i.e., una salida por cada tupla de entradas). Esto funciona para epacios pequeños, pero es impensable para dominios como ajedrez ($10^{120}$) o backgammon ($10^{50}$).

Una forma de hacerlo es con una representación implícita, i.e., una función.

Por ejemplo en juegos, una función de utilidad estimada se puede representar como una función lineal pesada sobre un conjunto de atributos ($F_i$'s):

$$V(i) = w_1 f_1(i) + w_2 f_2(i) + \ldots + w_n f_n(i)$$

En ajedrez se tienen aproximadamente 10 pesos, por lo que es una compresión bastante significativa.

La compresión lograda por una representación implícita permite al sistema de aprendizaje, generalizar de estados visitados a estados no visitados.

Por otro lado, puede que no exista tal función. Como en todos los sistemas de aprendizaje, existe un balance entre el espacio de hipótesis y el tiempo que toma aprender una hipótesis aceptable.

Muchos sistemas de aprendizaje supervisado tratan de minimizar el error cuadrado (MSE) bajo cierta distribución P de las entradas.

Si $\vec{\Theta}_t$ representa el vector de parámetros de la función parametrizada que queremos aprender:

$$MSE(\vec{\Theta}_t) = \sum_{s \in S} P(s) [V^{\pi(s)} - V_t(s)]^2$$

donde $P(s)$ es una distribución pesando los errores de diferentes estados.

Para ajustar los parámetros del vector de la función que queremos optimizar, las técnicas de gradiente ajustan los valores en la dirección que produce la máxima reducción en el error:

$$\begin{array}{lll} \vec{\Theta}_{t+1} & = & \vec{\Theta}_t -... ...(s_t)} - V_t(s_t)] \nabla_{\vec{\Theta_t}} V_t(s_t) \end{array}$$

donde $\alpha$ es un parámetro positivo $0 \leq \alpha \leq 1$ y $\nabla_{\vec{\Theta_t}} f(\Theta_t)$ denota un vector de derivadas parciales.

Como no sabemos $V^{\pi(s_t)}$ lo tenemos que aproximar. Podemos hacerlo con trazas de elegibilidad y actualizar la función $\Theta$ como sigue:

$$\vec{\Theta}_{t+1} = \vec{\Theta}_t + \alpha \delta_t \vec{e}_t$$

donde $\delta_t$ es el error:

$$\delta_t = r_{t+1} + \gamma V_t(s_{t+1}) - V_t(s_t)$$

y $\vec{e}_t$ es un vector de trazas de elegibilidad, una por cada componente de $\vec{\Theta}_t$, que se actualiza como:

$$\vec{e}_t = \gamma \lambda \vec{e}_{t-1} + \nabla_{\vec{\Theta}_t} V_t(s_t)$$

con $\vec{e}_0 = 0$.