# Factors that affect the number of iterations of value iteration

I had an assumption that value iteration will take more iterations to converge if the map size increases/environment's complexity increases.

I tried to verify this idea by running value iteration on randomly generated grid worlds of increasing sizes (from 5X5 grid world, 6x6 grid world ... to 50x50 grid world). In each grid world, there are 4 states with reward value of +1. All other states have reward value of 0, -0.03, -1.

Strangely, I noticed that although the computation time for value iteration to converge increased significantly (which is expected since the time complexity of each iteration increases as the grid world's size increases), number of iterations it took for value iteration to converge remained the same at 66 across all map sizes. This contradicts with my assumption that the number of iterations of value iteration should generally increase if the size/complexity of the environment increases.

I am quite sure my code implementation is correct (I have checked my code and policy/values obtained from the value iterations), and I believe the stop condition that I set for the value iteration is reasonable (I stops value iterations if the maximum change in the values in the current iteration is less than 0.001).

Could anyone explain this phenomenon, and if there are factors that may affect the number of iterations of value iteration?

• I think your results only make sense in a continuing (non-episodic) environment. Is that that case? Commented Mar 27, 2022 at 8:54
• Yes, the environment has no terminating state. Thank you for the detail explanation. I have a clear understanding of the issue now. Commented Mar 27, 2022 at 16:40

What was your value for $$\gamma$$? I'm guessing at $$0.9$$?
What is $$0.9^{66}$$? It is $$\approx 0.000955$$ which is less than $$0.001$$, whilst $$0.9^{65} \approx 0.001061 \gt 0.001$$
What you are measuring with the 66 max iterations in your chosen environments and problems is the point at which the signal from the backed up reward signal decays below your chosen accuracy threshold. This is also showing an interesting limit for those values - in an environment with maximum reward 1 and optimal trajectories longer than 66 (or with a loop repeat length greater than 66), your chosen values for $$\gamma$$ and $$\theta$$ may not be able to find the optimal policy.