Trong bài viết này mình giới thiệu về bài toán Multi-armed bandit, về sự đánh đổi trong quá trình thăm dò và khai thác (exploration–exploitation trade-offs) của thuật toán để thông qua đó giảm thiếu chi phí thăm dò và tăng hiệu quả khai thác được. Bài viết này mình chỉ tập trung nói về phương pháp tiếp cận/giải thuật, mình sẽ demo bằng code R và Python trong một bài viết khác.

Giới thiệu

Bài toán Multi-armed bandit (*) là một bài toán giả định, trong đó người chơi phải đối mặt với một dãy K máy đánh bạc. Mỗi máy sẽ có một xác suất nhất định để trả về phần thưởng. Xác suất này là khác nhau ứng với mỗi máy và xác suất này cũng là một biến không biết trước (unknown) đối với người chơi. Mục tiêu tối thượng của người chơi  chính là giảm thiểu thua lỗ hoặc tối ưu hóa lợi ích có được trong quá trình chơi. Đây là một trong những bài toán điển hình khi nhắc tới reinforcement learning.

TBrown_slots_38.0

Ứng dụng

Các giải thuật của bài toàn này có thể được đưa vào áp dụng trong các trường hợp sau:

  • Internet display advertising: Nếu phòng marketing của công ty bạn có nhiều banners khác nhau cho một chiến dịch quảng cáo nhưng lại không biết banner nào sẽ khiến khách hàng click vào nhiều hơn. Thay vì phải chạy A/B testing, bạn có thể sử dụng thuật toán để hệ thống tự học và chọn ra banner nào được người dùng yêu thích hơn.
  • Dynamic pricing: Chọn ra mức giá tối ưu nhất về mặt lợi nhuận (profit) hoặc doanh số (revenue).
  • Recommendation system: Gợi ý sản phẩm nào người dùng ưa thích nhất.
  • Finance: Chọn ra cổ phiếu có mức sinh lời nhiều nhất.
  • Clinical trials: Chọn ra phương pháp chữa trị tốt nhất, hay gây ra ít thiệt hại nhất.

Giải thích bài toán

Trong bài toán Multi-armed bandit, một trong yếu tố quan trọng cần được nhắc tới chính là sự đánh đổi trong quá trình thăm dò và khai thác (exploration–exploitation trade-offs). Để giữ cho mọi thứ đơn giản, hãy hình dung là bạn đang có 5 khu đất có dầu, nhưng bạn không biết được rằng khu đất nào có nhiều dầu nhất và đào ở vị trí nào thì sẽ lấy được dầu. Nếu mỗi mũi khoan thử bạn tốn $5000 và để cho đảm bảo thì bạn phải khoan 10 lần ở các vị trí khác nhau. Vậy có thể nói rằng bạn tốn $5000 * 10 * 5 = $250,000 cho mục đích thăm dò (exploration), trước khi có thể bắt đầu khai thác (exploitation).

Nếu bạn bỏ thời gian ra để nhìn vào bài toán trên bạn có thể sẽ nảy sinh rất nhiều câu hỏi, vd như:

  1. Nếu tôi chỉ có $100,000 thì phải làm như thế nào?
  2. 10 mũi khoan mỗi khu đất liệu có đủ? Liệu 5 hay 20 mũi khoan sẽ phù hợp hơn?
  3. Khu đất mà tôi chọn liệu có thật sự tối ưu?

Là một nhà tư bản thông minh, có thể bạn sẽ chọn khoan thăm dò mỗi khu đất 4 lần, rồi cứ thế bơm dầu từ khu đất cho kết quả tốt nhất. Sau đó khi đã có một tiền thu lại từ bán dầu bạn sẽ dùng nó để khoan thêm để hòng tìm ra được khu đất tối ưu để bạn tập trung khai thác. Nói theo một cách khác, bạn đang cố gắng cân đối giữa 2 tiến trình thăm dò (exploration) và khai thác (exploitation). Mục tiêu của bạn sẽ là làm sao tối ưu giữa chi phí thăm dò và lợi nhuận có được từ khai thác.

Thử map bài toàn trên với những bài toán khác trong thực tế như đầu tư tài chính, hay recommendation system, bạn cũng sẽ thấy mình đứng trước cùng một vấn đề. Bạn cần phải nhanh chóng biết được đâu là sản phẩm nên giới thiệu cho khách hàng tiềm năng, hay cổ phiếu nào có khả năng kiếm được lợi nhuận nhiều nhất với chi phí thăm dò thấp nhất có thể. Điều khác biệt chính là giá cổ phiếu hay sản phẩm yêu thích có thể bị thay đổi tuỳ ở mỗi khung thời gian khác nhau. Đây cũng chính là điều khiến cho các thuật toán reinforcement learning trở nên hữu ích.

Giải thuật

Hãy quay trở lại với bàn toán gốc và cùng tìm hiểu các thuật toán mà chúng ta có thể đưa vào sử dụng.

A Naive Algorithm:

Vì bạn, với tư cách người chơi, không biết được khả năng sinh lời của từng máy đánh bạc (expected value), nên cách tiếp cận đơn giản nhất chính là cố gắng tìm ra nó trong những lần thử đầu tiên.

Bước 1: kéo/chơi thử mỗi máy 100 lần, sau đó lấy trung bình phần thưởng thu được của 100 lần thử, chúng ta sẽ biết được phần thưởng trung bình (mean reward) của từng máy.

Bước 2: Chọn máy có hiệu suất sinh lời cao nhất để kéo cho tới khi hết trò chơi.

Đây là một thuật toán đơn giản, dễ hiểu tuy nhiên nó có một số điểm yếu như sau:

  1. Bạn nên thử bao nhiêu là đủ? ở hướng dẫn trên thì mình chọn 100 nhưng liệu 10-50-200 sẽ là một con số phù hợp hơn? Tùy thuộc vào bài toán cụ thể và người thực hiện mà số lần thử sẽ khác nhau. Không có một quy tắc nhất định để chọn số lần thử tối ưu.
  2. Giả sử như trong 100, hay 1000, lần thử đầu tiên bạn vẫn không tìm được kết quả tối ưu? hay kết quả bạn thu được không chính xác do phần thưởng được phân phối không đều theo thời gian? Bạn có thể kết thúc bằng việc chọn sai máy cho đến hết trò chơi.
  3. Trong bài toán Multi-armed bandit chúng ta không đề cập đến việc máy đánh bạc có thể thay đổi xác suất sinh ra giải thưởng theo thời gian. Tuy nhiên trong thực tế điều này hoàn toàn có thể thay đổi. Vd: Sở thích của người tiêu dùng thay đổi dẫn tới họ thích một phong cách thiết kế này nhiều hơn phong cách thiết kế khác vốn trước đó thịnh hành hơn; Hay do nhu cầu thay đổi dẫn tới việc mức giá này được ưu thích hơn so với mức giá khác.

ϵ− Greedy Algorithm

Naive Algorithm yêu cầu 1 khoảng thời gian thăm dò (exploration), thử mỗi máy 100 lần, trước khi bắt đầu khai thác (exploitation). Vậy nếu bạn muốn tranh thủ khai thác càng sớm càng tốt nhưng vẫn thỉnh thoảng thăm dò thì sao? Thuật toán Greedy cho phép bạn làm được điều này theo cách như sau:

Với xác xuất 1- ϵ Kéo/chơi máy có phần thưởng trung bình (mean reward) cao nhất ở thời điểm hiện tại (Nếu không có máy nào thỏa điều này thì có thể chọn máy ngẫu nhiên.)

Thuật toán này có 2 ưu điểm lớn:

  • Nếu số lần thử của bạn đủ lớn, bạn sẽ chọn được máy cho ra phần thưởng tốt nhất.
  • Trong hầu hết các lần khai thác của bạn,  bạn sẽ khai thác trên máy sinh ra phần thưởng lớn nhất.

Nhưng khuyết điểm của thuật toán này là bạn không thể biết được ϵ tối ưu nhất cho bài toán của bạn. Nếu ϵ của bạn quá lớn, nghĩa là bạn chọn số lần thử dành cho mục đích khai thác quá nhiều, nhưng nếu số ϵ của bạn quá nhỏ, bạn sẽ có khả năng đang khai thác không hiệu quả.

UCB – Upper Confidence Bound Algorithm

Thuật toán UCB tận dụng lý thuyết xác suất thống kê vào trong giải thuật của mình. Để có thể giải thích nó một cách tương đối đơn giản hãy lấy trường hơp tung xí ngầu làm ví dụ. Chúng ta đều biết giá trị trung bình (mean value) của việc tung xí ngầu là 3.5, tuy nhiên giả định là bạn không biết con số này. Vậy nếu bạn tung xí ngầu lần đầu tiên và bạn nhận được giá trị là 2, bạn không thể làm gì hơn là đoán đại giá trị trung bình của việc tung xí ngầu là 2, trong đó cận dưới 95 percentile là 1.4 và cận trên 95 percentile là 5.2 . Bằng cách tung cục xí ngầu nhiều lần bạn sẽ dần dần tìm ra giá trị trung bình thực tế cũng như thu hẹp khoảng tự tin (Confidence Bound).

Bằng cách chọn chơi trên máy có giá trị cận trên khoảng tự tin (Upper Confidence Bound) cao nhất thuật toán UCB có thể dần dần đi gần hơn tới giá trị trung bình thực tế của từng máy, đồng thời thu hẹp khoảng tự tin lại (Confidence Bound). Vì mình không muốn đi sâu vào thuật toán nên bạn có thể xem clip bên dưới để hiểu hơn về cách hoạt động của thuật toán.

Video giới thiệu về cách hoạt động của UCB

Ưu điểm của UCB so với Greedy Algorithm

Bạn có thể nhận ra rằng đối với Greedy Algorithm, số ϵ là con số cố định. Bạn gần như không thể chọn con số ϵ tối ưu ở thời điểm ban đầu, và số ϵ cũng không thể tự động thay đổi để tăng tỉ lệ khai thác (exploitation) so với thăm dò (exploration). Trái lại trong trường hợp của UCB, thuật toán này cho phép tăng tần suất khai thác sau một khoảng thời gian nhất định, nhưng đồng thời vẫn đảm bảo là không ngừng quá trình thăm dò.

Thompson sampling 

Thuật toán Thompson đi theo chiều hướng Bayesian thay vì Frequentist. Cụ thể hơn phương pháp Thompson sử dụng Beta distribution để sinh ra một xác suất ngẫu nhiên, nhưng vẫn năm trong vùng cho phép, để dự đoán máy nào có thể sẽ trả về phần thưởng trong lần kéo tiếp theo. Xác suất này được dựa trên kết quả của những lần kéo máy trước đó.

Do mình không thể giải thích thuật toán này chỉ trong vài dòng nên mình sẽ không giải thích thêm cách nó hoạt động cũng như cách kết quả được sinh ra. Thay vào đó mình chỉ nói tới lợi ích của Thompson với UCB khi đưa vào ứng dụng thực tế. Nếu bạn nào muốn tìm hiểu thêm về thuật toán có thể google key words: Beta distribution và Bernoulli distribution.

Lợi ích của Thompson với UCB khi đưa vào ứng dụng thực tế

Trong ứng dụng thực tế, 1 trong những vấn đề bạn gặp là gần như không có hệ thống nào có đủ khả năng tính toán (computing power) thể sinh ra kết quả trong real time (trừ khi bạn có quá ít dữ liệu). Vì vậy cái bạn có thể đạt được chỉ là tiệm cận ở mức real time, và mức tiệm cận này trong hầu hết mọi trường hợp vẫn rất lớn. Cũng chính vì điều này mà Thompson có lợi hơn so với UCB. Giả định là t và t + 1 là thời điểm hệ thống tổng hợp dữ liệu và phân tích kết quả. Đồng nghĩa với việc là trong khoảng thời gian giữa 2 thời điểm này kết quả bạn có trong tay chỉ là kết quả tổng hợp được ở thời điểm t. Đối với UCB, điều này cũng có nghĩa rằng bạn sẽ chết cứng với 1 lựa chọn duy nhất. Trái lại, Thompson sinh ra 1 xác suất ngẫu nhiên trong khoảng cho phép, và vì vậy bạn có thể có nhiều hơn 1 lựa chọn.

=> Bạn có thể thấy cách giải thích của mình hơi khó hiểu ở thời điểm này, nhưng khi bắt đầu chạm tay vào thuật toán, bạn có thể quay lại bất cứ lúc nào để hiểu rõ hơn.

Kết thúc

Như đã nói ở trên, mình kết thúc bài viết này ở đây. Trong phần 2 mình sẽ tập trung vào việc demo với R và Python. Đồng thời cũng sẽ hướng dẫn bạn cách visualize kết quả sinh ra của từng thuật toán.

Good luck! May the best algorithm win!

(*) Multi-armed bandit: Nếu bạn nào có đọc Lucky Luck thì chắc biết tập “Tướng cướp một tay” (one-armed bandit). Trong trường hợp này cũng tương tự, multi-armed bandit là để ám chỉ một máy đánh bạc có nhiều tay kéo. Note: vì tên bài toán này thú vị nên mình muốn giải thích thêm chứ tên bài toán không có ảnh hưởng tới giải thuật.

Reference:

https://en.wikipedia.org/wiki/Multi-armed_bandit

http://engineering.richrelevance.com/bandits-recommendation-systems/

http://engineering.richrelevance.com/recommendations-thompson-sampling/

https://dataorigami.net/blogs/napkin-folding/79031811-multi-armed-bandits

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s