AIXI
# AIXI

AIXI['ai̯k͡siː] es un formalismo matemático teórico para la inteligencia general artificial . Combina la inducción de Solomonoff con la teoría de decisión secuencial . AIXI fue propuesto por primera vez por Marcus Hutter en 2000 y varios resultados con respecto a AIXI se prueban en el libro de 2005 de Hutter Universal Artificial Intelligence. AIXI es un agente de aprendizaje por refuerzo (RL) . Maximiza las recompensas totales esperadas recibidas del entorno. Intuitivamente, considera simultáneamente todas las hipótesis (o entornos) computables. En cada paso de tiempo, analiza todos los programas posibles y evalúa cuántas recompensas genera ese programa en función de la siguiente acción que se realice. Las recompensas prometidas se ponderan luego por la creencia subjetiva de que este programa constituye el verdadero entorno. Esta creencia se calcula a partir de la duración del programa: los programas más largos se consideran menos probables, en línea con la navaja de Occam . Luego, AIXI selecciona la acción que tiene la recompensa total esperada más alta en la suma ponderada de todos estos programas.

## Definición

AIXI es un agente de aprendizaje por refuerzo que interactúa con algún entorno estocástico y desconocido pero computable $\mu$ . La interacción procede en pasos de tiempo, desde $t=1$ a $t=m$, dónde $m\in \mathbb {N}$ es la vida útil del agente AIXI. En el paso de tiempo t, el agente elige una acción $a_{t}\in {\mathcal {A}}$ (por ejemplo, un movimiento de una extremidad) y lo ejecuta en el entorno, y el entorno responde con una "percepción" $e_{t}\in {\mathcal {E}}={\mathcal {O}}\times \mathbb {R}$, que consiste en una "observación" $o_{t}\in {\mathcal {O}}$ (por ejemplo, una imagen de cámara) y una recompensa $r_{t}\in \mathbb {R}$, distribuidos según la probabilidad condicional $\mu (o_{t}r_{t}|a_{1}o_{1}r_{1}...a_{t-1}o_{t-1}r_{t-1}a_{t})$, dónde $a_{1}o_{1}r_{1}...a_{t-1}o_{t-1}r_{t-1}a_{t}$ es la "historia" de acciones, observaciones y recompensas. El entorno $\mu$ por lo tanto, se representa matemáticamente como una distribución de probabilidad sobre "percepciones" (observaciones y recompensas) que dependen del historial completo, por lo que no existe la suposición de Markov (a diferencia de otros algoritmos de RL). Nótese nuevamente que esta distribución de probabilidad es desconocida para el agente AIXI. Además, nótese nuevamente que $\mu$ es computable, es decir, las observaciones y recompensas que recibe el agente del entorno $\mu$ puede ser calculado por algún programa (que se ejecuta en una máquina de Turing ), dadas las acciones pasadas del agente AIXI.

El único objetivo del agente AIXI es maximizar $\sum _{t=1}^{m}r_{t}$, es decir, la suma de las recompensas desde el paso de tiempo 1 hasta m.

El agente AIXI está asociado a una política estocástica $\pi :({\mathcal {A}}\times {\mathcal {E}})^{*}\rightarrow {\mathcal {A}}$, que es la función que utiliza para elegir acciones en cada paso de tiempo, donde ${\mathcal {A}}$ es el espacio de todas las acciones posibles que AIXI puede tomar y ${\mathcal {E}}$ es el espacio de todas las "percepciones" posibles que puede producir el entorno. El entorno (o distribución de probabilidad) $\mu$ también se puede considerar como una política estocástica (que es una función): $\mu :({\mathcal {A}}\times {\mathcal {E}})^{*}\times {\mathcal {A}}\rightarrow {\mathcal {E}}$, donde el $*$ es la operación estrella de Kleene . En general, en el paso de tiempo $t$ (que va de 1 a m), AIXI, habiendo ejecutado previamente acciones $a_{1}\dots a_{t-1}$ (que a menudo se abrevia en la literatura como $a_{<t}$ ) y habiendo observado la historia de las percepciones $o_{1}r_{1}...o_{t-1}r_{t-1}$ (que se puede abreviar como $e_{<t}$ ), elige y ejecuta en el entorno la acción, $a_{t}$, definido de la siguiente manera

    $a_{t}:=\arg \max _{a_{t}}\sum _{o_{t}r_{t}}\ldots \max _{a_{m}}\sum _{o_{m}r_{m}}[r_{t}+\ldots +r_{m}]\sum _{q:\;U(q,a_{1}\ldots a_{m})=o_{1}r_{1}\ldots o_{m}r_{m}}2^{-{\textrm {length}}(q)}$

o, usando paréntesis, para eliminar la ambigüedad de las precedencias

    $a_{t}:=\arg \max _{a_{t}}\left(\sum _{o_{t}r_{t}}\ldots \left(\max _{a_{m}}\sum _{o_{m}r_{m}}[r_{t}+\ldots +r_{m}]\left(\sum _{q:\;U(q,a_{1}\ldots a_{m})=o_{1}r_{1}\ldots o_{m}r_{m}}2^{-{\textrm {length}}(q)}\right)\right)\right)$

Intuitivamente, en la definición anterior, AIXI considera la suma de la recompensa total sobre todos los "futuros" posibles hasta $m-t$ el tiempo avanza (es decir, desde $t$ a $m$ ), pondera cada uno de ellos por la complejidad de los programas $q$ (es decir, por $2^{-{\textrm {length}}(q)}$ ) consistente con el pasado del agente (es decir, las acciones ejecutadas previamente, $a_{<t}$, y percepciones recibidas, $e_{<t}$ ) que puede generar ese futuro, y luego elige la acción que maximiza las recompensas futuras esperadas.

Desglosemos esta definición para intentar entenderla completamente.

$o_{t}r_{t}$ es el "percepto" (que consiste en la observación $o_{t}$ y recompensa $r_{t}$ ) recibido por el agente AIXI en el paso de tiempo $t$ del entorno (que es desconocido y estocástico). Similarmente, $o_{m}r_{m}$ es la percepción recibida por AIXI en el paso de tiempo $m$ (el último paso de tiempo en el que AIXI está activo).

$r_{t}+\ldots +r_{m}$ es la suma de las recompensas del paso de tiempo $t$ paso de tiempo $m$, por lo que AIXI necesita mirar hacia el futuro para elegir su acción en el paso de tiempo $t$ .

$U$ denota una máquina de Turing universal monótona, y $q$ rangos sobre todos los programas (deterministas) en la máquina universal $U$, que recibe como entrada el programa $q$ y la secuencia de acciones $a_{1}\dots a_{m}$ (es decir, todas las acciones), y produce la secuencia de percepciones $o_{1}r_{1}\ldots o_{m}r_{m}$ . La máquina de Turing universal $U$ por lo tanto, se utiliza para "simular" o calcular las respuestas o percepciones del entorno, dado el programa $q$ (que "modela" el entorno) y todas las acciones del agente AIXI: en este sentido, el entorno es "computable" (como se indicó anteriormente). Tenga en cuenta que, en general, el programa que "modela" el entorno actual y real (donde AIXI debe actuar) es desconocido porque el entorno actual también es desconocido.

${\textrm {length}}(q)$ es la duración del programa $q$ (que se codifica como una cadena de bits). Tenga en cuenta que $2^{-{\textrm {length}}(q)}={\frac {1}{2^{{\textrm {length}}(q)}}}$ . Por lo tanto, en la definición anterior, $\sum _{q:\;U(q,a_{1}\ldots a_{m})=o_{1}r_{1}\ldots o_{m}r_{m}}2^{-{\textrm {length}}(q)}$ debe interpretarse como una mezcla (en este caso, una suma) sobre todos los entornos computables (que son consistentes con el pasado del agente), cada uno ponderado por su complejidad $2^{-{\textrm {length}}(q)}$ . Tenga en cuenta que $a_{1}\ldots a_{m}$ también se puede escribir como $a_{1}\ldots a_{t-1}a_{t}\ldots a_{m}$, y $a_{1}\ldots a_{t-1}=a_{<t}$ es la secuencia de acciones ya ejecutadas en el entorno por el agente AIXI. Similarmente, $o_{1}r_{1}\ldots o_{m}r_{m}=o_{1}r_{1}\ldots o_{t-1}r_{t-1}o_{t}r_{t}\ldots o_{m}r_{m}$, y $o_{1}r_{1}\ldots o_{t-1}r_{t-1}$ es la secuencia de percepciones producidas por el entorno hasta el momento.

Pongamos ahora todos estos componentes juntos para entender esta ecuación o definición.

En el paso de tiempo t, AIXI elige la acción $a_{t}$ donde la función $\sum _{o_{t}r_{t}}\ldots \max _{a_{m}}\sum _{o_{m}r_{m}}[r_{t}+\ldots +r_{m}]\sum _{q:\;U(q,a_{1}\ldots a_{m})=o_{1}r_{1}\ldots o_{m}r_{m}}2^{-{\textrm {length}}(q)}$ alcanza su máximo.

### Parámetros

Los parámetros para AIXI son la máquina de Turing universal U y el tiempo de vida del agente m, que deben elegirse. El último parámetro se puede eliminar mediante el uso de descuentos .

## El significado de la palabra AIXI

Según Hutter, la palabra "AIXI" puede tener varias interpretaciones. AIXI puede representar AI según la distribución de Solomonoff, denotada por $\xi$ (que es la letra griega xi), o por ejemplo, puede significar AI "cruzado" (X) con inducción (I). Hay otras interpretaciones.

## Optimalidad

El desempeño de AIXI se mide por el número total esperado de recompensas que recibe. Se ha demostrado que AIXI es óptimo de las siguientes maneras.

* Óptimo de Pareto : no hay otro agente que funcione al menos tan bien como AIXI en todos los entornos mientras se desempeña estrictamente mejor en al menos un entorno.
* Optimismo de Pareto equilibrado: como el óptimo de Pareto, pero considerando una suma ponderada de entornos.
* Autooptimización: una política p se denomina autooptimización para un entorno. $\mu$ si el rendimiento de p se acerca al máximo teórico para $\mu$ cuando la duración de la vida del agente (no el tiempo) llega al infinito. Para las clases de entorno en las que existen políticas de optimización automática, AIXI se optimiza automáticamente.

Más tarde, Hutter y Jan Leike demostraron que la optimización de Pareto equilibrada es subjetiva y que cualquier política puede considerarse óptima de Pareto, lo que describen como que socava todas las afirmaciones de optimización anteriores para AIXI. Sin embargo, AIXI tiene limitaciones. Se limita a maximizar las recompensas basadas en percepciones en lugar de estados externos. También asume que interactúa con el entorno únicamente a través de canales de acción y percepción, evitando que considere la posibilidad de ser dañado o modificado. Coloquialmente, esto significa que no se considera contenido por el entorno con el que interactúa. También asume que el entorno es computable.

## Aspectos computacionales

Al igual que la inducción de Solomonoff, AIXI es incomputable . Sin embargo, existen aproximaciones computables de la misma. Una de esas aproximaciones es AIXI tl, que funciona al menos tan bien como el mejor agente limitado en tiempo t y espacio l. Otra aproximación a AIXI con una clase de entorno restringido es MC-AIXI (FAC-CTW) (que significa Monte Carlo AIXI FAC- Context-Tree Weighting ), que ha tenido cierto éxito en juegos simples como Pac-Man parcialmente observable.

