APRENDIZAJE: Conjunto de procesos que permiten cambios adaptativos del comportamiento de un animal o del hombre (¿o máquina?) como consecuencia de experiencias exteriores.

REFUERZO: Se entiende por refuerzo un estímulo que modifica un reflejo condicionado o una conducta aprendida aumentando su arraigo (refuerzo positivo o premio) o disminuyéndolo (refuerzo negativo o castigo).

Se llama condicionamiento clásico a la creación de una conexión entre un estímulo nuevo y un reflejo ya existente. De manera más concreta, un estímulo originalmente neutro con relación a una respuesta llega a poderla provocar gracias a la conexión asociativa de este estímulo con el estímulo que normalmente provoca esta respuesta.

Como ejemplo de esto anterior, veremos el conocido caso del "perro de Pavlov": Pavlov estudió la relación entre estímulos y reacciones de las glándulas salivares. El experimento consistía en investigar las condiciones que provocaban un reflejo condicionado. Según Pavlov, cualquier estímulo que antes no provocaba la respuesta de secreción salivar, como por ejemplo un sonido, cuando se presentaba repetidamente con un intervalo muy pequeño antes de presentar la comida llegaba un momento que provocaba por sí solo la secreción de saliva, sin necesidad de presentación de la comida.

Ya en términos de Inteligencia Artificial, el aprendizaje basado en ejemplos usará un conjunto de ejemplos con la forma (entrada_i, salida_i) para entrenar al sistema. Cuando se reciba una entrada_n el sistema obtendrá mediante los ejemplos de entrenamiento una salida_n.

En cuanto al condicionamiento operante, podemos decir que se trata de un aprendizaje por relación de un estímulo con una respuesta. La respuesta puede hacer dos cosas: reforzar, con lo que se aumentaría la posibilidad de esa respuesta, o castigar, que disminuiría esta probabilidad. El siguiente ejemplo viene a ilustrar lo anterior: se utilizaron jaulas en las cuales se colocaba un animal. Éste debía manipular un resorte para salir y conseguir la comida que se colocaba en el exterior. Se descubrió que existía una correlación entre el número de veces que se metía el animal en la jaula y la rapidez con la que el animal abría la puerta y conseguía la comida. Es decir, se producía una conexión estímulo-respuesta, en contraste a la conexión estímulo-estímulo del condicionamiento clásico.

De nuevo en el contexto de la Inteligencia Artificial, el aprendizaje por refuerzo permite mejorar el comportamiento de un sistema frente a un problema en base a una señal que indica si la realización de este comportamiento ha sido adecuada o no para resolver el problema. Esta señal es la que llamaremos refuerzo.

Un claro ejemplo de la presencia del condicionamiento operante, o aprendizaje por refuerzo, en el mundo real es el origen de las supersticiones. Parece ser que el comportamiento supersticioso es consecuencia de premios o castigos de los que no conocemos la causa. El hombre busca la posible causa en sucesos recientes y las convierte en superstición.

El objetivo del aprendizaje por refuerzo es usar el premio-castigo para aprender una función de agente satisfactoria, la cual permitirá tomar decisiones en el futuro de qué acción tomar a partir de una percepción del entorno.

La función de agente utiliza la información contenida en una tabla para realizar la toma de decisiones. De ahí el nombre de Aprendizaje por Refuerzo en Tablas. En este contexto, entenderemos por aprendizaje la modificación de esta tabla.

Existen, no obstante, otros formalismos para aprender mediante refuerzo qué acción realizar en cada caso, como por ejemplo las Redes Neuronales. En este caso, las situaciones no se almacenan en una tabla sino en una red. Desgraciadamente, la investigación del desarrollo de algoritmos de aprendizaje por refuerzo en redes neuronales está poco avanzada, de forma que no existen modelos matemáticos conocidos que permitan resolver el problema óptimamente.

La señal de refuerzo puede ser inmediata o retardada. Inmediata es cuando se obtiene una crítica para cada acción efectuada justo después de su realización. La información aportada por el refuerzo en este caso es local a cada acción tomada. Por el contrario, en el caso del refuerzo retardado se dará cuando éste no se obtiene inmediatamente después de la realización de cada acción, sino al completar la secuencia de acciones empleadas para resolver el problema. En este caso, el refuerzo obtenido es una estimación global del comportamiento.

Una condición para poder aplicar el aprendizaje por refuerzo basado en tablas para resolver un problema es que éste sea modelizable mediante cadenas de Markov: la acción a escoger en una situación dada depende únicamente de esta situación y no del camino que se ha realizado para llegar a ella.

Procesos estocásticos: procesos en los que se estudia la interdependencia y el comportamiento límite de un conjunto de variables aleatorias (variable cuyos valores se toman de forma aleatoria, es decir, de acuerdo con una distribución de probabilidad). O sea, cada vez que observamos un proceso que se desarrolla en el tiempo de forma controlada mediante leyes probabilísticas, estamos ante un proceso estocástico. Se puede considerar la parte dinámica de la teoría de probabilidades.

Un ejemplo claro sería la estimación de las condiciones meteorológicas que se darán en días venideros. A partir de fenómenos de observación empíricos, se crea un proceso estocástico que daría lugar a un modelo probabilístico.

Nos ceñiremos a procesos discretos, es decir, procesos que son observados en tiempos discretos.

Proceso de Markov: es un caso particular de los procesos estocastícos en los que el valor de una variable aleatoria determinada en un momento dado (n) sólo depende del estado anterior, es decir, del valor de dicha variable en el instante n-1 y no de los otros estados anteriores. Es lo que en estadística se conoce como sistema sin memoria.

Ejemplo claro de proceso markoviano sería el juego del tres en raya en el que la decisión de mover una determinada ficha, sólo depende de la configuración actual del tablero (estado) y no del conjunto de moviomientos anteriores que he realizado.

Una cadena o proceso de Markov de parámetro discreto se puede representar mediante una matriz (grafo) de probabilidades, en la que las filas y columnas representan los estados (que pueden ser infinitos) y cada elemento de la matriz sería la probabilidad de ir del estado i al estado j en un solo paso. Si el número de valores posibles que puede tomar la variable aleatoria es finito e igual a k, entonces la matriz es finita y de orden k.

En esta matriz se debe de cumplir que:

P_i,j(n-(n+1)) ³ 0 , para todo i, j

S _k p_j,k(n-(n+1)) = 1, para todo j

Por tanto, para calcular la probabilidad de ir del estado i al estado j en pasos, habría que hacer la multiplicación de las matrices de probabilidades de un solo paso.

Cuando el número de estados es infinito o suficientemente grande, es más difícil calcular analíticamente las probabilidades de transición entre estados.

Desde el punto de vista que nos interesa, podemos representar los problemas mediante un conjunto de nodos y un conjunto de aristas dirigidas. Cada nodo representa una situación, que viene dada por un estado y un refuerzo asociado, y cada arista representa una acción que nos lleva de una situación a otra.

En este marco se dice que el problema es markoviano si la arista a escoger desde cada nodo para maximizar el refuerzo recibido no depende de las acciones anteriores tomadas, sino solamente del nodo y de la información de la que disponemos en él.

Se estudiará a partir de ahora la evolución de las cadenas de Markov en el tiempo.

Un estado k es accesible desde un estado j si existe N Î Z, N ³ 1, tal que p_j,k(N) > 0. Dos estados j y k se comunican si j es accesible desde k y k es accesible desde j (j « k).

Se define una clase comunicante de un estado j C(j) como el resultado de todos los estados k que comunican con j. Si C(j) es vacío, se dice que j es un estado sin retorno.

Dadas dos clases comunicantes en una cadena de Markov, o bien son iguales, o bien son disjuntas (en este caso, serían no coherentes).

Se puede escribir una cadena de Markov como la unión de una serie de clases comunicantes no coherentes.

Hay que tener cuidado con los conjuntos de estados cerrados, es decir, aquellos en los que desde ningún estado interno al conjunto es accesible ningún estado externo.

Cadena de Markov irreducible: si todos los pares de estados de la cadena se comunican, por tanto la cadena estará formada exactamente por una sola clase comunicante.

Definimos al agente como el aprendiz encargado de observar su entorno para recoger información que le permita modificar su comportamiento para así aprender a resolver un determinado problema. Como dijimos anteriormente, el objetivo del aprendizaje por refuerzo es la utilización de las recompensas para la obtención de una función de agente. Por tanto nuestro agente será una función que, recibiendo como entrada una percepción del entorno, devolverá la acción siguiente a realizar.

Entendemos el entorno (o ambiente) como el grafo de estados que representa al problema.

Distinguimos dos tipos posibles de agente:

• El agente pasivo sólo se limitará a observar el entorno y recopilar información sobre los refuerzos. No toma decisiones sobre la siguiente acción a realizar, sino que ésta será siempre la misma: seguir observando el entorno según éste evoluciona por sí mismo.

• El agente activo además de recoger información del entorno utilizará ésta para tomar decisiones sobre la siguiente acción a realizar.

El entorno, a su vez, puede ser de dos tipos:

• Entorno accesible: el agente ve el grafo completo del problema, incluyendo las probabilidades de cada transición.

• Entorno inaccesible: el agente sólo ve el estado actual donde se encuentra, y debe crearse un modelo del entorno guardando información sobre los estados visitados con anterioridad.

Vamos a diferenciar entre dos formas posibles de organizar la información que recoge el agente en las tablas:

• Función de utilidad: el agente la emplea para escoger aquellas acciones que permitan maximizar la utilidad esperada de sus resultados. El agente que desea aprender funciones de utilidad debe disponer de un modelo del ambiente, lo que le permitirá tomar decisiones, ya que debe saber los estados a los que le conducirán sus acciones.

• Función de acción-valor: expresa la utilidad esperada cuando el agente emprende una acción en un estado determinado. A esta forma de trabajar se le conoce como Q-learning. El agente que aprende una función de acción-valor no tiene necesidad de contar con el modelo de ambiente. Por lo tanto, puede ser más fácil diseñar aprendices de acción-valor en lugar de aprendices de utilidades. Por otra parte, puesto que ignoran a dónde les llevarán sus acciones, no pueden anticiparse, lo que restringe considerablemente su capacidad para aprender.

Empezaremos viendo los agentes que aprenden funciones de utilidad ya que han sido estudiados desde los comienzos de este campo de la Inteligencia Artificial.

En el aprendizaje pasivo, el entorno genera las transiciones y el agente las percibe. Por ejemplo, consideremos a un agente que intenta aprender las utilidades de los estados del siguiente grafo:

El entorno proporciona información sobre las probabilidades de cada transición almacenadas en la matriz Mij, que expresa la probabilidad de que se produzca una transición del estado i al j. Puesto que el aprendiz es pasivo, el ambiente nos proporciona una serie de secuencias de entrenamiento. En cada una de ellas, el agente experimenta una secuencia de transiciones de estados hasta llegar a uno de los estados terminales (4,2) ó (4,3) en donde recibe un refuerzo. Ejemplos de secuencias de entrenamiento son:

(1,1)-> (1,2)-> (1,3)-> (1,2)-> (1,3)-> (1,2)-> (1,1)-> (2,1)-> (3,1)-> (4,1)-> (4,2) -1

(1,1)-> (2,1)-> (3,1)-> (2,1)-> (1,1)-> (1,2)-> (1,3)-> (2,3)-> (3,3)-> (4,3) +1

(1,1)-> (1,2)-> (1,3)-> (2,3)-> (3,3)-> (4,3) +1

...

El objetivo es utilizar la información de las recompensas para aprender la utilidad esperada Ui que se asocia a cada estado no terminal i. Para simplificar, consideraremos que la utilidad esperada de una secuencia es la suma de las recompensas acumuladas en los estados de la secuencia.

El esqueleto de una función de agente de aprendizaje por refuerzo pasivo es el siguiente:

El agente recibe una percepción (e) que identifica a un estado y actualizará la utilidad de los estados de la secuencia. El elemento clave del aprendizaje por refuerzo está en el algoritmo para actualizar los valores almacenados en las tablas.

Se trata de un sencillo método para actualizar las estimaciones de utilidad basado en el promedio de mínimos cuadrados (PMC). Al término de cada una de las secuencias de entrenamiento, el algoritmo calcula la recompensa acumulada de cada uno de los estados del camino y actualiza la utilidad de estos nodos (ver Figura 2).

El método PMC produce estimaciones de utilidad que reducen al mínimo el error cuadrático medio con respecto a los datos observados.

Podemos considerar que el método PMC resuelve más o menos el problema del aprendizaje por refuerzo. Sin embargo, pasa por alto un aspecto muy importante del aprendizaje por refuerzo: el hecho de que la utilidad de los estados no es independiente (en este algoritmo, la utilidad de un estado depende del refuerzo acumulado, de su anterior utilidad y de la frecuencia de paso por ese nodo, pero no de las utilidades de los sucesores). Al no tener esto en cuenta, la actualización PMC converge de manera muy lenta a los valores de utilidad correctos del problema.

Los métodos que usan el conocimiento de la estructura del entorno normalmente aprenden mucho más rápido. Suponemos que las probabilidades de transición están contenidas en la tabla conocida M. Las utilidades se calculan resolviendo el siguiente conjunto de ecuaciones:

donde R(i) es la recompensa asociada con el estado i y Mij es la probabilidad de que ocurra una transición entre los estados i y j.

El algoritmo de programación dinámica adaptativa (PDA) proporciona desde el principio los valores correctos de utilidad para cada nodo. Sin embargo, no es útil para grandes espacios de estados. En el espacio de estados del backgammon, por ejemplo, implicaría resolver 10⁵⁰ ecuaciones con 10⁵⁰ incógnitas.

Este método trata de aunar lo mejor de los dos anteriores, esto es, trata de aproximar las ecuaciones del método anterior sin tener que resolverlas para todos los estados. La clave está en hacer el cálculo sólo para los estados por los que hemos pasado y ajustar sus valores de forma que se acerquen a los de las ecuaciones.

Supongamos que observamos una transición del estado i al estado j, en donde actualmente U(i)=-0.5 y U(j)=+0.5. Esto sugiere que deberíamos aumentar U(i) para ajustarlo mejor con su sucesor. Para ello, se puede utilizar la siguiente regla de actualización:

donde a es un valor comprendido entre 0 y 1 y representa la velocidad del aprendizaje. Debido a que esta regla de actualización usa las diferencias entre las utilidades de estados sucesivos, se le llama ecuación de Diferencias Temporales (DT).

El algoritmo que implementa la función de actualización de acuerdo con este método es el siguiente:

Conforme el modelo del ambiente se vaya aproximando al modelo real las estimaciones de utilidad convergerán en las utilidades correctas.

El modelo del ambiente se aprende a partir de la observación directa de las transiciones. Podemos actualizar el modelo de ambiente simplemente siguiendo la pista del número de veces que se produce una transición de un estado a su vecino. Hay que resaltar que el método PDA converge mucho más rápido que el PMC y el DT.

Los métodos ADP y DT están estrechamente relacionados: ambos intentan conseguir ajustes locales entre nodo y nodo de las estimaciones de utilidad para que cada estado se asemeje con sus sucesores. Una ligera diferencia es que el método DT ajusta un estado para que se asemeje con su sucesor observado, mientras que el ADP ajusta el estado para que se asemeje con todos sus sucesores, ponderando por sus probabilidades. Esta diferencia desaparece cuando el ajuste del DT se realiza sobre un gran número de transiciones, ya que la frecuencia de cada uno de los sucesores en el conjunto de transiciones es aproximadamente proporcional a su probabilidad. El método DT puede verse como una burda primera aproximación al método PDA.

Un agente de aprendizaje pasivo se puede ver como un agente que sigue una política fija, sin preocuparse de qué acciones debe tomar (la única acción que realiza es la acción "seguir observando", mientras que es el entorno quien genera las transiciones). Por el contrario, un agente de aprendizaje activo tiene que saber cuál es la siguiente acción que va a realizar.

• El modelo de entorno M debe ahora contener las probabilidades de transición a otro estado dada una acción en particular. Usaremos la notación M^a_ij para indicar la probabilidad de llegar al estado j cuando se toma la acción a en el estado i.

• La fórmula que expresa la utilidad de un estado debe ahora tener en cuenta el hecho de que el agente tiene una serie de acciones entre las que elegir. El agente maximizará la utilidad esperada, lo cual se expresa mediante la ecuación:

Para resolver los dos primeros puntos volveremos a examinar los enfoques de Programación Dinámica y Diferencias Temporales. El tercer punto se verá posteriormente cuando veamos la Exploración.

En cuanto al método de DT, la función de agente queda exactamente igual y la función de actualización sirve tal y como fue presentada con anterioridad.

Lo primero que se nos ocurriría para implementar esta función sería que el agente escogiera la acción que nos diera una mayor utilidad esperada según las actuales estimaciones de utilidades. El problema de esto es que si el agente siempre elige el camino con mayor utilidad es muy probable que se quede enclaustrado en un único camino, el primero que encuentre que tiene mayor utilidad esperada que el resto. Recordemos que al principio la tabla de utilidades está rellena con el mismo valor para todos los estados. Por tanto la primera secuencia de entrenamiento que nos lleve a un refuerzo positivo será la que se elegirá siempre con posterioridad.

En el otro extremo, si actuara para intentar aumentar el conocimiento continuamente, esto es, explorando siempre caminos alternativos, no es de utilidad ya que no se llega a poner el conocimiento en práctica. En el mundo real, constantemente tenemos que decidir entre continuar como estamos, en una existencia más o menos placentera, o bien lanzarse a lo desconocido con la esperanza de descubrir una vida mejor.

Así que tenemos dos enfoques: el "excéntrico" que actúa aleatoriamente con la esperanza de que llegue a explorar el entorno en su totalidad (exploración), y el "avaro" que sólo escoge las acciones que llevan a la máxima utilidad de acuerdo con las estimaciones actuales (explotación). Obviamente, tenemos que escoger un criterio que esté a medio camino entre ambos enfoques. La solución consiste en dar un peso a las acciones que no se han probado todavía con mucha frecuencia, mientras se evita escoger aquellas acciones que se conoce que tienen una utilidad pobre. De esta forma el agente actuaría en un principio como si hubiera regalos esparcidos por todo el grafo, y lo explora para encontrarlos.

Vamos a denotar por U⁺(i) la estimación optimista de la utilidad (esto es, el refuerzo acumulado esperado) para el estado i, y por N(a,i) al número de veces que la acción a se ha escogido en el estado i. Suponiendo que tenemos un agente PDA, tenemos que reescribir la ecuación de actualización para incorporar la estimación optimista de la utilidad, lo cual hacemos con la siguiente fórmula:

donde f(u,n) es conocida como la función de exploración. Esta determina cómo de "avaro" es (es decir, preferencia de valores altos de u) en contraposición a cómo de "excéntrico" es (preferencia de valores bajos de n, o sea, acciones que no se han escogido con mucha frecuencia). La función f(u,n) debería ser creciente en u, y decreciente en n. Por ejemplo podemos considerar la siguiente:

donde R⁺ es una estimación optimista del mejor refuerzo obtenible en cualquier estado, y N_e es un parámetro constante. El efecto de esto es que el agente pruebe cada par acción-estado al menos N_e veces.

El efecto de esta política de exploración es que se observa una rápida convergencia hacia el resultado óptimo, al contrario que ocurría con los enfoques "excéntrico" o "avaro".

Siguiendo en el marco de los agentes activos, una función acción-valor es aquella que asigna una utilidad al hecho de tomar una acción en un estado dado. A estos valores de utilidad se les llama también valores-Q. Usaremos la notación Q(a,i) para expresar el valor de tomar la acción a en el estado i. La relación entre estos valores y la función de utilidad vista anteriormente es la expresada por la siguiente ecuación:

Los valores-Q juegan un papel importante en el aprendizaje por refuerzo, por dos razones: en primer lugar, son suficientes para realizar la toma de decisiones sin necesidad de tener un modelo del entorno; en segundo lugar, estos valores pueden aprenderse directamente a partir de los refuerzos.

De igual forma a como hacíamos con las utilidades, podemos escribir una ecuación que muestre el equilibrio cuando los valores-Q son los correctos:

Podríamos usar esta ecuación para actualizar directamente los valores mediante una función iterativa tal y como hacíamos en el caso del agente activo por PDA. Sin embargo, esto requeriría también el aprendizaje del modelo ya que éste se necesita en la ecuación. Por otro lado, el algoritmo de diferencias temporales no necesita de este modelo. La regla de actualización para Q-learning mediante DT sería:

la cual se calcularía después de cada transición del estado i al j.

El diseño completo del agente exploratorio por Q-learning es el que se muestra en la Figura 5. Se utiliza exactamente la misma función f que en el agente exploratorio por PDA.

Con este algoritmo las estimaciones de utilidad tardan mucho más en asentarse que lo que ocurría con el agente PDA. Esto es debido al algoritmo DT en sí mismo. Cabe preguntarse si es mejor tener que aprender un modelo del entorno para funciones de utilidad o bien si aprender funciones de acción-valor sin necesidad de modelo. La Inteligencia Artificial nos ha enseñado que siempre es mejor tener un conocimiento sobre una parte al menos del entorno en el cual se mueve el agente, si bien hay algunos investigadores que no piensan así.

• "Artificial Intelligence. A modern approach" Stuart Russell & Peter Norvig. Ed. Prentice-Hall

• "Psicología General I" José Luis Fernández Tres Palacios. Ed. Gráficas Maravillas S.L.

• "Procesos Estocásticos" Emanuel Parzen. Ed. Paraninfo

• http://www-lsi.upc.es/~mmartin/home.html
  Aprendizaje de comportamientos complejos mediante mecanismos de refuerzo.
  Mario Martín. Universidad Politécnica de Cataluña.
• http://www.cs.cmu.edu/Web/Groups/reinforcement/web/homepage.html
  RL at CMU.
• http://www.cs.indiana.edu/classes/c463/reinforce.html
  RL in Indiana.
• http://piglet.cs.umass.edu:4321/~vijay/learn-skills.html
  UMass LPR Learning Page.
• http://envy.cs.umass.edu/People/sutton/archive.html
  Sutton papers.
• http://aepia.dsic.upv.es:1080/internet/internet-ia/subject/learn.htm
  Reinforcement Learning at Manchester University.