Proof By applying H2 to 
ondition 2 and expanding the result with 
ondition 2 again we get: H2 2 V 
1  H2V 
1  H1V 
1 = V 
1 . Repeating this we get in the limit V 
2      Hn 2 V 
1 
   H2 2 V 
1  H2V 
1  H1V 
1 = V 
1 , whi
h proves the result. 2

## A.2 A Ura Y Of A Lookahead Controller Based On Bounds

Theorem 7 Let bVU and bVL be upper and lower bounds of the optimal value fun
tion for the dis ounted innite-horizon problem. Let  = supb j bVU (b)  bVL(b)j = k bVU  bVLk be the maximum bound dieren e. Then the expe ted reward for a lookahead ontrol ler bV LA
,

onstru ted for either bVU or bVL, satises k bV LA  V k  (2
)
(1
)
.

Proof Let bV denotes either an upper or lower bound approximation of V 
and HLA be the value fun tion mapping orresponding to the lookahead poli y for bV . Note, that sin e the lookahead poli y always optimizes its a tions with regard to bV , H bV = HLA bV must hold.

The error of Vb LA 
an be bounded using the triangle inequality

$$\|\widehat{V}^{L A}\,-V^{*}\|\,\leq\,\|\widehat{V}^{L A}\,-\,\widehat{V}\|\,+\,\|\widehat{V}\,-V^{*}\|.$$

The rst omponent satises:

$$\begin{array}{r c l}{{\|\hat{V}^{L A}-\hat{V}\|}}&{{=}}&{{\|H^{L A}\hat{V}^{L A}-\hat{V}\|}}\\ {{}}&{{}}&{{\leq}}&{{\|H^{L A}\hat{V}^{L A}-H\hat{V}\|+\|H\hat{V}-\hat{V}\|}}\\ {{}}&{{}}&{{=}}&{{\|H^{L A}\hat{V}^{L A}-H^{L A}\hat{V}\|+\|H\hat{V}-\hat{V}\|}}\\ {{}}&{{}}&{{\leq}}&{{\gamma\,\|\hat{V}^{L A}-\hat{V}\|+\epsilon}}\end{array}$$

The inequality: kH bV  bV k   follows from the isotoni ity of H and the fa t that bV is either an upper or a lower bound. Rearranging the inequalities, we obtain: k bV LA  bV k = 
(1
)
.

The bound on the se ond term kVb  V 
k   is trivial.

Therefore, kVb LA  V 
k  [
1
(1
) + 1℄ = 
(2
) (1
)
. 2

## A.3 Mdp, Qmdp And The Fast Informed Bounds

Theorem 8 A solution for the fast informed bound approximation an be found by solving an MDP with jSjjAjjj states, jAj a tions and the same dis ount fa tor 
.

Proof Let a i be a linear fun
tion for a
tion a dening Vbi. Let i(s; a) denote parameters of the fun tion. The parameters of Vbi+1 satisfy:

$$\alpha_{i+1}{\big(}\,s,a\,{\big)}=\rho{\big(}s,a\,{\big)}+\gamma\sum_{o\,\in\,\Theta}\operatorname*{max}_{a^{\prime}\,\in\,A}\sum_{s^{\prime}\,\in\,S}P\,{\big(}\,s^{\prime},o|\,s,a\,{\big)}\alpha_{i}\,{\big(}\,s^{\prime},a^{\prime}\,{\big)}.$$

Let

$$\alpha_{i\,+1}{\big(}\,s,a\,,o{\big)}=\operatorname*{max}_{a^{\prime}\in A}\sum_{s^{\prime}\in S}P{\big(}\,s^{\prime},o|s,a\,{\big)}\alpha_{i}\,{\big(}\,s^{\prime},a^{\prime}\,{\big)}.$$
