..

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
-----------------------------------------------

CHÂU MẠNH QUANG
HỌC TĂNG CƯỜNG VÀ QUYẾT ĐỊNH MARKOV
LUẬN VĂN THẠC SĨ KHOA HỌC
CHUYÊN NGÀNH: XỬ LÝ THÔNG TIN VÀ TRUYỀN
THÔNG

NGƯỜI HƯỚNG DẪN KHOA HỌC:

Hà Nội - 2009


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
*********♦*********

CHÂU MẠNH QUANG

HỌC TĂNG CƯỜNG VÀ QUYẾT ĐỊNH MARKOV

LUẬN VĂN THẠC SĨ KHOA HỌC
CHUYÊN NGÀNH: XỬ LÝ THÔNG TIN VÀ TRUYỀN THÔNG

NGƯỜI HƯỚNG DẪN KHOA HỌC :
TS. NGUYỄN LINH GIANG

HÀ NỘI 2009


0

MỤC LỤC
CÁC TỪ THUẬT NGỮ VIẾT TẮT
LỜI NÓI ĐẦU
MỞ ĐẦU .................................................................................................................. 2

1 HỌC TĂNG CƯỜNG CƠ BẢN ................................................................. 6
1.1

Các thành phần: ......................................................................................... 6

1.2

Lý thuyết học tăng cường .......................................................................... 7

1.2.1 Ation-Value method ................................................................................. 7
1.2.2 Phương pháp Softmax .............................................................................. 8
1.2.3 Incremental evaluation ............................................................................. 8
1.2.4 Vấn đề về môi trường bất định (nonstationary environment) .................. 9
1.2.5 Reinforcement comparison ..................................................................... 10
1.2.6 Pursuit method ........................................................................................ 11
1.2.7 Associative search .................................................................................. 11
1.3

Các vấn đề về học tăng cường .......................................................................12


1.3.1 Agent-environment interface .................................................................. 12
1.3.2 Goal và reward........................................................................................ 13
1.3.3 Giá trị Return .......................................................................................... 13
1.3.4 Markov Decision Process ....................................................................... 14
1.3.4.1 Markov property .............................................................................. 14
1.3.4.2 Markov decision process ................................................................. 14
1.3.4.3 Value function ................................................................................. 18
1.3.4.4 Optimal value function .................................................................... 19
1.4

Các giải pháp cơ bản cho học tăng cường. .................................................23

1.4.1 Dynamic programming ........................................................................... 23
1.4.1.1 Policy evaluation ....................................................................................24
1.4.1.2 Policy improvement................................................................................27
1.4.1.3 Policy iteration .......................................................................................28
1.4.1.4 Value iteration ........................................................................................29


0

1.4.1.5 Generalized policy iteration..................................................................30
1.4.1.6 Độ phức tạp của thuật toán lập trình động .........................................31
1.4.2 Phương pháp Monte-Carlo ..................................................................... 31
1.4.2.1 Policy evaluation ....................................................................................31
1.4.2.2 Vấn đề về xác định action value ...........................................................34
1.4.2.3 Monte-Carlo control ..............................................................................34
1.4.2.4 On-policy Monte-Carrlo control ..........................................................36
1.4.2.5 Phương pháp đánh giá một policy trong khi thực hiện policy
khác


..................................................................................................................38

1.4.2.6 Off-policy Monte-Carlo control............................................................38
1.4.2.7 Cách thực hiện theo kiểu incremental .................................................40
1.4.3 Phương pháp Temporal-Difference ........................................................ 40
1.4.3.1 TD prediction ..........................................................................................41
1.4.3.2 Sarsa: on-policy TD control .................................................................46
1.4.3.3 Q-learning: off-policy TD control ........................................................47
1.4.3.4 Actor-critic method ................................................................................48
1.4.3.5 R-learning ................................................................................................49
1.4.3.6 Phương pháp TD(λ) ...............................................................................51
1.4.4 Học tăng cường có sử dụng các approximation function ....................... 66
1.4.4.1 Phương pháp gradient-descendent ......................................................68
1.4.4.2 Phương pháp tuyến tính.........................................................................70
1.4.4.3 Control có sử dụng hàm xấp xỉ .............................................................74
2

LÝ THUYẾT HỌC TĂNG CƯỜNG MỞ RỘNG ........................................ 78
2.1

Thuật toán chuyển giao (Transfer Algorithms) ........................................78

2.1.1 Phương pháp PPR ................................................................................... 80
2.1.2 Phương pháp MGE ................................................................................. 80
2.1.3 Phương pháp AdaTran ............................................................................ 82
2.1.4 Ví dụ minh hoạ: bài tốn gridworld ....................................................... 83
2.2

POMDP và phương pháp policy search ......................................................86


2.2.1 Giải pháp 1.............................................................................................. 86


0

2.2.2 Giải pháp 2.............................................................................................. 93
2.2.3 Giải pháp 3.............................................................................................. 95
2.3

Kết hợp giữa học tăng cường với thuật toán đàn kiến – Ant-Q ............96

2.3.1 Ant System ............................................................................................. 98
2.3.2 ACO ........................................................................................................ 98
2.3.3 Ant-Q ...................................................................................................... 99
2.4

Ứng dụng của học tăng cường kết hợp với suy diễn ngữ pháp ..............99

2.4.1 Các khái niệm cơ bản ........................................................................... 101
2.4.2 Mơ hình ngữ pháp cho MDP ................................................................ 102
2.4.3 Simple Context-Free Markov decision process .................................... 104
2.4.4 Thuật toán RSG-QL.............................................................................. 110
2.4.5 Ví dụ minh hoạ ..................................................................................... 111
3 KẾT QUẢ THỰC NGHIỆM .......................................................................... 114
4 KẾT LUẬN....................................................................................................... 123
5 TÀI LIỆU THAM KHẢO ............................................................................... 126


1

CÁC TỪ THUẬT NGỮ VIẾT TẮT

MDP:

Markov Decision Process.

POMDP: Partially Observable Markov Decision Process.
GPI:

Generalized Policy Iteration.

TD:

Temporal Difference.

PPR:

Probability Policy Reuse.

MGE:

Memory Guided Exploration.

CFG:

Context Free Grammar.

SG:

Simple Grammar.


VSG:

Very Simple Grammar.

RSG:

Right-Unique Simple Grammar.

PSG:

Probabilistic Simple Grammar.

USG:

Unifiable Simple Grammar.


2

MỞ ĐẦU
Ý tưởng về việc học thông qua tương tác với mơi trường có lẽ là cái mà ta
nghĩ đến đầu tiên khi ta xem xét đến các quá trình học trong tự nhiên. Khi một đứa
trẻ chơi, vẫy tay, nhìn ngó xung quanh, lúc đó mặc dù khơng có ai dạy bảo nhưng
đứa trẻ có tương tác với mơi trường. Qua đó, thu nhận được rất nhiều thơng tin về
nguyên nhân và hệ quả, về những tác động của từng hành động và từ đó đứa trẻ có
thể từng bước xác định được làm thế nào để đạt được một mục đích nào đó. Trong
cuộc đời chúng ta, những sự tương tác với môi trường như vậy mang lại cho chúng
ta nhiều kiến thức nhất về môi trường và bản thân. Bất kỳ lúc nào khi ta lái xe hay
nói chuyện thì chúng ta đều nhận thức được mơi trường đáp ứng lại mỗi hành động

của chúng ta và chúng ta tìm cách điều chỉnh những sự việc có thể xảy ra thơng qua
các hành động của mình. Việc học thông qua tương tác với môi trường là một trong
những ý tưởng cơ sở của lý thuyết máy học. Phương pháp học này được gọi là học
tăng cường.
Học tăng cường là phương pháp học cách hành động thích hợp để đáp ứng với
tình huống sao cho giá trị reward thu được là tối ưu. Người học không được hướng
dẫn trước cách hành động như những phương pháp học khác mà phải tự khám phá
ra những hành động nào thì cho ra được giá trị reward lớn nhất bằng cách thử thực
hiện chúng. Trong một số trường hợp đặc biệt, action có thể ảnh hưởng đến khơng
những giá trị reward tức thời mà cịn cả những tình huống tiếp theo và dẫn đến ảnh
hưởng cả những reward kế tiếp. Hai đặc tính này: trial-and-error search và delayed
reward là hai đặc trưng riêng của học tăng cường.
Quá trình học tăng cường thường được áp dụng trong hoàn cảnh mà một agent
nào đó học cách tương tác với mơi trường để đạt đến được đích của mình. Rõ ràng
là để làm được điều này thì agent phải có khả năng cảm nhận được tình thế của
mình trong mơi trường và ở một chừng mực nào đó phải có khả năng thực thi các
action để có thể thay đổi được tình thế. Như vậy là trong q trình học tăng cường
có 3 yếu tố là nhận thức (sensation), hành động (action) và đích (goal).


3
Học tăng cường khác với học có giám sát (supervised learning) ở chỗ là học
có giám sát thì học theo các mẫu kiến thức đã được xác định trước, và ứng với mỗi
mẫu input thì cho ra giá trị output nhất định. Với cách học này thì khơng thể đủ để
học bằng cách chỉ thông qua việc tương tác với môi trường. Nguyên nhân là ở chỗ
chỉ bằng cách tương tác với mơi trường thì khó có thể xác định được các mẫu mà
cho ra kết quả như ý cũng như không thể xác định hết tất cả các mẫu tình huống mà
agent gặp phải trong cả quá trình hành động của mình.
Một trong những vấn đề mà quá trình học tăng cường phải giải quyết là phải
cân bằng được 2 quá trình khai thác (exploitation) và khám phá (exploration). Tại

một thời điểm nếu agent hành động theo hướng này thì phải bỏ qua hướng kia. Để
nhận được nhiều reward thì agent phải ưu tiên thực hiện các action mà đã gặp trong
quá khứ mà cho ra nhiều reward (exploitation). Nhưng để khám phá ra được các
action đó thì agent buộc phải thử các action mà chưa được thử bao giờ (exploration).
Nói cách khác agent phải đồng thời khai thác những kiến thức đã học được nhưng
đồng thời cũng phải học hỏi cái mới.
Vấn đề khác đối với học tăng cường là agent phải tương tác với môi trường
không xác định.
Lý thuyết về học tăng cường đã làm cho 2 lĩnh vực engineering và trí tuệ nhân
tạo xích lại gần nhau hơn. Trước đây trí tuệ nhân tạo chỉ thuần tuý là các LISP
programs, không liên quan nhiều đến những thứ như linear algebra, differential
equation, và statistic. Nhưng gần đây, với sự phát triển của neural network,
intelligent control, và học tăng cường thì nhiều lĩnh vực của engineering bắt đầu
được áp dụng trong trí tuệ nhân tạo.
Trong thưc tế, học tăng cường được ra đời và được thúc đẩy phát triển bới
nhiều bài toán cần giải quyết cũng như từ sự quan sát các quá trình học tự nhiên.
Dưới đây là một số ví dụ điển hình:
Người chơi bài: khi đánh quân bài thì sự lựa chọn quân bài thì sự lựa chọn
quân bài đựa trên thông tin thu nhận được từ 2 nguồn. Thứ nhất là sự kết hợp của
việc lập kế hoạch (planning) và phỏng đoán khả năng đáp trả của đối phương


4
(anticipation). Nguồn thứ hai là từ việc đánh giá tình hình một cách trực giác
(intuitive).
Adaptive controller điều chỉnh các thơng số của nhà máy lọc dầu: controller
phải điều chỉnh một cách thích hợp và tối ưu các giá trị của yield, cost, và quality có
cân nhắc đến ảnh hưởng lẫn nhau của các giá trị. Để công việc điều chỉnh trên đạt
hiệu quả cao thì controller khơng thể chỉ dựa vào các tập hợp các giá trị được định
trước của kỹ sư.

Con nai con khi mới ra đời phải tập cách giữ thăng bằng để có thể đứng được
trên 4 chân, để rồi 30 phút sau nó có thể chạy được với tốc độ 20 dặm/giờ.
Mobile robot sử dụng năng lượng acquy khi hoạt động phải cân nhắc thực hiện
công việc một cách có hiệu quả dựa theo lượng điện còn lại trong ăcquy để còn đủ
điện để quay trở về chỗ nạp điện.
Những ví dụ trên đều có chung một đặc điểm dễ nhìn thấy: đó là tất cả mọi
agent đều phải tương tác với môi trường để từ đó agent có thể tìm cách đạt đến đích
mặc dù môi trường là không xác định đối với agent. Các action của agent có thể có
ảnh hưởng đến các bước quyết định tiếp theo (ví dụ: tiếp theo đánh quân bài nào,
lượng dầu trong các bể chứa, vị trí tiếp theo của robot), và từ đó ảnh hưởng đến các
chọn lựa và cơ hội đạt đến đích của agent trong giai đoạn về sau. Để có được quyết
định chính xác thì cần phải áp dụng các phương pháp dự đốn (foresight) và lập kế
hoạch (planning). Tại mỗi thời điểm thì tác động của các action đến giai đoạn tiếp
theo chưa thể xác định và cũng khơng dễ gì tiên đốn được. Do đó, agent cần phải
thường xun quan sát mơi trường và ra quyết định phù hợp với môi trường ở mọi
thời điểm. Agent đánh giá môi trường và khả năng đạt đến đích một phần dựa vào
những những kiến thức mà đã cảm nhận hoặc đánh giá được trong gia đoạn trước.
Ví dụ, người đánh bài nhìn vào những quân bài đã đánh có thể biết được họ có thể
thắng hoặc thua, controller biết được có bao nhiêu dầu đã được xử lý, mobile robot
biết còn bao nhiêu điện. Những gì agent thu nhận được qua sự tương tác với môi
trường được gọi là experience. Những experience này được sử dụng để làm tăng
hiệu quả của các action theo thời gian.


5
Trong học tăng cường thì các thuật tốn tiến hố (evolutionary methods) như
là genetic algorithms, genetic programming, simulated annealing, vv… ít khi được
sử dụng. Nguyên nhân là do học tăng cường học từ q trình tương tác với mơi
trường cịn các phép tính tiến hố thì thường khơng quan tâm đến từng state được đi
qua hay từng action được chọn tại mỗi thời điểm. Thay vào đó thì các phép tính tiến

hố lại thường xử lý thơng tin bằng cách gộp tất cả lại.
Đề tài của luận văn cao học này mang tính lý thuyết kết hợp với thực nghiệm
để kiểm chứng một số phần của lý thuyết. Mục đích của luận văn gồm có:
-Nghiên cứu một cách có hệ thống về lý thuyết học tăng cường.
-Nghiên cứu về các lý thuyết mở rộng về học tăng cường cũng như việc kết
hợp giữa học tăng cường với các lý thuyết khác.
-Tiến hành thực nghiệm với một bài toán để kiểm chứng lý thuyết và minh họa
cho sự khác biệt giữa một số phương pháp học tăng cường.


6

1 Học tăng cường cơ bản
1.1 Các thành phần:
Ngoài agent và mơi trường được đề cập ở trên thì học tăng cường còn được
đặc trưng bởi các thành phần như: policy, reward function, value function và trong
một số trường hợp cịn có cả model.
Policy xác định cách hành xử của agent tại mỗi thời điểm hay nói một cách cụ
thể hơn thì policy quyết định cách chọn action tại mỗi thờid điểm. Định nghĩa một
cách đơn giản thì policy là mapping từ trạng thái của môi trường vào action. Trong
một số trường hợp thì policy chỉ là hàm đơn giản hay là lookup table. Một số trường
hợp khác thì policy lại là một q trình tính tốn rất phức tạp ví dụ như là q trình
tìm kiếm (search process). Policy chính là thành phần quan trọng nhất của học tăng
cường bởi vì nó điều khiển các action của agent. Xét về tổng quan thì policy có thể
mang tính ngẫu nhiên, khơng thể dự đốn được (stochastic).
Hàm Reward xác định đích của q trình học tăng cường. Tại vị trí đích thì
giá trị của reward là lớn nhất. Những vị trí mà khả năng đạt được đích cao hơn thì
giá trị reward cũng cao hơn. Định nghĩa một cách đơn giản thì hàm reward map các
state (hay các cặp state-action) vào các giá trị số (reward). Các giá trị số này chỉ thị
mức độ quan trọng của state trong quá trình đạt đến đích.

Giá trị Value function xác định mức độ “tốt” của q trình tìm đến đích của
agent xét trong cả một giai đoạn dài, khác với giá trị reward chỉ xác định mức độ
“tốt” ở thời điểm hiện tại. Định nghĩa một cách đơn giản thì value của một state nào
đó là tổng của tất cả các reward mà agent trơng đợi là sẽ đạt được trong gia đoạn
tính từ state hiện tại tới khi đạt được đích.
Một thành phần nữa của học tăng cường là model. Model là mơ hình mơ
phỏng lại các quy luật hành xử của mơi trường. Nếucó model thì có thể tiên đốn
được các state và reward tiếp theo của từng cặp action-state xác định.


7

1.2 Lý thuyết học tăng cường
Giá trị của feedback cho phép ta xác định được các action được thực hiện là
“tốt” đến mức nào chứ không xác định được action nào là tốt nhất, hay action nào là
“kém” nhất. Dưới đây là một số phương pháp đánh giá feedback:

1.2.1 Ation-Value method
Phương pháp này sử dụng hàm đánh giá cho action thay vì hàm đánh giá cho
state như truyền thống. Ta gọi:
Q * (a) là giá trị đích thực (true value) của action a.
Q t (a) là giá trị ước đoán (estimated value) của action a.
Với phương pháp action-value thì giá trị ước tính Q t (a) của a được tính theo
giá trị trung bình của các reward của a. Giả sử đến thời điểm t thì action a đã được
thực hiện ka lần với các reward r 1 , r 2 , …, r ka thì:

Với k a = 0 thì Q t (a) được gán cho giá trị mặc định nào đó lúc khởi đầu, chẳng
hạn như Q 0 (a) = 0. Cịn với k a → ∞ thì Q t (a) → Q * (a).
Phương pháp xác chọn action đơn giản nhất là phương pháp lựa chọn action
theo kiểu “greedy”, có nghĩa là tại thời điểm t ta chọn một trong số các action

greedy action a * mà có giá trị đích thực của value function là lớn nhất trong số
value function của các action được xét. Khi đó ta có:
Q t (a * ) = max a Q t (a).
Một phương pháp khác có mức độ “greedy” nhỏ hơn được gọi là ε-greedy.
Khi đó với xác suất (1 – ε) ta chọn action theo kiểu greedy, còn với xác suất ε ta
chọn action một cách ngẫu nhiên. Với cách chọn như vậy thì đảm bảo vừa có khám
phá vừa có khai thác.


8
1.2.2 Phương pháp Softmax
Mặc dù chọn action theo phương pháp ε – greedy là khá hiệu quả nhưng
phương pháp này cũng có một nhược điểm là khi khám phá (exploration) thì mọi
action đều được chọn lựa với xác suất như nhau. Với cách chọn này thì cả những
action có hiệu quả kém nhất cũng được chọn. Một phương pháp hạn chế bớt nhược
điểm này là gán xác suất chọn lựa action với giá trị value ước đốn của nó. Đó là
phương pháp Softmax. Phương pháp này sử dụng luật phân bố Boltzmann
(Boltzmann distribution). Với luật này thì action a được chọn với xác suất:

Trong đó τ là nhiệt độ. Nếu nhiệt độ thật cao thì các xác suất là gần bằng nhau
-> chọn lựa trở thành phương pháp ngẫu nhiên. Nếu nhiệt độ càng thấp thì mức độ
chọn lựa kiểu greedy càng cao. Nếu τ = 0 thì phương pháp trở thành greedy hồn
tồn.

1.2.3 Incremental evaluation
Với phương pháp action-value thì tại mỗi thời điểm t action value được tính
theo cơng thức:

Khi đó ta cần có bộ nhớ để lưu các giá trị r1, r2, …, rn. Đây là vấn đề bởi vì
dung lượng bộ nhớ rất lớn. Do đó cần thiết phải nghĩ ra một phương pháp

incremental update nào đó để giá trị Q k +1 chỉ phụ thuộc vào Q k và từ đó ta chỉ cần
một đơn vị bộ nhớ cho mỗi action để lưu giá trị Q. Khi đó ta có thể tính giá trị của
Q theo giá trị trước đó như sau:


9

Có nghĩa là các giá trị được điều chỉnh theo quy luật sau:

Biểu thức [Target - OldEstimate] gọi là error.
Giá trị StepSize thường được tính theo cơng thức: α k (a) =

1
k

1.2.4 Vấn đề về môi trường bất định (nonstationary
environment)
Những phương pháp vừa được trình bày ở trên chỉ phù hợp với môi trường ổn
định (stationary). Với những trường hợp mà mơi trường khơng ổn định
(nonstationary) thì cách tính như vậy khơng cịn phù hợp. Trong một số trường hợp
thì những reward gần đây nhất cần phải có trọng lượng hơn là những reward nhận
được đã lâu rồi. Do đó một phương pháp sử dụng giá trị hằng số cho step-size là
phù hợp với tình huống này. Khi đó:

Giá trị step-size 0 < α <= 1 là hằng số (constant).
Khi đó ta có thể tính Q k theo Q 0 :


10


Ta gọi cách tính này là weighted average bởi vì tổng các weight là:

Rõ ràng là nếu chọn giá trị α k (a) ≤

1
thì giá trị Q mới hội tụ, nếu khơng thì sẽ
k

phân kỳ.

1.2.5 Reinforcement comparison
Phương pháp này dựa trên ý tưởng trực quan là những action có reward lớn thì
nên được lặp lại nhiều lần hơn là những action có reward nhỏ. Nhưng để agent nhận
biết được reward thế nào là lớn, reward thế nào là nhỏ thì có một phương pháp là so
sánh reward với mức chuẩn nào đó, gọi là reference reward. Thơng thường thì
reference reward được chọn là giá trị trung bình của tất cả các reward đã nhận được.
Reward được coi là lớn nếu lớn hơn giá trị reference, và được coi là nhỏ nếu nhỏ
hơn giá trị reference. Phương pháp học tăng cường dựa trên ý tưởng này được gọi là
reinforcement comparison. Với phương pháp này ta không phải lưu giữ các giá trị
value estimation Q t (a).
Gọi p t (a) là giá trị preference của action a.
Xác suất chọn action a được tính theo luật Softmax:

Giá trị p t (a) được chỉnh sửa lại sau mỗi lần lặp lại action:


11

Trong đó: β là step-size, r t là reference reward.
Giá trị r t cũng được chỉnh sửa lại sau mỗi action:


1.2.6 Pursuit method
Với phương pháp này thì xác suất lựa chọn action theo kiểu greedy tăng dần
theo thời gian. Khi sử dụng phương pháp này thì cần thiết phải lưu giữ các giá trị
của value estimate và cả action reference.
Gọi:

Là greedy action.
Xác suất chọn greedy action là:

Xác suất chọn action khác là:

1.2.7 Associative search
Với những trường hợp đơn giản hơn thì quá trình học tăng cường chỉ xử lý các
vấn đề thuộc loại “nonassociative”, có nghĩa là agent chỉ cần tìm một action thích
hợp nhất khi mơi trường là ổn định, hoặc là tìm action thích hợp nhất cho từng thời
điểm khi môi trường không ổn định. Tuy nhiên trong một số trường hợp thì tại một
thời điểm có thể có những action khác nhau thích hợp với từng hồn cảnh, hay nói
cách khác là có thể có nhiều policy khác nhau cho mỗi thời điểm và việc chọn lựa
policy nào là phụ thuộc vào hồn cảnh mơi trường lúc đó. Điều này địi hỏi q
trình học phải bao gồm q trình tìm kiếm những action thích hợp nhất và sử dụng
các phương pháp kết hợp giữa action với hoàn cảnh để tìm ra action thích hợp nhất


12
của tập các action xác định được. cách học như vậy được gọi là associative search.

1.3 Các vấn đề về học tăng cường
Học tăng cường như đã trình bày ở trên là quá trình học từ sự tương tác giữa
agent với mơi trường. Q trình học có thể là thụ động (passive) hoặc chủ động

(active).
Quá trình học thụ động, hay còn gọi là on-policy, sử dụng policy cố định cho
cả quá trình. Nhiệm vụ của agent chỉ là xác định các value function và từ đó chọ lựa
action theo policy đã định sẵn.
Trong quá trình học chủ động (off-policy) thì agent cịn phải học cách hành xử,
có nghĩa là phải thực hiện cả quá trình exploration. Với quá trình exploration thì
agent phải khám phá càng nhiều càng tốt mơi trường để từ đó có thể điều chỉnh
policy một cách linh hoạt.
Để hồn thành một q trình học tăng cường thì phải thực hiện nhiều bài toán
con và giải quyết nhiều vấn đề liên quan đến agent-environment interface, goals,
rewards, giá trị return, và áp dụng nhiều lý thuyết quyết định như MDP (Markov
decision process), Bellmann equation, value iteration, policy iteration, vv… Tiếp
theo đây các vấn đề nêu trên sẽ được trình bày tuần tự.

1.3.1 Agent-environment interface
Giao diện biểu diễn tương tác giữa agent và môi trường được biểu diễn dưới
đây:


13

Trong đó: agent có nhiệm vụ học và đưa ra quyết định. Mơi trường là những
gì tồn tại xung quanh agent, tương tác với agent.
Agent tương tương tác với môi trường, ra quyết định chọn action và thu nhận
về các giá trị reward và chuyển trạng thái sang state khác. hoạt động cụ thể của
agent được trình bày như sau: tại thời điểm t agent tìm hiểu các thơng số của mơ
trường tại thời điểm đó. Sau đó agent chọn action a(t) theo một policy nào đó.
Action cho ra giá trị output nào đó. Hiệu quả của action và ảnh hưởng của nó đối
với mơi trường được thơng báo lại cho agent thông qua giá trị reward r(t). Môi
trường chịu tác động của action a(t),

Trong học tăng cường thì goal được hình thức hố bằng cách dùng giá trị của
reward. Ở mỗi bước thì giá trị của reward thường là một con số đơn giản. Nếu dạt
được đến goal thì giá trị reward tổng hợp trong cả quá trình lâu dài sẽ đạt đến giá trị
tối đa. Để đạt được điều này thì vị trí goal thường có giá trị reward rất lớn.

1.3.2 Goal và reward
Trong học tăng cường thì trạng thái đích (goal state) thường được hiển thị bằng
giá trị reward đặc biệt, thông thường là giá trị rất lớn so với reward ở các state khác.

1.3.3 Giá trị Return
Gọi chuỗi các reward nhận được sau thời điểm t là r t +1 , r t + 2 , …
Giá trị Return R t được xác định theo phương pháp đơn giản nhất là bằng tổng
của các reward tính từ thời điểm t:

Nếu cả quá trình học tăng cường được chia thành nhiều giai đoạn thì mỗi giai
đoạn được gọi là một episode. Mỗi episode đều có terminal state riêng. Và sau đó
q trình lại bắt đầu từ starting state của episode tiếp theo. Trong trường hợp
continuing task thì cả q trình khơng chia thành episode mà tiếp diễn liên tục, và
final step T có thể tiên tới ∞. Với những trường hợp này thì giá trị reward phải lựa


14
chọn một cách thích hợp để các giá trị đó và kết quả của các phép tính dựa trên các
giá trị đó nằm trong khoảng xác định.
Trong trường hợp có áp dụng discounting cho các bước thì:

Trong đó 0 <= γ <= 1 gọi là discount rate.

1.3.4 Markov Decision Process
1.3.4.1


Markov property

Markov property: trong quá trình học tăng cường thì agent ra quyết định dựa
trên các state signal thu được từ môi trường. Nếu một state signal chứa được đủ
thông tin cần thiết (ví dụ như về q trình trong q khứ) để agent có thể ra quyết
định thì gọi là Markov property. Thuộc tính này rất quan trọng đối với học tăng
cường vì các quyết định và các giá trị của các bước trong học tăng cường chỉ dựa
vào bước trước đó. Ví dụ như ta có probability distribution của một quá trình tại
thời điểm t+1:
Nếu state signal của quá trình này có thuộc tính Markov thì ta có thể tiên đoán
cho bước tiếp theo mà chỉ dựa vào các thơng số của bước hiện tại (bởi vì các state
signal của bước hiện tại đã chứa đủ thông tin cần thiết rồi). Khi đó probability
distribution sẽ được xác định như sau:
Trong thực tế thì có một số trường hợp các state signal khơng hồn tồn mang
thuộc tính Markov nhưng vẫn có thể xem như là xấp xỉ Markov để ứng dụng trong
quá trình học tăng cường.
1.3.4.2

Markov decision process

Học tăng cường chủ yếu được dựa trên mơ hình Markov Decision Process
(MDP). Với mơi trường “Markov chain” thì state tiếp theo chỉ phụ thuộc vào state
trước đó do state signal của bước trước đó đã bao gồm các thơng tin cần thiết. MDP
là sự mở rộng của “Markov chain” với sự có mặt của các action và reward. Mơi
trường Markov có thể là non-deterministic (với state và action xác định thì có thể
cho ra các state kế tiếp khác nhau ở những thời điểm khác nhau) hay stationary


15

(state và action xác định cho ra state kế tiếp giống nhau ở mọi thời điểm).
MDP được định nghĩa là 4-tuple:
S: tập hợp của các state.
A: tập hợp của các action.
T: SxA -> P(S): là mapping từ states và actions vào giá trị probabilistic
distribution.
ρ: SxA -> R: là payoff function, mapping từ state và action vào reward.
Trong trường hợp phức tạp hơn ta có POMDP (partially observable Markov
decision process). Đây là trường hợp mà agent khơng hề biết mình đang ở state nào
mà thay vào đó chỉ nhận được giá trị observation là một giá trị nào đó mà agent
quan sát được sau khi thực hiện 1 action. Ở mỗi bước trong POMDP, agent quan sát
được giá trị o(t) và thực hiện action a(t) rồi nhận được giá trị reward r(t).
Về mặt hình thức POMDP được định nghĩa là tuple(S, O, A, B, T, ρ):
S: là tập hợp của các states.
O: là tập các observations.
A: là tập các actions.
B: là observation function B:S->P(O).
T: SxA->P(S) là mapping từ state và action vào probability distributions.
ρ:SxA->R là payoff function, mapping từ state và action vào reward.
Với MDP, Xác suất của state tiếp theo s’ là:

Expected value của reward tiếp theo là:

Ví dụ: Recycling Robot MDP
Recycling robot (robot nhặt rác) là một ví dụ đơn giản của MDP. Robot được
trang bị ăc qui và trong quá trình vận hành thì phải cân nhắc đến lượng điện cịn lại
trong ăc qui để sắp xếp cơng việc sao cho hiệu quả nhất và dặc biệt là ln phải có
đủ năng lượng đủ để quay về nạp lại điện. Tại mỗi thời điểm, robot quyết định giữa
các việc sau:
Tiếp tục tiếp tục tìm rác (tốn nhiều năng lượng nhất).

Đứng yên tại chỗ chờ người đem rác tới (ít tốn năng lượng hơn).


16
Quay về nạp lại điện (năng lượng sắp hết).
Cách tốt nhất để nhận được rác là tích cực tìm kiếm, tuy nhiên làm như vậy thì
sẽ hết điện nhanh hơn. Nếu trong quá trình làm việc mà robot hết điện giữa chừng
thì sẽ nhận đwợc reward rất thấp.
Như vậy trạng thái (state) của robot gồm có High và Low. Các action có thể
lựa chọn là:

Khi mà năng lượng ở mức High thì bước tìm kiếm rác tiếp theo ln kết thúc
mà không bị hết pin giữa chừng. Tuy nhiên sau bước tìm kiếm rác thì năng lượng
giữ nguyên mức High với xác suất α và chuyển sang trạng thái Low với xác suất (1
– α). Nếu bước tìm kiếm rác được thực hiện khi năng lượng ở mức Low thì xác suất
năng lượng giữ nguyên mức Low là β còn xác suất hết pin là (1 – β). Trong trường
hợp hết pin giữa chừng thì robot phải đươc “cứu” và khi đó thì reward nhận được là
-3. Gọi R search và R wait là số lương rác tìm được bởi bước chủ động tìm kiếm và
bước chờ rác. Trong những bước này thì nếu được bao nhiêu rác thì được bấy nhiêu
reward. Cịn với bước về nạp lại điện thì reward = 0.
Bảng dưới đây liệt kê các action cùng với reward của từng action:


17

Transition graph được biểu diễn bằng đồ thị sau:


18
1.3.4.3


Value function

Hầu như tất cả các thuật toán học tăng cường đều dựa trên sự ước đoán giá trị
của value function. Giá trị ước đoán này thể hiện mức độ “tốt” của của vị trí hiện tại
của agent, được xác định bằng các reward của các bước tiếp theo. Value function
được xác định dựa theo từng policy nhất định.
Ta có policy π, state s ∈ S, và action a ∈ A(s). Xác suất action a được chọn tại
state s với policy π là π(s,a). Khi đó giá trị value function của state s với policy π là
V π (s) – chính là giá trị return được mong đợi trong giai đoạn bắt đầu từ s và đi
theo policy π. Với MDP thì giá trị value function được tính như sau:

Hàm V π được gọi là state-value function của policy π.
Ta cũng định nghĩa value function cho việc chọn action a tại state s với policy
π, gọi là Q π (s,a). Hàm này được xác định như sau:

Ta goi Q π là action-value function của policy π.
Các giá trị của V π và Q π có thể xác định được từ experience. Các phương
pháp cụ thể sẽ được trình bày ở phần sau. Các hàm này có thể được khai triển theo
kiểu đệ quy. Ví dụ như hàm V π được khai triển như sau:

Công thức trên được gọi là Bellman equation.


19
Ví dụ: bài tốn gridworld
Đồ thị dưới đây biểu diễn các giá trị của value function cho các state trong bài
tốn 4x3 gridworld:

Bài tốn gridworld này được mơ tả như sau: ta có (4x3) gridworld, vị trí khởi

đầu là (1,1) đích đến (goal) là (4,3). Giá trị reward cho mỗi bước đi là -0.04, còn
reward của goal là +1. Nếu đi vào ơ (4,2) thì nhận được reward là -1. Giá trị
discount γ = 1. Nếu xác định giá trị reward cho các vị trí theo phương pháp value
iteration (sẽ được trình bày trong phần kế tiếp) thì giá trị value function cho các
state sẽ như là hình vẽ.
1.3.4.4

Optimal value function

Giải quyết bài tốn về học tăng cường có nghĩa là tìm ra policy mà nhận được
nhiều reward nhất, gọi là optimal policy. Tương tự cũng cần xác định các hàm tối
ưu của state-value function và action-value function.
Gọi Π* là optimal policy, V* là optimal state-value function, Q* là optimal
action-value function. Khi đó ta có:

Nếu tính Q* theo V* thì:


20
Nếu sử dụng Bellman Optimality function thì:

Để tính được các giá trị tối ưu này thì ta dùng phương pháp iteration. Với
Value function thì thuật tốn như sau:
function VALUE- ITERATION(^^^, E) returns a Value function
inputs: mdp, là MDP với states S, transition model P , reward function R,
discount γ,

ε: giá trị error tối đa cho phép

Biến nội bộ: V, V', vectors của Value tại S, Ban đầu gán giá trị 0.

δ, giá trị thay đổi lớn nhất của bất kỳ state nào trong một iteration nào đó.
repeat
V ← V’ ; δ ← 0
for each state s in S do
V’[s] ← R[s] + γ max a

∑

P sas ' V[s’]

s'

If |V’[s] - V[s]| > δ then δ ← |V’[s] - V[s]|