2024/06/11 by Maximilian Schäffeler, Schäffeler, Maximilian, Mohammad Abdulaziz +1 · 1 citation
Computer Science · #Age of Information Optimization #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2406.07340
openalex publication_date 2024/06/11 · openalex created_date 2024/06/13 · openalex updated_date 2026/07/28
We formally verify an algorithm for approximate policy iteration on Factored Markov Decision Processes using the interactive theorem prover Isabelle/HOL. Next, we show how the formalized algorithm can be refined to an executable, verified implementation. The implementation is evaluated on benchmark problems to show its practicability. As part of the refinement, we develop verified software to certify Linear Programming solutions. The algorithm builds on a diverse library of formalized mathematics and pushes existing methodologies for interactive theorem provers to the limits. We discuss the process of the verification project and the modifications to the algorithm needed for formal verification.