[RL series] Thuật toán Q-Learning - BeeLab

Thursday, December 16, 2021

[RL series] Thuật toán Q-Learning

Bài trước tôi đã giới thiệu về RL và bây giờ tôi sẽ nói về phương pháp đơn giản để chúng ta dễ dàng tiếp cập với RL.



Q-learning là gì?

Q-learning là một thuật toán học tăng cường không có mô hình (Model-free). Nó học tập dựa trên các giá trị (values-based). Các thuật toán dựa trên giá trị cập nhật hàm giá trị dựa trên một phương trình (đặc biệt là phương trình Bellman). Trong khi loại còn lại, dựa trên chính sách (policy-based) ước tính hàm giá trị với một chính sách tham lam có được từ lần cải tiến chính sách cuối cùng.

Q-learning is an off-policy learner 

Có nghĩa là nó học được giá trị của chính sách (policy) tối ưu một cách độc lập với các hành động của chủ thể (agent). Mặt khác, on-policy learner tìm hiểu giá trị của chính sách đang được thực hiện bởi chủ thể, bao gồm các bước thăm dò và họ sẽ tìm ra một chính sách tối ưu, có tính đến việc khám phá (exploration) vốn có trong chính sách.


"Q" ở đây là gì?

Chữ ‘Q’ trong Q-learning là viết tắt của "quality" chất lượng. Chất lượng ở đây thể hiện mức độ hữu ích của một hành động (action) nhất định trong việc đạt được một số phần thưởng (reward) trong tương lai.


Yếu tố chính của Q-learning

  • Q*(s, a) là giá trị kỳ vọng (phần thưởng chiết khấu tích lũy) của việc thực hiện hành động (action) a ở trạng thái (state) s và sau đó tuân theo chính sách tối ưu (optimal policy).
  • Q-learning sử dụng "Sự khác biệt theo thời gian" Temporal Differences (TD) để ước tính giá trị của Q*(s, a). TD là một chủ thể (agent) có khả năng học hỏi từ môi trường thông qua các giai đoạn (episodes) mà không có kiến ​​thức trước về môi trường.
  • Chủ thể (agent) duy trì một bảng Q[S, A], trong đó S là tập các trạng thái và A là tập các hành động.
  • Q[ssđại diện cho ước tính hiện tại của nó là Q*(s, a).


Ví dụ

Giả sử một nhân viên phải di chuyển từ điểm bắt đầu đến điểm kết thúc dọc theo một con đường có chướng ngại vật. Nhiệm vụ cần đạt được tìm đường ngắn nhất có thể mà không va vào chướng ngại vật và anh ta cần đi theo ranh giới được che bởi chướng ngại vật. 


Để tiến hành thực hiện, trước hết ta cần định nghĩa thêm các khái niệm sau:
Q-table là bảng cấu trúc dữ liệu được sử dụng để tính toán phần thưởng (reward) dự kiến ​​tối đa trong tương lai cho hành động (action) ở mỗi trạng thái (each state). Về cơ bản, bảng này sẽ hướng dẫn chúng ta hành động tốt nhất ở mỗi trạng thái. Để tìm hiểu từng giá trị của Q-table, thuật toán Q-Learning được sử dụng.
Hàm Q: sử dụng phương trình Bellman và nhận hai đầu vào: trạng thái (s) và hành động (a).

Bellman Equation. Source: link


Quy trình xử lý của thuật toán Q-learning

Q-learning Algorithm

Bước 1: Khởi tạo Q-Table 

Có n cột, trong đó n = số hành động (action). Có m hàng, trong đó m = số trạng thái (state).

Trong ví dụ của chúng ta, n = Đi trái, Đi phải, Đi lên và Đi xuống và m = "Bắt đầu, Không hoạt động, Đường đúng, Đường sai và Kết thúc". Đầu tiên, hãy khởi tạo các giá trị bằng các giá trị 0.

Initial Q-table

Bước 2: Chọn một hành động

Bước 3: Thực hiện một hành động

Sự kết hợp của bước 2 và bước 3 được thực hiện trong một khoảng thời gian không xác định. Các bước này chạy cho đến khi quá trình huấn luyện thời gian bị dừng lại hoặc khi vòng lặp huấn luyện dừng lại như được xác định trong mã.

Đầu tiên, một action (a) hành động trong trạng thái state (s)  được chọn dựa trên Q-Table. Lưu ý rằng, như đã đề cập trước đó, khi tập ban đầu bắt đầu, mọi giá trị Q phải bằng 0.

Sau đó, cập nhật các giá trị Q để ở đầu và di chuyển sang phải bằng cách sử dụng phương trình Bellman được nêu ở trên.

Khái niệm Epsilon greedy strategy xuất hiện ở đây. Trong thời gian đầu, tỷ lệ epsilon sẽ cao hơn. Chủ thể (agent) sẽ khám phá môi trường và lựa chọn ngẫu nhiên các hành động (action). Điều này xảy ra như thế này một cách hợp lý, vì agent không biết gì về môi trường. Khi agent tham dò môi trường, tỷ lệ epsilon giảm và agent bắt đầu khám phá môi trường.Trong quá trình thăm dò (exploration), agent dần dần tự tin hơn trong việc ước tính các giá trị Q.

Trong ví dụ, khi bắt đầu đào tạo agent của chúng taagent hoàn toàn không biết về môi trường. Vì vậy, giả sử nó thực hiện một hành động ngẫu nhiên theo hướng "phải" của nó.

Giờ đây, chúng tôi có thể cập nhật các giá trị Q ở thời điểm bắt đầu và chuyển động sang phải bằng cách sử dụng phương trình Bellman.

Updated Q-table

Bước 4: Đo phn thưởng
Bây gi chúng tôi đã thc hin mt hành động và quan sát mt kết qu và phn thưởng.
Bước 5: Đánh giá
Chúng ta cn cp nht hàm Q(s, a).
Quá trình này được lp đi lp li nhiu ln cho đến khi ngng hc. Bng cách này, Q-Table được cp nht và hàm giá tr Q được ti đa hóa. đây Q (trng thái, hành động) tr v phn thưởng d kiến ​​trong tương lai ca hành động đó ti trng thái đó.
Bellman Equation Explanation for the episodes

Trong ví d, tôi đã nhp sơ đồ khen thưởng như sau.
  • Phn thưởng khi tiến gn hơđến mc tiêu = +1
  • Phn thưởng khi đạt chướng ngi vt = -1
  • Phn thưởng khi nhàn ri = 0

Ban đầu, chúng ta khám phá môi trường ca chủ thể (agent) và cp nht Q-Table. Khi Q-Table đã sn sàng, agent bt đầu khám phá môi trường và bt đầu thc hin các hành động tt hơn. Q-Table cui cùng có th ging như sau (ví d).

Example final Q-table

Sau đây là những kết quả dẫn đến con đường ngắn nhất của nhân viên hướng tới mục tiêu sau khi đào tạo.

No comments:

Post a Comment