Up the Down Staircase: Hierarchical Reinforcement Learning - Realtime Data Mining - page 108

The remainder of the proof is by bounding the additive terms on the right-hand
side of the above equation separately:

I LRAL 1

1 δ

1

RA kk 1 E ðÞ

RAL 1 1 þ kk 1 kk 1 A γε

1

0 1

1

kk 1
1 αγ

@ A γε:

¼ 1 þ

Moreover, row stochasticity of P implies that (cf. Eq. (3.2.4) in [Pap11])

0 1

X
j∈ n \ i e

1 ¼ max
i

I γP

@ A

j 1 γe p ii j þ γ p ij

∈ n

i ∈ n 1 γe

Þ

¼ max j p ii j þ γ ð 1 e p ii

,

¼ 1 þ γ 1 2 min

i ∈ n e

p ii

which, by definition of A , gives rise to

1 q ðÞ T

A

¼ max
k∈ m

I n k αγ ¼ 1 þ 1 2 c ð Þαγ

1

1

21 αγ ð c Þ

1

E ðÞ

γε:

1 αγ

As for E (2) , we obtain

L kk 1
1 α

1
1 αγ γεγ:

1

E ðÞ kk 1 kk 1 ¼

y δ

Finally, we bound kE (3) k ∞ ε < γ 1 1 αγ as follows: the assumption that ð Þ

yields

1
RAL 1

k 1 δ kk 1 γε 1 αγ ¼ k R δ AL :

1

Hence, RAL and RAL satisfy the hypothesis of Theorem 2.7.2 in [GVL96,
pp. 80-86], and we may apply the perturbation provided therein to establish