Multi-Armed Bandits: Từ Greedy đến UCB rồi đến Exp3

Trò chơi với thông tin hạn chế

Hãy tưởng tượng bạn đang đứng trước một hàng gồm $K$ máy đánh bạc. Mỗi máy có một cơ chế trả thưởng riêng biệt mà bạn không hề biết trước. Đây là điểm khác biệt với bài toán học có giám sát (supervised learning - dữ liệu được đánh nhãn trước) vì dữ liệu chỉ được sinh ra sau khi thực hiện hành động.

Bài toán này còn gọi là Bài toán Multi-Armed Bandit (MAB) mô phỏng tình huống một thực thể (agent) đứng trước $K$ lựa chọn khác nhau (thường gọi là các "cánh tay" - arms).

Tại mỗi thời điểm $t = 1, 2, \dots, T$:

1. Hành động: Agent chọn một cánh tay $i \in \{1, \dots, K\}$.

2. Phần thưởng: Agent nhận được một giá trị thưởng $X_{t,i}$. Phần thưởng này là một biến ngẫu nhiên hoặc một giá trị cố định nhưng chưa biết trước.

3. Thông tin: Agent chỉ quan sát được phần thưởng của cánh tay mình đã chọn. Thông tin về các cánh tay còn lại hoàn toàn bị che khuất (đây được gọi là bandit feedback).

Mục tiêu: Tìm ra một chiến lược chọn cánh tay qua từng bước sao cho tổng phần thưởng tích lũy $\sum_{t=1}^T X_{t,i}$ là lớn nhất.

Không thể dùng phương pháp tối ưu truyền thống

Trong tối ưu hóa truyền thống (như Gradient Descent), ta thường có quyền truy cập vào hàm mục tiêu hoặc ít nhất là đạo hàm của nó trên toàn bộ không gian tham số. Tuy nhiên, MAB đối mặt với hai rào cản khiến các phương pháp này không thể áp dụng trực tiếp:

• Dữ liệu khuyết thiếu (Partial Observability): Bạn không biết "chuyện gì sẽ xảy ra nếu mình chọn khác đi". Nếu bạn chọn phương án A và nhận kết quả tốt, bạn không thể biết liệu phương án B có mang lại kết quả tốt hơn hay không.

• Bản chất động (Non-stationarity): Trong các kịch bản thực tế (như đấu giá quảng cáo), phân phối phần thưởng của các cánh tay có thể thay đổi theo thời gian hoặc bị thao túng bởi các tác nhân bên ngoài. Các thuật toán tối ưu tĩnh sẽ nhanh chóng bị lỗi thời.

Các vấn đề về mặt chiến lược - Exploitation vs. Exploration

Mọi chiến lược giải quyết MAB đều phải xử lý sự đánh đổi (trade-off) giữa hai trạng thái:

• Khai thác (Exploitation): Chọn cánh tay đang có hiệu suất cao nhất dựa trên dữ liệu quá khứ. Mục đích là tận dụng tối đa những gì đã biết để thu lợi nhuận ngay lập tức.

• Khám phá (Exploration): Chọn những cánh tay mà ta chưa có nhiều thông tin hoặc đang có hiệu suất thấp hơn. Mục đích là thu thập dữ liệu để cải thiện độ chính xác của các ước lượng trong tương lai, tránh việc bỏ sót "máy tốt nhất" thật sự.

Nếu chỉ Khai thác, ta dễ rơi vào tối ưu cục bộ. Nếu chỉ Khám phá, ta lãng phí quá nhiều chi phí cho các lựa chọn tồi.

Đánh giá thuật toán

Đối với bài toán Bandit, chúng ta không đánh giá thuật toán dựa trên tổng thưởng một cách đơn thuần, mà dựa trên khái niệm Regret (Sự hối tiếc).

Giả sử có một chiến lược tối ưu gọi là Oracle – thực thể biết trước mọi thông tin và luôn chọn cánh tay tốt nhất tại mọi thời điểm. Regret tại thời điểm $T$ được định nghĩa là chênh lệch giữa tổng thưởng của Oracle và tổng thưởng thực tế mà thuật toán của ta thu được:

Trong đó:

• $X_{t,i}$ là giá trị phần thưởng tại thời điểm $t$ khi chọn cánh tay $i$

• $\sum_{t=1}^T X_{t,i}$: Đây là tổng phần thưởng nếu bạn chỉ chọn duy nhất cánh tay $i$ từ đầu đến cuối (từ $t=1$ đến $T$).

• $\max_i \mathbb{E} [\dots]$: Giả sử có một "vị thần" biết trước mọi phân phối phần thưởng. Vị thần này sẽ chọn ra cánh tay $i^*$ tốt nhất ngay từ lượt đầu tiên và giữ nó mãi mãi.

• $A_t$ là cánh tay mà thuật toán chọn tại thời điểm $t$. Lưu ý rằng $A_t$ thay đổi theo thời gian dựa trên những gì thuật toán đã học được.

• $X_{t, A_t}$: Phần thưởng thực tế bạn nhận được tại bước $t$ từ cánh tay đã chọn.

Mục tiêu của một thuật toán tốt là làm cho tốc độ tăng trưởng của $R_T$ chậm hơn so với thời gian (sublinear regret, ví dụ $O(\sqrt{T})$ hoặc $O(\log T)$). Điều này đồng nghĩa với việc theo thời gian, thuật toán sẽ học được cách hành xử tiệm cận với Oracle.

Cách tiếp cận bản năng nhất: $\epsilon$-Greedy

Trước khi đến với các thuật toán phức tạp, hãy bắt đầu với chiến thuật rất tự nhiên và đơn giản.

Ý tưởng chủ đạo

Chiến thuật này chia việc ra quyết định thành hai chế độ rạch ròi dựa trên một tham số $\epsilon \in [0, 1]$ (thường chọn rất nhỏ, ví dụ $0.1$):

1. Khai thác (Exploitation) với xác suất $1 - \epsilon$: Bạn chọn cánh tay đang có phần thưởng trung bình cao nhất tính đến thời điểm hiện tại. Đây là lựa chọn "an toàn" dựa trên kinh nghiệm.

2. Khám phá (Exploration) với xác suất $\epsilon$: Bạn tung một đồng xu ảo. Nếu vào mặt "khám phá", bạn bỏ qua mọi kinh nghiệm và chọn ngẫu nhiên một trong số $K$ cánh tay.

Thuật toán và Quy trình

Tại mỗi bước $t$:

• Phát sinh một số ngẫu nhiên $r \in [0, 1]$.

• Nếu $r > \epsilon$:

  $$I_t = \arg \max_{i} \hat{\mu}_{i,t}$$

  (Chọn máy tốt nhất đã biết).

• Nếu $r \leq \epsilon$:

  $$I_t = \text{random}(1, \dots, K)$$

  (Thử đại một máy bất kỳ).

Ưu điểm

• Dễ cài đặt: Chỉ cần vài dòng code và một biến lưu trữ giá trị trung bình mẫu.

• Đảm bảo tính hội tụ: Vì luôn dành ra một tỉ lệ $\epsilon$ để thử nghiệm, về mặt lý thuyết, khi $t \to \infty$, agent sẽ thử mọi cánh tay vô số lần và cuối cùng sẽ tìm ra cánh tay tốt nhất.

Nhược điểm

Dù hiệu quả, $\epsilon$-Greedy bộc lộ hai vấn đề lớn khiến nó không tối ưu:

1. Khám phá mù quáng: Khi ở chế độ khám phá, nó chọn ngẫu nhiên hoàn toàn. Nó có thể chọn một cánh tay mà dữ liệu đã chứng minh là "rất tệ" với xác suất ngang bằng với một cánh tay "đầy triển vọng". Nó không biết tận dụng thông tin về độ bất định.

2. Sự hối tiếc (Regret) tuyến tính: Vì $\epsilon$ thường là hằng số, ngay cả khi bạn đã chơi 1 tỷ lần và biết chắc chắn máy nào là tốt nhất, bạn vẫn lãng phí $\epsilon$ thời gian để đi thử những máy tồi. Điều này khiến tổng hối tiếc $R_T$ tăng trưởng theo hàm tuyến tính $O(T)$, thay vì các hàm thấp hơn như $O(\log T)$.

Upper Confidence Bound (UCB): Chiến lược lạc quan trong sự bất định

Nếu các phương pháp như Greedy hay $\epsilon$-Greedy chỉ dựa vào giá trị trung bình đơn thuần, thì UCB tiến thêm một bước bằng cách tích hợp độ tin cậy của dữ liệu vào quá trình ra quyết định.

Ý tưởng chủ đạo

Mục tiêu của UCB là giải quyết bài toán Exploration-Exploitation bằng triết lý: "Optimism in the Face of Uncertainty" (Lạc quan trước sự bất định).

• Ý tưởng: Thay vì chỉ đánh giá một cánh tay qua những gì nó "đã thể hiện" (trung bình mẫu), chúng ta hãy đánh giá nó qua những gì nó "có khả năng đạt được" (tiềm năng tối đa).

• Chiến lược: Nếu một cánh tay chưa được chơi nhiều, chúng ta có ít thông tin về nó, dẫn đến sự bất định cao. UCB sẽ "ưu tiên" sự bất định này, giả định rằng trong kịch bản tốt nhất, cánh tay đó có thể mang lại phần thưởng lớn.

Khoảng tin cậy (Confidence Interval)

Khi ta thử một cánh tay $i$ được $n_i$ lần và thu được giá trị trung bình là $\hat{\mu}_i$, giá trị này thực chất chỉ là một ước lượng. Giá trị kỳ vọng thực sự $\mu_i$ (thứ mà ta tìm kiếm) nằm đâu đó xung quanh $\hat{\mu}_i$.

Khoảng tin cậy là một khoảng $[\hat{\mu}_i - \Delta_i, \hat{\mu}_i + \Delta_i]$ mà ta tin rằng $\mu_i$ sẽ nằm trong đó với một xác suất rất cao.

• $\hat{\mu}_i - \Delta_i$: Giới hạn dưới (Lower Bound).

• $\hat{\mu}_i + \Delta_i$: Giới hạn trên (Upper Bound).

Để định lượng "độ rộng" $\Delta_i$ của khoảng tin cậy, UCB sử dụng Bất đẳng thức Hoeffding. Bất đẳng thức này phát biểu rằng với các biến ngẫu nhiên $X_1, \dots, X_n$ độc lập trong khoảng $[0, 1]$, sai lệch giữa trung bình mẫu $\hat{\mu}$ và kỳ vọng thực $\mu$ được giới hạn bởi:

Trong bài toán Bandit, chúng ta chỉ quan tâm đến việc giá trị thực không vượt quá giá trị ước lượng cộng thêm một khoảng sai số. Đặt xác suất sai lầm là $p = e^{-2n\epsilon^2}$, giải phương trình theo $\epsilon$, ta tìm được biên độ sai số:

Để thuật toán tự động giảm xác suất sai lầm khi thời gian $t$ tăng lên, người ta thường chọn $p = \displaystyle \frac 1 {t^4}$ (hoặc một hàm giảm theo $t$). Từ đó, ta có giới hạn trên của khoảng tin cậy (Upper Confidence Bound).

Thuật toán UCB (Upper Confidence Bound)

Thuật toán UCB hoạt động dựa trên nguyên lý "Lạc quan khi đối mặt với sự bất định". Thay vì chỉ nhìn vào tỉ lệ thưởng trung bình, UCB tính toán một "giá trị tiềm năng" cho mỗi cánh tay và luôn chọn cánh tay có tiềm năng cao nhất.

Tại mỗi bước $t$, đối với mỗi cánh tay $i$, chúng ta tính toán một giá trị gọi là $UCB_{i,t}$:

Sau đó, thuật toán sẽ thực hiện hành động bằng cách chọn cánh tay có giá trị $UCB$ lớn nhất:

Trong đó:

• $UCB_{i,t}$: Là giá trị đại diện cho "mức trần" kỳ vọng của cánh tay $i$.

• $I_t$: Là chỉ số (index) của cánh tay được Agent chọn để kéo ở vòng $t$.

• $\hat{\mu}_{i,t}$: Tỉ lệ thưởng trung bình hiện tại của máy $i$.

• $n_{i,t}$: Số lần máy $i$ đã được chọn tính đến thời điểm $t$.

• $C$: Hệ số điều chỉnh độ lạc quan (Exploration Parameter).

  • Khi $C$ nhỏ ( $\sqrt{2}$): Thuật toán trở nên "thực dụng". Nó tin vào lịch sử hơn và ít tò mò hơn. Trong môi trường biến động (Adversarial), $C$ nhỏ khiến UCB dễ bị "ngoan cố", bám lấy một máy đã từng tốt nhưng nay đã bị đổi thưởng.

  • Khi $C$ lớn ( $\ge \sqrt{2}$): Thuật toán trở nên "phiêu lưu". Nó sẵn sàng bỏ qua máy đang tốt để đi kiểm tra lại các máy khác, giúp giảm rủi ro bị môi trường đánh lừa nhưng lại tốn nhiều "học phí" hơn để khám phá.

Trong các bài báo khoa học về UCB1 - thuật toán cụ thể và nổi tiếng nhất trong họ UCB - ta thường thấy công thức gộp gọn lại thành:

Thực tế, đây chính là trường hợp cụ thể khi ta đặt $C = \sqrt{2}$. Con số $2$ nằm trong căn chính là kết quả của việc gán $C^2 = 2$.

Cơ chế vận hành

Thuật toán UCB tạo ra một cơ chế tự điều chỉnh:

• Ban đầu, nó sẽ thử tất cả các cánh tay một lần để có dữ liệu khởi đầu ($n_i = 1$).

• Sau đó, nó ưu tiên những máy đang thắng ( $\hat{\mu}$ lớn).

• Tuy nhiên, nếu một máy cứ thua mãi hoặc không được chọn, cái "căn thức" (Exploration Bonus) của nó sẽ to dần lên theo $\ln t$.

• Đến một ngưỡng nhất định, giá trị UCB của máy "kém" đó sẽ vượt qua máy đang thắng, buộc Agent phải quay lại kiểm tra máy đó.

Ưu điểm lớn nhất của UCB là nó có Regret Bound ở mức $O(\log T)$, nghĩa là sự hối tiếc tăng trưởng rất chậm. Tuy nhiên, toàn bộ logic này dựa trên giả định rằng các phần thưởng là độc lập và cùng phân phối (i.i.d). Nếu môi trường là đối kháng (Adversarial), nơi phần thưởng bị thay đổi một cách có mục đích để "lừa" khoảng tin cậy, UCB sẽ hoàn toàn mất phương hướng.

Thuật toán Exp3 (Exponential-weight algorithm for Exploration and Exploitation)

Exp3 được thiết kế cho kịch bản Adversarial – nơi phần thưởng của các cánh tay có thể biến động bất kỳ hoặc bị điều chỉnh bởi một tác nhân đối kháng nhằm "đánh lừa" các ước lượng thống kê. Thay vì dựa vào khoảng tin cậy như UCB, Exp3 sử dụng phương pháp cập nhật trọng số nhân (Multiplicative Weights Update).

Các tham số và Ký hiệu

Để bắt đầu, chúng ta cần định nghĩa các thành phần cốt lõi:

• $K$: Số lượng cánh tay (lựa chọn).

• $w_t = (w_{t,1}, w_{t,2}, \dots, w_{t,K})$: vector trọng số để lưu trữ tín hiệu tích lũy của từng cánh tay

• $w_{t,i}$: Trọng số của cánh tay $i$ tại thời điểm $t$. Đây là giá trị lưu trữ tích lũy.

• $\eta$ (Learning Rate): Tốc độ học. Tham số này cực kỳ quan trọng; nếu $\eta$ quá lớn, thuật toán bị nhiễu; nếu $\eta$ quá nhỏ, thuật toán học rất chậm.

• $\gamma$ (Exploration factor): Mức độ khám phá.

Quy trình cập nhật và Luật chơi cụ thể

Thuật toán vận hành theo một vòng lặp kín qua từng bước $t = 1, 2, \dots, T$:

• Bước 1: Tính xác suất chọn ($P_{t,i}$)

Từ vector trọng số $w_t$, ta tính xác suất để chọn mỗi cánh tay. Công thức này kết hợp giữa việc khai thác trọng số đã có và một lượng nhỏ khám phá đồng đều:

• Bước 2: Chọn hành động và quan sát

Agent chọn một cánh tay $A_t$ dựa trên phân phối $P_t$ và nhận về phần thưởng $X_t \in [0, 1]$.

• Bước 3: Ước lượng phần thưởng không chệch ($\hat{X}_{t,i}$)

Thách thức lớn nhất trong Bandit là chúng ta không quan sát được phần thưởng của các cánh tay không được chọn. Để giải quyết vấn đề này mà vẫn đảm bảo tính chính xác cho tổng điểm tích lũy $\hat{S}$, Exp3 sử dụng kỹ thuật Importance Sampling.

Sau khi chọn cánh tay $A_t$ và nhận phần thưởng $X_t$, giá trị ước lượng $\hat{X}_{t,i}$ cho mọi cánh tay $i$ được tính như sau:

Cơ chế vận hành của công thức:

• Với các cánh tay không được chọn ($i \neq A_t$): $\hat{X}_{t,i} = 0$.

• Với cánh tay được chọn ($i = A_t$): Phần thưởng thực tế $X_t$ được chia cho xác suất chọn nó $P_{t,i}$.

Phép chia cho $P_{ti}$ đảm bảo $\hat{X}_{ti}$ là một ước lượng không chệch (unbiased estimator) của phần thưởng thực tế $X_{t,i}$. Cụ thể:

Điều này cho phép thuật toán cập nhật trọng số cho các cánh tay một cách công bằng, ngay cả khi dữ liệu quan sát được là không đầy đủ.

• Bước 4: Cập nhật trọng số $w$ cho bước kế tiếp

Đây là bước mấu chốt của thuật toán. Trọng số được cập nhật theo hàm mũ dựa trên giá trị ước lượng vừa tính:

• Nếu $i$ không được chọn: $\hat{X}_{t,i} = 0 \implies w_{t+1,i} = w_{t,i} \cdot e^0 = w_{t,i}$ (Trọng số giữ nguyên).

• Nếu $i$ được chọn: Trọng số sẽ tăng trưởng theo hàm mũ dựa trên phần thưởng đã được hiệu chỉnh.

Phân tích thuật toán

• Vai trò của Learning Rate ($\eta$): $\eta$ đóng vai trò điều phối sự nhạy cảm của thuật toán. Trong các chứng minh về Regret Bound, giá trị tối ưu của $\eta$ thường được đặt là $\sqrt{\frac{2 \ln K}{TK}}$. Nếu biết trước tổng số lượt chơi $T$, ta có thể thiết lập $\eta$ để đạt được mức hối tiếc tối ưu $O(\sqrt{TK \ln K})$.

• Cơ chế hàm mũ (Multiplicative Weights): Việc dùng $w_{t+1} = w_t \cdot \exp(\dots)$ tương đương với việc cộng dồn các phần thưởng ước lượng ở số mũ:

  $$w_{t+1,i} = \exp \left( \frac{\eta \sum_{s=1}^t \hat{X}_{s,i}}{K} \right)$$

  Điều này giúp biến tổng phần thưởng (thứ có thể rất lớn) thành một phân phối xác suất nằm trong khoảng $[0, 1]$ một cách mượt mà và nhạy bén với những thay đổi nhỏ.

Ý tưởng cốt lõi của Exp3

Có thể gói gọn trong cơ chế cập nhật trọng số nhân dựa trên ước lượng không chệch.

Đầu tiên, thuật toán giải quyết triệt để rào cản dữ liệu bị khuyết thiếu bằng cách xây dựng các giá trị phần thưởng ảo $\hat{X}_{t,i}$ thông qua kỹ thuật Importance-Weighted Estimator. Bằng cách chia phần thưởng thực tế cho xác suất được chọn ($P_{t,i}$), Exp3 tạo ra một ước lượng không chệch (unbiased), giúp "bù đắp" và phóng đại giá trị cho những lựa chọn ít được ưu tiên nhưng tiềm năng, từ đó đảm bảo bức tranh toàn cảnh về phần thưởng luôn chính xác về mặt kỳ vọng toán học.

Điểm chủ đạo thứ hai nằm ở việc sử dụng hàm mũ (Exponential Update) để cập nhật vector trọng số $w$ theo từng bước. Khác với các phương pháp cộng tuyến tính, hàm mũ cho phép thuật toán khuếch đại cực mạnh sự khác biệt giữa các lựa chọn; chỉ cần một cánh tay mang lại hiệu quả tốt hơn một chút, trọng số của nó sẽ tăng trưởng phi mã, giúp hệ thống có khả năng xoay trục chiến thuật (pivot) cực nhanh để thích nghi ngay cả khi môi trường đối kháng thay đổi liên tục.

Demo

Demo này giúp trực quan hóa hiệu suất của ba chiến thuật: $\epsilon$-Greedy, UCB, và Exp3 thông qua chỉ số Regret (Sự hối tiếc tích lũy). Regret càng thấp, thuật toán càng hiệu quả. Tích chọn "Chế độ Đối kháng Động" để kích hoạt kịch bản có sự can thiệp thay đổi của Adversary: khi hệ thống nhận ra có một chiến thuật phát hiện ra máy có tỷ lệ thắng cao, nó sẽ swap tỷ lệ máy này với máy có tỷ lệ thấp nhất.