Vấn đề khóa cứng
Một Bandit liên tục chiến thắng
UCB1 thuần túy tính toán lại điểm số ở mỗi bước. Chọn một cánh tay. Kéo nó. Cập nhật n_k & mean_reward(k). Lặp lại. Trong một lượt huấn luyện dài với nhiều nguồn, một cánh tay duy nhất có thể thu thập một chuỗi phần thưởng cao, đẩy giá trị trung bình của nó lên, & trở nên gần như không thể bị đánh bại. Các cánh tay khác trì trệ ở n_k thấp với các giá trị trung bình lỗi thời. Khóa cứng.
Khóa cứng gây hại cho ANDREA theo hai cách:
1. Sụp đổ sự đa dạng. Một mô hình huấn luyện 90% các bước trên một nguồn duy nhất sẽ học các đặc điểm phong cách của nguồn đó. Các mẫu sinh ra sẽ trôi dạt về phía các mẫu lặp lại, khớp với nguồn chiếm ưu thế.
2. Khám phá lỗi thời. Các nhánh (arms) có giá trị trung bình lỗi thời không thể phục hồi. Một nhánh mà giá trị trung bình của nó đã giảm từ sớm sẽ bị mắc kẹt ở giá trị đó, ngay cả khi mô hình hiện tại đã đủ năng lực để khai thác phần thưởng từ nó.
Một giai đoạn mua thêm thời gian
Giải pháp: giữ một bộ các nhánh trọng tâm cố định trong một giai đoạn (nhiều bước) trước khi đánh giá lại. Một giai đoạn gồm 14 bước có nghĩa là 14 lần truyền tiến (forward passes) nhắm vào cùng các nhánh trọng tâm đó. Phần thưởng trung bình sẽ ổn định. Nhiễu ngẫu nhiên (stochastic noise) được trung bình hóa. Sau đó, bandit sẽ quay lại (re-roll).
Độ dài giai đoạn biến đổi
ANDREA chọn ngẫu nhiên độ dài pha từ tập {7, 14, 21, 28, 42} bước tại mỗi ranh giới pha. Năm giá trị, phân phối ngẫu nhiên đều. Các pha ngắn (7) phản ứng nhanh với các lựa chọn kém; các pha dài (42) cho phép các bộ tập trung ổn định khai thác triệt để. Giới hạn trên đặt trần cho thiệt hại: tối đa 42 bước bị tiêu tốn cho một cấu hình tập trung kém trước khi bắt buộc phải rút lại.
Thống kê Độ dài Pha
1d3 (2 mắt) & 1d4 (3 mắt)
Ký hiệu Xúc Xắc
Ký hiệu trên bàn chơi: NdM có nghĩa là lăn N xúc xắc, mỗi xúc xắc có M mặt. 1d3 lăn một xúc xắc 3 mặt, trả về một giá trị trong {1, 2, 3}. 1d4 lăn một xúc xắc 4 mặt, trả về {1, 2, 3, 4}. ANDREA cũng cho phép kết quả là 0 theo quy ước: một lần lăn ra 0 có nghĩa là giai đoạn hoàn toàn ngẫu nhiên (không có cánh tay tập trung UCB).
Cấu hình 2 Mắt so với 3 Mắt
Cấu hình huấn luyện của ANDREA chọn một trong hai chế độ xúc xắc:
Cấu hình 2 mắt (1d3). Số lượng cánh tay tập trung có thể có: {0, 1, 2, 3}. Kết quả 0 được dành riêng cho pha ngẫu nhiên.
Cấu hình 3 mắt (1d4). Số lượng cánh tay tập trung có thể có: {0, 1, 2, 3, 4}. Các nhóm lớn hơn cho phép các pha tập trung hơn.
Ngẫu nhiên trước, UCB sau
Bất kể kết quả xúc xắc ra sao, ANDREA lấp đầy các ô tập trung theo hai lượt:
1. Cánh tay ngẫu nhiên trước. Chọn một phần các ô tập trung một cách ngẫu nhiên và đồng đều từ tất cả các cánh tay khả dụng. Điều này buộc sự đa dạng tổ hợp ở mỗi pha, bất kể xếp hạng UCB.
2. UCB lấp đầy các slot còn lại. Tính điểm UCB1 cho các cánh tay (arms) chưa được chọn. Chọn các cánh tay còn lại có xếp hạng cao nhất cho đến khi số lượng slot tập trung được lấp đầy.
Việc chọn ngẫu nhiên trước tiên là rất quan trọng. Nếu UCB được chọn trước, một cánh tay đang dẫn đầu chuỗi thắng (streak-leader) sẽ luôn chiếm một slot. Với cơ chế ngẫu nhiên trước tiên, ngay cả cánh tay UCB tốt nhất cũng có thể không được chọn trong một giai đoạn. Tính đa dạng vẫn được đảm bảo.
Các Giai Đoạn Ngẫu Nhiên Thuần Túy
Khi xúc xắc ra số 0, toàn bộ bộ tập trung (focus set) được tạo ra từ các lần chọn ngẫu nhiên. UCB không đóng góp gì. Khoảng 25% số giai đoạn (với 1d4) hoặc 33% số giai đoạn (với 1d3) rơi vào trường hợp này. Các giai đoạn ngẫu nhiên thuần túy buộc thuật toán bandit phải làm mới mẫu của các cánh tay có tỷ lệ chọn thấp, giữ cho các ước lượng mean_reward trung thực trên toàn bộ nhóm cánh tay.
Xác Suất Kết Quả Xúc Xắc
Giới hạn Thiệt hại
Một Pha Xấu Gây Mất Tối Đa 42 Bước
Giả sử các xếp hạng UCB chọn một cánh có giá trị trung bình thực sự thấp hơn nhiều so với giá trị trung bình quan sát được. Pha đó sẽ khóa cánh đó lại. Phần thưởng sẽ duy trì ở mức thấp trong suốt pha. Bao lâu thì bandit có thể sửa sai?
Độ dài tối đa của pha: 42 bước. Sau 42 bước, pha kết thúc, xúc xắc được gieo lại, các cánh tay tập trung được xáo trộn lại. Lựa chọn kém không thể kéo dài hơn 42 lần chuyền bóng về phía trước.
Tại sao là 42 (& Không phải 100, & Không phải 1000)
Các pha dài cho phép các ước tính của mean_reward ổn định. Lý thuyết thống kê: phương sai của trung bình của n mẫu giảm theo 1/n. Đi từ 7 mẫu lên 42 mẫu cho nhiều hơn 6 lần số mẫu, sqrt(6) xấp xỉ 2,45 lần sai số chuẩn chặt chẽ hơn. Sau 42 mẫu, mean_reward nằm trong khoảng +/-15% so với giá trị thực của nó (tùy thuộc vào phương sai của phần thưởng).
Quá 42 mẫu, lợi ích thu được giảm đi: 100 mẫu so với 42 mẫu = nhiều hơn 2,4 lần, sqrt(2,4) xấp xỉ 1,55 lần sai số chuẩn chặt chẽ hơn. Lợi ích biên giảm khi chi phí của việc khóa định vị sai tăng lên. 42 bước cân bằng cả hai yếu tố.
Đa dạng so với Hội tụ
Các pha ngắn (7 bước): các ước tính phần thưởng vẫn nhiễu, nhưng các lựa chọn sai gây ít thiệt hại. Các pha dài (42 bước): các ước tính chặt chẽ hơn, nhưng các lựa chọn sai gây thiệt hại nhiều hơn. ANDREA trộn độ dài pha một cách đồng đều để cả hai chế độ đều xuất hiện trong mỗi lượt huấn luyện.
Chi phí xây dựng lại Btok
Mỗi ranh giới pha kích hoạt việc xây dựng lại tệp btok cho các cánh tay tập trung. Việc xây dựng lại btok chạy trên một luồng nền; CUDA tự động nạp lại khi thời gian sửa đổi (mtime) thay đổi. Quá trình xây dựng lại mất vài giây; các pha phải chạy đủ dài để chi phí xây dựng lại vẫn nhỏ. 42 bước ở tốc độ huấn luyện ANDREA-120M vượt xa thời gian xây dựng lại một cách thoải mái.
Lập luận Về Trần (Ceiling)
Tiếp Theo
Những gì bạn đã có
Kiểm soát xúc xắc theo pha bao bọc UCB1 trong ba quy tắc bảo vệ: độ dài pha thay đổi (7-42), các cánh tay ngẫu nhiên trước, các pha ngẫu nhiên do xúc xắc điều khiển (25-33% hoàn toàn ngẫu nhiên). Trần 42 bước giới hạn thiệt hại; các pha ngẫu nhiên ngăn chặn sự cố định; các độ dài thay đổi kết hợp tốc độ phản ứng với tính ổn định của ước lượng.
Những gì còn lại
Tín hiệu phần thưởng cung cấp cho UCB thực sự đến từ đâu? Hoạt động 78 (gán phần thưởng) cho thấy cách CUDA báo cáo tổn thất theo từng nguồn ở mỗi bước, cách EMA theo từng nguồn theo dõi phần thưởng, & tại sao ANDREA nhân phần thưởng thô lên 1000 lần trước khi cung cấp cho UCB1.
Các quy tắc bảo vệ bổ sung từ sàn & hình phạt epoch (hoạt động 79) được áp dụng lên đầu ra của thuật toán bandit, đảm bảo các nguồn tin nhỏ không bị bỏ đói và các nguồn tin lớn không bị lặp lại đến mức thuộc lòng.
Tham khảo
Giấy trắng ANDREA, mục 3.2.