1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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