Resumen: El algoritmo de iteración de políticas de Howard es un método popular para resolver DMDP con objetivos de pago malo. Although Howard’s algorithm performs well in practice, as experimental studies suggested, the best known upper bound is exponential and the current known lower bound is as follows: For the input size $I$, the algorithm requires $tilde{Omega}(sqrt{I})$ iterations, where $tilde{Omega}$ hides the poly-logarithmic factors, es decir, el límite inferior actual en las iteraciones es sublineal con respecto al tamaño de entrada. Nuestro resultado principal es un límite inferior mejorado para este algoritmo fundamental donde mostramos que para el tamaño de entrada $ i $, el algoritmo requiere $ tilde { omega} (i) $ iteraciones.
Publicado Originalme en rss.arxiv.org El 16 de junio de 2025.
Ver Fuente Original
