refuerzo aprendizaje.pdf

Capı́tulo 11 Aprendizaje por Refuerzo 11.1 Introducción Uno de los enfoques más usados dentro de aprendizaje es el aprendizaje supervisado a partir de ejemplos (pares entradas – salida provistos por el medio ambiente), para después predecir la salida de nuevas entradas. Cualquier sistema...

Capı́tulo 11 Aprendizaje por Refuerzo 11.1 Introducción Uno de los enfoques más usados dentro de aprendizaje es el aprendizaje supervisado a partir de ejemplos (pares entradas – salida provistos por el medio ambiente), para después predecir la salida de nuevas entradas. Cualquier sistema de predicción puede verse dentro de este paradigma, sin embargo, ignora la estructura secuencial del mismo. En algunos ambientes, muchas veces se puede obtener sólo cierta retroali- mentación o recompensa o refuerzo (e.g., gana, pierde). El refuerzo puede darse en un estado terminal y/o en estados intermedios. Los refuerzos pueden ser componentes o sugerencias de la utilidad actual a maximizar (e.g., buena movida). En aprendizaje por refuerzo (RL) el objetivo es aprender cómo mapear situa- ciones a acciones para maximizar una cierta señal de recompensa. Promesa: programar agentes mediante premio y castigo sin necesidad de especificar cómo realizar la tarea. Diferencias con otro tipo de aprendizaje: 178  Figura 11.1: Aprendizaje por Refuerzo. No se le presentan pares entrada - salida. El agente tiene que obtener experiencia útil acerca de los estados, ac- ciones, transiciones y recompensas de manera activa para poder actuar de manera óptima. La evaluación del sistema ocurre en forma concurrente con el apren- dizaje. En RL un agente trata de aprender un comportamiento mediante interac- ciones de prueba y error en un ambiente dinámico e incierto. En general, al sistema no se le dice qué acción debe tomar, sino que él debe de descubrir qué acciones dan el máximo beneficio. En un RL estandar, un agente está conectado a un ambiente por medio de percepción y acción (ver figura 11.1). En cada interacción el agente recibe como entrada una indicación de su estado actual (s ∈ S) y selecciona una acción (a ∈ A). La acción cambia el estado y el agente recibe una señal de refuerzo o recompensa (r ∈ R). El comportamiento del agente debe de ser tal que escoga acciones que tiendan a incrementar a largo plazo la suma de las recompensas totales. 179  Figura 11.2: Ejemplo de problema. El objetivo del agente es encontrar una polı́tica (π), que mapea estados a acciones que maximice a largo plazo el refuerzo. En general el ambiente es no-determinı́stico (tomar la misma acción en el mismo estado puede dar resultados diferentes). Sin embargo, se asume que el ambiente es estacionario (esto es, las probabil- idades de cambio de estado no cambian o cambian muy lentamente). Aspectos importantes: (i) se sigue un proceso de prueba y error, y (ii) la recompensa puede estar diferida. Otro aspecto importante es el balance entre exploración y explotación. Para obtener buena ganancia uno prefiere seguir ciertas acciones, pero para saber cuáles, se tiene que hacer cierta exploración. Muchas veces depende de cuánto tiempo se espera que el agente interactue con el medio ambiente. La caracterización de esta problemática está dada por procesos de decisión de Markov o MDP. Un MDP modela un problema de decisión sequencial en donde el sistema evoluciona en el tiempo y es controlado por un agente. La dinámica del sistema esta determinada por una función de transición de probabilidad que mapea estados y acciones a otros estados. 180 Formalmente, un MDP es una tupla M =< S, A, Φ, R >. Los elementos de un MDP son: Un conjunto finito de estados S({1,..., n}. Un conjunto finito de acciones A, que pueden depender de cada estado. Función de recompensa (R): define la meta. Mapea cada estado–acción a un número (recompensa), indicando lo deseable del estado. Modelo del ambiente (opcional): imita el comportamiento del ambi- ente. Se puede usar para hacer planeación al considerar posibles situa- ciones futuras basadas en el modelo. Φ : A × S → Π(S) es una función de transición de estados dada como una distribución de probabilidad. La probabilidad de alcanzar el estado s0 ∈ S al realizar la acción a ∈ A en el estado s ∈ S, que se puede denotar como Φ(a, s, s0 ). Polı́tica (π): define cómo se comporta el sistema en cierto tiempo. Es un mapeo (a veces estocástico) de los estados a las acciones. Función de valor (V ): indica lo que es bueno a largo plazo. Es la recompensa total que un agente puede esperar acumular empezando en ese estado (predicciones de recompensas). Se buscan hacer acciones que den los valores más altos, no la recompensa mayor. Las recompensas están dadas por el ambiente, pero los valores se deben de estimar (aprender) en base a las observaciones. Aprendizaje por refuerzo aprende las funciones de valor mientras in- teractua con el ambiente. 11.1.1 Modelos de Comportamiento Óptimo Dado un estado st ∈ S y una acción at ∈ A(st ), el agente recibe una recom- pensa rt+1 y se mueve a un nuevo estado st+1. El mapeo de estados a probabilidades de seleccionar una acción particular es su polı́tica (πt ). Aprendizaje por refuerzo especifica cómo cambiar la polı́tica como resultado de su experiencia. 181 No trata de maximizar la recompensa inmediata, sino la recompensa a largo plazo (acumulada). La recompensa debe de mostrar lo que queremos obtener y se calcula por el ambiente. Si las recompensas recibidas después de un tiempo t se denotan como: rt+1 , rt+2 , rt+3 ,..., lo que queremos es maximizar lo que esperamos recibir de recompensa (Rt ) que en el caso más simple es: Rt = rt+1 + rt+2 + rt+3 +... + rT Si se tiene un punto terminal se llaman tareas episódicas, si no se tiene se llaman tareas continuas. En este último caso, la fórmula de arriba presenta problemas, ya que no podemos hacer el cálculo cuando T no tiene lı́mite. Podemos usar una forma alternativa en donde se van haciendo cada vez más pequeñas las contribuciones de las recompensas más lejanas: ∞ Rt = rt+1 + γrt+2 + γ 2 rt+3 +... = γ k rt+k+1 X k=0 donde γ se conoce como la razón de descuento y está entre: 0 ≤ γ < 1 Si γ = 0 se trata sólo de maximizar tomando en cuenta las recompensas inmediatas. En general, podemos pensar en los siguientes modelos: 1. Horizonte finito: el agente trata de optimizar su recompensa esperada en los siguientes h pasos, sin preocuparse de lo que ocurra despues: h X E( rt ) t=0 donde rt significa la recompensa recibida t pasos en el futuro. Este modelo se puede usar de dos formas: (i) polı́tica no estacionaria: donde en el primer paso se toman los h siguientes pasos, en el siguiente los h − 1, etc., hasta terminar. El problema principal es que no siem- pre se conoce cuántos pasos considerar. (ii) receding-horizon control : siempre se toman los siguientes h pasos. 182  2. Horizonte infinito: las recompensas que recibe un agente son reducidas geométricamente de acuerdo a un factor de descuento γ (0 ≤ γ ≤ 1): ∞ γ t rt ) X E( t=0 3. Recompensa promedio: optimizar a largo plazo la recompensa prome- dio: h 1X limh→∞ E( rt ) h t=0 Problema: no hay forma de distinguir polı́ticas que reciban grandes recompensas al principio de las que no. En general, se utiliza la de horizonte infinito. 11.1.2 Recompensa diferida y modelo Markoviano En general, las acciones del agente determinan, no sólo la recompensa in- mediata, sino también (por lo menos en forma probabilı́stica) el siguiente estado del ambiente. Los problemas con refuerzo diferido se pueden modelar como procesos de decisión de Markov (MDPs). El modelo es Markoviano si las transiciones de estado no dependen de estados anteriores. En aprendizaje por refuerzo se asume que se cumple con la propiedad Marko- viana y las probabilidades de transición están dadas por: a 0 Pss 0 = P r{st+1 = s | st = s, at = a} El valor de recompensa esperado es: Rass0 = E{rt+1 | st = s, at = a, st+1 = s0 } Lo que se busca es estimar las funciones de valor. Esto es, qué tan bueno es estar en un estado (o realizar una acción). 183 La noción de “qué tan bueno” se define en términos de recompensas futuras o recompensas esperadas. La polı́tica π es un mapeo de cada estado s ∈ S y acción a ∈ A(s) a la probabilidad π(s, a) de tomar la acción a estando en estado s. El valor de un estado s bajo la polı́tica π, denotado como V π (s), es el refuerzo esperado estando en estado s y siguiendo la polı́tica π. Este valor esperado se puede expresar como: ( ∞ ) π k X V (s) = Eπ {Rt | st = s} = Eπ γ rt+k+1 | st = s k=o y el valor esperado tomando una acción a en estado s bajo la polı́tica π (Qπ (s, a)): ( ∞ ) π k X Q (s, a) = Eπ {Rt | st = s, at = a} = Eπ γ rt+k+1 | st = s, at = a k=o Las funciones de valor óptimas se definen como: V ∗ (s) = maxπ V π (s) y Q∗ (s, a) = maxπ Qπ (s, a) Las cuales se pueden expresar como las ecuaciones de optimalidad de Bell- man: a a X V ∗ (s) = maxa Pss ∗ 0 0 [Rss0 + γV (s )] s0 y a a X Q∗ (s, a) = Pss ∗ 0 0 [Rss0 + γV (s )] s0 o a a X Q∗ (s, a) = Pss ∗ 0 0 0 [Rss0 + γmaxa0 Q (s , a )] s0 11.2 Métodos de Solución de MDPs Existen tres formas principales de resolver MDPs: (i) usando métodos de pro- gramación dinámica, usando métodos de Monte Carlo, y (iii) usando métodos de diferencias temporales o de aprendizaje por refuerzo. 184 11.2.1 Programación Dinámica Si se conoce el modelo del ambiente, osea las transiciones de probabilidad a a (Pss 0 ) y los valores esperados de recompensas (R ss0 ), las ecuaciones de op- timalidad de Bellman nos representan un sistema de |S| ecuaciones y |S| incognitas. Consideremos primero como calcular la función de valor V π dada una polı́tica arbitraria π. V π (s) = Eπ {Rt | st = s} = Eπ {rt+1 + γrt+2 + γ 2 rt+3 +... | st = s} = Eπ {rt+1 + γV π (st+1 ) | st = s} a a π 0 = a π(s, a) s0 Pss0 [Rss0 + γV (s )] P P donde π(s, a) es la probabilidad de tomar la acción a en estado s bajo la polı́tica π. Podemos hacer aproximaciones sucesivas, evaluando Vk+1 (s) en términos de Vk (s). a a X X 0 Vk+1 (s) = π(s, a) Pss 0 [Rss0 + γVk (s )] a s0 Podemos entonces definir un algoritmo de evaluación iterativa de polı́ticas como se muestra en la tabla 11.1. Una de las razones para calcular la función de valor de una polı́tica es para tratar de encontrar mejores polı́ticas. Dada una función de valor para una polı́tica dada, podemos probar una acción a 6= π(s) y ver si su V (s) es mejor o peor que el V π (s). En lugar de hacer un cambio en un estado y ver el resultado, se pueden con- siderar cambios en todos los estados considerando todas las acciones de cada estado, seleccionando aquella que parezca mejor de acuerdo a una polı́tica greedy. Podemos entonces calcular una nueva polı́tica π 0 (s) = argmaxa Qπ (s, a) y continuar hasta que no mejoremos. 185  Tabla 11.1: Algoritmo iterativo de evaluación de polı́tica. Inicializa V (s) = 0 para toda s ∈ S Repite ∆←0 Para cada s ∈ S v ← V (s) a a V (s) ← a π(s, a) s0 Pss 0 [Rss0 + γV (s ) 0 P P ∆ ← max(∆, |v − V (s)|) Hasta que ∆ < θ (número positivo pequeño) Regresa V ≈ V π Esto sugiere, partir de una polı́tica (π0 ) y calcular la función de valor (V π0 ), con la cual encontrar una mejor polı́tica (π1 ) y ası́ sucesivamente hasta con- verger a π ∗ y V ∗. A este procedimiento se llama iteración de polı́ticas y viene descrito en la tabla 11.2. Uno de los problemas de iteración de polı́ticas es que cada iteración involucra evaluación de polı́ticas que requiere recorrer todos los estados varias veces. Sin embargo, el paso de evaluación de polı́tica lo podemos truncar de varias formas, sin perder la garantı́a de convergencia. Una de ellas es pararla de- spués de recorrer una sola vez todos los estados. A esta forma se le llama iteración de valor (value iteration). En particular se puede escribir combi- nando la mejora en la polı́tica y la evaluación de la polı́tica truncada como sigue: a a X 0 Vk+1 (s) = maxa Pss 0 [Rss0 + γVk (s )] s0 Se puede ver como expresar la ecuación de Bellman en una regla de actual- ización. Es muy parecido a la regla de evaluación de polı́ticas, solo que se evalúa el máximo sobre todas las acciones (ver tabla 11.3). Para espacios muy grandes, el ver todos los estados puede ser computacional- mente muy caro. Una opción es hacer estas actualizaciones al momento de 186  Tabla 11.2: Algoritmo de iteración de polı́tica. 1. Inicialización: V (s) ∈ R y π(s) ∈ A(s) arbitrariamente ∀s ∈ S 2. Evaluación de polı́tica: Repite ∆←0 Para cada s ∈ S v ← V (s) π(s) π(s) V (s) ← s0 Pss0 [Rss0 + γV (s0 )] P ∆ ← max(∆, |v − V (s)|) Hasta que ∆ < θ (número positivo pequeño) 3. Mejora de polı́tica: pol-estable ← true Para cada s ∈ S: b ← π(s) a a π(s) ← argmaxa s0 Pss 0 [Rss0 + γV (s )] 0 P if b 6= π, then pol-estable ← false If pol-estable, then stop, else go to 2. Tabla 11.3: Algoritmo de iteración de valor. Inicializa V (s) = 0 para toda s ∈ S Repite ∆←0 Para cada s ∈ S v ← V (s) a a V (s) ← maxa s0 Pss 0 [Rss0 + γV (s ) ∗ 0 P ∆ ← max(∆, |v − V (s)|) Hasta que ∆ < θ (número positivo pequeño) Regresa una polı́tica determinı́stica tal que: a a π(s) = argmaxa s0 Pss 0 [Rss0 + γV (s )] ∗ 0 P 187  Tabla 11.4: Algoritmo de Monte Carlo para estimar V π. Repite Genera un episodio usando π Para cada estado s en ese episodio: R ← recompensa después de la primera ocurrencia de s Añade R a recomp(s) V (s) ← promedio(recomp(s)) estar explorando el espacio, y por lo tanto determinando sobre qué estados se hacen las actualizaciones. El hacer estimaciones en base a otras estimaciones se conoce también como bootstrapping. 11.2.2 Monte Carlo Los métodos de Monte Carlo, solo requieren de experiencia y la actualización se hace por episodio más que por cada paso. El valor de un estado es la recompensa esperada que se puede obtener a partir de ese estado. Para estimar V π y Qπ podemos tomar estadı́sticas haciendo un promedio de las recompensas obtenidas. El algoritmo para V π está descrito en la tabla 11.4. Para estimar pares estado-acción (Qπ ) corremos el peligro de no ver todos los pares, por lo que se busca mantener la exploración. Lo que normalmente se hace es considerar solo polı́ticas estocásticas que tienen una probabilidad diferente de cero se seleccionar todas las acciones. Con Monte Carlo podemos alternar entre evaluación y mejoras en base a cada episodio. La idea es que después de cada episodio las recompensas observadas se usan para evluar la polı́tica y la polı́tica se mejora para todos los estados visitados en el episodio. El algoritmo viene descrito en la tabla 11.5. 188  Tabla 11.5: Algoritmo de Monte Carlo. Repite Genera un episodio usando π con exploración Para cada par s, a en ese episodio: R ← recompensa después de la primera ocurrencia de s, a Añade R a recomp(s, a) Q(s, a) ← promedio(recomp(s, a)) Para cada s en el episodio: π(s) ← argmaxa Q(s, a) Existen dos formas para asegurar que todas las acciones pueden ser selec- cionadas indefinidamente: Los algoritmos on-policy: Estiman el valor de la polı́tica mientras la usan para el control. Se trata de mejorar la polı́tica que se usa para tomar decisiones. Los algoritmos off-policy: Usan la polı́tica y el control en forma sep- arada. La estimación de la polı́tica puede ser por ejemplo greedy y la polı́tica de comportamiento puede ser -greedy. Osea que la polı́tica de comportamiento está separada de la polı́tica que se quiere mejorar. Esto es lo que hace Q-learning, lo cual simplifica el algoritmo. Ejemplos de polı́ticas de selección de acciones son: −greedy: en donde la mayor parte del tiempo se selecciona la acción que da el mayor valor estimado, pero con probabilidad  se selecciona una acción aleatoriamente. softmax, en donde la probabilidad de selección de cada acción depende de su valor estimado. La más común sigue una distribución de Boltz- mann o de Gibbs, y selecciona una acción con la siguiente probabilidad: eQt (a)/τ Pn Qt (b)/τ b=1 e 189  donde τ es un parámetro positivo (temperatura). 11.2.3 Diferencias Temporales (Temporal Difference) Los métodos de TD combinan las ventajas de los dos anteriores: permite hacer bootstrapping (como DP) y no requiere tener un modelo del ambiente (como MC). Métodos tipo TD sólo tienen que esperar el siguiente paso. TD usan el error o diferencia entre predicciones sucesivas (en lugar del error entre la predicción y la salida final) aprendiendo al existir cambios entre predicciones sucesivas. Ventajas: Incrementales y por lo tanto fáciles de computar. Convergen más rápido con mejores predicciones. El más simple TD(0) es: V (st ) ← V (st ) + α [rt+1 + γV (st+1 ) − V (st )] El algoritmo de TD(0) viene descrito en la tabla 11.6. La actualización de valores tomando en cuenta la acción serı́a: Q(st , at ) ← Q(st , at ) + α[rt+1 + γQ(st+1 , at+1 ) − Q(st , at )] y el algoritmo es prácticamente el mismo, solo que se llama SARSA, y viene descrito en la tabla 11.7. Uno de los desarrollos más importantes en aprendizaje por refuerzo fué el desarrollo de un algoritmo “fuera-de-polı́tica” (off-policy) conocido como Q- learning. 190  Tabla 11.6: Algoritmo TD(0). Inicializa V (s) arbitrariamente y π a la polı́tica a evaluar Repite (para cada episodio): Inicializa s Repite (para cada paso del episodio): a ← acción dada por π para s Realiza acción a; observa la recompensa, r, y el siguiente estado, s0 V (s) ← V (s) + α [r + γV (s0 ) − V (s)] s ← s0 hasta que s sea terminal Tabla 11.7: Algoritmo SARSA. Inicializa Q(s, a) arbitrariamente Repite (para cada episodio): Inicializa s Selecciona una a a partir de s usando la polı́tica dada por Q (e.g., –greedy) Repite (para cada paso del episodio): Realiza acción a, observa r, s0 Escoge a0 de s0 usando la polı́tica derivada de Q Q(s, a) ← Q(s, a) + α [r + γQ(s0 , a0 ) − Q(s, a)] s ← s0 ; a ← a0 ; hasta que s sea terminal 191  Tabla 11.8: Algoritmo Q-Learning. Inicializa Q(s, a) arbitrariamente Repite (para cada episodio): Inicializa s Repite (para cada paso del episodio): Selecciona una a de s usando la polı́tica dada por Q (e.g., –greedy) Realiza acción a, observa r, s0 Q(s, a) ← Q(s, a) + α [r + γmax0a Q(s0 , a0 ) − Q(s, a)] s ← s0 ; hasta que s sea terminal La idea principal es realizar la actualización de la siguiente forma (Watkins, 89): Q(st , at ) ← Q(st , at ) + α[rt+1 + γmaxa Q(st+1 , at+1 ) − Q(st , at )] El algoritmo viene descrito en la tabla 11.8. 11.3 Trazas de Elegibilidad (eligibility traces) Están entre métodos de Monte Carlo y TD de un paso. Los métodos Monte Carlo realizan la actualización considerando la secuencia completa de recompensas observadas. La actualización de los métodos de TD la hacen utilizando únicamente la siguiente recompensa. La idea de las trazas de elegibilidad es considerar las recompensas de n es- tados posteriores (o afectar a n anteriores). Si recordamos: Rt = rt+1 + γrt+2 + γ 2 rt+3 +... + γ T −t−1 rT 192 Lo que se hace en TD es usar: Rt = rt+1 + γVt (st+1 ) lo cual hace sentido porque Vt (st+1 ) reemplaza a los términos siguientes (γrt+2 + γ 2 rt+3...). Sin embargo, hace igual sentido hacer: Rt = rt+1 + γrt+2 + γ 2 Vt (st+2 ) y, en general, para n pasos en el futuro. En la práctica, más que esperar n pasos para actualizar (forward view ), se realiza al revés (backward view ). Se guarda información sobre los estados por los que se pasó y se actualizan hacia atrás las recompensas (descontadas por la distancia). Se puede probar que ambos enfoques son equivalentes. Para implementar la idea anterior, se asocia a cada estado o par estado-acción una variable extra, representando su traza de elegibilidad (eligibility trace) que denotaremos por et (s) o et (s, a). Este valor va decayendo con la longitud de la traza creada en cada episodio. La figura 11.3 muestra este comportamiento. Para T D(λ): ( γλet−1 (s) si s 6= st et (s) = γλet−1 (s) + 1 si s = st Para SARSA se tiene lo siguiente: ( γλet−1 (s, a) si s 6= st et (s, a) = γλet−1 (s, a) + 1 si s = st El algoritmo para SARSA(λ) viene descrito en la tabla 11.9. Para Q-learning como la selección de acciones se hace, por ejemplo, sigu- iendo una polı́tica −greedy, se tiene que tener cuidado, ya que a veces los movimientos, son movimientos exploratorios. 193  Figura 11.3: Comportamiento de las trazas de elegibilidad. Tabla 11.9: SARSA(λ) con trazas de elegibilidad. Inicializa Q(s, a) arbitrariamente y e(s, a) = 0 ∀s, a Repite (para cada episodio) Inicializa s, a Repite (para cada paso en el episodeo) Toma acción a y observa r, s0 Selecciona a0 de s0 usando una polı́tica derivada de Q (e.g., −greedy) δ ← r + γQ(s0 , a0 ) − Q(s, a) e(s, a) ← e(s, a) + 1 Para todos s, a Q(s, a) ← Q(s, a) + αδe(s, a) e(s, a) ← γλe(s, a) s ← s0 ; a ← a0 hasta que s sea terminal 194 Aquı́ se puede mantener historia de la traza solo hasta el primer movimiento exploratorio, ignorar las acciones exploratorias, o hacer un esquema un poco más complicado que considera todas las posibles acciones en cada estado. 11.4 Planeación y Aprendizaje Asumamos que tenemos un modelo del ambiente, esto es, que podemos pre- decir el siguiente estado y la recomepensa dado un estado y una acción. La predicción puede ser un conjunto de posibles estados con su probabil- idad asociada o pouede ser un estado que es muestreado de acuerdo a la distribución de probabilidad de los estados resultantes. Dado un modelo, es posible hacer planificación. Lo interesante es que pode- mos utilizar los estados y acciones utilizados en la planificación también para aprender. De hecho al sistema de aprendizaje no le importa si los pares estado-acción son dados de experiencias reales o simuladas. Dado un modelo del ambiente, uno podrı́a seleccionar aleatoriamente un par estad-acción, usar el modelo para predecir el siguiente estado, obtener una recompensa y actualizar valores Q. Esto se puede repetir indefinidamente hasta converger a Q∗. El algoritmo Dyna-Q combina experiencias con planificación para aprender más rápidamente una polı́tica óptima. La idea es aprender de experiencia, pero también usar un modelo para simular experiencia adicional y ası́ aprender más rápidamente (ver tabla 11.10). El algoritmo de Dyna-Q selecciona pares estado-acción aleatoriamente de pares anteriores. Sin embargo, la planificación se puede usar mucho mejor si se enfoca a pares estado-acción especı́ficos. Por ejemplo, enfocarnos en las metas e irnos hacia atrás o más generalmente, irnos hacia atrás de cualquer estado que cambie su valor. Los cambios en las estimaciones de valor V o Q pueden cambiar, cuando se está aprendiendo o si el ambiente cambia y un valor estimado deja de ser 195  Tabla 11.10: Algoritmo de Dyna-Q. Inicializa Q(s, a) y M odelo(s, a) ∀s ∈ S, a ∈ A DO forever s ← estado actual a ← −greedy(s, a) reaiza acción a onserva s0 y r Q(s, a) ← Q(s, a) + α[r + γmaxa0 Q(s0 , a0 ) − Q(s, a)] M odelo(s, a) ← s0 , r Repite N veces: s ← estado anterior seleccionado aleatoriamente a ← acción aleatoria tomada en s s0 , r ← M odelo(s, a) Q(s, a) ← Q(s, a) + α[r + γmaxa0 Q(s0 , a0 ) − Q(s, a)] cierto. Lo que se puede hacer es enfocar la simulación al estado que cambio su valor. Esto nos lleva a todos los estados que llegan a ese estado y que también cambiarı́an su valor. Esto proceso se puede repetir sucesivamente, sin embargo, algunos estados cambian mucho más que otros. Lo que podemos hacer es ordenarlos y cam- biar solo los que rebacen un cierto umbral. Esto es precisamente lo que hacer el algoritmo de prioritized sweeping (ver tabla 11.11). 11.5 Generalización en Aprendizaje por Re- fuerzo 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 fun- ciona para epacios pequeños, pero es impensable para dominios como ajedrez (10120 ) o backgammon (1050 ). 196  Tabla 11.11: Algoritmo de Prioritized sweeping. Inicializa Q(s, a) y M odelo(s, a) ∀s ∈ S, a ∈ A y ColaP = ∅ DO forever s ← estado actual a ← −greedy(s, a) reaiza acción a onserva s0 y r M odelo(s, a) ← s0 , r p ←| r + γmaxa0 Q(s0 , a0 ) − Q(s, a) | if p > θ, then inserta s, a a ColaP con prioridad p Repite N veces, mientras ColaP 6= ∅: s, a ← primero(ColaP ) s0 , r ← M odelo(s, a) Q(s, a) ← Q(s, a) + α[r + γmaxa0 Q(s0 , a0 ) − Q(s, a)] Repite ∀s, a que se predice llegan a s: r ← recomensa predicha p ←| r + γmaxa Q(s, a) − Q(s, a) | if p > θ, then inserta s, a a ColaP con prioridad p 197 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 (Fi ’s): V (i) = w1 f1 (i) + w2 f2 (i) +... + wn fn (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. ~ t representa el vector de parámetros de la función parametrizada que Si Θ queremos aprender: ~ t) = P (s)[V π(s) − Vt (s)]2 X M SE(Θ s∈S 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: ~ t+1 = Θ ~ t − 1 α∇ ~ [V π(st ) − Vt (st )]2 Θ 2 Θt = ~ Θt − α[V π(st ) − Vt (st )]∇Θ~t Vt (st ) donde α es un parámetro positivo 0 ≤ α ≤ 1 y ∇Θ~t f (Θt ) denota un vector de derivadas parciales. Como no sabemos V π(st ) lo tenemos que aproximar. Podemos hacerlo con trazas de elegibilidad y actualizar la función Θ como sigue: ~ t+1 = Θ Θ ~ t + αδt~et 198 donde δt es el error: δt = rt+1 + γVt (st+1 ) − Vt (st ) ~ t, y ~et es un vector de trazas de elegibilidad, una por cada componente de Θ que se actualiza como: ~et = γλ~et−1 + ∇Θ ~ t Vt (st ) con ~e0 = 0. 11.6 Aplicaciones a Juegos y Control La primera aplicación en aprendizaje por refuerzo fué el programa para jugar damas de Samuel. Usó una función lineal de evaluación con pesos usando hasta 16 términos. Su programa era parecido a la ecuación de actualización de pesos, pero no usaba recompensa en los estados terminales. Esto hace que puede o no converger y puede aprender a perder. Logró evitar ésto haciendo que el peso para ganancia de material fuera siem- pre positivo. Se han hecho aplicaciones a control de robots. Una de las más conocidas es el control del péndulo invertido. Controlar la posición x para que se mantenga aproximadamente derecho (θ ≈ π/2), manteniendose en los lı́mites de la pista. X, θ, Ẋ y θ̇ son continuas. El control es de tipo bang–bang. Boxes (Michie, Chambers ’68) balanceaba el pendulo por más de una hora después de 30 intentos (no simulado). Idea: discretizar el espacio en cajas. Se corria el sistema hasta que se caı́a el péndulo o se salia de los lı́mites. Entonces se daba un refuerzo negativo a la última “caja” y se propagaba a la secuencia de “cajas” por las que pasó. Sin embargo, los resultados más impresionantes (un péndulo invertido triple) se lograron derivando un algoritmo con teorı́a de control clásica (simulado). TD-gammon (Tesauro ’92) ilustra la potencialidad de técnicas de aprendizaje por refuerzo. Tesauro primero trató de aprender Q(s, a) directamente con una red neuronal (Neurogammon) con poco éxito. Después representó una 199 función de evaluación con una sola capa intermedia con 40 nodos. Después de 200,000 juegos de entrenamiento mejoró notablemente su desempeño. Añadiendo atributos adicionales a una red con 80 nodos escondidos, después de 300,000 juegos de entrenamiento, juega como los 3 mejores jugadores del mundo. Recientemente (2000), se desarrolló un algoritmo de RL que actualiza las funciones de evaluación en un árbol de búsqueda en juegos (TDLeaf(λ). Aplicado a ajedrez, mejora el puntaje de un programa (KnightCap) de 1,650 a 2,150 después de 308 juegos en 3 dı́as. 11.7 Algunos desarrollos recientes Uno de los problemas principales de las técnicas usadas en aprendizaje por refuerzo, y para resolver MDP en general, es la aplicación a espacios grandes (muchos estados y acciones). Aunque el algoritmo converge en teorı́a, en la práctica puede tomar un tiempo inaceptable. Dentro de los enfoques que atacan, en parte, esta problemática, podemos mencionar: Agregación de estados, en donde se juntan estados “parecidos” y a todos ellos se les asigna el mismo valor, reduciendo con esto el espacio de estados. Algunos ejemplos de esto son: tile-coding, coarse coding, radial basis functions, Kanerva coding, y soft-state aggregation. Abstracciones basadas en máquinas de estado finito, en donde el apren- dizaje por refuerzo tiene que decidir que máquina utilizar (por ejemplo, HAM y PHAM). Definición de jerarquı́as, en donde se divide el espacio en subproblemas, se aprenden polı́ticas a los espacios de más bajo nivel y estas se usan para resolver problemas de más alto nivel (e.g., MAXQ, HEXQ). Algo parecido se usa con Macros y Options, en donde se aprenden polı́ticas de subespacios que se usan para resolver problemas mas grandes. 200  Otra opción es utilizar un sistema de planificación que decida la se- cuencias de submetas que se tienen que cumplir para resolver cierto problema (por ejemplo usando TOPs) y después aprender por apren- dizaje por refuerzo las acciones a realizar para resolver cada submeta (e.g., RL-TOP). También se ha buscado utilizar representaciones relacionales dentro de aprendizaje por refuerzo, ya sea para representar las funciones de valor y/o para representar los estados y las acciones. También se han utilizado soluciones conocidas como guı́as o trazas que se usan para aprender más rápidamente las funciones de valor o para aprender un subconjunto de acciones relevantes. 201