Học tăng cường

Trong ngành khoa học máy tính, học tăng cường (tiếng Anh: reinforcement learning) là một lĩnh vực con của học máy, nghiên cứu cách thức một agent trong một môi trường nên chọn thực hiện các hành động nào để cực đại hóa một khoản thưởng (reward) nào đó về lâu dài. Các thuật toán học tăng cường cố gắng tìm một chiến lược ánh xạ các trạng thái của thế giới tới các hành động mà agent nên chọn trong các trạng thái đó.

Môi trường thường được biểu diễn dưới dạng một quá trình quyết định Markov trạng thái hữu hạn (Markov decision process - MDP), và các thuật toán học tăng cường cho ngữ cảnh này có liên quan nhiều đến các kỹ thuật quy hoạch động. Các xác suất chuyển trạng thái và các xác suất thu lợi trong MDP thường là ngẫu nhiên nhưng lại tĩnh trong quá trình của bài toán (stationary over the course of the problem).

Khác với học có giám sát, trong học tăng cường không có các cặp dữ liệu vào/kết quả đúng, các hành động gần tối ưu cũng không được đánh giá đúng sai một cách tường minh. Hơn nữa, ở đây hoạt động trực tuyến (on-line performance) được quan tâm, trong đó có việc tìm kiếm một sự cân bằng giữa khám phá (lãnh thổ chưa lập bản đồ) và khai thác (tri thức hiện có). Trong học tăng cường, sự được và mất giữa khám phá và khai thác đã được nghiên cứu chủ yếu qua bài toán multi-armed bandit.

Một cách hình thức, mô hình học tăng cường bao gồm:

1. S: tập các trạng thái của môi trường;
2. A: tập các hành động; và
3. $\mathbb {R}$: tập các khoản "thưởng" với giá trị vô hướng.

Tại mỗi thời điểm t, agent thấy được trạng thái của nó là s_t $\in$ S và tập các hành động có thể A(s_t). Nó chọn một hành động a$\in$A(s_t) và nhận được từ môi trường trạng thái mới s_t+1 và một khoản thưởng r_t+1. Dựa trên các tương tác này, agent học tăng cường phải phát triển một chiến lược π:S$\rightarrow$A có tác dụng cực đại hóa lượng R=r₀+r₁+...+r_n với các MDP có một trạng thái kết thúc, hoặc lượng R=Σ_tγ^tr_t với các MDP không có trạng thái kết thúc (trong đó γ là một hệ số giảm khoản "thưởng trong tương lai" nào đó, với giá trị trong khoảng 0.0 và 1.0).

Do đó, học tăng cường đặc biệt thích hợp cho các bài toán có sự được mất giữa các khoản thưởng ngắn hạn và dài hạn. Học tăng cường đã được áp dụng thành công cho nhiều bài toán, trong đó có điều khiển robot, điều vận thang máy, viễn thông, các trò chơi backgammon và cờ vua.

Các thuật toán

Sau khi ta đã định nghĩa được một hàm trả về thích hợp cần được cực đại hóa, ta cần chỉ rõ thuật toán sẽ được sử dụng để tìm chiến lược thu được kết quả trả về cao nhất. Có hai cách tiếp cận chính, cách tiếp cận hàm giá trị và cách tiếp cận trực tiếp.

Cách tiếp cận trực tiếp dẫn đến hai bước sau đây:

1. Với mỗi chiến lược có thể, lấy mẫu các kết quả trong khi thực hiện chiến lược đó.
2. Chọn chiến lược có kết quả trả về kỳ vọng cao nhất.

Một vấn đề với cách tiếp cận này là số chiến lược có thể cực kỳ lớn, hoặc thậm chí vô hạn. Một vấn đề khác là các giá trị trả về có thể ngẫu nhiên, khi đó sẽ cần đến một lượng lớn các mẫu để có thể ước lượng chính xác kết quả trả về của mỗi chiến lược. Cách tiếp cận trực tiếp là cơ sở cho các thuật toán dùng trong ngành Robotic tiến hóa.

Các vấn đề của cách tiếp cận trực tiếp có thể được làm giảm nhẹ nếu ta giả thiết một cấu trúc nào đó trong bài toán và bằng cách nào đó cho phép các mẫu thu được từ một chiến lược này có thể được ảnh hưởng tới các ước lượng cho một chiến lược khác. Cách tiếp cận hàm giá trị thực hiện điều này bằng cách chỉ giữ một tập các ước lượng về các giá trị trả về của một chiến lược π (thường là chiến lược hiện tại hoặc chiến lược tối ưu). Trong các cách tiếp cận như vậy, người ta cố gắng ước lượng một trong hai hàm: giá trị trả về nếu xuất phát từ trạng thái s và theo chiến lược π như sau,

V(s) = E[R|s,π],

hoặc giá trị trả về kỳ vọng khi thực hiện hành động a trong trạng thái s và theo chiến lược π nghĩa là,

Q(s,a) = E[R|s,π],

Nếu có sẵn chiến lược tối ưu Q, ta luôn có thể chọn các hành động tối ưu đơn giản bằng cách tại mỗi trạng thái chọn hành động với giá trị cao nhất. Để thực hiện được điều này với V, ta phải có một mô hình môi trường, dưới dạng các xác suất P(s'|s,a), cho phép tính Q bằng công thức

$Q(s,a)=\sum _{s'}V(s')P(s'|s,a),$

hoặc ta có thể sử dụng các phương pháp Actor-Critic, trong đó mô hình được chia làm hai phần: phần critic giữ ước lượng giá trị trạng thái V, và phần actor có trách nhiệm chọn các hành động thích hợp với mỗi trạng thái.

Cho trước một chiến lược cố định π, việc ước lượng E[R|.] đối với γ=0 là đơn giản, do ta chỉ phải lấy trung bình của các khoản thưởng trực tiếp. Cách dễ thấy nhất để thực hiện việc này với γ>0 là lấy trung bình của tổng trả về sau mỗi trạng thái. Tuy nhiên, kiểu lấy mẫu Monte Carlo đòi hỏi MPD phải kết thúc.

Do đó, nói chung việc ước lượng $\gamma >0$ không dễ. Thực ra, việc này lại khá đơn giản khi ta nhận ra rằng giá trị kỳ vọng của R tạo nên một phương trình Bellman đệ quy: $E[R|s_{t}]=r_{t}+\gamma E[R|s_{t+1}]$

Bằng cách thay thế các giá trị kỳ vọng trên bằng các ước lượng của ta, V, và thực hiện thuật toán gradient descent với hàm chi phí lỗi bình phương, ta thu được TD(0) - thuật toán học temporal difference learning. Trong trường hợp đơn giản nhất, tập hợp các trạng thái và hành động đều là rời rạc và ta giữ các ước lượng dạng bản cho mỗi trạng thái. Các phương pháp cặp đôi trạng thái-hành động là SARSA và Q-Learning. Tất cả các phương pháp đều có các mở rộng mà nhờ đó một kiến trúc xấp xỉ nào đó được sử dụng, mặc dù trong một số trường hợp, sự hội tụ không được đảm bảo sẽ xảy ra. Các ước lượng thường được cập nhật bởi một dạng gradient descent, tuy rằng gần đây đã có các phương pháp bình phương tối thiểu cho các trường hợp xấp xỉ tuyến tính.

Các phương pháp trên không những đều hội tụ về các ước lượng đúng cho một chiến lược cố định, và còn có thể được dùng để tìm chiến lược tối ưu. Việc này thường được thực hiện bằng cách theo một chiến lược π được rút ra từ các ước lượng hiện tại, nghĩa là bằng cách hầu như luôn luôn chọn hành động với lượng giá cao nhất, và thỉnh thoảng chọn các hành động ngẫu nhiên để khám phá không gian. Các chứng minh cho sự hội tụ tới chiến lược tối ưu cũng tồn tại đối với các thuật toán nói đến ở trênvới một số điều kiện nhất định. Tuy nhiên tất cả các chứng minh này chỉ chứng tỏ sự hội tụ tiệm cận, và về lý thuyết người ta còn biết rất ít về hành vi của các thuật toán học tăng cường trong trường hợp mẫu nhỏ, ngoại trừ trong các điều kiện tham số (setting) rất hạn chế.

Một phương pháp khác để tìm chiến lược tối ưu là tìm thẳng trong không gian các chiến lược. Phương pháp không gian chiến lược định nghĩa chiến lược là một hàm có tham số π(s,θ) với các tham số θ. Thông thường, một phương pháp leo đồi (gradient method) được áp dụng để điều chỉnh các tham số. Tuy nhiên, việc áp dụng các phương pháp leo đồi không đơn giản, do không có thông tin nào về độ dốc (gradient information) được giả thiết. Thay vào đó, chính độ dốc phải được ước lượng từ các mẫu nhiều nhiễu (noisy samples) của kết quả trả về. Do điều này làm tăng mạnh chi phí tính toán, nên việc sử dụng một phương pháp leo đồi mạnh hơn là leo đồi độ dốc cao nhất(steepest gradient descent) có thể có lợi hơn. Các phương pháp leo đồi dùng cho không gian chiến lược đã được sự quan tâm lớn trong 5 năm trở lại đây và giờ đã đạt đến giai đoạn tương đối chính muồi, nhưng lĩnh vực nghiên cứu này vẫn còn hoạt động. Có nhiều cách tiếp cận khác, chẳng hạn luyện thép (simulated annealing), có thể dùng để khám phá không gian chiến lược. Các nghiên cứu về các kỹ thuật này ít phát triển hơn.

Nghiên cứu hiện tại

Các chủ đề nghiên cứu hiện tại bao gồm: Cách biểu diễn khác (chẳng hạn cách tiếp cận Predictive State Representation - biểu diễn trạng thái tiên đoán), tìm kiếm leo đồi trong không gian chiến lược, các kết quả hội tụ đối với mẫu nhỏ, các thuật toán và kết quả hội tụ cho các MDP quan sát được một phần (partially observable MDP), học tăng cường môdun và phân cấp (modular and hierarchical). Gần đây, học tăng cường đã được áp dụng trong lĩnh vực Tâm lý học để giải thích quá trình học và hoạt động của con người. Cụ thể, người ta đã dùng học tăng cường trong các mô hình nhận thức giả lập hoạt động của con người trong khi giải quyết các vấn đề hai khi học kỹ năng (v.d., Fu & Anderson, 2006).

Tham khảo

Leslie Pack Kaelbling; Michael L. Littman; Andrew W. Moore, Reinforcement Learning: A Survey Lưu trữ 2001-11-20 tại Library of Congress Web Archives, Journal of Artificial Intelligence Research 4 (1996) pp. 237–285

Richard S. Sutton; Andrew G. Barto, Reinforcement Learning Lưu trữ 2009-09-04 tại Wayback Machine, MIT Press, 1998, ISBN 0-262-19398-1 (full text online)

Dimitri P. Bertsekas; John Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996, ISBN 1-886529-10-8

Jan Peters; Sethu Vijayakumar; Stefan Schaal, Reinforcement Learning for Humanoid Robotics Lưu trữ 2013-05-12 tại Wayback Machine, IEEE-RAS International Conference on Humanoid Robots

Fu, W.-T., Anderson, J. R. (2006). Recurrent Choice to Skilled Learning Model. Learning: A Reinforcement Learning Model. Learning: A Reinforcement Learning Model. Lưu trữ 2009-07-04 tại Wayback Machine Journal of Experimental Psychology: General, 135 (2), 184-206.

Liên kết ngoài

• Reinforcement Learning Repository
• Reinforcement Learning and Artificial Intelligence Lưu trữ 2019-02-07 tại Wayback Machine
• RL-Glue Lưu trữ 2006-12-12 tại Wayback Machine