Q-learning (học tăng cường)

Q -learning là một thuật toán học tăng cường không mô hình. Mục tiêu của Q-learning là học một chính sách, chính sách cho biết máy sẽ thực hiện hành động nào trong hoàn cảnh nào. Nó không yêu cầu một mô hình (do đó hàm ý "không mô hình") của môi trường và nó có thể xử lý các vấn đề với chuyển đổi và phần thưởng ngẫu nhiên, mà không cần điều chỉnh."

Đối với bất kỳ quá trình quyết định Markov hữu hạn (QTQDMKHH) nào, Q -learning tìm một chính sách tối ưu theo nghĩa là nó tối đa hóa giá trị mong đợi của tổng số phần thưởng trên bất kỳ và tất cả các bước tiếp theo, bắt đầu từ trạng thái hiện tại. Q -learning có thể xác định một chính sách lựa chọn hành động tối ưu cho bất kỳ QTQDMKHH cụ thể nào, với thời gian thăm dò vô hạn và chính sách một phần ngẫu nhiên. "Q" đặt tên theo tên hàm phần thưởng trả về, được sử dụng để cải thiện hoạt động và có thể nói là đại diện cho "chất lượng" của một hành động được thực hiện trong một trạng thái nhất định.

Học tăng cường

Học tăng cường liên quan đến một tác nhân, một tập hợp các trạng thái $S$và một bộ $A$các hành động trên mỗi trạng thái. Bằng cách thực hiện một hành động $a\in A$, các tác nhân chuyển từ trạng thái này sang trạng thái khác. Thực hiện một hành động trong một trạng thái cụ thể cung cấp cho tác nhân một phần thưởng (một số điểm). Mục tiêu của tác nhân là tối đa hóa phần thưởng (trong tương lai) của nó. Nó thực hiện điều này bằng cách thêm phần thưởng tối đa có thể đạt được trong tương lai vào phần thưởng để đạt được trạng thái hiện tại, do đó hiệu quả hoạt động của hành động hiện tại được đánh giá bằng phần thưởng tiềm năng trong tương lai. Phần thưởng tiềm năng này là tổng của các giá trị dự kiến của phần thưởng của tất cả các bước trong tương lai bắt đầu từ trạng thái hiện tại.Ví dụ, hãy xem xét quá trình lên tàu, trong đó phần thưởng được đo bằng mức âm của tổng thời gian lên tàu (nói cách khác, chi phí lên tàu bằng thời gian lên tàu). Một chiến lược là vào tàu ngay khi cửa mở, giảm thiểu thời gian chờ đợi ban đầu cho chính bạn. Tuy nhiên, nếu tàu đông đúc, thì bạn sẽ vào chậm hơn, sau hành động đầu tiên là bước vào cửa thì mọi người sẽ đẩy bạn ra để rời tàu khi bạn cố gắng lên tàu. Tổng thời gian lên tàu, hoặc chi phí là:

• Thời gian chờ 0 giây + thời gian chiến đấu 15 giây

Vào ngày hôm sau, do tình cờ ngẫu nhiên (thử nghiệm), bạn quyết định chờ đợi và để người khác xuống tàu trước. Điều này ban đầu dẫn đến thời gian chờ đợi lâu hơn. Tuy nhiên, thời gian chiến đấu với các hành khách khác là ít hơn. Nhìn chung, con đường này có phần thưởng cao hơn so với ngày hôm trước, vì tổng thời gian lên máy bay là:

• Thời gian chờ 5 giây + thời gian chiến đấu 0 giây.

Thông qua thăm dò, mặc dù hành động ban đầu (chờ đợi) dẫn đến chi phí (hoặc phần thưởng âm) lớn hơn so với chiến lược lao vào tàu, chi phí chung là thấp hơn, do đó là một chiến lược bổ ích hơn.

Theo lý thuyết, việc lựa chọn hành động tiếp theo là ngẫu nhiên, nhưng trên thực tế, để đẩy nhanh tốc độ hội tụ, giải pháp tham lam được áp dụng, hành động có phần thưởng tiềm năng cao hơn sẽ được chọn và có 1 tỉ lệ ngẫu nhiên chọn các hành động khác.

Thuật toán

Bảng Q-Learning về các trạng thái được khởi tạo thành 0, sau đó mỗi ô được cập nhật thông qua đào tạo.

Chi phí cho một bước từ một trạng thái đến $\Delta t$bước trong tương lai được tính là $\gamma ^{\Delta t}$.Trong đó $\gamma$là hệ số chiết khấu, một số từ 0 đến 1($0\leq \gamma \leq 1$) và có tác dụng định giá phần thưởng nhận được sớm hơn so với phần thưởng nhận được sau này (phản ánh giá trị của "khởi đầu tốt"). $\gamma$cũng có thể được hiểu là xác suất thành công (hoặc tồn tại) ở mọi bước $\Delta t$. Do đó, thuật toán có hàm tính toán chất lượng của sự kết hợp hành động trạng thái:

$Q:S\times A\to \mathbb {R}$.

Trước khi bắt đầu học, $Q$được khởi tạo là một giá trị cố định tùy ý (được chọn bởi người lập trình). Sau đó, tại mỗi thời điểm $t$tác nhân chọn một hành động $a_{t}$, quan sát một phần thưởng $r_{t}$, bước vào một trạng thái mới $s_{t+1}$ (điều đó có thể phụ thuộc vào cả trạng thái trước đó $s_{t}$ và hành động đã chọn) và $Q$được cập nhật. Cốt lõi của thuật toán là một cập nhật lặp lại giá trị đơn giản, sử dụng trung bình trọng số của giá trị cũ và thông tin mới:$Q^{new}(s_{t},a_{t})\leftarrow (1-\alpha )\cdot \underbrace {Q(s_{t},a_{t})} _{\text{old value}}+\underbrace {\alpha } _{\text{learning rate}}\cdot \overbrace {{\bigg (}\underbrace {r_{t}} _{\text{reward}}+\underbrace {\gamma } _{\text{discount factor}}\cdot \underbrace {\max _{a}Q(s_{t+1},a)} _{\text{estimate of optimal future value}}{\bigg )}} ^{\text{learned value}}$

Với $r_{t}$ là phần thưởng nhận được khi chuyển từ trạng thái $s_{t}$ sang trạng thái $s_{t+1}$ và $\alpha$ là tỷ lệ học ($0<\alpha \leq 1$).

Một tập của thuật toán kết thúc khi trạng thái $s_{t+1}$ là trạng thái cuối cùng hoặc trạng thái kết thúc. Tuy nhiên, Q -learning cũng có thể học trong các nhiệm vụ không có tình tiết. Nếu hệ số chiết khấu thấp hơn 1, các giá trị hành động là hữu hạn ngay cả khi sự cố có thể chứa các vòng lặp vô hạn.Đối với tất cả các trạng thái cuối cùng $Q(s_{f},a)$ không bao giờ được cập nhật, nhưng được đặt thành giá trị phần thưởng $r$ cho trạng thái $s_{f}$. Trong hầu hết các trường hợp, $Q(s_{f},a)$ có thể được đặt bằng không.

Ảnh hưởng của các biến

Tỷ lệ học

Tỷ lệ học hoặc kích thước bước xác định mức độ thông tin mới thu được sẽ ghi đè thông tin cũ. Hệ số 0 làm cho tác nhân không học được gì (chỉ khai thác kiến thức trước), trong khi hệ số 1 khiến tác nhân chỉ xem xét thông tin gần đây nhất (bỏ qua kiến thức trước để khám phá các khả năng). Trong môi trường hoàn toàn xác định, tỷ lệ học tập của $\alpha _{t}=1$ là tối ưu. Khi vấn đề là ngẫu nhiên, thuật toán hội tụ trong một số điều kiện kỹ thuật về tốc độ học tập yêu cầu nó giảm xuống không. Trong thực tế, thường sử dụng một tỷ lệ học tập liên tục, chẳng hạn như $\alpha _{t}=0.1$cho tất cả $t$.

Hệ số chiết khấu

Hệ số chiết khấu $\gamma$ xác định tầm quan trọng của phần thưởng trong tương lai. Hệ số 0 sẽ khiến tác nhân "cận thị" (hay thiển cận) bằng cách chỉ xem xét các phần thưởng hiện tại, tức là $r_{t}$ (trong quy tắc cập nhật ở trên), trong khi một yếu tố tiếp cận 1 sẽ khiến nó phấn đấu để nhận phần thưởng cao dài hạn. Nếu hệ số chiết khấu bằng hoặc vượt quá 1, các giá trị hành động có thể phân kỳ. Dành cho $\gamma =1$, không có trạng thái cuối, hoặc nếu tác nhân không bao giờ đạt tới một, tất cả lịch sử môi trường trở nên dài vô tận và các tiện ích với phần thưởng phụ gia, không được tiết lộ thường trở thành vô hạn. Ngay cả với hệ số chiết khấu chỉ thấp hơn một chút, việc học theo chức năng Q dẫn đến việc lan truyền các lỗi và sự không ổn định khi hàm giá trị được xấp xỉ với mạng nơ ron nhân tạo. Trong trường hợp đó, bắt đầu với hệ số chiết khấu thấp hơn và tăng nó theo giá trị cuối cùng sẽ đẩy nhanh quá trình học tập.

Điều kiện ban đầu (Q₀)

Vì Q -learning là một thuật toán lặp, nó mặc nhiên thừa nhận một điều kiện ban đầu trước khi cập nhật đầu tiên xảy ra. Giá trị ban đầu cao, còn được gọi là "điều kiện ban đầu lạc quan", có thể khuyến khích thăm dò: bất kể hành động nào được chọn, quy tắc cập nhật sẽ khiến nó có giá trị thấp hơn so với phương án khác, do đó tăng xác suất lựa chọn của chúng. Phần thưởng đầu tiên $r$có thể được sử dụng để thiết lập lại các điều kiện ban đầu. Theo ý tưởng này, lần đầu tiên một hành động được thực hiện phần thưởng được sử dụng để đặt giá trị của $Q$. Điều này cho phép học ngay lập tức trong trường hợp phần thưởng xác định cố định. Một mô hình kết hợp thiết lập lại các điều kiện ban đầu (RIC) dự kiến sẽ dự đoán hành vi của người tham gia tốt hơn một mô hình giả định bất kỳ điều kiện ban đầu tùy ý (AIC). RIC dường như phù hợp với hành vi của con người trong các thí nghiệm lựa chọn nhị phân lặp đi lặp lại.

Thực hiện

Q -learning tại đơn giản nhất lưu trữ dữ liệu trong bảng. Cách tiếp cận này chùn bước với số lượng trạng thái / hành động ngày càng tăng.

Xấp xỉ hàm

Q -learning có thể được kết hợp với xấp xỉ hàm. Điều này cho phép áp dụng thuật toán cho các vấn đề lớn hơn, ngay cả khi không gian trạng thái liên tục.

Một giải pháp là sử dụng một mạng nơ ron nhân tạo (thích nghi) như một hàm xấp xỉ hàm. Xấp xỉ hàm có thể tăng tốc độ học tập trong các vấn đề hữu hạn, do thực tế là thuật toán có thể khái quát hóa các kinh nghiệm trước đó cho các trạng thái chưa từng thấy trước đây.

Lượng tử hóa

Một kỹ thuật khác để giảm không gian trạng thái / hành động định lượng các giá trị có thể. Hãy xem xét ví dụ về việc học cách cân bằng một cây gậy trên ngón tay. Để mô tả trạng thái tại một thời điểm nhất định liên quan đến vị trí của ngón tay trong không gian, vận tốc của nó, góc của thanh và vận tốc góc của thanh. Điều này mang lại một vectơ bốn phần tử mô tả một trạng thái, tức là ảnh chụp nhanh của một trạng thái được mã hóa thành bốn giá trị. Vấn đề là vô số trạng thái có thể có mặt. Để thu hẹp không gian có thể của các hành động hợp lệ, nhiều giá trị có thể được gán cho một nhóm. Khoảng cách chính xác của ngón tay từ vị trí bắt đầu của nó (- vô cực đến + vô cực) không được biết, mà là nó có ở xa hay không (Gần, Xa).

Lịch sử

Q -learning được giới thiệu bởi Watkins vào năm 1989. Một bằng chứng hội tụ đã được trình bày bởi Watkins và Dayan vào năm 1992. Một bằng chứng toán học chi tiết hơn bởi Tsitsiklis vào năm 1994, và bởi Bertsekas và Tsitsiklis trong cuốn sách Lập trình động học Neuro năm 1996 của họ.

Watkins đã giải quyết vấn đề Học tập từ các phần thưởng bị trì hoãn, tiêu đề của Luận án tiến sĩ của ông. Tám năm trước đó vào năm 1981, cùng một vấn đề, dưới cái tên Căng thẳng học tăng cường học tập, đã được giải quyết bằng Mảng thích nghi Crossbar (CAA) của Bozinovski. Ma trận bộ nhớ W =|| w(a,s)|| cũng giống như tám năm sau Q-bảng của Q-learning. Các kiến trúc đã giới thiệu thuật ngữ "đánh giá trạng thái" trong học tăng cường. Thuật toán học thanh ngang, được viết bằng mã giả toán học trong bài báo, trong mỗi lần lặp lại thực hiện các tính toán sau:

• Trong trạng thái s hiện hành động a;
• Nhận trạng thái hệ quả s';
• Tính toán đánh giá trạng thái v(s');
• Cập nhật giá trị thanh ngang w'(a,s) = w(a,s) + v(s').

Thuật ngữ "tăng cường thứ cấp", được sử dụng từ lý thuyết học tập động vật, để mô hình hóa các giá trị trạng thái thông qua backpropagation: giá trị trạng thái v(s') của tình huống hậu quả được đặt ngược lại cho các tình huống gặp phải trước đây. CAA tính toán các giá trị trạng thái theo chiều dọc và hành động theo chiều ngang ("thanh ngang"). Biểu đồ trình diễn cho thấy việc học tăng cường bị trì hoãn chứa các trạng thái (mong muốn, không mong muốn và trạng thái trung tính), được tính toán bởi hàm đánh giá trạng thái. Hệ thống học tập này là tiền thân của thuật toán Q-learning.

Vào năm 2014, Google DeepMind đã cấp bằng sáng chế một ứng dụng Q-learning để học sâu, có tiêu đề "học tăng cường sâu" hoặc "Q-learning sâu" có thể chơi các trò chơi Atari 2600 ở cấp độ chuyên gia.

Biến thể

Q-learning sâu

Hệ thống DeepMind đã sử dụng một mạng lưới thần kinh tích chập sâu, với các lớp bộ lọc tích chập để mô phỏng các hiệu ứng của các lĩnh vực tiếp nhận. Học tăng cường không ổn định hoặc phân kỳ khi xấp xỉ hàm phi tuyến như mạng nơ ron được sử dụng để biểu diễn Q. Sự không ổn định này xuất phát từ các tương quan có trong chuỗi các quan sát, thực tế là các cập nhật nhỏ cho Q có thể thay đổi đáng kể chính sách và dữ liệu phân phối và mối tương quan giữa Q và các giá trị đích.

Kỹ thuật sử dụng phát lại kinh nghiệm, một cơ chế lấy cảm hứng từ sinh học sử dụng một mẫu ngẫu nhiên các hành động trước thay vì hành động gần đây nhất để tiến hành. Điều này loại bỏ các mối tương quan trong chuỗi quan sát và làm mịn các thay đổi trong phân phối dữ liệu. Cập nhật lặp điều chỉnh Q theo các giá trị đích chỉ được cập nhật định kỳ, giảm hơn nữa tương quan với mục tiêu.

Q-learning đôi

Bởi vì giá trị hành động xấp xỉ tối đa trong tương lai trong Q-learning được đánh giá bằng cách sử dụng chức năng Q ở trong chính sách lựa chọn hành động hiện tại, trong môi trường nhiễu, Q-learning đôi khi có thể đánh giá quá cao các giá trị hành động, làm chậm quá trình học. Một biến thể được gọi là Double Q-learning đã được đề xuất để sửa lỗi này. Double Q-learning là một thuật toán học lại tăng cường ngoài chính sách, trong đó một chính sách khác được sử dụng để đánh giá giá trị so với chính sách được sử dụng để chọn hành động tiếp theo.

Trong thực tế, hai hàm giá trị riêng biệt được đào tạo theo kiểu đối xứng lẫn nhau bằng cách sử dụng các trải nghiệm riêng biệt, $Q^{A}$ và $Q^{B}$. Bước cập nhật Q-learning đôi như sau:

$Q_{t+1}^{A}(s_{t},a_{t})=Q_{t}^{A}(s_{t},a_{t})+\alpha _{t}(s_{t},a_{t})\left(r_{t}+\gamma Q_{t}^{B}\left(s_{t+1},\mathop {\operatorname {arg~max} } _{a}Q_{t}^{A}(s_{t+1},a)\right)-Q_{t}^{A}(s_{t},a_{t})\right)$ và

${\displaystyle }$ $Q_{t+1}^{B}(s_{t},a_{t})=Q_{t}^{B}(s_{t},a_{t})+\alpha _{t}(s_{t},a_{t})\left(r_{t}+\gamma Q_{t}^{A}\left(s_{t+1},\mathop {\operatorname {arg~max} } _{a}Q_{t}^{B}(s_{t+1},a)\right)-Q_{t}^{B}(s_{t},a_{t})\right).$

Bây giờ giá trị ước tính của tương lai được đánh giá bằng cách sử dụng một chính sách khác, cái giải quyết vấn đề đánh giá quá cao.

Thuật toán này sau đó được kết hợp với học sâu, thành thuật toán DQN, dẫn đến Double DQN, vượt trội hơn thuật toán DQN ban đầu.

Khác

Q-learning bị trì hoãn là một triển khai thay thế của thuật toán Q -learning trực tuyến, với việc học đúng xấp xỉ với xác suất cao (PAC).

GQ tham lam là một biến thể của Q -learning để sử dụng kết hợp với xấp xỉ hàm (tuyến tính). Ưu điểm của GQ tham lam là sự hội tụ được đảm bảo ngay cả khi sử dụng xấp xỉ hàm để ước tính các giá trị hành động.

Xem thêm

• Học tăng cường
• Học khác biệt tạm thời
• SARSA
• Tình trạng khó xử lặp đi lặp lại của tù nhân
• Lý thuyết trò chơi

Liên kết ngoài

• Watkins, CJCH (1989). Học hỏi từ phần thưởng bị trì hoãn. Luận án tiến sĩ, Đại học Cambridge, Cambridge, Anh.
• Stroundl, Li, Wiewiora, Langford, Littman (2006). Học tăng cường mô hình miễn phí PAC
• Học tăng cường: Giới thiệu [1] của Richard Sutton và Andrew S. Barto, một cuốn sách giáo khoa trực tuyến. Xem "6.5 Q-Learning: Kiểm soát TD ngoài chính sách".
• Piqle: Nền tảng Java chung để học tăng cường
• Củng cố học tập Mê cung, một cuộc biểu tình hướng dẫn một con kiến thông qua một mê cung sử dụng Q -learning.
• Q -learning công việc của Gerald Tesauro
• Ví dụ về JavaScript với việc học RNN được thúc đẩy Lưu trữ 2018-04-20 tại Wayback Machine
• Thư viện não
• Một thư viện di truyền học được sử dụng bởi bộ não