PHƯƠNG PHÁP Q-LEARNING
VÀ ỨNG DỤNG CỦA PHƯƠNG PHÁP NÀY
TRONG VIỆC GIẢI QUYẾT MỘT SỐ BÀI TOÁN TÌM ĐƯỜNG

ThS. CHÂU MẠNH QUANG
Bộ môn Thiết kế máy
Khoa Cơ khí
Trường Đại học Giao thông Vận tải Tóm tắt: Q-learning là phương pháp học tăng cường rất hiệu quả cho bài toán tìm
đường do phương pháp này được thực hiện theo kiểu off-policy. Vì vậy phương pháp này được
điều chỉnh hoặc kết hợp với một số phương pháp khác để giải quyết các bài toán đặc biệt như
tìm đường trong mạng (Q-routing) hay tìm đường của hệ thống multi-agent (Ant-Q).
Summary: Q-learning is a very effective reinforcement learning method in solving path
finding problem because it uses off-policy approach. Thus, this method is also modified or
combined with other methods to deal with some special cases of the path finding problem.
Some examples are Q-routing for network routing problems and Ant-Q for transferring
knowledge in the multi-agent environment. CT 2
I. ĐẶT VẤN ĐỀ
Trước đây người ta giải quyết bài toán tìm đường bằng cách sử dụng các thuật toán tìm
đường cổ điển. Tuy nhiên các thuật toán tìm đường có rất nhiều hạn chế ví dụ như đòi hỏi môi
trường phải xác định và cố định và không xử lý được nhiều tình huống thực tế. Với sự phát triển
của trí tuệ nhân tạo, ngày nay các phương tiện với sự trợ giúp của máy tính có thể “học”, hay

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 toá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) đ
CT 2
ược định nghĩa là tập hợp (tuple) <S, A, T, ρ>:
S: tập các vị trí (hay trạng thái - state).
A: tập các hành động (action).
T: SxA -> P(S): là hàm xác suất (probability distribution function) cho từng cặp vị trí -
hành động. Hàm này gán giá trị xác suất cho từng cặp vị trí - 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 vị trí - 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à:
P = Pr{s =s’|s
t
=s,a
t
=a}
a
ss'
t+1
Và giá trị phản hồi là:
R = E{r |s
t
= s,a
t
= a,s = s’}
a
ss'

∑
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ự
đoán mức độ “tốt” của agent ở vị trí hiện tại trong quá 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 cặp vị trí - 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ị vị trí -
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 {R
t
|s
t
= s} = E { |s
t
= s}
π
π π
k
t+k+1
k0
r
∞
=
γ
∑
CT 2
Hàm giá trị theo cặp vị trí - hành động (action - state value function) Q được xác định như
sau:
Q
π

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 mỗi vị trí s) [2].
Các loại thuật toá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ớ quá 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 toá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 toán tìm đường.
III. PHƯƠNG PHÁP Q-LEARNING
Đây là phương pháp học theo kiểu off-policy. Quá trình học tăng cường có thể được thực
hiện theo hai cách: off-policy và on-policy. On-policy sử dụng một luật chọn hành động để thực
hiện các bước hành động để tối ưu hóa chính luật chọn hành động đó. Phương pháp off-policy
sử dụng một luật chọn hành động để thực hiện các hành động nhưng với mục đích là để tối ưu
hóa một luật chọn hành động khác.
Phương pháp này sử dụng hàm Q (action-state value function). Hàm Q được xác định bằng
phương pháp Q-learning như sau:
Q(s
t
,a
t

Repeat (cho từng bước của episode)
Chọn hành động a (chẳng hạn bằng phương pháp ε-greedy)
Thực hiện bước a, nhận được giá trị phản hồi r và vị trí tiếp theo s’
Điều chỉnh giá trị hàm Q:
Q(s, a) Q(s, a) + α[r + γ Q(s’, a’) – Q(s, a)]
←
a'
max
s
←
s’
Until s là vị trí đích hoặc đã thực hiện hết số lượng bước giới hạn của episode.
Với phương pháp này thì luật chọn hành động để học thông thường được thực hiện theo
phương pháp ε-greedy trong khi việc điều chỉnh giá trị hàm Q ứng với mỗi cặp vị trí – hành
động (s,a) được thay đổi dựa trên giá trị Q tối ưu của cặp (s’,a’) kế tiếp mà hành động a’ không
nhất thiết là hành động được chọn theo “policy” đang được áp dụng. Do đó phương pháp này
thuộc loại off-policy.
Xét về lý thuyết ta có thể nhận thấy phương pháp kiểu off-policy cho phép khám phá được
nhiều hơn so với on-policy nên khả năng tìm ra được những lối đi mới có quãng đường ngắn
hơn là cao hơn so với phương pháp on-policy. Thực nghiệm cũng xác nhận quan điểm này.
Để minh họa cho lập luận trên và đồng thời để mô tả cách áp dụng thuật toán Q-learning
vào bài toán tìm đường thông thường ta có thể thực hiện bài toán kinh điển gridworld bằng
phương pháp Q-learning và bằng một phương pháp khác theo kiểu on-policy và so sánh kết quả.
Phương pháp on-policy được chọn là SARSA – là phương pháp học rất hiệu quả theo kiểu on-
policy. Với phương pháp SARSA thì hàm Q được điều chỉnh sau mỗi bước thực hiện hành động
theo công thức sau:
CT 2

Hình 2. Chương trình thực nghiệm. Các mũi tên màu xanh là các hướng đi tối ưu - chính
là bộ luật hành động tối ưu. Các mũi tên màu hồng là các hướng đi tối ưu đã học được.
Các thông số cần được xác định là số ô chưa được tìm ra “policy” tối ưu và quãng đường
ngắn nhất xác định được. Kết quả thống kê số ô chưa tìm được “policy” tối ưu được ghi lại
trong các bảng thực nghiệm của [5]. Do khuôn khổ của bài báo có hạn nên chỉ trình bày được
một vài kết quả thực nghiệm:
Q-learning, ε = 0.75, 100 episode, max 100 bước/episode
γ = 1 γ = 0.75 γ = 0.5 γ = 0.25 γ = 0
α = 1 72 22 31 66 74
α = 0.75 50 64 66 51 74
α = 0.5 55 41 42 46 74
CT 2

SARSA, ε = 0.75, 100 episode, max 100 bước/episode
γ = 1 γ = 0.75 γ = 0.5 γ = 0.25 γ = 0
α = 1 72 74 68 73 74
α = 0.75 72 64 60 73 74
α = 0.5 66 68 51 54 74
Từ kết quả thực nghiệm được tiến hành ở [5] cho thấy mặc dù kết quả thực nghiệm phụ
thuộc vào nhiều yếu tố (các tham số α, γ, ε), đặc biệt là giá trị ε có ảnh hưởng rất nhiều đến kết
quả học của Q-learning (ε càng bé thì quá trình khám phá được thực hiện càng ít dẫn đến kết
quả học của Q-learning càng xấu đi), tuy nhiên xét về kết quả chung thì Q-learning thường tìm
được luật hành động tối ưu cho nhiều ô hơn.
Thực nghiệm tiếp theo so sánh kết quả thực tế của hai phương pháp học trong cùng điều
kiện tham số. Kết quả được xác định ở đây là đường đi ngắn nhất từ điểm khởi đầu đến đích sau
x chọn server z’ trong số các server kề cận với mình mà có giá trị Q nhỏ nhất để điều chỉnh lại
giá trị Q của chính mình. Quá trình học được thực hiện bằng cách cho một số lượng ngẫu nhiên
các server đồng loạt gửi các gói thông tin vào mạng và sau một số lần lặp đi lặp lại quá trình này
đủ lớn thì giá trị Q của các server trên mạng hội tụ về gần với giá trị tối ưu.
Thuật toán được mô tả như sau:
Ta gọi: Q
x
(d,y) - là thời gian ước đoán mà từ x ta gửi được gói thông tin đến d đi qua y kề
cận với x, bao gồm cả thời gian gói thông tin nằm trong hàng đợi của x.
Thuật toán gồm các bước:
Khi x nhận được gói thông tin thì gửi cho máy kề cận là y. Y được chọn theo quy luật học
(learning policy).
Sau khi x đã gửi gói thông tin cho y, x nhận được giá trị phản hồi từ y. Giá trị phản hồi này
là giá trị Q của z nào đó kề cận với y mà có giá trị Q
y
(d,z) nhỏ nhất. Gọi giá trị phản hồi này là t
ta có:
t = min
z is a neighbor of y
Q
y
(d,z).
Giả sử gói thông tin được gửi đã nằm trong hàng đợi của x thời gian là q, và thời gian để
chuyển gói tin từ x sang y là s. Khi đó giá trị Q mới được điều chỉnh cho x là:
Q
x
(d,y)

độ di chuyển qua lại của đàn kiến tại mỗi vị trí của con đường ngắn sẽ cao hơn con đường dài.
Do mật độ qua lại lớn hơn dẫn đến kết quả là nồng độ pheromone trên con đường ngắn càng
ngày càng cao hơn con đường dài. Kết quả cuối cùng là đàn kiến ngày càng từ bỏ con đường dài
và đi theo con dường ngắn. Đến một lúc nào đó sẽ không còn con kiến nào đi theo con đường
dài nữa mà tất cả đều đi theo con đường ngắn.
Thuật toán dựa trên hoạt động của đàn kiến có một số biến thể. Dạng đơn giản nhất gọi là
AS (Ant System). Thuật toán này chỉ dùng để giải quyết bài toán tìm đường. Ở mức cao hơn là
thuật toán ACO (Ant Colony Optimization). Thuật toán này cho phép các agent trương tác với
nhau để điều chỉnh hướng đi. Thuật toán ACO kết hợp với thuật toán Q-learning được gọi là
Ant-Q. Nội dung chi tiết về các thuật toán sẽ được trình bày ở các phần kế tiếp.
5.1. AS
Thuật toán này rất đơn giản. Mỗi agent được trang bị một buffer. Các agent được khởi
động đi tìm đường một cách ngẫu nhiên bắt đầu ở vị trí xuất phát. Các vị trí mà agent đi qua
được lưu vào buffer. Khi mà đường đi của agent nào đó đã vượt quá độ dài cho phép thì dù cho
agent chưa đến được đích cũng bị “bay hơi” giữa chừng. Các agent đến được đích sẽ được kiểm
tra buffer để xác định đường đi ngắn nhất.
5.2. ACO
Thuật toán này có sử dụng đến yếu tố pheromone. Với một agent k nào đó tại vị trí I, agent
chọn đi tới vị trí j liền kề với i theo xác suất sau:

CT 2
Trong đó:
η
ij
là giá trị heuristic cho bài toán. Với bài toán TSP (Trade Salesman Problem) thì η =
1/d
ij

Như vậy là bằng việc kết hợp với phương pháp Q-learning đã làm cho phương pháp ACO
trở nên hiệu quả hơn và kết quả học của các agent được thể hiện qua nồng độ pheromone trên
từng vị trí.
VI. KẾT LUẬN
Sử dụng phương pháp học tăng cường hiệu quả hơn sử dụng các phương pháp tìm đường
cổ điển trong việc giải quyết bài toán tìm đường do đòi hỏi ít điều kiện ràng buộc hơn (môi
trường không nhất thiết phải xác định, cố định, v.v …). Ngoài ra bằng cách áp dụng học tăng
cường ta có thể xử lý được nhiều tình huống ví dụ như như là giúp agent tránh được các vị trí
“nguy hiểm” như “rơi xuống hố” hay “ngã xuống từ vách đá” từ nhiều bước trước đó - và những
vấn đề mà các phương pháp tìm đường cổ điển không xử lý được.
CT 2
Q-learning là phương pháp học tăng cường rất hiệu quả trong việc giải quyết bài toán tìm
đường. Nguyên nhân là do phương pháp này được thực hiện theo kiểu off-policy, có nghĩa là áp
dụng một luật hành động để học và lại tối ưu hóa cho luật hành động khác.
Do Q-learning hiệu quả trong việc giải quyết bài toán tìm đường nên phương pháp này
được điều chỉnh hoặc kết hợp với một số phương pháp khác để giải quyết các bài toán đặc biệt
như tìm đường trong mạng (Q-routing) hay tìm đường của hệ thống multi-agent (Ant-Q). Tài liệu tham khảo
[1]. Reinforcement Learning: Theory and Application, I-TECH Education and Publishing, 2008.
[2]. Reinforcement Learning: An Introduction, Richard S. Sutton, The MIT Press, 1998.
[3]. Artificial Intelligence - A Modern Approach, Stuart Russel, Pearson Education Inc. 2003.
[4]. Reinforcement Learning By Policy Search, PhD Dissertation, Leonid Peskin, 2002.
[5]. Học tăng cường và quyết định Markov, luận văn thạc sĩ, Châu Mạnh Quang, 2009.
[6]. Technical report: Comparison of the Q-Routing and Shortest Path Routing Algorithms. F. Tekiner, Z.
Ghassemlooy and T.R. Srikanth
♦