In Value Iteration, why can we initialize the value function arbitrarily?

Question

I have not been able to find a good explanation of this, other than statements that the algorithm is guaranteed to converge with arbitrary choices for initial values in each state. Is this something to do with the Bellman optimality constraint itself?

It's hard to see that this is true intuitively since my intuition states that there ought to be ways in which an arbitrary choice of values could cause the value function to converge incorrectly compared to the ground truth. For instance, what if a state that in practice had low reward is assigned a very high initial reward value in value iteration? Would the algorithm not construct a value function that highly values trajectories passing through that state?

Answer 1

If the value function of a state $v(s)$ is relatively high, then you are absolutely correct in saying that a greedy policy may choose to visit $s$, since the high $v(s)$ makes it very promising. The key idea here is that the update rule of value iteration will gradually change the value function and likewise will gradually change the policy.

Suppose that the optimal value function $v_*(s)$ of a specific state $s$ is low, yet the value function $v(s)$ is initialized much higher. Then, the update rule in the pseudocode you provided will eventually decrease $v(s)$ to $v_*(s)$. To see this fact intuitively, note that $v(s)$ can be decomposed as the expected return (sum of rewards) from that state: $$v(s) = \mathbb{E}[R_k + R_{k+1} + R_{k+2} + \ldots + R_T|S_k = s].$$ If the expected return from $s$ is smaller than $v(s)$, then $v(s)$ will decrease with the aforementioned update. The actual update rule approximates the expected return from $s$ using the next reward $R_k$ and the value function of the next state $v(s')$ via bootstrapping. Note that $v(s')$ can be decomposed as follows: $$v(s') = \mathbb{E}[R_{k+1} + R_{k+2} + \ldots + R_T|S_{k+1}=s'].$$ Therefore, $v(s')$ quantifies the part of the return aside from the next reward $R_k$, and the update rule indeed quantifies the expected return from $s$. If $v(s')$ is initialized too high or low, then the update rule will simultaneously be adjusting it to the optimal $v_*(s')$ while adjusting $v(s)$ closer to $v_*(s)$.

Once the value functions change as described above, then the greedy policy may also change and favor other states aside from $s$ with higher value functions.

Answer 2

Is this something to do with the Bellman optimality constraint itself?

That is part of it, and important for episodic problems without discounting. The Bellman equations link between time steps, providing a direction that data about returns is used to bootstrap value estimates. In episodic problems there are terminal states with 0 value by definition. In the first pass through state space, any state that can transition to a terminal state will be exposed to that fixed knowledge, and could be altered to take that transition. This data is backed up through time steps, at least once per value iteration sweep, and maybe more frequently depending on the order of updating states. You can visualise this effect like a "flood fill" starting from terminal states and filling in the table with true values.

In addition, when there is a discount factor (optional for episodic environments, but required for continuing ones), then this progressively reduces any bias in existing estimates due to the term $r + \gamma v(s')$ repeatedly - over many updates - multiplying any error in the bootstrap from next state by $\gamma$, the discount factor.

For instance, what if a state that in practice had low reward is assigned a very high initial reward value in value iteration? Would the algorithm not construct a value function that highly values trajectories passing through that state?

In limited cases you can construct a combination of environment and starting value function adversarially, so that it does not converge properly. This would require that there is no discounting (or very high $gamma$ and also high $\theta$ cutoff to stop iterations early), and a set of self-consistent high start value estimates that form a loop preventing the iterations from making changes. Any single "rogue" high value estimate should quickly get reduced by the update mechanism (only exception would be a high value state that can loop to itself deterministically and without any discounting applied).

In this question, the OP constructs just such an adversarial start condition: Is the initialisation of $V(s)$ and $\pi(s)$ really arbitrary in policy iteration?

So in some senses, the initialisation is not strictly arbitrary, in that you can set up non-working examples. However, the value iteration algorithm is far more robust than your initial concerns imply, thanks to the effects described above. In addition, if you are implementing a solver then you get to choose initialisation, and can make conservative choices (e.g. don't initialise any value higher than max possible reward - there is no known benefit to doing so for dynamic programming algorithms). These choices are not strictly required, the space of working initialisations is much larger, but you are also not required to attempt to code truly arbitrary value table initialisation.