I learned about the Value Iteration algorithm which can help find an optimal policy and values of an MDP with state rewards:


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .