Trí Tuệ Nhân Tạo Trong Lĩnh Vực May Rủi

KỲ 1: ĐA THỦ ĐẠO TẶC

“Cờ bạc là bác thằng bần”

Câu này thì chắc các huynh đệ đều biết cả, các cụ từ xưa đã nhắc “cờ bạc, rượu chè, trai gái, hút xách, tứ đổ tường”, trong đó cờ bạc đứng đầu bốn cái nguy hại ấy. Thế còn phương Tây thì sao, tất nhiên là ở bển cũng có món này, cơ mà bên đó lại hợp pháp hóa ba trò “may rủi” và phát triển nó lên thành một ngành công nghiệp nên lần lượt mấy lá bài Tây dần đánh bật bài tứ sắc khỏi chiếu bạc. Về sau các môn các phái trong giới “giang hồ” khoa học cũng bắt đầu nghiên cứu bí kíp để khám phá ngành công nghiệp này.

Học Tăng Cường - Reinforcement Learning

Trong đó Thống kê xác suất môn, Lý thuyết trò chơi đạo đã nắm giữ ngôi vị Thái Sơn, Bắc Đẩu võ lâm một thời gian dài nhưng giờ đây học máy giáo mà cụ thể hơn là phái học tăng cường nguyên văn tiếng Anh là Reinforcement Learning mà các huynh đệ tỉ muội hay gọi tắt là Rờ Lờ (RL) dần trở thành một thế lực đáng gờm trong lĩnh vực này.

Môn phái này dần khám phá ra nguyên tăc một số trò, ví dụ như mấy cái máy hình dưới:

Cho quý huynh đệ chưa rõ thì gọi nôm na đây là trò “gạt cần”, trả một khoản phí, nắm cần gạt xuống, ra được ba hình giống nhau là thắng; mỗi máy sẽ có xác suất thắng khác nhau trong hàng chục hàng trăm máy ở quán. Câu hỏi là làm sao để xác định xác suất thắng của các máy này ? Phái Rờ Lờ đặt tên cho bài toán này là multi-armed bandits (MAB), dịch sang tiếng ta tạm gọi là “đa thủ đạo tặc”.

Ý tưởng ở đây là sau khi chơi với số lần đủ nhiều ta sẽ ước tính được việc chọn chơi máy nào thì có được xác suất thắng cao hơn.

Bước vào quán ta chấm 10 máy để chơi, nếu các ông thích chơi nhiều hơn thì tùy, qua tầm 10 lượt chơi tùy ý với xác suất được chọn của mỗi máy là như nhau, ta xác định được máy có kết quả tốt nhất trong 10 máy. Câu hỏi là ở các lượt chơi tiếp theo ta chỉ chơi máy đó, được gọi là quá trình khai thác (exploitation) hay tiếp tục chia đều cơ hội được chơi cho tất cả các  máy, được gọi là quá trình khám phá (exploration), đây cũng chính là vấn đề cốt lõi của bài toán này: Khai thác hay khám phá?

Khai thác hay khám phá - Exploitation or Exploration?

Thật may là các bậc cao nhân phương Tây đã tạo ra nhiều bí kíp để giải quyết vấn đề này như: thuật toán Naive, -Greedy, Softmax,….

Trong đó công pháp nhập môn là Naive và -Greedy. Thuật toán Naive, tại hạ mạn phép gọi là Nhất Máy Chỉ theo tiếng ta, cứ theo máy đã thắng nhiều nhất tới cùng, chơi tham một cách ngây thơ. Còn chiêu Epsilon-Greedy thì khác chút, chiêu này dịch tạm là Tham Hữu Ngưỡng, tham lam với một ngưỡng xác định. Thế thì sẽ tham như nào, tức là ta vẫn ưu tiên chọn máy có kết quả tốt nhất trong cả quá trình chơi nhưng vẫn cho các máy khác một cơ hội để được chọn, cho ta cơ hội được khám phá.

Thông thường, ta sẽ chọn một số trong khoảng [0, 1],số này chính là cái ngưỡng của sự tham lam, là số quyết định xác suất của khai thác và khám phá; ta sẽ khai thác, chơi máy có kết quả tốt nhất với xác suất và khám phá, chơi một máy ngẫu nhiên với xác suất.

Khi chơi, ta chọn ngẫu nhiên một con số cũng trong khoảng [0, 1] nếu số lớn hơn, có ()*100% cơ hội xảy ra, thì tiếp tục chơi máy tốt nhất ngược lại thì ta thử ở một máy bất kỳ. Ví dụ chọn thì ta sẽ có 90% khả năng chọn được số lớn hơn 0.1 và đi khai thác, ngược lại 10% xác suất chọn được số nhỏ hơn 0.1 và khám phá một máy ngẫu nhiên.

Như vậy xác suất được chọn của máy có kết quả tốt nhất luôn cao vượt trội, xác suất được chọn là : 1- ε + ε⁄k

Trong đó k là tổng số máy, xác suất được chọn của các máy còn lại chỉ là ε⁄k .

Ví dụ cụ thể hơn, giả sử bạn có 6 khu mỏ vàng, mỗi ngày chỉ đủ nguồn lực để khai thác một mỏ, bạn chưa biết mỏ nào sẽ có nhiều vàng nhất. Những ngày đầu ta cần thăm dò lần lượt các mỏ này và khi có kết quả sơ bộ ta sẽ dùng công pháp ở trên và một cục súc sắc để tiếp tục khai thác. Lần này chọn ε = 1/6, nếu ra mặt 1 thì khám phá, ngược lại thì khai thác mỏ tốt nhất hiện tại, quy ước mỗi mặt xúc xắc cho một mỏ tương ứng.

Dễ thấy, xác suất để một mỏ không phải tốt nhất được khám phá chỉ là: 1/36 ≈ 2.8% còn xác suất mỏ tốt nhất được tiếp tục khai thác lên tới: 5/6 + 1/36 = 31/36 ≈ 86%

Tạm kết

Hai bí kíp nhập môn rõ ràng ưu ái rất nhiều máy có kết quả tốt nhất, thế còn máy tốt nhì, tốt ba thì sao, biết đâu được chơi nhiều hơn tốt nhì lại thành tốt nhất thì sao. Rất tiếc công pháp cho đệ tử nhập môn không quan tâm vấn đề này.

Liệu công pháp cấp độ cao hơn thì sao, tại sao lại đánh giá môn phái có khả năng vấn đỉnh minh chủ võ lâm. Liệu có bí kíp nào giúp ta đạt chiến thắng với xác suất cao không ?

Xin hẹn các vị hạ hồi phân giải.

Tài liệu tham khảo:

1. Volodymyr Kuleshov, Doina Precup (2000). Algorithms for the multi-armed bandit problem, 6.
2. Wikipedia Multi-armed bandit: https://en.wikipedia.org/wiki/Multi-armed_bandit
3. The epsilon-Greedy Algorithm: https://learning.oreilly.com/library/view/bandit-algorithms-for/9781449341565/ch03.html