∼

L∞
•
•
•

Lp
•

•
∼

•
∼

•
•

Artificial intelligence
Statistics
Clustering

Statistical learning
Theory of Learning
Cognitive Sciences Neural networks Applied Mathematics
Theory of approximation

Reinforcement Learning
Neurosciences Dynamic programming

Optimal control

Categorization Automatic

Active learning

Psychology
• (Xi , Yi )i Yi=f(XI ) + i f
f f(x)

• (Xi )I

Decision agent

State Action

Reinforcement

uncertain
partially observable
Environment complex

•
•

• V(x) V(y)

V(x)
{"text":"actions"}

0.2
transition probabilities 0.3 0.5 0.7 0.2
0.1
V(y)

•V
V(x) = maxa [r(x, a) + E[V(Y)|x, a]

• V

•
• V arg maxa [r(x, a) +
E[V(Y)|x, a]

•
•

CORTEX

Reinforcement Striatum
(part of the basal ganglia)
Action
Striosome Matrisome
Perception
critic (actor)

Difference
temporal Thalamus

Dopamine
Substance
Black net Hypothalamus
•

$$$

t k rt ∼νk νk

P t rt
6$,7$,5$,4$ 5$,0$

logn/n

• '

•
•

• (xt )t∈N∈X X

P(xt+1=x|xt , xt−1 , . . . , x 0 ) =P(xt+1=x|xt )

• X x0
p(y|x) = P(xt+1=y|xt=x)

xt

• (X, A, p, r)

•X

•A

p(y|x, a) : x∈X y ∈X a∈A

p(y|x, a) = P(xt+1=y|xt=x, at=a),

r(x, a, y) x y a∈A
• πt t

πtX to A pit (x) x

πtX times A leads to R pit (a|x) a x

• π= (π0 , π1 , π2 , . . .) π
π= (π, π, π, . . .)

π (xt )t≥0 at=π(xt )

π p(y|x) = p(y|x, π(x))

•
T−1
Vπ (t, x) = E
X r(xs , πs (xs )) +R(xT|xt=x;π ,
s=t

•
∞
Vπ (x) =E t
X γ r(xt ,π(xt ))|x0=x;π ,
t=0

0≤γ<1

•
T
V π (x) = E
X r(xt ,π(xt ))|x0 =x;π ,
t=0

•
T−1
1
Vπ (x) = lim E X r(xt ,π(xt ))|x0=x;π .
T→∞ T
t=0
 2 r=1
p=0.5
1 Rest
0.4 r = -10
Rest 0.5

r=0 Work 5
Work 0.3 0.4 0.6

0.5 0.7
0.5 r=100
Rest
0.6
r = -1
Rest
0.9 6
Work
3
0.1 r = -1000
0.5
1
0.5
Work
r = -10
4 7

•
•
•

V2 = 88.3
p=0.5r=1
Rest r = -10
Repose 0.5 0.4
V1 = 88.3
V5 = −10
r=0 Work
Work 0.3 0.4 0.6

0.5 0.7
0.5 r=100
Rest
0.6
V6 = 100
r = -1 0.9
V3 = 86.9 Work
Rest

0.1 r=-1000
0.5
1
0.5 r = -10 Work
V7 = −1000
V4 = 88.9

V5-10V6= 100 V7-1000V4=−10 + 0.9V 6+ 0.1V488.9V3=−1 + 0.5V 4+ 0.5V386.9

V2= 1 + 0.7V3+ 0.3V1 V1= max{0.5V2+ 0.5V1 0.5V3+ 0.5V1 } V1=V2= 88.3

xt
Dt
at

• h(x) C(a)
• f(q) q

• g(x)

• M

• T

• Dt

• xt∈X={0,1, . . . ,M}

• at is an element
t of Ax ={0,1, . . . M−xt }

• xt+1= [xt+at-Dt ]+ p(xt+1|xt , at )

• rt =−C(at )−h(xt+at ) +f([xt+at-xt+1]+ )

T−1
• E t=1 rt +g(xT)
P

Reward it
1 2 T

p(t) Restaurant

Reward 0

• i p(i)

• t t

•
 Renf 1 Renf 2 Renf T
to keep keeper To keep

L L L Renf 0
p(2) p(T)
p(1) Cont Cont. Cont
D 1−p(1)
1−p(2) 1−p(T)
O O O Renf 0

1 2 T

•
•

1061 20 10 7

T π= (π0 , . . . , π T−1 ) x
t ∈ {0, ..., T}

T−1
Vπ (t, x) = E
X r(xs , πs (xs )) +R(xT)|xt=x;π .
s=t

V∗ (t, x) = maxVπ (t, x).

π

∗
• π∗ Vπ (t, x) = V∗ (t, x)
 V∗ (t, x)

V∗ (t, x) = max r(x, a) + X p(y|x, a)V∗ (t+ 1, y) 0≤t < T

a is an element of A
y∈X

V∗ (T, x) = R(x)

π∗
t (x) ∈ arg max r(x, a) + X p(y|x, a)V∗ (t + 1, y) 0 ≤ t < T.
a is in A
y is in X

V∗ (T, x) = R(x) V∗ t < T π=

(πt , πt+1, . . . , π T−1 ) x t π= (a, π0 ) a is an element of A

π 0= (πt+1, . . . , π T−1 )
T−1
V∗ (t, x) = max E
π X r(xs , πs (xs )) +R(xT)|xt=x;π
s=t
0
= maxr(x,
h a) + X p(y|x, a)Vπ (t + 1, y) i
(a, π0 )
y is in X

π (t+ 1, y)0
= max hr(x, a) X
+ p(y|x, a) maxV i
a∈A 0 π
y∈X

= max r(x, a) X
+ p(y|x, a)V∗ (t + 1, y).
a∈A
y is in X

0
a)Vπ (y)≤yp(y|x, a) maxπ V(y) π0
• maxπ 0 yp(y|x, 0
P P

• π̄(=π̄, . . .)
t+1 π̄ (y)
t+1 = arg maxb∈Amax (πt+2 ,...) V(b,πt+2 ,... ) (t + 1, y)

π (t+ 1, y) = 0 π̄ π 0
X p(y|x, a) maxV
π0 X p(y|x, a)V (t + 1, y) ≤ maxπ0 X p(y|x, a)V (y).
y y y

π∗
t
∗
V∗ =Vπ

V∗ (t, L) V∗ (t, O) t

V∗ (T, L) = max{T,0}=T, V∗ (T, O) = 0,

V∗ (T−1, L) = max{T−1, p(T)V∗ (T, L) + (1−p(T))V∗ (T, O)}
V∗ (t, L) = max{t, p(t + 1)V∗ (t+ 1, L) + (1−p(t+ 1))V∗ (t+ 1, O)}
 π= (π0 , π1 , . . .) π
∞
Vπ (x) = E t
X γ r(xt , πt (xt Invalid input.0=x;π ,
t=0

0≤γ<1

V∗ = sup Vπ
π=(π0 ,π1 ,...)

• π π= (π, π, . . .) Vπ

π
Vπ (x) = r(x, π(x)) + γ X p(y|x, π(x))V (y).
y

• V∗
∗
V∗ (x) = max r(x, a) + γ X p(y|x, a)V (y).
a is an element of A
y

Vπ (x) = E t
X γ r(xt ,π(xt ))|x0=x;π
t≥0

=r(x, π(x)) + E t
X γ r(xt ,π(xt ))|x0 =x;π
t≥1
t−1
=r(x, π(x)) + γX P(x1=y|x0=x;π(x0 ))E X γ r(xt π(xt ))|x1=y;π
y t≥1

=r(x, π(x)) + γX p(y|x, π(x))Vπ (y).

y

π= (a, π0 )

V∗ (x) = max E t
π X γ r(xt ,π(xt ))|x0 =x;π
t≥0

π 0
= h a) + γ X p(y|x, a)V (y) i
maxr(x,
(a,π0 )
y

π (y) 0
max r(x,h a) + γ X p(y|x, a) maxV i
a 0 π
y

= max hr(x, a) +X γ p(y|x, a)V∗ (y). i

a
y

0
a)Vπ (y)≤yp(y|x, a) maxπ V(y) π0
• maxπ 0 yp(y|x, 0
P P
 π0
• π̄ m
πx
agraV(y)
=)y(π̄ 0

π (y) = 0 π̄ π 0
X p(y|x, a) maxV
π0 X p(y|x, a)V (y)≤max π0 X p(y|x, a)V (y).
y y y

π π W ∈ RN
T T T :RN→RN
π
TW(x) = r(x, π(x)) + γX p(y|x, π(x))W(y)
y

T:RN→RN

TW(x) = max
a is r(x, a) +ofγ A
an element X p(y|x, a)W(y).
y

Vπ N rπ rπ (x) =
r(x, π(x)) Pπ N×N P π (x, y) =p(y|x, π(x))

π Vπ (I−γPπ )−1 rπ
π
Vπ T
V∗ T
π ∗ (x)∈arg maxa∈A r(x, a) + γy p(y|x, a)V∗ (y)
P

W ∈ RN
π
π k π,
lim (T)W=V
k→∞
limit (T)k W=V∗ .
k→∞

π
T T

• W1≤W2
π π
TW1≤ T W2 ,
TW1≤ T W2 .

• W1 W2
π π
||TW 1- T W2 ||∞ ≤γ||W 1-W2 ||∞ ,
||TW1− TW2 ||∞ ≤γ||W 1−W2 ||∞ .
 x is an element of X

TW1 (x)− TW2 (x)|= maxr(x, a) +γ

a X p(y|x, a)W1 (y)−maxr(x,
a
a) +γ X p(y|x, a)W2 (y)
y y

≤γmax a X p(y|x, a)|W1 (y)−W2 (y)| ≤γ||W1-W2 ||∞

y

Vπ =rπ +γPπ Vπ (I−γPπ )Vπ =rπ Pπ

<=1 (I−γPπ )
≥1−γ
π π
Vπ T T
V∗ T T
π∗ π∗
π∗ T V∗ =TV∗ =V∗ V∗ T
∗ π∗ ∗
Vπ T Vπ =V∗
π∗

Wk+1=TWk W0=W Wk
rmax
||Wk+1||∞ ≤rmax+γ||Wk ||∞ ||Wk ||∞ ≤ 1−γ k≥p

k, p → ∞
||Wk −Wp ||∞ ≤γ||Wk−1−Wp−1 ||∞ ≤ · · · ≤γp ||Wk−p-W0 ||∞ −→0
(Wk ) RN L∞
(Wk ) W̃ Wk
˜
W=TW ˜ limk→∞ Wk= limk→∞(T)k W=V∗
T
π k π
limk→∞(T)W=V

(Vk ) V0 Vk

Vk+1=TVk .

limk→∞ Vk=V∗

||Vk+1-V∗ ||=||TV k- TV∗ || ≤γ||Vk-V∗ || ≤γk+1||V0-V∗ || →0

Vk
k xk Vk+1(xk ) =TVk (xk )
Vk→V∗
 π0 k

πk Vπ k
πk+1 Vπ k
π k
πk+1(x) ∈ arg max r(x, a) + γ X p(y|x, a)V (y),
a is an element of A
y

πk+1πk
πk+1 Vπ k T V =TVπ k

Vπ =V
k π k+1

Vπ k+1 ≥
Vπ k ) π∗

πk πk+1
T T T πk+1
πk πk πk+1πk
Vπ =T
k
V ≤ TVπ =T
k
V ,
πk+1
T
πk+1 n πkπ
k
Vπ ≤limn→∞
(T )V=V k+1
.

(Vπ k ) k
k

Vπ =TV
k π k

Vπ =V
k ∗ πk

Vπ
π
π T

• (I−γPπ (V)π =rπ

O(N3 ) O(N2.807 )
π
• T V0
π
Vn+1=TVn Vn Vπ
log 1/a
O(N2 log 1/γ ) γ 1

n ((xti)t≥0, 1≤i≤n
) x i
π xt+1
• ∼
p(·|xtI,π(x))
i
t
n
1
Vπ (x)' γ t r(xti,π(x)).
i
nX X
i=1 t≥0
t

O(1/n)√
• λ
xs
rt+γV(x t+1) − V ( x t ) t
λt−s

λ= 1
λ= 0

log 1/
• O(N2 A) O( log 1/γ )
V∗

• Vπ k
πk+1

π Qπ :X×A→R

Qπ (x, a) = E t
X γ r(xt , at )|x0=x, a0=a, at =π(xt ) t≥1
t≥0

Q∗ (x, a) = maxQπ (x, a).

π

Qπ (x, a) = r(x, a) + γ X p(y|x, a)Vπ (y)

y∈X

Inπ (x) =Qπ (x, π(x))

Q∗ (x, a) = r(x, a) + γ X p(y|x, a)V∗ (y)
y is in X

V∗ =Q∗ (x, π∗ (x)) = maxQ∗ (x, a)

a is an element of A

π ∗ (x)∈arg maxa∈AQ∗ (x, a)

Qπ (x, a) = r(x, a) + γ X p(y|x, a)Qπ (y, π(y))

y is in X
∗ (y,
Q∗ (x, a) = r(x, a) + γ X p(y|x, a) maxQ b)
b is in A
y is an element of X
 π
T T

X×A

π
TW(x, a) = r(x, a) + γ X p(y|x, a)W(y, π(y))
y is in X

TW(x, a) = r(x, a) + γ X p(y|x, a) maxW(y, b)

b is an element of A
y is an element of X

π Qπ
π
T Q∗ T

• Q0 Qk+1=TQk Q∗

• π0 k

Qπ k

πk+1(x) = arg maxQπk(x, a).

a is an element of A

T
B=T-I
πk
πk+1πk
Vπ k+1 =Vπ -(γP
k
π k+1
-I)−1 [T V -Vπ
k
]
k k
=Vπ −[B0 ]−1 BVπ

π
Vπ k+1 =(I−γP k+1
) −1 rπ k+1
-Vπ +Vπ
k k

=Vπ + (I−γPπ
k k+1
) −1 [rπ k+1
+ (γPπ k+1
−I)Vπ
k
]

B
 TV-V
Tπ 1V−V

π
T 2V−V

π
T 3V−V

V
π π2 π
V1 V V 3= V*

πk
Vπ k T -I V → TV - V = maxπ T π V−V
V0 TV0-V0greater than or equal to 0

V∗ V V≥
TV
V≥ TV =⇒ V≥lim (T)k V=V∗ .
k→∞

V∗

• P xV(x)

• RN

V(x) ≥ r(x, a) + γ X p(y|x, a)V(y), ∀x∈X, ∀a∈A

y

N N× |A|

π
∞
Vπ (x) = E
X r(xt ,π(xt ))|x0=x;π ,
t=0

0
 π n
n
ρπ = maxP(xn = 0|x0=x, π)<1.
x

P(x2n = 0 |x 0 =x, π) =P(x2n= 0 |x n= 0, π)×P(xn = 0 |x 0=

x, π)≤ρπ2 P(xt= 0 |x 0 =x, π)≤ρbt/nc
π 1

bt/nc .
||Vπ || ≤ X ρπ rmax
t≥0

π Vπ

V∗
W∈RN
T

TW(x) = max
a is r(x, a) +of A X p(y|x, a)W(y)].
an element
y

W ∈ RN
V∗ = limk→∞(T)k W

T L L∞
∞
µ |W(x)|
||W||µ maxx∈X µ(x)

µ greater than 0

β <1 For all x, y in XNFor all a in A

X p(y|x, a)µ(y) ≤ βµ(x).

y

π
T T L∞ µ

||TW1− TW2 ||µ ≤β||W1-W2 ||µ

µ
1
µ

µ(x) = 1 + max X p(y|x, a)µ(y).

a
y
µ(x)≥1 a ∈ A µ(x) ≥ 1 + y p(y|x, a)µ(y).
P

X p(y|x, a)µ(y)≤µ(x)−1≤βµ(x)
y

µ(x)−1
β= max <1.
x µ(x)

T L ∞,µ

|TW1 (x) - TW2 (x)|

TW1− TW2 ||µ max x µ(x)
p(y|x, a)
P y
≤maxx,a µ(x) |W1 (y)−W2 (y)|
yp(y|x, a)µ(y)
P
≤maxx,a µ(x) kW1-W2 kµ

≤βkW1-2 kµ