Home » Seminario del IIE » Q-learning

Q-learning

Dr. Ing. Juan Bazerque

La programación dinámica (PD) aborda el problema de optimizar un costo esperado a largo plazo cuyas variables son acciones a tomar en distintos instantes de tiempo (Bertsekas 2005). En particular, PD se aplica al caso en que estas acciones están acopladas por ecuaciones de transición de estados que modelan la dinámica del sistema a optimizar. Aunque también sea relevante ante modelos determinísticos si se busca reducir la carga computacional de los algoritmos, la PD es fundamental cuando se consideran procesos estocásticos que modelan incertidumbre. En estos casos el iterar en el tiempo permite operar en lazo cerrado, incorporando en cada instante la información obtenida de observar el estado y las variables aleatorias involucradas.

Figura 1

Desde la perspectiva de la teoría de control la PD aplicada a un caso de costos cuadráticos y dinámicas lineales resulta en la celebrada ecuación de Riccati que da forma al filtro de control óptimo. Esta idea tiene numerosas aplicaciones, tan diversas como el vuelo de drones o la operación de sistemas de potencia. Un ejemplo de esto es la operación óptima de baterías u otros sistemas de acumulación de energía en redes eléctricas. Esta operación busca minimizar la cantidad de energía generada a partir de combustibles fósiles, teniendo las ecuaciones de la red como restricciones. La incertidumbre viene dada por la demanda y el aporte de fuentes renovables, el estado del sistema corresponde al nivel de carga de las baterías, y la dinámica viene dada por su carga y descarga. Luego, el algoritmo de optimización decidirá cargar o descargar las baterías comparando la demanda y disponibilidad de renovables en cada instante con sus valores esperados a futuro.

Figura 2

Otra perspectiva se obtiene desde el aprendizaje automático por computadora, en que las acciones óptimas se ajustan en base a resultados de acciones previas, un concepto conocido en idioma inglés como reinforcement learning. Es desde este segundo punto de vista que nace en la década del 90 la idea de q-learning (Watkins et al 1992). La programación dinámica estocástica en su forma más pura requiere conocer las distribuciones de probabilidad de la incertidumbre para poder así calcular esperanzas. Si estas distribuciones no son conocidas entonces pueden “aprenderse” a partir de muestras como nos enseña Kolmogorov en sus leyes de los grandes números, o más específicamente según los algoritmos de aproximación estocástica de Robins, Monro y Dvoretsky (Dvoretsky 1956). Q-learning puede verse como una versión estocástica de PD en que a cada instante se observa el estado, se toma una acción y se observa su resultado. Se obtiene así una recompensa o castigo que se utiliza para subir o bajar la calificación de la acción tomada. Luego esta calificación será considerada al decidir la acción a óptima cuando el sistema vuelva a pasar por el mismo estado. Un ejemplo de esto es un jugador de ta-te-ti programado por computadora. El algoritmo escrito en Python considera el estado como la distribución de cruces, ceros y espacios vacíos en el tablero, la acción de control es la posición de una nueva cruz en los espacios vacíos, y la incertidumbre viene dada por la posición de un cero por parte del contrincante. Cada jugada tiene una recompensa positiva si gana la partida, negativa si lleva a la derrota, o nula si no es determinante. A lo largo de varias jugadas de entrenamiento el algoritmo forma una matriz de calificaciones para cada par tablero-jugada que utiliza para decidir las jugadas óptimas a futuro.

Figura 3

En un marco más abstracto puede combinarse la teoría de control óptimo con la del procesamiento de señales en grafos, con el fin de estabilizar un sistema distribuido e interconectado. Avances de investigación recientes en el modelado de sistemas interconectados se fundamentan en la nueva definición de la transformada de Fourier en un grafo, generalizando el concepto de componentes de frecuencia temporales para señales que fluctúan cuando atraviesan las aristas de una red. Desde esta nueva óptica los sistemas interconectados pueden modelarse según su transferencia espacio-temporal, esto es, una función de la frecuencia de grafo combinada con la transformada Z (Isufi et al 2016).

Figura 4
Figura 5

Según se reporta en (Bazerque-Monzón 2017) y se muestra en la figura 4, la transferencia deberá estar contenida en el cilindro de diámetro unitario para que el sistema en su conjunto sea estable. Luego se prueba que si las señales de estado y control se describen por sus transformadas de Fourier en el grafo, entonces tanto la ecuación de Riccati como el controlador óptimo se descomponen por componentes de frecuencia. El sistema controlado resulta estable ya que los modos de alta frecuencia del sistema son comprimidos como se muestra en la figura 5 de modo que la transferencia es forzada hacia dentro del cilindro unitario.

En conclusión, la PD fundamenta la teoría de control óptimo y q-learning, con aplicaciones en las más diversas áreas, incluyendo el vuelo de drones, el almacenamiento de energía en redes de potencia, y el aprendizaje automático por computadora.También abre perspectivas a nuevos temas de investigación, por ejemplo al combinarla con avances recientes en procesamiento de señales en grafos.

Referencias   

D. P.Bertsekas, Dynamic programming and optimal control, vol. 1, 3th Ed., Belmont, MA: Athena Scientific, 2005.

C. Watkins, and P Dayan, “Q-learning,” Machine Learning, vol. 8.3-4 pp. 279-292,1992.

A. Dvoretski, “On stochastic Approximation,” Proc. of the Third Berkeley Symposium on Mathematical Statistics and Probability, University of California Press, 1956.

E. Isufi, A. Loukas, A. Simonetto, and G. Leus, “Autoregressive Moving Average Graph Filtering,” IEEE Transactions on Signal Processing, vol.65, pp 274-288, 2017.

J. A. Bazerque and P. Monzón, “Control of networked systems in the graph-frequency domain,” IEEE Intl. Asilomar conf on Sig., Sys, and Comp., Monterrey, CA, 2017 (submitted).