Vấn đề Khóa chặt
Một Bandit Luôn Thắng
Vanilla UCB1 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 quá trình huấn luyện dài với nhiều nguồn, một cánh tay đơn lẻ có thể thu thập một chuỗi phần thưởng cao, đẩy trung bình của nó lên, & trở nên gần như không thể đánh bại. Các cánh tay khác đình trệ ở n_k thấp với trung bình cũ kỹ. Khóa chặt.
Khóa chặt làm tổn thương ANDREA theo hai cách:
1. Sụp đổ đa dạng. Một mô hình huấn luyện 90% các bước trên một nguồn sẽ học các đặc trưng phong cách của nguồn đó. Các mẫu sinh ra sẽ lệch về các mẫu lặp lại phù hợp với nguồn chiếm ưu thế.
2. Khám phá lỗi thời. Các cánh tay với giá trị trung bình lỗi thời không thể phục hồi. Một cánh tay có giá trị trung bình giảm sớm sẽ bị kẹt ở mức đó ngay cả khi mô hình giờ đây đã có đủ khả năng để trích xuất phần thưởng từ nó.
Một Giai Đoạn Mua Thời Gian
Giải pháp: giữ một tập hợp cố định các cánh tay tập trung cho một giai đoạn (nhiều bước) trước khi đánh giá lại. Một giai đoạn 14 bước nghĩa là 14 lần lan truyền thuận đánh vào cùng các cánh tay tập trung. Phần thưởng trung bình ổn định. Nhiễu ngẫu nhiên được trung bình hóa. Sau đó bandit lăn lại.
Độ Dài Giai Đoạn Biến Đổi
ANDREA chọn độ dài pha ngẫu nhiên từ {7, 14, 21, 28, 42} bước tại mỗi ranh giới pha. Năm giá trị, ngẫu nhiên đều. Các pha ngắn (7) phản ứng nhanh với các lựa chọn xấu; các pha dài (42) cho phép các tập focus ổn định khai thác đầy đủ. Giới hạn trên hạn chế thiệt hại: tối đa 42 bước dành cho một cấu hình focus xấu trước khi buộc phải re-roll.
Thống kê Độ dài Pha
1d3 (2-mắt) & 1d4 (3-mắt)
Ký Hiệu Xúc Xắc
Ký hiệu tabletop: NdM nghĩa là tung N xúc xắc với M mặt mỗi cái. 1d3 tung một xúc xắc 3 mặt, trả về giá trị trong {1, 2, 3}. 1d4 tung một xúc xắc 4 mặt, trả về {1, 2, 3, 4}. ANDREA cũng cho phép kết quả 0 theo quy ước: tung ra 0 nghĩa là giai đoạn hoàn toàn ngẫu nhiên (không có tay UCB tập trung).
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ể: {0, 1, 2, 3}. Kết quả 0 được dành riêng cho giai đoạn ngẫu nhiên.
Cấu hình 3-mắt (1d4). Số lượng cánh tay tập trung có thể: {0, 1, 2, 3, 4}. Các pool lớn hơn cho phép các giai đoạn tập trung hơn.
Ngẫu nhiên trước, UCB sau
Dù kết quả xúc xắc là gì, ANDREA cũng lấp đầy các ô tập trung qua 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 đồng đều từ tất cả các cánh tay có sẵn. Điều này buộc phải có sự đa dạng tổ hợp ở mọi giai đoạn, bất kể thứ hạng UCB. [BLOCK_TYPE SECTION/STEP] __BLOCK_N__ <translated content>
2. UCB lấp đầy các slot còn lại. Tính điểm UCB1 cho các arm chưa được chọn. Chọn các arm hàng đầu còn lại cho đến khi số slot focus được lấp đầy.
Việc chọn ngẫu nhiên trước rất quan trọng. Nếu UCB chọn trước, arm dẫn đầu streak sẽ luôn chiếm một slot. Với random-first, ngay cả arm UCB tốt nhất cũng có thể bị loại khỏi một phase. Sự đa dạng được đảm bảo.
Các Phase Hoàn Toàn Ngẫu Nhiên
Khi xúc xắc ra 0, toàn bộ focus set được lấy từ các lựa chọn ngẫu nhiên. UCB không đóng góp gì. Khoảng 25% các phase (1d4) hoặc 33% các phase (1d3) rơi vào đây. Các phase hoàn toàn ngẫu nhiên buộc bandit phải làm mới mẫu của các arm ít được kéo, giữ cho ước lượng mean_reward trung thực trên toàn bộ pool arm.
Xác Suất Kết Quả Xúc Xắc
Giới Hạn Thiệt Hại
Một Giai Đoạn Xấu Có Thể Tốn Tối Đa 42 Bước
Giả sử xếp hạng UCB chọn một cánh tay tập trung có giá trị trung bình thực tế thấp hơn nhiều so với giá trị trung bình quan sát được. Giai đoạn khóa chặt cánh tay đó. Phần thưởng giữ ở mức thấp suốt giai đoạn. Bao lâu thì bandit mới có thể sửa chữa?
Độ dài pha tối đa: 42 bước. Sau 42 bước, pha kết thúc, xúc xắc được tung lại, focus arms được xáo trộn lại. Lựa chọn xấu không thể kéo dài hơn 42 lần forward pass.
Tại sao 42 (Và Không Phải 100, & Không Phải 1000)
Các pha dài giúp ước lượng mean_reward ổn định. Lý thuyết thống kê: phương sai của trung bình n mẫu giảm theo 1/n. Từ 7 mẫu đến 42 mẫu cho 6x mẫu nhiều hơn, sqrt(6) khoảng 2.45x sai số chuẩn chặt hơn. Sau 42 mẫu, mean_reward nằm trong khoảng xấp xỉ +/-15% giá trị thực (tùy thuộc vào phương sai phần thưởng).
Sau 42 mẫu, lợi ích giảm dần: 100 mẫu so với 42 mẫu = 2.4x nhiều hơn, sqrt(2.4) khoảng 1.55x sai số chuẩn chặt hơn. Lợi ích biên giảm khi chi phí của việc khóa vào lựa chọn xấu tăng lên. 42 bước cân bằng hai yếu tố này.
Đa dạng vs Hội tụ
Các giai đoạn ngắn (7 bước): ước lượng phần thưởng vẫn nhiễu, nhưng lựa chọn xấu tốn ít. Các giai đoạn dài (42 bước): ước lượng chặt chẽ, nhưng lựa chọn xấu tốn nhiều hơn. ANDREA trộn độ dài giai đoạn đều đặn để cả hai chế độ đều xuất hiện trong mọi lần huấn luyện.
Chi Phí Tái Xây Dựng Btok
Mỗi ranh giới giai đoạn kích hoạt việc tái xây dựng file btok cho các cánh tay tập trung. Tái xây dựng btok chạy trong luồng nền; CUDA hot-reload khi mtime thay đổi. Việc tái xây dựng mất vài giây; các giai đoạn phải chạy đủ dài để chi phí tái xây dựng vẫn nhỏ. 42 bước ở tốc độ huấn luyện ANDREA-120M thoải mái vượt quá thời gian tái xây dựng.
Suy Luận Về Giới Hạn
Sắp Tới
Những Gì Bạn Có
Kiểm soát xúc xắc dựa trên pha bao bọc UCB1 trong ba quy tắc bảo vệ: độ dài pha biến đổi (7-42), arms ngẫu nhiên trước, pha ngẫu nhiên do xúc xắc điều khiển (25-33% ngẫu nhiên thuần túy). Giới hạn 42 bước kìm hãm thiệt hại; các pha ngẫu nhiên ngăn chặn khóa chặt; độ dài biến đổi trộn tốc độ phản ứng với độ ổn định ướ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 (phân bổ phần thưởng) cho thấy cách CUDA báo cáo mất mát theo nguồn mỗi bước, cách EMA theo nguồn theo dõi phần thưởng, & tại sao ANDREA mở rộng phần thưởng thô lên 1000x trước khi cung cấp cho UCB1.
Các tầng sàn & hình phạt epoch (hoạt động 79) thêm các quy tắc bảo vệ bổ sung lên trên đầu ra của bandit, đảm bảo các nguồn nhỏ không bị bỏ đói & các nguồn lớn không bị lặp lại để ghi nhớ.
Tài liệu tham khảo
Whitepaper ANDREA, phần 3.2.