Answers.Body: <blockquote>
  <p>Is this something to do with the Bellman optimality constraint itself?</p>
  </blockquote>
  <p>That is part of it, and important for episodic problems without discounting. The Bellman equations link between time steps, providing a <em>direction</em> 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 &quot;flood fill&quot; starting from terminal states and filling in the table with true values.</p>
  <p>In addition, when there is a discount factor (optional for episodic environments, but required for continuing ones), then this progressively <em>reduces</em> any bias in existing estimates due to the term <span class="math-container">$r + \gamma v(s')$</span> repeatedly - over many updates - multiplying any error in the bootstrap from next state by <span class="math-container">$\gamma$</span>, the discount factor.</p>
  <blockquote>
  <p>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?</p>
  </blockquote>
  <p>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 <span class="math-container">$gamma$</span> and also high <span class="math-container">$\theta$</span> cutoff to stop iterations early), and a <strong>set</strong> of self-consistent high start value estimates that form a loop preventing the iterations from making changes. Any single &quot;rogue&quot; 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).</p>
  <p>In this question, the OP constructs just such an adversarial start condition: <a href="https://ai.stackexchange.com/questions/34570/is-the-initialisation-of-vs-and-pis-really-arbitrary-in-policy-iteratio">Is the initialisation of $V(s)$ and $\pi(s)$ really arbitrary in policy iteration?</a></p>
  <p>So in some senses, the initialisation is not <em>strictly</em> 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-05T19:43:49.363Z
Answers.LastActivityDate: 2022-06-05T19:43:49.363Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <p>If the <em>value function</em> of a state <span class="math-container">$v(s)$</span> is relatively high, then you are absolutely correct in saying that a <em>greedy policy</em> may choose to visit <span class="math-container">$s$</span>, since the high <span class="math-container">$v(s)$</span> 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.</p>
  <p>Suppose that the <em>optimal value function</em> <span class="math-container">$v_*(s)$</span> of a specific state <span class="math-container">$s$</span> is low, yet the value function <span class="math-container">$v(s)$</span> is initialized much higher. Then, <strong>the update rule in the pseudocode you provided will eventually decrease</strong> <span class="math-container">$v(s)$</span> to <span class="math-container">$v_*(s)$</span>. To see this fact intuitively, note that <span class="math-container">$v(s)$</span> can be decomposed as the expected <em>return</em> (sum of rewards) from that state:
  <span class="math-container">$$v(s) = \mathbb{E}[R_k + R_{k+1} + R_{k+2} + \ldots + R_T|S_k = s].$$</span>
  If the expected return from <span class="math-container">$s$</span> is smaller than <span class="math-container">$v(s)$</span>, then <span class="math-container">$v(s)$</span> will decrease with the aforementioned update. The actual update rule approximates the expected return from <span class="math-container">$s$</span> using the next reward <span class="math-container">$R_k$</span> and the value function of the next state <span class="math-container">$v(s')$</span> via bootstrapping. Note that <span class="math-container">$v(s')$</span> can be decomposed as follows:
  <span class="math-container">$$v(s') = \mathbb{E}[R_{k+1} + R_{k+2} + \ldots + R_T|S_{k+1}=s'].$$</span>
  Therefore, <span class="math-container">$v(s')$</span> quantifies the part of the return aside from the next reward <span class="math-container">$R_k$</span>, and the update rule indeed quantifies the expected return from <span class="math-container">$s$</span>. If <span class="math-container">$v(s')$</span> is initialized too high or low, then the update rule will simultaneously be adjusting it to the optimal <span class="math-container">$v_*(s')$</span> while adjusting <span class="math-container">$v(s)$</span> closer to <span class="math-container">$v_*(s)$</span>.</p>
  <p>Once the value functions change as described above, then the greedy policy may also change and favor other states aside from <span class="math-container">$s$</span> with higher value functions.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-05T20:54:37.860Z
Answers.LastActivityDate: 2022-06-05T20:54:37.860Z
Answers.UserDisplayName: DeepQZero
Body: <p>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?</p>
  <p>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?</p>
  <p><a href="https://i.sstatic.net/yHlp9.png" rel="noreferrer"><img src="https://i.sstatic.net/yHlp9.png" alt="value iteration algorithm" /></a></p>
  
Tags: <reinforcement-learning><machine-learning><value-functions><sutton-barto><value-iteration>
Title: In Value Iteration, why can we initialize the value function arbitrarily?
UserDisplayName: Arham
ThreadText: # In Value Iteration, why can we initialize the value function arbitrarily?
  
  (Asked by: username_0 on 2022-06-05)
  
  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?
  
  [![value iteration algorithm](https://i.sstatic.net/yHlp9.png)](https://i.sstatic.net/yHlp9.png)
  
  **Tags:** reinforcement-learning, machine-learning, value-functions, sutton-barto, value-iteration
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2022-06-05. Score: 4 | Accepted answer
  
  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 by username_1 on 2022-06-05. Score: 6
  
  > 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?](https://ai.stackexchange.com/questions/34570/is-the-initialisation-of-vs-and-pis-really-arbitrary-in-policy-iteratio)
  
  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.
  
  
  ---
  
  