Chào các bạn, sau một thời gian ở ẩn, chúng ta lại tiếp tục với việc thực chiến AI, ở bài viết này, chúng ta sẽ train mô hình AI Reinforcement Learning với tựa game đã đi vào bao nhiêu thế hệ trẻ thơ, Mario, tuy nhiên, để bắt đầu bài viết, mình sẽ note lại một vài ý về Reinforcement Learning, Q learning, và cải tiến của Deep Q-Network là Double Deep Q-Network , trong phần code mình sẽ sử dụng Double Deep Q-Network

Lý thuyết căn bản Reinforcement Learning

Các thành phần cơ bản của Reinforcement Learning

Theo lý thuyết Reinforcement Learning, chúng ta cần các thành phần sau:

Agent: là đối tượng giữ các hành động (Action), thực hiện các hành động

Environment : Môi trường xung quanh nơi agent tương tác

Action : Danh sách các hành động mà Agent thực hiện, ví dụ nhảy, chạy, đi lên trước 1 bước, đi lùi 1 bước, bắn đạn … Khi Agent thực hiện các action, thì environment thay đổi

State : Danh sách các trạng thái của environment khi có action từ agent

Optimal Action-Value function : Hàm Q*(s,a), chữ Q có thể hiểu là viết tắt của từ quality

Reward : Agent nhận reward từ Environment khi có action

Ví dụ, Agent là con robot, Ation là [dậm chân, vỗ tay ], khi con robot dậm chân, môi trường thay đổi, đất lún hơn một chút, lúc này State là 1 bức tranh có 1 con rô bốt với chân con rô bốt hơi hơi lún một chút xuống đất, và environment sẽ trả về 1 giá trị Reward nào đó cho Agent sau hành động dậm chân của Agent, dễ hiểu phải không các bạn.

Reward của hành động dậm chân có thể sẽ có giá trị khác so với reward của hành động vỗ tay.

Vì chúng ta không biết khi nào hành động kết thúc, nên rewards sẽ là một chuỗi vô hạn các reward sau thời điểm action xảy ra, tính từ thời điểm t_0 ban đầu.

Chuỗi vô hạn không có hội tụ, nên người ta chế (trick) sẽ thêm 1 tham số là discount factor hay discount rate, để chuỗi này hội tụ.

Lý thuyết toán học đứng đằng sau là Markov decision process và sử dụng nền tản là phương trình Bellman, Markov decision process đã được đề xuất từ năm 1950s, bạn có thể tra google để tìm hiểu thêm. Giờ mình hiểu là có lý thuyết toán học đảm bảo chuỗi này hội tụ rồi, triển thôi.

Lý thuyết toán học

Ở mục này mình đề cập một chút về Markov decision process và phương trình Bellman, các bạn có thể bỏ qua nếu thấy ngán, mình note lại để sau này khỏi mất công tìm

Phương trình của Markov Decision Process (MDP) chính là biểu thức mô tả cách giá trị của các trạng thái hoặc hành động được cập nhật thông qua quá trình ra quyết định. Tuy nhiên, bản thân MDP không có một phương trình duy nhất cụ thể, mà thường được mô tả qua các thành phần cơ bản như tập trạng thái, hành động, xác suất chuyển trạng thái, phần thưởng, và hệ số chiết khấu.

Phương trình chính xác nhất liên quan đến MDP là phương trình Bellman, mà chúng ta có thể viết theo hai dạng: dạng hàm giá trị trạng thái và dạng hàm giá trị hành động. Hai phương trình này thể hiện rõ cách tính toán tổng phần thưởng kỳ vọng.

1. Markov Decision Process (MDP)

MDP là một khung toán học dùng để mô tả các bài toán ra quyết định trong môi trường không chắc chắn. Một MDP bao gồm các thành phần sau:

• S (State space): Tập hợp các trạng thái có thể xảy ra trong môi trường.
• A (Action space): Tập hợp các hành động mà người ra quyết định (agent) có thể thực hiện ở mỗi trạng thái.
• P (Transition probability): Xác suất chuyển trạng thái ( P(s’|s, a) ), biểu thị xác suất trạng thái kế tiếp ( s’ ) xảy ra khi thực hiện hành động ( a ) tại trạng thái ( s ).
• R (Reward function): Hàm thưởng ( R(s, a) ), là phần thưởng tức thì nhận được khi thực hiện hành động ( a ) tại trạng thái ( s ).
• $(\gamma) (Discount factor)$: Hệ số chiết khấu $( \gamma \in [0, 1] )$, xác định mức độ ưu tiên cho phần thưởng tức thì so với phần thưởng trong tương lai. Khi $( \gamma )$ gần bằng 1, giá trị các phần thưởng trong tương lai càng được đánh giá cao.

Mục tiêu của MDP là tìm ra chính sách tối ưu - optimal policy $( \pi^* )$, tức là một chuỗi các hành động giúp tối đa hóa tổng phần thưởng kỳ vọng trong dài hạn.

2. Phương trình Bellman

Phương trình Bellman mô tả mối quan hệ đệ quy giữa giá trị của một trạng thái hoặc một hành động với các trạng thái kế tiếp hoặc hành động tiếp theo. Nó thường được sử dụng để tính toán giá trị kỳ vọng của các trạng thái hoặc hành động, giúp đánh giá và tìm ra chính sách tối ưu.

a. Phương trình Bellman cho hàm giá trị trạng thái ( V(s) )

Hàm giá trị trạng thái ( V(s) ) cho biết tổng phần thưởng kỳ vọng khi bắt đầu từ trạng thái ( s ) và theo chính sách tối ưu. Phương trình Bellman cho hàm giá trị trạng thái là:

$$ [ V(s) = \max_{a} \left[ R(s, a) + \gamma \sum_{s’} P(s’|s, a)V(s’) \right] ] $$

Ở đây:

• ( V(s) ) là giá trị của trạng thái ( s ).
• ( R(s, a) ) là phần thưởng nhận được khi thực hiện hành động ( a ) tại trạng thái ( s ).
• ( P(s’|s, a) ) là xác suất chuyển từ trạng thái ( s ) sang trạng thái ( s’ ) khi thực hiện hành động ( a ).
• $( \gamma )$ là hệ số chiết khấu, và $( \sum_{s’} P(s’|s, a)V(s’) )$ là giá trị kỳ vọng của các trạng thái tiếp theo.

b. Phương trình Bellman cho hàm giá trị hành động ( Q(s, a) )

Hàm giá trị hành động ( Q(s, a) ) biểu diễn tổng phần thưởng kỳ vọng khi bắt đầu từ trạng thái ( s ), thực hiện hành động ( a ), và sau đó tiếp tục theo chính sách tối ưu. Phương trình Bellman cho hàm giá trị hành động là:

$$ [ Q(s, a) = R(s, a) + \gamma \sum_{s’} P(s’|s, a) \max_{a’} Q(s’, a’) ] $$

Ở đây:

• ( Q(s, a) ) là giá trị của hành động ( a ) ở trạng thái ( s ).
• ( \max_{a’} Q(s’, a’) ) là giá trị tối ưu của hành động tiếp theo ở trạng thái kế tiếp ( s’ ).

Q-Learning

Q-learning là một thuật toán trong nhóm học tăng cường (reinforcement learning) , thuộc nhóm model-free, value-based, off-policy. Thuật toán sẽ tìm ra chuỗi hành động tốt nhất dựa trên trạng thái hiện tại của agent. “Q” đại diện cho chất lượng. Chất lượng biểu thị giá trị của hành động trong việc tối đa hóa (cực đại hóa) phần thưởng ở tương lai.

Có một số key word cần làm rõ một chút.

Chúng ta có hai nhóm thuật toán là model-base và model-free

• model-base dùng 2 hàm là transition và reward để ước tính đường đi tối ưu, chúng ta phải vắt óc suy nghĩ 2 hàm này, tưởng tượng bạn chơi cờ và dự đoán trước các nước đi của đối thủ, biết được đối thủ sẽ đi như thế nào, nên ta có thể chọn những nước đi sao cho kết quả cuối cùng ta sẽ thắng.

• model-free học từ chuỗi hành động, rút ra kinh nghiệm, và vấp ngã đâu , đứng dậy ở đó, không cần định nghĩa transition function và reward function. Tưởng tượng bạn tự mình học cách đi xe đạp, bạn ngã, rút kinh nghiệm từ lỗi lầm và dần dần đi được mà không cần bản hướng dẫn chi tiết nào, cứ ôm xe đạp mà tập dần.

Tiếp tới, chúng ta có 2 loại phương thức là value-based và policy-based

• Phương pháp value-based , huấn luyện hàm giá trị, huấn luyện làm sao để hàm giá trị có thể tìm ra trạng thái mà trạng thái đó làm cho hàm giá trị đạt giá trị lớn nhất, đạt giá trị cực đại, từ đó quyết định sử dụng hành động đó. Nói cách khác, nó giúp agent hiểu xem ở trạng thái nào thì hành động nào sẽ mang lại phần thưởng cao nhất. Ví dụ, bạn chọn môn học có giá trị nhất để học trước nhằm đạt điểm số cao nhất.

• Phương pháp policy-based đưa ra các policy quy định ứng với từng state, ta sẽ đưa ra các action gì, nó học cách đưa ra quyết định tốt nhất trong từng trạng thái. Giống như khi bạn không chỉ học lý thuyết mà thực sự thực hành để biết cách hành động tốt nhất trong từng tình huống cụ thể.

Cuối cùng, có 2 cái chính sách đối lập là off-policy và on-policy

• off-policy thuật toán đánh giá và cập nhật lại policy mới, policy mới khác với policy đang thực hiện action. Nghĩa là nó không cần theo đúng chính sách hiện hành mà có thể học và cải thiện chính sách mới dựa trên dữ liệu và kinh nghiệm thu thập được, kiểu như là vừa chơi game vừa nghĩ ra chiến lược mới thay vì bám sát chiến lược cũ.

• on-policy nó không chỉ dùng chính sách hiện tại mà còn điều chỉnh và cải thiện chính sách đó liên tục dựa trên những gì đã học được từ mỗi hành động. Như cách bạn tiếp tục hoàn thiện chiến lược chơi game của mình mỗi lần chơi dựa trên những gì đã trải qua.

Các khái niệm trong Q-learning

Kế thừa các key trong Reinforcement Learning, chúng ta có

States(s) : vị trí hiện tại của agent trong environment

Action(a) : Hành động của agent trong một state cụ thể

Rewards : Giá trị phần thưởng hoặc giá trị phạt khi một Action xảy ra

Episodes: Kết thúc state, khi Agent không thể thực hiện một action mới. Episodes xảy ra khi agent phá đảo hoặc agent bị die

$Q(S_t+1, a)$ : Giá trị kỳ vọng đạt được Q value ở state t+1 và hành động a

Cách Q-learning hoạt động

Q-Table

Q-Table về cơ bản là một bảng tra cứu, trong đó mỗi hàng đại diện cho một trạng thái có thể có, và mỗi cột đại diện cho một hành động có thể thực hiện. Bảng này lưu trữ các giá trị Q-values (phần thưởng kỳ vọng) cho mỗi cặp trạng thái-hành động. Theo thời gian, Agent sẽ cập nhật bảng này để học cách lựa chọn hành động tốt nhất trong mỗi trạng thái.

Q-value

Q-value đại diện cho phần thưởng tương lai, kỳ vọng mà Agent sẽ nhận được khi thực hiện một hành động nhất định từ trạng thái hiện tại, và sau đó thực hiện theo policy tốt nhất (tối đa hóa phần thưởng).

Q-learning Function

Là một model-free reinforcement learning, sử dụng phương trình Bellman, cập nhật bảng Q thông qua việc học từ sự tương tác với môi trường. Khi Agent thực hiện một hành động, nó sẽ quan sát phần thưởng và trạng thái mới mà nó chuyển đến. Thuật toán sau đó sẽ cập nhật giá trị Q cho cặp trạng thái-hành động đó theo quy tắc cập nhật sau:

$$ [ Q(s, a) \leftarrow Q(s, a) + \alpha \left( r + \gamma \max_a’ Q(s’, a’) - Q(s, a) \right) ] $$

Trong đó:

• $( Q(s, a) )$ là giá trị Q cho trạng thái ( s ) và hành động ( a )
• $( \alpha )$ là tốc độ học (quyết định mức độ mà thông tin mới ghi đè thông tin cũ)
• $( r )$ là phần thưởng nhận được sau khi thực hiện hành động ( a ) ở trạng thái ( s )
• $( \gamma )$ là hệ số chiết khấu (xác định mức độ phần thưởng tương lai được tính đến)
• $( \max_a’ Q(s’, a’) )$ là phần thưởng kỳ vọng lớn nhất cho trạng thái tiếp theo ( s’ ) sau hành động ( a’ )

Theo thời gian, Agent sử dụng Q-learning sẽ dần dần hoàn thiện bảng Q của mình và học được cách thực hiện các hành động tối ưu cho mỗi trạng thái để tối đa hóa phần thưởng kỳ vọng.

Q-learning algorithm

Init Q_table -> Choose action -> Do action -> Mesure reward -> Update Q Table -> Choose action …

Init Q_table

Xây dựng bảng bao gồm hàng là các state, cột là các action , đầu tiên có thể khởi tạo giá trị của bảng này là 0.

Choose action

Ở lần chạy đầu tiên, chúng ta có thể random action, ở lần chạy sau, chúng ta lấy action ở bảng Q Table ở trên

Do action

Thực hiện chọn hành động và thực hiện hành động đến khi quá trình train dừng lại.

Với mỗi lần Choose action và Do action, chúng ta sẽ:

Ở lần chạy đầu tiên, chúng ta lấy ngẫu nhiên 1 hành động, sau đó Agent sẽ thực hiện hành động và nhận reward, update Q Table sử dụng Q-learning Function đã nêu phía trên. Ở các lần chạy sau, chúng ta lấy ra hành động tốt nhất để Agent thực hiện hành động và chúng ta lại update Q Table tiếp.

Vì lý do là Agent cần tối đa hóa phần thưởng đạt được, nên ở đây xuất hiện 2 khái niệm là exploration (khám phá) và exploitation (khai thác), và cần cân bằng cả 2

Exploration (Khám phá):

• Khám phá là khi Agent thử những hành động mới hoặc chưa từng thử trước đó để tìm hiểu thêm về môi trường. Điều này có nghĩa là Agent có thể sẽ không chọn hành động có phần thưởng cao nhất dựa trên thông tin hiện tại mà thay vào đó thử các hành động chưa rõ kết quả.
• Lý do: Nếu Agent chỉ khai thác các hành động có phần thưởng cao hiện tại mà không khám phá các hành động khác, nó có thể bỏ lỡ những hành động tốt hơn ở tương lai. Môi trường có thể phức tạp và thay đổi, nên Agent cần tiếp tục tìm hiểu để có dữ liệu đầy đủ.

Exploitation (Khai thác):

• Khai thác là khi Agent chọn hành động dựa trên thông tin mà nó đã học được để tối ưu hóa phần thưởng. Trong trường hợp này, Agent chọn hành động mà nó tin là có phần thưởng cao nhất dựa trên những gì nó đã trải nghiệm.
• Lý do: Sau khi đã tích lũy đủ thông tin về môi trường, Agent cần tập trung khai thác các hành động đã được biết là có lợi để tối đa hóa phần thưởng trong dài hạn.

Tại sao cần có cả hai?

• Cân bằng: Nếu chỉ khai thác mà không khám phá, Agent có thể rơi vào cái gọi là local optimum (cực đại cục bộ) mà bỏ lỡ cơ hội đạt được global optimum (cực đại toàn cục), tức là giải pháp tốt nhất. Mặt khác, nếu chỉ khám phá mà không khai thác, Agent sẽ không thể tận dụng những gì nó đã học được, dẫn đến không tối ưu hóa phần thưởng.

Ví dụ:

• Exploration: Bạn đi ăn ở một nhà hàng mới mà bạn chưa bao giờ thử, hy vọng tìm được món ăn ngon hơn.
• Exploitation: Bạn quay lại một nhà hàng quen thuộc mà bạn biết chắc món ăn ở đó rất ngon.

Trong thực tế, các thuật toán như epsilon-greedy sử dụng một chiến lược kết hợp cả khám phá và khai thác, cho phép Agent thực hiện phần lớn các hành động khai thác nhưng đôi khi vẫn khám phá những hành động mới với một xác suất nhỏ (epsilon).

Trong Q-learning, ở giai đoạn đầu, giá trị epsilon thường lớn để xác xuất Exploration xuất hiện nhiều, qua mỗi lần lặp, Agent càng ngày càng tự tin với các giá trị học được đã được cập nhật ở Q table, nên giá trị Exploration ở các lần lặp sau sẽ giảm bớt, nhỏ đần, từ đó xác xuất chọn action từ Q table sẽ lớn hơn.

Measuring the Rewards

Sau khi thực hiện hành động, chúng ta sẽ thu được kết quả và phần thưởng

Có nhiều cách cho thưởng, tùy , một dạng đơn giản nhất đó là

Nếu về đích , +1 điểm thưởng

Nếu thất bại, chưa về đích , 0 điểm

Update Q Table

Trong Q-learning, khi một Agent cập nhật giá trị Q cho một cặp trạng thái-hành động, quá trình này dựa trên sự kết hợp giữa giá trị Q cũ (former Q-value) và giá trị Q mới ước tính (new Q-value estimation). Đây là hai khía cạnh quan trọng của công thức cập nhật Q-value trong Q-learning:

Former Q-value (Giá trị Q cũ):

• Đây là giá trị Q hiện tại cho một cặp trạng thái-hành động cụ thể mà Agent đã ghi nhận trước đó. Nó thể hiện phần thưởng kỳ vọng mà Agent đã tính toán từ các lần tương tác trước đó với môi trường.

• Trong công thức cập nhật Q-learning:

$$ [ Q(s, a) \leftarrow Q(s, a) + \alpha \left( r + \gamma \max_a’ Q(s’, a’) - Q(s, a) \right) ] $$

Phần $( Q(s, a) )$ bên phải của dấu mũi tên là giá trị Q cũ.

New Q-value estimation (Giá trị Q mới ước tính): Đây là giá trị Q được cập nhật dựa trên phần thưởng vừa nhận được và dự đoán phần thưởng trong tương lai (dựa trên trạng thái tiếp theo và hành động tốt nhất có thể thực hiện).

Phần ( r + \gamma \max_a’ Q(s’, a’) ) trong công thức là phần thưởng mới và giá trị kỳ vọng của trạng thái tiếp theo. Điều này đại diện cho sự ước tính mới về phần thưởng nếu Agent tiếp tục thực hiện chính sách tối ưu từ trạng thái tiếp theo.

Alpha (α) - Hệ số học (Learning Rate):

-Ý nghĩa: Alpha kiểm soát mức độ mà các giá trị Q hiện tại được cập nhật bằng thông tin mới. Nó quyết định xem tác nhân sẽ học nhanh chóng từ các trải nghiệm mới hay học dần dần.

• Phạm vi: $( 0 \leq \alpha \leq 1 )$

• Giải thích:

• α = 1: Tác nhân hoàn toàn bỏ qua thông tin cũ và chỉ dùng giá trị mới ước tính. Nghĩa là mỗi khi có một trải nghiệm mới, giá trị Q cũ sẽ được thay thế hoàn toàn.

• α = 0: Tác nhân hoàn toàn không cập nhật giá trị Q cũ, có nghĩa là tác nhân sẽ không học gì từ trải nghiệm mới.

• Giá trị trung gian (0 < α < 1): Kết hợp giữa giá trị Q cũ và giá trị mới, tức là học tập từ cả kinh nghiệm cũ và mới một cách từ từ. Trong thực tế, alpha thường được chọn là một giá trị nhỏ (ví dụ: 0.1 hoặc 0.01) để tác nhân có thể học ổn định và không thay đổi quá đột ngột.

Gamma (γ) - Hệ số chiết khấu (Discount Factor):

• Ý nghĩa: Gamma xác định mức độ mà tác nhân coi trọng các phần thưởng trong tương lai. Nó cho phép tác nhân cân nhắc giữa việc nhận phần thưởng ngay lập tức và phần thưởng tiềm năng trong tương lai.
• Phạm vi: $( 0 \leq \gamma \leq 1 )$
• Giải thích:
  • γ = 0: Tác nhân chỉ quan tâm đến phần thưởng tức thì mà không để ý đến phần thưởng tương lai. Điều này khiến tác nhân chỉ tối ưu hóa cho lợi ích ngắn hạn.
  • γ = 1: Tác nhân đánh giá phần thưởng hiện tại và tương lai một cách cân bằng, tức là phần thưởng trong tương lai xa có cùng trọng số với phần thưởng ngay lập tức.
  • Giá trị trung gian (0 < γ < 1): Đây là lựa chọn phổ biến trong các bài toán thực tế. Gamma sẽ giảm dần giá trị của các phần thưởng càng xa trong tương lai, nhưng vẫn đảm bảo rằng tác nhân quan tâm đến việc tối đa hóa phần thưởng dài hạn.

Tóm lại, vai trò của α và γ:

• Alpha (α): Điều chỉnh tốc độ học, tức là mức độ cập nhật giá trị Q dựa trên thông tin mới.
• Gamma (γ): Điều chỉnh sự ưu tiên giữa phần thưởng hiện tại và phần thưởng trong tương lai.

Cả hai tham số này ảnh hưởng trực tiếp đến hiệu quả học tập của tác nhân trong môi trường và cần được tinh chỉnh phù hợp cho từng bài toán cụ thể.

Double Deep Q-Network

Sau khi tìm hiểu Q learning, chúng ta sẽ tìm hiểu 1 cải tiến của nó là Double Deep Q-Network

Double Deep Q-Network (DDQN) là một cải tiến của Q-learning (cụ thể là DQN - Deep Q-Network) nhằm giải quyết một số vấn đề quan trọng trong quá trình học tập. So với Q-learning, DDQN giúp giảm sự thiên lệch ước lượng (overestimation bias) và cải thiện độ chính xác trong việc chọn hành động. Dưới đây là chi tiết về các cải tiến của DDQN so với Q-learning:

1. Vấn đề của Q-learning (Overestimation Bias):

• Q-learning tiêu chuẩn (bao gồm cả DQN, phiên bản mở rộng với mạng nơ-ron) có xu hướng gặp phải vấn đề gọi là thiên lệch ước lượng quá mức (overestimation bias). Khi tính toán giá trị Q, Q-learning chọn hành động dựa trên giá trị Q lớn nhất trong Q-table (hoặc mạng Q trong DQN). Tuy nhiên, do sự ngẫu nhiên trong môi trường và các lỗi nhỏ khi ước tính, tác nhân có thể đánh giá quá cao giá trị Q của một số hành động.

• Công thức cập nhật Q-learning:

$$ [ Q(s, a) \leftarrow Q(s, a) + \alpha \left( r + \gamma \max_a Q(s’, a’) - Q(s, a) \right) ] $$

Trong đó, ( \max_a Q(s’, a’) ) chọn hành động có giá trị Q cao nhất cho trạng thái tiếp theo ( s’ ). Việc sử dụng cùng một mạng để chọn và đánh giá hành động này có thể dẫn đến thiên lệch khi các giá trị Q bị phóng đại một cách không chính xác.

2. Cải tiến của Double Deep Q-Network (DDQN):

• DDQN được phát triển để khắc phục vấn đề thiên lệch ước lượng quá mức trong Q-learning/DQN bằng cách tách biệt việc chọn hành động và đánh giá giá trị của hành động. Trong DDQN, hai mạng nơ-ron khác nhau được sử dụng để thực hiện hai nhiệm vụ này:

  • Mạng chính (main network): Được sử dụng để chọn hành động tốt nhất cho trạng thái tiếp theo.
  • Mạng mục tiêu (target network): Được sử dụng để ước tính giá trị của hành động đó.

• Công thức cập nhật DDQN:

$$ [ Q(s, a) \leftarrow Q(s, a) + \alpha \left( r + \gamma Q_{\text{target}}(s’, \arg\max_a Q_{\text{main}}(s’, a’)) - Q(s, a) \right) ] $$

Trong đó:

• ( Q_{\text{main}}(s’, a’) ): Mạng chính được dùng để chọn hành động tốt nhất tại trạng thái ( s’ ) (tức là hành động có giá trị Q cao nhất).

• ( Q_{\text{target}}(s’, a’) ): Mạng mục tiêu được dùng để đánh giá giá trị Q của hành động đó.

• Ý tưởng chính: Bằng cách sử dụng hai mạng riêng biệt (một để chọn hành động, một để đánh giá), DDQN tránh được việc phóng đại giá trị Q do cùng một mạng chọn và đánh giá hành động trong Q-learning/DQN tiêu chuẩn. Điều này giúp giảm thiên lệch và cải thiện hiệu quả học tập.

3. Lợi ích của DDQN so với DQN/Q-learning:

• Giảm thiên lệch ước lượng (Overestimation Bias): DDQN cải thiện độ chính xác của ước tính giá trị Q bằng cách tách rời nhiệm vụ chọn và đánh giá hành động.
• Học tập ổn định hơn: Việc giảm thiên lệch giúp DDQN ổn định hơn trong quá trình học tập, đặc biệt khi các tác nhân tương tác với những môi trường phức tạp và ngẫu nhiên.
• Cải thiện độ hội tụ (Convergence): Do các giá trị Q không bị phóng đại một cách sai lầm, quá trình học tập của tác nhân trở nên hiệu quả và nhanh hơn, giúp hệ thống hội tụ về giải pháp tốt hơn.

4. Ví dụ trực quan về sự khác biệt:

• DQN: Nếu có hai hành động A và B, và DQN đánh giá hành động A có giá trị Q là 10 (thực tế là 8) và B là 9 (thực tế là 7), DQN sẽ chọn A vì $( \max(10, 9) = 10 )$. Tuy nhiên, giá trị thực của A chỉ là 8, dẫn đến đánh giá sai.
• DDQN: Trong DDQN, mạng chính sẽ chọn A, nhưng mạng mục tiêu sẽ đánh giá A dựa trên giá trị thực tế của nó, làm giảm khả năng phóng đại giá trị và giúp lựa chọn chính xác hơn.

5. Tóm lại:

• Q-learning/DQN: Chỉ dùng một mạng để chọn và đánh giá, dễ gặp tình trạng ước lượng quá cao (overestimation).
• DDQN: Tách biệt việc chọn và đánh giá hành động, giúp giảm thiên lệch và cải thiện quá trình học tập.

Thực hành với chương trình mario

Ở bài thực hành này, mình kế thừa code từ blog chính chủ của pytorch

Train trò chơi mario sử dụng Reinforcement Learning

các nguyên liệu cần thiết

1pip install gym==0.22.0 --update
2pip install gym-super-mario-bros==7.4.0
3pip install tensordict==0.3.0
4pip install torchrl==0.3.0

Các bạn lưu ý sử dụng đúng phiên bản để khỏi bị lỗi

Environment

Khởi tạo môi trường

Trong trò chơi mario, chúng ta có nhiều đối tượng khi chơi, là cây nấm , các ống trụ màu xanh, các viên gạch …

Khi chúng ta thực hiện một hành động ( ấn nút trên Joypad ), trò chơi sẽ phản hồi lại next_state là hình ảnh của khung hình sau khi ta nhấn nút, reward, done, info

 1
 2env = gym_super_mario_bros.make("SuperMarioBros-1-1-v0")
 3
 4# Limit the action-space to
 5#   0. walk right
 6#   1. jump right
 7env = JoypadSpace(env, [["right"], ["right", "A"]])
 8
 9env.reset()
10next_state, reward, done, info = env.step(action=0)
11print(f"{next_state.shape},\n {reward},\n {done},\n {info}")
12
13
14(240, 256, 3),
15 0.0,
16 False,
17 {'coins': 0, 'flag_get': False, 'life': 2, 'score': 0, 'stage': 1, 'status': 'small', 'time': 400, 'world': 1, 'x_pos': 40, 'y_pos': 79}

Xử lý dữ liệu

Dữ liệu của state là một hình có kích thước (240, 256, 3) , hệ bgr, chúng ta sẽ convert về GrayScale (1 ,240, 256) và resize về hình vuông có kích thước 84x84 để tăng thời gian xử lý . Các bạn có thể thay đổi thành 112x112 hoặc 96x96 tùy thích.

Ngoài ra, do hình trước khi ấn và hình sau khi ấn nút thường sẽ gần gần giống nhau, nên chúng ta sẽ thêm một lớp SkipFrame, hiểu đúng như tên, chúng ta sẽ cộng dồn giá trị reward để trả ra cho mô hình thực hiện cập nhật trọng số. Ví dụ SkipFrame(4), nghĩa là ta sẽ cộng dồn giá trị reward của 4 hình liên tiếp thành tổng reward và cập nhật trọng số, cái này giúp cho mô hình chạy nhanh hơn xíu mà vẫn đảm bảo thông tin, tất nhiên số lượng frame bị skip cần be bé thôi

Chúng ta sẽ tạo các lớp , implement từ gym.Wrapper

 1
 2class SkipFrame(gym.Wrapper):
 3    def __init__(self, env, skip):
 4        """Return only every `skip`-th frame"""
 5        super().__init__(env)
 6        self._skip = skip
 7
 8    def step(self, action):
 9        """Repeat action, and sum reward"""
10        total_reward = 0.0
11        for i in range(self._skip):
12            # Accumulate reward and repeat the same action
13            obs, reward, done, trunk, info = self.env.step(action)
14            total_reward += reward
15            if done:
16                break
17        return obs, total_reward, done, trunk, info
18
19
20class GrayScaleObservation(gym.ObservationWrapper):
21    def __init__(self, env):
22        super().__init__(env)
23        obs_shape = self.observation_space.shape[:2]
24        self.observation_space = Box(low=0, high=255, shape=obs_shape, dtype=np.uint8)
25
26    def permute_orientation(self, observation):
27        # permute [H, W, C] array to [C, H, W] tensor
28        observation = np.transpose(observation, (2, 0, 1))
29        observation = torch.tensor(observation.copy(), dtype=torch.float)
30        return observation
31
32    def observation(self, observation):
33        observation = self.permute_orientation(observation)
34        transform = T.Grayscale()
35        observation = transform(observation)
36        return observation
37
38
39class ResizeObservation(gym.ObservationWrapper):
40    def __init__(self, env, shape):
41        super().__init__(env)
42        if isinstance(shape, int):
43            self.shape = (shape, shape)
44        else:
45            self.shape = tuple(shape)
46
47        obs_shape = self.shape + self.observation_space.shape[2:]
48        self.observation_space = Box(low=0, high=255, shape=obs_shape, dtype=np.uint8)
49
50    def observation(self, observation):
51        transforms = T.Compose(
52            [T.Resize(self.shape, antialias=True), T.Normalize(0, 255)]
53        )
54        observation = transforms(observation).squeeze(0)
55        return observation
56
57
58# Apply Wrappers to environment
59env = SkipFrame(env, skip=4)
60env = GrayScaleObservation(env)
61env = ResizeObservation(env, shape=84)
62
63env = FrameStack(env, num_stack=4)

Cuối cùng, chúng ta sẽ đóng các khai báo trên vào một FrameStack với số lượng lớp là 4, nghĩa là chúng ta sẽ đưa vào 4 hình có kích thước (240, 256, 3), kết quả là hình có kích thươc (4, 84, 84)

Agent

Chúng ta chơi mario, nên tạo 1 Agent tên là mario , theo lý thuyết, chúng ta sẽ có các hành động cho agent

• Act : Trả về 1 hành động tối ưu , trong danh sách các hành động dựa trên hình ảnh hiệnt tại

• Remember experiences. Experience = (current state, current action, reward, next state). Mario sẽ lưu lại các hành động (cache) và nhớ lại các hành động của mình để rút ra bài học

• Learn: Cập nhật trọng số

 1
 2class Mario:
 3    def __init__():
 4        pass
 5
 6    def act(self, state):
 7        """Given a state, choose an epsilon-greedy action"""
 8        pass
 9
10    def cache(self, experience):
11        """Add the experience to memory"""
12        pass
13
14    def recall(self):
15        """Sample experiences from memory"""
16        pass
17
18    def learn(self):
19        """Update online action value (Q) function with a batch of experiences"""
20        pass

Act

Khi chơi mario, hành động chúng ta sẽ thực hiện sẽ là lấy ngẫu nhiên 1 hành động trong tập lệnh (explore), hoặc là thực hiện lệnh tối ưu do mô hình gợi ý (exploit). Để đạt được tính năng này, chúng ta sẽ sử dụng exploration_rate để điều khiển xác xuất chọn explore hay exploit.

Ngoài ra, do là mô hình AI, nên chúng ta cần xây dựng một lớp CNN tên là MarioNet để hàm learn cập nhật trọng số

 1
 2class Mario:
 3    def __init__(self, state_dim, action_dim, save_dir):
 4        self.state_dim = state_dim
 5        self.action_dim = action_dim
 6        self.save_dir = save_dir
 7
 8        self.device = "cuda" if torch.cuda.is_available() else "cpu"
 9
10        # Mario's DNN to predict the most optimal action - we implement this in the Learn section
11        self.net = MarioNet(self.state_dim, self.action_dim).float()
12        self.net = self.net.to(device=self.device)
13
14        self.exploration_rate = 1
15        self.exploration_rate_decay = 0.99999975
16        self.exploration_rate_min = 0.1
17        self.curr_step = 0
18
19        self.save_every = 5e5  # no. of experiences between saving Mario Net
20
21    def act(self, state):
22        """
23    Given a state, choose an epsilon-greedy action and update value of step.
24
25    Inputs:
26    state(``LazyFrame``): A single observation of the current state, dimension is (state_dim)
27    Outputs:
28    ``action_idx`` (``int``): An integer representing which action Mario will perform
29    """
30        # EXPLORE
31        if np.random.rand() < self.exploration_rate:
32            action_idx = np.random.randint(self.action_dim)
33
34        # EXPLOIT
35        else:
36            state = state[0].__array__() if isinstance(state, tuple) else state.__array__()
37            state = torch.tensor(state, device=self.device).unsqueeze(0)
38            action_values = self.net(state, model="online")
39            action_idx = torch.argmax(action_values, axis=1).item()
40
41        # decrease exploration_rate
42        self.exploration_rate *= self.exploration_rate_decay
43        self.exploration_rate = max(self.exploration_rate_min, self.exploration_rate)
44
45        # increment step
46        self.curr_step += 1
47        return action_idx

Remember

Phần này gồm 2 hàm là cache và recall. cache, hiểu đúng như tên, là lưu lại các giá trị state, next_state, action, reward, done. recall là lấy các giá trị đã được nhớ ra

 1
 2class Mario(Mario):  # subclassing for continuity
 3    def __init__(self, state_dim, action_dim, save_dir):
 4        super().__init__(state_dim, action_dim, save_dir)
 5        self.memory = TensorDictReplayBuffer(storage=LazyMemmapStorage(100000, device=torch.device("cpu")))
 6        self.batch_size = 32
 7
 8    def cache(self, state, next_state, action, reward, done):
 9        """
10        Store the experience to self.memory (replay buffer)
11
12        Inputs:
13        state (``LazyFrame``),
14        next_state (``LazyFrame``),
15        action (``int``),
16        reward (``float``),
17        done(``bool``))
18        """
19        def first_if_tuple(x):
20            return x[0] if isinstance(x, tuple) else x
21        state = first_if_tuple(state).__array__()
22        next_state = first_if_tuple(next_state).__array__()
23
24        state = torch.tensor(state)
25        next_state = torch.tensor(next_state)
26        action = torch.tensor([action])
27        reward = torch.tensor([reward])
28        done = torch.tensor([done])
29
30        # self.memory.append((state, next_state, action, reward, done,))
31        self.memory.add(TensorDict({"state": state, "next_state": next_state, "action": action, "reward": reward, "done": done}, batch_size=[]))
32
33    def recall(self):
34        """
35        Retrieve a batch of experiences from memory
36        """
37        batch = self.memory.sample(self.batch_size).to(self.device)
38        state, next_state, action, reward, done = (batch.get(key) for key in ("state", "next_state", "action", "reward", "done"))
39        return state, next_state, action.squeeze(), reward.squeeze(), done.squeeze()

Learn

Ở phần init trên, chúng ta có cái khai báo MarioNet, ở đây, chúng ta sử dụng mô hình DDQN - Double Q-learning https://arxiv.org/pdf/1509.06461

DDQN sử dụng hai CNN đặt tên là Q_online và Q_target. Hai mô hình cnn này độc lập với nhau

Chúng ta sẽ chia sẽ chung features của Q_online và Q_target, nhưng FC classifiers sẽ độc lập nhau, các giá trị trọng số của Q_target sẽ bị frozen để ngăng cập nhật trọng số từ backprop

 1
 2class MarioNet(nn.Module):
 3    """mini CNN structure
 4  input -> (conv2d + relu) x 3 -> flatten -> (dense + relu) x 2 -> output
 5  """
 6
 7    def __init__(self, input_dim, output_dim):
 8        super().__init__()
 9        c, h, w = input_dim
10
11        if h != 84:
12            raise ValueError(f"Expecting input height: 84, got: {h}")
13        if w != 84:
14            raise ValueError(f"Expecting input width: 84, got: {w}")
15
16        self.online = self.__build_cnn(c, output_dim)
17
18        self.target = self.__build_cnn(c, output_dim)
19        self.target.load_state_dict(self.online.state_dict())
20
21        # Q_target parameters are frozen.
22        for p in self.target.parameters():
23            p.requires_grad = False
24
25    def forward(self, input, model):
26        if model == "online":
27            return self.online(input)
28        elif model == "target":
29            return self.target(input)
30
31    def __build_cnn(self, c, output_dim):
32        return nn.Sequential(
33            nn.Conv2d(in_channels=c, out_channels=32, kernel_size=8, stride=4),
34            nn.ReLU(),
35            nn.Conv2d(in_channels=32, out_channels=64, kernel_size=4, stride=2),
36            nn.ReLU(),
37            nn.Conv2d(in_channels=64, out_channels=64, kernel_size=3, stride=1),
38            nn.ReLU(),
39            nn.Flatten(),
40            nn.Linear(3136, 512),
41            nn.ReLU(),
42            nn.Linear(512, output_dim),
43        )

Estimate

Do chúng ta có 2 lớp cnn, nên chúng ta cần xây 2 hàm Estimate

Với Q_online, chúng ta thực hiện infer, xong.

Với Q_target, giá trị reward hơi phức tạp một chút, phân tích chúng

chúng ta có giá trị reward hiện tại

Chúng ta cần kết hợp với reward của Q_target, nhưng action thì không biết, vậy nên chúng ta sẽ lấy action tối ưu từ Q_online với state hiện tại

 1
 2class Mario(Mario):
 3    def __init__(self, state_dim, action_dim, save_dir):
 4        super().__init__(state_dim, action_dim, save_dir)
 5        self.gamma = 0.9
 6
 7    def td_estimate(self, state, action):
 8        current_Q = self.net(state, model="online")[
 9            np.arange(0, self.batch_size), action
10        ]  # Q_online(s,a)
11        return current_Q
12
13    @torch.no_grad()
14    def td_target(self, reward, next_state, done):
15        next_state_Q = self.net(next_state, model="online")
16        best_action = torch.argmax(next_state_Q, axis=1)
17        next_Q = self.net(next_state, model="target")[
18            np.arange(0, self.batch_size), best_action
19        ]
20        return (reward + (1 - done.float()) * self.gamma * next_Q).float()

Cập nhật model

Sử dụng cnn, nên chúng ta cần định nghĩa là loss và hàm optimizer, sau khi update trọng số của Q_online, chúng ta sẽ cập nhật trọng số đó cho Q_target

 1
 2class Mario(Mario):
 3    def __init__(self, state_dim, action_dim, save_dir):
 4        super().__init__(state_dim, action_dim, save_dir)
 5        self.optimizer = torch.optim.Adam(self.net.parameters(), lr=0.00025)
 6        self.loss_fn = torch.nn.SmoothL1Loss()
 7
 8    def update_Q_online(self, td_estimate, td_target):
 9        loss = self.loss_fn(td_estimate, td_target)
10        self.optimizer.zero_grad()
11        loss.backward()
12        self.optimizer.step()
13        return loss.item()
14
15    def sync_Q_target(self):
16        self.net.target.load_state_dict(self.net.online.state_dict())

Save checkpoint

 1class Mario(Mario):
 2    def save(self):
 3        save_path = (
 4            self.save_dir / f"mario_net_{int(self.curr_step // self.save_every)}.chkpt"
 5        )
 6        torch.save(
 7            dict(model=self.net.state_dict(), exploration_rate=self.exploration_rate),
 8            save_path,
 9        )
10        print(f"MarioNet saved to {save_path} at step {self.curr_step}")

Gom vào hàm learn

 1
 2class Mario(Mario):
 3    def __init__(self, state_dim, action_dim, save_dir):
 4        super().__init__(state_dim, action_dim, save_dir)
 5        self.burnin = 1e4  # min. experiences before training
 6        self.learn_every = 3  # no. of experiences between updates to Q_online
 7        self.sync_every = 1e4  # no. of experiences between Q_target & Q_online sync
 8
 9    def learn(self):
10        if self.curr_step % self.sync_every == 0:
11            self.sync_Q_target()
12
13        if self.curr_step % self.save_every == 0:
14            self.save()
15
16        if self.curr_step < self.burnin:
17            return None, None
18
19        if self.curr_step % self.learn_every != 0:
20            return None, None
21
22        # Sample from memory
23        state, next_state, action, reward, done = self.recall()
24
25        # Get TD Estimate
26        td_est = self.td_estimate(state, action)
27
28        # Get TD Target
29        td_tgt = self.td_target(reward, next_state, done)
30
31        # Backpropagate loss through Q_online
32        loss = self.update_Q_online(td_est, td_tgt)
33
34        return (td_est.mean().item(), loss)

Play

Chúng ta thực hiện learn 40000 lần

 1
 2use_cuda = torch.cuda.is_available()
 3print(f"Using CUDA: {use_cuda}")
 4print()
 5
 6save_dir = Path("checkpoints") / datetime.datetime.now().strftime("%Y-%m-%dT%H-%M-%S")
 7save_dir.mkdir(parents=True)
 8
 9mario = Mario(state_dim=(4, 84, 84), action_dim=env.action_space.n, save_dir=save_dir)
10
11logger = MetricLogger(save_dir)
12
13episodes = 40000
14for e in range(episodes):
15
16    state = env.reset()
17
18    # Play the game!
19    while True:
20
21        # Run agent on the state
22        action = mario.act(state)
23
24        # Agent performs action
25        next_state, reward, done, trunc, info = env.step(action)
26
27        # Remember
28        mario.cache(state, next_state, action, reward, done)
29
30        # Learn
31        q, loss = mario.learn()
32
33        # Logging
34        logger.log_step(reward, loss, q)
35
36        # Update state
37        state = next_state
38
39        # Check if end of game
40        if done or info["flag_get"]:
41            break
42
43    logger.log_episode()
44
45    if (e % 20 == 0) or (e == episodes - 1):
46        logger.record(episode=e, epsilon=mario.exploration_rate, step=mario.curr_step)

Replay

Ở hàm này, mình load model lên và cho auto chơi, sau vài vòng lặp cũng sẽ về đích được :)

Ở đây, các bạn chú ý phiên bản gym 0.22.0, ở bài viết gốc họ xài gym 0.17.x nên không có hàm save video, phải tự viết lại, còn các bản cao hơn thì họ tách rõ biến done của env.step thành 2 biến nên nếu bạn nào xài code thì sẽ bị lỗi.

 1
 2import random, datetime
 3from pathlib import Path
 4
 5import gym
 6import gym_super_mario_bros
 7from gym.wrappers import FrameStack, GrayScaleObservation, TransformObservation
 8from nes_py.wrappers import JoypadSpace
 9
10from metrics import MetricLogger
11from agent import Mario
12from wrappers import ResizeObservation, SkipFrame
13
14
15word = 1
16state = 1
17env = gym_super_mario_bros.make(f'SuperMarioBros-{word}-{state}-v0')
18
19
20
21env = JoypadSpace(
22    env,
23    [['right'],
24    ['right', 'A']]
25)
26
27env = SkipFrame(env, skip=4)
28env = GrayScaleObservation(env, keep_dim=False)
29env = ResizeObservation(env, shape=84)
30env = TransformObservation(env, f=lambda x: x / 255.)
31env = FrameStack(env, num_stack=4)
32env = gym.wrappers.RecordVideo(env=env, video_folder="video", name_prefix=f"mario_-{word}-{state}")
33
34env.reset()
35
36
37
38# Start the recorder
39env.start_video_recorder()
40
41save_dir = Path('checkpoints') / "test"
42save_dir.mkdir(parents=True,exist_ok=True)
43
44checkpoint = Path('checkpoints/2024-10-12T14-02-01/mario_net_15.chkpt')
45mario = Mario(state_dim=(4, 84, 84), action_dim=env.action_space.n, save_dir=save_dir, checkpoint=checkpoint)
46mario.exploration_rate = mario.exploration_rate_min
47
48logger = MetricLogger(save_dir)
49
50episodes = 50
51
52for e in range(episodes):
53
54    state = env.reset()
55
56    while True:
57
58        env.render()
59
60        action = mario.act(state)
61
62        next_state, reward, done, info = env.step(action)
63
64        mario.cache(state, next_state, action, reward, done)
65        # print(next_state, reward, done, info)
66
67        logger.log_step(reward, None, None)
68
69        state = next_state
70
71        if done or info['flag_get']:
72            break
73
74    logger.log_episode()
75
76    if e % 20 == 0:
77        logger.record(
78            episode=e,
79            epsilon=mario.exploration_rate,
80            step=mario.curr_step
81        )
82
83env.close_video_recorder()
84
85# Close the environment
86env.close()

code chính chủ https://pytorch.org/tutorials/intermediate/mario_rl_tutorial.html

Kết quả

Đợi tầm 48h khi chạy bằng GPU, mình train bằng RTX 4060 TI 16G, khá lâu

Nếu train với phần cứng mạnh hơn, như RTX 4090, hoặc A100, hoặc đổi một model mạnh hơn như Proximal Policy Optimizatio, sẽ nhanh hơn

Model trên mình train với level 1, để chạy auto cho level 2,3… 32, mình phải chạy 32 lân train tương ứng cho mỗi level.

Mình thử để model chạy thử cho level 2,3 nhưng không về đích được, phải train lại

Phần tiếp theo, mình sẽ train thử model PPO thay DDQN

Tham khảo

https://arxiv.org/pdf/1509.06461

https://www.geeksforgeeks.org/what-is-reinforcement-learning/

https://pytorch.org/tutorials/intermediate/mario_rl_tutorial.html

https://github.com/yfeng997/MadMario

https://towardsdatascience.com/reinforcement-learning-101-e24b50e1d292

Cảm ơn các bạn đã theo dõi bài viết. Xin cảm ơn và hẹn gặp lại.