Answers.Body: <p>Further I'll use the following notation: <span class="math-container">$V^\pi(s)$</span> would be the value of a state under some (in most cases - arbitrary) policy <span class="math-container">$\pi$</span>. There is a class of optimal policies with the same optimal value function <span class="math-container">$V^*(s)$</span>. To measure &quot;distances&quot; between different value functions the <a href="https://en.wikipedia.org/wiki/Matrix_norm#Matrix_norms_induced_by_vector_p-norms" rel="nofollow noreferrer">max norm</a> is used:
  <span class="math-container">$$\lVert V^\pi - V^{\pi'}\rVert_\infty = \max_{s \in S} \left| V^\pi(s) - V^{\pi'}(s)\right|$$</span></p>
  <p>The Bellman operator <span class="math-container">${\mathcal B}$</span> is a central concept for reasoning about RL algorithms. It takes a value function and returns a new one. (I'm using your notation there except keeping more general dependency of expected reward <span class="math-container">$R(s) = \max_aR(s,a)$</span>)
  <span class="math-container">$${\mathcal B}(V^\pi) = \max_a\left[ R(s,a) + \gamma\sum_{s'}T(s,a,s')V^\pi(s') \right]$$</span>
  The Value Iteration algorithm then starts with an arbitrary value function <span class="math-container">$V_0$</span> and iteratively applies the Bellman operator <span class="math-container">$V_t ={\mathcal B}(V_{t-1})$</span>. The <em>optimal</em> value function is the stationary point of <span class="math-container">${\mathcal B}$</span>. In other words, it satisfies the Bellman equation:
  <span class="math-container">$$V^* ={\mathcal B}(V^*)$$</span>
  Existence of such stationary point, as well as the convergence of the Value Iteration, follows from the contraction property of  <span class="math-container">${\mathcal B}$</span>:</p>
  <p><span class="math-container">$$\lVert {\mathcal B}(V^\pi) -  {\mathcal B}(V^{\pi'})\rVert_\infty \leq \gamma \lVert V^\pi - V^{\pi'}\rVert_\infty$$</span></p>
  <p>Substituting <span class="math-container">$V_{t-1}$</span> and <span class="math-container">$V_{t-2}$</span> into the inequality above, we get:</p>
  <p><span class="math-container">$$\lVert V_t -  V_{t-1}\rVert_\infty \leq \gamma \lVert V_{t-1} - V_{t-2}\rVert_\infty$$</span></p>
  <p>Iteratively applying this inequality to itself we get a useful intermediate result:</p>
  <p><span class="math-container">$$\lVert V_t -  V_{t-1} \rVert_\infty \leq \gamma^{t-1} \lVert V_1 - V_0\rVert_\infty \tag{*}\label{*}$$</span></p>
  <hr />
  <p>The expected immediate reward is assumed to be bounded by some value <span class="math-container">$R_{\max}$</span>
  <span class="math-container">$$ -R_{max} \leq R(s,a) \leq R_{max},\quad \forall s, a$$</span>
  Since for any policy, the value of a state is the expectation of the discounted sum of rewards, we can bound it with the sum of geometric series:
  <span class="math-container">$$V^\pi(s_0) = {\mathbb E}\left[R(s_0, a_0) + \gamma R(s_1, a_1) + \gamma^2 R(s_2, a_2) + \dots\right]$$</span>
  <span class="math-container">$$- (1 + \gamma + \gamma^2 + \dots) R_{max} \leq V^\pi(s_0) \leq (1 + \gamma + \gamma^2 + \dots)R_{max}$$</span>
  <span class="math-container">$$\lVert V^\pi\rVert_\infty \leq \frac{R_{max}}{1 - \gamma}$$</span>
  We can use it to bound the distance between any pair of value functions:</p>
  <p><span class="math-container">$$\lVert V^\pi - V^{\pi'}\rVert_\infty \leq \lVert V^\pi\rVert_\infty + \lVert V^{\pi'}\rVert_\infty \leq  \frac{2R_{max}}{1 - \gamma} $$</span>
  Applying this bound to  <span class="math-container">$\eqref{*}$</span> we get a convergence bound in terms of a distance from the optimal policy:
  <span class="math-container">$$\lVert V_t - V_{t-1}\rVert_\infty \leq \gamma^{t-1}\frac{2R_{max}}{1 - \gamma} \leq \epsilon $$</span></p>
  <p>Solving for (an integer) <span class="math-container">$t$</span> for a given <span class="math-container">$\epsilon$</span> I get the final convergence lower bound on the number of iterations:</p>
  <p><span class="math-container">$$t \geq \left\lceil \frac{\log\frac{(1-\gamma)\gamma\epsilon}{2 R_{max}}}{\log\gamma}\right\rceil$$</span>
  For your numbers (in your case <span class="math-container">$R_{max} = 5$</span>) I get <span class="math-container">$t \geq 67$</span> steps. Note that the whole thing doesn't depend on number of states and actions.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-18T23:54:43.757Z
Answers.LastActivityDate: 2023-02-24T17:33:39.370Z
Answers.LastEditDate: 2023-02-24T17:33:39.370Z
Answers.UserDisplayName: Kostya
Body: <p>I learned about the Value Iteration algorithm which can help find an optimal policy and values of an MDP with state rewards:</p>
  <p><span class="math-container">$$V_0(s)=R(s)$$</span></p>
  <p><span class="math-container">$$V_{t}(s)=R(s)+\gamma\cdot\underset{a}{max}\underset{s'}{\sum}T(s, a, s')\cdot V_{t-1}(s')$$</span></p>
  <p>How can I find an upper bound on the number of iterations required to have less than <span class="math-container">$\varepsilon$</span> difference in the value of state <span class="math-container">$s$</span> (i.e <span class="math-container">$|V_t(s)-V_{t-1}(s)|\le\varepsilon$</span>)?</p>
  <p>For example, suppose I have an MDP with 10 states, where in each state there are 2 actions and each action can lead to 3 states. The reward of each state is between 0 and 5, <span class="math-container">$\gamma=0.9$</span> and <span class="math-container">$\varepsilon=0.1$</span>.</p>
  <p>How can I find an upper bound for the number of iterations? I tried to solve the equations <span class="math-container">$0.9^t=0.1$</span>, but this is not the right way to do it.</p>
  
Tags: <markov-decision-process><value-iteration>
Title: How can I find an upper bound on the number of iterations required to have less than $\varepsilon$ difference in the value of state?
UserDisplayName: Daniel
ThreadText: # How can I find an upper bound on the number of iterations required to have less than $\varepsilon$ difference in the value of state?
  
  (Asked by: username_0 on 2023-02-18)
  
  I learned about the Value Iteration algorithm which can help find an optimal policy and values of an MDP with state rewards:
  
  $$V\_0(s)=R(s)$$
  
  $$V\_{t}(s)=R(s)+\gamma\cdot\underset{a}{max}\underset{s'}{\sum}T(s, a, s')\cdot V\_{t-1}(s')$$
  
  How can I find an upper bound on the number of iterations required to have less than $\varepsilon$ difference in the value of state $s$ (i.e $|V\_t(s)-V\_{t-1}(s)|\le\varepsilon$)?
  
  For example, suppose I have an MDP with 10 states, where in each state there are 2 actions and each action can lead to 3 states. The reward of each state is between 0 and 5, $\gamma=0.9$ and $\varepsilon=0.1$.
  
  How can I find an upper bound for the number of iterations? I tried to solve the equations $0.9^t=0.1$, but this is not the right way to do it.
  
  **Tags:** markov-decision-process, value-iteration
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-02-18. Score: 1
  
  Further I'll use the following notation: $V^\pi(s)$ would be the value of a state under some (in most cases - arbitrary) policy $\pi$. There is a class of optimal policies with the same optimal value function $V^\*(s)$. To measure "distances" between different value functions the [max norm](https://en.wikipedia.org/wiki/Matrix_norm#Matrix_norms_induced_by_vector_p-norms) is used:
  $$\lVert V^\pi - V^{\pi'}\rVert\_\infty = \max\_{s \in S} \left| V^\pi(s) - V^{\pi'}(s)\right|$$
  
  The Bellman operator ${\mathcal B}$ is a central concept for reasoning about RL algorithms. It takes a value function and returns a new one. (I'm using your notation there except keeping more general dependency of expected reward $R(s) = \max\_aR(s,a)$)
  $${\mathcal B}(V^\pi) = \max\_a\left[ R(s,a) + \gamma\sum\_{s'}T(s,a,s')V^\pi(s') \right]$$
  The Value Iteration algorithm then starts with an arbitrary value function $V\_0$ and iteratively applies the Bellman operator $V\_t ={\mathcal B}(V\_{t-1})$. The *optimal* value function is the stationary point of ${\mathcal B}$. In other words, it satisfies the Bellman equation:
  $$V^\* ={\mathcal B}(V^\*)$$
  Existence of such stationary point, as well as the convergence of the Value Iteration, follows from the contraction property of ${\mathcal B}$:
  
  $$\lVert {\mathcal B}(V^\pi) - {\mathcal B}(V^{\pi'})\rVert\_\infty \leq \gamma \lVert V^\pi - V^{\pi'}\rVert\_\infty$$
  
  Substituting $V\_{t-1}$ and $V\_{t-2}$ into the inequality above, we get:
  
  $$\lVert V\_t - V\_{t-1}\rVert\_\infty \leq \gamma \lVert V\_{t-1} - V\_{t-2}\rVert\_\infty$$
  
  Iteratively applying this inequality to itself we get a useful intermediate result:
  
  $$\lVert V\_t - V\_{t-1} \rVert\_\infty \leq \gamma^{t-1} \lVert V\_1 - V\_0\rVert\_\infty \tag{\*}\label{\*}$$
  
  ---
  
  The expected immediate reward is assumed to be bounded by some value $R\_{\max}$
  $$ -R\_{max} \leq R(s,a) \leq R\_{max},\quad \forall s, a$$
  Since for any policy, the value of a state is the expectation of the discounted sum of rewards, we can bound it with the sum of geometric series:
  $$V^\pi(s\_0) = {\mathbb E}\left[R(s\_0, a\_0) + \gamma R(s\_1, a\_1) + \gamma^2 R(s\_2, a\_2) + \dots\right]$$
  $$- (1 + \gamma + \gamma^2 + \dots) R\_{max} \leq V^\pi(s\_0) \leq (1 + \gamma + \gamma^2 + \dots)R\_{max}$$
  $$\lVert V^\pi\rVert\_\infty \leq \frac{R\_{max}}{1 - \gamma}$$
  We can use it to bound the distance between any pair of value functions:
  
  $$\lVert V^\pi - V^{\pi'}\rVert\_\infty \leq \lVert V^\pi\rVert\_\infty + \lVert V^{\pi'}\rVert\_\infty \leq \frac{2R\_{max}}{1 - \gamma} $$
  Applying this bound to $\eqref{\*}$ we get a convergence bound in terms of a distance from the optimal policy:
  $$\lVert V\_t - V\_{t-1}\rVert\_\infty \leq \gamma^{t-1}\frac{2R\_{max}}{1 - \gamma} \leq \epsilon $$
  
  Solving for (an integer) $t$ for a given $\epsilon$ I get the final convergence lower bound on the number of iterations:
  
  $$t \geq \left\lceil \frac{\log\frac{(1-\gamma)\gamma\epsilon}{2 R\_{max}}}{\log\gamma}\right\rceil$$
  For your numbers (in your case $R\_{max} = 5$) I get $t \geq 67$ steps. Note that the whole thing doesn't depend on number of states and actions.
  
  
  ---
  
  