Arms, Pulls, Rewards
Một Hàng Máy Đánh Bạc
Hãy tưởng tượng K máy đánh bạc xếp hàng. Mỗi máy trả phần thưởng trung bình khác nhau, nhưng bạn không biết bất kỳ trung bình nào. Mỗi bước bạn chọn một máy, kéo cần của nó, & quan sát khoản thanh toán. Mục tiêu của bạn: tối đa hóa tổng phần thưởng qua nhiều lần kéo.
Cấu hình đó định nghĩa một vấn đề multi-armed bandit. K = số lượng arms. Một pull chọn một arm. Reward đến từ phân phối ẩn của arm đó. mean_reward(k) của arm k theo dõi trung bình chạy qua các lần kéo của k.
Khám phá vs Khai thác
Hai áp lực kéo nhau:
Khai thác kéo cần có phần thưởng trung bình quan sát cao nhất. Tham lam. Rủi ro: một cần trông tuyệt vời sau 2 lần kéo có thể trở về mức trung bình thực thấp hơn.
Khám phá kéo một cần ít được thử nghiệm hơn để giảm sự không chắc chắn. Rủi ro: thời gian dành cho khám phá làm mất phần thưởng bạn có thể thu được từ một cần tốt đã biết.
Một chính sách tốt kết hợp cả hai. Khai thác thuần túy sẽ khóa chặt những người thắng cuộc ban đầu mãi mãi. Khám phá thuần túy không bao giờ thu được phần thưởng.
Các "Cánh tay" của ANDREA = Nguồn Dữ liệu
ANDREA coi việc huấn luyện như một bài toán bandit. Mỗi nguồn dữ liệu (hermes3-general, gutenberg, dictionary, synthetic-chat, smoltalk, v.v.) đóng vai trò là một cánh tay. Mỗi bước huấn luyện kéo một cánh tay: tải một tài liệu từ nguồn đó, chạy forward pass, quan sát mức giảm loss. Phần thưởng trung bình cho mỗi nguồn theo dõi mức độ nguồn đó cải thiện loss trung bình.
Tại sao điều này phù hợp: mô hình thay đổi nhu cầu trong quá trình huấn luyện. Các bước đầu hưởng lợi từ tiếp xúc rộng (nhiều nguồn). Các bước sau hưởng lợi từ đánh bóng nhắm mục tiêu (một vài nguồn có phần thưởng cao). Bandit thích ứng; tỷ lệ lấy mẫu cố định thì không thể.
Đặt Tên Cho Các Thành Phần
Điểm UCB1
Auer, Cesa-Bianchi & Fischer, 2002
Peter Auer và các cộng sự công bố UCB1 vào năm 2002 như một chính sách bandit hữu hạn với giới hạn regret O(log N). UCB1 chọn cánh tay bằng cách kết hợp phần thưởng trung bình hiện tại của nó với một bonus khám phá thu hẹp dần khi cánh tay được kéo.
Công thức
UCB(k) = mean_reward(k) + C * sqrt(ln(N) / n_k)
Từng thành phần:
- mean_reward(k): phần thưởng trung bình quan sát được cho cần k qua n_k lần kéo. Thành phần khai thác.
- N: tổng số lần kéo trên tất cả các cần cho đến nay. Tăng lên mỗi bước.
- n_k: số lần kéo của cần k cụ thể. Chỉ tăng khi k được chọn.
- C: hằng số khám phá. Giá trị tiêu chuẩn trong sách giáo khoa: 1.4 (sqrt(2)). ANDREA sử dụng C=0.5.
- sqrt(ln(N) / n_k): bán kính tin cậy. Một cần ít được kéo có n_k nhỏ & nhận thưởng lớn; một cần được kéo nhiều có n_k lớn & nhận thưởng nhỏ.
Tại sao Công thức Hoạt động
ln(N) tăng chậm (logarit), vì vậy tử số tăng nhẹ theo tổng kinh nghiệm. n_k ở mẫu số làm thu nhỏ thành phần khi bằng chứng tích lũy cho một cần cụ thể. Căn bậc hai làm dịu phản ứng, ngăn một cần ít được khám phá thống trị mãi mãi.
Chọn theo argmax_k UCB(k) ở mỗi bước tự động cân bằng cả hai áp lực. Không cần tham số epsilon, không cần lịch trình, không cần nhiệt độ. Toán học sẽ xử lý.
Tính điểm UCB
Tại sao C=0.5 thay vì 1.4
Giá trị trong Sách giáo khoa
Auer, Cesa-Bianchi & Fischer suy ra một giới hạn regret giả sử phần thưởng nằm trong [0, 1]. Giới hạn này đúng với C = sqrt(2) khoảng 1.414. Hầu hết các sách giáo khoa dạy C=1.4 là giá trị mặc định an toàn.
Mức độ Phần thưởng của ANDREA
ANDREA báo cáo cải thiện loss từng bước dưới dạng phần thưởng. Các cải thiện thô khoảng 0.001 (loss giảm từ 4.521 xuống 4.520). Sau hệ số mở rộng 1000x (được đề cập trong hoạt động 78, phân bổ phần thưởng), phần thưởng đã mở rộng có độ lớn gần 1.0. Phần thưởng trung bình qua lịch sử của một arm nằm trong khoảng 0.5 đến 3.0.
Bây giờ hãy xem xét bonus khám phá với C=1.4, N=10000, n_k=100:
1.4 sqrt(ln(10000) / 100) = 1.4 sqrt(9.21 / 100) = 1.4 * 0.303 = 0.425
0.425 nằm trong dải phần thưởng. Có thể chấp nhận được. Bây giờ n_k=10 (một cánh tay hiếm):
1.4 sqrt(9.21 / 10) = 1.4 0.960 = 1.344
1.344 nằm TRÊN hầu hết các mean_rewards quan sát được. Khám phá thống trị: cánh tay hiếm thắng bất kể mean thực tế của nó. Với nhiều nguồn & các lần huấn luyện dài, điều này làm ngập lịch trình bằng các cánh tay có mean thấp.
Giải pháp: C=0.5
0.5 sqrt(9.21 / 10) = 0.5 0.960 = 0.480
0.480 nằm dưới hầu hết các giá trị trung bình phần thưởng. Khám phá vẫn xảy ra (các cánh tay hiếm vẫn nhận được phần thưởng), nhưng mean_reward dẫn dắt. ANDREA khai thác nhiều hơn, khám phá ít hơn, & tránh sự thống trị của khám phá.
Điều chỉnh như Kỹ thuật, Không phải Lý thuyết
Giới hạn trong sách giáo khoa giả định phần thưởng trong [0, 1]. Phần thưởng của ANDREA nằm trong khoảng xấp xỉ [0, 5]. Việc mở rộng hằng số phù hợp hằng số với độ lớn phần thưởng. Thuật toán giống nhau, môi trường được hiệu chỉnh.
Chẩn đoán Thống trị Khám phá
Phần Tiếp Theo
Những Gì Bạn Có
UCB1 chọn cánh tay có upper confidence bound cao nhất. Bound kết hợp mean_reward (khai thác) với sqrt(ln(N) / n_k) được nhân với C (khám phá). ANDREA điều chỉnh C=0.5 vì phần thưởng mỗi bước nằm trong khoảng 0.5 đến 3.0, & giá trị 1.4 trong sách giáo khoa làm lịch trình tràn ngập các cánh tay có mean thấp.
Những Gì Còn Lại
Vanilla UCB1 chọn một cánh tay mỗi lần. ANDREA chọn một số cánh tay tập trung mỗi giai đoạn, trộn các cánh tay ngẫu nhiên trước, & giữ mỗi giai đoạn từ 7 đến 42 bước. Cấu trúc đó (hoạt động 77: các giai đoạn xúc xắc) ngăn UCB cam kết quá mức vào các người thắng sớm trong khi vẫn cho phép nó tập trung nỗ lực.
Phân bổ phần thưởng (hoạt động 78) cho thấy mean_reward(k) thực sự đến từ đâu. Các mức sàn & hình phạt epoch (hoạt động 79) thêm các quy tắc bảo vệ lên trên đầu ra của UCB.
Tài liệu Tham khảo
- Auer, Cesa-Bianchi, Fischer (2002). "Finite-time Analysis of the Multiarmed Bandit Problem." Machine Learning, 47, 235-256.
- ANDREA whitepaper, các phần 3.1 & 3.4.