¿Pueden los modelos obtener un 100% de precisión en juegos resueltos?

Question

Hoy tuve una pregunta que creo que ya debe tener una respuesta, así que estoy buscando.

Si le pedimos a un modelo que aprenda la función OR binaria, obtenemos una precisión perfecta con cada modelo (hasta donde yo sé).

Si le pedimos a un modelo que aprenda la función XOR, obtenemos una precisión perfecta con algunos modelos y una aproximación con otros (por ejemplo, perceptrones).

Esto se debe a la forma en que se diseñan los perceptrones: es una superficie que el algoritmo no puede aprender. Pero nuevamente, con una red neuronal de múltiples capas, podemos obtener un 100% de precisión.

Entonces, ¿podemos aprender perfectamente un juego resuelto también?

Tic-tac-toe es un juego resuelto; existe un movimiento óptimo para ambos jugadores en cada estado del juego. Entonces, en teoría, nuestro modelo podría aprender tic-tac-toe tan bien como podría una función lógica, ¿verdad?

Answer 1

Entonces, ¿podemos aprender perfectamente un juego resuelto también?

La respuesta corta es sí. Si su modelo tiene la complejidad suficiente, teóricamente puede aprender cualquier comportamiento que desee.

Entonces, en teoría, nuestro modelo podría aprender tic-tac-toe

Tic Tac Toe ya se ha resuelto. Otro juego popular que ha sido resuelto es Checkers, mediante el algoritmo Chinook.

Para ser más específicos, en Aprendizaje por refuerzo asumimos que cualquier proceso de toma de decisiones puede modelarse como un MDP (Proceso de decisión de Markov). Una vez allí, hay una gran cantidad de métodos diferentes como Q-Learning y TD que teóricamente convergen hacia la política óptima: la que se juega perfectamente.

Ahora bien, el hecho de que sea teóricamente posible no significa que siempre funcionará empíricamente. En juegos que son muy complejos y tienen un gran espacio de estado, es extremadamente difícil de resolver perfectamente. Esto se debe a que la única forma factible de abordarlos es aproximarlos y, como resultado, obtener un juego perfecto incluso en casos de bordes pequeños se vuelve mucho más difícil.

Si desea obtener más información sobre este tema, le recomiendo encarecidamente esta serie de cursos de RL de David Silver