Kẻ cướp nhiều vũ trang: Giải pháp học tăng cường tốt nhất cho nhiệm vụ của bạn

Kẻ cướp nhiều vũ trang (MAB) tạo thành nền tảng trong thế giới Học tăng cường, cung cấp một cơ chế mạnh mẽ để đàm phán các tình huống đòi hỏi sự cân bằng tối ưu giữa thăm dò và khai thác. Khám phá đề cập đến việc thử các tùy chọn mới, trong khi khai thác có nghĩa là gắn bó với tùy chọn tốt nhất hiện tại. Trong những trường hợp như vậy, MAB thường chứng tỏ là một lựa chọn tuyệt vời nhờ cơ chế học tập thông minh của chúng.

Đầu tiên, hãy làm sáng tỏ khái niệm đằng sau MAB. Hãy hình dung một con bạc bị vây quanh bởi một loạt máy đánh bạc, mỗi máy được gọi là "tên cướp một tay". Các quyết định quan trọng cần đưa ra ở đây liên quan đến việc xác định máy nào sẽ chơi, thứ tự chơi và tần suất chơi. Điều hấp dẫn là mỗi máy cung cấp một phần thưởng khác nhau, không chắc chắn. Mục tiêu cuối cùng là tích lũy phần thưởng tích lũy cao nhất qua một chuỗi các lượt chơi.

Kẻ cướp nhiều vũ trang là gì?

Cái tên "tên cướp nhiều vũ khí" xuất phát từ một thử nghiệm tưởng tượng liên quan đến một con bạc tại một dãy máy đánh bạc (thường được gọi là "tên cướp một tay"). Con bạc cần quyết định chơi máy nào, chơi bao nhiêu lần mỗi máy và theo thứ tự nào, với mục tiêu tối đa hóa tổng phần thưởng của chúng.

Trong một định nghĩa chính thức hơn, một vấn đề MAB là một bộ (A, R)

Mục tiêu trong bài toán MAB là tìm ra chính sách π (ánh xạ từ dữ liệu lịch sử đến hành động) giúp tối đa hóa tổng phần thưởng dự kiến Q qua một số vòng nhất định.

Vấn đề nan giải chính trong MAB là sự đánh đổi giữa "thăm dò" và "khai thác":

1. Khám phá liên quan đến việc thử các nhánh khác nhau để tìm hiểu thêm về phần thưởng mà chúng có thể mang lại. Điều này có thể liên quan đến việc kéo các nhánh phụ tối ưu, nhưng nó giúp thu thập thông tin về hệ thống.
2. Khai thác liên quan đến việc kéo cánh tay mà đại lý hiện đang tin là có phần thưởng kỳ vọng cao nhất, dựa trên thông tin mà họ đã thu thập được cho đến nay.

Cân bằng giữa khám phá và khai thác là một thách thức cốt lõi trong các vấn đề về học tăng cường và MAB.

Để giải quyết vấn đề này, một loạt các thuật toán đã được phát triển, bao gồm các chiến lược Epsilon-Greedy, Upper Confidence Bound (UCB) và Thompson Sampling.

Bài đánh giá chi tiết về Contextual Bandits như một phần mở rộng của MAB sẽ được đề cập trong các bài viết tiếp theo.

Epsilon(ε)-Tham Lam

Chiến lược Epsilon(ε)-Tham lam tuân theo một nguyên tắc đơn giản. Hầu hết thời gian, được định lượng là (1 - ε), nó chọn hành động mang lại phần thưởng ước tính cao nhất, do đó khai thác tùy chọn được biết đến nhiều nhất. Tuy nhiên, thời gian còn lại, được định lượng là ε, nó chọn một hành động ngẫu nhiên, do đó khám phá những khả năng mới. Sự khéo léo của chiến lược này nằm ở tính đơn giản và hiệu quả của nó, mặc dù có cảnh báo trước rằng nó có thể chọn các hành động ít bổ ích hơn với cùng xác suất với các hành động bổ ích nhất trong giai đoạn khám phá và giá trị của ε xác định sự cân bằng giữa khám phá và khai thác.

Về mặt toán học, nó có thể được định nghĩa là:

Điều này có thể được xác định bằng mã giả sau:

 Initialize Q(a) for all a Repeat: Generate a random number p between 0 and 1 If p < epsilon: Select a random action a Else: Select action a with the highest Q(a) Execute action a and observe reward r Update Q(a) = Q(a) + alpha * (r - Q(a))

Việc triển khai Pythonic của chiến lược Epsilon-Greedy khá đơn giản:

 import numpy as np class EpsilonGreedy: def __init__(self, epsilon, counts, values): self.epsilon = epsilon self.counts = counts self.values = values def select_arm(self): if np.random.random() < self.epsilon: return np.random.choice(len(self.values)) else: return np.argmax(self.values) def update(self, chosen_arm, reward): self.counts[chosen_arm] += 1 n = self.counts[chosen_arm] value = self.values[chosen_arm] new_value = ((n-1) / float(n)) * value + (1 / float(n)) * reward self.values[chosen_arm] = new_value

Thuật toán ε-tham lam có ưu điểm là tính đơn giản và đảm bảo rằng nó sẽ tiếp tục khám phá (một chút) ngay cả sau nhiều bước. Tuy nhiên, nó không tính đến mức độ được biết về mỗi hành động khi nó khám phá, không giống như UCB hoặc Thompson Sampling.

UCB

Ngược lại, chiến lược UCB tính đến cả phần thưởng ước tính và sự không chắc chắn hoặc phương sai liên quan khi quyết định một hành động. Nó thể hiện sự ưa thích đối với các hành động có tính không chắc chắn cao, tìm cách giảm thiểu nó và đảm bảo giai đoạn khám phá hiệu quả hơn. Chiến lược UCB được định nghĩa toán học như sau:

Việc triển khai Python của nó như sau:

 class UCB: def __init__(self, counts, values): self.counts = counts self.values = values def select_arm(self): n_arms = len(self.counts) for arm in range(n_arms): if self.counts[arm] == 0: return arm ucb_values = [0.0 for arm in range(n_arms)] total_counts = sum(self.counts) for arm in range(n_arms): bonus = sqrt((2 * log(total_counts)) / float(self.counts[arm])) ucb_values[arm] = self.values[arm] + bonus return np.argmax(ucb_values) def update(self, chosen_arm, reward): self.counts[chosen_arm] += 1 n = self.counts[chosen_arm] value = self.values[chosen_arm] new_value = ((n-1) / float(n)) * value + (1 / float(n)) * reward self.values[chosen_arm] = new_value

Sự cân bằng giữa thăm dò và khai thác trong UCB xuất phát từ công thức của nó: giá trị ước tính của một hành động cộng với số hạng giảm dần theo thời gian (khi bạn tìm hiểu thêm về hành động đó) nhưng tăng lên cùng với sự không chắc chắn về hành động đó. Do đó, thuật toán có xu hướng khám phá các nhánh có độ không chắc chắn cao và phần thưởng tiềm năng cao.

Lấy mẫu Thompson

Lấy mẫu Thompson là một thuật toán lấy cảm hứng từ Bayesian cho vấn đề kẻ cướp nhiều nhánh. Nó chỉ định một phân phối trước cho xác suất phần thưởng của từng tên cướp (hoặc từng hành động), sau đó cập nhật các ưu tiên này khi phần thưởng được quan sát. Việc lựa chọn hành động là xác suất, theo phân phối sau trên hành động tốt nhất.

Trong khung Beta-Bernoulli, chúng tôi coi phân phối phần thưởng của mỗi tên cướp là phân phối Bernoulli (nghĩa là phần thưởng nhị phân 0 hoặc 1). Sau đó, chúng tôi chỉ định Beta trước xác suất nhận được phần thưởng. Bản phân phối Beta là liên hợp trước bản phân phối Bernoulli, cho phép cập nhật sau dễ dàng.

Hợp lý:

1. Gán cho mỗi tên cướp một bản phân phối Beta với các tham số α=1, β=1 (Đồng nhất trước).

2. Đối với mỗi vòng:

   1. Lấy mẫu một số ngẫu nhiên từ bản phân phối Beta hiện tại của mỗi tên cướp.
   2. Chọn tên cướp có số lượng mẫu cao nhất và kéo tên cướp đó.
   3. Quan sát phần thưởng từ tên cướp bị kéo. Nếu thành công (1), hãy tăng α của tên cướp lên một; nếu thất bại (0), hãy tăng β của tên cướp lên một.
   4. Lặp lại bước 2 và 3.

 import numpy as np from scipy.stats import beta class Bandit: def __init__(self, true_probability): self.true_probability = true_probability self.alpha = 1 self.beta = 1 def pull(self): return np.random.random() < self.true_probability def sample(self): return np.random.beta(self.alpha, self.beta) def update(self, reward): self.alpha += reward self.beta += (1 - reward) def Thompson(bandits, num_trials): rewards = np.zeros(num_trials) for i in range(num_trials): # Thompson sampling j = np.argmax([b.sample() for b in bandits]) # Pull the arm for the bandit with the largest sample reward = bandits[j].pull() # Update rewards log rewards[i] = reward # Update the distribution for the bandit whose arm we just pulled bandits[j].update(reward) return rewards # Suppose we have 3 bandits with these true probabilities true_probabilities = [0.2, 0.5, 0.75] bandits = [Bandit(p) for p in true_probabilities] # Run experiment rewards = Thompson(bandits, num_trials=10000) # Print the total reward print("Total reward earned:", rewards.sum()) print("Overall win rate:", rewards.sum() / len(rewards))

Do đó, Thompson Sampling "khám phá" các hành động mà nó không chắc chắn (những hành động mà phân phối giá trị được trải ra) và "khai thác" các hành động mà nó tin rằng có thể có giá trị cao (những hành động mà phân phối bị lệch về giá trị cao).

Theo thời gian, khi mỗi hành động được tìm hiểu nhiều hơn, các phân phối trở nên cực đại hơn và các hành động được chọn bởi thuật toán có xu hướng hội tụ về một hành động có giá trị kỳ vọng cao nhất.

Cân bằng thăm dò/khai thác trong Thompson Sampling xuất phát tự nhiên từ hình dạng của các bản phân phối. Phương pháp này khá hiệu quả, nhưng có thể phức tạp hơn để triển khai so với UCB hoặc ε-greedy, đặc biệt đối với các vấn đề có không gian hành động lớn hoặc liên tục hoặc cấu trúc phần thưởng phức tạp.

Tại sao Kẻ cướp nhiều vũ trang là RL tốt nhất cho nhiệm vụ của bạn?

1. Tính đơn giản : Các thuật toán MAB đơn giản hơn và hiệu quả hơn về mặt tính toán so với các thuật toán RL chính thức, yêu cầu duy trì và cập nhật một bảng giá trị hành động trạng thái hoặc giá trị gần đúng có khả năng lớn.
2. Cân bằng giữa khám phá và khai thác : Thuật toán MAB cung cấp các phương pháp mạnh mẽ để quản lý sự đánh đổi giữa việc thử các hành động mới và gắn bó với các hành động tốt đã biết.
3. Khả năng thích ứng thời gian thực : Các thuật toán MAB có thể thích ứng trong thời gian thực với những thay đổi trong phân phối phần thưởng của các hành động.
4. Tích hợp dễ dàng : Tính đơn giản và hiệu quả của MAB cho phép tích hợp dễ dàng vào các hệ thống hiện có, mang lại lợi ích tức thì với sự gián đoạn tối thiểu.
5. Khả năng ứng dụng rộng rãi : MAB đã được áp dụng thành công trong nhiều lĩnh vực khác nhau, bao gồm quảng cáo (chọn quảng cáo nào sẽ hiển thị để tối đa hóa tỷ lệ nhấp), chăm sóc sức khỏe (chiến lược điều trị cá nhân hóa) và tối ưu hóa trang web (thử nghiệm A/B).

Ứng dụng của MAB

Kẻ cướp đa vũ trang (MAB) có nhiều ứng dụng trong các ngành và lĩnh vực khác nhau. Dưới đây là một số ví dụ về cách chúng có thể được sử dụng:

1. Quảng cáo trực tuyến : MAB có thể được sử dụng để tự động điều chỉnh lựa chọn quảng cáo để hiển thị cho người dùng dựa trên tương tác của họ. Điều này giúp tối đa hóa tỷ lệ nhấp hoặc chuyển đổi theo thời gian.
2. Thử nghiệm lâm sàng : Trong nghiên cứu y học, thuật toán MAB có thể được sử dụng để tự động chỉ định bệnh nhân cho các phương pháp điều trị khác nhau. Điều này đảm bảo rằng nhiều bệnh nhân nhận được các phương pháp điều trị hiệu quả nhất, do đó làm giảm sự hối tiếc, tức là tổn thất phát sinh do không phải lúc nào cũng chọn được phương pháp điều trị tốt nhất.
3. Khuyến nghị về Bài báo Tin tức : Các trang web tin tức có thể sử dụng MAB để cá nhân hóa các bài báo được hiển thị cho mỗi người dùng. Thuật toán MAB có thể tìm hiểu theo thời gian loại bài viết mà mỗi người dùng quan tâm và điều chỉnh các đề xuất cho phù hợp.
4. Định giá động : Nền tảng thương mại điện tử hoặc hãng hàng không có thể sử dụng thuật toán MAB để tối ưu hóa chiến lược định giá của họ trong thời gian thực, tối đa hóa doanh thu dựa trên hành vi của khách hàng và động lực thị trường.
5. Định tuyến mạng : Trong mạng máy tính, các thuật toán MAB có thể được sử dụng để quản lý tắc nghẽn và tối ưu hóa việc định tuyến các gói tin. Mỗi tuyến có thể được coi là một nhánh và thuật toán có thể tự động chọn các tuyến để giảm thiểu độ trễ hoặc mất gói.
6. Điều chỉnh siêu tham số học máy : MAB cũng có thể được sử dụng để tối ưu hóa việc lựa chọn siêu tham số trong các mô hình học máy. Mỗi bộ siêu tham số có thể được coi là một nhánh và thuật toán có thể lặp lại việc tinh chỉnh lựa chọn để tìm ra cấu hình mô hình tối ưu.

Về bản chất, tiện ích của MAB vượt xa các nhiệm vụ học tập tăng cường thông thường. Chúng tượng trưng cho một khuôn khổ hiệu quả để tăng cường quá trình ra quyết định trong môi trường không chắc chắn, cung cấp các giải pháp thiết thực cho các vấn đề trong thế giới thực trên nhiều lĩnh vực khác nhau. Do đó, khi nhiệm vụ hiện tại liên quan đến việc cân bằng thăm dò và khai thác, MAB thường nổi lên như một lựa chọn phù hợp, cung cấp giải pháp linh hoạt, mạnh mẽ và thích ứng cho các câu hỏi hóc búa khi ra quyết định.

Phần kết luận

Kẻ cướp đa vũ trang, với khả năng cân bằng giữa thăm dò và khai thác một cách hiệu quả, cung cấp giải pháp mạnh mẽ cho nhiều vấn đề ra quyết định trong thế giới thực. Khả năng thích ứng và tính linh hoạt vốn có của chúng khiến chúng trở thành một công cụ có giá trị, không chỉ trong lĩnh vực học tăng cường mà còn trên nhiều ứng dụng, từ chăm sóc sức khỏe đến quảng cáo trực tuyến. Cho dù bạn là nhà khoa học dữ liệu, người đam mê học máy hay chuyên gia đang tìm cách nâng cao quy trình ra quyết định của mình, việc hiểu và triển khai các chiến lược MAB có thể là một trải nghiệm phong phú và bổ ích.