Nhập Môn Học Tăng Cường: Các Phương Pháp Tabular
Trong phần này, chúng ta sẽ khám phá khái niệm cơ bản của Học Tăng Cường (Reinforcement Learning - RL) trong trạng thái tối giản nhất. Ở trạng thái này, không gian trạng thái (state space) và không gian hành động (action space) đủ để các giá trị (values) có thể được lưu trữ trong các mảng hoặc bảng. Trong các trường hợp như vậy, RL thường có khả năng tìm ra hành động tối ưu cho hầu hết các trạng thái.
Bài Toán K-armed Bandit
Hãy xem xét một tình huống lặp đi lặp lại trong việc chọn giữa n lựa chọn. Mỗi lần bạn chọn một hành động, bạn sẽ nhận được một phần thưởng ngẫu nhiên, và nhiệm vụ của bạn là phải lựa chọn các hành động sao cho tối ưu hóa số điểm nhận được sau một số lần nhất định.
Ví dụ: Giả sử bạn có 2 nút bấm: một nút màu đỏ và một nút màu xanh. Mỗi lần bấm nút màu đỏ, bạn nhận được 0, 1 hoặc 2 viên kẹo ngẫu nhiên. Mỗi lần bấm nút màu xanh, bạn nhận được 0, 1 hoặc 4 viên kẹo. Hãy đưa ra quyết định sao cho sau 10 lần bấm, bạn nhận được nhiều kẹo nhất.
Các Phương Pháp Giá Trị Hành Động
Chúng ta sẽ xem qua một số phương pháp đơn giản để ước tính giá trị của các hành động (actions) và sử dụng nó để đưa ra các quyết định trong việc chọn hành động sau này. Chúng ta định nghĩa giá trị thực tế (true value) của hành động a là q(a) và giá trị ước tính ở bước thứ t là Qt(a). Giá trị thực tế của một hành động là giá trị trung bình nhận được khi lựa chọn hành động đó.
Một trong những phương pháp phổ biến để xác định giá trị này chính là tính giá trị trung bình của phần thưởng (reward) khi một hành động được chọn. Nếu trong bước thứ t, hành động a được chọn Nt(a) lần, giá trị sẽ được dự đoán bằng công thức:
Nếu Nt(a) = 0, chúng ta sẽ đặt Qt(a) bằng một giá trị mặc định (có thể là 0). Khi Nt(x) tiến tới vô cùng, Qt(x) sẽ hội tụ về q(a). Phương pháp này được gọi là phương pháp sample-average để dự đoán giá trị hành động.
Một cách tiếp cận phổ biến để lựa chọn hành động là chọn hành động có giá trị cao nhất, theo cách gọi của các hành động tham lam (greedy actions).
Cách này được viết dưới dạng:
Hành động tham lam này luôn khai thác kiến thức hiện có để tối đa hóa giá trị phần thưởng tức thời. Nó sẽ không mất quá nhiều thời gian để lấy mẫu từ các hành động đã thực hiện để xác định hành động nào là tốt nhất. Một cách tiếp cận đơn giản là nó sẽ đưa ra các hành động tham lam hầu hết mọi lần thử, và chỉ thỉnh thoảng, với một xác suất thấp được xác định bởi epsilon, sẽ chọn các hành động ngẫu nhiên (explore). Phương pháp này được gọi là quy tắc chọn hành động gần tham lam (near-greedy action selection rule) hay còn gọi là phương pháp e-greedy. Lợi ích của phương pháp này là với số lần thử không ngừng tăng, mọi hành động sẽ được chọn vô hạn lần, đảm bảo rằng mọi Qt(a) sẽ hội tụ về q(a).
Bài Test 10-armed
Để kiểm tra hiệu quả của các phương pháp e-greedy và tham lam, chúng ta sẽ so sánh trên một tập hợp các bài test. Đây là một tập gồm 2000 bài k-armed bandit ngẫu nhiên với k=10. Trong mỗi bài, các giá trị hành động q*(a) sẽ được chọn ngẫu nhiên từ phân phối Normal (Gaussian) với trung bình 0 và phương sai 1.
Khi phương pháp lựa chọn được áp dụng để lựa chọn hành động At tại thời điểm t, phần thưởng thực tế Rt sẽ được chọn ngẫu nhiên từ phân phối Normal với trung bình q*(At) và phương sai 1.
Đối với mỗi phương pháp, chúng ta sẽ tính toán hiệu suất và hành vi của nó trong khi nó liên tục cải thiện trong 1000 bước của một trong các bài toán bandit. Điều này được gọi là một lần chạy (run), và chúng ta sẽ lặp lại việc này trong 2000 lần chạy độc lập để đo được hành vi trung bình.
Triển Khai Từng Bước
Trong các phương pháp giá trị hành động đã đề cập, chúng ta đều ước tính giá trị của các hành động dựa trên các giá trị trung bình của các phần thưởng nhận được. Bây giờ, chúng ta sẽ thảo luận về cách tính trung bình một cách hiệu quả nhất, trong thực tế với bộ nhớ cố định và tính toán không đổi ở mỗi bước.
Theo Dõi Vấn Đề Không Định Hình
Phương pháp tính trung bình mà ta đã đề cập là cho các bài toán k-bandit, nơi xác suất thưởng không thay đổi theo thời gian. Tuy nhiên, trong các bài toán không định hình (nonstationary problems), phương pháp đó có thể không hiệu quả. Trong những trường hợp này, hợp lý hơn khi đánh trọng số cho các phần thưởng gần gũi và hiện tại hơn là các phần thưởng đã nhận trong quá khứ.
Một phương pháp phổ biến hiện nay là sử dụng một hệ số bước (step-size constant). Trong ví dụ, công thức cập nhật giá trị trung bình Qn của phần thưởng có thể thay đổi thành:
Ở đây, tham số alpha thuộc (0, 1]. Kết quả của Qn+1 sẽ được tính toán bằng trung bình các phần thưởng trong quá khứ và giá trị khởi tạo Q1.
Phương pháp này được gọi là giá trị trung bình có trọng số (weighted average), vì tổng trọng số là.
Lưu ý rằng trọng số của Ri phụ thuộc vào số lần nhận được phần thưởng trước đó, n - i. Khi 1 - alpha nhỏ hơn 1, trọng số của Ri sẽ giảm dần theo số lần được hưởng phần thưởng. Thực tế, hệ số trọng số giảm dần theo cấp số nhân dựa trên mũ trong 1 - alpha.
Đôi khi, có thể cần điều chỉnh tham số bước với mỗi lần lựa chọn. Hãy để:
được sử dụng để tính toán phần thưởng nhận được sau lần thứ n chọn hành động a. Hãy lưu ý rằng lựa chọn là kết quả từ phương pháp mean sample, được xác nhận là hội tụ về giá trị hành động thực tế theo định lý đại số.
Rất tiếc, sự hội tụ không đảm bảo cho mọi lựa chọn của chuỗi. Một kết quả phổ biến từ lý thuyết xấp xỉ stochatic cho chúng ta biết điều kiện để đảm bảo sự hội tụ với xác suất 1:
- Điều kiện đầu tiên cần thiết để đảm bảo rằng các bước đủ lớn để vượt qua các điều kiện khởi đầu hoặc biến động ngẫu nhiên.
- Điều kiện thứ hai cần đảm bảo rằng các bước sẽ trở nên đủ nhỏ để đảm bảo sự hội tụ.
Cả hai điều kiện hội tụ đều được thỏa mãn trong trường hợp mẫu trung bình nhưng không phải cho trường hợp mà bước là hằng số.
Trong trường hợp này, điều kiện thứ hai không thỏa mãn, điều này cho thấy rằng dự đoán sẽ không hội tụ hoàn toàn mà sẽ tiếp tục thay đổi để thích ứng với các phần thưởng gần nhất. Đây cũng chính là lý do tại sao việc xác định trong môi trường không định hình (nonstationary environments) là hết sức quan trọng, đặc biệt phổ biến trong các bài toán Học Tăng Cường.
Cuối cùng, chuỗi bước hội tụ thường hội tụ chậm hoặc cần các phương pháp tuning để đạt tốc độ hội tụ tốt. Mặc dù vậy, các chuỗi bước hội tụ thoả mãn điều kiện hội tụ thường chỉ được sử dụng trong các vấn đề lý thuyết và ít khi được áp dụng trong thực tế hoặc nghiên cứu thực nghiệm.
Lời Kết
Tôi xin lỗi mọi người vì không dịch một số cụm từ sang tiếng Việt mà vẫn giữ nguyên tiếng Anh. Nguyên nhân là vì một số câu khi dịch mất đi nghĩa và không truyền đạt đầy đủ thông tin như mong muốn. Hy vọng bài viết này giúp bạn có cái nhìn sâu sắc hơn về Học Tăng Cường. Nếu bạn thật sự muốn tìm hiểu sâu hơn, hãy ủng hộ bài viết này nhé! Cảm ơn các bạn!
Tài Liệu Tham Khảo
- Học Tăng Cường - Tài liệu
source: viblo
