Ảnh chụp bởi marcos mayer

Phương pháp TRPO tương tự giống với Natural Policy Gradient nhưng nó hiệu quả trong việc tối ưu các chiến thuật lớn và phi tuyến tính như mạng nơ-ron. Sau khi hiểu được ba khái niệm cơ bản của TRPO trong phần trước bao gồm thuật toán MM, Vùng tin cậy và Importance Sampling, chúng ta sẽ cùng giải thích kỹ hơn về các khái niệm trong phần cuối cùng của bài viết về TRPO này.

Vấn đề về tối ưu hóa

Trong phần này, chúng ta sẽ xác định mục tiêu muốn tối ưu và sẽ xem xét về mặt toán học trước. Chúng ta sẽ tối ưu hóa điều gì? Phép tối ưu hóa chiến thuật π’ có thể được xây dựng lại như sau:

$maximize _{\pi '}\;J(\pi ')=maximize _{\pi '}\;J(\pi ')-J(\pi)$

Chúng ta thay đổi các ký hiệu để phù hợp và trùng khớp với các bài báo về phương pháp TRPO & PPO. Kí hiệu hàm phần thưởng thay đổi từ $\eta$ thành $J$ . $\pi '$ là biến số mà chúng ta muốn tối ưu hóa và $\pi$ là ký hiệu cho chiến thuật cũ. $J(\pi)$ , phần thưởng kỳ vọng cho chiến thuật cũ $\pi$ , là một hằng số và do đó sự thay đổi ở trên không làm thay đổi cách thức giải bài toán.

Hàm 𝓛

Bây giờ, chúng ta cần tìm hàm giới hạn dưới cho thuật toán MM. Số hạng đầu tiên của nó là 𝓛 được định nghĩa như sau:

$\mathcal{L} _{\pi}(\pi ')=\frac{1}{1-\gamma}E_{s\sim d^{\pi} | a\sim \pi \;}\left [ \frac{\pi '(a|s)}{\pi (a|s)}A^{\pi}(s,a) \right ]=E _{\tau \sim \pi}\left [\sum _{t=0}^{\infty}\gamma ^{t} \frac{\pi '(a|s)}{\pi (a|s)}A^{\pi}(s_{t},a_{t}) \right ]$

Trong đó:

$d^{\pi}(s)=(1-\gamma)\sum _{t=0}^{\infty}\gamma ^{t}P(s_{t}=s|\pi)$

d là phân phối cho trạng thái trong tương lai sẽ bị khấu hao. Nếu γ = 1, d là tần suất truy cập trạng thái (State visit frequency) theo chiến thuật π. A là hàm lợi ích (phần thưởng kỳ vọng đã điều chỉnh). Chúng ta có thể đơn giản xem 𝓛 như việc sử dụng phép Importance Sampling để ước tính hàm lợi ích.

Phụ lục A của bài báo TRPO đã đưa ra chứng minh và thiết lập ra một hàm đường ranh giới như sau:

$\left | J(\pi ')- (J(\pi)+\mathcal{L} _{\pi}(\pi ')) \right |\leq C\sqrt{E_{s\sim d ^{\pi}}\;\left [ D_{KL}(\pi '||\pi)[s] \right ]}$

trong đó D_KL là phép đo KL-divergence, đo mức chênh lệch giữa hai phân phối dữ liệu p và q. KL-divergence được định nghĩa như sau:

$D_{KL}(P||Q)=\sum _{x=1}^{N}P(x)log\frac{P(x)}{Q(x)}$

Sau một số điều chỉnh, đây là hàm giới hạn dưới cuối cùng M của chúng ta.

$J(\pi ')-J(\pi)\geq \mathcal{L}_{\pi}(\pi ')-C\sqrt{E_{s \sim d^{\pi}}\;\left | D_{KL}(\pi '||\pi)[s] \right |}$

Cho hàm mục tiêu như sau:

$maximize _{\pi '}\;J(\pi ')-J(\pi)$

Tóm lại, chúng ta sẽ sử dụng thuật toán MM để tối đa hóa:

$max_{\pi '}\mathcal{L}_{\pi}(\pi ')-C\sqrt{E_{s \sim d^{\pi}}\;\left [ D_{KL}(\pi '||\pi)[s] \right ]}$

Nguồn

Bất đẳng thức dưới đây sẽ rất quan trọng vì chúng ta có thể thiết lập sai số giới hạn trên cho phép để tính toán hàm mục tiêu. Điều này thiết lập một vùng tin cậy cho việc chúng ta để có thể tin tưởng vào kết quả được tính.

$J(\pi ')-J(\pi)\geq \mathcal{L}_{\pi}(\pi ')-C\sqrt{E_{s \sim d^{\pi}}\;\left [ D_{KL}(\pi '||\pi)[s] \right ]}$

Trong đó $C\sqrt{E_{s \sim d^{\pi}}\;\left [ D_{KL}(\pi '||\pi)[s] \right ]}$ là sai số giới hạn trên.

Thực tế, với hàm đối ngẫu Lagrangian, hàm mục tiêu của chúng ta về mặt toán học giống như hàm mục tiêu sau, sử dụng ràng buộc trong vùng tin cậy.

$max _{\pi '}\;\mathcal{L}_{\pi}(\pi ')$

$s.t \;\;E_{s\sim d^{\pi}}\left [ D_{KL}(\pi '||\pi)[s] \right ]\leq \delta$

Tóm tắt về Hàm mục tiêu

Chúng ta sẽ thiết lập hàm mục tiêu cần tối ưu hóa cho mỗi lần lặp MM. Mục tiêu đầu tiên được gọi là KL được hiệu chỉnh (KL penalized) và mục tiêu thứ hai được gọi là KL ràng buộc (KL constrained).

$max_{\pi '}\mathcal{L}_{\pi}(\pi ')-C\sqrt{E_{s \sim d^{\pi}}\;\left [ D_{KL}(\pi '||\pi)[s] \right ]}$

Hoặc

$max _{\pi '}\;\mathcal{L}_{\pi}(\pi ')$

$s.t \;\;E_{s\sim d^{\pi}}\left [ D_{KL}(\pi '||\pi)[s] \right ]\leq \delta$

Phép cải tiến đơn điệu được đảm bảo

Sức mạnh của TRPO, PPO và Natural Policy Gradient được xây dựng dựa trên khái niệm phép cải tiến đơn điệu được đảm bảo. Về mặt lý thuyết, chiến thuật sẽ cập nhật hoặc thay đổi trong mỗi lần lặp TRPO nhằm tạo ra một chiến thuật tốt hơn. Chúng ta có thể chứng minh:

$\mathcal{L}_{\pi}=0$

Số hạng R.H.S. dưới đây bằng 0 khi $\pi ' = \pi$ . Do đó, L.H.S. luôn luôn lớn hơn hoặc bằng 0.

$J(\pi ')-J(\pi)\geq \mathcal{L}_{\pi}(\pi ')-C\sqrt{E_{s\sim d^{\pi}}\left [ D_{KL}(\pi '||\pi)[s] \right ]}$

$\mathcal{L}_{\pi}(\pi)-C\sqrt{E_{s\sim d^{\pi}}\left [ D_{KL}(\pi '||\pi)[s] \right ]}=0$

$J(\pi ')-J(\pi)\geq 0$

Chiến thuật mới sẽ luôn tốt hơn chiến thuật cũ. Trên thực tế, chiến thuật mới sẽ có sự cải thiện tốt trong hàm mục tiêu thực hơn phép tính xấp xỉ cho hàm giới hạn dưới.

$J(\pi ')-J(\pi)\geq$ mức cải thiện trong M so với $\pi '$

Nguồn

Chúng ta có thể tính hàm lợi ích kỳ vọng cục bộ xung quanh chiến thuật hiện tại. Nhưng độ chính xác sẽ giảm khi chiến thuật mới và chiến thuật hiện tại chênh lệch nhau nhiều. Chúng ta có thể thiết lập một giới hạn trên cho sai số. Do đó, chúng ta có thể đảm bảo việc cải tiến chiến thuật, miễn là chúng ta tối ưu hóa được phép tính xấp xỉ cục bộ trong một vùng tin cậy. Nếu nằm bên ngoài vùng này, thì điều đó là không thể. Ngay cả khi nó có thể có giá trị được tính tốt hơn, phạm vi sai số của nó sẽ làm phá hỏng sự đảm bảo cho quá trình cải tiến. Với sự đảm bảo như vậy trong vùng tin cậy, chúng ta có thể xác định chiến thuật tối ưu lặp lại.

KL được hiệu chỉnh vs KL ràng buộc

Về mặt toán học, hàm mục tiêu của KL hiệu chỉnh và KL ràng buộc là đều giống nhau nếu chúng ta có nguồn tài nguyên tính toán vô hạn. Tuy nhiên, trên thực tế thì không phải vậy.

$max_{\pi '}\;\mathcal{L}_{\pi}(\pi)-C\sqrt{E_{s\sim d^{\pi}}\left [ D_{KL}(\pi '||\pi)[s] \right ]}$

Hoặc

$max_{\pi '}\mathcal{L}_{\pi}(\pi ')$

$s.t \;\;E_{s\sim d^{\pi}}\left [ D_{KL}(\pi '||\pi)[s] \right ]\leq \delta$

C sẽ đạt giá trị rất cao khi γ (hệ số khấu hao) gần bằng 1 và kích thước của bước Gradient tương ứng trở nên nhỏ hơn. Một giải pháp đó là thay đổi cả C và δ thành các siêu tham số có thể điều chỉnh được.

$C \infty \frac{\epsilon \gamma}{(1-\gamma)^{2}}$

Trên thực tế, δ là dễ điều chỉnh hơn nhiều so với C. δ đặt ra một ràng buộc cứng để kiểm soát các tình huống xấu trong vùng không gian chiến thuật. Nó hạn chế những thay đổi chiến thuật có thể làm phá hỏng quá trình. Việc điều chỉnh C thì khó hơn nhiều. Các kết quả thực nghiệm cho thấy nó không thể là một giá trị cố định mà phải là một giá trị có thể thay đổi được. Do đó, phương pháp ràng buộc trong vùng tin cậy được dùng phổ biến hơn.

Chúng ta đã xác định các vấn đề tối ưu hóa mà chúng ta muốn giải quyết. Tuy nhiên, việc giải quyết chúng không hề đơn giản. Tiếp theo, chúng ta sẽ xem xét cách Natural Policy Gradient giải quyết nó và cách mà phương pháp TRPO sẽ giải quyết các điểm yếu của nó.

Natural Policy Gradient

Natural Policy Gradient giải hàm mục tiêu sau đây:

$\pi _{k+1}=argmax _{\pi '}\;mathcal{L} _{\pi _{k}}(\pi ')$

$s.t \overline{D}_{KL}(\pi '||\pi_{k})\leq \delta$

Để giải được, chúng ta có thể sử dụng chuỗi Taylor để tăng cả hai hệ số ở trên lên đến bậc hai. Nhưng bậc hai của 𝓛 sẽ nhỏ hơn rất nhiều so với hệ số KL-divergence và do đó nó sẽ coi như bị bỏ, ta có được công thức như sau.

$\mathcal{L}_{\theta _{k}}(\theta) \approx g^{T}(\theta -\theta _{k})$

$\overline{D}_{KL}(\theta|\theta _{k})\approx \frac{1}{2}(\theta - \theta_{k})^{T}H(\theta -\theta _{k})$

$g\doteq \triangledown _{\theta}\mathcal{L}_{\theta_{k}}(\theta)|\theta_{k}$

$H\doteq \triangledown _{\theta}^{2}\overline{D}_{KL}(\theta|\theta_{k})|\theta_{k}$

Trong đó g là Policy Gradient và H đo độ nhạy của chiến thuật so với tham số của mô hình θ. Mục tiêu của chúng ta sẽ có dạng mới là:

$\theta_{k+1}=argmax _{\theta}\;g^{T}(\theta -\theta_{k})$

$s.t\;\frac{1}{2}(\theta -\theta_{k})^{T}H(\theta - \theta_{k})\leq \delta$

Đây là phương trình bậc 2 và được giải như sau:

$\theta_{k+1}=\theta _{k}+\sqrt{\frac{2\delta}{g^{T}H^{-1}g}}H^{-1}g$

Hệ số dưới đây sẽ ánh xạ các thay đổi mà ta muốn trong vùng không gian chiến thuật sang vùng không gian tham số tương ứng.

$H^{-1}g$

Nó đưa ra một giải pháp hiệu quả, bất kể chúng ta tham số hóa mô hình chiến thuật như thế nào. H có các giá trị khác nhau trong quá trình tham số hóa khác nhau. Nhưng nó sinh ra các thay đổi tham số $\triangle \theta$ mà có thể ánh xạ đến cùng thay đổi cho chiến thuật. Do đó, giải pháp của chúng ta sẽ là mô hình bất biến. Gradient Descent sẽ coi vùng không gian gần như là một mặt phẳng cục bộ. Điều này tương ứng với khoảng cách Euclide (khoảng cách căn bậc hai) mà chúng ta đã biết. Nếu chúng ta thay thế H ở trên bằng khoảng cách Euclide, chúng ta sẽ nhận ra rằng các cập nhật tham số không phải là mô hình bất biến. Các thay đổi tham số được tính toán cho các mô hình khác nhau sẽ tham chiếu đến các thay đổi cho chiến thuật khác nhau. Điều này giải thích lý do về mặt lý thuyết rằng tại sao Natural Policy Gradient tốt hơn Gradient Ascent.

Natural Policy Gradient là phương pháp tối ưu hóa bậc hai mà có độ chính xác cao hơn và hoạt động hiệu quả hơn bất kể mô hình được tham số hóa như thế nào (mô hình bất biến).

H là ma trận Hessian ở dạng tổng quát như sau:

$H=\triangledown ^{2}f=\begin{pmatrix}\frac{\partial ^{2}f_{1}}{\partial x_{1}^{2}} &\frac{\partial ^{2}f_{1}}{\partial x_{1}\partial x_{2}}&...&\frac{\partial^{2}f_{1}}{\partial x_{1} \partial x_{n}}\\ \frac{\partial ^{2}f_{2}}{\partial x_{1}^{2}} & \frac{\partial ^{2}f_{2}}{\partial x_{1}\partial x_{2}}&...&\frac{\partial^{2}f_{2}}{\partial x_{1} \partial x_{n}} \\ \vdots &\vdots &\ddots &\vdots \\ \frac{\partial ^{2}f_{m}}{\partial x_{1}^{2}} &\frac{\partial ^{2}f_{m}}{\partial x_{1}\partial x_{2}}&..&\frac{\partial^{2}f_{m}}{\partial x_{1}\partial x_{n}}\end{pmatrix}$

Ma trận trên đo độ cong (đạo hàm bậc hai) của hàm log cho xác suất xảy ra của chiến thuật. Có một vài hệ số đặc biệt là: Ma trận thông tin Fisher (FIM – Fisher Information Matrix). Nhiều bài viết sử dụng F thay vì H để đại diện cho FIM. Trong bài viết này, cả H và F đều tham chiếu đến FIM.

F cũng có thể được tính bằng biểu thức dưới đây:

$F=E_{s,a\sim \theta^{k}}\left [ \triangledown _{\theta}log\pi _{\theta}(a|s)|\theta _{k}\;\;\triangledown _{\theta}log\pi _{\theta}(a|s)|^{T}_{\theta_{k}} \right ]$

Sau đây là một đoạn giả mã (Là đoạn viết code sơ lược qua về ý tưởng). Chúng ta có thể lấy mẫu đường quỹ đạo từ chiến thuật hiện tại và sử dụng chúng để tính toán các hàm lợi ích. Sau đó, chúng ta tính toán Policy Gradient và chúng ta sử dụng phương trình trên để tính FIM.

Nguồn

Một số chú ý về Natural Policy Gradient

Việc tìm ra ma trận nghịch đảo của H là rất tốn kém nếu chiến thuật bị tham số hóa bởi quá nhiều tham số, đặc biệt là đối với mạng học sâu. Ngoài ra, ma trận nghịch đảo thường không ổn định về mặt số liệu (sai số dễ bị phóng đại do dữ liệu không chính xác).

Natural Policy Gradient dạng rút gọn

Natural Policy Gradient hay còn gọi là Truncated Natural Policy Gradient. Thay vì tìm ma trận nghịch đảo của FIM, chúng ta sẽ tính trực tiếp hệ số được kết hợp như sau:

$x_{k}\approx \widehat{H}^{-1}_{k}\widehat{g}_{k}$

Trong đó x được tính như sau:

$\widehat{H}_{k} x_{k} \approx \widehat{g}$

Chúng ta sẽ biến đổi phương trình này sang dạng tối ưu hóa cho phương trình bậc 2 như sau:

Giải $\;\; Ax=b$
Tương đương với
$minimize _{x}\;\; f(x)=\frac{1}{2}x^{T}Ax-b^{T}x$
Vì $f'(x)=Ax-b=0$

Tóm gọn lại, chúng ta sẽ biến đổi việc tối ưu hóa phương trình bậc 2 như bên dưới:

$min_{x\in R^{n}}\frac{1}{2}x^{T}Hx-g^{T}x$

Để tối ưu hóa, chúng ta sẽ áp dụng phương pháp Gradient liên hợp. Khái niệm của phương pháp này rất giống với Gradient Ascent nhưng có thể được thực hiện với ít vòng lặp hơn.

Trong Gradient Ascent, chúng ta luôn đi theo Gradient có độ dốc cao nhất. Trong ví dụ của chúng ta, chúng ta muốn tăng từ điểm màu vàng tới điểm màu đỏ. Giả sử bước đầu tiên chúng ta sẽ đi sang bên phải theo đường Gradient Contour. Để tiếp tục Gradient có độ dốc cao nhất một lần nữa, bước thứ hai có thể là đi lên và hơi dịch sang trái. Ở đây có một điều hơi khó hiểu là “Tại sao bước thứ hai lại đi sang trái?”

Nguồn

Nếu hàm mục tiêu là bậc hai, chúng ta có thể tránh được tính kém hiệu quả bằng cách sử dụng phương pháp Gradient liên hợp. Nếu mô hình có N tham số, chúng ta có thể tìm thấy điểm tối ưu tại điểm đi lên N. Trong lần di chuyển đầu tiên, chúng ta đi theo hướng Gradient tại điểm thấp nhất d và đạt tại điểm tối ưu theo hướng đó. Sau đó, đối với hướng tìm kiếm tiếp theo $d_{j}$ , nó sẽ là trực giao A với tất cả các hướng trước đó $d_{i}$ . Về mặt toán học, nó được biểu diễn như sau:

$d^{T}_{(i)}Ad_{(j)}=0$

Chúng ta có thể hình dung rằng các vectơ vuông góc với nhau sau một số phép biến đổi với A.

Nguồn

Gradient liên hợp là tìm ra được một hướng tìm kiếm mỗi khi A trực giao với tất cả các hướng trước đó. Vì vậy, chúng ta đảm bảo rằng chúng ta không xóa bỏ một phần của quá trình đã đạt được trước đó. Sau đó, chúng ta di chuyển theo hướng mới đến điểm tối ưu dọc theo đường tìm kiếm này.

Nguồn

Các vectơ này là độc lập với nhau và kéo dài trong một không gian N chiều. Vì vậy, chúng ta có thể giải quyết vấn đề nhiều nhất là n bước.Thuật toán này có độ phức tạp thấp hơn nhiều so với việc tính toán ma trận nghịch đảo của F. Bây giờ, chúng ta có thể tính

$x_{k}\approx\widehat{H}^{-1}_{k}\widehat{g}_{k}$

trong N vòng lặp. Truncated Natural Policy Gradient (TNPG) sử dụng phương pháp liên hợp bên dưới (phần gạch chân màu đỏ) để thay thế cho việc yêu cầu tính toán ma trận nghịch đảo của FIM.

Nguồn

Tối ưu hóa chiến thuật vùng tin cậy

Cuối cùng, chúng ta sẽ tổng hợp mọi thứ lại với nhau cho TRPO. TRPO áp dụng phương pháp Gradient liên hợp cho Natural Policy Gradient. Nhưng vẫn là chưa đủ. Vùng tin cậy cho Natural Policy Gradient là rất nhỏ. Chúng ta sẽ nới lỏng nó thành một giá trị có thể điều chỉnh lớn hơn. Ngoài ra, việc tính xấp xỉ bậc hai mà chúng ta thực hiện cũng làm giảm độ chính xác. Trong một số vòng lặp của quá trình đào tạo, hiệu suất có thể giảm sút. Một biện pháp để giảm thiểu là xác minh chiến thuât mới trước khi thực hiện thay đổi. Để làm điều đó, chúng ta sẽ xác minh:

KL-divergence cho chiến thuật mới $\theta$ là $\leq \delta$
$\mathcal{L} (\theta) \geq 0$ .

Nếu việc xác minh không thành công, chúng ta sẽ phân rã Natural Policy Gradient theo hệ số $\alpha$ với $0 < \alpha < 1$ cho đến khi các tham số mới đáp ứng yêu cầu ở trên.

Nguồn

Thuật toán TRPO

TRPO kết hợp Truncated Natural Policy Gradient (sử dụng Gradient liên hợp) và phương pháp tím kiếm theo một đường thẳng dò tìm (backtracking line search):

Nguồn

Các điểm yếu của phương pháp TRPO

TRPO tối thiểu hóa phương trình bậc hai để tính xấp xỉ ma trận nghịch đảo của F.

$min _{x\in R^{n}}\frac{1}{2}x^{T}Fx-g^{T}x$

Tuy nhiên, đối với mỗi lần cập nhật tham số của mô hình, chúng ta vẫn cần tính F. Điều này làm ảnh hưởng đến khả năng mở rộng:

Việc tính toán F mỗi lần cho mô hình chiến thuật hiện tại là rất tốn kém
Nó yêu cầu một loạt lớn các tập hợp quá trình Rollout để tính toán xấp xỉ giá trị F một cách chính xác

$F=E_{p(\tau)}\left [ \triangledown _{\theta}log \pi (a_{t}|s_{t}) (\triangledown _{\theta}log\pi(a_{t}|s_{t}))^{T}\right ]$

Nói chung, TRPO kém hiệu quả về việc lấy mẫu hơn so với các phương pháp Policy Gradient khác được đào tạo với các phép tối ưu hóa bậc một như Adam. Do vấn đề về khả năng mở rộng này, TRPO không được ứng dụng thực tế cho các mạng học sâu có quy mô lớn. Thay vào đó, phương pháp PPO & ACKTR được đưa ra để giải quyết những vấn đề này.

P/s: Mong mọi người luôn ủng hộ tek4 nhé!

« Trước

Mục lục

Tin tức liên quan

Leave a Reply Cancel Reply

Chuyên mục

Tin đọc nhiều

TRPO 2 – Tối ưu chiến thuật trong vùng tin cậy – Học tăng cường

Vấn đề về tối ưu hóa

Hàm 𝓛

Tóm tắt về Hàm mục tiêu

Phép cải tiến đơn điệu được đảm bảo

KL được hiệu chỉnh vs KL ràng buộc

Natural Policy Gradient

Natural Policy Gradient dạng rút gọn

Tối ưu hóa chiến thuật vùng tin cậy

Các điểm yếu của phương pháp TRPO

Tin tức liên quan

Leave a Reply Cancel Reply

Chuyên mục

Tin đọc nhiều