Database Reference
In-Depth Information
6.2.3 Model-Free Case: TD with Additive Preconditioner
We would now like to deploy the multilevel approach to accelerate the TD
(
)-method. To this end, we invoke the approach of a so-called preconditioner,
which we shall present in the following.
We consider the inter-level operators
I
lþ1
,
I
lþ
l
as described in Sect.
6.2.1
.
Moreover, let
I
l
be the prolongator from level
l
to level
m
defined as
I
l
¼ I
m
1
I
m
1
λ
I
l
1
l
...
,
ð
6
:
16
Þ
m
2
and
I
l
is stipulated to be the identity matrix. Let a preconditioner
C
1
t
be given by
¼
X
L
l¼
0
β
l
,
t
I
l
I
0
:
C
1
t
ð
6
:
17
Þ
It is summarized in Algorithm 6.3.
Algorithm 6.3: BPX preconditioner (Ziv)
Input: residual
y
, number of grids
L,
interpolator
I
lþ
1
, restrictor
I
lþ
1
, coefficient
l
vectors
β
l
Output: new guess
x
n
∈
R
1: procedure BPX(
y
)
2:
x
0
:
¼ y
3:
for
k ¼
1,
...
,
L
do
x
l
:
¼ I
l
1
x
l
1
4:
restriction
⊲
5:
end for
6:
for
k ¼
0,
...
,
L
do
x
l
:
¼ β
l
x
l
7:
⊲
scaling
8:
end for
for
k ¼ L
,
...
9:
,1do
x
l
1
:
¼ I
l
1
l
x
l
10:
interpolation
⊲
11: end for
12: return
x
0
13: end procedure
The preconditioner of Ziv (
6.17
) can be viewed as an algebraic counterpart to the
BPX preconditioner [BPX90] well known in numerical analysis.
Then the preconditioned TD(
λ
)-method (for simplicity we avoid the iteration
indexes)
:¼ w þ α
t
C
1
t
w
z
t
d
t
ð
6
:
18
Þ
converges almost surely to the same solution as the TD(
)-method (
3.20
).
The proof of convergence is essentially based on the subsequent theorem from
[Ziv04], a further generalization of which has been devised in [Pap10].
λ