Daily Arxiv

Esta página recopila y organiza artículos sobre inteligencia artificial publicados en todo el mundo.
La información aquí presentada se resume utilizando Google Gemini y el sitio se gestiona sin fines de lucro.
Los derechos de autor de los artículos pertenecen a sus autores y a las instituciones correspondientes; al compartir el contenido, basta con citar la fuente.

Criterios de detención para la iteración de valor en juegos concurrentes de alcanzabilidad y seguridad estocástica

Created by
  • Haebom

Autor

Marta Grobelna, Jan K\v{r}et insk y, Maximilian Weininger

Describir

Este artículo considera juegos estocásticos simultáneos de suma cero (CSG) para dos jugadores con objetivos de alcanzabilidad y seguridad en grafos. Si bien las clases degeneradas, como los procesos de decisión de Markov y los juegos estocásticos por turnos, pueden resolverse mediante programación lineal o cuadrática, en la práctica, la Iteración de Valor (IV) supera a otros enfoques y es el método más comúnmente implementado. Este rendimiento práctico convierte a los IV en una alternativa atractiva a las soluciones teóricas estándar que utilizan la teoría de números reales existenciales para los CSG. Los IV existentes comienzan con una aproximación del valor objetivo para cada estado y lo actualizan iterativamente, terminando tradicionalmente cuando dos aproximaciones sucesivas se aproximan a la ε-aproximación. Sin embargo, estos criterios de terminación carecen de garantías respecto a la precisión de la aproximación. En este artículo, presentamos un IV acotado (de intervalo) para CSG que compensa las secuencias de sobreaproximación que convergen al IV estándar y termina cuando tanto la sobreaproximación como la subaproximación se aproximan a la ε-aproximación.

Takeaways, Limitations

Takeaways: Presentamos un algoritmo de iteración de valores límite para CSG, que garantiza la precisión de las aproximaciones. Esto supera las limitaciones de los algoritmos de iteración de valores existentes y produce resultados más fiables.
Limitations: La complejidad computacional y el rendimiento práctico del algoritmo de iteración de valores límite presentado en este artículo son insuficientes. Se requiere una evaluación experimental con CSG de diversos tamaños y complejidades. Además, podría ser necesario realizar más investigaciones para determinar la eficacia del algoritmo para tipos específicos de CSG.
👍