Giá trị Q-Giá trị gia tăng không mong muốn, hậu quả của phần thưởng thường xuyên sau khi lặp lại cùng một hành động trong Q-Learning

Question

Tôi đang trong quá trình phát triển thực hiện Q-Learning đơn giản qua một ứng dụng tầm thường, nhưng có điều gì đó khiến tôi khó hiểu .

Hãy xem xét việc xây dựng tiêu chuẩn của Q-Learning

Q(S, A) = Q(S, A) + alpha * [R + MaxQ(S', A') - Q(S, A)] 

Giả sử có trạng thái này K có hai hành động có thể, cả hai trao đại lý của chúng tôi thưởng R và R' bởi A và A'.

Nếu chúng ta tuân theo một cách tiếp cận gần như hoàn toàn tham lam (giả sử chúng ta giả định là 0,1 epsilon), đầu tiên tôi sẽ chọn ngẫu nhiên một trong các hành động, ví dụ A. Lần sau, có lẽ tôi sẽ (90% số lần) chọn lại A và điều đó sẽ khiến Q (K, A) tiếp tục tăng trưởng và phát triển, đúng là trường hợp ngay cả khi tôi cố gắng thử A', phần thưởng có cùng độ lớn với A, chúng tôi sẽ rơi vào tình huống mà thực tế là không thể "hồi phục" từ lần đoán đầu tiên của chúng tôi, trong phần còn lại của việc học.

Tôi đoán điều này không được như vậy, nếu không đại lý về cơ bản sẽ không học - nó sẽ chỉ theo một công thức đơn giản: làm mọi thứ như bạn đã làm lần đầu tiên.

Tôi có thiếu gì đó không? Tôi biết tôi có thể tinh chỉnh giá trị alpha (nói chung, giảm dần theo thời gian), nhưng điều đó không hề cải thiện tình hình của chúng tôi.

Answer 1

Q(K, A) không chỉ tiếp tục phát triển vô hạn, do cụm từ minus Q(S, A). Đây là rõ ràng hơn nếu bạn viết lại quy tắc cập nhật:

Q(S, A) <-- Q(S, A)(1 - a) + a(R + maxQ(S', A'))

Điều này cho thấy Q(K, A) chậm di chuyển về phía giá trị "thực tế" của R + maxQ(S', A'). Q(K, A) chỉ phát triển để tiếp cận điều đó; không phải vô hạn. Khi nó ngừng phát triển (đã xấp xỉ giá trị thực tế của nó), Q(K, A) cho các số khác A s có thể bắt kịp.

Dù sao, toàn bộ điểm epsilon là để kiểm soát xem bạn muốn quá trình học tập tham gia nhiều hơn (heuristic) hoặc khám phá (ngẫu nhiên), do đó tăng nó nếu quá trình học quá hẹp.

Cũng lưu ý rằng một trong những điều kiện chính thức cho hội tụ QL là mỗi cặp (S, A) được truy cập một số lần vô hạn (được diễn giải)! Vì vậy, có, vào cuối của quá trình đào tạo, bạn muốn mỗi cặp đã được truy cập một số tiền khá nhiều lần.

Chúc may mắn!

Answer 2

Từ this, chúng ta đều biết:

Sự hội tụ của Q-learning khoản giữ lại sử dụng bất kỳ chính sách thăm dò, và chỉ yêu cầu rằng mỗi tiểu bang cặp hành động (s,a) được thực hiện vô thường.

epsilon-greedy policy là sự cân bằng giữa thăm dò và khai thác, cả hai đều đảm bảo sự hội tụ và hiệu suất thường xuyên tốt.Nhưng trong các vấn đề thực tế, chúng ta thường cần một số chẩn đoán để thay đổi tốc độ học tập alpha để thể hiện sự trở lại tốt hơn. Nếu không, yêu cầu infinite often khó đáp ứng.

Tôi liệt kê ví dụ bên dưới. Đây là một vấn đề cổ điển, trong đó bạn có một mạng lưới và bạn có thể có số tiền thưởng khác nhau trong mỗi ô. Ví dụ: lưới 4x4 được hiển thị bên dưới, trong đó mỗi ô chứa một phần thưởng là 1, ngoại trừ ô trên cùng bên trái (bạn có phần thưởng lớn hơn với số tiền là 10). Một robot đang di chuyển trong lưới. Các hành động pháp lý đang di chuyển LEFT, RIGHT, UP và DOWN, nhưng rô-bốt không thể di chuyển ra khỏi lưới.

Vì vậy, không gian trạng thái của chúng tôi chứa 16 trạng thái riêng biệt, tương ứng với 16 ô. Đối với mỗi tiểu bang, có một số hành động pháp lý khác nhau do ràng buộc biên giới. Mục tiêu của chúng tôi là tính toán chính sách tối ưu (cho bất kỳ trạng thái s nào, đưa ra một hành động tối ưu a).

+++++++++++++++++++++ 
+ 10 + 1 + 1 + 1 + 
+++++++++++++++++++++ 
+ 1 + 1 + 1 + 1 + 
+++++++++++++++++++++ 
+ 1 + 1 + 1 + 1 + 
+++++++++++++++++++++ 
+ 1 + 1 + 1 + 1 + 
+++++++++++++++++++++ 

Giả sử chúng ta sử dụng một epsilon-greedy policy với epsilon=0.1, một tỷ lệ học liên tục alpha=0.1. Chúng ta bắt đầu với một vị trí ngẫu nhiên trên lưới. Bất cứ khi nào chúng tôi đạt đến góc trên bên trái, chúng tôi khởi động lại với một vị trí ngẫu nhiên một lần nữa.

Dưới đây là kết quả của việc chạy mô phỏng 200.000 di chuyển. Khối ngoài cùng bên trái hiển thị chính sách tham chiếu hiện tại ở mỗi ô.

• --> di chuyển đúng
• <-- di chuyển trái
• ^ Chuyển lên
• v Di chuyển xuống

Vì vậy, bạn thấy điều này là xa từ một chính sách tối ưu. Rõ ràng là trong một chính sách tối ưu, mỗi ô nên trỏ sang trái hoặc lên vì chúng ta có phần thưởng lớn hơn đáng kể ở vị trí (0,0).

v v v v |  2  9  5  4 
v v v v |  14  98  75  14 
--> v v <-- | 258 3430 3312 245 
--> --> <-- <-- | 3270 93143 92978 3191 

Khối bên phải hiển thị số lần chúng tôi truy cập từng ô cho đến thời điểm này. Bạn thấy rằng chúng tôi dành hầu hết các lượt truy cập ở dưới cùng nhưng chúng tôi truy cập hàng trên cùng rất hiếm. Đây là lý do tại sao chúng tôi chưa đạt được chính sách tối ưu.

Nếu chúng tôi thay đổi tỷ lệ học là alpha=1/(number of times you visited (s,a) so far), chúng tôi có thể đạt được chính sách tối ưu (được hiển thị bên dưới) trong vòng 20.000 bước. Ngoài ra số lần chúng tôi truy cập mỗi ô được phân phối đồng đều hơn mặc dù không hoàn hảo.

--> <-- <-- <-- |  34 7997 7697 294 
^^^<-- | 731 898 524 132 
^^^^ | 709 176  88  94 
^^^^ | 245 256  96  77 

Đối với vấn đề lớn hơn với nhiều trạng thái hơn, ví dụ: lưới 10x10, tôi thấy tốt hơn nên sử dụng lớn hơn epsilon. Ví dụ: dưới đây là kết quả của mô phỏng sau khi 80.000 di chuyển trên lưới 10x10 với epsilon=0.5. Nó gần như tối ưu trừ góc dưới cùng bên phải. Ngoài ra còn có idea về cách sử dụng Simulated Annealing để giúp cải thiện tốc độ hội tụ của Q-learning.

v <-- <-- <-- <-- <-- <-- <-- <-- <-- |  19 2500 1464 716 386 274 216 159 121  71 
^ <-- <-- <-- <-- v <-- <-- <-- <-- | 9617 11914 3665 1071 580 410 319 225 207 131 
^ ^^<-- <-- <-- <-- v <-- <-- | 5355 5716 2662 1675 1465 611 302 183 162 101 
^ ^^^^<-- <-- <-- <-- <-- | 1604 1887 1192 621 1056 882 693 403 206 100 
^ ^^^^^^<-- <-- <-- | 639 735 731 333 412 399 480 294 172 114 
^ ^^<--^^^<-- <--^ | 373 496 640 454 272 266 415 219 107  98 
^ ^^^^^^^<--^ | 251 311 402 428 214 161 343 176 114  99 
^ ^^^<-- -->^<-- <-- <-- | 186 185 271 420 365 209 359 200 113  70 
^ ^^^^^^^ v v | 129 204 324 426 434 282 235 131  99  74 
^ ^^^^<--^<-- <-- <-- | 100 356 1020 1233 703 396 301 216 152  78 

BTW, mã Python (~ 100 dòng) cho vấn đề đồ chơi là here.

Answer 3

Như đã đề cập trong một trong các nhận xét, giá trị gamma nhỏ hơn một là những gì đảm bảo rằng tổng sẽ không trôi dạt đến vô cực dương (cho rằng phần thưởng tự bị ràng buộc).

Nhưng nó thực sự có thể gặp khó khăn trong một lựa chọn tồi trong một thời gian. Có một số điều có thể được thực hiện:

Khởi tạo tối ưu: Nếu bạn bắt đầu tất cả giá trị Q một cách lạc quan, thì mỗi khi bạn thử cái gì đó mới, bạn sẽ bị "vỡ mộng" để lần sau bạn sẽ muốn thử cái gì khác. Điều này tiếp tục cho đến khi bạn có ý nghĩa thực tế về giá trị của mỗi hành động.

Làm việc với các chức năng lợi thế: Trong trường hợp mọi hành động đều tốt nhưng một số thì tốt hơn các hành động khác, tốt hơn là sử dụng hàm lợi thế. trạng thái) để cập nhật thông số của bạn. Điều này đặc biệt hữu ích cho các gradient chính sách.