Factors that affect the number of iterations of value iteration

Question

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?

Answer 1

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.

It is also showing an interesting effect in that even for small environments, value iteration will keep refining the value accuracies, even if the optimal policy was found much earlier. In the small environments (e.g. the 5x5 grid), the chances are that value iteration could be used after much fewer iterations to generate the optimal policy, but it has no stopping criteria for that - instead it keeps resolving the value calculations until they stop changing by the cutoff you have set.

This effect you noticed should disappear for value iteration when there is a maximum trajectory length less than the "signal attenuation threshold" that you have created. For example, if reaching a specific location also terminated the episode and did so whilst maximising the return. In that case value iteration should behave like a "flood fill" and should terminate once the longest possible optimal trajectory has been calculated.