Recordemos que es la funicon de valor de estado bajo la política , y la funcion de valor de acción es , existe un número de estados/acciones y se puede guardar v(s) o q(s,a) en una tabla.
En RL el tamaño de un problema está determinado principalmente por su espacio de estados (y tambien acciones.)
Con ejemplos de Silver sencillos, de <10 estados podía hacer una tabla, para cada estado s, guardaba un número V(s) o para cada par guardaba . Pero para ejemplos como Go es tan grande que si ocuparamos 1 byte por estado se necesitarian bytes TB, lo cual es imposiblel, y en escenarios como el ejemplo del helicoptero, los etsados son infinitos, tenemos el peor de los casos.
Silver ilistraba ejemplos de lookup table, que basicamente es una tabla, tienes un indice por estados s, y ahí guardas un número , y si trabajas con una entrada por par (s,a). Formalmente esto es una función , no hay estructura, cada valor de estado es independiente.
Es correcto usar esto cuando el numero de estados es pequeño.
Necesitamos aprovechar estructura y similitud entre estados, como estados "parecidos“ deberían tener valores parecidos, aquí es donde entra la aproximación de funciones.
Idea central: en lugar de tener una tabla sin estructura, modelamos la funcion de valor como una función parametrizada.
o , donde w es un vector de parámetros (pesos). pudiendo ser un vector de pesos de un modelo lineal, todos los pesos de una red neuronal, parámetros de un árbol de desicicon, etc.
En lugar de guardar un número independiente para cada estado, aprendes una fórmula general de parámetros w que te da un valor para cualquier estado, ganando así una generalización. Debemos minimizar el error de la predicción
Gradient Descent
Sea una funcion diferenciable de el vector de parámetros . Definimos el gradiente como:
para encontrar un mínimo local de , ajustamos w en la dirección del gradiente negativo donde es el step-size (taza de aprendizaje).
Como queremos minimizar , así que no queremos ir hacia donde crece, si no hacia donde disminuye, usando aproximacón de tylor llegamos a:
el es una convención que podriua ser absorbida por
Stochastic Gradient Descent
Definimos la función de costos
Donde es la aproximación paramétrica con pesos , y es el valor verdadero del estado S bajo la politica (no lo conocemos, pero imaginemos que sí). error cuadrático medio entre y
Sea
Usamos que la derivada de una esperanza es la esperanza de la derivada:
Para derivar el cuadrado usamos regla de la cadena:
Sea (el error)
Ahora calculamos no depende de w su gradiente es 0
Como si depende de w
Metemos eso a la esperanza:
sacamos el −2
Esto es el gradiente completo.
Hasta ahora necesitamos calcular la esperanza, es decir promediar todoso los estados según su probabilidad, eso es caro o imposble de hacer, entonces usamos la idea de stochastic gradient descent (SGD en vez de usar la esperanza completa, usamos una muestra.
Aquí SGD es una aproximación “no sesgada” del gradiente.
Feature Vectors
Representamos el estado por un vector de características En vez de trabajar con la representación “cruda”, definimos un vector de características , donde cada es una función del estado que extrae información relevante.
¿Cómo usamos estas caractiristicas?
Representamos la función de valor mediante una combinación lineal de características, ese número será la predicción del valor
simplemente es un producto punto, cada caracteristica dice algo sobre el estado, el peso indica cuánto aporta esa característica al valor total.
Derivamos
Recordemos que
sustituyendo en el gradiente:
Supongamos que hay un número finito de estados: Silver define donde 1(⋅) es la función indicadora, entonces si S =
un vector one-hot, todo 0, exepto 1 en la posición k.
Usando el modelo líneal con estas features , si
Incremental Prediction Algorithms
Hasta ahora asumiamos que teníamos como “etiqueta correcta”, en RL no tenemos ; solo recompensas, entonces usamos un target (una estimación)
Targets:
para Monte Carlo (MC):
El caso de MC solo toma el caso particular Target = , y en el caso líneal así que finalmente
Para TD(0):
Para una política fija , el valor verdadero en el estdado es , definimos el target de paso: TD-targe = toma el valor de la recompensa inmediata mas el valor descontado del siguiente estado segun mi propia aproximación esto viene con error
Para TD()
Queremos algo intermedioentre TD(0) Y MC, sea donde cada es un return de n pasos que mira recopensas y luego bootstrtap con , por eso decimos que tambien es sesgado, por que cada suele usar al final y ahí entra el sesgo de aproximación.
Aquí encontramos un error normal que definimos como
Si la realidad fue mejor que lo que esperabas tus valores están demasiado bajos.
Si la realidad fue pero tus valores están demasiado altos.
esto define la traza de elegebilidad , que es un vector del mismo tamaño que .
es la traza en el paso anterior, multiplicas por y esto desvance la Contribución de estados viejos, luego sumamos el estado actual entra con peso 1, digamos que guarda un recuerdo borroso que ha sido visitado recientemente. Cuanto mas reciente un estado, mayor peso tiene su caracteristica en
es la regla de actualización, tomas el TD- error actual, lo multiplicas por la traza que reparte el error entre los estados recientes y escalas por y este es el ca,bio de
Note que todos tienen la misma forma
Action-Value Function Approximation
antes habiamos aproximado la función de valor de estadpo , ahora queremos aproximar la función de valor de accion , el valor esperado de empezar en s y tomar la acción a, y luego swguir la política .
Esto es analogo a lo que haciamos con , tenemos nuestra función objetivo
, donde (S,A) son los pares que vemos siguiendo la politica , y el objetivo es minimizar el error cuadrático medio entre el valor verdadero y nuestras aproximación
Sigueindo con lo mismo derivando usando regla de la cadena
lo que es update = step-size × (error de predicción) × (gradiente de la predicción)
Nuevamente como no conocemos el valor exacato de , lo sustituimos por un target TD o MC.
Analogamente antes teníamos x(S) para estados, ahora queremos aproximar q(S,A) así que las features dependen del par (estado, acción), es la i-ésima característica numérica del par (S,A).
Sea , donde puede ser ppr ejemplo la posición de un catto si tomas la acción A.
Representamos el action-vlaue por la combinación líneal de las características: que es exactamente lo mismo que hicimos para , solo que ahora con (S,A)
El gradiente igual que antes es el vector de features
Ahora tomamos esa formula y como en predicción la adaptamos a MC, TD, y TD(), pero para q-funciones.
Para MC
Para TD(O)
Donde tenemos un error TD:
Para TD()
Error TD
Traza de elegibilidad Guarda en memoria borrosa de qué pares (S,A) han sudo visitados recientemente, los va desvaneciendo con el tiempo.
Con esto hace paso a paso y en línea lo mismo que haría el fowaard view de TD() con action-values.