Q-learning là một phương pháp học tăng cường tuyệt vời và cơ bản đã cho thấy rất nhiều thành công gần đây nhờ cuộc cách mạng học sâu. Mặc dù hướng dẫn này sẽ không giải thích cái được gọi là deep Q-learning, nhưng chúng ta sẽ đi qua thuật toán Q-learning ban đầu để dạy một tác nhân cách chơi trò tic-tac-toe. Mặc dù đơn giản, nhưng chúng ta sẽ thấy rằng nó có thể mang lại kết quả tuyệt vời
Đầu tiên, chúng ta sẽ lướt qua một số kiến thức cơ bản cần thiết để có cái nhìn tổng quan về học tăng cường, sau đó chúng ta sẽ trình bày thuật toán Q-learning và cuối cùng là cách triển khai nó để dạy một tác nhân chơi tic-tac-toe
Để hiểu hướng dẫn này, không cần thiết phải có bất kỳ kiến thức nào trước đó về học tăng cường nhưng sẽ giúp bạn có hiểu biết cơ bản về giải tích và đại số tuyến tính. Cuối cùng, tôi đang chia sẻ kho lưu trữ Github của riêng mình, nơi tôi có những thứ mà tôi giải thích mà bạn có thể xem miễn phí, hãy nhấp vào đây nếu bạn quan tâm
Tổng quan về học tăng cường
Mục tiêu của học tăng cường là tối ưu hóa hành vi của một tác tử theo một số chức năng phần thưởng khi nó hoạt động trong một môi trường có các trạng thái khác nhau. Đối với hướng dẫn này, môi trường là trò chơi tic-tac-toe có các hành động được xác định rõ ràng và nhân viên phải quyết định chọn hành động nào để giành chiến thắng trong trò chơi. Hơn nữa, đại lý sẽ nhận được phần thưởng khi chiến thắng trò chơi, điều này khuyến khích đại lý học các chiến lược tốt trong trò chơi
Một khuôn khổ phổ biến cho việc học tăng cường là Quy trình quyết định Markov [hữu hạn] [MDP]. Nó giúp chúng tôi xác định một tập hợp các hành động và trạng thái làm cơ sở cho việc ra quyết định của tác nhân
Một MDP bao gồm
- Một tập hữu hạn các hành động A [vị trí để đánh dấu trên bàn trò chơi]
- Một tập hợp hữu hạn các trạng thái S [một cấu hình nhất định của bảng trò chơi]
- Hàm phần thưởng R[s,a] trả về giá trị dựa trên việc thực hiện hành động a ở trạng thái s
- Hàm chuyển tiếp T[s,a,s’]
Hàm chuyển tiếp đưa ra xác suất chuyển từ trạng thái s sang s' khi thực hiện hành động a. Điều này là cần thiết khi chúng ta ở trong một môi trường không chắc chắn liệu một hành động có luôn tạo ra kết quả mong muốn hay không. Tuy nhiên, trong trường hợp tic-tac-toe, chúng tôi biết chính xác mỗi hành động sẽ làm gì nên chúng tôi sẽ không sử dụng hành động này
Không gian trạng thái bao gồm tất cả các cấu hình trò chơi có thể. Tại mỗi trạng thái, chúng ta có thể thực hiện một tập hợp các hành động có sẵn. Trong ví dụ này, có sáu hành động có thể để người chơi hiện tại thực hiện. [Hình của tác giả]
Khung MDP giúp chúng tôi chính thức hóa vấn đề để xác định hành động nào, tùy thuộc vào trạng thái hiện tại, sẽ tối đa hóa tổng phần thưởng của tác nhân trong trò chơi. Hàm phần thưởng R[s,a] sẽ rất đơn giản
- Nếu tác nhân thực hiện một hành động â thắng trò chơi từ s, thì R[s,â] = 1
- Ngược lại, nếu đại lý mắc lỗi và chọn sai hành động ã dẫn đến thua trò chơi thì R[s,ã] = -1
- Mặt khác, khi không có điều nào ở trên xảy ra, phần thưởng chỉ đơn giản là R[s,a] = 0
Trong học tăng cường, chúng tôi tìm cách tìm ra một chính sách tối ưu mà tác nhân sử dụng để quyết định chọn hành động nào. Vì chúng tôi đang sử dụng Q-learning, chúng tôi sẽ chỉ biểu thị chính sách của mình là hành động a làm cực đại hàm Q[s,a] khi tác tử ở trạng thái s. Đây là cốt lõi của Q-learning, vậy chúng ta hãy tính toán hàm này như thế nào
Đối với mọi trạng thái trong trò chơi, mỗi hành động được liên kết với một giá trị Q. Chiến lược tốt nhất là chọn hành động có giá trị cao nhất. Trong ví dụ này với trạng thái s, lượt tiếp theo thuộc về người chơi X và rõ ràng hành động nào có phần thưởng được mong đợi cao nhất vì X sắp thắng
Cập nhật với phương trình Bellman
Giải thích Q[s,a] là Q là phần thưởng dự kiến được đưa ra khi kết thúc trò chơi nếu tác nhân chọn hành động a ở trạng thái s. Vì đại lý muốn tối đa hóa phần thưởng của mình, nên họ muốn chọn hành động tối đa hóa Q
Ví dụ về tình huống trong đó chúng tôi hiển thị các giá trị Q cho người chơi X hiện tại ở trạng thái này của trò chơi. Bằng cách đặt điểm đánh dấu tiếp theo ở vị trí có giá trị lớn nhất, người chơi sẽ thắng trò chơi và nhận phần thưởng. [Hình của tác giả]
Để tính Q[s,a], tác nhân phải khám phá tất cả các cặp trạng thái và hành động có thể có trong khi nhận phản hồi từ hàm phần thưởng R[s,a]. Trong trường hợp tic-tac-toe, chúng tôi cập nhật Q[s,a] lặp đi lặp lại bằng cách cho phép người đại diện chơi nhiều trò chơi với đối thủ. Với thuật toán Q-learning, phương trình được sử dụng để cập nhật Q như sau
- Chúng tôi thực hiện một hành động a trong trạng thái hiện tại s
- Thuật ngữ cuối cùng nhìn vào tương lai và trả về giá trị Q lớn nhất có sẵn, ŝ là trạng thái là trạng thái mới sau khi thực hiện hành động a. Khi đó, hành động â là hành động tốt nhất ở trạng thái tiếp theo ŝ
- Tỷ lệ học tập α quyết định mức độ chúng tôi ghi đè lên giá trị cũ, chúng tôi sẽ sử dụng α = 0. 1
- Hệ số chiết khấu γ quyết định mức độ quan trọng của phần thưởng trong tương lai so với phần thưởng hiện có tại thời điểm hiện tại bước t. Chúng tôi sẽ sử dụng γ = 0. 9
Phương trình này dựa trên phương trình nổi tiếng trong học tăng cường được gọi là phương trình Bellman. Hãy xem cách sử dụng phương trình này để dạy cho đại lý của chúng tôi
Triển khai thuật toán Q-learning
Để có được một đại lý được đào tạo, chúng ta cần tìm hiểu các giá trị của Q[s,a]. Điều này sẽ được thực hiện bằng cách để hai tác nhân chơi với nhau. Chúng tôi sẽ đưa ra xác suất ε là mỗi tác nhân chọn một hành động ngẫu nhiên, nếu không, nó sẽ chọn hành động tốt nhất theo Q[s,a]. Bằng cách này, chúng tôi đảm bảo cân bằng việc học sao cho các tác nhân đôi khi khám phá các hành động mới và những lần khác khai thác thông tin mà tác nhân đã học được
Giai đoạn đào tạo này có thể được mô tả bằng mã giả sau của thuật toán Q-learning
Initialise: Q[s,a] = 0, starting state s,
starting player P, iterations Nfor t = 0 : N With probability ε : P picks random action a
Else, pick action a that maximise Q[s,a] Observe new state ŝ and reward R[s,a] If current player is our agent,
update Q[s,a] = [1-α]Q[s,a] + α[R[s,a] + γ*max[Q[ŝ,â]]] s = ŝ
Switch turn, P = the other player
Chú ý số lần lặp N phải tương đối lớn, mình đang dùng khoảng 500.000. Ngoài ra, Q[s,a] có thể được triển khai dưới dạng lệnh Python hoặc dưới dạng mảng hai chiều nếu chúng ta biểu diễn [s,a] dưới dạng số nguyên. Cuối cùng, có thể thay đổi xác suất ε theo thời gian để nhấn mạnh việc khám phá ngẫu nhiên hơn trong các lần lặp lại trước đó, điều này có thể tăng tốc độ học tập
Sau khi bạn đã đào tạo đại lý của mình bằng thuật toán, bạn có thể lưu các giá trị của Q[s,a] và tải nó khi bạn muốn chơi với đại lý. Sau đó, tác nhân chỉ cần tuân theo chính sách tối ưu bằng cách chọn các hành động tối đa hóa Q[s,a]. Mặc dù tác nhân không trở nên thông minh lắm vì trò chơi tic-tac-toe đơn giản như thế nào, nhưng vẫn rất thú vị khi thử trò này nếu bạn muốn tìm hiểu cách triển khai Q-learning và thấy rằng nó hoạt động
Tóm lược
Tóm lại, hướng dẫn này lần đầu tiên giải thích khung Quá trình quyết định Markov [MDP] và cách nó được sử dụng trong học tăng cường. Chúng tôi đã lập mô hình trò chơi tic-tac-toe bằng cách sử dụng các trạng thái, hành động và chức năng phần thưởng. Ngoài ra, chúng tôi đã xác định hàm Q[s,a] định lượng phần thưởng mong đợi bằng cách chọn hành động a ở trạng thái s và đưa ra công thức tính Q[s,a] bằng cách chơi trò chơi nhiều lần
Tôi hy vọng rằng bạn thích hướng dẫn này, nếu bạn có bất kỳ câu hỏi nào thì bạn có thể liên hệ với tôi tại đây hoặc qua Twitter. Và cuối cùng, nếu bạn muốn xem nó hoạt động như thế nào trong thực tế thì hãy xem triển khai của tôi trong kho lưu trữ Github của tôi được liên kết bên dưới