BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI

TRIỆU THU THỦY

MÔ HÌNH ĐIỀU KHIỂN MARKOV RỜI RẠC
VỚI THỜI GIAN VÔ HẠN

Chuyên ngành :

LÝ THUYẾT XÁC SUẤT VÀ THỐNG KÊ TOÁN HỌC

Mã số : 60. 46 .01.06

LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học:

TS. NGUYỄN HỒNG HẢI

HÀ NỘI - 2017


Mục lục
Lời cam đoan . . . . . . . . . . . . . . . . . . . . . . . . . . .
Phần mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . .
Lời cảm ơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 Kiến thức chuẩn bị
1.1 Quá trình Markov và xích Markov . . . . . . . . . . . .
1.2 Mô hình điều khiển Markov . . . . . . . . . . . . . . . .
1.2.1 Định nghĩa mô hình điều khiển Markov . . . . .
1.2.2 Chiến lược điều khiển . . . . . . . . . . . . . . .

2.4 Chiến lược lặp và xấp xỉ giá tối ưu . . . . . . . . . . . . . .
2.4.1 Xấp xỉ hàm giá bị chặn . . . . . . . . . . . . . . . .
2.4.2 Xấp xỉ đệ quy giá bị chặn . . . . . . . . . . . . . . .
2.4.3 Chiến lược lặp . . . . . . . . . . . . . . . . . . . .
2.5 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . .
2.6 Tiệm cận tối ưu . . . . . . . . . . . . . . . . . . . . . . . .
2.6.1 Định nghĩa tiệm cận tối ưu . . . . . . . . . . . . . .
2

4
5
8
9
9
10
10
11
12
13
13
15

19
19
20
20
21
27
31
32

50
50
51
51
51
52
55

Kết luận

61

Tài liệu tham khảo

62

3


Lời cam đoan
Tôi xin cam đoan bản luận văn này là kết quả nghiên cứu của cá nhân
tôi. Các số liệu và tài liệu được trích dẫn trong luận văn là trung thực.
Kết quả nghiên cứu này không trùng với bất cứ công trình nào đã được
công bố trước đó.
Tôi chịu trách nhiệm với lời cam đoan của mình.
Hà Nội, ngày 05 tháng 6 năm 2017
Tác giả luận văn
Triệu Thu Thủy

4

lim ExU
n→∞

n

rk (xk , µk ) .
k=1

Kết quả chính thu được của luận văn là đưa ra phương trình tối ưu
dạng Bellman, nêu định nghĩa, điều kiện tồn tại và cách xác định chiến
lược điều khiển tối ưu và giá tối ưu.
Ngoài ra, chúng tôi xây dựng mô hình quá trình ngẫu nhiên rời rạc điều
khiển được trên khoảng thời gian vô hạn.
Với những lý do trên, dưới sự hướng dẫn tận tình của TS. Nguyễn Hồng
Hải, tôi đã chọn luận văn thạc sĩ mang tên Mô hình điều khiển Markov
rời rạc với thời gian vô hạn.

II. MỤC ĐÍCH NGHIÊN CỨU
Giới thiệu mô hình điều khiển quá trình Markov rời rạc với thời gian
vô hạn. Cụ thể là phương trình tối ưu Bellman, nghiên cứu giá tối ưu và
5


chiến lược tối ưu với hai dạng hàm giá: dạng suy giảm và dạng trung bình
trên khoảng thời gian vô hạn.

III. ĐỐI TƯỢNG NGHIÊN CỨU
• Mô hình điều khiển Markov.
• Mô hình điều khiển Markov rời rạc với thời gian vô hạn.
• Phương trình tối ưu Bellman, giá tối ưu và chiến lược điều khiển tối

Markov với bước nhảy Poisson liên quan đến quá trình semi Markov.

7


Lời cảm ơn
Trong quá trình học tập, nghiên cứu và hoàn thành luận văn "Mô
hình điều khiển Markov rời rạc với thời gian vô hạn", tôi đã nhận
được sự hướng dẫn, giúp đỡ và động viên của nhiều cá nhân và tập thể,
tôi xin được bày tỏ lòng biết ơn tới tất cả các cá nhân và tập thể đã tạo
điều kiện giúp đỡ tôi.
Đầu tiên, tôi xin bày tỏ lòng biết ơn chân thành tới các thầy cô giáo
trong khoa Toán, đặc biệt là các thầy trong Bộ môn Toán ứng dụng Trường Đại học Sư phạm Hà Nội đã mang đến cho tôi những kiến thức bổ
ích trong những năm học vừa qua và trong công việc sắp tới.
Tôi xin gửi lời cảm ơn sâu sắc đến TS. Nguyễn Hồng Hải - Người thầy đã
trực tiếp hướng dẫn, tận tình chỉ bảo, giúp đỡ tôi trong quá trình nghiên
cứu và hoàn thành luận văn.
Cuối cùng tôi xin gửi lời cảm ơn đến gia đình, bạn bè đã luôn ở bên tôi,
động viên và khuyến khích tôi trong quá trình thực hiện đề tài nghiên cứu
của mình.
Tôi rất mong nhận được những ý kiến đóng góp của các thầy cô, bạn bè
và những người quan tâm để luận văn được hoàn thiện và phát triển hơn.
Tôi xin chân thành cảm ơn!
Hà Nội, ngày 05 tháng 6 năm 2017
Triệu Thu Thủy

8


Chương 1



+ Nếu xích Markov có t ∈ [0, +∞) thì Xt được gọi là Xích Markov với
thời gian liên tục.
+ Nếu xích Markov có t ∈ N thì Xt được gọi là Xích Markov với thời
gian rời rạc.
Định nghĩa 1.1.2. Xét {Xt } là xích Markov với thời gian rời rạc. Đặt:

p(s, i, t, j) = P{X(t) = j|X(s) = i}, (s < t)
là xác suất để thời điểm s xích ở trạng thái i, đến thời điểm t chuyển sang
trạng thái j , được gọi tắt là xác suất chuyển.
Nếu xác suất chuyển chỉ phụ thuộc vào (t − s) tức là,

p(s, i, t, j) = p(s + h, i, t + h, j) với ∀h > 0
thì ta xích Markov rời rạc là thuần nhất theo thời gian.

1.2
1.2.1

Mô hình điều khiển Markov
Định nghĩa mô hình điều khiển Markov

Trước khi định nghĩa quá trình điều khiển Markov, ta có một số quy
ước và ký hiệu sau:
Không gian Borel: X là một không gian Borel nếu X là một không gian
metric đầy, khả ly và σ− đại số sinh bởi các tập con mở của X là σ− đại
số Borel, kí hiệu là B(X).
Hàm đo được: Xét hai không gian đo (X, B(X)) và (E, B(E)). Một hàm
số f : X → E gọi là đo được hay là "Borel đo được" nếu f −1 (A) ∈ B(X)
với mọi A ∈ B(E)

Giải thích sự hoạt động của mô hình
Tại thời điểm t, hệ thống có:
+ Trạng thái xt = x ∈ X
+ Điều khiển at = a ∈ A(x)
+ Khi đó hàm giá là c(x, a).
+ Đến thời điểm t + 1 quá trình chuyển sang trạng thái xt+1 là một biến
ngẫu nhiên nhận giá trị trên X với phân phối Q(.|x, a) tức là:

Q(B|x, a) := P (xt+1 ∈ B|xt = x, at = a) với B ⊂ X.
1.2.2

Chiến lược điều khiển

Xét mô hình điều khiển Markov trong định nghĩa 1.2.1. Với ∀t = 0, 1, ...
ta xác định không gian Ht - lịch sử (admissiable histories) đến thời điểm
t như sau: Giả sử H0 := X , và

Ht := Kt × X = K × Ht−1 , t = 1, 2, ...
11

(1.4)


trong đó K được cho bởi (1.3).
Mỗi phần tử ht ∈ Ht là một vectơ có dạng:

ht = (x0 , a0 , ..., xt−1 , at−1 , xt ),

(1.5)


Ω = (X × A)∞ = {(xn , an )|xn ∈ X, an ∈ A với n = 0, 1, 2, ...}.
Giả sử π = (πt ) là một chiến lược điều khiển bất kì và ν là độ đo xác
suất tùy ý trên X được gọi là "phân phối ban đầu".
Kí hiệu Pνπ là độ đo xác suất trên Ω cảm sinh bởi chiến lược π =
(π1 , π2 , ...) với điều kiện ν .
Khi đó theo định lý Ionescu - Tulcea thì Pνπ tồn tại và duy nhất, ngoài ra
nó thỏa mãn Pνπ (H∞ ) = 1 và với ∀B ∈ B(X), C ∈ B(A) và ht ∈ Ht , t =

12


0, 1, 2, ... thì
Pνπ (x0 ∈ B) = ν(B)

(1.8)

Pνπ (at ∈ C|ht ) = πt (C|ht )

(1.9)

Pνπ (xt+1 ∈ B|ht , at ) = Q(B|xt , at )

(1.10)

Định nghĩa 1.2.3. Quá trình ngẫu nhiên (Ω, F, Pνπ , {xt }) được gọi là một
quá trình điều khiển Markov thời gian rời rạc (hoặc quá trình quyết định
Markov).
Từ định nghĩa ta thấy quá trình {xt } ∈ X phụ thuộc vào chiến lược π
và phân phối ban đầu ν
Mặt khác,ta gọi họ


Φ := {ϕ ∈ P(A|X)|ϕ(A(x)|x) = 1, ∀x ∈ X}
Đặt F là tập hợp tất cả các hàm số đo được f : X → A sao cho
f (x) ∈ A(x) với ∀x ∈ X .
F = {f : X → A|f đo được và f (x) ∈ A(x) với ∀x ∈ X}.
Ta có F = ∅ và Φ = ∅.
Một hàm số f ∈ F có thể được xác định với một hạt nhân ngẫu nhiên
ϕ ∈ Φ, vì thế ϕ(.|x) là đo được tại f (x) với ∀x ∈ X ,

ϕ(C|x) = IC [f (x)], ∀x ∈ X, C ∈ B(A)
ở đó IC là hàm chỉ tiêu của C . Vì thế, chúng ta có thể thấy rằng F là một
tập con của Φ,
F ⊂ Φ.
(1.11)
Định nghĩa 1.3.2. Một chiến lược π = {πt } ∈ Π được gọi là:
(a) Một chiến lược Markov ngẫu nhiên (randomized Markov policy) nếu
tồn tại một dãy {ϕt } các hạt nhân ngẫu nhiên ϕt ∈ Φ sao cho:

πt (.|ht ) = ϕt (.|xt ), ∀ht ∈ Ht , t = 0, 1, ...;

(1.12)

(b) Một chiến lược ngẫu nhiên dừng (randomized stationary policy) nếu
tồn tại một hàm ϕ ∈ Φ sao cho

πt (.|ht ) = ϕ(.|xt ), ∀ht ∈ Ht , t = 0, 1, ...;
Tập hợp tất cả các chiến lược Markov ngẫu nhiên ký hiệu là ΠRM , tập các
chiến lược ngẫu nhiên dừng ký hiệu là ΠRS .
Ta thấy:
ΠRS ⊂ ΠRM ⊂ Π

Q(.|x, a)ϕ(da|x)

(1.14)

A

và

Q(.|x, ϕ) :=
A

Đặc biệt nếu với f ∈ F(⊂ Φ) thì công thức (1.13) và (1.14) trở thành:

c(x, f ) = c(x, f (x))
và

Q(B|x, f ) = Q(B|x, f (x))
1.3.2

Quá trình điều khiển Markov rời rạc thuần nhất

Xét quá trình điều khiển Markov rời rạc {yt } trên không gian trạng thái
X với dãy hạt nhân {Rt } tương ứng. Khi đó ta có tính Markov được viết
thành: với mọi B ∈ B(X) và t = 0, 1, 2, ... thì

P (yt+1 ∈ B|y0 , ..., yt ) = P (yt+1 ∈ B|yt ) = Rt (B|yt )

(1.15)

Nếu Rt = R là tất định thì {yt } được gọi là một quá trình điều khiển

Q(B|xt , at )πt (dat |ht )

=
A

Vậy ta chứng minh được (1.17).
Đặc biệt, nếu π = {ϕt } là một chiến lược Markov ngẫu nhiên, π ∈ ΠRM
thì (1.17) trở thành:

Pνπ (xt+1 ∈ B|ht ) =

Q(B|xt , at )ϕt (dat |xt ) = Q(B|xt , ϕt )

(1.18)

A

vì Q(.|x, ϕ) được xác định trong (1.14). Đặt xt0 = (x0 , x1 , ..., xt ) ta có:

Pνπ (xt+1 ∈ B|xt0 ) = Eνπ [Pνπ (xt+1 ∈ B|ht )|xt0 ]
= Eνπ [Q(B|xt , ϕt )|xt0 ]
= Q(B|xt , ϕt )
16


ở đó, tiếp tục áp dụng tương tự, trong trường hợp này (1.16) thỏa mãn:

Pνπ (xt+1 ∈ B|xt ) = Eνπ [Pνπ (xt+1 ∈ B|ht )|xt ]
= Eνπ [Q(B|xt , ϕt )|xt ]
= Q(B|xt , ϕt )


(1.23)

quy ước Q1 (.|., ϕ) = Q(.|., ϕ) và

Qn (B|x, ϕ) =
=

Q(B|y, ϕ)Qn−1 (dy|x, ϕ)

(1.24)

Qn−1 (B|y, ϕ)Q(dy|x, ϕ), với n ≥ 1

(1.25)

(c) Với mô hình điều khiển Markov với chiến lược π = {at } và trạng thái
ban đầu x0 = x. Thông thường có 2 dạng hàm giá phổ biến:
Thứ nhất: hàm giá dạng suy giảm:
∞

V (π, x) :=

Exπ

αt .c(xt , at ) , π ∈ Π, x ∈ X
t=0
17



xác định chiến lược tối ưu và giá tối ưu.

18


Chương 2

Bài toán điều khiển ngẫu nhiên
dạng hàm giá suy giảm với thời
gian vô hạn
2.1

Một số khái niệm mở đầu

Cho mô hình điều khiển Markov (X, A, {A(x)|x ∈ X}, Q, c). Nội dung
chính của chương này là tìm giá trị nhỏ nhất của hàm giá dạng suy giảm
với thời gian vô hạn:
∞

V (π, x) :=

Exπ

αt .c(xt , at ) , π ∈ Π, x ∈ X

(2.1)

t=0

ở đó α ∈ (0, 1) là một hệ số cho trước gọi là tham số suy giảm hoặc tỷ lệ

2.2
2.2.1

(2.4)

Phương trình tối ưu dạng Bellman
Định nghĩa nghiệm của phương trình tối ưu Bellman

Định nghĩa 2.2.1. Một hàm đo được v : X → R được gọi là một nghiệm
của phương trình tối ưu dạng Bellman nếu nó thỏa mãn:

v(y)Q(dy|x, a) , ∀x ∈ X.

v(x) = min c(x, a) + α
A(x)

(2.5)

X

Ta sẽ chứng minh rằng V ∗ là nghiệm của phương trình tối ưu Bellman,
tức là

V ∗ (x) = min c(x, a) + α

V ∗ (y)Q(dy|x, a)

A(x)

X

A(x)

Jt+1 (y)Q(dy|x, a)]
X

Đặt: Vt (.) := α−t .Jt (.) với t = 0, 1, 2, ..., n thì Vn (x) = cn (x) và với t =
n − 1, n − 2, ..., 0 ta có:

Vt (x) := min c(x, a) + α
A(x)

Vt+1 (y)Q(dy|x, a)]
X

20


Tiếp tục đặt vt (.) := Jn−t (.) với t = 0, 1, ..., n thì

v0 (x) := cn (x) = 0,
vt (x) := min c(x, a) + α
A(x)

vt−1 (y)Q(dy|x, a)
X

vn (x) = inf J(π, x).
Π

Vậy ta có:

đó, thì chúng ta chuyển thành bài toán tối ưu với cách đặt c := c − m,
hàm không âm.
Giả thiết 2.2.3. Tồn tại một chiến lược π sao cho

V (π, x) < ∞ với ∀x ∈ X.
Ký hiệu Π0 := {π ∈ Π|V (π, x) < ∞, ∀x ∈ X}.
Ta thấy nếu c là bị chặn thì Π = Π0 , bởi vì nếu tồn tại hằng số dương
21


M sao cho 0 ≤ c ≤ M thì
∞

0 ≤ V (π, x) ≤

Exπ

∞
t

αt =

α .M = M.
t=0

t=0

M

là chiến lược tối ưu thì nó thỏa mãn (2.11);
(c) Nếu π ∗ là một chiến lược sao cho V (π ∗ , .) là một nghiệm của phương
trình tối ưu Bellman và thỏa mãn

lim αn Exπ V (π ∗ , xn ) = 0, với ∀π ∈ Π0 , x ∈ X

n→∞

(2.12)

thì V (π ∗ , .) = V ∗ (.) cho nên π ∗ là chiến lược tối ưu. Nói cách khác, nếu
π ∗ thỏa mãn phương trình (2.12) thì nó là chiến lược tối ưu khi và chỉ khi
V (π ∗ , .) thỏa mãn phương trình tối ưu Bellman.
(d) Nếu tồn tại một chiến lược tối ưu thì trong đó tồn tại một chiến lược
không ngẫu nhiên (thuộc ΠDS ).
Để chứng minh định lý 2.2.4 ta cần chứng minh các bổ đề sau.
Bổ đề 2.2.5. Giả sử u và un (n = 1, 2, ...) là những hàm số nửa liên tục
dưới, bị chặn dưới và compact địa phương trên K. Nếu un ↑ u, thì:

lim min un (x, a) = min u(x, a), ∀x ∈ X

n→∞ A(x)

A(x)

22


Chứng minh.


M (X)+ = {u : X → R|u đo được và u(x) ≥ 0, ∀ x}.
Giả sử rằng giả thiết 2.2.2 được thỏa mãn, với ∀u ∈ M (X)+ , ta định
nghĩa toán tử T : M (X)+ → M (X)+ như sau:

u(y)Q(dy|x, a) , ∀x ∈ X

T u(x) := min c(x, a) + α
A(x)

(2.13)

X

Như vậy, T u : X → R là một hàm số trên X sao cho với ∀x ∈ X
thì T u(x) được xác định bởi (2.13). Để thuận tiện, ta sử dụng ký hiệu
T u := T u(.) với ∀x ∈ X .
23


Bổ đề 2.2.7. Hơn nữa, tồn tại một phần tử f ∈ F sao cho

u(y)Q(dy|x, f ), ∀x ∈ X

T u(x) := c(x, f ) + α

(2.14)

X

Khi sử dụng T , ta có thể viết phương trình tối ưu Bellman (2.10) và


Exf

αt c(xt , f ) + αn Exf u(xn ), ∀n ≥ 1, x ∈ X

(2.17)

t=0

trong đó

Exf u(xn ) =

u(y)Qn (dy|x, f );

Qn (.|x, f ) là n là hạt nhân tại bước thứ n của quá trình Markov {xt } ứng
với f ∈ Φ. Vì thế, u là hàm không âm và
n−1

u(x) ≥

Exf

αt c(xt , f )
t=0

24


với mọi n và x. Cho n → ∞, từ (2.1) và (2.2) ta có:

Chúng ta sẽ sử dụng bổ đề 2.2.5 để chứng minh bổ đề sau:
Bổ đề 2.2.9. (Sự hội tụ của hàm truy hồi (2.6))
Giả sử rằng giả thiết 2.2.2 được thỏa mãn, khi đó vn ↑ V ∗ và V ∗ thỏa
mãn phương trình tối ưu Bellman.
Chứng minh. Đầu tiên giả sử c ≥ 0, với ∀π ∈ Π, x ∈ X từ (2.8) ta có:

vn (x) = inf Vn (π, x) ⇒ vn (x) ≤ Vn (π, x)
Π

Mặt khác từ định nghĩa của Vn (π, x) và V (π, x) ta lại có:

Vn (π, x) ≤ V (π, x) với ∀n
vì thế ta thu được: vn (x) ≤ Vn (π, x) ≤ V (π, x). Hơn nữa, do

V ∗ (x) = inf V (π, x)
Π

25