TRẦN QUỐC KIỆT

TRƯỜNG ĐẠI HỌC VINH

TRẦN QUỐC KIỆT

TOÁN HỌC TĂNG CƯỜNG
KHĨA 23
VÀ ỨNG DỤNG TRONG BÀI TỐN TÌM ĐƯỜNG ĐI CHO ROBOT

THUẬT TOÁN HỌC TĂNG CƯỜNG VÀ ỨNG DỤNG TRONG BÀI
TỐN TÌM ĐƯỜNG ĐI CHO ROBOT

LUẬN VĂN THẠC SĨ CƠNG NGHỆ THÔNG TIN

NGHỆ AN, 3/2017


TRƯỜNG ĐẠI HỌC VINH

TRẦN QUỐC KIỆT

THUẬT TOÁN HỌC TĂNG CƯỜNG VÀ ỨNG DỤNG TRONG BÀI
TỐN TÌM ĐƯỜNG ĐI CHO ROBOT

CHUN NGÀNH: CÔNG NGHỆ THÔNG TIN
MÃ SỐ: 60.48.02.01
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

Người hướng dẫn khoa học: TS.Trần Xuân Sang

NGHỆ AN, 3/2017


1

LỜI CẢM ƠN

Trong suốt quá trình học tập cũng như quá trình làm luận văn, em đã
nhận được sự quan tâm của Ban giám hiệu trường Đại Học Vinh, Ban Giám
Hiệu trường Đại học Kinh Tế Công Nghiệp Long An, sự giúp đỡ của các thầy
cô giáo trong khoa Công Nghệ Thông Tin khoa sau Đại Học trường Đại học
Trường Đại học Vinh, khoa Liên kết Trường Đại học Kinh Tế Công Nghiệp
Long An. Đặc biệt là sự hướng dẫn tận tình của thầy giáo hướng dẫn TS Trần
Xuân Sang. Với lịng biết ơn sâu sắc cơ trưởng khoa CNTT TS. Phan Lê Na,
thầy phó khoa CNTT TS. Hồng Hữu Việt đã giúp đỡ để em hoàn thành luận
văn thạc sỹ khoa học này.
Em cũng xin gửi lời cảm ơn tới ban lãnh đạo, các đồng nghiệp nơi em
đang công tác đã tạo điều kiện giúp em, cảm ơn các bạn ban cán sự lớp cao
học CNTT khóa 23 Long An đã cũng em có khoảng thời gian học tập rất bổ
ích. Cuối cùng, em xin gửi lời cảm ơn tới gia đình, bạn bè, những người thân
đã ln động viên và chia sẻ cũng em trong suốt thời gian học tập.


2

LỜI CAM ĐOAN
Tôi xin cam đoan luận văn này là do tự bản thân thực hiện và là sản
phẩm của riêng tôi. Các số liệu và tài liệu trong luận văn là trung thực, các tin
thứ cấp sử dụng trong luận văn là có nguồn gốc và được trích dẫn rõ ràng.
Tơi hồn tồn chịu trách nhiệm về tính xác thực và nguyên bản của luận

văn.
Học viên thực hiện
Tác giả
Trần Quốc Kiệt


3

MỤC LỤC
LỜI CẢM ƠN

Trang
1

LỜI CAM ĐOAN

2

MỤC LỤC

3

DANH MỤC CÁC TỪ VIẾT TẮT

5

DANH MỤC CÁC BẢNG
DANH MỤC CÁC HÌNH
MỞ ĐẦU


5
6
7

1. Lý do chọn đề tài.

7

2. Lịch sử vấn đề

7

3. Đối tượng và phạm vi nghiên cứu

7

NỘI DUNG
Chương 1 TỔNG QUAN
1.1. Đặt vấn đề

10
10
10

1.2. Phát biểu bài toán cây quyết định markov.

10

1.2.2. Các thành phần củamơ hình Markov


15

1.2.3. Phương pháp học tăng cường
1.2.4. Phân loại thuật toán học tăng cường

17
18

1.3. Tổng quan về tình hình nghiên cứu

19

Chương 2 CÁC THUẬT TỐN HỌC TĂNG CƯỜNG
2.1. Tổng quan về phương pháp học tăng cường

20
20

2.1.1. Phương pháp Monte Carlo (MC)

20

2.1.2. Phương pháp MC on-policy
2.1.3. Phương pháp MC off-policy

22
22

2.2. Phương pháp Temporal Difference (TD)


23

2.2.1. Thuật toán Q-learning

24

2.2.2. Thuật toán Sarsa (state, action, reward, state, action)

25

2.2.3. Thuật toán Dyna-Q

26

Chương 3 THIẾT KẾ HỆ THỐNG THỬ NGHIỆM
30
3.1. Bài tốn mơ phỏng tìm đường đi ngắn nhất cho robot mơi trường 2x3 28
3.1.1. Mơ hình hóa mơi trường

28

3.1.2. Trạng thái và hành động để đi đến mục tiêu.

29


4

3.1.3. Thực hiện một vài bước của thuật toán Q-Learning


31

3.1.4. Kết quả kiểm thử với mã code Matlab
36
3.2. Bài toán mơ phỏng tìm đường đi ngắn nhất cho robot mơi trường 5x5 38
3.2.1. Môi tả môi trường

38

3.2.2 Sự hội tụ của bài tốn

39

3.3. Đánh giá mơ phỏng dự trên các thuật tốn Q-Learning , Sarsa, DynaQ 41
3.3.1. Mơ tả và u cầu của bài tốn mơ phỏng đánh giá

41

3.3.2. Các giả định

42

KẾT LUẬN

51

TÀI LIỆU THAM KHẢO

52



5

DANH MỤC CÁC TỪ VIẾT TẮT

Thuật ngữ

Viết tắt

Học tăng cường (Reinforcement Learning)

RL

Phương pháp Monte Carlo

MC

Phương pháp Temporal Difference

TD

Phương pháp quy hoạch động (Dynamic

DP

Programming)

DANH MỤC CÁC BẢNG
Thuật ngữ


Tên bảng

Bảng phần thưởng

Bảng 3.1

Bảng giá trị Q(1)

Bảng 3.2

Bảng giá trị Q(2)

Bảng 3.3

Bảng giá trị Q(3)

Bảng 3.4

Bảng giá trị Q(4)

Bảng 3.5

Bảng giá trị Q(5)

Bảng 3.6

Bảng số bước di chuyển ở tường giai đoạn của thuật
toán Q-learning
Bảng số bước di chuyển ở tường giai đoạn của thuật
toán Sarsa

Bảng số bước di chuyển ở tường giai đoạn của thuật
toán Dyna-Q
Bảng so sánh số đường đi ngắn nhất

Bảng 3.7

Bảng 3.10

Bảng so sánh số đường đi ngắn nhất

Bảng 3.11

Bảng so sánh giá trị chiến lược và giai đoạn
Bảng so sánh giá trị chiến lược và giai đoạn

Bảng 3.12
Bảng 3.13

Bảng 3.8
Bảng 3.9


6

DANH MỤC CÁC HÌNH
Thuật ngữ

Tên hình

Sơ đồ học tăng cường


Hình 1.1

Mơ phỏng trị chơi Tic-Tac-Toe

Hình 1.2

Mơ phỏng mơi trường

Hình 3.1

Sơ đồ mơ phỏng mơi trường dạng 1

Hình 3.2

Sơ đồ mơ phỏng mơi trường dạng 2

Hình 3.3

Mơ phỏng mơi trường

Hình 3.4

Sơ đồ mơ phỏng mơi trường

Hình 3.5

Sơ đồ mơ phỏng mơi trường

Hình 3.6


Kết quả thực nghiệm

Hình 3.7

Mê cung 5 x5

Hình 3.8

Trạng thái tốt nhất được sử dụng

Hình 3.9

Trạng thái tốt nhất được sử dụng

Hình 3.10

Trạng thái tốt nhất được sử dụng

Hình 3.11

Trạng thái tốt nhất được sử dụng

Hình 3.12

Biểu đồ giá trị của Q

Hình 3.13

Mê cung 9x6


Hình 3.14

Trạng thái các bước của robot trong thuật toán
Qlearning
Trạng thái các bước của robot trong thuật tốn Sara

Hình 3.15

Trạng thái các bước của robot trong thuật tốn
DynaQ
Sơ đồ hội tụ của các thuật tốn

Hình 3.17

Sơ đồ đường đi thuật tốn Q-learning

Hình 3.19

Sơ đồ đường đi thuật tốn Sarsa

Hình 3.20

Sơ đồ đường đi thuật tốn Dyna-Q

Hình 3.21

Sơ đồ so sánh số phương án tối ưu của thuật tốn

Hình 3.22


Sơ đồ so sánh hệ số học và giá trị chiến lược

Hình 3.23

Mối quan hệ giữa số đoạn lặp và hệ số học

Hình 3.24

Hình 3.16

Hình 3.18


7

MỞ ĐẦU
1. Lý do chọn đề tài.
Trước đây, người ta giải quyết bài tốn tìm đường bằng cách sử dụng các
thuật tốn tìm đường cổ điển, ví dụ như thuật toán Dijkstra, thuật toán BellmanFord, thuật toán Johnson. Tuy nhiên các thuật tốn tìm đường nói trên có một số
hạn chế như là địi hỏi mơi trường phải được xác định trước và khơng thay đổi
trong q trình tìm đường. Như vậy các thuật tốn đó khơng xử lý được các bài
tốn tìm đường đi thực tế vì mơi trường đường đi trong thực tế thường bị thay
đổi. Với sự phát triển của trí tuệ nhân tạo, ngày nay các cơng nghệ với sự trợ
giúp của máy tính, máy tính có thể “học”, hay nói cách khác là tự tìm ra được
quy luật hành động nói chung hay tự tìm đường nói riêng thơng qua các kinh
nghiệm thu được từ những hành động được thực hiện trước đó.
Từ các thực tế đó, chúng tơi hướng tới việc nghiên cứu thuật toán học tăng
cường Q-learning để áp dụng trong việc lập kế hoạch đường đi cho các robot tự
hành.

2. Lịch sử vấn đề
Các phương pháp học máy đã được đề xuất để chỉ khả năng các hệ thống
thơng minh có khả năng tự tích lũy thơng tin trong q trình hoạt động, phân tích
các thơng tin thu được từ đó tự nâng cao khả năng của hệ thống, đây chính là
mục đích quan trọng trong lý thuyết quyết định cũng như trong các bài toán tự
động hoá và điều khiển tối ưu.
3. Đối tượng và phạm vi nghiên cứu
3.1. Đối tượng nghiên cứu
Nghiên cứu lý thuyết:


8

Nghiên cứu các tài liệu về thuật toán học tăng cường đã cơng bố ở trong và
ngồi nước.
Nghiên cứu tài liệu về trích chọn đặc trưng của các thuật tốn học tăng
cường.
Nghiên cứu các thuật toán học tăng cường áp dụng trong bài tốn tìm
đường đi ngắn nhất.
Nghiên cứu thực nghiệm:
Nghiên cứu cách xây mơ hình đường đi ngắn nhất cho robot.
Cài đặt cho bài tốn tìm đường đi ngắn nhất và cài đặt đánh giá thuật toán
học tăng cường.
3.2. Phạm vi nghiên cứu
Bài tốn tìm đường đi ngắn nhất có thể được thực hiện bằng nhiều thuật
tốn khác nhau như: thuật tốn Sarsa, Dyna-Q, DynaH …và có thể được giải
quyết với thời gian hội tụ khá nhanh.
Trong phạm vi Luận văn này, tôi tập trung vào các phương pháp phương
pháp Monte Carlo (MC) và phương pháp Temporal Difference (TD) để giải
quyết bài tốn tìm đường đi ngắn nhất cho Robot.

4. Mục đích, nhiệm vụ nghiên cứu
Luận văn tập trung vào 3 mục tiêu chính sau:
Nắm vững các kiến thức về phương pháp học tăng cường, hiểu rõ các ý
tưởng, các cơ chế hoạt của thuật toán và ứng dụng trong bài toán cụ thể.
Nghiên cứu và cài đặt bài tốn tìm đường đi ngắn nhất bằng các thuật tốn
học tăng cường (thuật toán Q-Learning).


9

Đánh giá hiệu quả của các thuật tốn qua mơ phỏng.
5. Phương pháp nghiên cứu
Nghiên cứu tổng quan về bài tốn tìm đường đi ngắn nhất bằng thuật tốn
học tăng cường đã được cơng bố.
Nghiên cứu về bài tốn quyết định Markov về sự hội tụ áp dụng vào học
tăng cường.
Nghiên cứu các thuật toán học tăng cường với hai phương pháp là học dựa
trên mơ hình và học khơng có mơ hình.
Lập trình các thuật tốn trên máy tính và đánh giá hiệu quả của các thuật
tốn.
6. Đóng góp của luận văn
Trong Luận văn chỉ ra các thuật toán Dyna-Q là có hiệu quả tốt nhất trong
số các thuật toán Q-learning, Sarsa, Q (k), Sarsa (k). Tuy nhiên luận văn chỉ
nhấn mạnh trên các mô phỏng trong phạm vi mê cung.
7. Cấu trúc của luận văn
Luận văn gồm 3 phần:
Chương 1 Tổng quan.
Chương 2 Các thuật toán học tăng cường.
Chương 3 Thiết kế hệ thống thử nghiệm.
Kết luận.



10

Chương 1 TỔNG QUAN
1.1. Đặt vấn đề
Xác định đường đi hoặc xác định quỹ đạo đường đi của robot di động là đề
cập đến việc xác định một con đường khơng có chướng ngại vật từ vị trí của nó
đến một vị trí mục tiêu thơng qua một mơi trường nhiều vật cản mà không cần
sự can thiệp của con người. Hiện nay các phương pháp học máy đã cho phép
robot có thể tự tìm đường và di chuyển dựa vào việc cập nhật trạng thái hiện thời
của môi trường mà nó đang hoạt động.
1.2. Phát biểu bài tốn cây quyết định markov.
Bài toán quyết định Markov là bài toán học từ các tác động để đạt được
mục đích. Người học và người ra quyết định được gọi là tác tử. Tất cả những gì
mà chúng tương tác với, bao gồm mọi thứ bên ngoài tác tử được gọi là môi
trường. Các tác động thực hiện một cách liên tục, tác tử lựa chọn các hành động,
môi trường đáp ứng lại các hành động đó và chuyển từ trạng thái hiện thời sang
trạng thái mới. Môi trường cũng đem lại các mục tiêu, các giá trị bằng số mà tác
tử cố gắng cực đại hoá qua thời gian. Một đặc tả hồn thiện về mơi trường được
coi là một “nhiệm vụ”, một thực thể của bài toán quyết định Markov. Tóm lại,
bài tốn quyết định Markov liên quan đến lớp bài tốn trong đó một tác tử rút ra
kết luận trong khi phân tích một chuỗi các hành động của nó cùng với tín hiệu
vơ hướng được đưa ra bởi môi trường.
Học tăng cường là phương pháp học thông qua tương tác với mơi trường.
Mơ hình của học tăng cường gồm có 3 thành phần chính: tác tử (agent), mơi
trường (environment) và giá trị phản hồi (reward). Quá trình học là một quá
trình lặp đi lặp lại (iteration) các hành động (action). Sau khi thực hiện mỗi hành
động thì agent nhảy từ vị trí (hay trạng thái - state) này sang vị trí (trạng thái)
khác, và đồng thời nhận được giá trị phản hồi (reward) từ hành động cũ. Dựa

vào các giá trị phản hồi nhận được agent có thể điều chỉnh luật chọn hành động


11

(policy) của mình trong các bước tiếp theo. Việc điều chỉnh và tối ưu hóa luật
chọn hành động dựa vào các giá trị phản hồi chính là q trình học tăng cường.
Rõ ràng là quy luật chọn lựa hành động của agent thu được sau quá trình học
càng gần tối ưu nếu quá trình học càng kéo dài và số lượng các tình huống mà
agent gặp phải là càng nhiều.

Agent
State
(st)

Reward
(rt)
rt+1
st+1

Action
(at)

Environment

Hình 1.1: Sơ đồ học tăng cường
Với mơ hình học tăng cường như vậy thì vấn đề cần giải quyết là các thông
tin phản hồi (reward) được xử lý như thế nào. Sau mỗi hành động thì tác tử nhận
được một giá trị phản hồi và sau một quá trình học lâu dài thì số lượng các thơng
tin phản hồi này là rất lớn mà tại mỗi thời điểm không thể quan tâm đến tất cả

mọi giá trị này được. Để giải quyết vấn đề này thì mơ hình học tăng cường được
đưa về mơ hình Markov (MDP - Markov Decision Process), là sự mở rộng của
chuỗi Markov. Chuỗi Markov là một quá trình ngẫu nhiên mà giá trị hàm xác
suất (probability distribution function) của mỗi bước tiếp theo chỉ phụ thuộc vào
các thơng số của bước trước đó, điều này cho phép ta chỉ quan tâm tới giá trị
phản hồi ngay trước đó tại mỗi vị trí. Lý thuyết học tăng cường hiện nay dựa vào
mơ hình Markov, do đó các bài tốn khơng thể đưa về được mơ hình Markov thì
khơng thể giải quyết được bằng phương pháp học tăng cường. Mơ hình Markov
(MDP) được định nghĩa là tập hợp (tuple) <S, A, T, ρ>: [1]
S: tập các vị trí (hay trạng thái- state).
A: tập các hành động (action); R: là tập điểm thưởng.


12

T: SxA -> P(S): là hàm xác suất (probability distribution function) cho
từng cặp trạng thái - hành động. Hàm này gán giá trị xác suất cho từng cặp trạng
thái - hành động.
ρ: SxA -> R: là payoff function, gán giá trị phản hồi cho từng hành động
tại vị trí xác định. Mơ hình Markov có thể là xác định (với từng cặp trạng thái hành động xác định thì cho ra vị trí kế tiếp giống nhau ở mọi thời điểm) hoặc
khơng xác định. Với mơ hình Markov xác suất chuyển đến vị trí s’ từ vị trí s và
hành động a là:

Pssa  Pr{s1  s  | st  s, at  a} [1]
Và giá trị phản hồi là:

Pssa '  E{r1 | st  s | st  s, at  a, st 1  s '} [1]
Ta gọi giá trị “return” là tổng của các giá trị phản hồi tính từ thời điểm
hiện tại cho đến khi tác tử đạt đến đích, hoặc đến cuối giai đoạn (nếu quá trình
học được chia thành nhiều giai đoạn -episode). Và tổng của các giá trị phản hồi

tính từ thời điểm hiện tại cho đến khi agent đạt đến đích.

Rt  rt 1  rt 2  ...  rT
Trong đó T là bước cuối cùng trước khi đến đích. [1]
Thực nghiệm cho thấy nếu ta giảm dần mức độ quan trọng của các bước ở
các thời điểm xa với thời điểm hiện tại thì quá trình học sẽ hội tụ nhanh hơn.
Điều đó có nghĩa là ta cần thêm vào hệ số khấu hao γ. Giá trị phản hồi ở thời
điểm cách hiện tại bao nhiêu bước thời gian thì sẽ được nhân với giá trị khấu hao
γ bấy nhiêu lần. Như vậy giá trị “return” sẽ được tính như sau:


Rt  rt 1   rt  2   2 rt 3  ...    k rt  k 1
k 0

[2]


13

Mọi thuật toán của học tăng cường đều dựa trên hàm giá trị. Hàm giá trị
cung cấp giá trị dự đốn mức độ “tốt” của tác tử ở vị trí hiện tại trong q trình
tìm đến đích. Hàm này chính là giá trị “return” ước tính tại từng vị trí (hay trạng
thái - hành động ) ứng với một luật chọn hành động (policy) xác định nào đó. Ta
có thể xác định hàm giá trị theo vị trí hay theo cặp giá trị trạng thái - hành động.
Hàm giá trị theo vị trí (state - value function) V ứng với luật chọn hành
động π tại vị trí s được xác định như sau:


V ( s)  E {Rt | st  s}  E {  k rt  k 1 | st  s}



k 0

[4]

Hàm giá trị theo cặp vị trí - hành động (action - state value function) Q
được xác định như sau:


Q ( s, a)  E {Rt | st  s, at  a}  E {  k rt  k 1 | st  s, at  a}


k 0

[4]

Quá trình học tăng cường là q trình tìm kiếm policy tối ưu, có nghĩa là
q trình điều chỉnh giá trị của hàm giá trị về giá trị tối ưu. Quá trình điều chỉnh
được thực hiện bởi việc lặp đi lặp lại một số lượng lớn bước thực hiện các hành
động, gọi là iteration. Một luật chọn hành động là tối ưu nếu và chỉ nếu giá trị
của hàm giá trị ứng với luật chọn hành động đó ln lớn hơn hoặc bằng hàm giá
trị của các luật chọn hành động khác. Gọi V* và Q* là các hàm giá trị tối ưu ta
có thể xác định các hàm này bằng cách sau:

V *(s)  max v (s)


Q* (s, a)  max Q ( s, a)



Có nghĩa là giá trị các hàm V* và Q* chính là giá trị của các hàm V và Q
ứng với luật chọn hành động tối ưu (cho ra giá trị V(s) hay Q(s, a) lớn nhất tại


14

mỗi vị trí s . Các loại thuật tốn học tăng cường thơng thường gồm có lập trình
động (dynamic programming), Monte-Carlo và phương pháp TD (temporal
difference). Tuy nhiên các phương pháp lập trình động và Monte-Carlo khơng
hiệu quả do địi hỏi bộ nhớ q lớn, hoặc mơ hình phải xác định hay khó hội tụ
nên ít khi cho ra kết quả tối ưu. Phương pháp TD là sự kết hợp của những
phương pháp kể trên và cho phép giải quyết được nhiều bài tốn thực tế bởi vì
phương pháp này khơng địi hỏi mơi trường xác định và có khả năng hội tụ cao.
Một biến thể của phương pháp TD được gọi là Q-learning, là phương pháp học
kiểu TD theo hướng off-policy, rất hiệu quả trong việc giải quyết các bài tốn
tìm đường. [3]
Ví dụ 1: Trị chơi Tic-Tac-Toe. Hai người chơi thực hiện chơi trên một
bảng kích thước 4x4. Một người ghi kí hiệu X và một người ghi kí hiệu O, đến
tận khi có người thắng nhờ ghi 4 dấu trên cùng một hàng dọc hoặc hàng ngang
hoặc hàng chéo, như người ghi dấu X trong hình vẽ:
X
O

O
X

O
O

X

X

X

Hình 1.2: Mơ phỏng trị chơi Tic-Tac-Toe
Nếu bảng bị lấp đầy mà không người chơi nào ghi được 4 dấu trong cùng
một hàng thì trận đấu sẽ hồ. Bài tốn tic-tac-toe được tiếp cận sử dụng RL như
sau:
Trạng thái: Bảng 4x4.
Hành động: phép di chuyển tiếp theo.
Mục tiêu: 1 nếu thắng, -1 nếu thua, 0 nếu hồ.
Bài tốn: tìm π: S→A sao cho R lớn nhất.


15

Ví dụ 2: Robot di động
Trạng thái: vị trí của Robot và của người.
Hành động: sự di chuyển.
Mục tiêu: số các bước đối mặt thành cơng.
Bài tốn: tìm π: S→A sao cho R lớn nhất.
Để hiểu rõ ràng về các bài toán trong thực tế, ở đây chúng ta xét ví dụ một
cuộc đối thoại về mối quan hệ giữa tác tử và môi trường như sau:
Môi trường: Bạn đang ở trạng thái 65. Bạn có 4 hành động để
lựa chọn.
Tác tử: Tôi lựa chọn hành động 2.
Môi trường:Bạn nhận được một giá trị tăng cường là 7 đơn vị.
Hiện tại bạn đang ở trạng thái 15.
Bạn có 2 hành động để lựa chọn.
Tác tử: Tôi lựa chọn hành động 1.

Môi trường: Bạn nhận được một giá trị tăng cường là -4 đơn vị.
Hiện tại bạn đang ở trạng thái 65.
Bạn có 4 hành động để lựa chọn.
Tác tử: Tơi lựa chọn hành động 2.
Môi trường: Bạn nhận được một giá trị tăng cường là 5 đơn vị.
Hiện tại bạn đang ở trạng thái 44.
Bạn có 5 hành động để lựa chọn.
1.2.2. Các thành phần củamơ hình Markov
Trong mơ hình Markov có thể định nghĩa các phần tử con của một bài tốn
quyết định Markov đó là: Chiến lược (policy), hàm phản hồi (reward function),
hàm giá trị (value function).[2]
a) Chiến lược:


16

Chiến lược định nghĩa cách thức tác tử học từ hành động tại thời điểm đưa
ra. Chiến lược là một ánh xạ từ tập các trạng thái của môi trường đến tập các
hành động được thực hiện khi môi trường ở trong các trạng thái đó.
b) Hàm phản hồi:
Hàm phản hồi dùng để định nghĩa mục tiêu trong bài toán quyết định
Markov. Nó ánh xạ mỗi trạng thái quan sát được (hoặc một cặp trạng thái-hành
động) của môi trường với một giá trị phản hồi thực chất về trạng thái đó.
Trong các bài tốn số bước hữu hạn với những bài tốn này ta có một số
hữu hạn các bước trong tương lai. Sẽ tồn tại một trạng thái kết thúc và một chuỗi
các hành động giữa trạng thái đầu tiên và trạng thái kết thúc được gọi là một giai
đoạn. Ta có:

Rt  rt  rt 1  ...  rt  K 1 [4]
Trong đó K là số các bước trước trạng thái kết thúc.

Trong các bài toán số bước vơ hạn Với những bài tốn này ta có chuỗi các
hành động là vơ hạn. Một hệ số suy giảm γ, 0≤γ≤1 được đưa ra và hàm phản hồi
được biểu diễn dưới dạng tổng của các giá trị mục tiêu giảm dần:

Rt 




k 0

k

rt  k [4]

c) Hàm giá trị:
Trong mọi trạng thái st, một tác tử lựa chọn một hành động dựa theo một
chiến lược điều khiển, π: at = π(st). Hàm giá trị tại một trạng thái của hệ thống
được tính bằng kỳ vọng tốn học của hàm phản hồi theo thời gian. Hàm giá trị là
hàm của trạng thái và xác định mức độ thích hợp của chiến lược điều khiển π đối
với tác tử khi hệ thống đang ở trạng thái s. Hàm giá trị của trạng thái s trong
chiến lược π được tính như sau:[1]


17

Vπ (s) = Eπ {Rt | st = s}[1]
Hàm giá trị tối ưu.
V * ( st )  max Q * ( st , at ) [1]



Giá trị của at ở trạng thái st
Q * ( St , at )  E[ t 1 ]    P( St 1 | St , at ) max Q * ( St 1 , at 1 ) [1]
St 1

at 1

1.2.3. Phương pháp học tăng cường
a) Ý tưởng chung
Có hai phương pháp thường được sử dụng để giải các bài toán quyết định
đó là tìm kiếm trong khơng gian chiến lược và tìm kiếm trong khơng gian hàm
giá trị hay cịn gọi là “phép lặp chiến lược” và “phép lặp giá trị”. Hai phương
pháp này chính là các giải thuật học tăng cường đặc trưng. Ngồi ra cịn xuất
hiện một phương pháp lai giữa hai phương pháp trên: Actor-Critic learning.
b) Phép lặp chiến lược
Ý tưởng là ở chỗ, bắt đầu từ một chiến lược bất kỳ π và cải thiện nó sử

'
dụng V để có một chiến lược tốt hơn π’. Sau đó có thể tính V và cải thiện nó

với một chiến lược tốt hơn nữa π”,…Kết quả của tiến trình lặp này, có thể đạt
được một chuỗi các bước cải thiện chiến lược và các hàm giá trị.
Thuật toán lặp chiến lược:
(1) Bắt đầu với một chiến lược bất kỳ π.
(2) Lặp đánh giá chiến lược π.
Cải tiến chiến lược tại mỗi trạng thái.
Đến tận khi chiến lược khơng có khả năng thay đổi.
c) Phép lặp giá trị



18

Trong phương pháp này, chúng ta không cố gắng quyết định chiến lược
một cách rõ ràng, mà sẽ quyết định hành động có giá trị tối ưu cho mọi trạng
thái. Thuật toán lặp giá trị sinh ra từ dạng đệ qui của hàm giá trị trạng thái tối ưu
Bellman. Phương trình chi phối thuật tốn lặp giá trị như sau:
Vk 1 ( s)  max  Pssa' [ Rssa '   Vk ( s ')] [1]


s'

Thực nghiệm đã chứng minh được rằng giải thuật này hội tụ tại một số hữu
hạn các bước lặp để đạt tới đích là chiến lược tối ưu, chuỗi {Vk} hội tụ đến giá
trị trạng thái tối ưu V*. Phép lặp giá trị kết hợp một cách hiệu quả cả việc đánh
giá chiến lược và cải thiện chiến lược.
1.2.4. Phân loại thuật toán học tăng cường
Các thuật toán học tăng cường được chia thành hai loại chính đó là: học
dựa trên mơ hình (model-based) và học khơng có mơ hình hay nói cách khác học
tự do (model-free). Đại điện cho kiểu học dựa trên mơ hình phải kể đến phương
pháp quy hoạch động (Dynamic Programming DP), cịn đại diện cho kiểu học
khơng có mơ hình là phương pháp Monte Carlo và phương pháp TD (Temporal
Difference).
a) Học dựa trên mơ hình
Phương pháp này thực hiện học theo mơ hình và sử dụng nó để quyết định
chính sách tối ưu. Tác tử ước lượng mơ hình từ các quan sát về cả khả năng
chuyển đổi trạng thái và hàm tăng cường, cuối cùng sẽ sử dụng mơ hình ước
lượng này như là mơ hình thực tế để tìm ra chiến lược tối ưu. Một cách cụ thể,
tác tử tiến hành lập kế hoạch và biên dịch kết quả sang một tập các phản hồi
nhanh hoặc các luật tình huống – phản hồi, sau đó sẽ được sử dụng trong quyết
định thời gian thực. Cách tiếp cận này tuy nhiên bị giới hạn vào sự phục thuộc

của nó vào một mơ hình hồn thiện về mơi trường.
b) Học khơng có mơ hình.


19

Phương pháp này tìm thấy chính sách tối ưu mà khơng phải học theo mơ
hình. Tác tử học các giá trị hành động mà khơng có mơ hình về mơi trường được
a
a
mô tả bởi Pss ' và Rss ' . Trong phương pháp này tác tử tương tác trực tiếp với mơi

trường và biên dịch thơng tin nó thu thập được thành một cấu trúc phản hồi mà
khơng có học từ mơ hình. Trong phương pháp này, các bước chuyển đổi trạng
thái và các giá trị phản hồi tác tử quan sát thay thế cho mơ hình mơi trường.
1.3. Tổng quan về tình hình nghiên cứu
a) Tình hình nghiên cứu trong nước
Thuật toán học tăng cường được nghiên cứu ở Việt Nam từ những năm
2000 và đã cũng có cơng bố cụ thể “Tìm đường đi ngắn nhất bằng phương pháp
q-learning” đăng trên tạp chí chí Khoa học Cơng nghệ & Thực phẩm xuất bản
2014.
b) Tình hình nghiên cứu ngồi nước
Ở ngồi nước có những cơng trình nghiên cứu về các lĩnh vực học tăng
cường nổi bật là cơng trình luận án tiến sĩ “Q-Learning for Robot Control”, luận
án tiến sĩ của tác giả Coulom R năm 2000. Đã đưa những phương pháp học
tăng và áp dụng hiệu quả vào thực tế.


20


Chương 2 CÁC THUẬT TOÁN HỌC TĂNG CƯỜNG
2.1. Tổng quan về phương pháp học tăng cường
2.1.1. Phương pháp Monte Carlo (MC)
Các phương pháp Monte Carlo thích hợp cho việc học từ các kinh nghiệm
trong đó khơng u cầu nhận thức trước đó về tính động của mơi trường. Chúng
giải quyết bài tốn quyết định dựa trên việc tính trung bình các giá trị phản hồi
mẫu.
Phương pháp MC kiểm tra toàn bộ ước lượng Vπ(s) bằng trung bình các
phản hồi sau tất cả các bước kiểm tra đối với s. Qπ(s,a) được ước lượng là trung
bình các phản hồi sau tất cả các bước kiểm tra đối với cặp (s,a). Phương pháp
MC kiểm tra đầu tiên tính trung bình chỉ giá trị phản hồi sau bước kiểm tra đầu
tiên trong phép ước lượng Vπ(s) và Qπ(s,a). Cả hai phương pháp này đều hội tụ
đến Vπ(s) hoặc Qπ(s,a) như là số các bước đến s hoặc cặp (s,a).
Thuật toán sử dụng chiến lược bằng phương pháp MC lặp vô hạn:
(1) Tạo một đoạn mẫu sử dụng chiến lược được ước lượng
(2) s0, a0,s1, a1, r1, …,st, rt
(1) (2) Với mỗi trạng thái s xuất hiện trong đoạn

Rtotal (s)  Rtotal (s)  RCurrentFirstOccurrence ( s)
V  ( s) 

Rtotal ( s)
LoopCounter [1]

Chú ý rằng khi tạo từng đoạn, tất cả các trạng thái phải có khả năng tương
đương với trạng thái bắt đầu. Nếu mơ hình mơi trường khơng sẵn có thì sử dụng
ước lượng các giá trị hành động tốt hơn là ước lượng các giá trị trạng thái.
Nếu có mơ hình mơi trường thì các giá trị trạng thái đủ khả năng để quyết
định chiến lược. Chúng ta không thể sử dụng các ước lượng giá trị trạng thái để
quyết định chiến lược mà khơng có mơ hình về mơi trường.



21

Trong khi đó, chúng ta có thể sử dụng các ước lượng giá trị hành động
trong việc quyết định chiến lược mà khơng cần u cầu mơ hình mơi trường.
Với một chiến lược π, chúng ta sẽ chỉ quan sát các giá trị phản hồi đối với chỉ
một hành động tại mỗi trạng thái.
Như vậy, ước lượng Monte Carlo của các trạng thái khác sẽ không cải tiến
theo kinh nghiệm. Đây là một vấn đề quan trọng vì mục đích của các giá trị hành
động học là giúp cho việc lựa chọn giữa các giá trị có hiệu lực trong mỗi trạng
thái. Kết quả là chúng ta cần ước lượng giá trị của tất cả các hành động từ mỗi
trạng thái. Để giải quyết vấn đề này, chúng ta có thể bắt đầu mỗi đoạn tại một
cặp hành động - trạng thái, mọi cặp như vậy sẽ có khả năng lựa chọn khác 0 khi
bắt đầu. Giải pháp khác là sử dụng chiến lược ngẫu nhiên với khả năng lựa chọn
tất cả các hành động khác 0. Điều này đảm bảo rằng tất cả các cặp hành động –
trạng thái sẽ được kiểm tra một số lần vô hạn trong giới hạn là có vơ hạn các
đoạn.
Chiến lược tối ưu sử dụng phương pháp MC. Bắt đầu với một chiến lược π
ngẫu nhiên và Q(s,a) ngẫu nhiên lặp vô hạn:
(a) Tạo một đoạn mẫu sử dụng π với khả năng lựa chọn tất cả
các hành động là khác 0, độc lập với π tại thời điểm bắt đầu s0,
a0,s1, a1, r1, …,st, rt.
(b) Với mỗi cặp s, a xuất hiện trong đoạn.

Rtotal (s, a)  Rtotal (s, a)  RCurrentFirstOccurrence (s, a)
Q( s, a ) 

Rtotal ( s, a)
Loop Counter


(c) Với mỗi s trong đoạn:

 (s)  arg max a Q( s, a)
Tóm lại, một vấn đề chính trong khi sử dụng phương pháp MC là đảm bảo
rằng tất cả các hành động được lựa chọn không giới hạn. Để đảm bảo điều này,
chúng ta sử dụng các chiến lược soft với π(s,a) > 0 cho tất cả các trạng thái và


22

hành động. Khả năng thực hiện có thể được chuyển dần chiến lược hướng đến
chiến lược tối ưu. Ví dụ, có thể áp dụng phương pháp lựa chọn hành động εgreeady và softmax để thực hiện khả năng trên.
2.1.2. Phương pháp MC on-policy
On-policy: hành động tiếp theo được chọn dựa vào policy.
Trong phương pháp này, chiến lược điều khiển tác tử sẽ được cải thiện.
Một chiến lược soft sử dụng phương pháp lựa chọn hành động ε-greeady là một
chiến lược ngẫu nhiên.
Chúng ta có thể thay đổi thuật tốn cho chiến lược tối ưu với giả sử rằng
phép lựa chọn tất cả các hành động độc lập với π tại thời điểm bắt đầu sử dụng
các chiến lược soft. Các chiến lược soft đảm bảo phép lựa chọn tất cả các hành
động tại tất cả các bước.
Thuật toán 1: Phương pháp MC on-policy.
Initialize, for all s  S , a  S , a  A(s ) :
Q( s, a)  arbitrary
Re turns( s, a)  empty list
  arbitrary   soft policy
Re peat forever :
(1) Generte an episodeu sin g 
(2) For each pair s, a appearing intheepisode

R  Re turns( s, a)
Append R to Re turns ( s, a)
Q( s, a)  average(Re turns( s, a))
(3) For each s intheepisode :
a*  average max a Q(s, a)
For all a  A(s) :
*

1     / | A( s) | if a  a
 ( s, a )  
*

 / | A( s) | if a  a

2.1.3. Phương pháp MC off-policy
Off-policy là hành động tốt nhất tiếp theo được chọn không dựa vào
policy.


23

Trong phương pháp này, chiến lược được sử dụng để tạo hành vi khác so
với chiến lược được ước lượng và cải tiến. Chiến lược được sử dụng để tạo hành
vi được gọi là chiến lược hành vi và chiến lược khác được gọi là chiến lược ước
lượng. Một đặc điểm quan trọng của chiến lược hành vi đó là chiến lược cần
phải có khả năng lựa chọn tất cả các hành động được lựa chọn bởi chiến lược
ước lượng là khác 0.
Thuật toán 2: Phương pháp MC off-policy.
Initialize, for all s  S , a  S , a  A(s ) :
Q(s, a)  arbitrary

N ( s, a )  0
D ( s, a )  0
Re turns( s, a)  empty list
  an arbitrary policy
Re peat forever :
(1) Sclect a policy  ' and s0 , a0 , s1 , a1 , r2 ,..., sT 1 , aT 1 , rT , sT
(2)T  latest time at which aT   ( sT )
(3) For each pair (s, a) appearing intheepisode
t  thetimeof of fist occurrenceof (s, a ) suchthet  T

   k k 1
T 1

1
 '( sk , ak )

N ( s, a )  N ( s, a )   R t
D ( s, a )  D ( s, a )  
Q ( s, a ) 

N ( s, a )
D ( s, a )

(4) For each s  S :
  average max a Q(s, a)

2.2. Phương pháp Temporal Difference (TD)
Đây là phương pháp học theo sự khác biệt về thời gian. Trong phương
pháp (TD) thuật tốn có thể xác định ý tưởng chính của phương pháp TD chắc
chắn sẽ là Sarsa và Q-learning. Thuật toán Sarsa (viết tắt của trạng thái, hành

động, khoản tưởng, trạng thái, hành động) là một thuật tốn học TD khơng theo