Để minh họa ý tưởng chung của việc học củng cố và đối chiếu nó với các cách tiếp cận khác, tiếp theo, chúng ta sẽ xem xét một ví dụ chi tiết hơn.
Hãy xem trò chơi tic-tac-toe quen thuộc của trẻ em. Hai người chơi lần lượt chơi trên bảng ba nhân ba. Một người chơi chơi X và O cho đến khi một người chơi thắng bằng cách đặt ba dấu liên tiếp, theo chiều ngang, chiều dọc hoặc đường chéo, như người chơi X trong trò chơi được hiển thị ở bên trên. Nếu bàn chơi lấp đầy mà không có người chơi nào nhận được ba quân liên tiếp, thì trò chơi là một kết quả hòa. Bởi vì một người chơi có kỹ năng có thể chơi để không bao giờ thua, chúng ta hãy giả sử rằng chúng ta đang đấu với một người chơi không hoàn hảo, người có lối chơi đôi khi không chính xác và cho phép chúng ta giành chiến thắng. Trên thực tế, hiện tại, chúng ta hãy coi những trận hòa và những trận thua đều tồi tệ như nhau đối với chúng ta. Làm thế nào chúng ta có thể xây dựng một người chơi tìm ra điểm chưa hoàn hảo trong cách chơi của đối thủ và học cách tối đa hóa cơ hội chiến thắng?
Mặc dù đây là một vấn đề đơn giản, nó không thể dễ dàng được giải quyết một cách thỏa đáng thông qua các kỹ thuật cổ điển. Ví dụ, giải pháp "minimax" cổ điển từ lý thuyết trò chơi không đúng ở đây vì nó giả định một cách chơi cụ thể của đối thủ. Ví dụ, một người chơi minimax sẽ không bao giờ đạt đến trạng thái trò chơi mà từ đó nó có thể thua, ngay cả khi trên thực tế, nó luôn thắng từ trạng thái đó do đối thủ chơi không chính xác. Các phương pháp tối ưu hóa cổ điển cho các vấn đề quyết định tuần tự, chẳng hạn như lập trình động, có thể tính toán một giải pháp tối ưu cho bất kỳ đối thủ nào, nhưng yêu cầu đầu vào là thông số kỹ thuật hoàn chỉnh của đối thủ đó, bao gồm cả xác suất mà đối thủ thực hiện mỗi nước đi trong mỗi trạng thái bàn cờ. Hãy giả sử rằng thông tin này không có sẵn cho vấn đề này, vì nó không dành cho phần lớn các vấn đề của quan tâm thực tế. Mặt khác, những thông tin đó có thể được ước tính từ kinh nghiệm, trong trường hợp này là bằng cách chơi nhiều trò chơi với đối thủ. Điều tốt nhất mà người ta có thể làm đối với vấn đề này trước tiên là tìm hiểu mô hình hành vi của đối thủ, đến một mức độ tin cậy nào đó, sau đó áp dụng lập trình động để tính toán một giải pháp tối ưu dựa trên mô hình gần đúng của đối thủ.
Một phương pháp tiến hóa được áp dụng cho vấn đề này sẽ trực tiếp tìm kiếm không gian của các chính sách khả thi cho một phương pháp có xác suất chiến thắng đối thủ cao. Ở đây, chính sách là một quy tắc cho người chơi biết phải thực hiện động thái nào cho mọi trạng thái của trò chơi — mọi cấu hình có thể có của X và O trên bảng ba nhân ba. Đối với mỗi chính sách được xem xét, ước tính xác suất chiến thắng của chính sách đó sẽ đạt được bằng cách chơi một số trò chơi với đối thủ. Đánh giá này sau đó sẽ định hướng chính sách hoặc chính sách nào được xem xét tiếp theo. Một phương pháp tiến hóa điển hình sẽ leo dốc trong không gian chính sách, tạo ra và đánh giá liên tiếp các chính sách nhằm cố gắng đạt được những cải tiến gia tăng. Hoặc, có lẽ, một thuật toán kiểu di truyền có thể được sử dụng để duy trì và đánh giá một tập hợp các chính sách. Theo nghĩa đen, hàng trăm phương pháp tối ưu hóa khác nhau có thể được áp dụng.
Đây là cách tiếp cận vấn đề tic-tac-toe với một phương pháp sử dụng hàm giá trị. Đầu tiên, chúng ta sẽ thiết lập một bảng các con số, một cho mỗi trạng thái có thể có của trò chơi. Mỗi con số sẽ là ước tính mới nhất về xác suất chiến thắng của chúng ta từ trạng thái đó. Chúng ta coi ước tính này là giá trị của trạng thái và toàn bộ bảng là hàm giá trị đã học. Trạng thái A có giá trị cao hơn trạng thái B hoặc được coi là “tốt hơn” so với trạng thái B, nếu ước tính hiện tại về xác suất chiến thắng của chúng ta từ A cao hơn từ B. Giả sử chúng ta luôn chơi X, thì đối với tất cả các trạng thái có ba X liên tiếp xác suất trúng là 1, vì chúng ta đã trúng rồi. Tương tự, đối với tất cả các trạng thái có ba Os liên tiếp hoặc được điền đầy, xác suất chính xác là 0, vì chúng ta không thể giành chiến thắng từ chúng. Chúng ta đặt giá trị ban đầu của tất cả các trạng thái khác là 0,5, thể hiện phỏng đoán rằng chúng ta có 50% cơ hội chiến thắng.
Sau đó chúng ta chơi nhiều trò chơi với đối thủ. Để chọn nước đi của mình, chúng ta kiểm tra các trạng thái sẽ là kết quả của mỗi nước đi có thể có của chúng ta (một nước cho mỗi khoảng trống trên bàn cờ) và tra cứu các giá trị hiện tại của chúng trong bảng. Hầu hết thời gian chúng ta di chuyển một cách tham lam, chọn nước đi dẫn đến trạng thái có giá trị lớn nhất, tức là với xác suất chiến thắng ước tính cao nhất. Tuy nhiên, thỉnh thoảng, chúng ta chọn ngẫu nhiên trong số các nước đi khác. Đây được gọi là những động thái khám phá bởi vì chúng khiến chúng ta trải qua những trạng thái mà nếu không chúng ta có thể sẽ không bao giờ thấy. Một chuỗi các nước đi được thực hiện và xem xét trong một trò chơi có thể được vẽ sơ đồ như trong Hình 1.1
Hình 1.1: Một chuỗi các động tác tic-tac-toe. Các đường liền nét màu đen đại diện cho các nước đi được thực hiện trong một trò chơi; các đường đứt nét thể hiện các nước đi mà chúng ta (người chơi học tăng cường của chúng ta) đã xem xét nhưng không thực hiện. Dấu * cho biết động thái hiện được ước tính là tốt nhất. Nước đi thứ hai của chúng ta là một nước đi thăm dò, nghĩa là nó được thực hiện ngay cả khi một nước đi anh em khác, nước đi dẫn đến e*, được xếp hạng cao hơn. Các bước di chuyển thăm dò không dẫn đến bất kỳ hoạt động học nào, nhưng mỗi bước di chuyển khác của chúng ta thì có, gây ra các cập nhật như được đề xuất bởi các mũi tên màu đỏ, trong đó các giá trị ước tính được chuyển lên cây từ các nút sau đến các nút trước đó như được nêu chi tiết trong văn bản.
Trong khi chơi, chúng ta thay đổi giá trị của các trạng thái mà chúng ta nhận thấy trong trò chơi. Chúng ta cố gắng làm cho họ ước tính chính xác hơn về xác suất chiến thắng. Để làm điều này, chúng ta "sao lưu" giá trị của trạng thái sau mỗi lần di chuyển tham lam vào trạng thái trước khi di chuyển, như được gợi ý bởi các mũi tên trong Hình 1.1. Chính xác hơn, giá trị hiện tại của trạng thái trước đó được cập nhật để gần với giá trị của trạng thái sau hơn. Điều này có thể được thực hiện bằng cách di chuyển giá trị của trạng thái trước đó một phần nhỏ so với giá trị của trạng thái sau. Nếu chúng ta đặt
[imath]S_t[/imath]
biểu thị trạng thái trước khi di chuyển tham lam và
[imath]S_t + 1[/imath]
trạng thái sau khi di chuyển đó, thì cập nhật giá trị ước tính của
[imath]S_t[/imath]
, được ký hiệu là
[imath]V(S_t)[/imath]
có thể được viết như
[math]
V(S_t) \leftarrow V(S_t) + \alpha[V(S_{t+1}) - V (S_t)]
[/math]
trong đó
[imath]\alpha [/imath]
là một phần dương nhỏ được gọi là tham số kích thước bước, ảnh hưởng đến tốc độ học tập. Quy tắc cập nhật này là một ví dụ về phương pháp học chênh lệch thời gian, được gọi như vậy vì những thay đổi của nó dựa trên sự chênh lệch,
[imath]V(S_{t+1}) - V (S_t)[/imath]
, giữa các ước tính tại hai thời điểm liên tiếp.
Phương pháp được mô tả ở trên thực hiện khá tốt nhiệm vụ này. Ví dụ: nếu thông số kích thước bước được giảm đúng cách theo thời gian, thì phương pháp này, đối với bất kỳ đối thủ cố định nào, sẽ hội tụ xác suất chiến thắng thực sự từ mỗi trạng thái do người chơi của chúng ta đưa ra. Hơn nữa, các nước đi được thực hiện sau đó (ngoại trừ các nước đi thăm dò) trên thực tế là các nước đi tối ưu để chống lại đối thủ (không hoàn hảo) này. Nói cách khác, phương pháp này hội tụ một chính sách tối ưu để chơi trò chơi chống lại đối thủ này. Nếu thông số kích thước bước không giảm hết về 0 theo thời gian, thì người chơi này cũng chơi tốt trước những đối thủ chậm thay đổi cách chơi của họ.
Ví dụ này minh họa sự khác biệt giữa phương pháp tiến hóa và phương pháp học các hàm giá trị. Để đánh giá một chính sách, một phương pháp tiến hóa giữ chính sách đó cố định và chơi nhiều trò chơi với đối thủ hoặc mô phỏng nhiều trò chơi bằng cách sử dụng mô hình của đối thủ. Tần suất chiến thắng đưa ra ước tính không khách quan về xác suất chiến thắng với chính sách đó và có thể được sử dụng để chỉ đạo lựa chọn chính sách tiếp theo. Nhưng mỗi thay đổi về chính sách chỉ được thực hiện sau nhiều trò chơi và chỉ kết quả cuối cùng của mỗi trò chơi được sử dụng: những gì xảy ra trong trò chơi bị bỏ qua. Ví dụ: nếu người chơi thắng, thì tất cả các hành vi của họ trong trò chơi đều được ghi nhận, độc lập với việc các nước đi cụ thể có thể đóng vai trò quan trọng như thế nào đối với chiến thắng. Tín dụng thậm chí còn được trao cho những động thái không bao giờ xảy ra! Ngược lại, các phương pháp hàm giá trị cho phép các trạng thái riêng lẻ được đánh giá. Cuối cùng, các phương pháp hàm giá trị và tiến hóa đều tìm kiếm không gian của các chính sách, nhưng việc học hàm giá trị sẽ tận dụng thông tin có sẵn trong quá trình chơi.
Ví dụ đơn giản này minh họa một số đặc điểm chính của phương pháp học củng cố. Đầu tiên, cần phải chú trọng đến việc học hỏi trong khi tương tác với môi trường, trong trường hợp này là với một cầu thủ đối phương. Thứ hai, có một mục tiêu rõ ràng và hành vi đúng đắn đòi hỏi phải có kế hoạch hoặc tầm nhìn xa, có tính đến những ảnh hưởng bị trì hoãn đối với lựa chọn của một người. Ví dụ, người chơi học tăng cường đơn giản sẽ học cách đặt bẫy nhiều nước đi cho một đối thủ thiển cận. Đó là một đặc điểm nổi bật của giải pháp học tăng cường là nó có thể đạt được hiệu quả của việc lập kế hoạch và nhìn trước mà không cần sử dụng mô hình của đối thủ và không cần tiến hành tìm kiếm rõ ràng các chuỗi trạng thái và hành động có thể xảy ra trong tương lai
Trong khi ví dụ này minh họa một số tính năng chính của việc học tăng cường, nó đơn giản đến mức có thể tạo ấn tượng rằng việc học tăng cường bị hạn chế hơn thực tế. Mặc dù tic-tac-toe là một trò chơi hai người, nhưng học tập củng cố cũng được áp dụng trong trường hợp không có đối thủ bên ngoài, tức là trong trường hợp “trò chơi chống lại tự nhiên”. Học tập củng cố cũng không bị giới hạn đối với các vấn đề trong đó hành vi được chia thành các tập riêng biệt, như các trò chơi tic-tac-toe riêng biệt, chỉ có phần thưởng vào cuối mỗi tập. Nó chỉ áp dụng khi hành vi tiếp tục vô thời hạn và khi có thể nhận được phần thưởng lớn hơn bất cứ lúc nào. Học củng cố cũng có thể áp dụng cho các bài toán thậm chí không chia nhỏ thành các bước thời gian rời rạc như chơi tic-tac-toe. Các nguyên tắc chung cũng áp dụng cho các bài toán thời gian liên tục, mặc dù lý thuyết trở nên phức tạp hơn và chúng ta bỏ qua phần điều trị mở đầu này.
Tic-tac-toe có tập trạng thái tương đối nhỏ, hữu hạn, trong khi học tăng cường có thể được sử dụng khi tập trạng thái rất lớn, hoặc thậm chí là vô hạn. Ví dụ, Gerry Tesauro (1992, 1995) đã kết hợp thuật toán được mô tả ở trên với một mạng nơron nhân tạo để học cách chơi backgammon, có khoảng 1020 trạng thái. Với nhiều trạng thái này, không thể nào trải nghiệm nhiều hơn một phần nhỏ trong số chúng. Chương trình của Tesauro đã học được cách chơi tốt hơn nhiều so với bất kỳ chương trình nào trước đó và cuối cùng tốt hơn so với những người chơi giỏi nhất thế giới. Mạng nơ-ron nhân tạo cung cấp cho chương trình khả năng tổng quát hóa từ kinh nghiệm của nó, để ở các trạng thái mới, nó lựa chọn các bước di chuyển dựa trên thông tin được lưu từ các trạng thái tương tự đã gặp trong quá khứ, do mạng xác định. Hệ thống học tập củng cố có thể hoạt động tốt như thế nào trong các vấn đề với các tập hợp trạng thái lớn như vậy được ràng buộc chặt chẽ với mức độ phù hợp mà nó có thể khái quát từ quá khứ kinh nghiệm. Chính trong vai trò này, chúng ta có nhu cầu lớn nhất về các phương pháp học tập có giám sát trong học tập tăng cường. Mạng nơ-ron nhân tạo và học sâu không phải là cách duy nhất hoặc nhất thiết phải là cách tốt nhất để làm điều này.
Trong ví dụ tic-tac-toe này, việc học bắt đầu mà không có kiến thức trước nào ngoài các quy tắc của trò chơi, nhưng học tăng cường không có nghĩa là đòi hỏi một cái nhìn về học tập và trí thông minh. Ngược lại, thông tin trước đó có thể được đưa vào quá trình học tập củng cố theo nhiều cách khác nhau mà có thể là yếu tố quan trọng đối với việc học tập khoa học. Chúng tôi cũng có quyền truy cập vào trạng thái thực trong ví dụ tic-tac-toe, trong khi học tăng cường cũng có thể được áp dụng khi một phần của trạng thái bị ẩn hoặc khi các trạng thái khác biệt xuất hiện với người học là giống nhau.
Cuối cùng, người chơi tic-tac-toe đã có thể nhìn về phía trước và biết các trạng thái sẽ là kết quả của mỗi bước di chuyển có thể có của nó. Để làm được điều này, nó phải có một mô hình trò chơi cho phép nó thấy trước môi trường của nó sẽ thay đổi như thế nào để đáp ứng với những động thái mà nó có thể không bao giờ thực hiện. Nhiều vấn đề là như vậy, nhưng ở những vấn đề khác, thậm chí còn thiếu một mô hình ngắn hạn về tác động của các hành động. Học tập củng cố có thể được áp dụng trong cả hai trường hợp. Mô hình không bắt buộc, nhưng có thể dễ dàng sử dụng mô hình nếu chúng có sẵn hoặc có thể học được.
Tổng kết
Học tập củng cố là một cách tiếp cận tính toán để hiểu và tự động hóa việc học tập và ra quyết định theo mục tiêu. Nó được phân biệt với các phương pháp tiếp cận tính toán khác bởi nó nhấn mạnh vào việc học của một tác nhân từ tương tác trực tiếp với môi trường của nó, mà không yêu cầu sự giám sát mẫu mực hoặc mô hình hoàn chỉnh của môi trường. Theo chúng tôi, học tăng cường là lĩnh vực đầu tiên giải quyết nghiêm túc các vấn đề tính toán nảy sinh khi học từ tương tác với môi trường để đạt được các mục tiêu dài hạn. Học tập củng cố sử dụng khuôn khổ chính thức của các quy trình quyết định Markov để xác định sự tương tác giữa tác nhân học tập và môi trường của nó về trạng thái, hành động và phần thưởng. Khung này nhằm mục đích là một cách đơn giản để biểu diễn các tính năng thiết yếu của vấn đề trí tuệ nhân tạo. Những đặc điểm này bao gồm ý thức về nguyên nhân và kiến thức, cảm giác không chắc chắn và không xác định, và sự tồn tại của các mục tiêu rõ ràng. Các khái niệm về giá trị và hàm giá trị là chìa khóa. Việc sử dụng các hàm giá trị phân biệt các phương pháp học tập củng cố với các phương pháp tiến hóa tìm kiếm trực tiếp trong không gian chính sách được hướng dẫn bởi các đánh giá về toàn bộ chính sách.
