# Aprendizaje por Refuerzo Cuántico

El Aprendizaje por Refuerzo Cuántico es un área de investigación, en la que se aprovechan las propiedades de la mecánica cuántica de cara a optimizar el aprendizaje por refuerzo. La forma de abordar los problemas principales del aprendizaje automático mediante la computación cuántica permite construir una estrategia por exploración (basada en un criterio de recompensas a aprender por el agente) cuadráticamente más rápida respecto del aprendizaje por refuerzo clásico.
El aprendizaje por refuerzo cuántico permitirá abordar problemas de complejidad superior a los resueltos clásicamente, como por ejemplo la teoría de juegos, teorías de control óptimo, investigación de operaciones y Teoría de la información.
Los algoritmos relacionados con el aprendizaje por refuerzo cuántico se basan en emplear la propiedad de la superposición cuántica, para expresar la acción del agente y estado del medio-ambiente con el que interacciona como una combinación lineal de auto-acciones y de estados del medio-ambiente, pesados con sus respectivos pesos probabilísticos.

## Problemas que pueden resolverse con Aprendizaje por Refuerzo Cuántico

Existen diferentes tipos de Aprendizajes Automáticos: el supervisado, el no supervisado y el aprendizaje por refuerzo. Cada uno de ellos sirve para abordar diferentes problemas. Concretamente, el Aprendizaje por Refuerzo, es lo que más se parece a "aprender". Dadas unas condiciones de reglas y metas, el agente consigue recompensas con un valor equivalente a la acción que ha tomado. Si el agente ha escogido una estrategia buena, tendrá mayor recompensa que una estrategia mala. Es entonces cuando el agente "aprende" a tomar mejores o peores acciones de cara al siguiente episodio (estudio de una nueva estrategia). Los problemas que se abordan con aprendizaje supervisado y no supervisado son en general problemas de agrupamiento de datos y análisis de datos (data-learning), sin embargo, el aprendizaje por refuerzo es útil para aplicaciones relacionadas con la Inteligencia Artificial.
El aprendizaje por refuerzo cuántico no ha recibido la misma atención que el aprendizaje supervisado y no supervisado cuántico. Sin embargo es un tema que se ha estudiado a fondo: por ejemplo se sugiere que QIP (Quantum Information Processing) podría nuevas maneras para evaluar políticas, y se ha demostrado, por primera vez en el Aprendizaje por Refuerzo cuántico, una ventaja cuadrática utilizando un algoritmo cuántico sobre el algoritmo clásico de Aprendizaje por Refuerzo, Projective Simulation.
El estudio de estrategias, como lo hace la Teoría de Juegos y la investigación de operaciones es optimizado aplicando un algoritmo cuántico, aprovechando las propiedades de la mecánica cuántica. Esquemáticamente, el aprendizaje por refuerzo automático estudia en cada episodio una posible estrategia, evaluándose al final la bondad de la estrategia en función de la recompensa obtenida consecuencia de la interacción entre el agente y el medio en cada acción. El aprendizaje por refuerzo cuántico estudia las posibles estrategias (entre un estado y otro) una vez interactúa, conociendo todas las recompensas que podría haber obtenido. Esto refleja claramente que el proceso de elección de una acción por parte del agente de cara a buscar la mejor estrategia, se agiliza.

## Principios básicos
### Superposición de auto-acciones (auto-estados)

En la computación cuántica podemos expresar un cúbit en superposición como combinación lineal de estados $|\psi \rangle =\alpha |0\rangle +\beta |1\rangle$. Si tenemos un sistema de n-cúbits expresamos el estado como un productorio tensorial de cúbits, $|\phi \rangle =|\psi _{1}\rangle \otimes ...\otimes |\psi _{n}\rangle =\sum _{x=00...0}^{11...1}c_{x}|x\rangle$. Empleando estas propiedades básicas, se puede expresar un número finito de auto-acciones y auto-estados como:
    $\left|s^{(m)}\right\rangle =\sum _{s=00...0}^{11...1}C_{s}\left|s\right\rangle \sum _{s=00...0}^{11...1}\left|C_{s}\right|^{2}=1$
    $|a^{(n)}\rangle =\sum _{a=00...0}^{11...1}C_{a}|a\rangle \sum _{a=00...0}^{11...1}|C_{a}|^{2}=1$
Los coeficientes $C_{s}$ y $C_{a}$ se corresponden con las amplitudes de probabilidad del estado del entorno y de la acción, respectivamente. Son números complejos y la suma algebraica de sus módulos al cuadrado debe de ser 1 por la regla de conservación de probabilidad.
Este enfoque permite acelerar el procedimiento usual del aprendizaje por refuerzo clásico, ya que implementa un algoritmo cuántico que actúa sobre un estado $s_{t}$ del entorno, evaluando todas las posibles acciones en superposición sobre el mismo estado, que posteriormente evoluciona al estado $s_{t+1}$.

### Política de selección para la acción

En el aprendizaje por refuerzo cuántico el agente debe de aprender una política $\pi :S\times \cup _{i\in S}A_{(i)}\rightarrow [0,1]$, que maximiza la recompensa obtenida por cada acción para cada estado entorno. Podemos traducir esto como el mapeo de los estados a las acciones posibles desde este estado:
    $f(s)=|a_{s}^{(n)}\rangle =\sum _{a=00...0}^{11...1}C_{a}|a\rangle$
Cuando se mide $|a_{s}^{(n)}\rangle$, el agente colapsa a una de las auto-acciones $|a\rangle$ con una probabilidad $|C_{a}|^{2}$. El objetivo es entonces amplificar la probabilidad de las acciones con mayor recompensa.

## Amplificación de la amplitud de probabilidad

Acorde con el postulado de colapso cuántico, la elección de una acción se hace acorde con la medida de la misma para un estado $|s\rangle$, obteniéndose una auto-acción $|a\rangle$ con probabilidad $|C_{a}|^{2}$. Es claro que mediante un procedimiento de prueba y error, se busca el $|a\rangle$ con mayor recompensa, para el cual su amplitud de probabilidad debe ser amplificada, mediante un algoritmo de Grover. Primero se prepara una acción combinación lineal de auto-acciones con los mismos pesos probabilísticos tal que:
    $|a_{0}^{(n)}\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{a=00...0}^{11...1}|a\rangle$
Este estado se construye aplicando n puertas de Hadamard en secuencia a n cúbits independientes con estados iniciales $|0\rangle$:
    $H^{\otimes n}|00...0\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{a=00...0}^{11...1}|a\rangle$
Para construir el algoritmo de Grover combinamos dos reflexiones, $U_{a}$ y $U_{a_{0}^{(n)}}$, que se definen de la siguiente forma:
    $U_{a}=I-2|a\rangle \langle a|$
    $U_{a_{0}^{(n)}}=H^{\otimes n}\left(2|0\rangle \langle 0|-I\right)H^{\otimes n}=2|a_{0}^{(n)}\rangle \langle a_{0}^{(n)}-I$
Donde $I$ es la identidad y $U_{a}$ es el oráculo $O$ del algoritmo de Grover. Una iteración del algoritmo de Grover se construye combinando estos dos operadores: $U_{grov}=U_{a_{0}^{(n)}}U_{a}$.

## Algoritmo de aprendizaje por refuerzo cuántico

El algoritmo de aprendizaje por refuerzo cuántico sigue el siguiente protocolo:
* Inicializamos un estado con m cúbits y con n acciones posibles $f(s)$ para una función criterio $V(s)$ arbitraria.
* Repetimos para cada episodio el siguiente procedimiento:
** Para todos los estados $|s\rangle$ en $|s^{(m)}\rangle =\sum _{s=00...0}^{11...1}C_{s}|s\rangle$ se observa $f(s)=|a_{s}^{(n)}\rangle$ y se obtiene $|a\rangle$.
** Tomando la acción $|a\rangle$ se observa el estado $|s^{'}\rangle$, por la cual se obtiene una recompensa r, entonces:
*** Se actualiza la función criterio $V(s)\leftarrow V(s)+\alpha (r+\gamma V(s^{'})-V(s))$.
*** Se actualizan las amplitudes de probabilidad, repitiendo $U_{grov}$ L veces.
Para una tolerancia dada ($\epsilon$), el algoritmo se detendrá cuando la función criterio converja tal que $|\Delta V(s)|\leq \epsilon$.
El aprendizaje se basa en la predicción de diferencia temporal para la actualización de la función criterio $V(s)$. Como el aprendizaje es estrictamente positivo y decreciente, se asegura la convergencia de la Cadena de Markov al valor óptimo $V^{*}(s)$ con probabilidad 1 mediante un proceso de política de exploración si se cumplen las siguientes propiedades del índice de aprendizaje $\alpha$:
    ${\underset {T\rightarrow \infty }{lim}}\sum _{k=1}^{T}\alpha _{k}=\infty$
    ${\underset {T\rightarrow \infty }{lim}}\sum _{k=1}^{T}\alpha _{k}^{2}<\infty$
Los criterios de convergencia para un algoritmo estocástico como es el anteriormente explicado fueron probados por Bertsekas y Tsitsiklis. Muchos algoritmos del aprendizaje por refuerzo clásico son estocásticos. Sin embargo, este algoritmo presenta las siguientes diferencias (que permiten comparar la convergencia del algoritmo cuántico respecto del clásico, mientras la anterior condición se satisfaga):
* La política de exploración se basa en el postulado del colapso cuántico al medir.
* Este algoritmo se basa en el paralelismo cuántico (que no viola el teorema de no-clonación), lo que se traduce como que se actualizan todos los estados simultáneamente y se sincroniza con el aprendizaje.