A k-armed Bandit Problem

sonnh

Hãy xem xét vấn đề học tập sau đây. Bạn phải đối mặt nhiều lần với một sự lựa chọn trong số k lựa chọn hoặc hành động khác nhau. Sau mỗi lựa chọn, bạn sẽ nhận được phần thưởng số được chọn từ phân phối xác suất cố định phụ thuộc vào hành động bạn đã chọn mục tiêu là tối đa hóa tổng phần thưởng dự kiến trong một khoảng thời gian, ví dụ: hơn 1000 lựa chọn hành động hoặc các time steps.

Đây là dạng ban đầu của bài toán k-armed bandit problem, nên được đặt tên tương tự với máy đánh bạc, hay “one-armed bandit", ngoại trừ việc nó có k đòn bẩy thay vì một đòn bẩy. Mỗi lựa chọn hành động giống như một trò chơi của một trong những đòn bẩy của máy đánh bạc và phần thưởng là phần thưởng để trúng giải độc đắc. Thông qua các lựa chọn hành động lặp đi lặp lại, bạn sẽ tối đa hóa số tiền thắng của mình bằng cách tập trung hành động vào các đòn bẩy tốt nhất. Một sự tương tự khác là một bác sĩ lựa chọn giữa các phương pháp điều trị thử nghiệm cho một loạt bệnh nhân nặng. Mỗi hành động là sự lựa chọn của một phương pháp điều trị và mỗi phần thưởng là sự sống còn hoặc hạnh phúc của bệnh nhân. Ngày nay, thuật ngữ k-armed bandit problem đôi khi được sử dụng để khái quát vấn đề được mô tả ở trên.

Trong k-armed bandit problem của chúng ta, mỗi hành động trong số k hành động có một phần thưởng mong đợi hoặc trung bình cho rằng hành động đó được chọn; chúng ta hãy gọi đây là giá trị của hành động đó. Chúng ta biểu thị hành động được chọn ở bước thời gian t là [imath]A_t [/imath] và phần thưởng tương ứng là R. Giá trị sau đó của một hành động tùy ý a, được ký hiệu là [imath]q_* (a)[/imath] , là phần thưởng mong đợi cho rằng a được chọn:

[math] q_*(a) \dot{=} E[R_t | A_t =a] [/math]

Nếu bạn biết giá trị của mỗi hành động, thì việc giải quyết vấn đề k-armed bandit: bạn sẽ luôn chọn hành động có giá trị cao nhất. Chúng ta giả định rằng bạn không biết các giá trị hành động một cách chắc chắn, mặc dù bạn có thể có các ước tính. Chúng ta biểu thị giá trị ước tính của hành động a tại thời điểm bước t là [imath]Q_t(a)[/imath] . Chúng ta muốn [imath]Q_t(a)[/imath] gần với [imath]q_*(a)[/imath] .

Nếu bạn duy trì ước tính của các giá trị hành động, thì tại bất kỳ bước nào cũng có ít nhất một hành động có giá trị ước tính lớn nhất. Chúng tôi gọi đây là những hành động tham lam (greedy). Khi bạn chọn một trong các hành động này, chúng tôi nói rằng bạn đang khai thác(exploiting) kiến thức hiện tại của mình về các giá trị của các hành động. Thay vào đó, nếu bạn chọn một trong các hành động phi tự do, thì chúng tôi cho rằng bạn đang khám phá(exploring), bởi vì điều này cho phép bạn cải thiện ước tính của mình về giá trị của hành động. Khai thác là điều đúng đắn cần làm để tối đa hóa phần thưởng mong đợi trên một bước, nhưng thăm dò có thể tạo ra tổng phần thưởng lớn hơn về lâu dài. Ví dụ: giả sử giá trị của một hành động tham lam được biết đến một cách chắc chắn, trong khi một số hành động khác được ước tính là tốt nhưng có độ không chắc chắn đáng kể. Sự không chắc chắn đến mức ít nhất một trong những hành động khác này có thể thực sự tốt hơn hành động tham lam, nhưng bạn không biết hành động nào. Nếu bạn còn nhiều thời gian để thực hiện các lựa chọn hành động, thì tốt hơn hết là bạn nên khám phá các hành động phi tham lam và khám phá xem hành động nào trong số đó tốt hơn hành động tham lam. Phần thưởng thấp hơn trong thời gian ngắn, trong quá trình thăm dò, nhưng cao hơn về lâu dài vì sau khi bạn phát hiện ra các hành động tốt hơn, bạn có thể khai thác chúng nhiều lần. Bởi vì không thể vừa khám phá vừa khai thác với bất kỳ lựa chọn hành động đơn lẻ nào, người ta thường đề cập đến “mâu thuẫn” giữa thăm dò và khai thác

Trong bất kỳ trường hợp cụ thể nào, việc khám phá hay khai thác tốt hơn phụ thuộc một cách phức tạp vào các giá trị chính xác của các ước tính, độ không đảm bảo và số bước còn lại. Có rất nhiều phương pháp phức tạp để cân bằng giữa việc thăm dò và khai thác cho các công thức toán học cụ thể của k-armed bandit problem và các bài toán liên quan.

Tuy nhiên, hầu hết các phương pháp này đưa ra các giả định mạnh mẽ về tính ổn định và kiến thức trước đó bị vi phạm hoặc không thể xác minh trong hầu hết các ứng dụng và trong vấn đề học tập củng cố đầy đủ mà chúng ta xem xét. Trong những phần tiếp trình bày một số phương pháp cân bằng đơn giản cho bài toán k-armed bandit problem và cho thấy rằng chúng hoạt động tốt hơn nhiều so với các phương pháp luôn khai thác. Nhu cầu cân bằng giữa việc khám phá và khai thác là một thách thức đặc biệt nảy sinh trong học tập củng cố;