# How can I find an upper bound on the number of iterations required to have less than $\varepsilon$ difference in the value of state?

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.

## 1 Answer

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 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.