Value iteration (VI) is a ubiquitous algorithm for optimal control, planning,\nand reinforcement learning schemes. Under the right assumptions, VI is a vital\ntool to generate inputs with desirable properties for the controlled system,\nlike optimality and Lyapunov stability. As VI usually requires an infinite\nnumber of iterations to solve general nonlinear optimal control problems, a key\nquestion is when to terminate the algorithm to produce a "good" solution, with\na measurable impact on optimality and stability guarantees. By carefully\nanalysing VI under general stabilizability and detectability properties, we\nprovide explicit and novel relationships of the stopping criterion's impact on\nnear-optimality, stability and performance, thus allowing to tune these\ndesirable properties against the induced computational cost. The considered\nclass of stopping criteria encompasses those encountered in the control,\ndynamic programming and reinforcement learning literature and it allows\nconsidering new ones, which may be useful to further reduce the computational\ncost while endowing and satisfying stability and near-optimality properties. We\ntherefore lay a foundation to endow machine learning schemes based on VI with\nstability and performance guarantees, while reducing computational complexity.\n