HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------

VÕ HÀ QUỐC HUY

BÀI TOÁN BANDITS THEO NGỮ CẢNH
(CONTEXTUAL BANDITS) VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ KỸ THUẬT

TP.HCM - 2016


HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------

VÕ HÀ QUỐC HUY

BÀI TOÁN BANDITS THEO NGỮ CẢNH
(CONTEXTUAL BANDITS) VÀ ỨNG DỤNG
CHYÊN NGÀNH: HỆ THỐNG THÔNG TIN
MÃ SỐ:

60.48.01.04

LUẬN VĂN THẠC SĨ KỸ THUẬT
NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. BÙI XUÂN LỘC

TP.HCM - 2016

i
LỜI CAM ĐOAN
Tôi cam đoan đây là công trình nghiên cứu riêng của tôi.
Các số liệu và kết quả luân văn điều là trung thực và chưa từng ai công bố
trong các công trình nghiên cứu khác.

TP.HCM, ngày 20 tháng 06 năm 2016
Học viên thực hiện luận văn

Võ Hà Quốc Huy


ii
LỜI CẢM ƠN
Để hoàn thành luận văn này, ngoài sự nghiên cứu và những cố gắng của bản
thân, em xin gửi lời cảm ơn sâu sắc tới Tiến sĩ Bùi Xuân Lộc, giáo viên hướng dẫn
trực tiếp, tận tình chỉ bảo và định hướng cho em trong suốt quá trình nghiên cứu và
thực hiện luận văn.
Em xin gửi lời cảm ơn chân thành đến tất cả các Thầy Cô của trường Học
Viện Công Nghệ Bưu Chính Viễn Thông đã giảng dạy và dìu dắt chúng em trong
suốt quá trình học tập tại Trường.
Cuối cùng, em xin gửi lời cảm ơn đến gia đình, bạn bè và những người luôn
cổ vũ tinh thần, tạo điều kiện thuận lợi cho em học tập tốt và hoàn thành luận văn
này.
Em xin chân thành cảm ơn!
TP.HCM, ngày 20 tháng 06 năm 2016
Học viên thực hiện luận văn

Võ Hà Quốc Huy



iii
MỤC LỤC
LỜI CAM ĐOAN ........................................................................................................ i
LỜI CẢM ƠN .............................................................................................................ii
MỤC LỤC ................................................................................................................ iii
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ............................................. v
DANH SÁCH BẢNG ................................................................................................ vi
DANH SÁCH HÌNH VẼ ..........................................................................................vii
CHƯƠNG 1- TỔNG QUAN VỀ BANDITS THEO NGỮ CẢNH .......................5
 
1.
  Giới thiệu về các hệ thống trực tuyến ................................................................5
 
1.1.
  Khái niệm hệ thống......................................................................................5
 
1.2.
  Hệ thống thông tin .......................................................................................5
 
1.3.
  Hệ thống thương mại điện tử .......................................................................5
 
2.
  Bài toán Multi-armed Bandits ............................................................................7
 
2.1.
  Tổng quan về bài toán Multi-armed Bandits (MAB) ..................................7
 
2.2.

  Giới thiệu bài toán Multi-armed Bandits ..................................................... 8
 
2.2.1.
  Tiến trình Bandits..................................................................................8
 
2.2.2.
  Vấn đề bài toán Multi-armed Bandits ..................................................9
 
3.
  Bandits theo ngữ cảnh ......................................................................................11
 
3.1.
  Tổng quan bài toán Bandits theo ngữ cảnh ...............................................11
 
3.2.
  Vấn đề của bài toán ...................................................................................11
 
CHƯƠNG 2- THỰC TRẠNG NGHIÊN CỨU ....................................................14
 
1.
  Đưa về bài toán K- Armed Bandits ..................................................................14
 
1.1.
  Giới thiệu ...................................................................................................14
 
1.2.
  Một số định lý ............................................................................................14
 
2.
  Thuật toán EXP4 ..............................................................................................15

 
2.1.
  Giới thiệu thuật toán ..................................................................................15
 
2.2.
  Thuật toán ..................................................................................................16
 
Một số định lý ....................................................................................................17
 
3.
  Thuật toán EXP4.P ...........................................................................................17
 
3.1.
  Giới thiệu thuật toán ..................................................................................17
 
3.2.
  Thuật toán ..................................................................................................18
 
4.
  Thuật toán LinUCB ..........................................................................................20
 
4.1.
  Giới thiệu thuật toán ..................................................................................20
 
4.2.
  Thuật toán ..................................................................................................21
 


iv

4.3.
  Một số định lý: ...........................................................................................21
 
5.
  Thuật toán Epoch-Greedy ................................................................................22
 
5.1.
  Giới thiệu thuật toán ..................................................................................22
 
5.2.
  Thuật toán ..................................................................................................23
 
6.
  Thuật toán Thompson Sampling with Linear Regression ................................24
 
6.1.
  Giới thiệu thuật toán ..................................................................................24
 
6.2.
  Thuật toán ..................................................................................................25
 
7.
  Thuật toán Thompson Sampling with Logistic Regression .............................25
 
7.1.
  Giới thiệu ...................................................................................................25
 
7.2.
  Thuật toán ..................................................................................................26
 

CHƯƠNG 3- THỰC NGHIỆM .............................................................................28
 
1.
  Các phương pháp đánh giá thuật toan bandits theo ngữ cảnh ..........................28
 
1.1.
  Phương pháp dựa trên mô phỏng ...............................................................28
 
1.2.
  Phương pháp dựa trên đánh giá dữ liệu offine ..........................................29
 
2.
  Giới thiệu ngôn ngữ Julia .................................................................................31
 
3.
  Giới thiệu về dữ liệu dùng trong đánh giá thuật toán bandits ..........................34
 
4.
  Kết quả đánh giá với dữ liệu click quảng cáo trên di đông ..............................36
 
4.1.
  Thuật toán EXP4 .......................................................................................36
 
4.2.
  Thuật toán LINUCB ..................................................................................37
 
4.3.
  Thuật toán Uniform ...................................................................................39
 
4.4.

  Kết quả thực nghiệm các thuật toán ..........................................................40
 
KẾT LUẬN VÀ KIẾN NGHỊ ................................................................................42
 
DANH MỤC TÀI LIỆU THAM KHẢO...............................................................44
 


v

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Từ viết tắt

Tiếng Anh

Tiếng Việt

MPD

Markov Decision Processes

Tiến trình quyết định Markov

MAB

Multi-armed Bandit

EXP

Expert advice


Lời khuyên của chuyên gia

LIN UCB

Linear Upper Confidence Bound

Thuật toán chặn trên độ tự tin
tuyến tính

ERM

Empirical Risk Minimization

Giảm thiểu rủi ro thực nghiệm

CTR

Click-through Rate

Tỷ lệ nhấp chuột


vi

DANH SÁCH BẢNG
Bảng 1.1: Bốn giả định lý luận không chắc chắn từ ................................................ 7
 
Bảng 2.1: Mô tả một số thuật toán liên quan tới bài toán Bandits theo ngữ cảnh . 14
 

Bảng 3.1: Mô tả dữ liệu mô phỏng ........................................................................ 35
 
Bảng 3.2: Kết quả thực nghiệm của thuật toán EXP4, LINUCB và Uniform ....... 40
 


vii

DANH SÁCH HÌNH VẼ
Hình 1.1: Mô tả hệ thống thương mại điện tử ......................................................... 6
 
Hình 1.2: Mô tảcác arm của bài toán ....................................................................... 7
 
Hình 3.1: Kết quả đánh giá của một số thuật toán dựa trên mô phỏng của bài toán
bandits .................................................................................................................... 29
 
Hình 3.2: Mô tả thời gian chuẩn liên quan đến C (nhỏ hơn là tốt hơn, hiệu suất C =
1,0) ......................................................................................................................... 32
 
Hình 3.3: Mô tả cú pháp, các dòng lệnh trong Julia .............................................. 33
 
Hình 3.4: Mô tả hình ảnh chụp từ phiên bản Notebook IJulia ............................... 34
 
Hình 3.5: Định dạng thông tin của dữ liệu............................................................. 36
 
Hình 3.6: Biểu đồ kết quả đánh giá của thuật toán EXP4, LINUCB và Uniform . 40
 


1


MỞ ĐẦU
a. Tính cấp thiết của đề tài
Ngày nay, cùng với sự phát triển của ngành công nghệ thông tin là sự phát triển
với tốc độ chóng mặt,ước tính mỗi ngày trên thế giới có khoảng 15 tỉ lượt truy cập
(www.nghiencuuthitruong.net) vào các hệ thống website. Với kết quả số liệu thống
kê trên, đã một phần nào đó cho chúng ta thấy nhu cầu của người sử dụng ngày
càng cao. Do vậy, các website hay các hệ thống trực tuyến cần phải đưa ra các
chính sách phù hợp và các dịch vụ ngày càng tốt hơn để hỗ trợ cho những nhu cầu
của người sử dụng. Hiện nay đã có rất nhiều nghiên cứu về vấn đề này, một trong
những nghiên cứu mà được nhiều người quan tâm đến là bài toán Bandits theo ngữ
cảnh (Contextual Bandits). Bài toán Bandits theo ngữ cảnh này là gì? Nó sẽ giải
quyết được những vấn đề nào?…Một cái nhìn tổng quan về bài toán Bandits theo
ngữ cảnh sẽ được đưa ra dưới đây để trả lời cho câu hỏi trên.
Một trong những bài toán liên quan tới bài toán Bandits theo ngữ cảnh là bài
toán Multi-Armed Bandits (MAB). Bài toán đó được mô tả như sau: giả sử, ta có
tập K các đồng xu, mỗi đồng xu có hai trường hợp là mặt sấp và mặt ngửa.Với quy
định, khi ta tiến hành tung một đồng xu nếu xuất hiện mặt ngửa thì ta sẽ có điểm
thưởng và ngược lại, nếu ta tung đồng xu mà xuất hiện mặt sấp thì không có điểm
thưởng. Gọi Pi là xác suất xuất hiện mặt ngửa của một đồng xu thứ i. Tại một thời
điểm ta chỉ tung một đồng xu và cho biết kết quả điểm thưởng (1 hoặc 0) của đồng
xu đó. Yêu cầu bài toán đặt ra làm sao đạt được số điểm thưởng nhiều nhất trong
quá trình chọn đồng xu để tung.
Để có thông tin chi tiết về xác suất xuất hiện mặt ngửa của các đồng xu này thì
ta tiến hành khám phá (explore) bằng cách tung từng đồng xu để ghi nhận lại kết
quả. Với việc ghi nhận lại kết quả đó, sẽ cung cấp cho ta thông tin của từng đồng
xu. Từ những thông tin đã có, ta sẽ khai thác (exploit) thông tin để có sự lựa chọn
đồng xu nào là tối ưu nhất. Nhưng việc ta khám phá để lấy được thông tin ngữ cảnh
của các đồng xu cũng đồng nghĩa với việc vì ta sẽ mất một khoản chi phí, về thời
gian cho việc khai thác. Do vậy,để đưa ra một quyết định lựa chọn đúng đắn thì ta

phải cân bằng giữa hai yếu tố khám phá các thông tin và khai thác các thông tin từ
các đối tượng.


2
Bài toán Bandits theo ngữ cảnh là bài toán được mở rộng của Multi-Armed Bandits
cho trường hợp xác suất của các đồng xu Pi thay đổi theo ngữ cảnh. Ví dụ, một
người dùng truy cập vào hệ thống website, nếu người dùng đó là nam thì họ sẽ có
nhiều khả năng click vào các mục quảng cáo về xe hơi, nhà cửa hơn. Trong khi,
người dùng đó là nữ thì họ sẽ có nhiều khả năng click vào các mục quảng cáo như
thời trang, làm đẹp, gia đình hơn. Ngữ cảnh ở đây chính là những thông tin khác
nhau của người dùng mà hệ thống thu thập được trong quá trình giám sát người
dùng. Một số vấn đề mà bài toán Bandits theo ngữ cảnh có thể giải quyết:
l

Trong lĩnh vực tuyền thông tin, các gói tin truyền đi trên mạng từ máy nguồn
tới máy đích có thể đi qua rất nhiều đường khác nhau với các giao thức khác
nhau, vậy làm sao chúng ta biết đường nào là đường đi tốt nhất. Bài toán
Bandits có thể được áp dụng để đưa ra lựa chọn một đường đi cho gói tin
truyền đi trên mạng một cách tối ưu.

l

Trong lĩnh vực quảng cáo, Bài toán Bandits có thể được áp dụng được trong
việc hiển thị nội dung của các bài quảng cáo trên các hệ thống trực tuyến hay
website: làm sao ta biết được tại một thời điểm số lượng người dùng nào sẽ
truy cập vào những lien kết quảng cáo loại nào nhiều để từ đó hệ thống sẽ cung
cấp thông tin cho người dùng một cách tốt nhất.

l


Ngoài ra, bài toán Bandits theo ngữ cảnh này có thể hỗ trợ các lĩnh vực khác
như: trong việc chuẩn đoán và đưa ra cách điều trị trong y học, trong việc tìm
kiếm thông tin làm sao đưa ra thông tin chính xác nhất cho người dùng…

b. Tổng quan về vấn đề nghiên cứu
Hiện nay trên thế giới đã có rất nhiều nghiên cứu về bài toán Bandits theo ngữ
cảnh với nhiều ứng dụng khác nhau. Các thuật toán được sử dụng thường được áp
dụng trên dữ liệu của người dùng tại các website hay các hệ thống trực tuyến.
Luận văn sẽ tập trung vào nghiên cứu thuật toán Bandits theo ngữ cảnh được đề
xuất trong một số bài báo dưới đây:
Bài báo ‘A Survey on Contextual Multi-armed Bandits’[5] của tác giả Li Zhou
định nghĩa bài toán Multiarmed Bandits, bài toán Bandits theo ngữ cảnh và đưa ra
một số ràng buộc của bài toán này. Bên cạnh đó, thông qua bài báo này cũng đưa ra
một số thuật toán như: Reduce to MAB, EXP4, EXP4.P, Lin UCB, EpochGreedy…cũng như giới thiệu về một số ứng dụng trên thực tế.


3
Bài báo‘A Contextual-bandit Approach to Personalized News Article
Recommendation’ [6] của tác giả Lihong Li và các cộng sự nghiên cứu về các dịch
vụ web cá nhân (Personalized web services) như là một vấn đề trong bài toán
Bandits theo ngữ cảnh. Thông qua bài viết này, nhóm tác giả này cũng đưa ra được
ba vấn đề chính: thứ nhất, đưa ra được thuật toán mới trong bài toán Bandits theo
ngữ cảnh với hiệu quả cao. Thứ hai, bất kỳ thuật toán Bandits nào cũng đánh giá
được độ tin cậy việc sử dụng lưu lượng truy cập ngẫu nhiên của người dùng trong
quá khứ. Thứ ba, sử dụng phương pháp đánh giá không trực tuyến và thành công
trên bộ dữ liệu của Yahoo.
Bài báo‘A Fast and Simple Algorithm for Contextual Bandit’ [1] của tác giả
Alekh Agarwal và các cộng sự đã nghiên cứu phương pháp tối ưu thuật toán để đảm
bảo tính hiệu quả của bài toán Bandits theo ngữ cảnh.


c. Mục tiêu nghiên cứu
Đề tài nhằm thực hiện các mục tiêu sau:
Nghiên cứu tổng quan bài toán Bandits theo ngữ cảnh, một số thuật toán liên
quan trong việc giải quyết vấn đề bài toán Bandits theo ngữ cảnh và phương pháp
tiếp cận của bài toán Bandits theo ngữ cảnh để đánh giá bài toán. Từ đó, chúng ta sẽ
đưa ra kết quả đánh giá thuật toán đó sẽ phù hợp với ứng dụng trong hệ thống trực
tuyến.
Phương pháp nghiên cứu lý thuyết kết hợp với thực nghiệm để phân tích và đánh
giá kết quả của bài toán Bandits theo ngữ cảnh.
Phần còn lại của luận văn được tổ chức như sau:
Chương 1: Tổng quan về Bandits theo ngữ cảnh
Tóm tắt chương: Trong chương này chúng tôi sẽ giới thiệu hệ thống trực tuyến,
đồng thời giới thiệu các định nghĩa và các khái niệm liên quan tới Multi-armed
banditsvà Bandits theo ngữ cảnh gổm 3 phần:
-­‐

Giới thiệu về hệ thống trực tuyến

-­‐

Bài toán Multi-armed bandits

-­‐ Bài toán Bandits theo ngữ cảnh
Chương 2: Thực trạng nghiên cứu
Tóm tắt chương: Trong chương này chúng tôi sẽ nghiên cứu về lý thuyết các định
nghĩa, công thức, định lý và các ký hiệu,... của một số thuật toán liên quan tới bài
toán Bandits theo ngữ cảnh. Việc nghiên cứu các thuât toán này giúp chúng ta có cơ
sở lý thuyết để giúp cho việc tiến hành cài đặt và chạy thực nghiệm.



4
-­‐

Thuật toán Reduce to MAB

-­‐

Thuật toán Uniform

-­‐
-­‐

Thuật toán EXP4
Thuật toabs EXP4.P

-­‐

Thuật toán Lin UCB

-­‐

Thuaatn toán Epoch-Greedy

-­‐

Thuật toán Thompson Sampling with Linear Regression

-­‐


Thuật toán Thompson Sampling with Logistic Regression

Chương 3: Thực nghiệm
Tóm tắt chương: Tiến hành trình bày các thực nghiệm, ghi nhận kết quả, rút ra nhận
xét và đánh giá kết quả thực nghiệm đó gồm các nội dung:
-­‐

Các phương pháp đánh giá bài toán Bandits theo ngữ cảnh

-­‐
-­‐

Xây dựng demo với dữ liệu thực
Ngôn ngữ cài đặt julia

-­‐

Đánh giá và kết quả đánh giá

-­‐

Kết luận


5

CHƯƠNG 1- TỔNG QUAN VỀ BANDITS THEO NGỮ CẢNH
1. Giới thiệu về các hệ thống trực tuyến
1.1.


Khái niệm hệ thống
Hệ thống là tập hợp gồm nhiều phần tử có mối quan hệ ràng buộc lần nhau,

tác động chi phối lẫn nhau theo các quy định để trở thành một chỉnh thể và cùng
hoạt động hướng tới mục đích chung.
Điều kiện để trở thành hệ thống: gồm hai yếu tố là tập hợp các yếu tố và
những mối quan hệ, liên hệ lẫn nhau trong các yếu tố đó.
Ví dụ: một cỗ máy là một hệ thống các chi tiết liên kết với nhau thực hiện chức
năng của cổ máy, hệ thống giao thông, hệ thống truyền thông, hệ thống các trường
đại học ...

1.2.

Hệ thống thông tin
Hệ thống thông tin (information system) là một tập hợp và kết hợp của các

phần cứng, phần mềm và các hệ thống mạng truyền thông được xây dựng và sử
dụng thu thập, tạo, tái tạo, phân phối và chia sẽ các dữ liệu, thông tin và tri thức
nhằm phục vụ các mục tiêu tổ chức.
Các tổ chức có thể sử dụng các hệ thống thông tin với nhiều mục đích khác
nhau. Trong việc quản trị nội bộ, hệ thống thông tin sẽ giúp đạt được sự thông hiểu
nội bộ, thống nhất hành động, duy trì sức mạnh của tổ chức, đạt được lợi thế cạnh
tranh.Đối với bên ngoài, hệ thống thông tin giúp nắm bắt được nhiều thông tin về
khách hàng hơn hoặc cải tiến dịch vụ, nâng cao sức cạnh tranh, tạo đà cho phát
triển.
Các đặc điểm của hệ thống: Thành phần, liên hệ giữa các thành phần, ranh giới,
mục đích, môi trường, giao diện, đầu vào, đầu ra, ràng buộc.
Các thành phần của hệ thống thông tin: các phần cứng, phần mềm, các hệ
thống mạng, dữ liệu, con người trong hệ thống thông tin.
Ứng dụng của hệ thống thôngtin:hệ thống thương mại điện tử (ecommerce)…


1.3.

Hệ thống thương mại điện tử

Thương mại điện tử (E-commerce, Electronic commerce) là hình thái hoạt động
thương mại bằng phương pháp điện tử; là việc trao đổi thông tin thương mại thông
qua các phương tiện công nghệ điện tử mà nói chung là không cần phải in ra giấy


6
trong bất cứ công đoạn nào của quá trình giao dịch. (nên còn được gọi là thương
mại không giấy tờ).
Hệ thống thương mại điện tử là một hệ thống mà các hoạt động được tiến hành
bằng những phương tiện điện tử, vẫn mang bản chất như các hoạt động thương mại
truyền thống. Tuy nhiên, thông qua các phương tiện điện tử các hoạt động thương
mại được nhanh hơn, hiệu quả hơn, giúp việc tiết kiệm chi phí và mở rộng không
gian kinh doanh. Hệ thống thương mại điện tử được biết tới như một phương thức
kinh doanh hiệu quả từ khi Internet hình thành và phát triển. Chính vì vậy, nhiều
người hiểu như là một công cụ giao dịch thương mại.
Ví dụ: hệ thông mua hàng trực tuyến, hệ thống tra cứu thông tin, hệ thống cung
cấp thông tin…

Hình 1.1: Mô tả hệ thống thương mại điện tử
(Nguồn: />

7

2. Bài toán Multi-armed Bandits
2.1.


Tổng quan về bài toán Multi-armed Bandits (MAB)

Hình 1.2: Mô tảcác arm của bài toán
(Nguồn: />Trong quá trình nghiên cứu, để đưa ra một quyết định cho các đối tượng thì phải
dựa trên những quan sát trong thế giới thực. Những quan sát này thường cung cấp
các thông tin không đầy đủ. Do đó, các đối tượng không thể dự đoán được kết quả
của các hành động,cho nên kết luận thường không chắc chắn. Các nhà nghiên cứu
đã đưa ra 4 giả định luận lýđược mô tả tại bảng 1, trong mỗi trường hợp của kịch
bản đưa ra sẽ có những khuyết điểm riêng. Đối với cả hai giả định Multi-armed
bandits và Reinforcement Learning thì các mô hình này được đưa ra từ dữ liệu
thường không xác định được, trong khi Decision theory và Markov Decision
Processes (MDP) các mô hình được đưa ra một cách ngẫu nhiên. Tuy nhiên, giả
định của Multi-armed bandits đưa ra là các hành động cuả các đối tượng không thay
đổi theo trạng thái của thế giới thực, như vậy thì không đúng với kịch bản
Reinforcement Learning.
Bảng 1.1: Bốn giả định lý luận không chắc chắn từ
Multi-armed Bandits

Reinforcement Learning

Decision theory

Markov Decision Process
(Nguồn:[8])


8
Bài toán Multi-armed Bandits là vấn đề phân bố tuần tự của một lớp liên
quan tới một hay một số các phương pháp được chọn của kế hoạch. Như vậy, vấn

đề là chúng ta tiến hành xây dựng mô hình giữa các cuộc xung đột cơ bản giữa việc
lựa chọn (các phương pháp) mà hiệu quả thường cao, so với việc đưa ra quyết định
mà bỏ qua lợi ích hiện tại với các dự án tiềm năng có phần tốt hơn trong tương lai.
Bài toán Multi-armed Bandits đưa ra mô hình phân bố nguồn tài nguyên trong các
vấn đề cho một số ngành công nghệ và các ngành khoa học như là quản lý cảm
biến, hệ thống sản xuất, kinh tế và mạng thông tin liên lạc, các thử nghiệm lâm
sàng, lý thuyết điều khiển, lý thuyết tìm kiếm...
Trong bài toán MAB cổ điển, vấn đề của bài toán là tại mỗi thời gian thì chỉ
có một phương pháp được đưa ra xem xét để đánh giá. Các kế hoạch phân bố có thể
thay đổi theo trạng thái; các đối tượng mà ta đưa ra xem xét lại không thay đổi trạng
thái. Nhìn chung, việc đưa ra phương pháp tuần tự là vấn đề có thể giải quyết bởi
các chương trình động, mà nó dựa trên phương pháp quy nạp ngược, đưa ra những
phương thức tốt để giải quyết cho vấn đề tối ưu động. Với cấu trúc đặc biệt của bài
toán MAB cổ điển đã khám phá ra chỉ số mà chính sách tối ưu có thể tính toán bằng
phương pháp chuyển tiếp, với phương pháp này thì ta tính toán ít chuyên sâu hơn
phương pháp quy nạp ngược.

2.2.

Giới thiệu bài toán Multi-armed Bandits

2.2.1. Tiến trình Bandits
Tiến trình single – armed bandit được mô tả trạng thái của các arm (đối
tượng khảo sát), đặc trưng bởi các cặp tuần tự ngẫu nhiên ({X(0), X(1),…,},
{R(X(0)), R(X(1)),…, }), trong đó X(n) biểu thị trạng thái của một đối tượng (các
arm mà ta đang xem xét) sau khi được vận hành n lần và R(X(n)) biểu thị một kết
quả đạt được khi đối tượng đó hoạt động trong thời gian thứ n. Trạng thái X(n) là
giá trị thực biến ngẫu nhiên và R(X(n)) là giá trị ngẫu nhiên lấy trong dãy R+. Tóm
lại, khi đối tượng đó hoạt động trong thời gian thứ n thì trạng thái nó sẽ thay đổi
theo

X(n) = fn-1(X(0),…,(X(n-1), W(n-1))

(1.1)

Với fn-1 được đưa ra và {W(n), n = 1,2, …}là dãy độc lập các biến có giá trị thực
ngẫu nhiên và giá trị này độc lập với X(0) và được mô tả dưới dạng thống kế.


9

2.2.2. Vấn đề bài toán Multi-armed Bandits
Multi-armed Banditslà vấn đề cổ điển trong lý thuyết đánh giá và đưa ra một
quyết định cụ thể. Vấn đề này là được mô hình hoá một cách đơn giản số lần luân
phiên của các arm ứng với mỗi lần luân phiên đó chúng ta sẽ có một điểm thưởng
ngẫu nhiên với kết quả dự kiến là tốt nhất. Một trong những tính năng hấp dẫn của
vấn đề là chia thành nhiều nhánh. Với gốc độ lý thuyết thì đơn giản nhưng nó là vấn
đề rất quan trọng trong việc dự đoán và đưa ra quyết định,chăng hạn như sự cân
bằng giữa việc thăm dò và khai thác.
Vấn đề này đã được nghiên cứu năm 1940. Vấn đề này được giải quyết bằng
một chương trình động ngẫu nhiên, nhưng không có tiến bộ đáng kể trong việc tìm
hiểu bản chất của giải pháp tối ưu của nó đã được thực hiện cho đến khi Gittins và
Jones cho thấy một giải pháp tối ưu là đưa ra loại chỉ số. Nghĩa là, đối với mỗi quá
trình Bandit người ta có thể tính toán những gì Gittins gọi là chỉ số giao động, mà
chỉ phụ thuộc vào quá trình đó, và sau đó tại mỗi thời điểm người điều khiển hoạt
động trên các tiến trình Bandit với chỉ số cao nhất. Vì vậy, việc tìm kiếm một chính
sách lập lịch trình tối ưu, mà ban đầu đòi hỏi các giải pháp của một vấn đề k-armed
bandit, làm giảm đến việc xác định chỉ số dao động cho k single bandit duy nhất, do
đó làm giảm sự phức tạp của vấn đề theo cấp số nhân.
Một quá trình Multi-armed Bandits là quá trình thu thập tập K độc lập single
armed. Các vấn đề liên quan của bài toán MAB bao gồm tiến trình Multi-armed

Bandits và người điều khiển (gọi là bộ xử lý). Tại một thời điểm người điều khiển
chỉ có thể điều khiển chính xác một đối tượng mà ta nghiên cứu, tất cả các đối
tượng khác ở trạng thái đứng yên. Mỗi đối tượng thứ i, với i = 1,2, …, k được mô tả
một cách tuần tự
{(Xi(Ni(t)), Ri(Xi(Ni(t)))), Ni(t) = 0, 1, 2, …,t; t = 0,1, 2,…}
Trong đó Ni(t) mô tả số lần đối tượng i đã được khai thác tại thời điểm t, U(t)
=U1(t),…,UK(t) là các hành động được kiểm soát được thực hiện bởi người điều
khiển tại thời điểm t. Do vậy, người điều khiển có thể biết được hành động chính
xác trên tại một thời điểm, điều khiển hành động U(t) có giá trị trong khoảng {e1,…,
ek} trong đó ej = (0, …, 0, 1, 0, …, 0) là một đơn vịvector k-1 với 1 tại vị trí thứ j.
Các đối tượng khác không hoạt động , cụ thể như sau:


10
Xi(Ni(t+1))
f Ni(t)(Xi(0),…, Xi(Ni(t)),Wi(Ni(t))) nếu Ui(t) = 1
=

(1.2)
Xi(Ni(t)),

nếu Ui(t) = 0

Và
Ni(t),
Ni(t+1) =

nếu Ui(t) = 0
(1.3)


nếu Ui(t) = 1

Ni(t) + 1,

với mọi i = 1, 2, ..., k. Như vậy Ni(t), thời gian tại thời điểm đó của đối tượng
thứ i, chỉ tăng khi người điều khiển hoạt động trên đối tượng thứ i tại thời điểm t;
nghĩa là, chỉ khi Ui(t) = 1. {Wi(n); i = 1, ..., k; n = 0, 1, ...} là một dãy các biến ngẫu
nhiên độc lập mà {X1 (0), ..., Xk (0)} và đã được biết đến khi chúng ta mô tả thống
kê.
Đối tượng thứ i tạo ra một kết quả (điểm thưởng) chỉ khi nó được vận hành.
Hay Ri(t) là các điểm thưởng được tạo ra bởi đối tượng i tại thời điểm t; sau đó

Ri(t) = Ri(X(Ni(t).Ui(t)) =

Ri(Xi(Ni(t))),
0,

nếu Ui(t) = 1,

(1.4)

nếu Ui(t) = 0,

Chính sách lập lịch trình γ: = (γ1, γ2, ...) là một quy tắc quyết định như vậy mà
tại mỗi thời điểm t ngay lập tức, các hành động kiểm soát U(t) có giá trị trong
{e1,..., ek} theo
U(t) = γt(Z1(t),…, Zk(t), U(0),…, U(t-1)),

(1.5)


trong đó,
Zi(t) = [Xi(0),…, Xi(Ni(t))].

Các vấn đề MAB là như sau đây: Xác định một chính sách lập kế hoạch làm sao
cho tối ưu
k
⎡∞
⎤
J γ := E ⎢∑ β t ∑ Ri ( X i ( Ni (t )) | Z (0) ⎥
⎣ t =0 i =1
⎦

(1.6)


11

3. Bandits theo ngữ cảnh
3.1. Tổng quan bài toán Bandits theo ngữ cảnh
Bandits theo ngữ cảnh là bài toán được sử dụng trong máy học, một thuật toán
làm cho các quyết định tuần tự theo các phương thức sau: trong mỗi lần thử thực
nghiệm, một ngữ cảnh được đưa ra, thuật toán chọn một hành động từ các thiết lập
cố định và được biết đến của các hành động có thể, và sau đó là điểm thưởng cho
hành động này được tiết lộ; điểm thưởng có thể phụ thuộc vào ngữ cảnh, và có thể
thay đổi theo thời gian. Có rất nhiều vấn đề mà chúng ta có thể nghiên cứu bài toán
Bandits theo ngữ cảnh. Một ví dụ của bài toán Bandits theo ngữ cảnh được lựa chọn
quảng cáo cho một công cụ tìm kiếm. Ở đây, mục tiêu là để chọn quảng cáo có lợi
nhuận cao nhất để hiển thị cho người sử dụng đưa ra dựa trên một truy vấn tìm kiếm
và các thông tin sẵn có về người sử dụng này, và tối ưu hóa các lựa chọn quảng cáo
theo thời gian dựa trên phản hồi của người dùng như nhấp chuột. Mô tả này đưa ra

nhiều chi tiết quan trọng, một trong số đó là mỗi quảng cáo được liên kết với một
ngân sách vốn làm hạn chế số lượng tối đa của doanh thu quảng cáo mà có thể tạo
ra.
Hai vấn đề mà chúng ta cần quan tâm khi giải quyết bài toán này là giải pháp tối
ưu với chi phí hạn chế và giải pháp tối ưu với chi phí không hạn chế. Giả sử trong
quảng cáo trực tuyến với giải pháp được chọn là tốt nhất dự kiến là doanh thu cao
nhưng chi phí cho việc quảng cáo đó lại thấp và hiệu quả mang lại người dùng chỉ
xem một lần. Đối với các trường hợp như thế này thì chúng ta sẽ không sử dụng
trong quảng cáo trực tuyến. Ở góc độ các nhà quảng cáo thì chúng tôi mong muốn
rằng quảng cáo này phải được người dùng quan tâm nhiều hơn và ở góc độ người
dùng thì họ mong muốn có đa dạng về sự lựa chọn. Như vậy, để làm được điều này
thì chúng ta phải tăng phần chi phí lên cùng với phương pháp tối ưu. Tuy nhiên
không phải đối với tất cả các trường hơp nào cũng đúng với điều này. Chúng ta cần
phải đưa ra lựa chọn một cách hợp lý nhất. Trên thực tế, vấn đề này là rất quan
trọng một trong những giải pháp chính là bài toán Bandits theo ngữ cảnh.

3.2. Vấn đề của bài toán
Chúng ta xem xét một thiết lập trực tuyến, trong đó mỗi vòng một thuật toán
quan sát một ngữ cảnh X từ một tập hợp được biết đến có thể vô hạn của thể ngữ


12
cảnh X và chọn một hành động một từ một tập hữu hạn được biết A. Thực tế sau đó
chỉ định một điểm thưởng r ∈ [0, 1] và phương pháp được sử dụng. Có d phương
pháp có thể được sử dụng và được xác định bởi số ci∈ [0, 1] cho mỗi phương pháp
thứ i. Vì vậy, chúng ta có các vector (ri; c1, cd...), Mà chúng ta gọi là các vector kết
quả; vector kết quả này có thể phụ thuộc vào các hành động được lựa chọn số lần
chúng ta tiến hành thực nghiệm. Có một hạn chế khó biết Bi∈ R + vào việc sử dụng
phương pháp thứ i; chúng ta gọi nó là một chi phí cho phương pháp thứ i. Các thuật
toán dừng lại ở thời gian τ sớm nhất khi có bất kỳ ràng buộc chi phí bị vi phạm;

tổng điểm thưởng của nó là tổng hợp của những điểm thưởng trong tất cả các lần
thực nghiệm trước τ. Mục tiêu của thuật toán là tối đa hóa tổng điểm thưởng dự kiến
ở thời điểm ban đầu.
Chúng tôi cũng phải quan tâm trong khi chúng ta tiến hành thực nghiệmcó một
yếu tố xảy ra là quá trình tiến hành thực nghiệm nhưng mang lại hiệu quả không cao
như chúng ta kì vọng hay gọi là yếu tố đáng tiếc (regret) tại một thời điểm cụ thể T
được biết đến với thuật toán. Thông thường, chúng ta mô tả dưới dạng mô hình thời
gian như một giải pháp cụ thể với chi phí T và tiêu hao xác định trong tổng số 1 cho
mỗi hành động Bi ≤ T cho mọi giải pháp thứ i.
Giả định Stochastic: Chúng tôi giả định rằng có tồn tại một sự phân phối D
chưa biết (x, r, ci), được gọi là phân phối kết quả, từ đó mỗi lần quan sát số lượt
thực hiện được tạo ra một cách độc lập, nơi các vectơ được đánh số chỉ mục bởi
những hành động cá nhân. Đặc biệt, ngữ cảnh x được rút ra từ phân phối cận biên
Dx, và các điểm thưởng và phương pháp sử dụng được quan sát cho mỗi hành động
một được vẽ từ sự phân bố D có điều kiện (ra, ci,a | x). Để rõ ràng, chúng tôi giả định
rằng sự phân bố nhỏ so với các ngữ cảnh D(x).
Quy định và tiêu chuẩn: Một thuật toán được đưa ra một tập Π hữu hạn các
chính sách ánh xạ từ các ngữ cảnh để hành động. Tiêu chuẩn của chúng tôi là một
thuật toán giả thuyết mà biết sự phân bố kết quả D, và ra quyết định tối ưu cho kiến
thức này. Điểm chuẩn được giới hạn trong chính sách Π: trước mỗi lần thực hiện,
phải cam kết một số π chính sách ∈ Π, và sau đó chọn hành động π (x) khi đến các
hoàn cảnh cụ thể x.


13
Ký hiệu: r (π) = E (x, r) ~D [rπ (x)] và ci (π) = E (x, ci) ~D [ciπ (x)] Là dự kiến
điểm thưởng cho mỗi vòng và dự kiến mỗi vòng tiêu thụ tài nguyên i cho π chính
sách. Tương tự, xác định r (P) = Eπ~P [r (π)] và ci (P) = Eπ~P [ci (π)] như phần mở
rộng tự nhiên đến một P phân phối qua các chính sách. Các tuple µ = ((r (π); c1 (π),
cdd(π)):... Π ∈ Π) được gọi là kết quả được mong đợi của tuple. Đối với một P

phân phối qua các chính sách, để cho P (π) là xác suất mà P trên π chính sách. Được
sử dụng bởi ký hiệu này, cho P (a | x) = P π (x) = P (π) là xác suất mà P trên hành
động một ngữ cảnh nhất định x. Như vậy, mỗi ngữ cảnh x gây ra tại một phân phối
P ( x) cho các hành động.
Điểm chuẩn và xấp xỉ tuyến tính:
Với luật phân phối P được định nghĩa một thuật toán ALGP: trong mỗi vòng một
π chính sách được lấy mẫu độc lập từ P, và các hành động a = π (x) đã được chọn.
Giá trị của P là tổng điểm thưởng của thuật toán này, trong sự mong đợi trong phân
bố kết quả.
Như giá trị của P là khó để mô tả một cách chính xác, chúng ta chỉ xét thấy gần
đúng cho phiên bản không theo ngữ cảnh. Chúng tôi sử dụng một phương pháp gọi
là xấp xỉ tuyến tính, với tất cả các điểm thưởng và tiêu hao được xác định và thời
gian là liên tục. Hãy r (P, µ) và ci (P, µ) được dự kiến sẽ thưởng cho mỗi vòng và dự
kiến mỗi vòng tiêu thụ tài nguyên i cho π chính sách ~ P, sẽ được kết quả dự kiến µ.
Sau đó xấp xỉ tuyến tính tương ứng với các giải pháp của một chương trình tuyến
tính đơn giản:
Maximise
Subject to
t ≥ 0.

t .r (P, µ )
t. ci (P, µ ) ≤ B

với t є R
với mỗi i

Tiểu kết: Đối với chương này chúng tôi chỉ tập trung nêu các vấn đề liên quan tới
cơ sở lý luận. Thông tin về các hệ thống trực tuyến hiện nay mà người dùng đang
được sử dụng hiện nay và được các cá nhân và tổ chức quan tâm khai thác và cũng
là vấn đề mà tôi đang nghiên cứu. Cung cấp thêm thông tin về các vấn đề liên quan

đang được nghiên cứu. Bài toán Multi-arm Bandits có những vấn đề liên quan tới
hay các vấn đề liên quan tới bài toán Bandits theo ngữ cảnh. Từ đó chúng ta sẽ có
cái nhìn toàn cảnh hơn về các cơ sở lý luận đang được nghiên cứu đến trong đề tài.


14

CHƯƠNG 2- THỰC TRẠNG NGHIÊN CỨU
Một số thuật toán trong bài toán Bandits theo ngữ cảnh:
Bảng 2.1: Mô tả một số thuật toán liên quan tới bài toán Bandits theo ngữ cảnh

(Nguồn: [8])
1. Đưa về bài toán K- Armed Bandits
1.1.

Giới thiệu

Giả sử, chúng ta liệt kê tất cả các ngữ cảnh của một quá trình thực nghiện. Sau
đó, để đơn giản là chúng ta áp dụng một thuật toán Multi- armed bandits chuẩn ứng
với mỗi ngữ cảnh đó. Tuy nhiên chúng ta có thể sẽ làm mất đi mối liên hệ giữa các
ngữ cảnh với nhau khi chúng ta xử lý chúng một cách độc lập. Giả sử có N ngữ
cảnh trong tập ngữ cảnh X, và ngữ cảnh tại thời điểm t là xt∈ {1, 2, ..., N}. Cũng
giả sử có K arm trong tập ngữ cảnh A và arm được lựa chọn tại thời điểm t là tại ∈
{1, 2, ..., K}. Xác định các thiết lập chính sách π = {f: X → A}, sau đó regret được
định nghĩa là:
⎡T
⎤
RT = sup f ∈F Ε ⎢ ∑ (rt , f ( xt ) − rt ,at ) ⎥
⎣ t =1
⎦


1.2.
l

(2.1)

Một số định lý
Định lý 1.1: theo thuật toán EXP3, một thuật toán non-contextual Multi-armed
bandits với từng ngữ cảnh, thì có regret là:
RT ≤ 2.63

TNK ln K

(2.2)


15

Với phương pháp này, ngữ cảnh chúng ta giả định là ngữ cảnh có thể được liệt
kê, mà không phải là trường hợp khi các ngữ cảnh chúng ta đưa ra là liên tục. Ngoài
ra thuật toán này sử dụng với từng ngữ cảnh một cách độc lập.

2. Thuật toán EXP4
2.1.

Giới thiệu thuật toán

Thuật toán EXP4 giải quyết vấn đề của bài toán Bandits theo ngữ cảnh là xây
dựng dưới dạng các mô hình với chuyên gia tư vấn. Ý tưởng cơ bản là có một tập N
các chuyên gia, và tại mỗi thời điểm t từng chuyên gia đưa ra lời khuyên về những

arm để lựa chọn. Thông qua các lời khuyên từ các chuyên gia đó, người học có
chiến lược riêng của mình để chọn một arm dựa trên những lời khuyên nó được.
Khi nhận được các điểm thưởng từ các arm đó, người học có thể điều chỉnh chiến
lược của mình chẳng hạn như thay đổi trọng lượng từ thông tin của từng chuyên gia.
Giả định, tồn tại một tập N các chuyên gia được đưa ra. Mỗi một chuyên gia tạo
ra một vector tư vấn dựa trên xt ngữ cảnh hiện tại thời điểm t. Vector tư vấn được
phân phối trên các arm, và được mô tả bằng ξ1t, ξ2t, …, ξktє[0,1]k. ξit,jvới các chuyên
gia thứ i đưa ra đề nghị cho một arm j tại thời điểm t. công việc của thuật toán này
là thực hiện một quyết định chọn một arm dựa trên các vector lời khuyên. Với rtє
[0,1]k là vector kết quả đúng tại thời điểm t, sau đó là kết quả mong đợi của các
chuyên gia thứ i làξit .rt. Thuật toán sẽ lựa chọn ra các chuyên gia tốt nhất, giúp đạt
được kết quả là tốt nhất.
T

Gmax = maxi ∑ ξ i t .rt (2.3)
t =1

Hay có thể định nghĩa của regret:
T

T

RT = maxi ∑ ξ t .rt - E ∑ rat
t =1

i

(2.4)

t =1


Sự kỳ vọng của thuật toán đó là việc lựa chọn ngẫu nhiên của các arm hay việc lựa
chọn ngẫu nhiên các biến khác của thuật toán. Lưu ý rằng là chúng ta sẽ có bất kỳ
giả định nào về sự phân bố kết quả, do vậy kết quả có thể là không như chúng ta
mong muốn.


16
Với các thiết lập trên, thuật toán đơn giản chỉ là với mỗi chuyên gia thì phù hợp
với mỗi arm. Thuật toán này sẽ cho chúng ta có regret là O( TN ln N ) và thuật toán
này chỉ tốt khi chúng ta có số lượng nhỏ các chuyên gia và số lượng lớn các arm.
Tuy nhiên, nếu chung ta có số lượng lớn các chuyên gia thì các chặn kết quả của
thuật toán này khá yếu.

2.2.

Thuật toán

l Giải thuật:
Yêu cầu: γ є [0,1]
Set wi,t = 1 for i = 1, …, N
for t = 1, 2, …, T do
nhận các vector chuyên gia tư vấn {ξ1t, …, ξkt}, mỗi vector là phân phối của
các arm.
for j = 1, …, K do

Pt,j= (1- γ)

1
W

N t,iξ t,j

∑
N

∑

i=1

wt,i

+

y
K

(2.5)

i=1

end for
Các hành động at theo pt, nhận kết quả rat
for j = 1, …, k do
r’t,j =

rt , j
pt , j

(j = at)(2.6)


end for
for i = 1, ..., N do
y’t,i = ξ1t. r’t
wt+1,i = wt exp(γ.y’t,i/ K)
end for
end for

(2.7)